CSEP 590Data CompressionAutumn 2007Lossy Image CompressionTransform CodingJPEGCSEP 590 - Lecture 7 - Autumn 2007 2Lossy Image Compression Methods• DCT Compression– JPEG• Scalar quantization (SQ).• Vector quantization (VQ).• Wavelet Compression– SPIHT– UWIC (University of Washington Image Coder)– EBCOT– JPEG 2000CSEP 590 - Lecture 7 - Autumn 2007 3JPEG Standard• JPEG - Joint Photographic Experts Group– Current image compression standard. Uses discrete cosine transform, scalar quantization, and Huffman coding.• JPEG 2000 uses to wavelet compression.CSEP 590 - Lecture 7 - Autumn 2007 4BarbaraoriginalJPEGVQ Wavelet-SPIHT32:1 compression ratio.25 bits/pixel (8 bits)CSEP 590 - Lecture 7 - Autumn 2007 5JPEGCSEP 590 - Lecture 7 - Autumn 2007 6VQCSEP 590 - Lecture 7 - Autumn 2007 7SPIHTCSEP 590 - Lecture 7 - Autumn 2007 8OriginalCSEP 590 - Lecture 7 - Autumn 2007 9Images and the Eye• Images are meant to be viewed by the human eye (usually).• The eye is very good at “interpolation”, that is, the eye can tolerate some distortion. So lossy compression is not necessarily bad. The eye has more acuity for luminance (gray scale) than chrominance (color).– Gray scale is more important than color.– Compression is usually done in the YUV color coordinates, Y for luminance and U,V for color.– U and V should be compressed more than Y– This is why we will concentrate on compressing gray scale (8 bits per pixel) images.CSEP 590 - Lecture 7 - Autumn 2007 10Distortion• Lossy compression:• Measure of distortion is commonly mean squared error (MSE). Assume x has n real components (pixels). Encoder Decodercompressedoriginalxyxˆdecompressedxxˆ≠21)ˆ(1∑=−=niiixxnMSECSEP 590 - Lecture 7 - Autumn 2007 11PSNR• Peak Signal to Noise Ratio (PSNR) is the standard way to measure fidelity.• PSNR is measured in decibels (dB).– .5 to 1 dB is said to be a perceptible difference.– Decent images start at about 30 dB)(log10210MSEmPSNR =where m is the maximum value of a pixel possible. For gray scale images (8 bits per pixel) m = 255.CSEP 590 - Lecture 7 - Autumn 2007 12Rate-Fidelity Curve202224262830323436380.020.130.230.330.420.520.650.730.830.92bits per pixelPSNRSPIHT coded BarbaraProperties:- Increasing- Slope decreasingCSEP 590 - Lecture 7 - Autumn 2007 13PSNR is not EverythingPSNR = 25.8 dB PSNR = 25.8 dBVQCSEP 590 - Lecture 7 - Autumn 2007 14PSNR Reflects Fidelity (1)PSNR 25.8.63 bpp12.8 : 1VQCSEP 590 - Lecture 7 - Autumn 2007 15PSNR Reflects Fidelity (2)PSNR 24.2.31 bpp25.6 : 1VQCSEP 590 - Lecture 7 - Autumn 2007 16PSNR Reflects Fidelity (3)PSNR 23.2.16 bpp51.2 : 1 VQCSEP 590 - Lecture 7 - Autumn 2007 17Idea of Transform Coding• Transform the input pixels x0,x2,...,xN-1into coefficients c0,c1,...,cN-1(real values)– The coefficients have the property that most of them are near zero– Most of the “energy” is compacted into a few coefficients• Quantize the coefficients– This is where there is loss, since coefficients are only approximated– Important coefficients are kept at higher precision• Entropy encode the quantization symbolsCSEP 590 - Lecture 7 - Autumn 2007 18Decoding• Entropy decode the quantized symbols• Compute approximate coefficients c’0,c’1,...,c’N-1 from the quantized symbols.• Inverse transform c’0,c’1,...,c’N-1 to x’0,x’1,...,x’N-1which is a good approximation of the original x0,x2,...,xN-1.CSEP 590 - Lecture 7 - Autumn 2007 19Block Diagram of Transform Codingtransformquantization bit allocationentropy codingEncoderxcinversetransformc’ x’Decoderinputcoefficientssentropy decodingsymbolsbdecode symbolsbit streamcoefficientsssymbolsoutputCSEP 590 - Lecture 7 - Autumn 2007 20Mathematical Properties of Transforms• Linear Transformation - Defined by a real nxnmatrix A = (aij)• Orthonormality=1-N01-N01-N1,-N1,0-N1-N0,00ccxxaaaaMMLMMLT1AA=−(transpose)CSEP 590 - Lecture 7 - Autumn 2007 21Why Coefficients=++==−1-N01N1-N1,-N1,0-N01-N0,001-N01-N01-N1,-N1-N0,1,0-N00TxxcaacaaxxccaaaaxcAMMLMMMLMMLbasis vectorscoefficientsCSEP 590 - Lecture 7 - Autumn 2007 22Why Orthonomality• The energy of the data equals the energy of the coefficients∑∑−=−=======1N0i2iTTTTTTT1N0i2ixxxA)x(Ax)(Ax)A(x(Ax)(Ax)cccCSEP 590 - Lecture 7 - Autumn 2007 23Squared Error is Preserved with Orthonormal Transformations• In lossy coding we only send an approximation c’iof cibecause it takes fewer bits to transmit the approximation. Let ci= c’i+ εi∑∑∑−=−=−=−=======−=1N0i2iiTTTTTTTT1N0i2ii1N0i2i)x'(x)x'-(x)x'-(x)x'-A)(x(A)x'-(x))x'-)(A(xA)x'-((x ))x'-(A(x))x'-(A(x)Ax'-(Ax ) Ax'-(Ax )c'-(c)c'-(c)c'(cSquared error in original.CSEP 590 - Lecture 7 - Autumn 2007 24Compaction Example=−===⇒=−=−−0b2bb111121AAAAAAA111121A1T12orthonormalcompactionCSEP 590 - Lecture 7 - Autumn 2007 25Discrete Cosine Transform>+==0i if2N1)i(2jcosN20i if N1dij=.270598-.65328.65328-.270598.5.5-.5-.5.65328-.270598-.270598.65328.5.5.5.5DN = 4CSEP 590 - Lecture 7 - Autumn 2007 26Basis Vectors-1-0. 8-0. 6-0. 4-0. 200. 20. 40. 60. 810 1 2 3row 0row 3row 2row 1-1-0.8-0.6-0.4-0.200. 20. 40. 60. 810 1 2 3-1-0 . 8-0 . 6-0 . 4-0 . 200. 20. 40. 60. 810 1 2 3-1-0.8-0.6-0.4-0.200. 20. 40. 60. 810 1 2 3CSEP 590 - Lecture 7 - Autumn 2007 27Decomposition in Terms of Basis Vectors=−+−−+−+32103210xxxxc.270598.653281.653281-.270598c.5.5.5.5c.653281-.270598.270598.653281c.5.5.5.5DC coefficient AC coefficientsCSEP 590 - Lecture 7 - Autumn 2007 28Block TransformEach 8x8 block isindividually codedImageCSEP 590 - Lecture 7 - Autumn 2007 292-Dimensional Block Transformx00x01x02x03x10x11x12x13x20x21x22x23x30x31x32x33Block of pixels X=33323130232221201312111003020100aaaaaaaaaaaaaaaaATransformTmk1N0kkjim1N0mmk1N0kkj1N0mimmj1N0mimijik1N0kkjijAXACxaaxaaracxar=====∑∑∑∑∑∑−=−=−=−=−=−=Transform rowsTransform
View Full Document
Unlocking...