Fundamentals of Wavelets

Theory, Algorithms, and Applications

Jaideva C. Goswami, Andrew K. Chan

• Publisher: Wiley
• Year: 2011
• ISBN:
  9780470934647
• Edition: 2
• Topic: Computer Science
• Subtopic: Programming Algorithms
• Index: Computer Science

Most existing books on wavelets are either too mathematical or they focus on too narrow a specialty. This book provides a thorough treatment of the subject from an engineering point of view. It is a one-stop source of theory, algorithms, applications, and computer codes related to wavelets. This second edition has been updated by the addition of:

• a section on "Other Wavelets" that describes curvelets, ridgelets, lifting wavelets, etc
• a section on lifting algorithms
• Sections on Edge Detection and Geophysical Applications
• Section on Multiresolution Time Domain Method (MRTD) and on Inverse problems

CHAPTER ONE

What Is This Book All About?

The concept of wavelet analysis has been in place in one form or the other since the beginning of this century. The Littlewood-Paley technique and Calderón-Zygmund theory in harmonic analysis and digital filter bank theory in signal processing can be considered forerunners to wavelet analysis. However, in its present form, wavelet theory drew attention in the 1980s with the work of several researchers from various disciplines—Strömberg, Morlet, Grossmann, Meyer, Battle, Lemarié, Coifman, Daubechies, Mallat, and Chui, to name a few. Many other researchers have also made significant contributions.

In applications to discrete data sets, wavelets may be considered basis functions generated by dilations and translations of a single function. Analogous to Fourier analysis, there are wavelet series (WS) and integral wavelet transforms (IWT). In wavelet analysis, WS and IWT are intimately related. The IWT of a finite-energy function on the real line evaluated at certain points in the time-scale domain gives the coefficients for its wavelet series representation. No such relation exists between the Fourier series and Fourier transform, which are applied to different classes of functions; the former is applied to finite energy periodic functions, whereas the latter is applied to functions that have finite energy over the real line. Furthermore, Fourier analysis is global in the sense that each frequency (time) component of the function is influenced by all the time (frequency) components of the function. On the other hand, wavelet analysis is a local analysis. This local nature of wavelet analysis makes it suitable for time-frequency analysis of signals.

Wavelet techniques enable us to divide a complicated function into several simpler ones and study them separately. This property, along with fast wavelet algorithms which are comparable in efficiency to fast Fourier transform algorithms, makes these techniques very attractive for analysis and synthesis. Different types of wavelets have been used as tools to solve problems in signal analysis, image analysis, medical diagnostics, boundary-value problems, geophysical signal processing, statistical analysis, pattern recognition, and many others. While wavelets have gained popularity in these areas, new applications are continually being investigated.

A reason for the popularity of wavelets is their effectiveness in representation of nonstationary (transient) signals. Since most of the natural and manmade signals are transient in nature, different wavelets have been used to represent a much larger class of signals than the Fourier representation of stationary signals. Unlike Fourier-based analyses that use global (nonlocal) sine and cosine functions as bases, wavelet analysis uses bases that are localized in time and frequency to more effectively represent nonstationary signals. As a result, a wavelet representation is much more compact and easier for implementation. Using the powerful multiresolution analysis, one can represent a signal by a finite sum of components at different resolutions so that each component can be adaptively processed based on the objectives of the application. This capability of representing signals compactly and in several levels of resolutions is the major strength of the wavelet analysis. In the case of solving partial differential equations by numerical methods, the unknown solution can be represented by wavelets of different resolutions, resulting in a multigrid representation. The dense matrix resulting from an integral operator can be sparsified using wavelet-based thresholding techniques to attain an arbitrary degree of solution accuracy.

There have been many research monographs on wavelet analysis as well as textbooks for certain specific application areas. However, there does not seem to be a textbook that provides a systematic introduction to the subject of wavelets and its wide areas of applications. This is the motivating factor for this introductory text. Our aims are (1) to present this mathematically elegant analysis in a formal yet readable fashion, (2) to introduce to readers many possible areas of applications both in signal processing and in boundary value problems, and (3) to provide several algorithms and computer codes for basic hands-on practices. The level of writing will be suitable for college seniors and first-year graduate students. However, sufficient details will be given so that practicing engineers without background in signal analysis will find it useful.

