One-Dimensional Discrete Wavelet Transform (Biomedical Image Analysis)

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:

tmp2F-176_thumb

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


tmp2F-177_thumb

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.

Localization of discrete wavelets as a function of the translation parameter k and the scaling parameter j.

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

tmp2F-179_thumb

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:

tmp2F-180_thumb

which is contrary to the requirement for a wavelet functiontmp2F-181_thumbThe frequency responsetmp2F-182_thumbof the finite impulse response filter defined by the filter coefficients h(k) is

tmp2F-183_thumb

wheretmp2F-184_thumbfor a lowpass filter. While each wavelet function-scaling function pairtmp2F-185_thumband ^(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 wtmp2F-186_thumb,, It can be seen that the scaling filter is characterized bytmp2F-187_thumbThis 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

tmp2F-188_thumb

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

tmp2F-194_thumb

and vanishing moments are moments wheretmp2F-195_thumbFor 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

tmp2F-189

Daubechies-4

2

2

tmp2F-190

Daubechies-8

4

4

tmp2F-191

Coiflet-6

2

2

tmp2F-192

Coiflet-12

4

4

tmp2F-193

 

 

 Some wavelets (black) and their corresponding scaling functions (gray) of the Daubechies family.

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.

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.

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).

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.

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 outputstmp2F-199_thumbcontain 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.

tmp2F-200_thumb

Each sequence of output coefficients,tmp2F-201_thumbcontains half the number of data values of the input sequencetmp2F-202_thumbThe 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.

Schematic representation of the pyramidal decomposition scheme performed by the filter in Figure 4.5 in the example of the Haar wavelet (arrows).

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,tmp2F-204_thumbandtmp2F-205_thumbRearranging the coefficients (R) provides the scaling coefficientstmp2F-206_thumbfollowed 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, tmp2F-207_thumbrespectively, are combined until the original signal is restored for j = 0:

tmp2F-208_thumb

Next post:

Previous post: