信号处理的小波导引（英文版·第2版） (2009 年度畅销榜NO.4616 )

本书取材于作者在多所国际知名大学讲授”小波信号处理”课程时的讲义，作者以信号处理的问题为背\r\n\r\n景，用浅显的数学语言阐述小波理论及应用，使读者可以透过复杂的数学公式来窥探小波的精髓，但又不致\r\n\r\n陷入小波纯数学理论的迷宫。\r\n\r\n 本书既可以让计算机及电子工程系的学生了解工程问题的数学描述．又可以让数学系的学生了解数学公\r\n\r\n式的工程意义，是一本极有价值的教材及参考书。\r\n\r\n\r\n\r\n 作者简介：\r\n\r\n Stephane Mallat是纽约大学Courant学院计算机科学系的教授，法国巴黎Ecole理工大学应用数学系的教授，并兼任麻省理工学院电子工程系以及特拉维夫大学应用数学系的客座教授。\r\n\r\nMallat博士还曾荣获\r\n\r\n ·1990年IEEE信号处理学会评选的论文奖。\r\n\r\n ·1993年“斯隆”数学研究基金。\r\n\r\n ·1997年SPIE光学仪器工程师学会评选的杰出成就奖。\r\n\r\n ·1997年法国科学院评选的应用数学方面的“Blaise帕斯卡”奖。\r\n
\r\n

PREFACE xiii \r\n\r\n PREFACE TO THE SECOND EDITION xviii \r\n\r\n NOTATION xx \r\n\r\n I \r\n\r\n INTRODUCTION TO A TRANSIENT WORLD \r\n\r\n 1.1 Fourier Kingdom \r\n\r\n 1.2 Time-Frequency Wedding \r\n\r\n 1.2.1 Windowed Fourier Transform \r\n\r\n 1.2.2 Wavelet Transform \r\n\r\n 1.3 Bases of Time-Frequency Atoms \r\n\r\n 1.3.1 Wavelet Bases and Filter Banks \r\n\r\n 1.3.2 Tilings of Wavelet Packet and Local Cosine Bases \r\n\r\n 1.4 Bases for What? \r\n\r\n 1.4.1 Approximation \r\n\r\n 1.4.2 Estimation \r\n\r\n 1.4.3 Compression \r\n\r\n 1.5 Travel Guide \r\n\r\n 1.5.1 Reproducible Computational Science \r\n\r\n 1.5.2 Road Map \r\n\r\n II \r\n\r\n FOURIER KINGDOM \r\n\r\n 2.1 Linear Time-Invariant Filtering 1 \r\n\r\n 2.1.1 Impulse Response \r\n\r\n 2.1.2 Transfer Functions \r\n\r\n 2.2 Fourier Integrals l \r\n\r\n 2.2.1 Fourier Transform in L1(R) \r\n\r\n 2.2.2 Fourier Transform in L2(R) \r\n\r\n 2.2.3 Examples \r\n\r\n 2.3 Properties 1 \r\n\r\n 2.3.1 Regularity and Decay \r\n\r\n 2.3.2 Uncertainty Principle \r\n\r\n 2.3.3 Total Variation \r\n\r\n 2.4 Two-Dimensional Fourier Transform 1 \r\n\r\n 2.5 Problems \r\n\r\n III \r\n\r\n DISCRETE REVOLUTION \r\n\r\n 3.1 Sampling Analog Signals 1 \r\n\r\n 3.1.1 Whittaker Sampling Theorem \r\n\r\n 3.1.2 Aliasing \r\n\r\n 3.1.3 General Sampling Theorems \r\n\r\n 3.2 Discrete Time-Invariant Filters 1 \r\n\r\n 3.2.1 Impulse Response and Transfer Function \r\n\r\n 3.2.2 Fourier Series \r\n\r\n 3.3 Finite Signals 1 \r\n\r\n 3.3.1 Circular Convolutions \r\n\r\n 3.3.2 Discrete Fourier Transform \r\n\r\n 3.3.3 Fast Fourier Transform \r\n\r\n 3.3.4 Fast Convolutions \r\n\r\n 3.4 Discrete Image Processing 1 \r\n\r\n 3.4.1 Two-Dimensional Sampling Theorem \r\n\r\n 3.4.2 Discrete Image Filtering \r\n\r\n 3.4.3 Circular Convolutions and Fourier Basis \r\n\r\n 3.5 Problems \r\n\r\n IV \r\n\r\n TIME MEETS FREQUENCY \r\n\r\n 4.1 Time-Frequency Atoms 1 \r\n\r\n 4.2 Windowed Fourier Transform 1 \r\n\r\n 4.2.1 Completeness and Stability \r\n\r\n 4.2.2 Choice of Window 2 \r\n\r\n 4.2.3 Discrete Windowed Fourier Transform 2 \r\n\r\n 4.3 Wavelet Transforms 1 \r\n\r\n 4.3.1 Real Wavelets \r\n\r\n 4.3.2 Analytic Wavelets \r\n\r\n 4.3.3 Discrete Wavelets 2 \r\n\r\n 4.4 Instantaneous Frequency 2 \r\n\r\n 4.4.1 Windowed Fourier Ridges \r\n\r\n 4.4.2 Wavelet Ridges \r\n\r\n 4.5 Quadratic Tune-Frequency Energy 1 \r\n\r\n 4.5.1 Wigner-Ville Distribution \r\n\r\n 4.5.2 Interferences and Positivity \r\n\r\n 4.5.3 Cohen's Class 2 \r\n\r\n 4.5.4 Discrete Wigner-Ville Computations 2 \r\n\r\n 4.6 Problems \r\n\r\n V \r\n\r\n FRAMES \r\n\r\n 5.1 Frame Theory 2 \r\n\r\n 5.1.1 Frame Definition and SampLing \r\n\r\n 5.1.2 Pseudo Inverse \r\n\r\n 5.1.3 Inverse Frame Computations \r\n\r\n 5.1.4 Frame Projector and Noise Reduction \r\n\r\n 5.2 Windowed Fourier Frames 2 \r\n\r\n 5.3 Wavelet Frames 2 \r\n\r\n 5.4 Translation Invariance 1 \r\n\r\n 5.5 Dyadic Wavelet Transform 2 \r\n\r\n 5.5.1 Wavelet Design \r\n\r\n 5.5.2 'Algorithme a Trous' \r\n\r\n 5.5.3 Oriented Wavelets for a Vision 3 \r\n\r\n 5.6 Problems \r\n\r\n VI \r\n\r\n WAVELET ZOOM \r\n\r\n 6.1 Lipschitz Regularity 1 \r\n\r\n 6.1.1 Lipschitz Definition and Fourier Analysis \r\n\r\n 6.1.2 Wavelet Vanishing Moments \r\n\r\n 6.1.3 Regularity Measurements with Wavelets \r\n\r\n 6.2 Wavelet Transform Modulus Maxima 2 \r\n\r\n 6.2.1 Detection of Singularities \r\n\r\n 6.2.2 Reconstruction From Dyadic Maxima 3 \r\n\r\n 6.3 Multiscale Edge Detection 2 \r\n\r\n 6.3.1 Wavelet Maxima for Images 2 \r\n\r\n 6.3.2 Fast Multiscale Edge Computations 3 \r\n\r\n 6.4 Multifractals 2 \r\n\r\n 6.4.1 Fractal Sets and Self-Similar Functions \r\n\r\n 6.4.2 Singularity Spectrum 3 \r\n\r\n 6.4.3 Fractal Noises 3 \r\n\r\n 6.5 Problems \r\n\r\n VII \r\n\r\n WAVELET BASES \r\n\r\n 7.1 Orthogonal Wavelet Bases 1 \r\n\r\n 7.1.1 Multiresolution Approximations \r\n\r\n 7.1.2 Scaling Function \r\n\r\n 7.1.3 Conjugate Mirror Filters \r\n\r\n 7.1.4 In Which Orthogonal Wavelets Finally Arrive \r\n\r\n 7.2 Classes of Wavelet Bases 1 \r\n\r\n 7.2.1 Choosing a Wavelet \r\n\r\n 7.2.2 Shannon, Meyer and Battle-Lemarie Wavelets \r\n\r\n 7.2.3 Daubechies Compactly Supported Wavelets \r\n\r\n 7.3 Wavelets and Filter Banks 1 \r\n\r\n 7.3.1 Fast Orthogonal Wavelet Transform \r\n\r\n 7.3.2 Perfect Reconstruction Filter Banks \r\n\r\n 7.3.3 Biorthogonal Bases of I2(z) z \r\n\r\n 7.4 Biorthogonal Wavelet Bases 2 \r\n\r\n 7.4.1 Construction of Biorthogonal Wavelet Bases \r\n\r\n 7.4.2 Biorthogonal Wavelet Design 2 \r\n\r\n 7.4.3 Compactly Supported Biorthogonal Wavelets 2 \r\n\r\n 7.4.4 Lifting Wavelets 3 \r\n\r\n 7.5 Wavelet Bases on an Interval 2 \r\n\r\n 7.5.1 Periodic Wavelets \r\n\r\n IX \r\n\r\n AN APPROXIMATION TOUR \r\n\r\n 9.1 Linear Approximations 1 \r\n\r\n 9.1.1 Linear Approximation Error \r\n\r\n 9.1.2 Linear Fourier Approximations \r\n\r\n 9.1.3 Linear Multiresolution Approximations \r\n\r\n 9.1.4 Karhunen-Loeve Approximations 2 \r\n\r\n 9.2 Non-Linear Approximations 1 \r\n\r\n 9.2.1 Non-Linear Approximation Error \r\n\r\n 9.2.2 Wavelet Adaptive Grids \r\n\r\n 9.2.3 Besov Spaces 3 \r\n\r\n 9.3 Image Approximations with Wavelets 1 \r\n\r\n 9.4 Adaptive Basis Selection 2 \r\n\r\n 9.4.1 Best Basis and Schur Concavity \r\n\r\n 9.4.2 Fast Best Basis Search in Trees \r\n\r\n 9.4.3 Wavelet Packet and Local Cosine Best Bases \r\n\r\n 9.5 Approximations with Pursuits 3 \r\n\r\n 9.5.1 Basis Pursuit \r\n\r\n 9.5.2 Matching Pursuit \r\n\r\n 9.5.3 Orthogonal Matching Pursuit \r\n\r\n 9.6 Problems \r\n\r\n X \r\n\r\n ESTIMATIONS ARE APPROXIMATIONS \r\n\r\n 10.1 Bayes Versus Minimax 2 \r\n\r\n 10.1.1 Bayes Estimation \r\n\r\n 10.1.2 Minimax Estimation \r\n\r\n 10.2 Diagonal Estimation in a Basis 2 \r\n\r\n 10.2.1 Diagonal Estimation with Oracles \r\n\r\n 10.2.2 Thresholding Estimation \r\n\r\n 10.2.3 Thresholding Refinements 3 \r\n\r\n 10.2.4 Wavelet Thresholding \r\n\r\n 10.2.5 Best Basis Thresholding 3 \r\n\r\n 10.3 Minimax Optimality 3 \r\n\r\n 10.3.1 Linear Diagonal Minimax Estimation \r\n\r\n 10.3.2 0rthosymmetric Sets \r\n\r\n 10.3.3 Nearly Minimax with Wavelets \r\n\r\n 10.4 Restoration3 \r\n\r\n 10.4.1 Estimation in Arbitrary Gaussian Noise \r\n\r\n 10.4.2 Inverse Problems and Deconvolution \r\n\r\n 10.5 Coherent Estimation 3 \r\n\r\n 1O.5. I Coherent Basis Thresholding \r\n\r\n 10.5.2 Coherent Matching Pursuit \r\n\r\n 10.6 Spectrum Estimation 2 \r\n\r\n 10.6.1 Power Spectrum \r\n\r\n 10.6.2 Approximate Karhunen-Lotve Search 3 \r\n\r\n 10.6.3 Locally Stationary Processes 3 \r\n\r\n 10.7 Problems \r\n\r\n Xl \r\n\r\n TRANSFORM CODING \r\n\r\n 11.1 Signal Compression z \r\n\r\n 11.1.1 State of the Art \r\n\r\n 11.1.2 Compression in Orthonormal Bases \r\n\r\n 11.2 Distortion Rate of Quantization 2 \r\n\r\n 11.2.1 Entropy Coding \r\n\r\n 11.2.2 Scalar Quantization \r\n\r\n 11.3 High Bit Rate Compression 2 \r\n\r\n 11.3.1 Bit Allocation \r\n\r\n 11.3.2 Optimal Basis and Karhunen-Loeve \r\n\r\n 11.3.3 Transparent Audio Code \r\n\r\n 11.4 Image Compression 2 \r\n\r\n 11.4.1 Deterministic Distortion Rate \r\n\r\n 11.4.2 Wavelet Image Coding \r\n\r\n 11.4.3 Block Cosine Image Coding \r\n\r\n 11.4.4 Embedded Transform Coding \r\n\r\n 11.4.5 Minimax Distortion Rate 3 \r\n\r\n 11.5 Video Signals 2 \r\n\r\n 11.5.1 Optical Flow \r\n\r\n 11.5.2 MPEG Video Compression \r\n\r\n 11.6 Problems \r\n\r\n Appendix A \r\n\r\n MATHEMATICAL COMPLEMENTS \r\n\r\n A.1 Functions and Integration \r\n\r\n A.2 Banach and Hilbert Spaces \r\n\r\n A.3 Bases of Hilbert Spaces \r\n\r\n A.4 Linear Operators \r\n\r\n A.5 Separable Spaces and Bases \r\n\r\n A.6 Random Vectors and Covariance Operators \r\n\r\n A.7 Diracs \r\n\r\n Appendix B \r\n\r\n SOFTWARE TOOLBOXES \r\n\r\n B.1 WAVELAB \r\n\r\n B.2 LASTWAVE \r\n\r\n B.3 Freeware Wavelet Toolboxes \r\n\r\n BIBLIOGRAPHY \r\n\r\n INDEX \r\n
\r\n

