Wavelets : A Survey

Part I : The first generation wavelet

Abstract

Wavelet bases are defined as the dyadic translates and dilates of one particular function, the mother wavelet . They form a versatile tool for representing general functions of L²(R) or data sets. But in some situations, when data lie in the general domain, say , the wavelets must be generalized. Wim Swelden provided such a generalization. In this paper, we just would like to give a brief survey about wavelet theory and its applications. The paper has two parts, in part I we give a short review of the first generation wavelet and in part II we w ill introduce the lifting scheme of Wim Sweldens, a new construction of wavelets which are not necessarily translates and dilates of one fixed function, and give some examples to show how one can construct the traditional wavelets with the Wim Sweldens' lifting scheme.

1. Introduction

Although the wavelet theory has a long history, it has only drawn much attention after a paper of Goupil laud, Grossman and Morlet in geophysical signal processing[9], and two-volume book Ondelettes et Operateurs of Y. Meyer with a strong mathematical framework. After that the Fast Wavelet transform was proposed by Mallat in his paper on multiresolution analysis [11], in particular, Daubechies' orthonornal wavelet with compact support was discovered in 1988 [7], interest in wavelet analysis has grown at an explosive rate. Several applications range from speech, acoustics, to image processing, and fast algorithm in numerical analysis were developed using wave let bases.

The subject is huge and is growing rapidly, to give a short review of the subject is almost an impossible work. One must select some areas and ignore others. In this paper, we would like to give a short introduction to the wavelet theory and only concentrate on orthogonal and biorthogonal wavelets, special Daubechies' wavelets and their relationship with the Sweldens' lifting scheme. The term "wavelet" is meant to suggest "small waves", and the idea is to opposite them to "long ones", like the sine and cosine. Wavelets form a basis for L²(R), say , so that any function f(x) L²(R) can be written as: (1)

where is the usual inner product in L²(R). There are many ways to construct the wavelet basis functions. In the following sections we will consider some of them . The part I of the paper is organized as follows. In section 2 we give a brief introduction to multiresolution analysis which is basic for wavelet theory and its applica tions, include the scaling function and wavelet bases. Section 3 gives a short introduction to filter bank as a tech nique to construct wavelet bases, and the result is the fast wavelet transform algorithm. In section 4, orthonormal wavelets are generalized to biorthonal bases. Wavelet packets introduced by R.R. Coifman, Y. Meyer, and V. Wickerhauser are considered in section 5. Wavelet bases can easy be generalized to higher dimensions, specially the two-dimensional case which is used in image processing. This generalization is the topic of section 6.

2. Multiresolution analysis (MRA)

2.1 Definition

{V_j}_jZ

(i) . . . V_-1 V₀ V₁ . . .
(ii) _jZ V_j = {0} & _jZ V_j is dense in L²(R)
(iii) f(x) V_j f(2x) V_j+1
(iv) f(x) V₀ f(x-k) V₀
(v) There is a function V₀ such that { (x-k), k Z} form a Riesz basis for V₀, i.e. there exist two constants A , B with 0 < A B < such that: (2)

A( | _k |²) _k(x-k) B( | _k |²)

for all square summable sequences { _k }. The function is called a scaling function and is used to construct wavelet bases.

2.2 The scaling function

{ (x-k), k Z }

j Z

_j,k(x) = 2 ^j/2 (2 ^jx - k)

then { _j,k }_kZ form a basis for V_j. Since V_j, there exists a sequence h_k so that: (4)

(x) = h_{k 1,k} (x) = h_k (2x - k)

which is called a refinement equation. Conversely, if we have a function (x) that satisfies the refinement equation (4), then we can construct a MRA by defining V_j = span{ _j,k }_kZ where _j,k are defined by (3). In many cases, no explicit expression for (x) is available. However, there are fast algorithms that use the refinement equation (4) to evaluate the values of at the dyadic points x = 2^-j k, j, k Z. The function is usually normalized so that: (5)

_R (x)dx = 1

and it satisfies the "partition of unity" property: (6)

(x - k) = 1 , x R

The sequence { h_k } plays an important role in the construction of . Under assumptions (5) and (6), we have: (7)

h_k =

(-1)^k h_k = 0

2.3 The wavelet bases

{ V_i }_iZ

V₁ = V₀ W₀

If there exists a function (x) such that { (x - k) }_kZ forms an orthonormal basis for W₀ , then: (9)

_j,k = 2 ^j/2 (2 ^jx - k), k Z

forms an orthonormal basis for , where: (10)

V_j = V_{j - 1} W_{j - 1} = V₀ W₁ W₂ . . . W_{j - 1}

The function (x) is called the "mother wavelet". Since (x) V₁ , it may be expressed as: (11)

(x) = g_{k 1,k} (x) = g_k (2x - k)

The problem now is to find the sequence {g_k} . By using the Fourier Analysis, Daubechies in [5] has found a solution for {g_k} : (12)

g_k = (-1)^k h_{1 - k}

here h_k and g_k are assumed to be real sequences. Let us look at some examples.

2.4 Examples

Let: (13)

(x) = [0, 1) =		1 , x [0, 1
		0 , x [0, 1

hk =		1 / , k = 0 , 1
		0 otherwise

and from (4) we can evaluate g_k : (15)

The Haar wavelet then can be defined as: (16)

By using (9) and (16) we can define a Haar Wavelet basis for L²(R) . The basis functions are well localized in time (compact support), however the frequency localization is not very good since the Fourier transform of (16) decays only as . They are also discontinous.

Example 2 : The Shannon scaling function We start with a scaling function that is a sinc function : (17)

Its Fourier transform is: (18) The coefficients h_k now can be computed by using Parseval's equality and the fact that : 19

It is easy to check that is an orthonomal basis for

And a wavelet function can be obtained by (11) and (12). Any function f(x) V₀ can be written as: (20)

thus a band-limited function in V₀ can be reconstructed by its discrete values on the integers. This is used in signal processing to convert a digital to an analog signal. The formula (20) is the Shannon sampling theorem.

As we can see in these examples that the sequence h_k is very important to construct wavelets. In pratice, it is not sure that a closed form for the scaling function and the associated wavelet function exists or has a simple form. Thus the construction of wavelets based on h_k and g_k is an important approach, specially in signal and image processing. We will deal with this approach in the next section.

3. Wavelets and filter banks

3.1 Filter banks

Figure 1 : Two channel Filter banks is the decimation operator that removes one sample out of two of the original signal x (removes the sample 2 with odd indexes). is the interpolation operator that insert a zero between each two samples, see [20, 22]. 2 Here we assume that h and g are two real sequences. Define the operator H, and similarly for G, that first takes convolution of h and x and then performs decimation of the result. The adjoint operator of H(G) is denoted by H*(G*) that performs interpolation before its convolution. H and G are called the Quadrature Mirror Filters (QMF). Assume that the filter is a finite real sequence of the length L, we get the following results: (21) (22)

Start with a finite real sequence of the length L, we can apply the filter bank scheme of the figure 1 many times to get a continous scaling function. Take x = h, apply the filter bank scheme of the figure 1. Denote h⁽ⁱ⁾ to be the sequence h at the level i, then: (23)

Define

and use (22), we get: (24)

If the function f⁽ⁱ⁾(x) converges to a function (x) as i , then (24) leads to the equation

(x) = h_k (2x - k)

This is the refinement equation (4). Many authors have studied the necessary and sufficient conditions for that (24) to be convergent [7, 8]. We don't review these properties here, but take time to look at the fast wavelet trans form algorithms.

3 .2 The Fast Wavelet Transform Algorithm

_{j, k}

_{j, k}

c_{j, k} = <f , _{j, k} >
d_{j, k} = <f , _{j, k} >

for a given f. The cascade algorithm will compute c_{j, k} at resolution j when we know the coefficients c_{j+1, k} at the finer resolution j + 1 . It is called the analysis (or decomposition) processing. Conversely, the coefficient c_{j+1, k} can be reconstructed from c_{j, k} and d_{j, k} (synthesis or reconstruction). By considering x_k as c_{j+1, k} and (Hx)_k as c_{j, k}, (Gx)_k as d_{j, k} and apply the filter bank scheme of the figure 1, we get the cascade algorithm:

1. Analysis (26)

2. Synthesis (27)

and the inverse wavelet transform will reconstruct the signal c_J from c₀ and {d₁, d₂, . . ., d_J-1} as follows:

Let us look at an example, a signal is given at the resolution as shown in the figure 2. c J J = 3

Figure 2 : The wavelet transform As we can see, the storage place needed to store the coefficients is the same of the original { c 0 , d 1 , d 2 , ..., d J } signal. But the values of the arrays are often small, we get an compression approach. Let us plot { d 1 , d 2 , ..., d J } the Daubechies' scaling function as shown in figure 3. Start with a filter h of the lenght L = 20, see [8] for the va lues of h . Use an array v of lenght 512 (for example) to store the values of at the integers i = 0, 1, ..., 511 . We * initialize v as an impulse signal (at the coarsest level), i. e., for one value j between 0 and v [ k ] = * j , k 511. Apply the inverse wavelet transform, we get the continuos scaling function as plotted in figure 3. With the fast wavelet transform, we don't need to use the functions explicitely. All will work well with the MQF * and * filters . { H, G } Figure 3 : The Daubechies' scaling function , L = 20 However, they have some drawbacks, one of them is that they cannot be both finite impulse response (FIR) and linear phase that is an important property in signal processing. A generalization from orthogonal wavelet bases to biorthogonal wavelet bases is needed and this is the topic that we will consider in the next section.

4. Biorthogonal Wavelets

Figure 4 : The Filter bank scheme The set of operators is said to form a set of biorthogonal quadrature filters if it satifies the follow H, H * , G, G * ing conditions [20}: H * H * = HH * * = I = G * G * = GG * * G * H * = H * G * = GH * * = HG * * = 0 They are usually normalized so that: (33) H 1 = H * 1 = 2 1 and (34) G 1 = G * 1 = 0 where and . Suppose now that we have a biorthogonal 1 = ( . . ., 1 , 1 , 1 , . . . ) T 0 = ( . . ., 0 , 0 , 0 , . . . ) T function set associated with the biorthogonal quadrature filters , then from figure { * , * , * , * } H, H * , G, G * 4: * j , k = 2 * l h * l - 2 k * j + 1 , k (35) * j , k = 2 * l g * l - 2 k * j + 1 , k and similarly for . Set , the cascade algorithm * * j , k and * * j , k c j , k =< f , * * j , k > and d j , k =< f , * * j , k > now becomes : 1. Analysis : c j , k = 2 * l h * l - 2 k c j + 1 , k (36) d j , k = 2 * l g * l - 2 k d j + 1 , k 2. Synthesis (37) c j + 1 , k = 2 * k ( h l - 2 k c j , k + g l - 2 k d j , k )

5. Wavelet Packets

Figure 5 : The wavelet packet Decomposition

6. Multidimensional Wavelets

Figure 6 : Two-dimensional wavelet Decomposition

Figure 7 : Two-dimensional FWT So far, we have reviewed some of the most important subjects of the wavelet theory that now become classical. The wavelets are now going to another phase, the second generation. They must have capacity to represent the functions not only on but also on , for a general domain , or to represent data on curves, surfaces, L 2 ( R ) L 2 (*)

etc. These are topics of part II of this survey. 

References

1. G. Beylkin, R.R Coifman and V. Rokhlin, Fast Wavelet transform and Numerical Algorithms I , Comm. on Pure and Applied Math., vol. XLIV, 141-183, 1991
2. C. K. Chui. An introduction to Wavelets. Academic Press, San Diego, CA, 1992
3. C. K. Chui, editor. Wavelets : A Tutorial in Theory and Applications . Academic Press, San Diego, CA, 1992
4. A. Cohen. Biorthogonal Wavelets.
5. A. Cohen, I. Daubechies, and J. Feauveau. Bi-orthogonal bases of compactly supported wavelets. Comm. Pure Appl. Math., 45: 485-560, 1992
6. R. R. Coifman, Y. Meyer, V. Wickerhauser, Size Properties of Wavelets-Packets, in [17].
7. I. Daubechies. Orthonormal bases of compactly supported wavelets. Comm. Pure Appl. Math. , 41: 909-996, 1988
8. I. Daubechies. Ten lectures on Wavelets. CBMS-NSF Conf. Series in Appl. Math., Vol. 61, SIAM, 1992
9. P. Goupillaud, A. Grossman, and J. Morlet, Cycle-octave and related transform in seismic signal analysis, Geoexploration, vol. 23, pp. 85-102, 1984
10. A. Grossman and J. Morlet, Decomposition of Hardy functions into square integrable wavelets of constant shape, Siam. J. Math. Anal., vol 15, no.4, 1984
11. S. Mallat. Multiresolution approximations and wavelet orthonormal bases of . L 2 ( R ) Trans. Amer. Math. Soc. 315(1) : 69-87, 1989
12. S. Mallat. A theory for multiresolution signal decomposition: The wavelet representation . IEEE Trans. Patt. Anal. Mach. Intell. , 11(7) : 674-693,1989
13. S. Mallat. Multifrequency channel decompositions of images and wavelet models. IEEE Trans. Acoust. Speech Signal Process., 37(12) : 2091-2110, 1989
14. Y. Meyer, Wavelets and Operators, Cambridge University Press, Enlish edition, 1992
15. Y. Meyer, Wavelets, Algorithms & Applications, SIAM, Enlish edition, 1993
16. P. Schröder and W. Swelden. Spherical wavelets : Efficiently representing functions on the sphere. Computer Graphics, SIGGRAPH '95 Proceedings, 1995
17. M. B. Ruskai, Wavelets and Their Applications, Jones and Bartlett publishers, 1992
18. W. Swelden . The lifting scheme : A custom-design construction of biorthogonal wavelets. Technical Report 1994:7, Industrial Mathematics Initiative, Department of Mathematics, University of South Carolina, 1994
19. W. Swelden and P. Schröder . Buiding your own wavelets at home. Technical Report 1995:5, Industrial Mathematics Initiative, Department of Mathematics, University of South Carolina, 1995
20. P.P. Vaidyanathan, Multirate systems and filter banks, Prentice Hall, Inc. 1993
21. M. Vetterli and C. Herley. Wavelets and filter banks: theory and Design. IEEE Trans. on Signal Process. 40(9) : 2207-2232, 1992
22. M. Vetterli and J. Kova evik. Wavelets and Subband Coding. Prentice Hall, c Englewood Cliffs, NJ, 1995
23. G. G. Walter, Wavelets and Other Orthogonal Systems with Applications, CRC Press, Inc. 1994
24. M. V. Wickerhauser, Adapted Wavelet Analysis from theory to Software, A K Peters, Wellesley Massachusetts, 1994

HØit

Nr. 1-96