This chapter is concerned with the analysis of datasets (or functions or operators) in terms of frequency and scale components using wavelet transforms. Wavelet transforms have been applied in many fields from time series analysis to image processing and the localization in either frequency or scale that they provide is useful for data compression or denoising. In general the standard wavelet transform uses dilation and scaling of a chosen function,

ψ (t)

, (called the mother wavelet) such that

ψ_{a, b} (t) = \frac{1}{\sqrt{a}} ψ (\frac{t - b}{a})

where

a

gives the scaling and

b

determines the translation. Wavelet methods can be divided into continuous transforms and discrete transforms. In the continuous case, the pair

a

and

b

are real numbers with

a > 0

. For the discrete transform,

a

and

b

can be chosen as

a = 2^{- j}

b = k 2^{- j}

for integers

j

k

ψ_{j, k} (t) = 2^{j / 2} ψ (2^{j} t - k) .

The continuous real valued, one-dimensional wavelet transform (CWT) is included in this chapter. The discrete wavelet transform (DWT) at a single level together with its inverse and the multi-level DWT with inverse are also provided for one, two and three dimensions. The Maximal Overlap DWT (MODWT) together with its inverse and the multi-level MODWT with inverse are provided for one dimension. The choice of wavelet for CWT includes the Morlet wavelet and derivatives of a Gaussian while the DWT and MODWT offer the orthogonal wavelets of Daubechies and a selection of biorthogonal wavelets.

Syntax

C#
public static class C09

Visual Basic
Public NotInheritable Class C09

Visual C++
public ref class C09 abstract sealed

F#
[<AbstractClassAttribute>] [<SealedAttribute>] type C09 = class end

Background to the Problems

The CWT computes a time-frequency analysis of a signal,

x (t)

, which can yield high localization in time of the high frequency features present. It is defined as

C (a, b) = \int_{- \infty}^{+ \infty} \frac{1}{\sqrt{a}} ψ^{*} (\frac{t - b}{a}) x (t) d t

where

ψ^{*}

denotes the complex conjugate of the wavelet function,

a

is the dilation parameter and

b

is the localization parameter. (Currently only the real valued transform is offered.)

The discrete wavelet transform (DWT) is defined by a mother wavelet function

ψ (t)

, and a related scaling function,

ϕ (t)

, where

\begin{matrix} ϕ (t) = \sum_{k} g_{k} \sqrt{2} ϕ (2 t - k) . \\ ψ (t) = \sum_{k} h_{k} \sqrt{2} ϕ (2 t - k) . \end{matrix}

These in turn are represented as a pair of filters with finite support. They can be viewed as a high pass filter,

\{h_{k}\}

, for

k = 1, 2, \dots, m

, paired with a low pass filter,

\{g_{k}\}

, for

k = 1, 2, \dots, n

. The DWT at a single level is carried out by convolution of the filter with the input data, followed by downsampling by two. The MODWT at a single level is carried out by convolution of the filter with the input data only; no downsampling is used in the MODWT. In order to obtain exact reconstruction of the original input these filters must satisfy certain conditions. For orthogonal wavelets,

n = m

, these are,

\begin{matrix} \sum_{k = 1}^{m} h_{k} = 0, & \sum_{k = 1}^{m} h_{k}^{2} = 1, & \sum_{k = - \infty}^{\infty} h_{k} h_{k + 2 l} = 0, \\ \sum_{k = 1}^{m} g_{k} = \sqrt{2}, & \sum_{k = 1}^{m} g_{k}^{2} = 1, & \sum_{k = - \infty}^{\infty} g_{k} g_{k + 2 l} = 0 . \end{matrix}

for all nonzero integers,

l

The DWT reconstruction algorithm convolves the inverse filters with the wavelet coefficients previously computed together with upsampling and summation to return to the original input. The MODWT reconstructs in the same way, except without upsampling. For orthogonal wavelets the inverse filters are the same as those for the forward DWT.

In the simplest case, the Haar wavelet, the nonzero filter coefficients are