Facing the unusual popularity of wavelets in sciences, I began to wonder whether this was just another fashion that would fade away with time. After several years of research and teaching on this topic, and surviving the painful experience of writing a book, you may righfiy expect that I have calmed my anguish. This might be the natural self-delusion affecting any researcher studying his comer of the world, but there might be more.

Wavelets are not based on a "bright new idea", but on concepts that already existed under various forms in many different fields. The formalization and emergence of this "wavelet theory" is the result of a multidisciplinary effort that brought together mathematicians, physicists and engineers, who recognized that they were independently developing similar ideas. For signal processing, this connection has created a flow of ideas that goes well beyond the construction of new bases or transforms.

A Personal Experience At one point, you cannot avoid mentioning who did what.For wavelets, this is a particularly sensitive task, risking aggressive replies from forgotten scientific tribes arguing that such and such results originally belong to them. As I said, this wavelet theory is truly the result of a dialogue between scien-tists who often met by chance, and were ready to listen. From my totally subjective point of view, among the many researchers who made important contributions, I would like to single out one, Yves Meyer, whose deep scientific vision was a major ingredient sparking this catalysis. It is ironic to see a French pure mathematician,

raised in a Bourbakist culture where applied meant trivial, playing a central role along this wavelet bridge between engineers and scientists coming from different disciplines.

