3.2 Compression Steps

           In this section there is a detailed explanation of each step.

3.2.1  Discrete Wavelet Transform
 

           The foundations of the DWT go back to 1976 when Croiser, Esteban, and Galand devised a technique to decompose discrete time signals. Crochiere, Weber, and Flanagan did a similar work on coding of speech signals in the same year. They named their analysis scheme as subband coding. In 1983, Burt defined a technique very similar to subband coding and named it pyramidal coding which is also known as multiresolution analysis. Later in 1989, Vetterli and Le Gall made some improvements to the subband coding scheme, removing the existing redundancy in the pyramidal coding scheme. By all these studies, today subband coding has come very popular[4].

3.2.1.1  The Subband Coding and the Multiresolution Analysis

           The Subband Coding and The Multiresolution Analysis, firstly, has come with continues wavelet transform (CWT). CWT is not convenient in digital environment. So discrete wavelet transform (DWT) was developed.

           A time-scale representation of a digital signal is obtained using digital filtering techniques. The continuous wavelet transform was computed by changing the scale of the analysis window, shifting the window in time, multiplying by the signal, and integrating over all times. In the discrete case, filters of different cutoff frequencies are used to analyze the signal at different scales. The signal is passed through a series of high pass filters to analyze the high frequencies, and it is passed through a series of low pass filters to analyze the low frequencies.

           The resolution of the signal, which is a measure of the amount of detail information in the signal, is changed by the filtering operations, and the scale is changed by up-sampling and down-sampling (sub-sampling) operations. Sub-sampling a signal corresponds to reducing the sampling rate, or removing some of the samples of the signal. Up-sampling a signal corresponds to increasing the sampling rate of a signal by adding new samples to the signal.

           Although it is not the only possible choice, DWT coefficients are usually sampled from the CWT on a dyadic grid, i.e., s₀ = 2 and τ₀ = 1, yielding s=2^j and t =k*2^j. Since the signal is a discrete time function, the sequence will be denoted by x[n], where n is an integer.

           The procedure starts with passing this signal (sequence) through a half band digital lowpass filter with impulse response h[n]. Filtering a signal corresponds to the mathematical operation of convolution of the signal with the impulse response of the filter. The convolution operation in discrete time is defined as follows:

                                               (3)

 
A half band low-pass filter removes all frequencies that are above half of the highest frequency in the signal.

           The unit of frequency is of particular importance at this time. In discrete signals, frequency is expressed in terms of radians. Accordingly, the sampling frequency of the signal is equal to 2π radians in terms of radial frequency. Therefore, the highest frequency component that exists in a signal will be π radians, if the signal is sampled at Nyquist’s rate (which is twice the maximum frequency that exists in the signal); that is, the Nyquist’s rate corresponds to π rad/s in the discrete frequency domain.

           After passing the signal through a half band low-pass filter, half of the samples can be eliminated according to the Nyquist’s rule, since the signal now has a highest frequency of π/2 radians instead of π radians. Simply discarding every other sample will sub-sample the signal by two, and the signal will then have half the number of points. The scale of the signal is now doubled. The low-pass filtering removes the high frequency information, but leaves the scale unchanged. Only the sub-sampling process changes the scale. Resolution, on the other hand, is related to the amount of information in the signal, and therefore, it is affected by the filtering operations. Half band low-pass filtering removes half of the frequencies, which can be interpreted as losing half of the information. Therefore, the resolution is halved after the filtering operation. However the sub-sampling operation after filtering does not affect the resolution, since removing half of the spectral components from the signal makes half the number of samples redundant anyway. Half the samples can be discarded without any loss of information.

           This procedure can mathematically be expressed as

                                            (4)

           The DWT analyzes the signal at different frequency bands with different resolutions by decomposing the signal into a coarse approximation and detail information. DWT employs two sets of functions, called scaling functions and wavelet functions, which are associated with low pass and high-pass filters, respectively. The decomposition of the signal into different frequency bands is simply obtained by successive high-pass and low-pass filtering of the time domain signal. The original signal x[n] is first passed through a half-band high-pass filter g[n] and a low-pass filter h[n]. After the filtering, half of the samples can be eliminated according to the Nyquist’s rule, since the signal now has a highest frequency of π/2 radians instead of π. The signal can therefore be sub-sampled by 2, simply by discarding every other sample. This constitutes one level of decomposition and can mathematically be expressed as follows:

                                       (5)

