WAVELET BASICS W A VELET BASICS by Y. T. Chan Royal Military College of Canada SPRINGER SCIENCE+BUSINESS MEDIA, LLC ISBN 978-1-4613-5929-6 ISBN 978-1-4615-2213-3 (eBook) DOI 10.1007/978-1-4615-2213-3 Library of Congress Cataloging-in-Publication Data A c.I.P. Catalogue record for this book is available from the Library of Congress. Copyright © 1995 Springer Science+Business Media New York Originally published by Kluwer Academic Publishers in 1995 Softcover reprint ofthe hardcover Ist edition 1995 AU rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, mechanical, photo-copying, recording, or otherwise, without the prior written permission of the publisher, Springer Science+Business Media, LLC. Printed on acid-free paper. Contents Preface 1. Introduction 1 1.1 Signal Transformation 1 1.2 Orthogonal Transform 4 1.3 Frames in Vector Space 8 1.4 Time-Frequency Analysis 13 1.5 Applications of Time-Frequency Analysis 20 2. Principles of the Wavelet Transform 23 2.1 Introduction 23 2.2 The Continuous Wavelet Transform 32 2.3 Discrete Parameter Wavelet Transform 39 Appendix A - Resolution of the Identity 50 3. Multiresolution Analysis, Wavelets and Digital 53 Filters 3.1 Introduction 53 3.2 The DPWT and MRA 55 3.3 Principles of MRA 63 3.4 Filters for Perfect Reconstruction 74 3.5 Paraunitary Filters and Orthonormal Wavelets 83 3.6 Filter Design for Orthonormal Wavelets 89 3.7 Biorthogonal Filters 91 3.8 Wavelet Construction from Two-Scale Equations 94 3.9 Two Dimensional Wavelets 101 Appendix B - Theorem for Convergence of <1>( (J) ) 103 Appendix C - Solution of a Polynomial in cos( (J) 108 4. Current Topics 111 4.1 Wavelet Packets 111 4.2 Discrete Time Wavelet Transform 113 4.3 Signal Processing Applications 120 References 125 Index 131 Preface This book had its humble beginning one morning in April, 1993. I was then on my second sabbatical leave at the Chinese University of Hong Kong and having the time of my life. That morning, as I was leaving for the office as usual with my tennis racket and gym bag, May told me in a normal wifery manner that my court time lately had been fast approaching office time and that I should do something about the situation. My main excuse for the sabbatical was to learn about wavelets and I decided that morning the best way to learn is to write a book on it. It was quite a struggle. There were no introductory level texts for engineers and it was not easy to learn from the literature. Since it is a new subject, its terminology is non-standard, concepts and proofs are hard to follow and were at times confusing. I wrote this book for beginners, aiming to help readers avoid many of my own difficulties. The terminology is familiar to engineers. Whenever possible, I give examples to illustrate new concepts, answer questions that I encountered when studying the subject, and give intuitive insight. As it turned out, my six months at the Chinese University were rather fruitful. Dr. P. C. Ching, of the department of electronic engineering at CUHK, made the arrangement for the visit and deserves a sincere thank you. This book will not be possible without the extraordinary efforts of Dr. K. C. Ho, a research fellow here at the Royal Military College. He not only typed the entire manuscript, did all the figures, but also corrected my mistakes and suggested proofs. lowe him a great deal. As to May, who is responsible for my last one and half years of misery, I cannot accord her the customary gratitude of having been understanding, supportive and tolerant, etc. Y. T. CHAN Kingston, Ontario, Canada WAVELET BASICS Chapter 1 INTRODUCTION 1.1 Signal Transformation The transformation of a function or signal s (t) is a mathematical operation that results in a different representation of set). The well known Fourier transform gives the spectrum of a signal while a two dimensional transformation of an image may aim to concentrate the image energy into a smaller region for compression purposes. A prism acts as a Fourier transformer by decomposing sunlight into its visual spectrum of different colours (frequencies). Hence a transform also reveals the composition of a signal in terms of the building blocks, or basis functions, of the transformed domain. In the Fourier domain, the building blocks are sinusoids. A signal has a unique representation in the Fourier domain as a continuous sum of sinusoids of different amplitudes, frequencies and phases. On the other hand, the simple Walsh transform has basis functions that are variable width pulse sequences of amplitudes ±I, as shown in Figure 1.1, where it is assumed without loss of generality that set) is of duration from t =0 to t = 1. The Fourier transform pair is J~ S(w) = s(t)e-jOlI dt (1.1) I (- set) = 21t J_ Sew) ejOlI dw (1.2) The decomposition of s(t) is via (Ll), the Fourier transform. It decomposes set) into sinusoids of frequency w, amplitude IS(w)1 and phase LS(w). The inverse Fourier transform, (1.2), synthesizes set) from the basis functions of complex amplitude Sew). Another way to view (1.1) is that the ej.", weight Sew) is the "amount" of ejOlI that s(t) contains. Hence the cross-correlation of set) with e-jOlI yields Sew). A simple parallel of (Ll) is in the determination of the coefficients ex and /3 of the basis vectors e1 = [ 1 0] T, e2 = [ 0 I ] T needed to synthesize a particular vector v : 2 futroduction 1 IIIIII LIIIIII ~ 0 -1 -JIIIII IIIIII I I I I I III LII ~ IIIII IIIII ~ II II I I I II II Figure 1.1 Some typical Walsh functions (1.3) To find ex., take the inner product (cross-correlation) of v and e i.e. l, a=<v,el>=a (1.4) 1.1 Signal Transformation 3 and (1.5) Or, the projections of v onto e and e give a. and P respectively. Using 1 2 simple basis functions, e.g. Walsh, will greatly simplify the transformation, or inner product, calculations. However, computation load is usually only one of several factors in choosing a particular transform. Others are a transform's properties and its suitability for a given application. The reasons for transforming or decomposing a signal are numerous. The Laplace transform is a generalization of the Fourier transform and expresses a function x(t) as a weighted, continuous sum of the basis function est. Thus x(t)= f~ X(s)eSI ds (1.6) where the weight X(s) is the Laplace transform of x(t) and s is a complex quantity called the complex frequency. As easily seen from (1.6), the equivalent operations in the Laplace domain of differentiation or integration of x(t) in the time domain are multiplications of X( s) by s or 1/ s . Thus taking the Laplace transform of a linear integro-differential equation will change it into an algebraic equation. This important result is the foundation of linear system analysis by the Laplace transform. More recently, with the introduction of the Fast Fourier Transform (FFT), there is sometimes a speed gain in doing calculations in the frequency domain, for time domain operations such as convolution and correlation. Modem radar and sonar receivers invariably have an FFT front end and functions such as matched filtering and beam-forming are performed in the frequency domain. Signal transformations, by virtue of offering an alternate representation, often reveal key features of a signal that are difficult or impossible to discern in the original domain. The existence and locations of multiple periodicities, spectral and phase patterns, for example, are useful features in the frequency domain for detection and classification. Yet another important transform application is data compression. Let <I> be an N xN matrix whose elements are samples of an image. A transform operation gives (1.7)