When beginning my Ph.D. in the U.S., the only project I had in mind was to travel, never become a researcher, and certainly never teach. I had clearly destined myself to come back to France, and quickly begin climbing the ladder of some big corporation. Ten years later, I was still in the U.S., the mind buried in the hole of some obscure scientific problem, while teaching in a university. So what went wrong? Probably the fact that I met scientists like Yves Meyer, whose ethic and creativity have given me a totally different view of research and teaching. Trying to communicate this flame was a central motivation for writing this book. I hope

that you will excuse me if my prose ends up too often in the no man's land of scientific neutrality.

A Few Ideas Beyond mathematics and algorithms, the book carries a few impor-tant ideas that I would like to emphasize.

Time-frequency wedding Important information often appears through a simultaneous analysis of the signal's time and frequency properties. This motivates decompositions over elementary "atoms" that are well concen-trated in time and frequency. It is therefore necessary to understand how the uncertainty principle limits the flexibility of time and frequency transforms.

· Scale for zooming Wavelets are scaled waveforms that measure signal vari-ations. By traveling through scales, zooming procedures provide powerful characterizations of signal structures such as singularities.

· More and more bases Many orthonormal bases can be designed with fast computational algorithms. The discovery of filter banks and wavelet bases has created a popular new sport of basis hunting. Families of orthogonal bases are created every day. This game may however become tedious if not motivated by applications.