where yhigh[k] and ylow[k] are the outputs of the high-pass and low-pass filters, respectively, after sub-sampling by 2.

           This decomposition halves the time resolution since only half the number of samples characterizes the entire signal. However, this operation doubles the frequency resolution, since the frequency band of the signal spans only half the previous frequency band, effectively reducing the uncertainty in the frequency by half. The above procedure, which is also known as the subband coding, can be repeated for further decomposition. At every level, the filtering and sub-sampling will result in half the number of samples (and hence half the time resolution) and half the frequency band spanned (and hence doubles the frequency resolution). Figure 3 illustrates this procedure, where x[n] is the original signal to be decomposed, and h[n] and g[n] are low-pass and high-pass filters, respectively. The bandwidth of the signal at every level is marked on the figure as "f".

           The frequencies that are most prominent in the original signal will appear as high amplitudes in that region of the DWT signal that includes those particular frequencies. The difference of this transform from the Fourier transform is that the time localization of these frequencies will not be lost. However, the time localization will have a resolution that depends on which level they appear. If the main information of the signal lies in the high frequencies, as happens most often, the time localization of these frequencies will be more precise, since they are characterized by more number of samples. If the main information lies only at very low frequencies, the time localization will not be very precise, since few samples are used to express signal at these frequencies. This procedure in effect offers a good time resolution at high frequencies, and good frequency resolution at low frequencies. Most practical signals encountered are of this type.
 

Figure 3. Wavelet transform procedure.

           The frequency bands that are not very prominent in the original signal will have very low amplitudes, and that part of the DWT signal can be discarded without any major loss of information, allowing data reduction.

3.2.1.2  Inverse DWT (Reconstruction)

           The reconstruction of the signal is very easy since half-band filters form orthonormal bases. The procedure on Figure 2. is followed in reverse order for the reconstruction. The signals at every level are up-sampled by two, passed through the synthesis filters g’[n], and h’[n] (high-pass and low-pass, respectively), and then added. The interesting point here is that the analysis and synthesis filters are identical to each other, except for a time reversal. Therefore, the reconstruction formula becomes (for each layer)
 

                   (6)

           However, if the filters are not ideal half-band, then perfect reconstruction cannot be achieved. Although it is not possible to realize ideal filters, under certain conditions it is possible to find filters that provide perfect reconstruction. The most famous ones are the ones developed by Ingrid Daubechies, and they are known as Daubechies’ wavelets.

           Due to successive sub-sampling by 2, the signal length must be a power of 2, or at least a multiple of power of 2, in order this scheme to be efficient. The length of the signal determines the number of levels that the signal can be decomposed to.

3.2.1.3  DWT on Images

           One dimensional DWT transform is for audio signals or any other signals. It can not be implemented directly to image but using one dimensional DWT it is possible to transform an image to wavelet domain.

           Two dimensional DWT is simple as one dimensional DWT. As seen in Figure 4.a firstly each column is transformed independently to wavelet domain. Using results of column DWT, all rows are transformed respectively.
 

(a)

 (b)

Figure 4. 2D Discrete Wavelet Transform

           Transforming the image into wavelet domain makes image to appear in blocks. Figure 5 shows a transformed image for level 3. LL is the lowest frequency band and HH₁, HH₂ and HH₃ are the highest frequency bands in corresponding levels indicating the different characteristics of image in hierarchical order.

Figure 5. Wavelet Transformed image for level 3.