Vol. 31 Issue 3 Reviews

Stéphane Mallat: A Wavelet Tour of Signal Processing, 2nd edition

Hardcover, 1999, ISBN 0-12-466606-X, 637 pages, US$ 77.95; Academic Press, Inc., 525 B Street, Suite 1900, San Diego, California 92101, USA; telephone (+1) 800-321-5068; fax (+1) 800-874-6418; electronic mail ap@acad.com; Web www.apnet.com/

Reviewed by Bob L. Sturm
Santa Barbara, California, USA

A Wavelet Tour of Signal Processing (AWT) is a complete guide to not only the important results and applications of wavelets—also known as multiresolution analysis—but also many of its lesser-known aspects. It contains eleven well-written chapters, two appendices, and 361 references. Each chapter, except for the first, contains several theorems—most accompanied by thorough proofs—and concludes with a set of problems for students and further exploration. Stéphane Mallat, having made seminal contributions to the theory behind and application of wavelets to signal processing, is certainly qualified to be an official tour guide to the world of wavelets.

The history of multiresolution analysis is quite diverse, extending from contributions made by mathematicians, physicists, statisticians, and engineers. As such, it has found application in a broad range of disciplines, of which signal processing is only one. In fact, it is especially applicable to signal processing, whether working with sounds, images, or higher-dimensional data. Mr. Mallat makes this clear in his first chapter, where he motivates the utility of wavelets by discussing problems difficult to approach using Fourier methods, but easier using wavelets. He writes, “If we are interested in transient phenomena—a word pronounced at a particular time, an apple located in the left corner of an image—the Fourier transform becomes a cumbersome tool” (p. 2). Wavelets provide an intuitive means of analyzing signals at various scales for, among other things, segmenting and representing these transient structures.

The formal definition of the wavelet transform (WT) is no different from the Fourier transform, save for the fact that the signal is correlated with a basis created by scaling and translating a single zero-mean time-localized function. In contrast, the Fourier transform basis consists of a set of infinite duration sinusoids, and the short-time Fourier transform (STFT) uses a basis of windowed sinusoids at a fixed time resolution. Therein lies a world of difference. A wavelet basis allows one to resolve a signal at multiple resolutions in a very efficient manner, which is not possible with the Fourier transform. Like the fast Fourier transform, fast methods exist for computing wavelet transforms. Furthermore one is free in designing wavelet functions that are “intrinsically well adapted to represent a class of signals” (p. 11). Indeed the largest chapter in the book is devoted to this subject.

AWT functions as an indispensable guide to any serious “tourist”—be they students, teachers, or professionals—intrigued by the technical aspects of wavelets and how they are and can be applied to signal processing. It is a beautifully-produced book with nice paper, crisp text, and plenty of well-produced and thought-out graphics complementing the contents. One cannot help but want to visit these places after viewing the pictures alone. Like a good tour guide, AWT provides many paths of interest suited to particular levels of complexity and depth. Material is graded throughout the text by three levels of “difficulty.” Essentials and easy proofs are marked with a “1.” Important results for particular applications are marked “2.” And items “at the frontier of research” (p. 18) are marked “3.” This makes it easy to know where time must be necessarily spent, and which content can be skimmed. AWT is in no sense an introductory text; it is rigorous and complete in its presentation. The first four chapters however provide an excellent and thorough introduction to time-frequency (TF) representations, and motivate the utility and applicability of wavelets.

AWT begins with an introduction to the TF domain and transforms. A well-known example is the short-time Fourier transform (STFT), alluded to as early as 1946 by Nobel Prize physicist Dennis Gabor (inventor of the hologram). The discrete STFT partitions the TF plane uniformly, but with a trade-off between resolution in time and frequency. The “narrow-band” STFT has excellent frequency resolution but poor time resolution. The “wide-band” STFT has those relationships reversed. Though one can never escape the inverse relationship between time and frequency resolution, the WT instead provides excellent frequency resolution at low frequencies and excellent time-resolution at high frequencies. With the logarithmic nature of human hearing, this makes wavelets attractive for analyzing and representing musical signals.

After introducing the subject of wavelets, the next two chapters present the essential background upon which wavelets in signal processing is based. Chapter 2 provides a review of linear shift-invariant filtering and Fourier theory. Here we are reminded of properties of the Fourier transform, the significance of the Heisenberg uncertainty relation (tradeoff in time and frequency resolution), and the Gibbs phenomena. The third chapter reviews the principle results of sampling continuous one and two-dimensional signals: the Shannon-Nyquist-Whittaker Sampling Theorem, discrete time-invariant filters, and Fourier series. Fast implementations of the discrete Fourier transform (FFT) are also discussed.

The fourth chapter, “Time Meets Frequency,” is where the real meat of AWT starts. In the first part, Mr. Mallat describes in detail the STFT; the second part discusses the WT. For these two TF transforms many essential properties are proven, such as energy conservation, uniqueness, and completeness. Uniqueness ensures that the original signal can be obtained from its TF representation. Completeness means that the entire TF-plane is fully partitioned by the transform. The spectrogram (squared magnitude of STFT) and scalogram (squared magnitude of WT) are introduced with several figures. These essentially show how energy is distributed in time and frequency or scale. Another visualization of time-frequency energy, the quadratic Wigner-Ville distribution, is presented in the last section.

