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