Fundamentals of Wavelets E-Book

Jaideva C. Goswami

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley Series in Microwave and Optical Engineering
• Sprache: Englisch

Seitenzahl: 393

Veröffentlichungsjahr: 2011

Beschreibung

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

Leseprobe

Table of Contents

Cover

Table of Contents

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

2.1 LINEAR SPACES

2.2 VECTORS AND VECTOR SPACES

2.3 BASIS FUNCTIONS, ORTHOGONALITY, AND BIORTHOGONALITY

2.4 LOCAL BASIS AND RIESZ BASIS

2.5 DISCRETE LINEAR NORMED SPACE

2.6 APPROXIMATION BY ORTHOGONAL PROJECTION

2.7 MATRIX ALGEBRA AND LINEAR TRANSFORMATION

2.8 DIGITAL SIGNALS

2.9 EXERCISES

CHAPTER THREE Fourier Analysis

3.1 FOURIER SERIES

3.2 EXAMPLES

3.3 FOURIER TRANSFORM

3.4 PROPERTIES OF FOURIER TRANSFORM

3.5 EXAMPLES OF FOURIER TRANSFORM

3.6 POISSON’S SUM AND PARTITION OF UNITY

3.7 SAMPLING THEOREM

3.8 PARTIAL SUM AND GIBB’S PHENOMENON

3.9 FOURIER ANALYSIS OF DISCRETE-TIME SIGNALS

3.10 DISCRETE FOURIER TRANSFORM (DFT)

3.11 EXERCISES

CHAPTER FOUR Time-Frequency Analysis

4.1 WINDOW FUNCTION

4.2 SHORT-TIME FOURIER TRANSFORM

4.3 DISCRETE SHORT-TIME FOURIER TRANSFORM

4.4 DISCRETE GABOR REPRESENTATION

4.5 CONTINUOUS WAVELET TRANSFORM

4.6 DISCRETE WAVELET TRANSFORM

4.7 WAVELET SERIES

4.8 INTERPRETATIONS OF THE TIME-FREQUENCY PLOT

4.9 WIGNER-VILLE DISTRIBUTION

4.10 PROPERTIES OF WIGNER-VILLE DISTRIBUTION

4.11 QUADRATIC SUPERPOSITION PRINCIPLE

4.12 AMBIGUITY FUNCTION

4.13 EXERCISES

4.14 COMPUTER PROGRAMS

CHAPTER FIVE Multiresolution Analysis

5.1 MULTIRESOLUTION SPACES

5.2 ORTHOGONAL, BIORTHOGONAL, AND SEMIORTHOGONAL DECOMPOSITION

5.3 TWO-SCALE RELATIONS

5.4 DECOMPOSITION RELATION

5.5 SPLINE FUNCTIONS AND PROPERTIES

5.6 MAPPING A FUNCTION INTO MRA SPACE

5.7 EXERCISES

5.8 COMPUTER PROGRAMS

CHAPTER SIX Construction of Wavelets

6.1 NECESSARY INGREDIENTS FOR WAVELET CONSTRUCTION

6.2 CONSTRUCTION OF SEMIORTHOGONAL SPLINE WAVELETS

6.3 CONSTRUCTION OF ORTHONORMAL WAVELETS

6.4 ORTHONORMAL SCALING FUNCTIONS

6.5 CONSTRUCTION OF BIORTHOGONAL WAVELETS

6.6 GRAPHICAL DISPLAY OF WAVELET

6.7 EXERCISES

6.8 COMPUTER PROGRAMS

CHAPTER SEVEN DWT and Filter Bank Algorithms

7.1 DECIMATION AND INTERPOLATION

7.2 SIGNAL REPRESENTATION IN THE APPROXIMATION SUBSPACE

7.3 WAVELET DECOMPOSITION ALGORITHM

7.4 RECONSTRUCTION ALGORITHM

7.5 CHANGE OF BASES

7.6 SIGNAL RECONSTRUCTION IN SEMIORTHOGONAL SUBSPACES

7.7 EXAMPLES

7.8 TWO-CHANNEL PERFECT RECONSTRUCTION FILTER BANK

7.9 POLYPHASE REPRESENTATION FOR FILTER BANKS

7.10 COMMENTS ON DWT AND PR FILTER BANKS

7.11 EXERCISES

7.12 COMPUTER PROGRAM

CHAPTER EIGHT Special Topics in Wavelets and Algorithms

8.1 FAST INTEGRAL WAVELET TRANSFORM

8.2 RIDGELET TRANSFORM

8.3 CURVELET TRANSFORM

8.4 COMPLEX WAVELETS

8.5 LIFTING WAVELET TRANSFORM

CHAPTER NINE Digital Signal Processing Applications

9.1 WAVELET PACKET

9.2 WAVELET-PACKET ALGORITHMS

9.3 THRESHOLDING

9.4 INTERFERENCE SUPPRESSION

9.5 FAULTY BEARING SIGNATURE IDENTIFICATION

9.6 TWO-DIMENSIONAL WAVELETS AND WAVELET PACKETS

9.7 EDGE DETECTION

9.8 IMAGE COMPRESSION

9.9 MICROCALCIFICATION CLUSTER DETECTION

9.10 MULTICARRIER COMMUNICATION SYSTEMS (MCCS)

9.11 THREE-DIMENSIONAL MEDICAL IMAGE VISUALIZATION

9.12 GEOPHYSICAL APPLICATIONS

9.13 COMPUTER PROGRAMS

CHAPTER TEN Wavelets in Boundary Value Problems

10.1 INTEGRAL EQUATIONS

10.2 METHOD OF MOMENTS

10.3 WAVELET TECHNIQUES

