=9.in =6.375in =0.01in =0.25in
This book has a two-part subject. One part is discrete, the other is continuous. In discrete time we develop the idea and applications of filter banks. In continuous time we have scaling functions and wavelets w(t). By a natural limiting process, iteration of the lowpass filter leads to the scaling function. One highpass filter then produces a wavelet. Our goal is to make this connection clear. We find the conditions on the discrete coefficients that lead to good filter banks and good wavelets.
Historically and mathematically, the filters come first. Perfect reconstruction filter banks were developed in the early 1980's. The excitement around wavelets started later (and grew quickly). This excitement was not universal - designers of filter banks naturally asked what was new. Part of the answer is precisely in that process of iteration. For a filter to behave well in practice, when it is combined with subsampling and repeated five times, it must have an extra property - not built into earlier designs. This property expresses itself in the frequency domain by a sufficient number of ``zeros at ''. Then the frequency band can be successfully separated into five octaves.
The underlying problem is to choose a good basis. We want to represent a signal well, by a small number of basic signals. These can be sinusoids and they can be wavelets. On a discrete grid, is the highest frequency at which a signal can oscillate. Those oscillations are stopped by the lowpass filter with a ``zero at ''. The highpass filter lets fast oscillations through, and the synthesis filters can reconstruct the exact input. But compression may come between analysis and synthesis. Frequencies that are barely represented will be intentionally lost. That mostly means high frequencies but the filter bank is impartial - it keeps the basis functions that are important to the specific signal. We want to show when, and why, filter banks and wavelets are effective in reconstruction and signal representation and compression. Filter Banks
Some readers will begin this book with Chapter 1. Others will jump forward to a topic of particular interest. This brief guide is for both, especially to tell the first readers what is coming and the second group where to look. We are pointing to places where preparation and explanation come together, to design and study new structures.
For filter banks, that place is Section 4.1. There we identify the two conditions for perfect reconstruction (in the absence of lossy compression). One condition removes distortion, the other condition removes aliasing. The anti-distortion condition applies to the products and along the channels of the filter bank. Then the anti-aliasing condition controls how those products can be separated into the four filters.
The design of a perfect reconstruction filter bank is a choice of and then a factorization. To understand the conditions on distortion and aliasing, we apply the techniques of multirate filtering. Those techniques are explained in Chapters 1-3, with examples throughout. Of course filters are to be defined! But we can go forward even now, to illustrate a filter bank that gives perfect reconstruction.
The analysis bank is on the left. It has a lowpass filter , and a highpass filter , and decimation by - which removes the odd-numbered components after filtering. The analysis bank yields two ``half-length'' outputs. Then the synthesis bank on the right begins with the upsampling operation - which inserts zeros in those odd components:
The gap in the center indicates where the subband signals are compressed or enhanced. The applications of this structure are extremely widespread. We believe that any reader interested in signal processing (and image processing) will find that filter bank analysis is extremely useful.
The filters , , and are linear and time-invariant. The operators and are not time-invariant. These multirate operations are responsible for aliasing and for imaging - they create undesirable and extraneous signals that the filters must cancel. To understand how that happens, and to design good filters, we use the tools developed in Chapters 1-3: especially transformation to the frequency domain and z-domain. We try to explain the analysis of multirate filtering, with and , clearly and memorably.
The theory and the design of filter banks and wavelets will dominate Chapters 4-6. This is the heart of the book. The structure of an orthogonal bank is very special, and the next figure shows how the filters are related. For length 4 all filters use the four coefficients, that Daubechies derived:
How did she choose ? Part of the answer will have to wait, but here is the essential idea. The product along the top channel gives a particular ``halfband filter'':
This convolution is a multiplication of two polynomials, when are the coefficients:
The four coefficients are pleasant to calculate. The serious job in Chapter 4 is to explain what is special about that degree polynomial in which and are missing.
A filter bank also gives perfect reconstruction if it is biorthogonal. This design is less restricted. The product must skip the same odd powers of , but does not have to be the transpose (the flip) of . Here are specific numbers for the filter coefficients - not the only choice and maybe not the best. They show how the filters and on the synthesis side are related to the analysis filters and (by alternating signs):
For filters, we stop here. This time . Multiplied by it gives the same important degree polynomial as before. To understand why the zero coefficients are necessary in that polynomial, and why and are desirable, I am afraid that you have to read the book!
Our discussion went this far (further than we intended) so as to make a basic and encouraging point: The construction of new filter banks need not be complicated. This subject is accessible to new ideas and experiments.
Wavelets
Wavelets are localized waves. Instead of oscillating forever, they drop to zero. They come from the iteration of filters (with rescaling). The link between discrete-time filters and continuous-time wavelets is in the limit of a logarithmic filter tree:
Scaling functions and wavelets have remarkable properties. They inherit orthogonality, or biorthogonality, from the filter bank. Because of the repeated rescaling that produces them, wavelets decompose a signal into details at all scales. The wavelet w(t) and its shifts w(t-k) are at unit scale. The wavelets and are at scale . The biorthogonal functions and come from iterating the synthesis bank.
Wavelets produces a natural ``multiresolution'' of every image, including the all-important edges. Where the low frequency part of the Fourier transform is often a blur, the output from the lowpass channel is a useful compression.
Sections 5.5 and 6.2 study the particular wavelets created by Ingrid Daubechies. They are orthogonal, with the advantages and limitations that this property brings. Sections 4.1 and 6.5 study biorthogonal alternatives, which come from different factorizations of the same polynomial (as above). This polynomial corresponds to a ``maxflat halfband filter'', and we hope you will like the connections.
More than that, we hope you enjoy the whole book. This subject is a beautiful combination of mathematical analysis and signal processing applications. The analysis and the applications are based on designs that give perfect reconstruction. To explain both sides of this subject, we need words from mathematics and words from digital signal processing. The Glossary at the end is a dictionary of their meanings. Above all we need ideas from both sides, and from a tremendous range of application areas. It is to the understanding of filters and wavelets, and the growth of successful applications, that this book is dedicated.
There are four conditions that play a central part in this book. Because of their importance we highlight them here. They apply directly to the coefficients in the filter banks - and the consequences are felt (after iteration!) in the scaling functions and wavelets. Here are the four conditions - some might say in decreasing order of importance:
One step further and this Guide is ended. The four fundamental conditions will be stated explicitly for a two-channel filter bank, with the sections in which they appear. We continue to use the polynomials , , , and , whose coefficients come directly from the filters. By convention, these are polynomials in , and the lowpass analysis filter is represented by . Here are the conditions that give filters and wavelets with good properties:
1. Perfect Reconstruction (PR condition in Section 4.1)
The second equation gives the anti-aliasing choices and . 2. Orthogonality (Condition O in Section 5.3)
The filter coefficients are reversed by and . Then perfect reconstruction depends on the ``double-shift orthogonality'' of the lowpass coefficients :
In terms of the polynomials this is
3. Accuracy of order p (Condition in Sections 5.5 and 7.1)
The lowpass filter has a zero of order p at z=-1:
4. Convergence and Stability (Condition E in Section 7.2)
The transition matrix has as simple eigenvalue and all other .
Final note: The sixth degree polynomial in the examples above has four zeros at z=-1:
These zeros give flat responses near and also . The absence of and is the key to perfect reconstruction. Polynomials of higher degree, also with zeros at z=-1 and also with only one odd power, factor into to give the best filters for iteration. In the limit of the iterations, these filters give good wavelets.