Wavelets and Applications
|
Introduction
|
|
Wavelets are powerful tools that can be used in signal processing and data compression. Wavelet transforms are an excellent alternative to Fourier transforms in many situations. In Fourier analysis, a signal is decomposed into periodic components; in wavelet analysis, a signal is decomposed into components localized in both time and frequency domains. Thus, wavelet transforms are ideal when signals are not periodic.
|
|
The Theory
|
|
In Fourier analysis, is used as an orthonormal basis of . In wavelet analysis, a father wavelet and a mother wavelet are chosen such that:
form an orthonormal basis of . In theory, is chosen to satisfy the conditions of a multiresolutional analysis (MRA), and then is determined from and the MRA. In practice, and are assumed to satisfy the following functional equations, and the coefficients are computed according to the desired properties of the MRA.
(1)
(2)
In fact, often and cannot be determined symbolically, and are defined solely in terms of these coefficients. In such cases, the Cascades Algorithm can be used to obtain numerical approximations.
The fact that and must be orthogonal reduces to the following numerical conditions on the and , when has norm 1.
(3)
(4)
(5)
Usually, the are computed, then the are determined by reversing the and negating every term. The and are also known as the scaling and wavelet coefficients, or the low pass and high pass filters, respectively.
|
Z Transforms
|
|
When the Fourier transform of equation (1) is computed,
is obtained. This is the motivation for defining:
This is known as the Z transform associated with . In this context, the orthogonality conditions reduce to:
The generation of wavelets is often phrased in this language.
|
|
Orthogonal and Biorthogonal Wavelets
|
|
Technically, the above discussion applies only to orthogonal wavelets. In a variant of this theory, different bases of are used for the analysis and synthesis of signals. Such pairs of bases are generated by biorthogonal bases. Note that orthogonal wavelets can be viewed as biorthogonal wavelets for which the analysis and synthesis processes coincide. However, biorthogonal wavelets are not orthogonal; their main advantage is that the orthogonality conditions are relaxed, allowing more smoothness conditions to be imposed.
Some authors refer to wavelets that are neither orthogonal or biorthogonal, but such wavelets are not discussed here.
|
|
|
Wavelet Generation
|
|
This section provides examples showing how some wavelets are generated by Maple. This section is not intended as a complete guide to the generation of these wavelets, and it is not intended as a thorough discussion of their theory. It is a simplified outline of how Maple generates these wavelets.
|
Symlets
|
|
Symlets are a variant of the Daubechies wavelet. In fact, they are also called Daubechies least asymmetric wavelets. They have the same vanishing moments as the Daubechies wavelets, and the same size, but they have minimal phase. A complex valued function is said to have linear phase if there are real numbers a and b such that . It is known that there are no compactly supported (that is, finite length) orthogonal wavelets with linear phase. The Symlets were designed by Ingrid Daubechies to have phase as close as possible to linear.
The generation of Symlets is very similar to the generation of the Daubechies wavelets. To generate the Symlet of size , start by finding the roots of the polynomial that is used in the generation of the Daubechies wavelet. Then transform these roots to get roots of the Laurent polynomial , where . The plot demonstrates that these roots come in groups of conjugates and reciprocals, so you are able to restrict your attention to those with norm less than or equal to 1 and non zero imaginary part.
Now perform spectral factorization on . This means that you want to find a such that . This is done by using the Feyer Reiz algorithm. For each root of , you simply have to assign one of the roots of to . Because of the properties of , this is sufficient. This is where the Symlets are different from the Daubechies wavelets. In the generation of the Daubechies wavelets, you can simply pick the root in the unit circle of the complex plane. This choice of spectral factorization has maximal phase. To compute the choice of spectral factorization with minimal phase, you have to compute all spectral factorizations, and pick the one where the nonlinear part has the smallest L1 norm.
>
|
|
Note that and should be thought of as binary numbers whose digits encode the factorization being used.
To save time, you can assign the first value. This means that you only range over half of all possible factorizations, but this is enough. Within the loop below, save a list of the phases, , so that you can graph them later. Remember that minimal phase is defined by minimum L1 norm.
>
|
|
With this done, you can now graph all of the phases that were considered, with the minimal phase displayed with a bold line.
>
|
|
Now construct the spectral factorization with the minimal factorization computed above, and extract the normalized scaling (low pass) coefficients.
>
|
|
| (3.1.1) |
Verify this against the Maple function that computes wavelets.
| (3.1.2) |
|
|
|
The Discrete Wavelet Transform
|
|
The wavelet transform can be accomplished for discrete signals by using an algorithm known as the (fast) discrete wavelet transform. Recall the coefficients and from equations (1) to (5). The low pass filter, , is the , and the high pass filter, , is the (in vector form). In almost all useful cases, these are finite. The size of and is called the filter length. If has elements, is often called an -tap wavelet.
The discrete wavelet transform produces two outputs, each half the size of the input. The first output is the high detail coefficients, and the second is the low detail coefficients. They are computed by convolving and , respectively, against the input data, and then downsampling (throwing away every second term).
The low detail coefficients are then recursively processed. It is not obvious, but this in fact computes the wavelet coefficients (the coefficients of each function in the orthonormal base of wavelets).
The discrete wavelet transform is a linear transformation on the input signal. If the high and lows pass filter are:
then this linear transform on a signal of length 6 can be viewed as multiplication by the Matrix:
The result of the multiplication of this Matrix by the signal is an interlacing of the high and low pass coefficients.
The orthogonality conditions on (recall that and are the wavelet and scaling coefficients from equations (3) to (5)) are equivalent to the Matrix being orthogonal! This makes the discrete wavelet transform an orthogonal linear transformation, and hence very easy to invert.
|
End Conditions
|
|
In the above convolutions, the filter mask "falls off" the end of the data. To maintain the orthogonality of the discrete wavelet transform (and the resulting easy invertibility), the data must be assumed to be periodic (as shown in preceding diagrams). However, two other common alternatives exist. The data can be padded with zeros, or the data can be reflected to generate extra data. In both cases, the transform is usually not invertible with orthogonal or biorthogonal wavelets, but can sometimes be modified to maintain easy invertibility. Such modifications are not discussed here.
For example, given the signal [1,2,3,4,5,6], the following are the periodic, zeros, and reflection end conditions for extending the data.
Periodic:
|
|
Zeros:
|
|
Reflection:
|
|
|
|
|
|
|
Maple Functions for Wavelets
|
|
All of Maple's functions for wavelets are part of the DiscreteTransforms package. They are:
- DiscreteWaveletTransform
- InverseDiscreteWaveletTransform
- WaveletCoefficients
- WaveletPlot
See the corresponding help pages for basic information and examples.
|
Examples
|
|
This is a quick example to explore the Daubechies length 4 wavelet.
| (5.1.1) |
>
|
|
| (5.1.2) |
Plot the Daubechies mother and father wavelets by using the WaveletPlot command. WaveletPlot uses a numerical algorithm called Cascades to approximate and plot functions satisfying equations (1) and (2). No explicit definition exists of the Daubechies length 4 mother and father wavelets.
>
|
|
The WaveletCoefficients command respects the Digits setting. In this case, if you increase the setting of Digits, you can correctly identify the symbolic expressions of the the wavelet coefficients.
| (5.1.3) |
And of course, you can use the Daubechies 4 wavelet to transform data.
| (5.1.4) |
You can also transform an image, by using the ImageTools package.
>
|
|
|
|
|
Sample Applications
|
|
Wavelets are of growing importance in a number of diverse fields, including seismology, underwater acoustics, computer vision, and signal processing. The largest application seems to be in image compression; below are three sample applications to illustrate of the capabilities of Maple's new wavelet functions.
|
Procedures and Initialization
|
|
First, define functions to transform (and inverse transform) a grayscale image. Discrete wavelet transforms of images are done by transforming first one dimension, and then the other. This process generates four outputs, the high-high, high-low, low-high, and low-low coefficients. The low-low coefficients can then be transformed recursively.
Also define a small procedure to count the zeros in a Matrix, returning the result as a percentage of the number of elements in the Matrix, and two procedures needed for signal denoising.
>
|
|
>
|
|
>
|
|
>
|
|
| (6.1.1) |
>
|
|
>
|
|
|
|
Image Compression
|
|
The discrete wavelet transform is the analytical core of both the FBI fingerprint compression standard and the JPEG 2000 image compression standard. The success of wavelets in the FBI's case is nothing short of stunning: fingerprints are stored in a small fraction of the space while maintaining all of their distinguishing features.
The power of wavelets in this area comes from the zero and near zero values that appear in images transformed by using wavelets. In lossy compression, these values can be set to zero, making the data much easier to compress. The examples below demonstrate the power of this method without actually performing any compression.
You have already loaded an image above.
>
|
|
Now set the level of transform to be used, the percentage of zeros desired, and the wavelet to be used.
Now you can transform and threshold the data. In the thresholding step, the smallest (in absolute value) per percent of the values in the transformed data are set to zero. As a check, output the percentage of zeros in R, the thresholded, transformed data.
>
|
|
| (6.2.1) |
>
|
|
And now you can invert the transformation, using the thresholded data.
>
|
|
The quality of the new image is amazing, given that it was constructed from data that was per percent zero!
In addition to visually judging the quality of the reconstructed image, you can compute the average error (relative to the original image), view a black and white Matrix representing high error pixels, and use the ImageTools[Quality] command.
| (6.2.2) |
>
|
|
Given the ability to transform images to produce lots of zeroes without significantly affecting image quality, the applications of wavelets in image compression are obvious.
|
|
Signal Denoising
|
|
First create a signal, , and a noisy version, .
Now transform the data, threshold it, and perform the inverse transform.
>
|
|
>
|
|
Amazing!
|
|
Matrix-Vector Multiplication
|
|
In the situation where a fixed Matrix must be multiplied by many Vectors , the discrete wavelet transform can sometimes be used to speed up the calculations. The algorithm presented below preprocesses by using wavelets to exploit patterns. If consists of random values, there will be no speed up. By thresholding, this algorithm tries to reduce the number of floating point multiplications required, but does not represent any decrease in algorithmic complexity.
Note that orthogonal wavelets must be used in this algorithm. This application exploits the fact that, for orthogonal wavelets, the discrete wavelet transform is an orthogonal linear transformation. (See the section Discrete Wavelet Transform for a brief comment on the orthogonality of the discrete wavelet transform.)
>
|
|
Because the discrete wavelet transform is an orthogonal linear transformation, you can simultaneously transform the rows of the Matrix M and the whole Vector , while leaving their inner product unchanged. This is related to the fact that, for Vectors and and an orthogonal Matrix ,
= x.y
The fact that the transformation does not affect can be verified numerically.
| (6.4.1) |
It is also possible to transform the columns of , but then the result has to be inverse transformed.
| (6.4.2) |
>
|
|
So this means that you can effectively apply the same techniques that were used to transform and threshold images to simplify Matrix-Vector multiplication.
|
|
|
References
|
|
Introductory books
•
|
Aboufadel, Edward and Schlicker, Steven. Discovering Wavelets. Interscience, 1999.
|
Intermediate books; note that these books use fourier transforms extensively
•
|
Mallat, Stephane. A Wavelet Tour of Signal Processing. Academic Press, 1999.
|
•
|
Hernandez, Eugenio and Weiss, Guido. First course on wavelets. CRC, 1996.
|
The definitive book on wavelets from an expert standpoint
•
|
Daubechies, Ingrid. "Ten Lectures on Wavelets." SIAM, 1992.
|
|
Return to Index for Example Worksheets
|