Preface

Yehoshua Y. Zeevi, Haifa, Israel

Ronald Coifman, New Haven, Connecticut

Wavelets are a generic name for a collection of self similar localized waveforms suitable for signal and image processing. The first set of such functions that constituted an orthonormal basis for L2() was introduced in 1910 by Haar. However the Haar functions do not have good localization in the combined time-frequency space and, therefore, in many cases do not satisfy the properties required in signal and image processing and analysis. The problem of how to construct functions that are well localized in both time and frequency was confronted by communication engineers dealing with the analysis of speech in the 1920s and 1930s. About half a century ago Gabor introduced the optimally localized function, obtained by windowing a complex exponential with a Gaussian window. The main advantage of this localized waveform is in achieving the lowest bound on the joint entropy, defined as the product of effective temporal or spatial extent and frequency bandwidth. However, the Gabor elementary functions, which span L2(), are not orthogonal.

The subject of representation in combined spaces refers to wavelet-type and Gabor-type expansions. Such expansions are more suitable for the analysis and processing of natural signals and images than expansion by the traditional application of Fourier series, polynomials, and other functions of infinite support, since the nonstationarity of natural signals calls for localization in both time (or spatial variables in the case of images) and frequency (or scale) in their representation. While global transforms such as the Fourier transform, which is the most widely used in engineering, describe the spectrum of the entire signal as a whole, the wavelet-type and Gabor-type transforms allow for extraction of the local signatures of the signal as they vary in time, or along the spatial coordinates in the case of images. By correlating signals with appropriately chosen wavelets, certain analysis tasks such as feature extraction, signal compression, and recognition can be facilitated. The ability of wavelets to localize signals in time, or spatial variables in the case of images, allows for a multiresolution approach in signal processing. In fact, since the wavelet transform is defined by either its basic time-scale, position-scale, or decomposition structure, it naturally lends itself to multiresolution analysis. Yet, a great deal of freedom is left for the exact choice of the transform’s kernel and various parameters. Thus, the wavelet approach provides us with a wide range of powerful tools for signal processing and analysis. These are described in this volume.

The general interrelated topics involving multiscale analysis, wavelet and Gabor analysis, can all be viewed as enhancing the traditional Fourier analysis by enabling an adaptation of combined time and frequency localization procedures to various tasks. The simple and basic transition from the global Fourier transform to the localized (windowed) Fourier analysis, consists of segmenting the signal into windows of fixed length, each of which is expanded by a Fast Fourier Transform (FFT) or Discrete Cosine Transform (DCT). This type of procedure corresponds to spectrograms, to Gabor transform, as well as to localized trigonometric transforms. A dual version of this procedure corresponds to filtering the signal, or windowing its Fourier transform, usually referred to as wavelet, wavelet packets, or subband coding transforms.

Wavelet analysis and more generally adapted waveform analysis has provided a simple processing tools, as well as many new tools which evolved as a result of the cross-fertilization of ideas originated in many fields, such as the Calderon-Zygmund theory in mathematics, multiscale ideas from geophysical seismic prospecting, mathematical physics of coherent states and wave packets, pyramid structures in image processing, band and subband filtering in signal processing, music, numerical analysis, etc. In this volume we don’t intend to elaborate on the origin of these ideas, but rather on the current state of this elaborate toolkit and the relative advantages it brings to the scene.

While to some extent most of the qualitative analytical aspects of wavelet analysis, and of the windowed Fourier transform, have been well understood by mathematicians for at least 30 years, the recent explosion of activity and algorithms is due to the discovery of the orthogonal wavelets by Stromberg and Meyer, and the connection to Quadrature Mirror Filter (QMF) by Mallat and Daubechies. More fundamental yet is our better understanding of structures permitting construction of a multitude of orthogonal and nonorthogonal expansions customized to tasks at hand, and enabling the introduction of fast computational methods and realtime processing. The role and usefulness of redundancy in providing stability in signal representation, as opposed to efficiency, has also become clear by means of the application of frame analysis and the Zak transform.

