AN OVERVIEW OF WWI!-LET BASED MULTIEBSOLUTION ANALYSES
`
`19
`
`the re.
`When applied recursively, the-M formulae defint the feel uioeelet Irumfonn;
`lations (35) and
`define the forward transform, while (37) defines the inverse
`transform”
`Now, from thefact that H[0) = G(w) -_- land G{0} = H(:r] = 0, we see thstB'(u)
`acts like a low pass lllter for the interval [0.1rf2] and G(tu} similarly behaves like a band
`pass filter for the interval [1rf2.1rl. Equation (8) (respectively (12)) then implies that
`the major part of the energy of the functions in V9 (respectively We) is cbnocntrated
`in the intervals {l],s'] (respectively [1r,21r]). The basic behavior of the dual functions
`is the same. In an approicimate sense. this rn_eans that the wavelet expansion splits
`the frequency space into dyadic blocks [2-'1r,21+‘-.r] with j E Z [103, 104].
`In si,g:na.l procuring this idea is known as subband filtering, or, more specifically,
`as quadrature mirror filtering. Quadrature mirror filters were studied before wavelet
`theory.‘ The decomposition step consists of applying a low-pass (H) and a band-
`pass
`filter followed by downsampling (1 2] (Le. retaining only the even index
`samples}, see Figure 1. The reconstruction consists of upsalnpiing (1 2) (i.e. putting
`a -zero between every two samples) followed by filtering and addition. One.-can show
`that the conditions (2?) correspond to the exact reconstruction cl‘ a aubbancl filtering
`scheme. More details about this can be found in I115, 132, 133, 134].
`An interesting problem now is-. given a function I, determine, with a certain
`accuracy and in a computationally favorable way. the coeficionts Am; of a function in
`the space V“. which are needed to start the fast wavelet transform. A trivial solution
`could be
`
`Ami = fW9"l‘
`
`Other sampling procedures. such as [quasi-Jinterpoletion and quadrature formulae
`were proposed in ll, 2. 35.120. 123. 133}.
`An implementation of a fast wavelet transform in pseudo code is given in the
`appendix.
`
`10. Example! of wavelets. Now that we have discussed the essentials of wave-
`let Inultireeolutioa analysis, we tabs a look at some important properties of wavelets.
`
`Orthegnnelity. Orlhogonality is convenient to have in many situations. e.5.
`directly links the L’ norm of a function to the norm of its wavelet coefflcients by
`
`it
`
`llfil = En...
`it
`
`In th biortliogonal case these two quantities are only equivalent. Another advantage
`of orthogonal wavelets it that the fast wavelet transform is a unitary transionuation
`(Le. its atiioiot is its inverse). Consequently, its condition number is equal to 1, which
`is the optimal case. (Recall that the condition number of a linear transformation A
`is defined as
`This is of importance in numerical calculations. It means
`that an error present in the initial data will not grow under the transformation, and
`that stable numerical computations are possible.
`If the multiresolution analysis is orthogonal (remember that this includes semiar-
`thogond wavelets). the projection operators onto the diflsrent subspaces yield optimal
`approximations in the L‘ sense.
`
`Page 360 of 437
`
`Page 360 of 437
`
`

`
`20
`
`BJORN JAWERTH AND Will BWELDENS
`
`Compact support. It the scaling function and wavelet are compactly supported,
`the filters H and G’ are finite impulse responselfllters, so that the summations in
`the fast wavelet transform are finite. This ol:-in-iously is of use in implementations. If
`they are not compactly supported, a. fast decay is desirable so that the filters can be
`approximated reasonably by finite impulse response. lllters.
`
`Rational coefiirimu. For computer implementations it is of use if the filter co-
`efficients hi and 9; are rationals or. even better, dyadic rationals. Multiplication
`by a power of two on a computer corresponds to shifiing bits, which is a very fast
`operation.
`'
`l
`
`Symmetr-yr. lftha scaling functionand wavelet are symmetric, then the filters have
`generalized linear phase. The absence of this property can lead to phase distortion.
`This is important in signal processing applications.
`‘
`
`Smootfmeu. The smoothness of wavelets plays an important role in compression
`applications. Compression is usually achieved by setting small coeilicients 1,-._;
`to
`zero. and thus leaving out a ¢omponent~13_niI_f.;[a:) from the original function.
`If
`the original function represents an image and the wavelet is not smooth, the error
`can easily ‘be detected visually. Note that the smoothness of the primary functions
`is more important to this aspect than that of the dual. Also, a higher degree of
`smoothness corresponds to better frequency localisation of the filters. Finally, smooth
`basis functions are desired in numerical analysis applications where derivatives are
`involved.
`
`Nam-ller of nanisnirig moments of the dual nmnelet. We saw earlier that this is
`important in singularity detection and characterization of smoothness spaces. Also,
`it determines the convergence rate of wavelet approxirnationa of smooth functions.
`Finally,
`the number of vanishing moments of the dual wavelet is connected to the
`smoothness of the Iravelet (and ’vice versa).
`
`Analytic sspmsions. As previously noted. an analytic expression for a scaling
`function or wavelet does not always exists but in some cases it is available and nice
`to have.
`In harmonic analyail, analytic expansions of the Fourier transform are
`particularly useful.
`
`Inierpalntion. If the scaling function satisfies
`
`:,o{ls) = 6;.
`
`for
`
`It E 2,
`
`then it is trivial to llnd the function of if, that interpolates data sampled on a grid
`with spacing 2"’, since the cneffidenta are equal to the samples.
`As could he expected, it is not possible to construct wavelets that have all these
`properties and there is a trade-olf between them. We new take a look at several
`compromises.
`
`.
`Examples of orthogonal wavelets.
`(E) Two simple examples of orthogonal scaling functions are the box function
`x[n‘1;(:) and the Shannon sampling function sinc{:-re). The orthogonality conditions
`are easy to verify. either in the time or trequency space. The corresponding wavelet
`for the box function is the Haar wavelet
`
`lbfionrlzl = x[a.1;a:i3l " xn;_:.ni=r=].
`
`Page 361 of 437
`
`Page 361 of 437
`
`

`
`AN C-)VliRV'IEW OF WAVELET BASE-D MULTIRESOLUTIOH ANALYSES
`
`21
`
`and the Shannon wavelet is
`
`sin(2ire) - sin(1r=)
`'3
`iifsam-uni“) =
`in practice. since the first has very low
`These two, however, are at very useful
`regiilerity and the second has very slow decay.
`-
`(i.i] A more interesting example is the Meyer wavelet and scaling function [106 .
`These functions belong to C“ and have faster than polynomial decay. Their Fourier
`transform is compactly supported. The scaling function and wavelet are symmetric
`around 0 and U2, respectively, and the wavelet has an infinite number of vanishing
`moments.
`
`The Battle-Lemon‘! tonoslets are constructed by orthogoltalizing B—epline
`functions using (30) and have exponential decay [12, 95]. The wavelet with N van-
`ishing moments is s. piecewise polynomial of degree N — 1 that belongs to CR4.
`[iv] Probably the most frequently used orthogonal wavelets are the original Dau-
`hechies wavelets [-IT. 49}. They are afarnily of orthogonal wavelets indexed lJy.N E N.
`where N is the number of vanishing wavelet momenta. They are supported on an in-
`terval of length EN - 1. A disadvantage is that, except for the Haar wavelet {which
`has N ; 1}. they cannot be symmetric or antisymmetric. Their regularity increases
`linearly with N and is approximately equal to |l.2{i75N for large N.
`In {1311 a. dif-
`ferent family‘ with regularity asymptotically equal to 0.31‘? was prmnted.
`In [50]
`three variations of the original family. all with orthogonal and compactly supported
`functions, are contracted:
`1. The previous construction does not lead to a unique solution if N and the
`support length are fixed. One family is constructed by choosing, for each N. the
`solution with closest to linear phase (or closest to symmetry]. In fact, the original
`family corresponds to choosing the extremal phase.
`2. Another funily has more regularity, at the price of a. slightly larger support
`length (2N + 1].
`3. In a third family. the scaling function also has vanishing moments (M, = 0
`for 0 < 12 < N). This in of use in numerical analysis applications where inner products
`of arbitrary functions with scaling functions have to be calculated very test [17]. Their
`construction III asked by Ronald Coifman and Ingrid Dauhechies therefore named
`them eoiflels. They are supported on an interval with length 3N —~ 1.
`
`Eeomples of tisrthogonsl tsasslets.
`(i) Biorthogonal wavelets were constructedilay Albert Cohen, Ingrid Daubechies
`and .le|.n-Christophe Feauveeu in [31]. Here Alp) is chosen equal to e"“', and thus
`
`ch») = —:-W H'(w + tr}
`
`and E'(o) in 4"" HT+ r).
`
`In one of the families oonltructed in [31], the scaling functions are the cardinal B-
`splines and the wavelets too are spline functions. All functions including the duel
`ones have -compact support and linear phase. Moreover. all filter coefllcients are
`dyadic rationals. A disadvantage is that for small filter lengths, the dual functions
`have very low regularity.
`(ii) Serniorthogonal spline wavelets were constructed by Charles Chui and Jinn-
`thong Wang in [23, 34. 25]. The scaling functions are cardinal B-splines of order
`m and the wavelet functions are splines with support [l),2m - ll. All primary and
`dual function: still. have generalized linear phase and all coefiicients used in the fast
`
`Page 362 of 437
`
`Page 362 of 437
`
`

`
`22
`
`aroma JAWERTH sun wm svintnnns
`TABLE I
`A with em-nporiron of wavelet families.
`
`I
` In
`
`in um-ion
`
`1 e
`
`Danbeehiu‘ orthogonal II-avelzels
`blolthognlal spline wsvaletl
`b:
`saudorthogoaal npiine wavelets
`I:-.
`d.‘ Meyer vuvelst
`n
`anliogoasl spline wavelets
`
`wavelet transform are rationals. A powerful feature here is that analytic expressions
`for the wavelet, scaling function, and dual functions are available. A disadvantage
`is that the dual functions do not have oompaot support, but have exponential decay’
`instead. The same wavelets, but in a difisrent setting. were also’ derived by Akrmn
`Aldrouhi, Murray Eden and Michael [inset in [129, 131]. They also showed that for
`N going to infinity, the spline wavelets converge to Gabor functions [I30].
`(iii) Other Iemiorthogonsl wavelets can be found in [39, I09, 110. 113]. A cher-
`ncterization of all semiorthogonel wavelets is given in ii, 2].
`The properties of some of the orthogonal. biorthogoul sud semiorthogonnl wave-
`let families are summarised in ‘Ruble 1.
`
`Example: of interpolating scaling fun-=t:'ana.
`(i) The Shannen sampling function
`
`8":
`
`‘P
`
`an-ion
`
`=
`
`sin(1I':t}
`T:
`
`s
`
`is an interpolating scaling function. It is hand limited, but it has very slow deny.
`(ii) An interpolating scaling function, whose translates also generate Va. can be
`found by letting
`
`i5(=-J]
`_
`._
`v.....rp-:(=-ll - T2Wlrm.
`I
`
`provided that the denominator does not vanish [1, 2, 129, 138]. Even if p is comps.-:I|y_
`supported, m,,...,,; is in general not compactly supported. The cardinal. spline inter-
`polanta of even order are constructed this way [118].
`An interpolating scaling function can also be constructed from 5 pair of
`biorthogonel u-nling functions ea
`
`+00
`so«..:..p.e(z)= I v(y+a=)$7'G')'d:I-
`The interpolation property irnmediatueljf follows from the binrtlzognnality condition.
`In the case of an orthogonal scsling function this is just its autocomletion func-
`tion. The interpolating function and its translates do not generate the some spare ‘
`
`Page 363 of 437
`
`Page 363 of 437
`
`

