第1页 / 共88页
第2页 / 共88页
第3页 / 共88页
第4页 / 共88页
第5页 / 共88页
第6页 / 共88页
第7页 / 共88页
第8页 / 共88页
daubechies小波.pdf
Orthonormal Bases of Compactly Supported Wavelets
INGRID DAUBECHIES
A T&T Bell Laboratories
Abstract
We construct orthonormal bases of compactly supported wavelets, with arbitrarily high regular-
ity. The order of regularity increases linearly with the support width. We start by reviewing the
concept of multiresolution analysis as well as several algorithms in vision decomposition and
reconstruction. The construction then follows from a synthesis of these different approaches.
In recent years, families of functions h4. 6 ,
1. Introduction
a , b E W, a # 0,
generated from one single function h by the operation of dilations and transla-
tions, have turned out to be a useful tool in many different fields of mathematics,
pure as well as applied. Following Grossmann and Morlet [l], we shall call such
families “wavelets”.
Techniques based on the use of translations and dilations are certainly not
new. They can be traced back to the work of A. Calderbn [2] on singular integral
operators, or to renormalization group ideas (see [3]) in quantum field theory and
statistical mechanics. Even in these two disciplines, however, the explicit intro-
duction of special families of wavelets seems to have led to new results (see, e.g.
[4],[5],[6]). Moreover, wavelets are useful in many other applications as well.
They are used for e.g. sound analysis and reconstruction in [7], and have led to a
new algorithm, with many attractive features, for the decomposition of visual
data in [8]. They seem to hold great promise for the detection of edges and
singularities; see [9]. It is therefore fair to surmise that they will have applications
in yet other directions.
Depending on the type of application, different families of wavelets may be
chosen. One can choose, e.g., to let the parameters a , b in (1.1) vary continuously
on their range W * X R (where R * = R \ (0)). One can then, for instance,
represent functions f E L2(W) by the functions Uf,
Communications on Pure and Applied Mathematics, Vol. XLI 909-996 (1988)
6 1988 John Wiley & Sons, Inc.
CCC 0010-3640/88/070909-88$04.00
910
I. DAUBECHIES
If h satisfies the condition
where denotes the Fourier transform,
then U (as defined by (1.2)) is an isometry (up to a constant) from L2(R) into
da db). The map U is called the “continuous wavelet transform”;
L2(W* x W;
see [1],[10]. In this form, wavelets are closest to the original work of Calderbn.
The continuous wavelet transform is also closely related to the “afline coherent
state representation” of quantum mechanics (first constructed in [ll], see also
[12]); in fact, for appropriate choices of h, the h@, are “affine coherent states”,
and have been used in the study of some quantum mechanics problems in
[111, [121.
Note that the “admissibility condition” (1.3) implies, if h has sufficient decay
which we shall always assume in practice, that h has mean zero,
(1 -4)
J d x h ( x ) = 0.
Typically, the function h will therefore have at least some oscillations. A
standard example is
For other applications, including those in signal analysis, one may choose to
restrict the values of the parameters a, b in (1.1) to a discrete sublattice. In this
case one fixes a dilation step a, > 1, and a translation step b, # 0. The family of
wavelets of interest becomes then, for m, n E Z,
(1.6)
h,,(x) =
- nb,).
Note that this corresponds to the choices
a = a,“,
b = nb,a,”,
indicating that the translation parameter b depends on the chosen dilation rate.
For m large and positive, the oscillating function h,,
is very much spread out,
and the large translation steps boa,” are adapted to this wide width. For large but
ORTHONORMAL. BASES OF WAVELETS
91 1
negative m the opposite happens; the function h,, is very much concentrated,
and the small translation steps boa,” are necessary to still cover the whole range.
A “discrete wavelet transform” T is associated with the discrete wavelets
(1.6). It maps functions f to sequences indexed by Z2,
If h is “admissible”, i.e., if h satisfies the condition (1.3), and if h has sufficient
decay, then T maps L2(R) into 12(Z2). In general, T does not have a bounded
inverse on its range. If it does, i.e., if, for some A > 0, B < 00,
for all f in L2(W), then the set { hmn; rn, n E H} is called a “frame”. In this case
one can construct numerically stable algorithms to reconstruct f from its wavelet
coefficients (h,,, f). In particular,
with
For B / A close to 1, which is the case in the decompositions and reconstructions
of music and other sound signals, as done by A. Grossmann, R. Kronland and J.
Morlet [7], the “error term” R can be omitted. In practice, with e.g. the basic
wavelet (lS), and with a, = 21/4, b, = .5, one finds B / A - 1 < lop5, and the
reconstruction formula (1.8) restricted to its first term gives excellent results. In
fact, even for the larger value a, = 2, corresponding to B / A - 1 = .08, the
truncated reconstruction formula, when applied to the wavelet decomposition of
speech signals, leads to a clearly understandable reconstruction; see [13].
In the use of wavelet frames for sound analysis, and reconstruction, as studied
by the Marseilles group [7], the families of wavelets h,, considered are highly
redundant, i.e., they are not independent, in the sense that any finite number of
them lies in the closed linear span generated by the others. Consequently, the
range of the discrete wavelet transform T is a proper subspace of 12(Z2). The
higher the redundancy of the frame, the smaller this subspace, which is a
desirable feature for some purposes (e.g. the reduction of calculational noise). If
a,, b, are chosen very close to 1,0, respectively, then the resulting frame is very
912
I. DAUBECHIES
redundant and very close to the continuous family of wavelets (1.1); this type of
frame was used in the “edge detection” study mentioned earlier; see [9].
For other applications, as e.g. in S. Mallat’s vision decomposition algorithm
in [8], it is preferable to work with the other extremum, and to reduce re-
dundancy as much as possible. In this case, one can turn to choices of h and
a,, b, (typically a, = 2) for which the h,, constitute an orthonormal basis. This
is the case to which we shall be restricting ourselves in the remainder of this
paper. For a more detailed study of general (non-orthonormal) wavelet frames,
and a discussion of the similarities and the differences between wavelet transform
and windowed Fourier transform, the reader is referred to [14], [15].
One example of an orthonormal basis of wavelets’ for L2(R) is the well-known
Haar basis. For the Haar basis one chooses
1, o j x < + ,
f s x < l ,
-1,
0, otherwise,
and a, = 2, b, = 1. The resulting h,,,
(1.10)
h,,(x) = 2-”’%(2-”x - n ) ,
m , n E Z,
constitute an orthonormal basis for L2(W). The h,,
tional basis for all LP(R), 1 < p < 00.
also constitute an uncondi-
Recently, some much more surprising examples of orthonormal wavelet bases
have surfaced. The first one was constructed by Y. Meyer [4] in the summer of
1985. He constructed a C“-function h of rapid decay (in fact h, in his example,
as defined by (1.10)
is a compactly supported Cm-function) such that the h,,,
(i.e., with a , = 2, b, = l), constitute an orthonormal basis for L2(W). As in the
case of the Haar basis, Y. Meyer’s basis is also an unconditional basis for all the
LP spaces, 1 < p < 00. Much more is true, however. The Meyer basis turns out
to be an unconditional basis for all the Sobolev spaces, for the Hardy-Littlewood
space HI, for the Besov spaces, etc.; see [4]. The Meyer basis is therefore a much
more powerful tool than the Haar basis.
Some time later, in 1986, another interesting orthonormal basis of wavelets
was constructed, independently, by P. G. LemariB [17] and G. Battle [18]. In their
construction the function h is only Ck, but it has exponential decay (as compared
‘Following Grossmann and Morlet [l] we call “wavelet” any L2-function h satisfying the admissibil-
ity condition (1.3). This is less restrictive than Y. Meyer [16], who, in keeping with the tradition in
harmonic analysis, also imposes some regularity. In the terminology of [16], the Haar basis function
(1.9) is not a wavelet.
913
with decay faster than any power in Y. Meyer’s case). It also has k vanishing
moments, i.e.,
ORTHONORMAL BASES OF WAVELETS
I d X X ’ h ( X ) = 0,
j = O , l , * . * , k - 1,
which makes these h,, an unconditional basis for all the Sobolev spaces 2$, with
s < k - l .
In all these constructions the choices a, = 2, b, = 1 were made. The choice
for b, is of course arbitrary, a simple dilation of the function h allows one to fix
it is convenient to choose b, = 1. The choice of a, is
any non-zero choice for b,;
far less arbitrary. We shall restrict ourselves here to a, = 2, although it is
possible to consider other, though by no means arbitrary, choices for a, (see
[41,1211).
In the fall of 1986, S. Mallat and Y. Meyer [16],[19] realized that these
different wavelet basis constructions can all be realized by a “multiresolution
analysis”. This is a framework in which functions f E L2(Wd) can be considered
- P, f, where the different
as a limit of successive approximations, f = lim,
P, f, m E Z, correspond to smoothed versions of f, with a “smoothing out
action radius” of the order of 2”’. The wavelet coefficients (h,,, f ), with fixed m,
then correspond to the difference between the two successive approximations
P, - f and P, f. A more detailed description of multiresolution analysis will be
given in Section 2.
~
The concept of multiresolution analysis plays a central role in S. Mallat’s
algorithm for the decomposition and reconstruction of images in [8]. In fact,
ideas related to multiresolution analysis (a hierarchy of averages, and the study of
their differences) were already present in an older algorithm for image analysis
and reconstruction, namely the Laplacian pyramid scheme of P. Burt and E.
Adelson [20]. The Laplacian pyramid ideas triggered S. Mallat to view the
orthonormal bases of wavelets as a vehicle for multiresolution analysis. Together,
S. Mallat and Y. Meyer then carried out a more detailed mathematical analysis,
showing how all the “accidental” previous constructions found their natural
framework in multiresolution analysis; see [16], [19]. By the use of multiresolution
analysis and orthonormal wavelet bases, S. Mallat constructed an algorithm that
is both more economical and more powerful in its orientation selectivity. On the
other hand, by a curious feedback, the combination of Mallat’s ideas and of the
restrictions on “filters” imposed in [20] led to my construction of orthonormal
wavelet bases of compact support, which is the main topic of this paper.
Because of the important role, in the present construction, of the interplay of
all these different concepts, and also to give a wider publicity to them, an
extensive review will be given in Section 2 of multiresolution analysis (subsection
2A), of the Laplacian pyramid scheme (subsection 2B) and of Mallat’s algorithm
(subsection 2C).
Sections 3 and 4 contain the new results of this paper. A closer look at
Mallat’s work shows that he uses the intermediary of orthonormal wavelet bases
914
I. DAUBECHIES
for function spaces to build an essentially discrete algorithm. It seemed therefore
natural to wonder whether similar, and as powerful, discrete algorithms could be
built directly, without using function spaces as an intermediate step. It turns out
that it is very easy to write a set of necessary and sufficient conditions, on the
“discrete side”, ensuring that an algorithm similar to Mallat’s works. This is done
in subsection 3A. In order to have a useful algorithm, however, an extra
regularity condition has to be imposed (this condition is already satisfied in e.g.
Burt and Adelsen’s Laplacian pyramid scheme). This is done in subsection 3B.
The combination of the discrete conditions and the regularity condition on the
discrete algorithm turns out, however, to be strong enough to impose an underly-
ing multiresolution analysis of functions, with associated orthonormal wavelet
basis. Provided the regularity condition is satisfied, there is therefore a one-to-one
correspondence between orthonormal wavelet bases and discrete multiresolution
decompositions, in the sense of Mallat’s algorithm. This equivalence is proved in
subsection 3C. Another proof of the same result, using different techniques, can
be found in [19]; the proof presented here is more “graphical”, and closer to the
“filter” point of view of [20].
In Section 4, we exploit the equivalence between discrete and function
schemes to build orthonormal bases of wavelets with compact support. Using this
equivalence, it turns out that it is sufficient to build a discrete scheme using filters
with a finite number of taps. This can be done explicitly, as shown in subsection
4B. As a result one can construct, for any k E N, a Ck-function + with compact
support, such that the corresponding +,,,
+&) = 2-”’751(2-”x - n),
the regularity. Moreover, + has K consecutive moments equal to zero,
constitute an orthonormal basis. The size of the support increases linearly with
JdXxi+(x) = 0,
j = O , l , * . - , K - 1,
where K also increases linearly with k. All these properties of the construction
are proved in subsection 4C. Finally, the “graphical” approach which, as ex-
plained in subsection 3B, was the guideline to the proof of the link between the
“regularity” condition of Burt and Adelson (see subsection 2B) and multiresolu-
tion analysis, can also be used to plot the functions +. We conclude this paper
with the plots of a few of the compactly supported wavelets constructed here.
2. Multiresolution Analysis and Image Decomposition and Reconstruction
2.A. A review of multiresolution analysis and orthonormal wavelet bases. In
this subsection we review the definition of multiresolution analysis, and show
how orthonormal bases of wavelets can be constructed starting from a multireso-
lution analysis. We illustrate this construction with examples. No proofs will be
given; for proofs, more details and generalizations we refer to [16], [19] or [21].
ORTHONORMAL BASES OF WAVELETS
915
The idea of a multiresolution analysis is to write L2-functions f as a limit of
successive approximations, each of which is a smoothed version of f, with more
and more concentrated smoothing functions. The successive approximations thus
use a different resolution, whence the name multiresolution analysis. The succes-
sive approximation schemes are also required to have some translational invari-
ance. More precisely, a multiresolution analysis consists of
(i) a family of embedded closed subspaces V, C L2(W), m E h,
* * - c V 2 c V l c V o c V ~ , c V ~ , c
* . .
(2.1)
such that (ii)
(2.2)
and (iii)
n V, = (01, m= LYW),
rn€Z
,€Z
(2.3)
moreover, there is a + E Vo such that, for all m E H, the +ffln constitute an
unconditional basis for V,, that is, (iv)
f E V, *f(2 *) E Vm-l;
(2.4a)
and there exist 0 < A 6 B < co such that, for all ( c J n G z E 12(h),
n E Z}
V, = linear span { +,,,
(2.4b)
A C I C ~ I ~ ~ ~ ~ ~ ~ n + r n n l ~
n
2
s BClcnt2*
n
Here +,,(x) = 2-m/2+(2-"x - n). Let P, denote the orthogonal projection
onto V,. It is then clear from (2.1), (2.2) that lim, -t -,P,f = f, for all f E L2(W).
The condition (2.3) ensures that the V, correspond to different scales, while the
translational invariance
is a consequence of (2.4).
EXAMPLE 2.1. A typical though crude example is the following. Take the V,
to be spaces of piecewise constant functions,
V, = { f~ L ~ ( w ) ; fconstant on [2mn,2m(n + 1) [for all n E z}.
The conditions (2.1)-(2.3) are clearly satisfied. The projections P, are defined by
916
I. DAUBECHIES
The successive P, f (as m decreases) do therefore correspond to approximations
of f on a finer and finer scale. Finally, we can choose for + the characteristic
function of the interval [0,1[,
Clearly, + E Vo and V, = span{ +mn } .
1, O l X < l
,
0, otherwise.
In what follows, we shall revisit this example to illustrate the construction of
an orthonormal wavelet basis from multiresolution analysis.
Note that, in view of (2.3), the condition (2.4a) may be replaced by the weaker
. Moreover, one may, without loss of generality,
condition Vo = span{
are orthonormal (which automatically implies that the cp,,
assume that the
are orthonormal for every fixed m). If the +on are not orthonormal to start with,
then one defines 6 by
(2.5)
(i)^CE) = C $ W ( c J&E + 2 k d 12)-1'2
k c Z
(where we implicitly assume that $ has sufficient decay to make the infinite sum
converge). One finds that
~ span{ +on 1 = span{ 6 O n } ,
~
while, moreover, the 6ofl are orthonormal. See [16] for a detailed proof.
EXAMPLE 2.1 (continued). In this case the +on are orthonormal from the
start. If we define
then
Pmf = C C m n ( f ) +mn*
n
Let us look at the difference between P, f and the next coarser approximation
P, + f. One easily checks that
hence
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