Some of the main tasks that can be accomplished by the application of wavelet-based tools are related to feature extraction and efficient description of large data sets for processing and computations. This is the point where, instead of using algebraic or analytic formulas, functions or measured data are described efficiently by adapted waveforms which are, in turn, described algorithmically and designed specifically to optimize various tasks. Perhaps the most natural analogy to the new modes of analysis (or signal transcription) is provided by musical scores and orchestration; an overlay of time frequency analysis. The musical score is somewhat more general and abstract than the alphabet and corresponds roughly to a description of a piece of music by specifying which notes are being played, i.e., the note’s characteristic pitch, amplitude, duration, and location in time. While traditional windowed Fourier analysis considers a Fourier representation of the signal in each window of space (or time), wavelets, wavelet packets, and their variants provide a description in which notes of different duration (or resolution) are superimposed. For images, this corresponds to an overlay of patterns of different size and scale. This multiscale representation allows for a better separation of textures and structures, and of decomposition of the textures into their basic elements. The complementary procedure introduces a new approach to speech, music, and image synthesis, yet to be further explored.

Most of the chapters in this book are based on the lectures delivered at the Neaman Workshop on Signal and Image Representation in Combined Spaces, held at Technion. Additional chapters were contributed by invitees who could not attend the workshop. The material presented in this volume brings together a rich variety of ideas that blend most aspects of analysis mentioned above. These papers can be clustered into affinity groups as follows:

Variations on the windowed Fourier transform and its applications, relating Fourier analysis to analysis on the Heisenberg group, are provided in the following group of papers: M. An, A. Bordzik, I. Gertner, and R. Tolimieri: “Weyl-Heisenberg System and the Finite Zak Transform;” M. Bastiaans: “Gabor’s Expansion and the Zak Transform for Continuous-Time and Discrete-Time Signals;” W. Schempp: “Non-Commutative Affine Geometry and Symbol Calculus: Fourier Transform Magnetic Resonance Imaging and Wavelets;” M. Zibulski and Y. Y. Zeevi: “The Generalized Gabor Scheme and Its Application in Signal and Image Representation.”

Constructions of special waveforms suitable for specific tasks are given in: J. S. Byrnes: “A Low Complexity Energy Spreading Transform Coder;” A. Cohen and N. Dyn: “Nonstationary Subdivision Schemes, Multiresolution Analysis and Wavelet Packets.”

The use of redundant representations in reconstruction and enhancement is provided in: J. J. Benedetto: “Noise Reduction in Terms of the Theory of Frames;” Z. Cvetkovic and M. Vetterli: “Overcomplete Expansions and Robustness;” F. Bergeaud and S. Mallat: “Matching Pursuit of Images.”

Applications of efficient numerical compression as a tool for fast numerical analysis are described in: A. Averbuch, G. Beylkin, R. Coifman, and M. Israeli: “Multiscale Inversion of Elliptic Operators;” A. Harten: “Multiresolution Representation of Cell-Averaged Data: A Promotional Review.”

Approximation properties of various waveforms in different contexts are described in the following series of papers: A. J. E. M. Janssen: “A Density Theorem for Time-Continuous Filter Banks;” V. E. Katsnelson: “Sampling and Interpolation for Functions with Multi-Band Spectrum: The Mean Periodic Continuation Method;” M. A. Kon and L. A. Raphael: “Characterizing Convergence Rates for Multiresolution Approximations;” C. Chui and Chun Li: “Characterization of Smoothness via Functional Wavelet Transforms;” R. Lenz and J. Svanberg: “Group Theoretical Transforms, Statistical Properties of Image Spaces and Image Coding;” J. Prestin and K. Selig: “Interpolatory and Orthonormal Trigonometric Wavelets;” B. Rubin: “On Calderón’s Reproducing Formula;” and “Continuous Wavelet Transforms on a Sphere;” V. A. Zheludev: “Periodic Splines, Harmonic Analysis and Wavelets.”

Acknowledgments

The Neaman Workshop was organized under the auspices of The Israel...