Chapter 2 Background
Overview of wavelet based image compression system
The primary goal of any image compression technique is to reduce the number of bits needed to represent the image with little perceptible distortion. Subband coding using wavelets is one of the best performing techniques among di erent transform based image compression techniques. Figure 2.1 shows the block diagram of a wavelet based image compression system The rst three blocks (DWT, quantizer and entropy coder) compress the image data whereas the last two blocks (entropy decoder, inverse discrete wavelet transform (IDWT)) reconstruct the image from the compressed data.
The DWT performs an octave frequency subband decomposition of the image information. In its subband representation, an image is more compactly represented since most of its energy is concentrated in relatively few DWT coe cients.
The quantizer then performs quantization by representing the transform coe cients with a limited number of bits. Quantization represents lossy compression|some image information is irretrievably lost. A quantizer in a DWT-based coder exploits the spatial correlation in a wavelet-based, hierarchical scale-space decomposition.
The entropy coder follows the quantization stage in a wavelet based image compression sys-tem. Entropy coding is lossless; it removes the redundancy from the compressed bitstream. However, the typical performance improvement of 0.4-0.6 dB  achieved by entropy cod-ing is accompanied by higher computational complexity. We concentrate on the DWT and quantizer blocks and do not consider entropy coding for the results in this thesis. A detailed description of widely used entropy coding schemes is presented in .
The channel is the stored or transmitted compressed bitstream. We consider the channel to be noiseless|the received DWT coe cients are free from errors. The synthesis stage reconstructs the image from the compressed data. The entropy decoder and IDWT invert the operations performed by the entropy encoder and DWT, respectively.
One and two dimensional discrete wavelet transform
Perfect reconstruction lter bank
A perfect reconstruction (PR) lter bank consists of lters that divide the input signal into subbands; the synthesis part of a PR lter bank reconstructs the original signal by recombining the subbands. The structure of a one dimensional (1-D), two channel PR lter bank is shown in Figure 2.2. X (z) is the 1-D input signal. H (z) and G(z) are the z-transforms of the analysis lowpass and highpass lters; F (z) and J (z) are the z-transforms of the synthesis lowpass and highpass lters.
H (z) and G(z) split the input signal X (z) into two subbands: lowpass (XL(z)) and highpass (XH (z)). The lowpass and highpass subbands are then downsampled generating XLD (z) and XHD (z) respectively. The upsampled signals, XLU (z) and XHU (z) are ltered by the corre-sponding synthesis lowpass (F (z)) and highpass (J (z)) lters and then added to reconstruct the original signal X (z) that has an overall delay of d.
Although downsampling preserves the original sampling rate, it introduces aliasing since the magnitude response of the analysis lters are not ideal brickwall responses (they extend beyond their =2 symmetry point). Apart from aliasing distortion, there are amplitude and phase distortions associated with the analysis lters. The synthesis lters are chosen to cancel the errors introduced by the analysis lters and the relation between the analysis and synthesis is given by the two PR conditions: F (z)H (z) + J (z)G(z) = 2z d ;
Equation (2.1) is called the ‘no distortion’ condition while Equation (2.2) is called the ‘anti-aliasing’ condition. The relation between the analysis and synthesis lters changes slightly for orthogonal and biorthogonal PR lter banks.
In the case of an orthogonal PR lter bank, the synthesis lters are time reversed versions of the analysis lters: F (z) = H (z 1) and J (z) = G(z 1). Moreover, the highpass lter is the alternating ip of the lowpass lter, G(z) = z N H ( z 1), where N is the length of the lter. Thus, the entire lter bank is de ned by just one lter|the lowpass analysis lter(z).
In the case of a biorthogonal PR lter bank, the PR conditions are satis ed by choosing G(z) = F ( z) and J (z) = H ( z). Thus, the biorthogonal lter bank is de ned by two lters H (z) and F (z). It is possible to obtain linear phase lters for biorthogonal wavelets unlike the case for orthogonal wavelets, where all the lters are derived from one lter H (z).
One dimensional discrete wavelet transform
For any signal x(t) 2 L2(R), the orthogonal discrete wavelet transform (DWT) analysis and synthesis equations are given by:
Equations (2.3) and (2.5) are the orthogonal and biorthogonal analysis (DWT) equations; equations (2.4) and (2.6) are the orthogonal and biorthogonal synthesis (IDWT) equations.
(t) and (t) in equations (2.3) and (2.4) are the orthogonal scaling and wavelet functions; aj;k and bj;k are the corresponding scaling and wavelet coe cients. Biorthogonal wavelets have two sets of scaling and wavelet functions. (t) and (t) are the synthesis scaling and wavelet functions and ~(t) and ~(t) are the analysis scaling and wavelet functions. a~j;k and bj;k are the scaling and wavelet coe cients respectively; together they form the biorthogonal DWT coe cients of x(t).
A DWT is a representation of the signal x(t) in terms of scale (j) and shift (k). The lower limit, j = N , indicates that the DWT captures all the coarse(lowpass) information; the upper limit, (j = M 1), indicates that the DWT must stop at some nest scale. M N gives the number of decomposition levels in the DWT of x(t).
Fast wavelet transform
Mallat’s fast wavelet transform (FWT) gives a complete discrete time algorithm for deriving the DWT coe cients for some coarse scale from the coe cients at the next ner scale. Thus, the FWT avoids calculating the inner products as in equations (2.3) and (2.5). The PR bank as shown in Figure 2.2 is used to compute the FWT and IFWT (inverse fast wavelet transform). H (z) corresponds to the scaling function; G(z) corresponds to the wavelet function. The orthogonal FWT and IFWT are given by equations (2.7) and (2.8); the corresponding biorthogonal FWT and IFWT are given by equations (2.9) and (2.10).
1.2 Previous work
1.3 Signicance of this work
1.4 Organization of this thesis
2.1 Overview of wavelet based image compression system
2.2 One and two dimensional discrete wavelet transform
2.3 Extension techniques
2.4 DWT implementation methods
3 Wavelet properties
3.2 Filter length .
3.3 Vanishing order, smoothness and magnitude response
3.4 Group delay dierence
4 Performance analysis and results
4.1 Choice of wavelets and images
4.2 Test conditions
4.3 PSNR results
4.4 Analysis of PSNR results
4.5 Subjective results and analysis
5 Conclusions and future work
5.2 Future work
GET THE COMPLETE PROJECT
Orthogonal vs. Biorthogonal Wavelets for Image Compression