Why Wavelets?
by Don Morgan
This month, I begin to look at a relatively new phenomenon in the fields of mathematics and signal processing. I say "relatively new" because upon examination, wavelets have been
with us for a long time in one form or another, and with one name or another. Once the theory of wavelet decomposition is described, you will recognize it in such common equipment as the graphic equalizer on the your home stereo.
Wavelets have successfully been used with magnetic resonance to image the beating heart with very few coefficients. They are being used in some areas of mathematics in the study of fractals and to reduce the number of calculations necessary in solving very large matrices.
They are also being used in astronomy for such things as separating subclusters from within superclusters.
Wavelet theory involves some highly intuitive elements that will be immediately obvious, and some perhaps not so obvious. I will attempt to move slowly and with enough illustration to remain clear in my explanations. In the end, I hope that I will have lifted some of the obscurity from the subject.
Let us begin with an examination of what we actually want when we use a transform.
Transforms
A transform is a device designed to highlight, reinforce, or make more explicit certain features of whatever we are examining. It doesn't have to be elaborate, fancy, or expensive.
Using our numbering system and base 10, it is breathlessly simple to determine what numbers will result from a multiplication or division by the number 10. At the same time, however, it isn't as easy to determine what numbers will result from multiplications and divisions by, say,
nine or 17. Yet we can make it easy by simply moving from base 10 to base 9 or 17. This movement is a transform. Though this may seem a trivial example, it isn't to a programmer writing arithmetical routines.
The number line comprises all numbers from minus infinity to infinity. If we call any arbitrary number on this line x and make it equal to y (x = y) so that we can plot it, we will have a sloping line that is linear and exists equally in the negative and positive quadrants. This line is
represented in Figure 1a. Suppose now that we square x (x2 = y) and plot this. Now, we notice several items. By applying this transform, we have put a focus on both the smallest values in the number line and the larger values.
A highly important aspect of a transform is its invertibility (biorthogonality). While not all transforms are invertible, those that are through the same function (orthogonal) are especially convenient and useful.
FIGURE 1
1a-Sloping
line illustrating the progression of the number line x=y.
1b-Transformed number line illustrating the change of focus x-squared=y.)
Fourier Transform
In signal processing, we are often given serial data streams to work with, bounded (such as video) or unbounded (such as audio). If you are given an array of values as you might find on a table, a stock market report for the previous year, a check book, one scan line of video, or the feed from a preamp in a movie theater, and asked
to determine the frequencies involved in the cycling of numbers, you would probably feel somewhat daunted. That's because the data is all time-based. If we were to plot it, we would label the x-axis "time."
If the frequency components are simple (say, one frequency) and we examine the sequence on something like an oscilloscope, we could count the samples between zero crossings of the same phase and determine the frequency with which the data is changing. If too many frequencies are involved,
however, this is no longer possibleıwe may find some but miss others.
Enter the transform. In signal processing, there are many transforms useful in this context, most of them Laplace-based. An important example is the Fourier transform that allows us to change the index on the x-axis from "time" to "frequency." (Unfortunately, in doing so, we lose all reference to time.)
The Fourier transform works by multiplying vectors that represent frequencies orthogonal to one another by the input
vector and summing the results. Those elements common to all the frequencies vanish in the algebraic sum and we have, as a result, a vector of coefficients representing sign and magnitude of frequency contributions to the input vector. To achieve any order of resolution, we must have many samples with which to work. Because each sample is separated by a fixed period, this requires timeıthe greater the resolution, the greater the number of samples required and therefore, the more time required.
There is
a fixed inverse relationship between resolution and time with the Fourier-based tools. This means that if we wished to analyze a symphonic work, we could sample the work and input it to a Fourier transform and get very good frequency resolution, showing us precisely the nature of every frequency contribution to the work. However, we would not know with any precision when any one frequency (note) was played.
There are many techniques for ameliorating this situation, such as windowing, as in the
Short Time Fourier Transform, where a Fourier transform is applied to a highly over-sampled data stream in pieces, thereby localizing the frequency analysis. Unfortunately, you can't get a purely continuous view of a data sequence with these methods.
Wavelet Transform
The concept behind the wavelet transform has been around for some time, though the exact implementation and name have been highly discipline-dependent. The concept has been used for earthquake studies, medical analysis,
home entertainment, and astronomical research. There are a number of variations, and we will cover many in subsequent columns. Here, however, I'll concentrate on the orthogonal wavelet, as defined by Ingrid Daubechies and Stephane Mallat.
What these two contributed that changed the face of the work in this field was the idea of multi-resolution. Simply put, multi-resolution describes a sequence of spaces that proceed from the infinitesimal (zero=DC) to include the infinite. Each space has twice
the resolution of its predecessor. (It is of little consequence, but Daubechies and Mallat used two opposing directions for the sequence of spaces to step through.) Each such space of lower resolution is entirely contained within the previous space.
The interesting part is that as you proceed toward infinity, each space of finer resolution is an orthogonal sum of the previous coarser level and the details available at the new level. The details are the result of the wavelet function, and the level
is a result of what is known as the scaling function.
When we change frequencies in increments of two, we are making octave jumps. Let's say that we have an input signal bandlimited to 24kHz, and that we process this signal with complementary low- and high-pass filters at 12kHz. We will have two outputs. From the low-pass filter, we have information that is changing more slowly than 12kHzıthis is the coarser level. From the high-pass filter, we have data that exists between 12kHz and 24kHzıthe
details. The entire input signal is the sum of these two.
This effect can be accomplished by constructing an appropriate half-band low-pass filter (as described in last month's column) and its complementary high-pass function by reversing the sign of every other coefficient in the impulse response of the low-pass filter. In fact, we can make an equalizer for your home theater unit by cascading sections such as these. First, we define a block as a parallel connection of half-band filters designed as
described. We then connect these blocks in cascade by taking the output of each low-pass section as the input to the next block. In addition, each subsequent block in the cascade is operated at half the sample rate of the previous one. This allows us to process each section at half the rate of the previous one and keep the same coefficients.
The output of the high-pass sections represents the detail information for each octave (24 to 12kHz, 12 to 6kHz, 6 to 3kHz, 3 to 1.5kHz, and so on). This is the
information that we manipulate (attenuate) to get the sort of sound that best fits the room we are in. We then sum these signals to reconstruct the modified form of the input that we want. What we have are octave-based band-pass filters.
Obviously, this is a simplified look at the process, but a workable one, nonetheless. For an illustration, see Figure 2.
FIGURE 2
Cascade of half-band filter sections that form the basis of a wavelet transform
In Figure 3, we have the wavelet decomposition of a square wave using the well-known Daubechies four-coefficient wavelet. It is immediately evident how the octave decomposition separates and sorts the frequency contributions of the input without losing any data regarding the timing of the contribution. It should also be clear that the sum of the decomposition is again the input signal.
FIGURE 3a
FIGURE 3b
3a-Square wave
input signal
3b-Eight-level wavelet decomposition using Daubechies four-coefficient wavelet
I should point out that wavelets exist in all sizes and shapes. In working with wavelets on a particular signal type, it is often appropriate to find the size and shape wavelet that best brings out the desired detail. In later issues, I'll describe how to create wavelets of different sizes, shapes, and smoothness. Each of these points affects the decomposition and can make a particular wavelet better
suited for certain applications than others.
So How Can I Use It?
An immediate application of wavelets is in noise reduction. The wavelet decomposition essentially picks out change. Constants or DC components in a signal result in wavelet coefficients of zero. Signals vary and what is noise to one may well be a signal to another! There are no general rules for noise reductionımost such algorithms are adapted versions.
A simple mechanism for de-noising a signal can be
fashioned from some basic knowledge of the kind of noise with which we're dealing. White noise, for instance, is defined as having uniform energy across the spectrum. If we were to eliminate all coefficients in the wavelet vector below a certain level on all levels, we could do a very good job of eliminating white noise.
By the same token, if correlations are found at the same points in the various decomposition levels, it is highly suggestive that something is going on there. Reconstruction of the
signal with these coefficients can make a phenomenon evident that might otherwise be completely obscured by noise.
Wavelet maxima are wavelet coefficients that are greater than their neighboring coefficients and possess a high degree of correlation (at each level of decomposition) to the input signal. Not only can these be used for bringing important features out of an input signal, but they may also be used for pattern recognition and edge detection in video systems. It is very possible that
wavelet filters could operate faster and more efficiently than the Discrete Cosine Transform commonly used in such applications.
Because wavelet coefficients only indicate change, zero change or very small change can be ignored, thereby reducing the number of coefficients required to encode information. This condition has led to compression schemes that have allowed images to be encoded in as little as 1/40th the space of the original signal.
What's Next
In upcoming issues,
we will delve deeper into the creation and application of wavelets. Next month, we'll explore in depth the continuous wavelet transform and the concept of multi-resolution using orthogonal filter techniques.
Don Morgan is senior engineer at Ultra Stereo Labs and a consultant with 25 years experience in signal processing, embedded systems, hardware and software. He is currently completing a book about numerical methods, featuring multi-rate signal processing and wavelets. He is the author of
Practical DSP Modeling, Techniques, and Programming in C, from John Wiley & Sons, in New York and Numerical Methods for Embedded Systems from M&T.
|
