Lecture notes of Image Compression and Video Compression 2 Transform Coding Topics z Introduction to Image Compression z Transform Coding z Subband Coding Filter Banks z Haar Wavelet Transform z SPIHT EZW JPEG 2000 z Motion Compensation z Wireless Video Compression 2 Transform Coding z Why transform Coding z z Purpose of transformation is to convert the data into a form where compression is easier This transformation will transform the pixels which are correlated into a representation where they are decorrelated The new values are usually smaller on average than the original values The net effect is to reduce the redundancy of representation For lossy compression the transform coefficients can now be quantized according to their statistical properties producing a much compressed representation of the original image data 3 Transform Coding Block Diagram z Transmitter Original Image f j k Segment into n n Blocks z F u v Forward Transform F uv Quantization and Coder Channel Receiver Combine n n Blocks Reconstructed Image Inverse Transform f j k Decoder F u v F uv 4 How Transform Coders Work z Divide the image into 1x2 blocks z Typical transforms are 8x8 or 16x16 x1 x2 x1 x2 5 Joint Probability Distribution z Observe the Joint Probability Distribution or the Joint Histogram Probability x2 x1 6 Pixel Correlation in Image Amar z Rotate 45o clockwise Y1 cos 45o Y o Y2 sin 45 sin 45o X 1 cos 45o X 2 Before Rotation Source Image Amar After Rotation 7 Pixel Correlation Map in Amar coordinate distribution z z z z Upper Before Rotation Lower After Rotation Notice the variance of Y2 is smaller than the variance of X2 Compression apply entropy coder on Y2 8 Pixel Correlation in Image Lenna z Let s look at another example Y1 cos 45o Y o Y sin 45 2 Before Rotation sin 45o X 1 cos 45o X 2 Source Image Lenna After Rotation 9 Pixel Correlation Map in Lenna coordinate distribution z z z z Upper Before Rotation Lower After Rotation Notice the variance of Y2 is smaller than the variance of X2 Compression apply entropy coder on Y2 10 Rotation Matrix z Rotated 45 degrees clockwise cos 45o Y1 Y AX o Y2 sin 45 z sin 45o X 1 2 2 o cos 45 X 2 2 2 2 2 X 1 2 2 X 2 Rotation matrix A cos 45o A o sin 45 sin 45o 2 2 o cos 45 2 2 2 2 2 1 1 2 2 2 1 1 11 Orthogonal orthonormal Matrix z Rotation matrix is orthogonal z z z Futhermore the rotation matrix is orthonormal z z The dot product of a row with itself is nonzero The dot product of different rows is 0 The dot product of a row with itself is 1 Example 2 A 2 0 Ai A j 0 1 Ai A j 0 if i j else if i j else 1 1 1 1 12 Reconstruct the Image z z z z z Goal recover X from Y Since Y AX so X A 1Y Because the inverse of an orthonormal matrix is its transpose we have A 1 AT So Y A 1X ATX We have inverse matrix o cos 45 A 1 AT o sin 45 sin 45o 2 1 1 o cos 45 2 1 1 13 Energy Compaction Y1 Y Y2 z z X1 A X2 2 A 2 1 1 1 1 Rotation matrix A compacted the energy into Y1 Energy is the variance http davidmlane com hyperstat A16252 html 1 N xi 2 where is the mean N 1 i 1 z Given 4 2 2 1 1 4 X then Y AX 1 1 5 2 5 2 2 z z 9 6 364 1 0 707 The total variance of X equals to that of Y It is 41 Transformation makes Y2 0 707 very small z z z If we discard min X we have error 42 41 0 39 If we discard min Y we have error 0 7072 41 0 012 Conclusion we are more confident to discard min Y 14 Idea of Transform Coding z Transform the input pixels X0 X1 X2 Xn 1 into coefficients Y0 Y1 Yn 1 real values z z z Scalar quantize the coefficient z z z The coefficients have the property that most of them are near zero Most of the energy is compacted into a few coefficients This is bit allocation Important coefficients should have more quantization levels Entropy encode the quantization symbols 15 Forward transform 1D z z Get the sequence Y from the sequence X Each element of Y is a linear combination of elements in X n 1 Y j a j i X i j 0 1 L n 1 i 0 Y0 a 0 0 M M Yn 1 a n 1 0 L O L Basis Vectors a 0 n 1 X 0 M M a n 1 n 1 X n 1 Y AX The element of the matrix are also called the weight of the linear transform and they should be independent of the data except for the KLT transform 16 Choosing the Weights of the Basis Vector z z The general guideline to determine the values of A is to make Y0 large while remaining Y1 Yn 1 to be small The value of the coefficient will be large if weights aij reinforce the corresponding data items Xj This requires the weights and the data values to have similar signs The converse is also true Yi will be small if the weights and the data values to have dissimilar signs 17 Extracting Features of Data z z z Thus the basis vectors should extract distinct features of the data vectors and must be independent orthogonal Note the pattern of distribution of 1 and 1 in the matrix They are intended to pick up the low and high frequency components of data Normally the coefficients decrease in the order of Y0 Y1 Yn 1 So Y is more amenable to compression than X Y AX 18 Energy Preserving 1D z Another consideration to choose rotation matrix is to conserve energy z For example we have orthogonal matrix 1 1 1 1 1 1 1 1 A 1 1 1 1 1 1 1 1 4 6 X 5 2 17 3 Y AX 5 2 Energy before rotation 42 62 52 22 81 z Energy after rotation 172 32 5 2 12 324 z Energy changed z z Solution scale W by scale factor The scaling does not change the fact that most of the energy is concentrated at the low frequency components 19 Energy Preserving Formal Proof z z The sum of the squares of the transformed sequence is the same as the sum of the squares of the original sequence Most of the energy are concentrated in the low frequency coefficients Energy n 1 T Y Y Y i 2 i 1 AX T AX X T AT AX X T AT A X XTX n 1 Xi i 1 2 Orthonormal Matrix See page 12 20 …