For applications in signal and image processing, that is, applications on discrete data, a discrete wavelet transform must exist. For a discrete wavelet transform it is not necessary to translate and scale the mother wavelet continuously. Rather, it is possible to rewrite Equation (4.7) to reflect discrete translation and scaling steps j and k:
where s and t are now constant scaling and translating increments. Typically, s = 2 and t = 1 are chosen in discrete wavelet implementations. The localization of discrete wavelets as a function of the scaling and translating parameters j and k is shown in Figure 4.2, where each circle represents the location of one wavelet. Figure 4.2 not only shows the doubling of the scale with increasing j, but also the doubling of the time step size at larger scales.
The discrete wavelet transform is realized by using the principles of subband coding. The discrete convolution of the signal with a wavelet function can be interpreted as bandpass filtering of a signal x(k) with discrete filter coefficients g(r) according to
Equation (4.10) represents the discrete convolution, which was introduced in Section 2.3. The discrete filter coefficients g(r) are related to the wavelet function ^ and are responsible for the matching frequency behavior between the discrete filter [Equation (4.10)] and the continuous filter [Equation (4.4)]. In the context of digital signal processing, the filter coefficients g(r) constitute the impulse response function of the filter, and a filter with a finite number of filter coefficients is referred to as a finite impulse response filter.
FIGURE 4.2 Localization of discrete wavelets as a function of the translation parameter k and the scaling parameter j.
To complete the subband coding filter, a function ^s,T (t) needs to be defined that is complementary to ^ s,T (t), and filtering of the signal f(t) with the function ^s,T (t) leads to a lowpass filtered output. In the same manner that the discrete wavelet filter uses the filter coefficients g(r), the discrete filter with the filter function ^s,T (t) uses the filter coefficients h(r). The two sets of filter coefficients g(r) and h(r) are related as
where L is the total number of filter coefficients and n runs from 0 to L — 1. The function ^(t) is called a scaling function, and the name is derived from a special property, namely, that ^(t) obeys the scaling equation:
which is contrary to the requirement for a wavelet functionThe frequency responseof the finite impulse response filter defined by the filter coefficients h(k) is
wherefor a lowpass filter. While each wavelet function-scaling function pairand ^(t) have discrete filter coefficients, g(k) and h(k), respectively, the relationship between the continuous functions and the discrete filter coefficients is not trivial. The derivation of the equations that lead to the design of the filter parameters h(k) goes beyond the scope of this topic. A detailed description of the mathematical foundations and necessary steps to design wavelets and to derive the filter coefficients h(k) can be found in the topic by Burrus et al.4 Instead, the filter parameters h(k) for several widely used wavelets are provided in Table 4.1. Note that g(k) can be computed from h(k) using Equation (4.11). The simplest case is the Haar wavelet with the wavelet parameters w,, It can be seen that the scaling filter is characterized byThis is a simple averaging lowpass filter, whereas the wavelet filter is a first-order finite-difference filter. Ingrid Daubechies has pioneered the wavelet transform,9,10 and the Daubechies series of filter coefficients is listed for filter orders 2 through 10 in her topic Ten Lectures on Wavelets.10 The filter functions of higher-order filters are more regular, smoother, and
In addition, being a lowpass filter, any scaling function ^(t) cannot have a vanishing zeroth moment; more specifically,
more often differentiable, as can be seen in Figure 4.3. This smoothness is represented by the number of vanishing moments of the wavelet. The kth moment of a wavelet is defined as
and vanishing moments are moments whereFor example, the Haar wavelet has only one vanishing moment, = 0, which is the minimum requirement for a wavelet, as stated initially. A smooth wavelet has a smooth frequency response, which is generally a desired property.
TABLE 4.1 Filter Parameters for Several Widely Used Wavelets
Wavelet |
Order N |
Vanishing Moments |
Parameters hk |
Haar |
1 |
1 |
|
Daubechies-4 |
2 |
2 |
|
Daubechies-8 |
4 |
4 |
|
Coiflet-6 |
2 |
2 |
|
Coiflet-12 |
4 |
4 |
FIGURE 4.3 Some wavelets (black) and their corresponding scaling functions (gray) of the Daubechies family.
At this point we have assembled all necessary tools to realize the discrete wavelet transform. The key elements are the discrete convolutions [Equation (4.10)] with finite impulse response filters characterized by the filter coefficients g(k) and h(k). With the scaling constant s = 2, the bandwidth of the filtered signal is half of the bandwidth of the original signal. For this reason, the Nyquist sampling theorem is still satisfied if the number of discrete samples in the filter output is reduced by a factor of 2 (by omitting every other sample). This step is called subsampling by a factor of 2. The elements of one subband filter stage are shown in Figure 4.4. Each subband filter splits the signal into a lowpass and a complementary highpass component (both subsampled by 2). This filter pair in Figure 4.4 is known as a quadrature mirror filter pair in digital signal processing.
FIGURE 4.4 Sketch of one subband filter stage. The input signal Xj (k) is convolved with the highpass filter function g(k) to provide the high-detail content 7j+1 (k) and with the lowpass filter function h(k) to provide the low-detail content Xj+1 (k). The latter can be used as input to the next filter stage. The operations labeled with |2 indicate subsampling by a factor of 2.
The wavelet filter bank can be implemented using a recursive scheme. Since the subsampled signal has twice the sampling interval of the input signal, a scaling factor s = 2 is inherent. Consequently, the lowpass-filtered component can be used as the input to the next (identical) filter stage, and multiple subband filter stages can be chained recursively to form a multiscale analysis filter, as shown in Figure 4.5. The output values of such a filter bank are called the wavelet coefficients of the signalf(k).
FIGURE 4.5 Multiscale analysis wavelet filter composed of four identical subband filter stages (shown in Figure 4.4). The lowpass output of each filter stage is used as input signal to the next filter stage. The wavelet filter outputscontain successively less detail, and each signal has half the number of points of the preceding signal. The filter chain is ended by adding to the outputs the lowpass signal X4(k), as the component with the lowest detail.
Each sequence of output coefficients,contains half the number of data values of the input sequenceThe pyramidal decomposition scheme as laid out in Figure 4.5 with the subband filter in Equation (4.16) is explained in more detail in Figure 4.6. Starting with the initial signal (sequence of values fk), the subband filter is applied. The result is an interleaved sequence of scaling and wavelet coefficients. These need to be rearranged (operation R) to separate the scaling coefficients from the wavelet coefficients. Only the scaling coefficients from one filter stage are propagated to the next filter stage, followed in turn by rearrangement. From stage to stage, therefore, a shorter sequence of wavelet coefficients with less detail is provided, indicated by a darker shade of gray. Each sequence of lower detail has half the length of the higher-detail sequence. For this reason, the input sequence must have a power-of-2 length.
The discrete wavelet transform is indeed a transform in the sense that it allows the exact reconstruction of the original data from the filter output.
The two components of the subband filter (Figure 4.4) are described as (4.17) describes the reconstruction process in an manner analogous to Equation (4.16), that is, by using the recursive scheme in reverse.
FIGURE 4.6 Schematic representation of the pyramidal decomposition scheme performed by the filter in Figure 4.5 in the example of the Haar wavelet (arrows). Data pairs of the initial data sequence fk are subjected to the filter in Equation (4.16), resulting in pairs of scaling and wavelet coefficients,andRearranging the coefficients (R) provides the scaling coefficientsfollowed by the wavelet coefficients 7 k .In the next step, the reduced number of scaling coefficients is again subjected to the subband filter and rearranged. After each filter step, a new sequence of coefficients with less detail (darker gray shade) is available.
By reversing the signal flow through the filter in Figure 4.4, the lowpass and highpass components of each stage, respectively, are combined until the original signal is restored for j = 0: