1Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 1Multiresolution coding and wavelets Predictive (closed-loop) pyramids Open-loop (“Laplacian”) pyramids Discrete Wavelet Transform (DWT) Quadrature mirror filters and conjugate quadrature filters Lifting and reversible wavelet transform Wavelet theory Embedded zero-tree wavelet (EZW) codingBernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 2Interpolation error coding, IInterpolatorInterpolatorSubsampling• • •• • •Input pictureReconstructed pictureQQ++--++++InterpolatorSubsampling• •• •Coder includes Decoder Sample encoded in current stagePreviously coded sample2Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 3Interpolation error coding, IIsignals to be encodedoriginal imageBernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 4Predictive pyramid, IInterpolatorSubsamplingQQ++--++++InterpolatorInterpolatorFilteringFilteringSubsamplingInput pictureReconstructed picture• • •• • •• •• •Coder includes Decoder Sample encoded in current stage3Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 5Predictive pyramid, IINumber of samples to be encoded =1+1N+1N2+ ...⎛ ⎝ ⎞ ⎠ =NN−1x number of original image samplessubsampling factorBernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 6Predictive pyramid, IIIoriginal imagesignals to be encoded4Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 7Comparison:interpolation error coding vs. pyramid Resolution layer #0, interpolated to original size for displayInterpolation Error Coding PyramidBernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 8Comparison:interpolation error coding vs. pyramid Resolution layer #1, interpolated to original size for displayInterpolation Error Coding Pyramid5Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 9Comparison:interpolation error coding vs. pyramid Resolution layer #2, interpolated to original size for displayInterpolation Error Coding PyramidBernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 10Comparison:interpolation error coding vs. pyramid Resolution layer #3=(original)Interpolation Error Coding Pyramid6Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 11Open-loop pyramid (Laplacian pyramid)InterpolatorInterpolatorSubsamplingQ+Q+--FilteringFilteringInterpolatorInterpolatorSubsamplingInput pictureReconstructed picture• •• •• •• •Receiver Transmitter[Burt, Adelson, 1983]Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 12When multiresolution coding was a new idea . . . This manuscript is okay if compared to some of the weaker papers.[. . .] however, I doubt that anyone will ever use this algorithm again.Anonymous reviewer of Burt and Adelson‘s original paper, ca. 19827Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 13Cascaded analysis / synthesis filterbanks0h0g1g1h0g1g0h1hBernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 14Discrete Wavelet Transform Recursive application of a two-band filter bank to the lowpass band of the previous stage yields octave band splitting: Same concept can be derived from wavelet theory: Discrete Wavelet Transform (DWT)frequency8Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 152-d Discrete Wavelet Transformωxωyωxωyωxωyωxωyωxωyωxωyωxωyωxωyωxωy...etcBernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 162-d Discrete Wavelet Transform example9Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 172-d Discrete Wavelet Transform exampleBernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 182-d Discrete Wavelet Transform example10Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 192-d Discrete Wavelet Transform exampleBernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 202-d Discrete Wavelet Transform example11Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 21Two-channel filterbank Aliasing cancellation if :0110() ( )() ( )gz h zgz h z=−−=−[][]()00 1100 111ˆ() () () () () ()21()() ()()2xz h zg z h zg z xzhzgzhzgzxz=++− +− −Aliasing22220h1h0g1g()xz()ˆxzBernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 22Example: two-channel filter bank with perfect reconstruction Impulse responses, analysis filters:LowpassHighpass Impulse responses, synthesis filtersLowpassHighpass Mandatory in JPEG2000 Frequency responses:|g |0|h |01|h |1|g |π2π1200FrequencyFrequency response1131 1,,,,42224−−⎛⎞⎜⎟⎝⎠111,,424−⎛⎞⎜⎟⎝⎠11 311,, ,,42 2 24−⎛⎞⎜⎟⎝⎠111,,424⎛⎞⎜⎟⎝⎠“Biorthogonal 5/3 filters”“LeGall filters”12Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 23frequency ωClassical quadrature mirror filters (QMF) QMFs achieve aliasing cancellation by choosing  Highpass band is the mirror image of the lowpass band in the frequency domain Need to design only one prototype filter1010() ( )() ( )hz h zgz g z=−=−=−Example:16-tap QMF filterbank[Croisier, Esteban, Galand, 1976]Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 24Conjugate quadrature filters Achieve aliasing cancelation by Impulse responses Orthonormal subband transform! Perfect reconstruction: find power complementary prototype filter()()()1001111() ( )()hz gz fzhz gz zf z−−−=≡==−[Smith, Barnwell, 1986]Prototype filter[][][][] [ ]() ( )0011111khk g k fkhk g k f k+=−==−=− −+⎡⎤⎣⎦() ()222FFωωπ+±=13Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 25Lifting Analysis filters L “lifting steps” First step can be interpreted as prediction of odd samples from the even samplesK01λ2λ1Lλ−LλΣΣΣ ΣK1[]even samples 2xn[]odd samples 21xn+0low band y1high band y[Sweldens 1996]Bernd Girod: EE398A Image Communication I Multiresolution & Wavelets no. 26Lifting (cont.) Synthesis filters Perfect reconstruction (biorthogonality) is directly built into lifting structure Powerful for both implementation and filter/wavelet design1λ2λ1Lλ−LλΣΣΣ Σ[]even samples