Sparse representations An orthonormal basis is useful if it defines a representation where signals are well approximated with a few non-zero coef ficients. Applications to signal estimation in noise and image compression are closely related to approximation theory.

Try it non-linear and diagonal Linearity has long predominated because of its apparent simplicity. We are used to slogans that often hide the limitations of "optimal" linear procedures such as Wiener filtering or Karhunen-Loeve bases expansions. In sparse representations, simple non, linear diagonal operators can considerably outperform "optimal" linear procedures, and fast algorithms are available.

WAVELAB and LASTWAVE Toolboxes Numerical experimentations are necessary to fully understand the algorithms and theorems in this book. To avoid the painful programming of standard procedures, nearly all wavelet and time-frequency algo-rithms are available in the WAvELAB package, programmed in MATLAB. WAVELAB is a freeware software that can be retrieved through the Internet. The correspon-dence between algorithms and WAVELAB subroutines is explained in Appendix B.

All computational figures can be reproduced as demos in WAVELAB. LASTWAVE is a wavelet signal and image processing environment, written in C for Xl 1/Unix and Macintosh computers. This stand-alone freeware does not require any additional commercial package. It is also described in Appendix B.

Teaching This book is intended as a graduate textbook. It took form after teaching "wavelet signal processing" courses in electrical engineering depart, lents at MIT and Tel Aviv University, and in applied mathematics departments at the Courant Institute and Ecole Polytechnique (Paris).

In electrical engineering, students are often initially frightened by the use of vector space formalism as opposed to simple linear algebra. The predominance of linear time invariant systems has led many to think that convolutions and the Fourier transform are mathematically sufficient to handle all applications. Sadly enough, this is not the case. The mathematics used in the book are not motivated by theoretical beauty; they are truly necessary to face the complexity of transient signal processing. Discovering the use of higher level mathematics happens to

be an important pedagogical side-effect of this course. Numerical algorithms and figures escort most theorems. The use of WAvELAB makes it particularly easy to include numerical simulations in homework. Exercises and deeper problems for class projects are listed at the end of each chapter.

In applied mathematics, this course is an introduction to wavelets but also to signal processing. Signal processing is a newcomer on the stage of legitimate applied mathematics topics. Yet, it is spectacularly well adapted to illustrate the applied mathematics chain, from problem modeling to efficient calculations of solutions and theorem proving. Images and sounds give a sensual contact with theorems, that can wake up most students. For teaching, formatted overhead transparencies with enlarged figures are available on the Internet:

http: //www. cmap. polytechnique, fr/~mallat/Wavetour_fig/.Francois Chaplais also offers an introductory Web tour of basic concepts in the book at

http: //cas. ensmp, fr/~chaplais/Wavetour_presentation/.

Not all theorems of the book are proved in detail, but the important techniques are included. I hope that the reader will excuse the lack of mathematical rigor in the many instances where I have privileged ideas over details. Few proofs are long;they are concentrated to avoid diluting the mathematics into many intermediateresults, which would obscure the text.

Course Design Level numbers explained in Section 1.5.2 can help in designing an introductory or a more advanced course. Beginning with a review of the Fourier transform is often necessary. Although most applied mathematics students have already seen the Fourier transform, they have rarely had the time to understand it well. A non-technical review can stress applications, including the sampling theorem. Refreshing basic mathematical results is also needed for electrical engineering students. A mathematically oriented review of time-invariant signal

processing in Chapters 2 and 3 is the occasion to remind the student of elementary

properties of linear operators, projectors and vector spaces, which can be found

in Appendix A. For a course of a single semester, one can follow several paths,

oriented by different themes. Here are a few possibilities.

One can teach a course that surveys the key ideas previously outlined. Chapter 4 is particularly important in introducing the concept of local time-frequency decompositions. Section 4.4 on instantaneous frequencies illustrates the limitations of time-frequency resolution. Chapter 6 gives a different perspective on the wavelet transform, by relating the local regularity of a signal to the decay of its wavelet coefficients across scales. It is useful to stress the importance of the wavelet vanishing moments. The course can continue with the presentation of wavelet bases in Chapter 7, and concentrate on Sections 7.1-7.3 on orthogonal bases, multireso-lution approximations and filter bank algorithms in one dimension. Linear and

