95f:94005 94A12 00A69 42C15 68U10 94A11
   Meyer, Yves(F-PARIS9-A)
   Wavelets. (English)
   Algorithms & applications.
   Translated from the French and with a foreword by Robert D. Ryan.
   Society for Industrial and Applied Mathematics (SIAM), Philadelphia,
   PA, 1993. xii+133 pp. $19.50. ISBN 0-89871-309-9
   
   The study of wavelets and their applications has enjoyed considerable
   attention over the past decade because of their utility in addressing
   problems in a wide range of disciplines. Among these areas one finds
   signal analysis, image processing, scientific computing, turbulence
   and astronomy. Yves Meyer, who is one of the principals in the
   development of this discipline, has written a particularly fine
   monograph, in conjunction with Ryan as translator, which serves as a
   highly "readable" and worthwhile introduction to the subject. The
   purpose of the book is to describe certain coding algorithms that have
   recently been used to analyze signals with a fractal structure or for
   the compression and storage of information. Having said this, I will
   summarize the contents and features of the book.
   
   The first chapter gives the reader an overview of the scientific
   content of the book, acquaints the reader with the notions of a signal
   and signal processing, and introduces the main objectives and issues
   of the study. Although the author notes many areas of application,
   ranging from telecommunications and image processing to
   neurophysiology, cryptography and archived data found in the FBI's
   fingerprint records, I would view the theme in the context of signal
   and image processing, where the relevant issues are analysis and
   diagnostics, coding, quantization and compression, transmission,
   storage and synthesis and reconstruction. Some basic terminology and
   concepts for "time-frequency" (Grossmann-Morlet) and "time-scale"
   (Gabor and Malvar) type wavelets are set up along with the framework
   for the development of algorithms.
   
   The second chapter has a special status. It develops a historical
   perspective of wavelets and frames some of the major topics for
   discussion in the following chapters. It seems that wavelets are
   synthesized from roughly seven related concepts. The idea begins with
   Fourier (1807), who represented a function in terms of its constituent
   frequencies. Fourier analysis is inadequate in describing many
   phenomena that have a random, "rough" or fractal structure. The first
   steps toward an attempt to address functions with these
   characteristics were taken by Paul Du Bois-Reymond (1873) and Haar
   (1909), in whose studies Fourier's frequency analysis became an
   analysis of scale.
   
   We start an overview of some of the discussion after the real advances
   appeared in the 1930s. Paul Levy showed that the Schauder basis is
   superior to Fourier's in the study of local regularity properties of
   Brownian motion. The motion may be considered a random signal for
   which Fourier analysis is not suited to highlight the inherent
   multifractal structure. A similar deficiency is found by trying to
   localize the energy of a function. The problem is that the norms
   $\Vert f\Vert \sb p$ cannot be calculated or estimated from the
   Fourier coefficients except in the case $p=2$. J. E. Littlewood and R.
   Paley redressed this shortcoming by defining partial sums of Fourier
   series taken in "dyadic blocks" so that the function could be expanded
   as a series of these partial sums. They then determined upper and
   lower bounds on the $p$-norms of the expansion in terms of the
   $p$-norm of the function.
   
   A. Zygmund and his associates considered the Littlewood-Paley result
   on $\bold R\sp n$. It was at this point that the notion of a "mother
   wavelet" $\psi(x)$ arose. Such a function is an infinitely
   differentiable, rapidly decreasing function of $x$ defined on $\bold
   R\sp n$ which has a Fourier transform $\psi\sphat(\xi)$ that satisfies
   the following four properties: $\psi\sphat(\xi)=1$ if
   $1+\alpha\leq\vert \xi\vert \leq 2-2\alpha$, $\psi\sphat(\xi)=0$ if
   $\vert \xi\vert \leq 1-\alpha$ or $\vert \xi\vert \geq 2+2\alpha$,
   $\psi\sphat(\xi)\in C\sp \infty(\bold R\sp n)$, and $\sum\sp \infty\sb
   {-\infty}\vert \psi\sphat(2\sp {-j}\xi)\vert =1$ for $\xi\neq 0$. The
   theory proceeds by setting $\psi\sb j(x)=2\sp {nj}\psi(2\sp jx)$ and
   replacing Littlewood's and Paley's dyadic blocks with the convolution
   products $\Delta\sb j(f)=f*\psi\sb j$. The operators $\Delta\sb j$
   constitute a bank of bandpass filters taken on intervals that cover
   about one octave. The Paley-Littlewood-Stein function is defined by
   $g(x)=(\sum\sp \infty\sb {-\infty}\vert \Delta\sb j(f)\vert \sp 2)\sp
   {1/2}$. The dominant feature of this function is the ability to
   analyze $f(x)$ by basing the analysis on an arbitrary choice of
   scales. The main result states that there exist constants $0\leq c\sb
   p\leq C\sb p$ such that for all $f\in L\sp p(\bold R\sp n)$, $c\sb
   p\Vert f\Vert \sb p\leq\Vert g\Vert \sb p\leq C\sb p\Vert f\Vert \sb
   p$. Later on this theorem is tied in with the work of D. Marr and S.
   Mallat, who derived an effective algorithm for numerical signal
   processing.
   
   I. Daubechies (1987) was able to build on Mallat's theory to complete
   Haar's work by constructing an orthonormal basis for $L\sp 2(\bold R)$
   of the form $2\sp {j/2}\psi\sb r(2\sp jx-k)$, $j,k\in\bold Z$ for each
   integer $r\geq 1$. The functions $\psi\sb r(x)\in C\sp {\gamma r}$,
   $\gamma\sim\frac15$, have support on $[0,2r+1]$ and satisfy $\int\sp
   \infty\sb {-\infty}x\sp k\psi\sb r(x)dx=0$, $k=0,1,\cdots,r$. The Haar
   system which corresponds to the special case $r=0$ is not regular. The
   preselected regularity and compact support of the Daubechies wavelets
   makes them far superior to the Haar system for both analysis and
   synthesis.
   
   The substance of Chapter Two is to trace the paths leading from
   Fourier analysis to two "syntheses". The first path leads to A.
   Calderon ("Calderon's identity") in 1960, to Franklin's and
   Stromberg's wavelets (1981), and then to the work of G. Weiss and R.
   Coifman in the 1980s as a first synthesis based on the notion of
   wavelets and wavelet analysis (atomic decompositions). The second
   synthesis begins with the work of Grossman-Morlet (which is generally
   that of Calderon) and provides a physically intuitive flexible
   approach leading to Daubechies wavelets via Mallat.
   
   My brief accounting of the development omits important contributions
   and contributors and their roles in the foundations of the wavelet
   theory. The chapter is a nice development of the various schools of
   thought. It shows that mathematicians have been developing the concept
   for a long time, and in some cases as groups acting independently of
   each other, so that wavelets have been rediscovered. The chapter is
   written so that a scientist with a basic knowledge of analysis can
   understand the significance of each of the contributions.
   
   The next two chapters concern time-scale algorithms. The third chapter
   introduces quadrature mirror filters. The concept arose in the thesis
   of C. Galand (1983). Galand was motivated to improve the digital
   telephone. He directed his efforts at coding methods for transmitting
   speech well below the standard of 64 kilobits per second. The results
   have applications to many devices that rely on digital information.
   There are three basic types of coding procedures that yield the same
   asymptotic quality for compression. Galand saw that introduction of a
   treelike arrangement of quadrature mirror filters in conjunction with
   a simple coding algorithm would dramatically reduce the effects of
   quantization. Mallat used Galand's notion of time-frequency algorithms
   and quadrature mirror filters to construct time-scale algorithms using
   a "herringbone" algorithm which converges to the analysis of the
   signal in an orthonormal wavelet basis.
   
   The fourth chapter describes pyramid algorithms for numerical image
   processing. The stage is set in the context of cartography, where the
   key information is spread over a broad range of scales. The
   information usually shows a dependence from scale to scale. This
   example suggests imbedded relations and a treelike structure for the
   representation of scales and leads to Burt's and Adelson's pyramid
   algorithms in the context of image compression. Examples of pyramid
   algorithms are presented, including the Laplacian pyramid, which
   occurs later on in the chapter with the introduction of bi-orthogonal
   wavelets. Multiresolution analyses are introduced in the context of
   pyramid analyses by describing a continuous version of the algorithm.
   The multiresolution analysis relies on a huge range of scales in which
   an image is replaced by its best approximation at that scale. The
   algorithm that moves the approximation from one scale to the next
   finer scale and improves the quality of the representation is known as
   multiresolution analysis. Mallat and Y. Meyer explicitly determined
   the interactions between the discrete and continuous versions of the
   algorithms implied by the work of Burt and Adelson.
   
   The flaw in the Burt and Adelson algorithm is that it replaces
   information coded by $N\sp 2$ pixels with information coded by
   $(4/3)N\sp 2$ pixels. This is offset by developing a two-dimensional
   version of Mallat's algorithm to produce an "exact reconstruction"
   identity. A. Cohen examined the outputs of Mallat's algorithm and
   determined limits on the coefficients under very general conditions
   which retained the key information from scale to scale. However,
   orthonormal wavelet bases fall short of the requirements of image
   processing from the point of view of quantization. One of the main
   defects was the lack of symmetry, which resulted in visible defects
   following quantization. This deficiency was overcome by the work of
   Cohen, Daubechies and Jean-Christophe Feauveau, who built on the work
   of P. Tchamitchian to develop symmetric bi-orthogonal compactly
   supported wavelets. M. Barlaud used these wavelets and an efficient
   vector quantization method for coding wavelet coefficients to achieve
   a compression ratio on the order of one to one hundred.
   
   Chapter Five focuses on time-frequency analysis for signal processing.
   The principal discussion centers around the Wigner-Ville transform
   from Ville's viewpoint. The discussion begins with the work of D.
   Gabor (1946) and Jean Ville (1947), who studied the problem of
   developing a mixed signal representation in terms of a double sequence
   of elementary signals. Each of the elementary signals occupies a
   domain in the time-frequency plane which contains useful information
   about the signal frequencies and temporal structure. Ville's idea was
   to unfold a signal in the time-frequency domain so that the
   development would produce a mixed representation in terms of
   time-frequency atoms. The selection of the atoms would be determined
   by the signal's energy distribution in the time-frequency plane. The
   real problem is to determine the best method for decomposing a signal
   into a sum of appropriately chosen time-frequency atoms.
   
   The Wigner-Ville transform addresses this problem. Ville's idea was to
   display the energy density of a signal in the time-frequency plane in
   terms of an energy density function $W(t,\xi)$ which analyzes the time
   and frequency components. This approach commences with a pair of
   Plancherel formulas connecting the signal, its Fourier transform and
   the energy density function $W(t,\xi)$. These formulas are not
   sufficient. One must impose "Moyal's formula", which is a type of
   Parseval identity, together with a condition connected to Gabor's
   time-frequency atoms and their transform $W\sb \xi(t,\xi)$. One then
   finds that the energy density $$W(t,\xi)=\int\sp \infty\sb
   {-\infty}f(t+\tau/2) f\sp *(t-\tau/2)e\sp {-i\xi\tau}d\tau$$ satisfies
   all the previous criteria for finite energy signals. The Wigner-Ville
   transforms of some signals are computed and an important identity
   connecting the Wigner-Ville transform of a signal and its Fourier
   transform is noted. The connections among the transform,
   pseudodifferential operators and quantum mechanics are pointed out.
   The author describes the representation of a signal in terms of the
   corresponding analytic signal. The two major shortcomings of the
   theory are discussed. The author notes that the Wigner-Ville transform
   presents an imperfect representation of the energy distribution in the
   time-frequency domain and that there is no algorithm that permits
   atomic decomposition of a signal analogous to octaves of musical notes
   using these methods.
   
   The sixth chapter concerns time-frequency algorithms based on Malvar's
   wavelets. The idea is to determine procedures for numerical processing
   in real time. These methods favor synthesis and transmission over
   Ville's physics-based analysis. Ville's approach was deficient and did
   not lead to the transmission of information. The main concern here is
   to devise algorithms that expand a signal $f(t)=\sum\sp \infty\sb
   0\alpha\sb jf\sb {R\sb j}(t)$ in the minimum number of terms. The
   nonuniqueness of the decomposition gives flexibility in determining
   optimal decompositions. The time-frequency atoms $f\sb R(t)$ are coded
   by "symbolic" Heisenberg rectangles $R$ in the time-frequency plane.
   The algorithms may be approached from the viewpoint of Malvar wavelets
   or wavelet packets. The Malvar wavelets are in a sense a windowed
   Fourier analysis based on a simpler and more explicit choice of
   windows for the continuous version of the discrete cosine transform.
   R. Coifman and Y. Meyer modified the constructions to obtain variable
   length windows that could be defined arbitrarily.
   
   The Malvar wavelets have attack, stationary and decay components which
   can be selected arbitrarily and independently of each other. These
   characteristics distinguish Malvar's wavelets from the other classes
   of wavelets and give them versatility of design. Pierre-Gilles Lemarie
   and Y. Meyer constructed a function $\psi(t)$ in the Schwartz class
   $S(R)$ for which the functions $2\sp {j/2}\psi(2\sp jt-k)$,
   $j,k\in\bold Z$, form an orthonormal basis for $L\sp 2(\bold R)$.
   These Lemarie-Meyer wavelets are a special case of Malvar's
   construction methods. This is interesting because the Lemarie-Meyer
   wavelets form a time-scale algorithm, in contrast to the Malvar
   wavelets which constitute a time-frequency algorithm. The author
   describes adaptive segmentation, the split and merge algorithm and the
   entropy of a vector relative to an orthonormal basis. The design is
   given of the algorithm that leads to the minimum entropy and optimal
   partition for reduction of transmitted data. The author remarks that
   the chapter presents a striking application of the Grossmann-Morlet
   wavelets, namely that the Grossmann-Morlet analysis determines the
   fractal exponents of a multifractal object as functions of its
   position.
   
   Chapters Six and Seven are complementary. Chapter Six views Malvar
   wavelets which are based on adaptive segmentation whereas Chapter
   Seven offers the dual technique of wavelet packets which are based on
   adaptive filtering. Chapter Seven's point of view is time-frequency
   analysis via wavepackets. The signal is expanded in terms of
   time-frequency atoms which are characterized by their arbitrary
   duration and arbitrary frequency. Gabor's wavelets are the well-known
   example defined by $f\sb R(t)=e\sp {i\omega\sb 0t}h\sp {-1/2}g(t/h)$,
   where $g(t)$ is the Gaussian $g(t)=\pi\sp {-1/4}e\sp {-t\sp 2/2}$. The
   function $f\sb R(t)$ is essentially supported on the Heisenberg
   rectangle $R$. Since the wavelet $f\sb R(t)$ and its Fourier transform
   $f\sphat\sb R(\xi)$ cannot both have compact support, less stringent
   requirements are applied. The Gabor wavelets are precisely the optimal
   solutions to the less stringent criteria in the time-frequency domain.
   However, the wavelets have an annoying property. E. Sere has shown
   that the remoteness of the rectangles $R\sb 0,R\sb 1,R\sb 2,\cdots$
   does not imply that the wavelets $f\sb {R\sb 0}(t),f\sb {R\sb
   1}(t),f\sb {R\sb 2}(t),\cdots$ are well separated from each other. In
   fact, the remoteness of the rectangles does not even guarantee that
   the Gabor wavelets are almost orthogonal.
   
   Wavelet packets are introduced as a remedy to this problem. These
   packets are given by the simple algorithm $2\sp {j/2}w\sb n(2\sp
   jx-k)$, where $n\in\bold N$ and $j,k\in\bold Z$, and the $w\sb n(x)$
   have support on $[0,L]$. We associate each of these wavepackets with
   the frequency interval $I(j,n)$ defined by $2\sp jn\leq\xi\leq 2\sp
   j(n+1)$, and let $E$ be a set of pairs $(j,n)$, $j\in\bold Z$,
   $n\in\bold N$, such that the corresponding frequency intervals form a
   partition of $[0,\infty)$ up to a countable set. Then the subsequence
   $2\sp {j/2}w\sb n(2\sp jx-k)$ with $(j,n)\in E$ and $k\in\bold Z$ is
   an orthonormal basis for $L\sp 2(\bold R)$. The author notes that the
   choice of the partition $E$ is active and that the corresponding
   sampling with respect to the variable $x$ that is prescribed by
   Shannon's theorem is passive. Wavelet packets are organized into
   collections which form orthonormal bases for $L\sp 2(\bold R)$.
   Daubechies' orthogonal wavelets are a special example. It is
   convenient to compare the various choices in the "library" of
   orthonormal bases. The optimal solution is determined by entropy
   criteria which provide an adaptive filter of the signal.
   
   Chapter Seven completes the author's description of "wavelets". This
   theme is central to the first part of the book. The remaining four
   chapters focus on applications of these methods to numerical image
   processing, fractals, turbulence and astronomy. The last two chapters
   summarize articles found in the literature.
   
   Chapter Eight is devoted to computer vision and human vision. The
   author describes and comments on D. Marr's analysis of the "low-level"
   processing of information by the retina. Low-level vision is the
   aspect of human perception that allows us to recreate the
   three-dimensional organization of our environment. Marr's belief was
   that the zero-crossings of the wavelet transform coded the luminous
   information of the retinal cells. Marr's working assumption was that
   human and computer vision face the same problems. The implication is
   that algorithmic structures must be tested within the morphology of
   robotics and artificial vision.
   
   Marr developed three general premises connecting the science of vision
   with the science of robotics. These premises were the foundation of a
   philosophy that sought to construct algorithms from representations
   based on the physiology and psychology of the problem. Marr's belief
   was that human vision was based on a hierarchical structure in which
   the low-level processing provided a representation used at higher
   levels. Contrary to the basis of existing algorithms, he did not
   believe that iterative loops occurred. Marr felt that the retinal
   system utilized a series of line-based sketches scaled on a geometric
   progression. The lines are the zero crossings of his theory. Marr's
   observations of the detection of intensity changes in images lead him
   to construct ("Marr's") wavelets $\psi(x,y)$. The wavelets are derived
   from the the Gaussian distribution $g(x,y)=\exp(-(x\sp 2+y\sp
   2)/2\sigma\sp 2)$ and the "Mexican hat" operator $\Delta g$ via the
   action of the filter $\Delta$ as $\psi(x/\sigma,y/\sigma)=\sigma\sp
   2\Delta g$. When we codify black and white images as levels of gray in
   the function $f(x,y)$, the zero-crossings are precisely the lines of
   the convolution equation $(f*\psi\sb \sigma)=0$. Since the
   convolutions are essentially the wavelet coefficients of $f(x,y)$, the
   zero-crossings are determined when the coefficients vanish.
   
   Marr's conjecture is essentially that the zero-crossings yield a
   natural method of digitizing a two-dimensional image in a manner in
   which all the information is likely to be retained. There are,
   however, counterexamples for periodic images that are not compactly
   supported. The conjecture of S. Mallat, a version of Marr's, is
   examined in detail. Mallat gives an explicit algorithm for image
   reconstruction that works well. Interestingly, his algorithm is based
   on a conjecture which is false. Mallat's methods are described and
   discussed. The author offers as an opinion that the problems of unique
   representation and stable reconstruction in Mallat's conjecture are
   distinguished, and, as a consequence, the reconstruction is never
   stable except in very special cases.
   
   Chapter Nine concerns "wavelets and fractals", a title that covers the
   theme for the remainder of the book. The chapter ties in with earlier
   discussions of the shortcomings exhibited by Fourier analysis in
   describing a signal's multifractal structure. The author shows that
   the Weierstrass function $\omega(t)=\sum\sp \infty\sb 0 2\sp
   {-j}\cos(2\sp jt)$ and its companion $\sum\sp \infty\sb 0 2\sp
   {-j}\sin(2\sp jt)$ are nowhere differentiable. The proofs use wavelets
   and have the general format of Littlewood-Paley analysis. The method
   is G. Freud's. Wavelet analysis provides a main theorem based on the
   modulus of the wavelet coefficients to characterize the regular points
   of a function which is set in a "fractal background". There is an
   interesting discussion of the Riemann function $W(t)=\sum\sp \infty\sb
   1(1/n\sp 2)\sin(\pi n\sp 2t)$, which is studied in terms of the
   analytic signal $F(t)=\sum\sp \infty\sb 1(1/n\sp 2)\exp(i\pi n\sp
   2t)$. The signal's holomorphic extension to the upper half-plane is
   $F(z)$. This extension is analyzed using Luzin's methods to establish
   that the wavelet transform of $F(z)$ is, up to a normalization,
   $F'(z)=i\pi(\theta(z)-1)/2$, where $\theta(z)$ is Jacobi's theta
   function. A Grossman-Morlet wavelet-based transform representation of
   $F(t)$ is developed. This representation is tied in with the main
   theorem to note a proof of a theorem of J. Gerver (1970) that
   completely characterized the points of regularity of $W(t)$.
   
   The last two chapters are very brief. Chapter Ten comments on wavelets
   and the statistical theory of turbulence. The work of M. Farge and her
   studies of two-dimensional fully developed turbulence are noted. The
   author mentions G. Parisi's and U. Frisch's studies of turbulent
   fluids and their conjecture that turbulent flows develop multifractal
   singularities when the Reynolds number is large. The general idea
   seems to be that wavelet analysis may lead to computational techniques
   that improve upon the traditional numerical methods when physical
   problems are involved that suggest self-similarity across scales or
   fractal structures. The monograph concludes with a chapter commenting
   on the work of A. Bijaoui and his collaborators. They are attempting
   to use wavelets to describe the hierarchial structure and formation of
   distant galaxies.
   
   The reader will find a nice balance between the detail of "hard"
   analysis and the exposition supporting the development of the concepts
   and applications. The detail is at a level appropriate to support the
   analysis, yet is not too detailed to burden the "nonexpert" reader who
   seeks to evaluate the potential for application of wavelets in a
   particular area of research. There are a number of nice illustrations
   that explain the algorithms and analysis in "pictorial" form. The
   monograph is the result of the efforts of an author and a translator
   with insight and ability.
             Reviewed by Peter A. McCoy

   © Copyright American Mathematical Society 1995, 1997