`
`AN OVERWEW OF WAVELET BASED MULTIILBSOLUTION ANALYSES
`
`23
`
`as to and its translates. This construction, stertirig iron: the Deubechies orthogonal
`or biorthogonsl wavelets, yields a family of interpolating functions which had been
`studied earlier by Gilles Dcslauriers and Serge Duhuc in {56, 5?}. These functions are
`smooth and compactly supported. More information can also be found in [61, 111']. A
`natural choice for the wavelet here is 16(2) = ¢(2:c — 1) and this is a typical example of
`a. wavelet with a non-vanishing integral. The dual scaling function is a Dirac impulse
`and the dual wavelet is a linear combination of Dirac impulses (and has several van-
`ishing moments). we still have a fast wavelet transform with finite impulse response
`filters.
`-
`[iv] Also wavelets can be interpolating. In [2] wavelets that are both symmetrical
`and interpolating were constructed.
`'
`11. Wavelets on an interval. So far we have been discussing wavelet theory
`on the real line (and its higher dimensional analogs). For many applications, the
`functions involved are only defined on a compact set. suds as an interval or a. square.
`and to apply wavelets then requires some modifications.
`11.1. Simple solutions. To be specific, let us discuss the case of the unit inter-
`val [0,1]. Given a function f on [D,1], the most obvious approach is to set fire] = ll
`outside [{l,1], and then use wavelet theory on the line. However, for a general func-
`tion I this “padding with Us” introduces discontinuities at the endpoints O and 1,-
`conslder for example the simple functio Hz} = 1. c E [0,1]. Now. as we have said
`earlier, wavelets are etlective for detecting singularities, so artificial ones are lilnely to
`introduce significant errors.
`Another approach, which is often better, is to consider the function to be periodic
`with period 1, Hz +1) = )'(:t). Expressed in another way, we assume that the
`function is defined on the tons: and identify the torus with [0, I}. Wavelet theory
`on the torus parallels that on the line.
`In fact, note that if f has period 1, then
`the wavelet coefllcisnts on a given scale satisfy (f,1t_;’,,) = ( f,¢j..+:; }, J: E 2,
`j 2 0. This simple observation readily allows us to rewrite was-elet expansions on
`the line as analogous ones on the turns. with wavelets defined on [11, 1]. A periodic
`multirlsolution analysis on the interval [0,1] can be constructed by periodizing the
`basis functions as follows,
`
`(33)
`
`p;,,(:) = x{.,_1,(=) Er,p,'.;(:I: 5- m)
`
`for o e 1 < 2*‘ and j 3 o.
`
`then q:'-_;{::) = to-“(:). Otherwise
`If the support of1p_;';{:), is a subset of [0, 1],
`p,-';(:) is chopped into pieces of length 1, whid are a ilted onto [0,1] and added
`up, yielding tp;I,(:s). Similar definitions hold for 15;,“ J and $11,. The algorithm
`in the appends: describe the periodic fast wavelet transform. This “wrap around”
`procedure is s-atistsctory in many situations {and certainly takes care of functions liine
`,f(:r) = 1. :s E I0.1}). However, unless the behavior of the function f at 0 matches
`that at I,
`the periodic version of f has singularities there. A simple function like
`f(r:] = x, :r E [U.1f, gives a good illustration of this.
`A third method. which works if the basis functions are symmetric. is to use
`reflection across the edges. This preserves continuity, but introduces discontinuities
`in the tint derivative. This solution is sometimes satisfactory in image processing
`applications.
`11.2. Meyerls boundary wavelets. What really is needed. are wavelets in-
`trinsically defined on [0, 1]. We shetch a construction of orthogonal wavelets on [0, 1],
`
`Page 364 of 437
`
`Page 364 of 437
`
`

`
`24
`
`BJORN JAWEKTH AND VWM SWELDENS
`
`recently presented by Yves Meyer [I07]. We start from an orthogonal Dnubechiea
`scaling function with 211! non--tern coeflicients:
`'
`IN‘-1
`
`{$9}
`
`—
`
`:,a(n} =2 )3 it. :p[2z — la).
`:0
`
`It is easy to see thet cios{: : 9(3) 75 D} = [i},2N - 1], and, an a. consequence,
`
`(40)
`
`B,-_. = cloe{z : pfltz) y D} 2 {2'5k,2'j(k + RN —
`
`This implies that for Iufllclently small scales 2'5, j 3 jg, a function 'P;'.l: can only
`intersect at molt one of the endpoints 0 or 1. Lei. us rmtnte this in e. difiereni. way.
`Define the set of indict:
`
`5:‘ = {k = 3:1 0 (0.1) 55 3}-
`
`We define three sublets of this set containing the indicea of the basis functions at the _
`left boundary, in the interior, and at the right boundsry:
`
`39) = {is :0 e 3;_,,}
`5}" = {in : 3;‘, c [n,1)}
`3}” = {t : 1 c n;,_}_
`
`Here E“ denotes the interior of the set E. For sniliciently large j the sets 3:” snd
`5}” are disjoint and
`
`33 = sf,“ u 3}” U Sf’.
`It in easy to write down what these me are more explicitly:
`
`s§‘?={x: —2N+2g:=g -1}
`sj"={e:o:;::;2i—2N+1}
`3}" ={k.~2"—2N+2qr: $2141}.
`
`Note. in particular. that the nets S”) and S?’ contain the indices of MN’ -2 functions,
`independently of 3'. We acne let 140") denote the restriction oifunctionl in
`
`I/fin“! = {I : {(3) = 5(1), 2 E [D,1|, for some function 9 E if}}.
`Clearly, since the P} form an increasing sequence of spaces,
`
`1+1 |'
`'|/jlanll C V_l°.l-l
`
`and vJl°-‘L j 2; 5.. form a mummoiunon anslym of L=([n,11)_ 1: is also obvious
`that the functions in {:p(z — I)|m‘,]
`:
`l E S,-} span ‘irglml. Bare 9(2) ][._1| denotes
`the restriction of 3(1) to [0,1]. Not quite as obvious is the fact that the functions in
`this collection are linen:-ly independent, and hence forrn a. basis for ‘lgmll.
`In order
`
`Page 365 of 437
`
`Page 365 of 437
`
`

`
`AN OVERVIEW OF‘ WAVELET BASED MULTIRESOLUTION ANALYSES
`
`'25
`
`to obtain an orthonormal basis, we may arguelns follows. As long as the function
`{pig lives entirely inside [0, ll, restricting it to [0,1] has no effect. In particular, the
`functions r,o,~_t,
`it E 3?] are still pairwise ortho5arI.I1- A key observation now is that
`for it E 3?}, l' E 5'?) U5"),
`
`1
`(V5.1-r;.i>[o.11= A V’.t‘.ii3.ll"i.l(-’-id? =
`
`i-tn
`—oe
`
`(41)
`
`w;.i(=)v5.:(=id= = 0.
`
`and similarly when It E 3?’. I E 3:“ USE”. We see that the three collections
`{viz '*ili[a.1] = I e s§"1. i‘Pi’ — new = I e SP}. and {sets - rm...” = I e Si-"} are
`mutually orthogonal. So, since the functions in {p(: — l)[[m} : I E S_?;'} already form
`an orthonormal set, there only remains to separately orthogooslise the functions in
`{on — him, = : e 5”} and in {M2 - l)|[.,_1] ; c s s§'i}. no a. easily accomplished
`with a Gram-Schmhlt procedure.
`Now, if we let W,i""i denote the restriction oi functions in W,- to [0, ll; then we_
`have that
`V
`
`(42)
`
`'
`
`vi°-" — vi”-*1 + W!“-‘T.
`
`So, the basis demerits in lK}i°'1i together with the restriction of the wavelets 'p,-_;, to
`[0,1] span Viki}. However. there are 21" + 2N - 2 wavelets that intemoct [DJ], and.
`since dim lf,i_,‘[_'11] — dirnV{°'1i I 2-’ we have too many functions. The restrictions of
`the wavelets in
`that live entirely inside [0,1] are still mutually orthogonal and, by
`an observation similar to [41], they are also orthogonal to iv’,-[°'“. There are EN - 2
`wavelets whose support intersects an endpoint. However. we only need N - 1 basis
`functions at each endpoint. One can now use (30) to write out the dependencies,
`and construct N — l bests functions at each endpoint. After that we just apply a
`Gram-Schmidt procedure again, and we have an orthonormal basis for WJlu'1].
`This elegant construction of Yves Meyer has a couple of disadvantages. Among
`the functions 59,-... that intersect El}, 1] there are seine that are almost zero there. Hence,
`the set {{O_1Ig}§E_g’ is almost linearly dependent, and. an a consequence, the condition
`number of the matrix. corresponding to the change of basis from irp,-,;}t.-,3, to the
`orthonormal one, becomes quite large. lhlrthertnore, we have din: ‘iv’,-[""‘i 7£ dim lvt7__§°"',
`which means that there is an inherent imbalance between the spaces lfj[°"’l and l-IVE“,
`which is not present in the case of the whole real line.
`all polynomials of
`11:8. Dyadic boItndI.l'y Wavelets. As we noted earlier
`degree ( N - 1 can be written as linear combinations of the 50,-‘; for l E
`Hence,
`the restriction of such polynomials to [l], l] are in i”i°'1i. Since this fact is directly
`linked to many of the approximation properties of wavelets, any construction of a
`muitiresolution analysis on [0,1] should preserve this. The construction in [5, 3?. 33]
`uses this as a starting point and is slightly rlifierent from the one by Yves Meyer.
`Let us briefly describe this construction as well. Again we start with an orthogonal
`Daubechies scaling function go with 2N non-zero coellicients, and assume that we have
`picked the scale flue enough so that the endpoints are independent as before. By (33)
`and, since the {pm} is an orthonormal basis for lg. each rnonornial a:'’',- a 5 N — 1.
`has the rsproeentationz“ = E. (z"'.uu,-,1: H-?;,g{x). The restriction to [(1.11 can then
`
`Page 366 of 437
`
`Page 366 of 437
`
`

`
`25
`
`-
`
`BJORN EAWERTH AND WIN SWELDENS
`
`-
`
`o
`
`'."—:N
`
`:‘—1
`
`-’F'l[e.1]'-'( 2 + Z + 2 )(=°'.w.a)v.-'.r(=)l[o.u-
`
`;_.=_-.-11+:
`
`i=1
`
`t=:.«_:N+1
`
`ll
`
`=-’§'..z.=3"’l"“m E (="si°:.rli9:'.t(=ll[a.:]
`J:--.nr+:
`
`31-1
`
`=31; = 2""'“"" X (="»*-at J w:'.n(=)|{u.n.
`h=:1—:lII'+r
`
`_
`I‘ -2?!
`
`md, similarly,
`
`then
`
`9ml3j=)"l{n.1] = 3;; + 2’l"+l‘m Z:
`run;
`
`l1"-‘Pitt l t°:‘.k(¢ll[n,:| + ‘fin-
`
`We let the space: E-, j 2; jg. that form I. niultiresnlution analysis of L’[[O, 1]), be the
`linear span of the functions {z;'_L}.‘y..;, {z;':R}‘,,‘y_]_. and {4p3,g][o,1]}:’=_1“lY:
`
`9;‘ = =}’.':.ln<N-1 U {W.I}l'=i'" U {==§fn}ncN—1
`
`Finding an orthonormal bail for V5 is easy; in fact, the collections {zfiL),¢y_1.
`{r,p,_],}:::‘1’”. and {:rj[n}.gg-l are mutually orthogonal. and
`of the functions in
`these are linearly independent. We thus only have to ortllogonslize the flinctione 5
`and 3 to get our orthonormal heels. Note that. by construction. dint’; = 25 end
`all polfnomialnofdeg-me5N—1arsin l7',~..Itienlsoes.ey hoses that
`
`V} C 93+!-
`
`To get to the corresponding wavelets we let W5 be the orthogonal Dfllnplement of
`'9} ln 'pj+1. The wavelet! ii,-lg with I. Q It ( 2’ —2N are tall in 9}.” and live entirely
`inside [0,1]. The remaining EN functions required for an orthonormal heels of W,-,
`can be found. for example by using (30) again.
`This last construction carries over to more general situations. Flat example. we can
`also use biorthogonal wavelets and much more general closed sets then [0, 1] [5, 33. 8'7].
`There are ollo other c0l|.Bl!.l'1.'lt:tlDIIS oi‘ wavelets on [0,1].
`In (set, for historical
`perspective it is interesting to notice that Fn.nh.lin‘s original construction'[TI‘J] was
`given for [0,1]. Another interesting one, in the case of semiorthogonal spline wavelets,
`has been given by Charles Chui and Ewsld Qua]: [I9]; we refer to the original paper
`l'or details.
`
`12. Wavelet paclnetn. A simple, but most poweriul extension of wavelets and
`multlresolution anelyeln are wevelet packets [3T. 38]. In this section it will be useful
`to evrltch to the following notation:
`
`m.{w} = H‘{r.-J} G"‘(u} for
`
`s = 0.1.
`
`Page 367 of 437
`
`Page 367 of 437
`
`

`
`an ovnimnw or wavewr BASED MULTIRBSOLUTION ANALYSES
`
`27 ‘
`
`
`
`Flo. -I. Weuciet yacht: sdheme.
`
`The fundamental observation is the following fact, cailed the splitting trick I22, 30.
`1B3]:
`Suppose rile! the eel nffimeliam {f(m — it] I
`linear span S. Then the fimetians
`
`it E Z} is a filter: basis fsritr closes‘
`
`and },,‘=-1‘/-§f'(::f2-—l:)
`ff:-71§f°{:r;‘2—k)
`also earuiiiufe a Ride; irasis for S. where
`
`for tez,
`
`I'M = mew/2) Ra/2).
`
`We see that the cleeeicel multireeniution analysis is obtained by splitting V; with
`this trick into V}..; and 39].; and then doing the name for lr}_1 recursively. The
`wavelet packets are the ‘basis functions that we obtain if we also use the spiitting trick
`on the W} spaces. So starting from s speee V}, we obtain, after applying the splitting
`trick L times, the basis functions
`
`with
`
`$c"1.....|;,:j.i(:) = 2(j-L”2""f......e; {2j_La _ ,5)!
`
`;£‘.,....n.(""'} = fimeii 4”} $£2_L“)'
`
`So. after L splittings, we have 25' basis fi1netioris.a.nd their translates over integer
`multiples at‘ 2"" as a basis ef ‘V,-. The connection between the wavelet packets and
`the wavetet and selling fiinctions is
`
`5° = ii’¢i'.'_‘__,n "Id 13’ "= 1i’1",s,...,n-
`In
`However, we do not necessarily have to split each subepece at every stege.
`Figure 4 we give a echemeticnl representation of a space and its subspaces after using
`the splitting on 3 levels. The top rectangle represents the space V; and each other
`rectangle corresponds to I certain subspace of V. generated by wavelet packets. The
`slanted lines between the rectangles indicate the splitting, the left referring to the
`filter mg and the right to 111;. The dashed rectangles then correspond to the wavelet
`.
`
`Page 368 of 437
`
`Page 368 of 437
`
`

`
`28
`
`.
`
`sJonN JAWERTH AND wm swsnnnss
`
`multiresolution anslysis V; =: H. 3 Wfl 93 W1 39 W,. The bold rectangles correspond to
`a possible wavelet peclnet splitting and it boots with functions
`
`"index - Ia). ¢-§..(2z a ma. v:_...tz — re). ¢r..._.t= — 1:) I k e 2}-
`For the dual functions, as similar procedure has to be followed.
`In the Fourier domain, the splitting trick corresponds to dividing the frequency
`interval essentially represented by the original space into two psrte. So the wavelet
`packets allow more flexibility in adapting the basis to the frequency contents of s.
`signal.
`It is easy to develop a last wavelet packet transform. It just involves applying
`the same low and band pass filters also to the coetflcient of functions of W; again
`in an iterative manner. This means that, starting from M samples, we construct a
`full binary tree with [M log, M) entries. The power of this construction lies in the
`fact that we have much more freedom in deciding which basis functions we will use
`to represent the given function. We can choose to use the set of M coeficients of th
`tree to represent the function that is optimal with respect to a certain criterion. This
`procedure _is called best bnsis selection. and one can design fast algorithms that make
`use of the tree structure. The particular criterion is determined by the application.
`and which buis fuuctiorrs that will end up in the basis depends on the data.
`For epplications in image processing, entropy-bsssrl criteria were proposed in
`[ill]. The best basis selection in that case has a numerical complexity of 0(M).
`Applications in slgnsl procmsing can be found in [36, 139].
`This wavelet padhrts construction can also be combined with wsvelete on an
`interval and wavelets in higher dimensions (551.
`13. Multldlsnsmionsl wavelets. Up till now we have focused on functions of
`one variable and the one—dimensional situation. However, there are also wavelets in
`higher dimensions. A simple way to obtain these is to use tensor products. To fix
`ideas, let us oonsider the one of the plane. Let
`
`and define
`
`'1*(mr)- 9(3) wit) -= 9 3 viz. v).
`
`Pi = {I : l'(=.vl = E a...»..¢(=— h.v- km e t'(z'}}.
`the.
`
`Of course, if {pfs - I} I I (E Z} is an orthonormal set, then [i(:s - #1,}: -- kfl} form
`an orthonormal basis for V9. By dyadic scaling we obtain a. multiresolution analysis
`of L‘(R'). The complement We of V9 in V; is similarly generated by the translates
`of the three functions
`.
`
`(43)
`
`-1"" = saw. em = V5 o 59.
`
`and ~1r‘”= too.
`
`There is another, perhaps even more strsightfomard, wavelet decomposition in
`higher dimensions. By carrying out a one-dimensional wavalel. decomposition for each
`variable sepustely, we obtain
`
`(44)
`
`l'i=ut'i = E zilstm 3101.5} 'i'u'.: ®tiJj.s(3.¥l-
`M ,-'.r
`
`Page 369 of 437
`
`Page 369 of 437
`
`

`
`\
`
`AN OVERVIEW OF WAVELET BASED lntULTIlt.E3OL'U'I'lON ANALYSES
`
`29
`
`Note that the functions tint 8 at,“ involve "two scales, 2“ and 2"5, and each at
`these functions are (eslantially) supported on a rectangle. The decomposition (44) is
`therefore called the rectangular wavelet decomposition of f while the functions in [43]
`are the basis Functions of the square wavelet decomposition. For both decompositions,
`the corresponding last wavelet transform consists of applying the one-dimensional fast
`wavelet transform to the rows and columns at a matrix.
`These simple constructions are insunicient in many cases. What we need some-
`times are wavelets intrinsically constructed for higher dimensions. One of the inter-
`esting problems here is how to split a space into complementary subspaces.
`In the
`unitrariate case we split into two spaces, each with essentially the same “size.” If we
`use the square tensor product basis in H. dimensions, we split into 2‘ subspaces, 2“ - 1
`of which are spatlned by wavelets. There are several constructions of nonsvepsrahle
`wavelets that use this hind of splitting. One of the problems here is, given the scal-
`ing Eunction,
`is there an easy wear, at. (1.9), to find the wavelets? This was studied
`in {B4, 113. 121]. Another idea is to still try to split into just two subspaces. This
`involves the use of difiennt lattices
`In the bivariate case, Ingrid Datlbechies
`and Albert Cohan constructed smooth, compactly supported, hiorthogonal wavelets,-
`using ideaslrom the unlvariate construction [29].
`By now, there is a lot of material about multivariate wavelets. However, we shall
`leave this topic for now and just mention some other possibilities such as hexagonal
`lattices. and Clittord valued wavelets [6, 9. 34].
`14. Application.
`
`14.1. Data compression. One of the most common applications of wavelet
`theory is data compression. There are two basic kinds of compression schemes: lossleas
`and lossy. In the case of losslsss compression one is interested in reconstructing the
`data exactly. without any loss of information. We consider here lousy compression.
`This means we are ready to accept an error, as long as the quality after compression is
`acceptable. With losay compression schemes we potentially can achieve much higher
`compression ratios than with lnsslsm compression.
`To be specific, let us assume that we are given a digitized image. The compression
`ratio is defined u the number of bite the initial image takes to store on the computer
`divided by the number of hits required to store the compressed image. The interest
`in compression in general has grown as the amount of information we pass around
`has increased. This is easy to understand when we consider the tact that to store a
`moderately large image, any a 512 X 512 pixels, 2-! hit color image, taken about 0.75
`MB1rtes. This is only for still images: in the case of video, the situation hecornes even
`worse. Then, we need this kind of storage for each frame, and we have something
`like 3fl_fi'arnes per second. There are several reasons other than just the storage
`requirement for the interest in compression techniques. However, instead of going
`into this, let: us now look at the connection with wavelet theory.
`.
`First, let us define, somewhat mathematically, wliat we mean by an image. Let
`us for simplicity discuss an L X L graysosle image with 256 greyscales [i.s. 8 bit]. This
`can be considered to he a piecewise constant function I defined on a square
`
`J(=.tr)'~'-raiEN.
`
`f0rI‘$4=<*'+13="1 J'Sv<J'+1ar-cl 0<i.:'<L.
`
`where E] < pg; Q 255. Now, one of the standard procedures for lousy compression is
`through transl'o_rm coding, see Figure 5. The most common transform used in this
`context is the “Discrete Cosine Transform", which uses a Fourier transform of the
`
`Page 370 of 437
`
`Page 370 of 437
`
`

`
`30
`
`BJORN JAWEKTH AND WIN SWELDENS
`
`original
`imase
`
`song‘:
`transform
`
`coding M
`ooeficients
`
`lnvurln
`transform
`
`reoonstroeled
`“M89
`
`Fm. 5.'Is1te,-ye tnen-efoI'm ooling.
`
`image I. However. we are more interested in the case when the transform is the fast
`iravelet transform.
`There are in tact several ways to use the wavelet transfiorm for compression pur-
`poses [l01_ 102]. One way is to consider compression to be an apprmeimatinn problem
`[58, 59]. More epecifitmlly. let us fix an orthogonal wavelet 1b. Given an integer M 3 1.
`we try to find the "-best” approximation of I by using a representation
`
`[45]
`
`H
`f,;[:} a: E b,1.1,t,»;.(s] with M non-zero coeflicients 5,}.
`
`The basic reason why this potentially might be useful is that each wavelet picks up
`information about the image f essentially at a given location and at a given sale.
`Where the image has more interesting features. we can spend more coefllcients. and
`where the image is nice and smooth we calruse fewer and still get good quality of
`approximation. In other words, the wavelet transform allows us to focus on the not
`relevant parts of 1'. Now. to give this mathematical meaning we need to agree on an
`error measure. Ideally, for image compression we should use a norm that corresponds
`as closely as possible to the human eye [58]. However, let us make it simple and
`discuss the came of L3.
`So we are interested in finding an optimal apprcoimation minlmiring the error
`||f - fyllp. Because of the orthogonafity of the wavelets this equals
`in
`
`(46)
`
`(}:1<:.¢-,1.) -Earl’)
`
`fl
`
`.
`
`A moment's thought, reveals that the best way to pick M’ non-zero coeficients bjh
`making the error as snlall as possible, is by simply picking the M ooeflicients with
`largest absolute value, and setting him = U.tlr;t) for these numbers. This then
`yields the optimal approximation ff,’ .
`Another fundamental question is which images can he spproscimeted well by using
`the procedure just sketched. Let us tabs this to mean that the error