Lecture notes of Image Compression and Video Compression 4 Introduction to Wavelet Topics Introduction to Image Compression z Transform Coding z Subband Coding Filter Banks z Introduction to Wavelet Transform z Haar SPIHT EZW z Motion Compensation z Wireless Video Compression z 2 Contents History of Wavelet z From Fourier Transform to Wavelet Transform z Haar Wavelet z Multiresolution Analysis z General Wavelet Transform z EZW z SPIHT z 3 Wavelet Definition The wavelet transform is a tool that cuts up data functions or operators into different frequency components and then studies each component with a resolution matched to its scale Dr Ingrid Daubechies Lucent Princeton U 4 Wavelet Coding Methods z EZW Shapiro 1993 z z SPIHT Said and Pearlman 1996 z z Uses arithmetic coding with different context JPEG 2000 new standard based largely on EBCOT GTW Hong Ladner 2000 z z Uses arithmetic coding with context EBCOT Taubman 2000 z z z Set Partitioning in Hierarchical Trees coding Also uses zerotrees ECECOW Wu 1997 z z Embedded Zerotree coding Uses group testing which is closely related to Golomb codes UWIC Ladner Askew Barney 2003 z Like GTW but uses arithmetic coding 5 Comparison of Wavelet Based JPEG 2000 and DCT Based JPEG z JPEG2000 image shows almost no quality loss from current JPEG even at 158 1 compression 6 Introduction to Wavelets z the new computational paradigm wavelets eventually may swallow Fourier transform methods z a new approach to data crunching that if successful could spawn new computer architectures and bring about commercial realization of such difficult data compression tasks as sending images over telephone lines from New wave number crunching C Brown Electronic Engineering Times 11 5 90 7 Early History of Wavelet Theory z Roots found in a variety of disciplines z z 1910 Haar basis z z Contains the continuous wavelet transform 1971 A Rosenfeld and M Thurston z z z Short time Fourier transform with Gaussian window function 1964 Calderon s work on singular integral operators z z First wavelet 1946 The Gabor transform z z Mathematics Signal Processing Computer Vision Physics Multi resolution techniques invented in machine vision Multi resolution schemes inherent in the wavelet transform 1976 A Croiser D Estaban C Galand z z Quadrature mirror filter banks for speech coding Digital implementation of wavelets 8 Recent History of Wavelets z 1984 J Morlet and A Grossman z z z 1985 Meyer z z Developed multiresolution theory DWT wavelet construction techniques but still noncompact 1988 I Daubechies z z tried to prove that no orthogonal wavelet other than Haar exists found one by trial and error 1987 Mallat z z Invent term wavelets Apply them to the analysis of seismic signals Found compact orthogonal wavelets with arbitrary number of vanishing moments 2001 wavelet based JPEG2000 finalized 9 Model and Prediction z z Compression is PREDICTION There are many decomposition approaches to modeling the signal z z Every signal is a function Modeling is function representation approximation Model Model Probability Distribution Source Messages Encoder Probability Distribution Probability Estimates Transmission System Compressed Bit Stream Probability Estimates Original Source Decoder Messages 10 Methods of Function Approximation z Sequence of samples z z z z Pyramid hierarchical Polynomial Piecewise polynomials z z Finite element method Fourier Transform z z z Time domain Frequency domain Sinusoids of various frequencies Wavelet Transform z Time frequency domain 11 The Fourier Transform z z Analysis forward transform F u f t e j 2 ut dt Synthesis inverse transform f t F u e j 2 ut du z Forward transform decomposes f t into sinusoids z z F u represents how much of the sinusoid with frequency u is in f t Inverse transform synthesizes f t from sinusoids weighted by F u 12 The Fourier Transform Properties Linear Transform z Analysis decomposition of signals into sines and cosines has physical significance z z z tones vibrations Fast algorithms exist z The fast Fourier transform requires O nlogn computations 13 Problems With the Fourier Transform z z Fourier transform wellsuited for stationary signals signals that do not vary with time This model does not fit real signals well For time varying signals or signals with abrupt transitions the Fourier transform does not provide information on when transitions occur 14 Problems With the Fourier Transform z z z Fourier transform is a global analysis A small perturbation of the function at any one point on the time axis influences all points on the frequency axis and vise versa If a signal is received correctly for hours and gets corrupted for only a few second it totally destroys the signal The lack of time information makes Fourier transform error prone 15 Problems With the Fourier Transform z A qualitative explanation of why Fourier transform fails to capture time information is the fact that the set of basis functions sines and cosines are infinitely long and the transform picks up the frequencies regardless of where it appears in the signal z Need a better way to represent functions that are localized in both time and frequency 16 Uncertainty Principle Preliminaries for the STFT z The time and frequency domains are complimentary z z z z If one is local the other is global For an impulse signal which assumes a constant value for a very brief period of time the frequency spectrum is infinite If a sinusoidal signal extends over infinite time its frequency spectrum is a single vertical line at the given frequency We can always localize a signal or a frequency but we cannot do that simultaneously z If the signal has a short duration its band of frequency is wide and vice versa 17 Uncertainty Principle z Heisenberg s uncertainty principle was enunciated in the context of quantum physics which stated that the position and the momentum of a particle cannot be precisely determined simultaneously z This principle is also applicable to signal processing 18 Uncertainty Principle In Signal Processing Let g t be a function with the property Then g t 2 dt 1 1 t tm g t dt f f m G f dt 2 16 2 2 2 2 where t m f m denote average values of t and f and G f is the Fourier transform of g t 19 The STFT is an attempt to alleviate the problems with FT z It takes a non stationary signal and breaks it down into windows of signals for a specified short period of time and does Fourier transform on the window by considering the signal to consist of repeated windows
View Full Document
Unlocking...