Chapter 5 presents frame theory, which provides a formalized way to determine various properties of a given set of discretized TF functions. For instance, it gives the necessary conditions under which the discrete STFT is stable and complete. It also provides a way to make the WT translation-invariant, a result also known as the dyadic WT. Frame theory is essential for designing computer implementations of any TF transform possessing desirable properties.

A unique aspect of the WT is its ability to resolve a signal at multiple levels. By reducing the scale of a wavelet one in effect “zooms in” on the signal. Chapter 6, “Wavelet Zoom,” discusses this ability in the context describing the type of “singularities”—spots that are not infinitely differentiable—that may exist in the signal (for instance in fractal signals). The Fourier transform can only do this on a global level, and its trouble efficiently representing any type of singularity is well known. These signal aspects are important because singular regions may reveal something of interest, such as edges in images, or transients in musical signals. As the author says in the introduction, “The world of transients is considerably larger and more complex than the garden of stationary signals” that are efficiently analyzed with Fourier methods (p. 1).

Chapter 7, the longest of AWT, discusses the heart of multiresolution analysis: the wavelets themselves. Here we see the design of wavelets, their properties, and their utility in multiresolution approximations. This chapter also reveals an important relationship between wavelets and multirate filterbank theory, an interpretation due to Mr. Mallat’s seminal work. An orthogonal wavelet basis is shown to be equivalent to the impulse responses of a conjugate mirror filter bank. This relationship provides an avenue for fast wavelet transforms. Whereas the FFT makes Fourier analysis of real signals tractable, the fast wavelet transform does so for multiresolution analysis.

While the discrete STFT results in a uniform tiling of the TF domain, and the WT gives a tiling that is logarithmic in time and frequency, more exotic tilings can be creating using “wavelet packets.” This is the subject of chapter 8. Additionally, the author discusses lapped transforms, of which the discrete STFT, and the lapped discrete Cosine transform (for instance the modified discrete cosine transform used in MPEG-1, Layer 3 audio coding), are examples.

Chapter 9, “An Approximation Tour,” takes us from linear to non-linear signal approximations. A signal can be approximated using a linear combination of any subset of basis vectors. Choosing the first 20 terms in a Fourier series analysis of a signal creates a low-frequency approximation of it. If instead the 20 terms with the largest energies are selected, a better approximation may result. Such a procedure, choosing basis functions depending on the signal, is non-linear. One can go a step further and instead build a basis on the fly, adapting in a sense to the structures in the signal. The goal here is to create a representation that is at once sparse, efficient, and meaningful for the signal. Here one is not restricted to conditions of orthogonality; functions can be selected from any collection desired. This is currently a very exciting area in signal processing (I may be biased, however, since this is the subject of my doctoral dissertation). In the world of computer music, this method provides the analytical equivalent to granular synthesis.

The final two chapters discuss in detail the application of wavelets to problems of signal estimation, and efficient coding of signals in the transform domain. In Chapter 10, Mr. Mallat demonstrates one of the most useful aspects of wavelets: denoising of signals. In contrast to methods using Fourier analysis, denoising can be effectively done using wavelets and thresholding of coefficients. More advanced techniques have been used to denoise, for instance, an early wax cylinder recording of Johannes Brahms playing the piano. Chapter 11, “Transform Coding,” discusses the application of wavelets to signal compression, of which the best-known result has produced JPEG2000. After reviewing quantization, entropy coding, and compression optimized with respect to distortion, the author presents image and video compression using wavelets.

One of the most unique aspects of AWT is its “reproducible experiment” approach: “The reproducibility of experiments thus requires having the complete software and full source code for inspection, modification and application under varied parameter settings” (p. 17). Taking a bow to lessons learned from the history and philosophy of science, Mr. Mallat has made available the MATLAB (produced by MathWorks, Inc.) code used in producing all figures in the text in order to more fully demonstrate vital aspects of wavelets. Indeed the real results of much of this work are not embodied in terse mathematical expressions, but in the actual implementation with computer code. Working with the code of this book is just as important as reading it. The second appendix provides a list of this software.

The title of AWT makes it clear that this book is about the world of signal processing seen through the lens of multiresolution analysis. While Fourier methods are quite well established in the field of computer music through uses such as pitch-detection and sound transformation, wavelets have found more use in practical applications, such as denoising, than in creative ones. Computer musicians have learned that wavelets are fragile entities, and even a minimal amount of modification in a wavelet representation can result in undesired artifacts. Interesting effects can be created, but to produce a desired effect, e.g., pitch shift, is profoundly difficult. Wavelets will not replace Fourier analysis. Instead the two will complement each other and provide efficient and meaningful representations of signals. With the continuing development of decompositions using redundant and over-complete “dictionaries” of wavelets—so called “pursuit strategies” discussed in chapter 8—such meaningful transformation of signal content will be possible with great precision in time and frequency.

There is nothing in AWT that I would suggest be changed. Mr. Mallat has done a remarkable job producing a rigorous and complete text that can serve as a textbook and a reference. It is refreshing to read a technical book written by an expert that remains approachable at many levels. A Wavelet Tour of Signal Processing is truly an essential guidebook to accompany travel through the sometimes steep, but never treacherous, slopes of wavelet theory.