non-linear approximations in wavelet bases are covered in Chapter 9. Depending

upon students' backgrounds and interests, the course can finish in Chapter 10 with

an application to signal estimation with wavelet thresholding, or in Chapter 11 by

presenting image transform codes in wavelet bases.

A different course may study the construction of new orthogonal bases and their applications. Beginning with the wavelet basis, Chapter 7 also gives an introduction to filter banks. Continuing with Chapter 8 on wavelet packet and local cosine bases introduces different orthogonal tilings of the time-frequency plane.

It explains the main ideas of time-frequency decompositions. Chapter 9 on linear and non-linear approximation is then particularly important for understanding how to measure the efficiency of these bases, and for studying best bases search proce dures. To illustrate the differences between linear and non-linear approximation procedures, one can compare the linear and non-linear thresholding estimations studied in Chapter 10.

The course can also concentrate on the construction of sparse representations with orthonormal bases, and study applications of non-linear diagonal operators in these bases. It may start in Chapter 10 with a comparison of linear and non-linear operators used to estimate piecewise regular signals contaminated by a white noise.

A quick excursion in Chapter 9 introduces linear and non-linear approximations to explain what is a sparse representation. Wavelet orthonormal bases are then presented in Chapter 7, with special emphasis on their non-linear approximation properties for piecewise regular signals. An application of non-linear diagonal operators to image compression or to thresholding estimation should then be studied in some detail, to motivate the use of modern mathematics for understanding these problems.

A more advanced course can emphasize non-linear and adaptive signal processing. Chapter 5 on frames introduces flexible tools that are useful in analyzing the properties of non-linear representations such as irregularly sampled transforms.

The dyadic wavelet maxima representation illustrates the frame theory, with applications to multiscale edge detection. To study applications of adaptive repre sentations with orthonormal bases, one might start with non-linear and adaptive approximations, introduced in Chapter 9. Best bases, basis pursuit or matching pursuit algorithms are examples of adaptive transforms that construct sparse representations for complex signals. A central issue is to understand to what extent adaptivity improves applications such as noise removal or signal compression,

depending on the signal properties.

Responsibilities This book was a one-year project that ended up in a never will finish nightmare. Ruzena Bajcsy bears a major responsibility for not encouraging me to choose another profession, while guiding my first research steps. Herprofound scientific intuition opened my eyes to and well beyond computer vision.

Then of course, are all the collaborators who could have done a much better job of showing me that science is a selfish world where only competition counts. The wavelet story was initiated by remarkable scientists like Alex Grossmann, whose modesty created a warm atmosphere of collaboration, where strange new ideas and ingenuity were welcome as elements of creativity.

I am also grateful to the few people who have been willing to work with me.

Some have less merit because they had to finish their degree but others did it on a voluntary basis. I am thinking of Amir Averbuch, Emmanuel Bacry, Francois Bergeaud, Geoff DaviS, Davi Geiger, Fr6d6ric Falzon, Wen Liang Hwang, Hamid Krim, George Papanicolaou, Jean-Jacques Slotine, Alan Willsky, Zifeng Zhang and Sifen Zhong. Their patience will certainly be rewarded in a future life.

Although the reproduction of these 600 pages will probably not kill many trees, I do not want to bear the responsibility alone. After four years writing and rewriting each chapter, I first saw the end of the tunnel during a working retreat at the Fondation des Treilles, which offers an exceptional environment to think,write and eat in Provence. With WAvELAB, David Donoho saved me from spending the second half of my life programming wavelet algorithms. This opportunity was

beautifully implemented by Maureen Clerc and Jerome Kalifa, who made all the figures and found many more mistakes than I dare say. Dear reader, you should thank Barbara Burke Hubbard, who corrected my Franglais (remaining errors are mine), and forced me to modify many notations and explanations. I thank her for doing it with tact and humor. My editor, Chuck Glaser, had the patience to wait but I appreciate even more his wisdom to let me think that I would finish in a year.

She will not read this book, yet my deepest gratitude goes to Branka with whom ,life has nothing to do with wavelets.

Stephane Mallat

无封面