Citation |

- Permanent Link:
- http://digital.auraria.edu/AA00001700/00001
## Material Information- Title:
- The fast wavelet transform (FWT)
- Creator:
- Boyer, Keith G
- Place of Publication:
- Denver, CO
- Publisher:
- University of Colorado Denver
- Publication Date:
- 1995
- Language:
- English
- Physical Description:
- 67 leaves : illustrations ; 29 cm
## Subjects- Subjects / Keywords:
- Wavelets (Mathematics) ( lcsh )
Wavelets (Mathematics) ( fast ) - Genre:
- bibliography ( marcgt )
theses ( marcgt ) non-fiction ( marcgt )
## Notes- Bibliography:
- Includes bibliographical references (leaves 66-67).
- Thesis:
- Submitted in partial fulfillment of the requirements for the degree, Master of Science, Applied Mathematics
- General Note:
- Department of Mathematical and Statistical Sciences
- Statement of Responsibility:
- by Keith G. Boyer.
## Record Information- Source Institution:
- |University of Colorado Denver
- Holding Location:
- |Auraria Library
- Rights Management:
- All applicable rights reserved by the source institution and holding location.
- Resource Identifier:
- 34889301 ( OCLC )
ocm34889301 - Classification:
- LD1190.L622 1995m .B69 ( lcc )
## Auraria Membership |

Downloads |

## This item is only available as the following downloads: |

Full Text |

PAGE 1 The Fast Wavelet Transform (FWT) by Keith G. Boyer B.S.E.E.T., DeVry Institute of Technology, 1984 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Applied Mathematics 1995 PAGE 2 This thesis for the Master of Science degree by Keith G. Boyer has been approved by William L. Briggs William E. Cherowitzo Weldon A. Lodwick Date PAGE 3 Boyer, Keith G. (M.S., Applied Mathematics) The Fast Wavelet Transform (FWT) Thesis directed by Professor William L. Briggs ABSTRACT A mathematical basi s for the constr u c t ion of the fast wavelet t r ansfor m (FWT), based on the wavelets of Daubechies, is given. A contrast is made between the continuous wavelet transform and the discrete wavelet transform that provides the fundamental structure for the fast wavelet transform algorithm. The wavelets considered here lead to orthonormal bases. To realize the orthonormality of these bases, the Fourier transform is u sed to cons t r u c t equivalent realizations of the wa velet r e c ursions i n the spec t ral domain. Thes e spe c t ral r epre sentations lead to a complementary pair of filter t r ansfer functions, f rom whic h the inv erse Fourier t ransfor m can be u sed to generate equivalent Daubechies' convolution coefficients. The discrete wa velet transfor m generated from the convolution filter operations, is incorporated into a recursive filter decimation algorithm that is the FWT. Finally, the FWT is applied to the image compression problem. This abstract accurately represents the content of the candidate' s thesis. Signed ________________________ __ William L. Briggs PAGE 4 Contents Chapter 1. 1.1 1.2 1.3 2. 2.1 2.2 2.3 2.4 3. 3.1 3.2 4. 4.1 4.2 4.3 Introduction Wavelets and Signal Analysis The continuous wavelet Transform Discretization of the Continuous Wavelet Transform Multiresolution Approximations wavelet and scaling Function coefficients Orthonormality of Compactly Supported Wavelets Bi-Orthogonal Decomposition z-Transform and Filter coefficients Daubechies' Construction Spectral Factorization of 12 Daubechies' Examples for N=2 and N=3 Fast Wavelet Transform (FWT) The FWT Algorithm The FWT and Image Compression The FWT Image Compression Algorithm Appendix A. Matlab Code and Compression Images References 1 1 2 5 7 11 12 16 19 22 27 29 34 45 46 48 52 66 PAGE 5 1. Introduction 1.1 Wavelets and Signal Analysis A signal may e xist in its original form as a continuous entity. This continuous signal may then be converted into a quantized form as a sequence of sampled values that describe the signal at discrete points in time. A signal may also be generated in its original form as a discrete sequence. Images and audio signals are e xamples of signals that originate in a continuous form, and a r e stored as discrete sequences on compact disks. These signals may also be generated directly as discrete sequences. Signal analysis is born out of the need to understand the composition of both discrete and continuous signals. This analysis usually takes the form of a sub-space decomposition into a linear combination of basis functions. The classic decomposition tool is the Fourier transform, which decomposes a signal into a linear combination of complex e xponential functions (equivalently, sines and cosines). The concept of signal stationarity plays a key role in determining the effectiveness of the signal decomposition obtained from the Fourier transform. The stationarity of a signal is judged by its statistical invariance over time. If the probability of a signal being a certain value is constant over time, then the signal is said to be stationary. If, however, transient statistical events occur that cannot be predicted, the signal becomes nonstationary. Due to the periodic nature of the Fourier transform, it is ideal for the decomposition and analysis of stationary signals. On the other hand, transient nonstationary signals require a basis that is more localized in both time and frequency. To see how the Fourier transform is not localized in time and frequency, consider the transformation of a square pulse in the time domain. The Fourier transform of this 1 PAGE 6 pulse is a sine (sin(x ) / x ) function in the spectral domain, a function for which the energ y is clearly not localized. As for the time domain, the periodic basis functions of the Fourier transform are clearly not localized [ 5 ] Wavelets solve this problem by having a prescribed smoothness, with energy that is well-localized in both time and frequency. In general, not only do wavelets requir e fewer basis functions than trigonometric basis functions, but the well-localized nature of the wavelet basis ameliorates such reconstruction anomalies as the Gibbs' phenomenon [ 9 ] To understand the wavelet basis, we will consider a continuous t ransformation in L2(R) 1.2 The Continuous Wavelet Transform The wavelet basis is a family of functions based on a well-localized oscillating function 111(t) of t h e real variable t 111(t) i s calle d the because all other wavelet functions within the family are generated from translations and dilations of 111(t). Actually, the mother wavelet 111(t) i s t h e function w i t h zero translation and a dilation of 1 Equation (1 .1) shows the family of functions generated f rom 111 by translation and dilation. In (1 .1), b is the t ranslation variable and a is the dilation variable. 1 ( t-b] 111a,b (t) = -111 -a-' ..;a a >0, be.:IR. (1.1) A simple e xample of a wavelet might be the Mexican hat function 111 (x) (1.2) The mother wavelet of (1 .2) is the solid function is the center of figure (1 .1), together with two translated dilations. 2 PAGE 7 1 .5,----.------.------.---.---.--------, 0 5 \ -0. 5 \ I 1 I I I I I I I I I I I \ \ \ _\':-5 ----1L.O ---5':----o-'-------'------1L-0-----"15 Figure 1.1: Translations and dilations of (x). A restriction on (t) is that it have a zero integral. Actually, for reasons we will discover later, a further restriction on (t) requires that the first m+1 moments vanish. This gives us condition (1 .3), a series of integral moments equal to zero. o = i:w, t) dt -... (1. 3) Figure (1.2) shows plots of the integrands of (1 .3) as an example of the vanishing moments of ( x ) in ( 1.2) In this case, if we consider the integral of the functions in figure (1.2) moments 0 and 1 vanish, while moment 2 does not. 3 PAGE 8 (\ I I 05 Mome n t 1 I I ' 0 5 -1 1 5 Mo me n t 2 2 10 8 6 -4 2 4 6 1 0 Figure 1.2: Moments of (1. 2) With a mother wavelet w meeting t h e restriction of (1 .3), a corresponding set of functions in the form of (1 .1) can be considered. The translation and dilation parameters a b will range over a continuous set S such that the set of functions {Wab} has sufficient cardinality to allow any function fin L2( R) to be reconstructed from the coefficients of the wavelet transform defined by the inner product of f and The inner product of the vector space L2(R) of s quare-integrable, m easurable functions is defined by PAGE 9 This is the analysis of the function or signal that is the motivation for the construction of the wavelet family. The synthesis of f(x) from F involves a linear combination of the original wavelets using the coefficients of F(a,b) The synthesis or inversion formula is given by fJ db da f(x) = F(a,b)lJI b(x)--o -oo a, a 2 These formulas, from a historical perspective, are interesting in that they show the basic analysis involved in the early development of wavelets. However, continuous analysis is usually impractical, which gave rise to discrete solutions of the wavelet analysis problem. For an extensive historical perspective, reference [5] is very complete. 1.3 Discretization of the Continuous Wavelet Transform For the same reasons that we discretize differential equations, we will consider a discretization of the continuous wavelet transform in the (a,b) plane. This discretization will allow for numerical solutions based on a summation rather than a continuous integral. Obviously, many possible discretizations of the continuous (a,b) plane exist. However, only certain restrictions on (a,b) will give the desired basis functions One classic choice for restricting (a,b) is a binary discretization that leads to the wavelets of Daubechies [2]. This binary discretization sets a=2-j and b=ak, where j,k E Z. The discretization of F(a,b) then becomes F(rj,rjk), j,k E z, where the corresponding discrete wavelet functions are defined by (1. 4) 5 PAGE 10 Equation (1.4) is one of three formal definitions of a wavelet [5]. To introduce further wavelet definitions, we must first define the Fourier transform. The Fourier transform of the function fin L2(R) is The inverse Fourier transform is the expression With the Fourier transform pair defined, we can consider the formal wavelet definitions. (1) A wavelet is a function ljr(t) in L2(E) whose Fourier transform satisfies the condition rM = 1 almost J 0 t everywhere, (continuous sense) (2) A wavelet is a function ljr(t) in L2(E) whose Fourier transform satisfies the condition 12 = 1 almost everywhere, (discrete sense) ( 3) A wavelet is a function 1jJ ( t) in L2 (E) such that 2i121jr (2i x-k), j, k E Z is an orthonormal basis for L2 (E). From definitions (2) and (3) above, we can see that each subspace is defined by an integer power of 2. These integer subspaces form a nested sequence of subspaces of L2(R) known as a multiresolution analysis (approximation), which is the subject of the next chapter. 6 PAGE 11 2. Multiresolution Approximations The construction of the fast wavelet transform (FWT) begins by splitting L2(R) i n t o a sequence (V4 ) j e Z, o f closed subspaces, each of which is spanned by an orthonormal basis of translates of a single function keZ, (2 .1) such that the following p roperties hold [14] \fjeZ LJ;: __ V j is dense in L2 (R) & n;: __ V J {0} f(x) e v1 -(2x ) e v1+1 \:1 j e z V0 has an orthogonal basis of translates (x-k), \:1 k e z Given the properties for the basis of above, we can define an approximation of a function f(x ) e L2(R), at the resolution 2j, as the orthogonal projection of f(x ) onto Vj. This is an orthogonal projection because each basis function involved in the approximation of f(x ) is orthogonal to every other. The construction of the o rthogonal p rojection above begins by finding a unique function (x ) e L2(R) A wavelet basis, related to (x), t h e n evolves from the additional information of an approximation at a resolution 2j'1 compared with the resolution 2j. This additional information is just the projection of the orthogonal complement of V in v ,1 That is, v ,1= V $ W,, where W is the space defined by-the projection-of the orthogonal complement of Vj in Vj t1 The space W will be 7 PAGE 12 spanned by the w a velet o rthonormal basis defined b y kEZ. (2. 2) We can summarize the relationship of these subspaces at every level by To u nderstand the p rojection of f onto a n y of the particular subspaces, let' s consider the simple Haar basis defined by (x) { 1, if O!:x PAGE 13 ll1 (x) 1, -1, if 2 1 if -,;;x<1, 2 0, otherwise Figure (2.1) shows the Haar scaling function (x) and corresponding wavelet l!J(x). This is one of the only wavelet functions that can be described explicitly. The wavelets that we will see throughout the rest of this work are recursively defined. As such, they cannot be viewed in the usual way. In later chapters we will see how to view these recursive functions. Figure 2.1: The Haar scaling function (top) and the Haar wavelet w (bottom) If we consider the projection of a function f onto the Haar basis at two resolutions, we would get figure ( 2. 2 ) 9 PAGE 14 Proj. v_o Proj. V_1 Figure 2.2: Some f (x) and its projection onto V0 and V1 spanned by two resolutions of the Haar basis. In figure (2.2), f is projected by the scaling function cj.l(x) onto V0 But we know that V0 c V1 ; that is, V1 is a higher resolution than V0 This explains why the projection of f onto V1 is more accurate than the projection onto V0 It is also important to realize that since V0 c V1 the projection of f onto V0 can exist in V1 but the projection of f onto V1 cannot exist in V0 We briefly introduced the scaling function and restrictions on the coefficients { e n } in the above example. We will now develop restrictions on the wavelet and scaling function coefficients more formally. 10 PAGE 15 2.1 Wavelet and Scaling Function Coefficients With V c V,.1 and (x) E V, -(2x) E V,.1 i t follows thai foi some set of c6efficients (x) can be written as a linear combination of (2x), XER. (2. 3) Alternatively, if we consider equation (2 .3) written as a linear combination of (x ) in the scaled form defined in equation (2 .1), the recursion for (x ) can be written in terms of a new set of coefficients {hn} as X E R (2. 4) so that To normalize (x) we require J :
( 2 Xn ) and W (x) = fi Ln gn Q> (2x-n) Consequently, this power of two algorithm and the FWT operator A defined previously, define the structure of the FWT algorithm. The core of this algorithm is structured correspondingly, into two Matlab functions. The first function "waveletn. m (Matlab A.3, appendix A ) calls the core operator function "daubn. m (Matlab A 4 appendix A) for each resolution of either the transform or inverse transform operation depending on whether the variable transform "xform" is greater than zero or not, respectively. If "transform" is true, the operation continues until the length of the vector is no longer greater than or equal to four. The algorithm stops after four because no more decimation is possible. Each time through the "while" loop the vector is divided in half, corresponding to the multiresolution analysis decimation described above. If "transform" is false, then the inverse transform core operation is called recursively from the lowest resolution (nn=4) to the highest resolution defined by the original vector space size (n) The function "daubn. m is relatively straight forward. The transform operation follows the Row vector multiplies defined by the operator A The main thing to realize here, and in the inverse transform operation, is that these are convolution operations (this is the same as saying that they are filter operation) and, as such, 45 |