1CMU SCS15-826: Multimedia Databases and Data MiningCompression: JPEG, MPEG, fractalC. Faloutsos15-826 Copyright: C. Faloutsos (2005) 2CMU SCSOutlineGoal: ‘Find similar / interesting things’• Intro to DB• Indexing - similarity search• Data Mining15-826 Copyright: C. Faloutsos (2005) 3CMU SCSIndexing - Detailed outline• primary key indexing• ..• multimedia• Digital Signal Processing (DSP) tools• Image + video compression– JPEG– MPEG– Fractal compression15-826 Copyright: C. Faloutsos (2005) 4CMU SCSMotivation• Q: Why study (image/video) compression?15-826 Copyright: C. Faloutsos (2005) 5CMU SCSMotivation• Q: Why study (image/video) compression?• A1: feature extraction, for multimedia data mining• A2: (lossy) compression = data mining!15-826 Copyright: C. Faloutsos (2005) 6CMU SCSJPEG - specs• (Wallace, CACM April ‘91)• Goal: universal method, to compress– losslessly / lossily– grayscale / color (= multi-channer)• What would you suggest?215-826 Copyright: C. Faloutsos (2005) 7CMU SCSJPEG - grayscale - outline• step 1) 8x8 blocks (why?)• step 2) (Fast) DCT (why DCT?)• step 3) Quantize (fewer bits, lower accuracy)• step 4) encoding• DC: delta from neighbors• AC: in a zig-zag fashion, + Huffman encodingResult: 0.75-1.5 bits per pixel (8:1 compression) -sufficient quality for most appsloss15-826 Copyright: C. Faloutsos (2005) 8CMU SCSJPEG - grayscale - lossless• Predictive coding:• Then, encode prediction errorsResult: typically, 2:1 compressionCABXX= f ( A, B, C)eg. X= (A+B)/2, or?15-826 Copyright: C. Faloutsos (2005) 9CMU SCSJPEG - color/multi-channel• apps?• image components = color bands = spectral bands = channels• components are interleaved (why?)15-826 Copyright: C. Faloutsos (2005) 10CMU SCSJPEG - color/multi-channel• apps?• image components = color bands = spectral bands = channels• components are interleaved (why?)– to pipeline decompression with display8x8 ‘red’ block8x8 ‘green’ block8x8 ‘blue’ block15-826 Copyright: C. Faloutsos (2005) 11CMU SCSJPEG - color/multi-channel• tricky issues, if the sampling rates differ• Also, hierarchical mode of operation: pyramidal structure– sub-sample by 2– interpolate– compress the diff. from the predictions15-826 Copyright: C. Faloutsos (2005) 12CMU SCSJPEG - conclusions• grayscale, lossy: 8x8 blocks; DCT; quantization and encoding• grayscale, lossless: predictions• color (lossy/lossless): interleave bands315-826 Copyright: C. Faloutsos (2005) 13CMU SCSIndexing - Detailed outline• primary key indexing• ..• multimedia• Digital Signal Processing (DSP) tools• Image + video compression– JPEG– MPEG– Fractal compression15-826 Copyright: C. Faloutsos (2005) 14CMU SCSMPEG• (LeGall, CACM April ‘91)• Video: many, still images• Q: why not JPEG on each of them?15-826 Copyright: C. Faloutsos (2005) 15CMU SCSMPEG• (LeGall, CACM April ‘91)• Video: many, still images• Q: why not JPEG on each of them?• A: too similar - we can do better! (~3-fold)15-826 Copyright: C. Faloutsos (2005) 16CMU SCSMPEG - specs• ??15-826 Copyright: C. Faloutsos (2005) 17CMU SCSMPEG - specs• acceptable quality• asymmetric/symmetric apps (#compressions vs #decompressions)• Random access (FF, reverse)• audio + visual sync• error tolerance• variable delay / quality• editability15-826 Copyright: C. Faloutsos (2005) 18CMU SCSMPEG - approach• main idea: balance between inter-frame compression and random access• thus: compress some frames with JPEG (I-frames)– rest: prediction from motion, and interpolation– P-frames (predicted pictures, from I- or P-frames)– B-frames (interpolated pictures - never used as reference)415-826 Copyright: C. Faloutsos (2005) 19CMU SCSMPEG - approach• useful concept: ‘motion field’f1f215-826 Copyright: C. Faloutsos (2005) 20CMU SCSMPEG - conclusions• with the I-frames, we have a balance between– compression and– random access15-826 Copyright: C. Faloutsos (2005) 21CMU SCSIndexing - Detailed outline• primary key indexing• ..• multimedia• Digital Signal Processing (DSP) tools• Image + video compression– JPEG– MPEG– Fractal compression15-826 Copyright: C. Faloutsos (2005) 22CMU SCSFractal compression• ‘Iterated Function systems’ (IFS)• (Barnsley and Sloane, BYTE Jan. 88)• Idea: real objects may be self-similar, eg., fern leaf024681012-3 -2 -1 0 1 2 3Serie s 115-826 Copyright: C. Faloutsos (2005) 23CMU SCSFractal compression• simpler example: Sierpinski triangle.– has details at every scale -> DFT/DCT: not good– but is easy to describe (in English)• There should be a way to compress it very well!• Q: How??00.20.40.60.811.20 0.5 1 1.5 2 2.515-826 Copyright: C. Faloutsos (2005) 24CMU SCSFractal compression• simpler example: Sierpinski triangle.– has details at every scale -> DFT/DCT: not good– but is easy to describe (in English)• There should be a way to compress it very well!• Q: How??• A: several, affine transformations• Q: how many coeff. we need for a (2-d) affine transformation?515-826 Copyright: C. Faloutsos (2005) 25CMU SCSFractal compression• A: 6 (4 for the rotation/scaling matrix, 2 for the translation)• (x,y) -> w( (x,y) )= (x’, y’)– x’ = a x + b y + e– y’ = c x + d y + f• for the Sierpinski triangle: 3 such transformations - which ones?15-826 Copyright: C. Faloutsos (2005) 26CMU SCSFractal compression• A:a b c d e f p0.5 0 0 0.5 0 0 1/30.5 0 0 0.5 1 0 1/30.5 0 0 0.5 0.5 0.5 1/3w1w2w3prob (~ fractionof ink)15-826 Copyright: C. Faloutsos (2005) 27CMU SCSFractal compression• The above transformations ‘describe’ the Sierpinski triangle - is it the only one?• ie., how to de-compress?15-826 Copyright: C. Faloutsos (2005) 28CMU SCSFractal compression• The above transformations ‘describe’ the Sierpinski triangle - is it the only one?• A: YES!!!• ie., how to de-compress?• A1: Iterated functions (expensive)• A2: Randomized (surprisingly, it works!)15-826 Copyright: C. Faloutsos (2005) 29CMU SCSFractal compression• Sierpinski triangle: is the ONLY fixed point of the above 3 transformations:w1 w2w315-826 Copyright: C. Faloutsos (2005) 30CMU SCSFractal compression• We’ll get the Sierpinski triangle, NO MATTER what image we start from! (as long as it has at least one black pixel!)• thus, (one, slow) decompression algorithm:– start from a random image– apply the given transformations–