\begin{matrix} \{h\} = \{\frac{- 1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\} \\ \{g\} = \{\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\} \end{matrix}

while for the Daubechies wavelet with two vanishing moments and four nonzero coefficients, the filter coefficients are

\begin{matrix} \{h\} = \{\frac{- (1 + \sqrt{3})}{4 \sqrt{2}}, \frac{3 + \sqrt{3}}{4 \sqrt{2}}, \frac{- 3 + \sqrt{3}}{4 \sqrt{2}}, \frac{1 - \sqrt{3}}{4 \sqrt{2}}\} \\ \{g\} = \{\frac{1 - \sqrt{3}}{4 \sqrt{2}}, \frac{3 - \sqrt{3}}{4 \sqrt{2}}, \frac{3 + \sqrt{3}}{4 \sqrt{2}}, \frac{1 + \sqrt{3}}{4 \sqrt{2}}\} \end{matrix}

In the orthogonal case the same filters are used for both decomposition and reconstruction.

Relaxing the orthogonality requirement allows for biorthogonal wavelets which consist of two dual wavelet bases. For example, the biorthogonal 2.2 filters are,

\begin{matrix} \{h\} = \sqrt{2} \{\frac{1}{4}, - \frac{1}{2}, \frac{1}{4}\}, \\ \{g\} = \sqrt{2} \{- \frac{1}{8}, \frac{1}{4}, \frac{3}{4}, \frac{1}{4}, - \frac{1}{8}\} \\ \{h^{'}\} = \sqrt{2} \{\frac{1}{8}, \frac{1}{4}, - \frac{3}{4}, \frac{1}{4}, \frac{1}{8}\} \\ \{g^{'}\} = \sqrt{2} \{\frac{1}{4}, \frac{1}{2}, \frac{1}{4}\} . \end{matrix}

Note that there are several possible interpretations of orthogonal and biorthorgonal wavelet filters which satisfy the requirements. These differ in the sign of the coefficients and the ordering of the filters.

In order to obtain exact reconstruction when applying the DWT or MODWT and its inverse to a finite dataset, say

\{x_{t}\}

, for

t = 1, 2, \dots, N

, some method of extending the input at its end is required. Several methods which are in general use are: periodic extension, half-point symmetric extension, whole-point symmetric extension and zero end extension where the added data points are taken to be zero. The two types of symmetric end extension reflect the given data values from the end points for whole-point extension or else by repeating the end points and reflecting from points halfway between the end point and its repeat for half-point extension. Each of these end extension methods are available for the DWT. Only the periodic end extension is currently available for the MODWT.

Multiresolution and higher dimensional DWT

Rather than simply applying the wavelet transform at a single level the process is commonly repeated to give a multiresolution analysis. For the DWT, multiresolution is implemented as the pyramid (or cascade) algorithm. Applying the DWT at a given level,

L

, the detail coefficients (which are the output from the high pass filter) are stored while the approximation coefficients resulting from convolution with the low pass filter are passed to the next level and the processs is repeated. When the length of the initial data input is an array of length

N = 2^{J}

, for some integer

J

(and assuming that the dataset is extended by periodic repetition) this can be continued until, at level

J

, there is a single detail coefficient from the high pass filter. The final coefficient from the action of the low pass filter is also stored. The result is an array of coefficients of the same length,

N

, as the input.

For the multi-level MODWT it is, in theory, possible to continue for any number of levels. However, in practice it is common to not exceed

\log_{2} (N)

levels in order to avoid scales that exceed the length of the input data,

N

. This restriction is enforced for the one-dimensional mutli-level MODWT method in this chapter.

For two-dimensional data sets the DWT is computed as a series of one-dimensional DWTs, first over columns of the input data, and then over rows of the intermediate result. This produces four types of output coefficients: one set of approximation coefficients and three types of detail coefficients, containing information about the horizontal, vertical and diagonal components of the input data. The approximation coefficients are the result of applying convolution and downsampling with the low pass filter over both columns and rows; the horizontal detail coefficients are the result of applying convolution and downsampling with the high pass filter over columns and then the low pass filter over rows; the vertical detail coefficients are the result of applying convolution and downsampling with the low pass filter over columns and the high pass filter over rows; and the diagonal detail coefficients are the result of applying convolution and downsampling with the high pass filter over both columns and rows. An example of the single level decomposition of an image performed using (C09EAF not in this release) is given in Figure 1.

The original image (top, 996×1332 pixels) is transformed using method (C09EAF not in this release) into the four coefficient (approximation, horizontal, vertical and diagonal) matrices (501×669) displayed below the original. The transformation was performed using the Daubechies wavelet with four vanishing moments and half-point end extension. Note that the approximation coefficients are a very close representation of the original image, while the horizontal, vertical and diagonal features of the image are visible in the respective coefficient matrices.

Figure 1: The original image (top, $996 \times 1332$ pixels) is transformed using method (C09EAF not in this release) into the four coefficient (approximation, horizontal, vertical and diagonal) matrices ( $501 \times 669$ ) displayed below the original. The transformation was performed using the Daubechies wavelet with four vanishing moments and half-point end extension. Note that the approximation coefficients are a very close representation of the original image, while the horizontal, vertical and diagonal features of the image are visible in the respective coefficient matrices.

Similarly, for three-dimensional data sets the DWT is also computed as a series of three one-dimensional DWTs, first over columns of the input data, and then over rows of the intermediate result and finally over frames of the second intermediate result. This produces eight types of output coefficients: one set of approximation coefficients (labelled LLL since the low pass filter is applied over columns, rows and frames) and seven types of detail coefficients, labelled similarly according to whether the low pass (L) or high pass filter (H) is applied in each of the three dimensions. For convenience, where methods (C09ECF not in this release) (two-dimensional multi-level DWT), (C09FAF not in this release) (three-dimensional DWT) and (C09FCF not in this release) (three-dimensional multi-level DWT) return coefficients packed into one-dimensional arrays, coefficient extraction methods (C09EYF not in this release) (two-dimensional) and (C09FYF not in this release) (three-dimensional) are provided which will return a selected set of coefficients into two and three-dimensional arrays, respectively. For the three-dimensional DWT this process is represented by Figure 2.

As in the one-dimensional case, the multi-level DWT in two and three dimensions is also implemented as the pyramid (or cascade) algorithm, where at a given level,

L

, all detail coefficients are stored, while the approximation coefficients are passed as input to the next level.

The three-dimensional DWT filter bank. The original input is downsampled by 2 and the high pass (H) and low pass (L) filters are applied along columns. This process is repeated along the rows and then frames to produce 8 sets of output coefficients – one set of approximation coefficients and 7 sets of detail coefficients.

Figure 2: The three-dimensional DWT filter bank. The original input is downsampled by $2$ and the high pass (H) and low pass (L) filters are applied along columns. This process is repeated along the rows and then frames to produce $8$ sets of output coefficients – one set of approximation coefficients and $7$ sets of detail coefficients.

Recommendations on Choice and Use of Available Methods

The one-dimensional real valued continuous wavelet transform is provided by (C09BAF not in this release). It is useful for resolving discontinuities and high frequency features in a signal. It is a redundant representation of the input data containing repeated information and the set of coefficients produced as output is larger than the input data set.

The one-dimensional discrete wavelet transform at a single level is performed by c09ca. The inverse or reconstruction is carried out by c09cb.

The one-dimensional multi-level discrete wavelet transform is computed by c09cc and the inverse or reconstruction is given by c09cd. The discrete wavelet transform is widely used for image processing and data compression.

The one-dimensional maximal overlap discrete wavelet transform at a single level is performed by (C09DAF not in this release). The inverse or reconstruction is carried out by (C09DBF not in this release).

The one-dimensional multi-level maximal overlap discrete wavelet transform is performed by (C09DCF not in this release). The inverse or reconstruction routine is (C09DDF not in this release). The maximal overlap discrete wavelet transform overcomes the lack of translation invariance inherent in the DWT, and thus there are advantages to using the MODWT when carrying out multiresolution analysis.

C09 Communication class constructor is provided to determine some of the input parameters for the one-dimensional discrete wavelet transform and maximal overlap discrete wavelet transform methods and must be called before the one-dimensional transform methods.

The two-dimensional discrete wavelet transform at a single level is performed by (C09EAF not in this release). The inverse or reconstruction is carried out by (C09EBF not in this release).

The two-dimensional multi-level discrete wavelet transform is computed by (C09ECF not in this release) and the inverse or reconstruction is given by (C09EDF not in this release).

(C09ECF not in this release) (C09EDF not in this release) use a one-dimensional array to store the discrete wavelet transform coefficients. These may be extracted into two-dimensional arrays using (C09EYF not in this release). A complementary method (C09EZF not in this release) allows for the insertion of coefficients held in a two-dimensional array back into the one-dimensional array.

(C09ABF not in this release) is provided to determine some of the input parameters for the two-dimensional discrete wavelet transform methods and must be called before the two-dimensional transform methods.

(C09EYF not in this release) is provided to extract selected sets of coefficients returned by (C09ECF not in this release) in a one-dimensional array into two-dimensional arrays.

The three-dimensional discrete wavelet transform at a single level is performed by (C09FAF not in this release). The inverse or reconstruction is carried out by (C09FBF not in this release).

The three-dimensional multi-level discrete wavelet transform is computed by (C09FCF not in this release) and the inverse or reconstruction is given by (C09FDF not in this release).

(C09FAF not in this release) (C09FBF not in this release) (C09FCF not in this release) (C09FDF not in this release) use a one-dimensional array to store the discrete wavelet transform coefficients. These may be extracted into three-dimensional arrays using (C09FYF not in this release). A complementary method (C09FZF not in this release) allows for the insertion of coefficients held in a three-dimensional array back into the one-dimensional array.

(C09ACF not in this release) is provided to determine some of the input parameters for the three-dimensional discrete wavelet transform methods and must be called before the three-dimensional transform methods.

(C09FYF not in this release) is provided to extract selected sets of coefficients returned by (C09FAF not in this release) and (C09FCF not in this release) in a one-dimensional array into three-dimensional arrays.

References

Daubechies I (1992) Ten Lectures on Wavelets SIAM, Philadelphia

Mallat S G (1998) A Wavelet Tour of Signal Processing Academic Press

Percival D B and Walden A T (2000) Wavelet Methods for Time Series Analysis Cambridge University Press

Strang G and Nguyen T (1996) Wavelets and Filter Banks Wellesley-Cambridge Press

Vidakovic B (1999) Statistical Modeling by Wavelets John Wiley and Sons Inc.

Wickerhauser M V (1994) Adapted Wavelet Analysis from Theory to Software A K Peters Ltd

Inheritance Hierarchy

System..::..Object
NagLibrary..::..C09

Syntax

Background to the Problems

Multiresolution and higher dimensional DWT

Recommendations on Choice and Use of Available Methods

References

Inheritance Hierarchy

See Also