CSEP 590Data CompressionAutumn 2007Wavelet Transform CodingPACWCSEP 590 - Lecture 9 - Autumn 2007 2Wavelet Transform• Wavelet Transform– A family of transformations that filters the data into low resolution data plus detail data.L LHHdetail subbandslow pass filterhigh pass filterimagewavelet transformed imageCSEP 590 - Lecture 9 - Autumn 2007 3Wavelet Transformed Barbara (Enhanced)DetailsubbandsLowresolutionsubbandCSEP 590 - Lecture 9 - Autumn 2007 4Wavelet Transformed Barbara(Actual)most of thedetails are smallso they are very dark.CSEP 590 - Lecture 9 - Autumn 2007 5Wavelet Transform Compressionwavelettransformimage(pixels)waveletcodingwaveletdecodinginversewavelettransformtransformed image (coefficients)bitstreamEncoderDecoderdistortedimagetransformed image(approx coefficients)Wavelet coder transmits wavelet transformed image in bit planeorder with the most significant bits first.CSEP 590 - Lecture 9 - Autumn 2007 6Bit Planes of Coefficients0 0 0 0 10 1 0 0 01 0 1 0 00 0 0 1 1...+ - + + +sign plane1234...Coefficients are normalized between –1 and 1CSEP 590 - Lecture 9 - Autumn 2007 7Why Wavelet Compression Works• Wavelet coefficients are transmitted in bit-plane order.– In most significant bit planes most coefficients are 0 so they can be coded efficiently.– Only some of the bit planes are transmitted. This is where fidelity is lost when compression is gained.• Natural progressive transmission...compressed bit planestruncated compressed bit planesCSEP 590 - Lecture 9 - Autumn 2007 8Rate-Fidelity Curve202224262830323436380.020.130.230.330.420.520.650.730.830.92bits per pixelPSNRSPIHT coded BarbaraThe more bit planes of the wavelet transformed image thatare sent the higher the fidelity.CSEP 590 - Lecture 9 - Autumn 2007 9Wavelet Coding Methods• EZW - Shapiro, 1993– Embedded Zerotree coding. • SPIHT - Said and Pearlman, 1996– Set Partitioning in Hierarchical Trees coding. Also uses “zerotrees”.• ECECOW - Wu, 1997– Uses arithmetic coding with context.• EBCOT – Taubman, 2000– Uses arithmetic coding with different context.• JPEG 2000 – new standard based largely on EBCOT• GTW – Hong, Ladner 2000– Uses group testing which is closely related to Golomb codes• PACW - Ladner, Askew, Barney 2003– Like GTW but uses arithmetic codingCSEP 590 - Lecture 9 - Autumn 2007 10Wavelet Transformwavelettransformimage(pixels)waveletcodingwaveletdecodinginversewavelettransformtransformed image (coefficients)bitstreamEncoderDecoderdistortedimagetransformed image(approx coefficients)A wavelet transform decomposes the image into a low resolutionversion and details. The details are typically very small so they canbe coded in very few bits.CSEP 590 - Lecture 9 - Autumn 2007 11One-Dimensional Average Transform (1)xyxyHow do we representtwo data points at lower resolution?(x+y)/2 (y-x)/2averagedetailCSEP 590 - Lecture 9 - Autumn 2007 12One-Dimensional Average Transform (2)xy(y-x)/2 = H(x+y)/2 = Llow pass filterhigh passfilterLHxyTransformInverse Transformx = L - Hy = L + HdetailCSEP 590 - Lecture 9 - Autumn 2007 13One-Dimensional Average Transform (3)LHLow Resolution VersionDetailNote that the low resolutionversion and the detail togetherhave the same number of values as the original.CSEP 590 - Lecture 9 - Autumn 2007 14One-Dimensional Average Transform (4)A BL = B[0..n/2-1]H = B[n/2..n-1]2ni01],A[2i21A[2i]21i]B[n/22ni01],A[2i21A[2i]21B[i]<≤++−=+<≤++=L HCSEP 590 - Lecture 9 - Autumn 2007 15One-Dimensional Average Inverse TransformB2ni0i],B[n/2B[i]1]A[2i2ni0i],B[n/2B[i]A[2i]<≤++=+<≤+−=L HACSEP 590 - Lecture 9 - Autumn 2007 16Two Dimensional Transform (1)L HLLHL HHLHhorizontaltransformverticaltransformTransform each rowTransform each columnin L and H3 detailsubbandslow resolutionsubbandCSEP 590 - Lecture 9 - Autumn 2007 17Two Dimensional Transform (1)LLHL HHLHhorizontaltransformverticaltransformTransform each row in LLTransform each column inLLL and HLLHL HHLHHLLLLLHL HHLHHLLL HHLLLLLL LHLL2 levels of transform gives 7 subbands.k levels of transform gives 3k + 1 subbands.CSEP 590 - Lecture 9 - Autumn 2007 18Two Dimensional Average Transformhorizontaltransformvertical transformnegative valueCSEP 590 - Lecture 9 - Autumn 2007 19Wavelet Transformed Image2 levels of wavelet transform1 low resolutionsubband6 detail subbandsCSEP 590 - Lecture 9 - Autumn 2007 20Wavelet Transform Details• Conversion to reals.– Convert gray scale to floating point.– Convert color to Y U V and then convert each band to floating point. Compress separately.• After several levels (3-8) of transform we have a matrix of floating point numbers called the wavelet transformed image (coefficients).CSEP 590 - Lecture 9 - Autumn 2007 21Wavelet Transforms• Technically wavelet transforms are special kinds of linear transformations. Easiest to think of them as filters.– The filters depend only on a constant number of values. (bounded support)– Preserve energy (norm of the pixels = norm of the coefficients)– Inverse filters also have bounded support.• Well-known wavelet transforms– Haar – like the average but orthogonal to preserve energy. Not used in practice.– Daubechies 9/7 – biorthogonal (inverse is not the transpose). Most commonly used in practice.CSEP 590 - Lecture 9 - Autumn 2007 22Haar Filterslow pass = high pass =2ni01],A[2i21A[2i]21i]B[n/22ni01],A[2i21A[2i]21B[i]<≤++−=+<≤++=low passhigh pass-0.8-0.6-0.4-0.200.20.40.60.80 1-0.8-0.6-0.4-0.200.20.40.60.80 121,2121,21−Want the sum of squares of the filter coefficients = 1CSEP 590 - Lecture 9 - Autumn 2007 23Daubechies 9/7 Filters-1-0.8-0.6-0.4-0.200.20.40.60.81-4 -3 -2 -1 0 1 2 3 4low pass filter-1-0.8-0.6-0.4-0.200.20.40.60.81-3 -2 -1 0 1 2 3high pass filter2ni0j],i A[2gi]B[n/22ni0j],i A[2hB[i]33jj44jj<≤+=+<≤+=∑∑−=−=low passhigh passhjgjreflection used near boundariesCSEP 590 - Lecture 9 - Autumn 2007 24Linear Time Complexity of 2D Wavelet Transform• Let n = number of pixels and let b be the number of coefficients in the filters.• One level of transform takes time – O(bn)• k levels of transform takes time proportional to– bn + bn/4 + ... + bn/4k-1 < (4/3)bn. • The wavelet transform is linear time when the filters have constant size.– The point of wavelets is to use constant size filters unlike many other transforms.CSEP 590 - Lecture 9 - Autumn 2007 25Wavelet Transformwavelettransformimage(pixels)waveletcodingwaveletdecodinginversewavelettransformtransformed image
View Full Document
Unlocking...