The book is organized in a logical fashion to develop the concept of wavelets. The contents are divided into four major parts. Rather than vigorously proving theorems and developing algorithms, the subject matter is developed systematically from the very basics in signal representation using basis functions. The wavelet analysis is explained via a parallel with the Fourier analysis and short-time Fourier transform. The multiresolution analysis is developed for demonstrating the decomposition and reconstruction algorithms. The filter-bank theory is incorporated so that readers may draw a parallel between the filter-bank algorithm and the wavelet algorithm. Specific applications in signal processing, image processing, electromagnetic wave scattering, boundary-value problems, geophysical data analysis, wavelet imaging system and interference suppression are included in this book. A detailed chapter by chapter outline of the book follows.

Chapters 2 and 3 are devoted to reviewing some of basic mathematical concepts and techniques and to setting the tone for the time-frequency and time-scale analysis. To have a better understanding of wavelet theory, it is necessary to review the basics of linear functional space. Concepts in Euclidean vectors are extended to spaces in higher dimension. Vector projection, basis functions, local and Riesz bases, orthogonality, and biorthogonality are discussed in Chapter 2. In addition, least-square approximation of functions and mathematical tools like matrix algebra and z-transform are also discussed. Chapter 3 provides a brief review of Fourier analysis to set the foundation for the development of continuous wavelet transform and discrete wavelet series. The main objective of this chapter is not to redevelop the Fourier theory but to remind readers of some of the important issues and relations in Fourier analysis that are relevant to later development. The main properties of Fourier series and Fourier transform are discussed. Lesser known theorems, including Poisson’s sum formulas, partition of unity, sampling theorem, and Dirichlet kernel for partial sum are developed in this chapter. Discrete-time Fourier transform and discrete Fourier transform are also mentioned briefly for the purpose of comparing them with the continuous and discrete wavelet transforms. Some advantages and drawbacks of Fourier analysis in terms of signal representation are presented.

Development of time-frequency and time-scale analysis forms the core of the second major section of this book. Chapter 4 is devoted to the discussion of short-time Fourier transform (time-frequency analysis) and the continuous wavelet transform (time-scale analysis). The similarities and the differences between these two transforms are pointed out. In addition, window widths as measures of localization of a time function and its spectrum are introduced. This chapter also contains the major properties of the transform such as perfect reconstruction and uniqueness of inverse. Discussions on the Gabor transform and the Wigner-Ville distribution complete this chapter on time-frequency analysis. Chapter 5 contains an introduction to and discussion of multiresolution analysis. The relationships between the nested approximation spaces and the wavelet spaces are developed via the derivation of the two-scale relations and the decomposition relations. Orthogonality and biorthogonality between spaces and between basis functions and their integer translates are also discussed. This chapter also contains a discussion on the semiorthogonal B-spline function as well as mapping techniques of function onto the multiresolution spaces. In Chapter 6, methods and requirements for wavelet construction are developed in detail. Orthogonal, semiorthogonal and biorthogonal wavelets are constructed via examples to elucidate the procedure. Biorthogonal wavelet subspaces and their orthogonal properties are also discussed in this chapter. A derivation of formulas used in methods to compute and display the wavelet is presented at the end of this chapter.

The algorithm development for wavelet analysis is contained in Chapters 7 and 8. Chapter 7 provides the construction and implementation of the decomposition and reconstruction algorithms. The basic building blocks for these algorithms are discussed in the beginning of the chapter. Formulas for decimation, interpolation, discrete convolution and their interconnections are derived. Although these algorithms are general for various types of wavelets, special attention is given to the compactly supported semiorthogonal B-spline wavelets. Mapping formulas between the spline spaces and the dual spline spaces are derived. The algorithms of perfect reconstruction filter banks in digital signal processing are developed via z-transform in this chapter. The time-domain and polyphase-domain equivalent of the algorithms are discussed. Examples of biorthogonal wavelet construction are given at the end of the chapter. In Chapter 8, limitations of the discrete wavelet algorithms, including time-variant property of DWT and sparsity of the data distribution are pointed out. To circumvent the difficulties, the fast integral wavelet transform (FIWT) algorithm is developed for the semiorthogonal spline wavelet. Starting with an increase in time resolution and ending with an increase in scale resolution, a step-by-step development of the algorithm is presented in this chapter. A number of applications using FIWT are included to illustrate its importance. Special topics in wavelets, such as ridgelet, curvelets, complex wavelets, and lifting algorithms, are briefly described.