10.4 WAVELETS ON THE BOUNDED INTERVAL

10.5 SPARSITY AND ERROR CONSIDERATIONS

10.6 NUMERICAL EXAMPLES

10.7 SEMIORTHOGONAL VERSUS ORTHOGONAL WAVELETS

10.8 DIFFERENTIAL EQUATIONS

10.9 EXPRESSIONS FOR SPLINES AND WAVELETS

Index

WILEY SERIES IN MICROWAVE AND OPTICAL ENGINEERING

WILEY SERIES IN MICROWAVE AND OPTICAL ENGINEERING

KAI CHANG, Editor

Texas A&M University

A complete list of the titles in this series appears at the end of this volume.

Copyright © 2011 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permissions.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Goswami, Jaideva C.

Fundamentals of wavelets : theory, algorithms, and applications / Jaideva C. Goswami, Andrew K. Chan.—2nd ed.

p. cm.—(Wiley series in microwave and optical engineering; 219)

ISBN 978-0-470-48413-5 (hardback); ISBN 978-0-470-93464-7 (ebk)

 1. Wavelets (Mathematics) 2. Image processing–Mathematics. 3. Electromagnetic waves–Scattering–Mathematical models. 4. Boundary value problems. I. Chan, Andrew K. II. Title.

TK5102.9.G69 2010

621.301′5152433—dc22

2010025495

To

Shrimati Sati and Shri Chandra Nath Goswami

— Jaideva C. Goswami

My Lord Jesus Christ from whom I received wisdom and knowledge

and

my wife, Sophia, for her support and encouragement

— Andrew K. Chan

Preface to the Second Edition

Since the appearance of the first edition over a decade ago, several new wavelets and wavelet-like functions have been introduced along with many interesting applications. These developments have motivated us to substantially revise the book and bring out this second edition. The basic structure of the book remains the same. Apart from making a few minor additions and corrections, the first seven chapters are carried over from the earlier edition. In these chapters, wavelet theory and algorithms are gradually and systematically developed from basic linear algebra, Fourier analysis, and time-frequency analysis. Chapter 8 is renamed as “Special Topics in Wavelets and Algorithms” where four new sections on ridgelets, curvelets, complex wavelets, and lifting wavelet transform are introduced. Various edge detection techniques are summarized in a new section in Chapter 9. Another interesting addition in Chapter 9 is a comprehensive review of applications of wavelets to geophysical problems, in particular to the oilfield industry. In Chapter 10, the section on differential equations has been expanded by including the multiresolution time domain method.

Some of the new material in the second edition is derived from our col­laboration with students and colleagues at Texas A&M university, College Station; Indian Institute of Technology, Kharagpur; Georgia Institute of Technology, Atlanta; and Schlumberger. To them and to many readers who drew our attention to errors and misprints, we wish to express our gratitude. We also thank George Telecki, Kristen Parrish, and Lucy Hitz of John Wiley & Sons for their assistance during the preparation of the second edition.

July 2010

JAIDEVA C. GOSWAMI AND ANDREW K. CHAN

Preface to the First Edition

This textbook on wavelets evolves from teaching undergraduate and postgraduate courses in the Department of Electrical Engineering at Texas A&M University and teaching several short courses at Texas A&M University as well as in conferences such as the Progress in Electromagnetic Research Symposium (PIERS), the IEEE Antenna and Propagation (IEEE-AP) Symposium, the IEEE Microwave Theory and Technique (IEEE-MTT) Conference, and the Association for Computational Electromagnetic Society (ACES). The participants at the short courses came from industries as well as universities and had backgrounds mainly in electrical engineering, physics, and mathematics with little or no prior understanding of wavelets. In preparing material for the lectures, we referred to many books on this subject; some catering to the need of mathematicians and physicists, while others were written for engineers with a signal-processing background. We felt the need for a textbook that would combine the theory, algorithm, and applications of wavelets and present them in such a way that readers can easily learn the subject and be able to apply them to practical problems. That being the motivation, we have tried to keep a balance between the mathematical rigor and practical applications of wavelet theory. Many mathematical concepts are elucidated through the figures.

The book is organized as follows. Chapter 1 gives an overview of the book. The rest of the book is divided into four parts. In Chapters 2 and 3 we review some basic concepts of linear algebra, Fourier analysis, and discrete signal analysis. Chapters 4–6 are devoted to discussing theoretical aspects of time-frequency analysis, multiresolution analysis, and the construction of various types of wavelets; Chapters 7 and 8 give several algorithms for computing wavelet transform and implement them through a filter bank approach. Part of Chapter 8 and Chapters 9 and 10 present many interesting application of wavelets to signal-processing and boundary value problems.

In preparing this book we have benefited from a number of individuals. We learned a lot on wavelets from our association with Professor Charles Chui. To him we are very grateful. We would like to thank Professors Raj Mittra, Linda Katehi, and Hao Ling for inviting us to speak at the short courses in the IEEE AP and MTT conferences. Thanks are also due to Profession L. Tsang for inviting us to organize the short course at PIERS. Parts of Chapters 9 and 10 come from our collaboration with graduate students at Texas A&M University, notable among them are Minsen Wang, Howard Choe, Nai-wen Lin, Tsai-fa Yu, and Zhiwha Xu. We thank all of them for their contribution. We wish to express our deep sense of appreciation to Michelle Rubin who typed and proofread most of this book. We thank Profession Kai Chang and Mr. George J. Telecki for giving us the opportunity to write this book. Last but not the least, we thank Mousumi Goswami and Sophia Chan for their encouragement and support during the preparation of this book.

October 1998

JAIDEVA C. GOSWAMI AND ANDREW K. CHAN

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.