COMPLEX WAVELET TRANSFORMS
COMPLEX WAVELET TRANSFORMSANDTHEIR APPLICATIONSByPanchamkumar D SHUKLAForMaster of Philosophy (M.Phil.)2003Signal Processing DivisionDepartment of Electronic and Electrical EngineeringUniversity of StrathclydeGlasgow G1 1XWScotlandUnited Kingdom
COMPLEX WAVELET TRANSFORMSANDTHEIR APPLICATIONSA DISSERTATIONSUBMITTED TO THE SIGNAL PROCESSING DIVISION,DEPARTMENT OF ELECTRONIC AND ELECTRICAL ENGINEERINGAND THE COMMITTEE FOR POSTGRADUATE STUDIESOF THE UNIVERSITY OF STRATHCLYDEIN PARTIAL FULFILMENT OF THE REQUIREMENTSFOR THE DEGREE OFMASTER OF PHILOSOPHYByPanchamkumar D SHUKLAOctober 2003ii
The copyright of this thesis belongs to the author under the terms of the UnitedKingdom Copyright Act as qualified by University of Strathclyde Regulation 3.49.Due acknowledgement must always be made of the use of any material contained in,or derived from, this thesis. Copyright 2003iii
Dedicated tomy parentsRajeshwari and Dilipand to my wifeKrupaiv
DeclarationI declare that this Thesis embodies my own research work and that is composed bymyself. Where appropriate, I have made acknowledgements to the work of others.Panchamkumar D SHUKLAv
AcknowledgementsFirst of all, I am very much thankful to my supervisor, Prof. John Soraghan, for hisexcellent guidance, support and patience to listen. His always-cheerful conversations,a friendly behaviour, and his unique way to make his students realise their nowledgehisconstantencouragements and his genuine efforts to explore possible funding routes for thecontinuation of my research studies. I am also thankful to him for giving me anopportunity to work as a Teaching Assistant for MSc courses.My sincere acknowledgements to Dr. Kingsbury (Cambridge University),Prof. Selesnick (Polytechnic University, NY, USA) and Dr. Fernandes (RiceUniversity, USA) for their useful suggestions on complex wavelets transforms, andanswering my queries. I also acknowledge Dr. P. Wolfe (Cambridge University) forgiving useful information about applying wavelets in audio signals processing. Iextend my thanks to my senior research colleague Mr. Akbar for his encouragementand tips regarding statistical validation of my results.I will always remember my friends Chirag, Ratnakar, Satya, (Flatmates), andNandu, Santi, Stefan, Fadzli etc. (from Signal Processing Group) that I have madeduring my stay in Glasgow, and with whom I have cherished some joyous momentsand refreshing exchanges.I wish to extend my utmost thanks to my relatives in India, especially myparents, and parents’ in-law for their love and continuous support. Finally, my thesiswould have never been in this shape without lovely efforts from my wife Krupa. Herinvaluable companionship, warmth, strong faith in my capabilities and me hasalways helped me to be assertive in difficult times. Her optimistic and enlighteningboosts have made this involved research task a pleasant journey.vi
AbstractStandard DWT (Discrete Wavelet Transform), being non-redundant, is a verypowerful tool for many non-stationary Signal Processing applications, but it suffersfrom three major limitations; 1) shift sensitivity, 2) poor directionality, and 3)absence of phase information. To reduce these limitations, many researchersdeveloped real-valued extensions to the standard DWT such as WP (Wavelet PacketTransform), and SWT (Stationary Wavelet Transform). These extensions are highlyredundant and computationally intensive. Complex Wavelet Transform (CWT) isalso an alternate, complex-valued extension to the standard DWT. The initialmotivation behind the development of CWT was to avail explicitly both magnitudeand phase information. This thesis presents a detailed review of Wavelet Transforms(WT) including standard DWT and its extensions. Important forms of CWTs; theirtheory, properties, implementation, and potential applications are investigated in thisthesis.Recent developments in CWTs are classified into two important classes firstis, Redundant CWT (RCWT), and second is Non-Redundant CWT (NRCWT). Theimportant forms of RCWT include Kingsbury’s and Selesnick’s Dual-Tree DWT(DT-DWT), whereas the important forms of NRCWT include Fernandes’s andSpaendonck’s Projection based CWT (PCWT), and Orthogonal Hilbert transformfilterbank based CWT (OHCWT) respectively. All recent forms of CWTs try toreduce two or more limitations of standard DWT with limited (or controllable)redundancy, or without any redundancy. Potential applications such as Motionestimation, Image fusion/registration, Denoising, Edge detection, and Textureanalysis are suggested for further investigation with RCWT. Directional and phasebased Compression is suggested for investigation with NRCWT.Denoising and Edge detection applications are investigated with DT-DWTs.Promising results are compared with other DWT extensions, and with the classicalapproaches. After thorough investigations, it is proposed that by employing DTDWT for Motion estimation and NRCWT for Compression might significantlyimprove the performance of the next generation video codecs.vii
Acronyms1-DOne Dimensional2-DTwo DimensionalFTFourier TransformDFTDiscrete Fourier TransformFFTFast Fourier TransformWTWavelet TransformDWTDiscrete Wavelet TransformMRAMulti-Resolution AnalysisPRPerfect ReconstructionWPWavelet Packet TransformSWTStationary Wavelet TransformTFRTime Frequency RepresentationSTFTShort Time Fourier TransformAWTAnalog (Continuous) Wavelet TransformCoWTContinuous (Analog) Wavelet TransformCWTComplex Wavelet TransformFIRFinite Impulse ResponseGUIGraphical User InterfaceSDWSymmetric Daubechies WaveletsRCWTRedundant Complex Wavelet TransformNRCWTNon Redundant Complex Wavelet TransformDT-DWTDual Tree Discrete Wavelet TransformDT-DWT(K)Kingsbury’s Dual Tree Discrete Wavelet TransformDT-DWT(S)Selesnick’s Dual Tree Discrete Wavelet TransformDDWTDouble Density Discrete Wavelet TransformDDTWTDouble Density Discrete Wavelet TransformCDDWTComplex Double Density Wavelet TransformPCWTProjection based Complex Wavelet Transformviii
ontrollable RedundancyPCWT-NRProjection based Complex wavelet Transform with NoRedundancyOHCWTOrthogonal Hilbert Transform Filterbank based ComplexWavelet TransformMSEMean Square ErrorRMSERoot Mean Square ErrorSNRSignal to Noise RatioPSNRPeak Signal to Noise RatioSUREStein’s Unbiased Risk EstimatorMRIMagnetic Resonance ImagingSARSynthetic Aperture RadarHMMHidden Markov ModelSTSAShort Time Spectrum AttenuationSTWAShort Time Wavelet AttenuationMZ-MEDMallat and Zong’s Multiscale Edge DetectionECGElectrocardiogramFMEDFuzzy Multiscale Edge DetectionFWOMEDFuzzy Weighted Offset Multiscale Edge DetectionDBFMEDDual Basis Fuzzy Multiscale Edge DetectionCMEDComplex Multiscale Edge DetectionIMEDImaginary Multiscale Edge DetectionFCMEDFuzzy Complex Multiscale Edge DetectionSFCMEDSpatial Fuzzy Complex Multiscale Edge DetectionNFCMEDNon-decimated Fuzzy Complex Multiscale Edge DetectionCBIRContent Based Image RetrievalMSDMean Square DistanceFOMFigure of Meritix
Table of ronymsviiiTable of ContentsxList of FiguresxivList of Tablexviii1. Introduction11.1 Introduction 11.2Motivation and Scope of Research 21.3Organisation of Thesis . 32. Wavelet Transforms (WT)52.1 Introduction 52.22.32.1.1Wavelet Definition . 52.1.2Wavelet Characteristics . 62.1.3Wavelet Analysis 62.1.4Wavelet History . 62.1.5Wavelet Terminology . 7Evolution of Wavelet Transform . 82.2.1Fourier Transform (FT) . 82.2.2Short Time Fourier Transform (STFT) . 82.2.3Wavelet Transform (WT) . 102.2.4Comparative Visualisation . 11Theoretical Aspects of Wavelet Transform . 152.3.1Continuous Wavelet Transform (CoWT) 152.3.2Discrete Wavelet Transform (DWT) . 16x
2.42.5Implementation of DWT 182.4.1Multiresolution Analysis (MRA) 182.4.2Filterbank Implementation . 202.4.3Perfect Reconstruction (PR) 22Extensions of DWT 242.5.1Two Dimensional DWT (2-D DWT) . 252.5.2Wavelet Packet Transform (WP) 292.5.3Stationary Wavelet Transform (SWT) 322.6Applications of Wavelet Transforms 332.7Limitations of Wavelet Transforms . 332.8Summary . 363. Complex Wavelet Transforms (CWT)383.1 Introduction 383.2Earlier Work . 393.3Recent Developments . 403.4Analytic Filter .433.5Redundant Complex Wavelet Transforms (RCWT) . 453.63.5.1Introduction . 453.5.2Filterbank Structure of Dual-Tree DWT based CWT . 463.5.3Kingsbury’s Dual-Tree DWT (DT-DWT(K)) 493.5.4Selesnick’s Dual-Tree DWT (DT-DWT(S)) . 563.5.5Properties of DT-DWT 58Non-Redundant Complex wavelet Transforms (NRCWT) 613.6.1Introduction . 613.6.2Projection based CWT (PCWT) . 623.6.2.1Generic Structure 623.6.2.2Theory of Complex Projection .633.6.2.3Realisation of Complex Projection 643.6.2.4Non-redundant Complex Projection . 673.6.3PCWT with Controllable Redundancy (PCWT-CR) . 693.6.4PCWT with No-Redundancy (PCWT-NR) 70xi
3.6.5Orthogonal Hilbert TransformFilterbank based CWT (OHCWT) 723.7Advantages and Applications of CWT .743.8Summary . 764. Application I – Denoising804.1 Introduction 804.2Wavelet Shrinkage Denoising 814.2.1Basic Concept . 814.2.2Shrinkage Strategies 824.3 1-D Denoising . 834.3.1 Signal and Noise Model . 834.44.3.2Shrinkage Strategy . 844.3.3Algorithm 844.3.4Performance Measure . 854.3.5Results and Discussion 85Audio Signal Denoising .924.4.1WT for Audio Signals . 924.4.2Denoising Model . 924.4.3Shrinkage Strategies 934.4.4Performance Measure .944.4.5Results and Discussion 944.5 2-D Denoising . 984.64.5.1Image and Noise Model . 984.5.2Shrinkage Strategy . 984.5.3Algorithm 984.5.4Performance Measure . 994.5.5Results and Discussion 99Conclusion . 1175. Application II - Edge Detection1185.1 Introduction 118xii
5.25.35.45.5Edge Detection Approaches . 1195.2.1Classical Approaches . 1195.2.2Multiscale Approaches 1201-D Edge Detection 1215.3.1Review of Existing Approaches .1215.3.2Edge Model . 1225.3.3Multiscale Decomposition . 1225.3.4FMED (Fuzzy Multiscale Edge Detection) Algorithms . 1235.3.5CMED (Complex Multiscale Edge Detection) Algorithms 1265.3.6Performance Measure . 1275.3.7Results and Discussion . 1282-D Edge Detection 1375.4.1Basic Approach . 1375.4.2Algorithms . 1385.4.2.1WT based Algorithm .1385.4.2.2CWT based Algorithm . 1385.4.3Performance Measure . 1395.4.4Results and Discussion . 140Conclusion . 1426. Conclusions and Future Scope1436.1Conclusions . 1436.2Future Scope . 146Appendix A148Appendix B150Appendix C152References153xiii
List of FiguresFigure 2.1Representation of a wave (a), and a wavelet (b) .Figure 2.2(a) Uniform division of frequency with constant bandwidth in5STFT, (b) logarithmic division of frequency with constant-Q inWT Figure 2.310Comparative visualisation of time-frequency representation of anarbitrary non-stationary signal in various transform domains .12Figure 2.4Two signals x1(t) and x2(t) and their FFTs .13Figure 2.5Spectrograms and scalograms of signals x1(t) and x2(t) .14Figure 2.6Standard DWT on dyadic time-scale grid 17Figure 2.7Nested vector spaces spanned by scaling and wavelet basis 18Figure 2.8Two-channel, three-level analysis filterbank with 1-D DWT .21Figure 2.9Two-channel, three-level synthesis filterbank with 1-D DWT 21Figure 2.10A simple 2-channel filterbank model .22Figure 2.11Single level analysis filterbank for 2-D DWT .25Figure 2.12Multilevel decomposition hierarchy of an image with 2-D DWT.26Figure 2.13Frequency plane partitioning with 2-D DWT .27Figure 2.14(a) Test image ‘Pattern’, (b) single level 2-D DWT decompositionof the same .Figure 2.1528Wavelet packet transform:(a) binary-tree decomposition, (b) timefrequency tiling of basis .30Figure 2.16Vector subspaces for WP .31Figure 2.17Uniform frequency division for WP .31Figure 2.18Flexible representation with WP: either with boxes or with circles31Figure 2.19Three level decomposition with SWT .32Figure 2.20Shift-sensitivity of standard 1-D DWT 34Figure 2.21Directionality of standard 2D DWT .35Figure 2.22Presentation of (a) real, and (b) analytic wavelets .36Figure 3.1Hilbert Transform in (a) polar form, (b) frequency domain 43Figure 3.2Spectral representation of (a) original signal f(t), (b) analytic signalxiv
x(t) .44Figure 3.3Interpretation of an analytic filter by 2-real filters .45Figure 3.4(a) Analysis filterbank for 1-D DT-DWT, (b) synthesis filterbankfor 1-D DT-DWT 47Figure 3.5Filterbank structure for 2-D DT-DWT .48Figure 3.6Filterbank structure of tree-a of figure 3.5 .49Figure 3.7Analysis tree using odd-even filters .50Figure 3.8Analysis tree using Q-shift filters .50Figure 3.9Modelling of DT-DWT(K) filter structure for deriving the shiftinvariance constraints .51Figure 3.10Shift-invariance property of 1-D DT-DWT .59Figure 3.11Directionality of 2-D DT-DWT .59Figure 3.123-D representation of 12 wavelets of DT-DWT .60Figure 3.13A complex wavelet as a quadrature combination of real andimaginary wavelets for 1-D DT-DWT .61Figure 3.14Generic implementation of PCWT .63Figure 3.15Realisable complex projection in softy-space .65Figure 3.16 H (ω) , the magnitude response of complex projection filter h .66Figure 3.17Relation between function spaces 66Figure 3.18Figure 3.19Non-redundant complex projection . 67 The relationship between non-redundant mapping H and Softyspace mapping h . 68Figure 3.20Implementation of realisable PCWT: PCWT-CR 69Figure 3.21Realisation of non-redundant mapping 70Figure 3.223-band filterbank structure for 1-D OHCWT .72Figure 3.23Single level analysis filterbank equivalence of 1-D OHCWT forreal signal as shown in figure (3.22) 73Figure 3.24Three possible ways of implementing CWT for natural signals .79Figure 4.1Thresholding functions; (a) linear, (b) hard, (c) soft 82Figure 4.2(a) Denoising of signal ‘blocks’ with standard DWT, WP andSWT, (b) Denoising of signal ‘blocks’ with redundant CWT, DT- 90DWT(S) and DT-DWT(K) .91xv
Figure 4.3Block diagram of STWA (short time wavelet attenuation) method. 92Figure 4.4Spectrograms of audio signals with standard DWT baseddenoising 96Figure 4.5Spectrograms of audio signals with DT-DWT(K) based denoising. 97Figure 4.6Conventional filtering methods for denoising of ‘Lenna’ imagewith reference to tables (4.7) and (4.8) . 107Figure 4.7Wavelet Transform based methods for denoising of ‘Lenna’ imagewith reference to tables (4.7) to (4.9) Figure 4.8108Threshold vs MSE for determination of optimum threshold valuefor all wavelet based methods. Image for denoising is ‘Lenna’ withreference to table (4.9) . 109Figure 4.9Conventional filtering methods for denoising of ‘Lenna’ imagewith reference to tables (4.10) and (4.11) . 110Figure 4.10Wavelet Transform based methods for denoising of ‘Lenna’ imagewith reference to tables (4.10) to (4.12) Figure 4.11111Threshold Vs MSE for determination of optimum threshold valuefor all wavelet based methods. Image for denoising is ‘Lenna’ withreference to table (4.12) . 112Figure 4.12DWT based denoising of ‘Lenna’ image using hard and softthresholding with reference to tables (4.10) to (4.12) .Figure 4.13SWT based denoising of ‘Lenna’ image using hard and softthresholding with reference to tables (4.10) to (4.12) .Figure 4.14114DT-DWT(K) based denoising of ‘Lenna’ image using hard andsoft thresholding with reference to tables (4.10) to (4.12) Figure 4.15113115DT-DWT(S) based denoising of ‘Lenna’ image using hard andsoft thresholding with reference to tables (4.10) to (4.12) 116Figure 5.1Generalised step edge model .122Figure 5.2Cubic spline smoothing function φ(t) and its derivative ψ(t) d/dt(φ(t)) 123Figure 5.31-D edge detection with FMED (‘cubic’) with σ 0.6 and 5 .133Figure 5.4J level wavelet coefficients (left) and their only positive parts(right) with FMED(‘cubic’) under the noise of σ 0.6 and slope ofxvi
5 Figure 5.5133J level fuzzy subsets (left) and their corresponding 2 to J levelfuzzy intersection (right) for the computation of minimum fuzzyset (right top) employing FMED (‘cubic’) under the noise of σ 0.6 and slope of 5 134Figure 5.61-D edge detection with CMED: σ 0.6 and 5 . 134Figure 5.7J level of decimated real and imaginary coefficients with CMED:σ 0.6 and 5 . 135Figure 5.8J level of decimated original and modified (inverted and left cyclicshift of 1 sample for levels 2 to J ) real coefficients with CMED:σ 0.6 and 5 . 135Figure 5.9J level of interpolated modified real and original imaginarycoefficients with CMED: σ 0.6 and 5 Figure 5.10136J level of complex magnitude coefficients (left) and fuzzy subsetsof complex magnitudes (right). Top left shows detected edge withcomplex magnitude (at level 5) and top right shows detected edgewith fuzzy subset (at level 5) employing CMED: σ 0.6 and 5. 136Figure 5.112-D edge detection with conventional edge operators .140Figure 5.122-D edge detection with wavelet based methods .141xvii
List of TablesTable 3.1Classification of complex wavelet transforms .42Table 3.2Comparative summary of complex wavelet transforms . 78Table 4.1Effect of thresholding criteria for 1-D denoising .Table 4.2Effect of different SNRi and MSEi for 1-D denoising . 88Table 4.3Effect of low SNRi for 1-D denoising .Table 4.4Effect of long-tap filters for 1-D denoising . 89Table 4.5Effect of more number of decomposition levels for 1-D denoising. 89Table 4.6The MSE and SNR of denoised audio signal .Table 4.7MSE for various denoising methods (σ 10) . 101Table 4.8PSNR for various denoising methods (σ 10) . 102Table 4.9Optimum threshold value for various denoising methods (σ 10).103Table 4.10MSE for various denoising methods (σ 40) . 104Table 4.11PSNR for various denoising methods (σ 40) .105Table 4.12Optimum threshold value for various denoisin
FT Fourier Transform DFT Discrete Fourier Transform FFT Fast Fourier Transform WT Wavelet Transform . CDDWT Complex Double Density Wavelet Transform PCWT Projection based Complex Wavelet Transform viii. . Appendix B 150 Appendix C 152 References 153 xiii.
wavelet transform combines both low pass and high pass fil-tering in spectral decomposition of signals. 1.2 Wavelet Packet and Wavelet Packet Tree Ideas of wavelet packet is the same as wavelet, the only differ-ence is that wavelet packet offers a more complex and flexible analysis because in wavelet packet analysis the details as well
aspects of wavelet analysis, for example, wavelet decomposition, discrete and continuous wavelet transforms, denoising, and compression, for a given signal. A case study exam-ines some interesting properties developed by performing wavelet analysis in greater de-tail. We present a demonstration of the application of wavelets and wavelet transforms
Wavelet analysis can be performed in several ways, a continuous wavelet transform, a dis-cretized continuous wavelet transform and a true discrete wavelet transform. The application of wavelet analysis becomes more widely spread as the analysis technique becomes more generally known.
The wavelet analysis procedure is to adopt a wavelet prototype function, called an analyzing wavelet or mother wavelet. Temporal analysis is performed with a contracted, high-frequency version of the prototype wavelet, while frequency analysis is performed with a dilated, low-frequency version of the same wavelet.
Workshop 118 on Wavelet Application in Transportation Engineering, Sunday, January 09, 2005 Fengxiang Qiao, Ph.D. Texas Southern University S A1 D 1 A2 D2 A3 D3 Introduction to Wavelet A Tutorial. TABLE OF CONTENT Overview Historical Development Time vs Frequency Domain Analysis Fourier Analysis Fourier vs Wavelet Transforms Wavelet Analysis .
computes the approximation coefficients vector cA and detail coefficients vector cD, obtained by a wavelet decomposition of the vector X. The string 'wname' contains the wavelet name. [cA,cD] dwt(X,Lo_D,Hi_D) computes the wavelet decomposition as above, given these filters as input: Lo_D is the decomposition low-pass filter.
3. Wavelet analysis This section describes the method of wavelet analy-sis, includes a discussion of different wavelet func-tions, and gives details for the analysis of the wavelet power spectrum. Results in this section are adapted to discrete notation from the continuous formulas given in Daubechies (1990). Practical details in applying
The book has evolved as the textbook for a course taught to a mostly undergraduate audience over a number of years in the Department of Linguistics at UCLA. The course meets in lecture for four hours per week, with a one hour problem-solving session, during a ten-week term. The ideal audience for this book is a student who has studied some linguistics before (and thus has some idea of what .