The final section of this book is on application of wavelets to engineering problems. Chapter 9 includes the applications to signal and image processing, and in Chapter 10, we discuss the use of wavelets in solving boundary value problem. In Chapter 9, the concept of wavelet packet is discussed first as an extension of the wavelet analysis to improve the spectral domain performance of the wavelet. Wavelet packet representation of the signal is seen as a refinement of the wavelet in a spectral domain by further subdividing the wavelet spectrum into subspectra. This is seen to be useful in the subsequent discussion on radar interference suppression. Three types of amplitude thresholding are discussed in this chapter and are used in subsequent applications to show image compression. Signature recognition on faulty bearing completes the one-dimensional wavelet signal processing. The wavelet algorithms in Chapter 7 are extended to two-dimensions for the processing of images. Several edge detection algorithms are described. Major wavelet image-processing applications included in this chapter are image compression and target detection and recognition. Details of the tree-type image coding are not included because of limited space. However, the detection, recognition, and clustering of microcalcifications in mammograsm are given in moderate detail. The application of wavelet packets to multicarrier communication systems and the application of wavelet analysis to three-dimensional medical image visualization are also included. Applications of wavelets in geophysical problems are presented.

Chapter 10 concerns with wavelets in boundary value problem. The traditional method of moment (MOM) and the wavelet-based method of moment are developed in parallel. Different techniques of using wavelet in MoM are discussed. In particular, wavelets on a bounded interval as applied to solving integral equations arising from electromagnetic scattering problems are presented in some detail. These boundary wavelets are also suitable to avoid edge effects in image processing. An application of wavelets in the spectral domain is illustrated by applying them to solving a transmission line discontinuity problem. Finally, the multiresolution time domain method is described along with its applications to electromagnetic problems.

Most of the material is derived from lecture notes prepared for undergraduate and graduate courses in the Department of Electrical Engineering at Texas A&M University as well as for short courses taught in several conferences. The material in this book can be covered in one semester. Topics can also be selectively amplified to complement other signal-processing courses in any existing curriculum. Some homework problems are included in some chapters for the purpose of practice. A number of figures have been included to expound the mathematical concepts. Suggestions on computer code generation are also included at the end of some chapters.

CHAPTER TWO

Mathematical Preliminary

The purpose of this chapter is to familiarize the reader with some of the mathematical notations and tools that are useful in an understanding of wavelet theory. Since wavelets are continuous functions that satisfy certain admissibility conditions, it is prudent to discuss in this chapter some definitions and properties of functional spaces. For a more detailed discussion of functional spaces, the reader is referred to standard texts on real analysis. The wavelet algorithms discussed in later chapters involve digital processing of coefficient sequences. A fundamental understanding of topics in digital signal processing, such as sampling, the z-transform, linear shift-invariant systems, and discrete convolution, are necessary for a good grasp of wavelet theory. In addition, a brief discussion of linear algebra and matrix manipulations is included that is very useful in discrete-time domain analysis of filter banks. Re...

Table of contents

• Cover
• Series page
• Title page
• Copyright page
• Dedication
• Preface to the Second Edition
• Preface to the First Edition
• CHAPTER ONE What Is This Book All About?
• CHAPTER TWO Mathematical Preliminary
• CHAPTER THREE Fourier Analysis
• CHAPTER FOUR Time-Frequency Analysis
• CHAPTER FIVE Multiresolution Analysis
• CHAPTER SIX Construction of Wavelets
• CHAPTER SEVEN DWT and Filter Bank Algorithms
• CHAPTER EIGHT Special Topics in Wavelets and Algorithms
• CHAPTER NINE Digital Signal Processing Applications
• CHAPTER TEN Wavelets in Boundary Value Problems
• Index
• WILEY SERIES IN MICROWAVE AND OPTICAL ENGINEERING