Introduction To Wavelet
Workshop 118 on Wavelet Application in Transportation Engineering,Sunday, January 09, 2005Introduction to Wavelet A TutorialSSDA11D2A2A3D3Fengxiang Qiao, Ph.D.Texas Southern University
TABLE OF CONTENTOverviewHistorical DevelopmentTime vs Frequency Domain AnalysisFourier AnalysisFourier vs Wavelet TransformsWavelet AnalysisTools and SoftwareTypical ApplicationsSummaryReferences
OVERVIEWWavelet A small waveWavelet Transforms Convert a signal into a series of wavelets Provide a way for analyzing waveforms, bounded in bothfrequency and duration Allow signals to be stored more efficiently than by Fouriertransform Be able to better approximate real-world signals Well-suited for approximating data with sharp discontinuities“The Forest & the Trees” Notice gross features with a large "window“ Notice small features with a small "window”
DEVELOPMENT IN HISTORYPre-1930 Joseph Fourier (1807) with his theories of frequencyanalysisThe 1930s Using scale-varying basis functions; computing the energyof a function1960-1980 Guido Weiss and Ronald R. Coifman; Grossman and MorletPost-1980 Stephane Mallat; Y. Meyer; Ingrid Daubechies; waveletapplications today
PRE-1930Fourier Synthesis Main branch leading to wavelets By Joseph Fourier (born in France,1768-1830) with frequency analysistheories (1807)From the Notion of FrequencyAnalysis to Scale Analysis Analyzing f(x) by creatingmathematical structures that vary inscaleFor any 2π periodical function f ( x ) :f ( x ) a0 The first mention of wavelets appearedin an appendix to the thesis of A. Haar(1909) With compact support, vanishesoutside of a finite interval Not continuously differentiablek 1(ak cos kx bk sin kx )1 2πf ( x )dx2π 01 2πak f ( x ) cos(kx )dxa0 Construct a function, shift it by someπamount, change its scale, apply thatstructure in approximating a signal1Repeat the procedure. Take that basic bk πstructure, shift it, and scale it again.Apply it to the same signal to get a newapproximationHaar Wavelet 02π0f ( x )sin (kx )dx
THE 1930sFinding by the 1930s Physicist Paul Levy Haar basis function is superior to the Fourierbasis functions for studying small complicateddetails in the Brownian motionEnergy of a Function by Littlewood, Paley,and Stein Different results were produced if the energywas concentrated around a few points ordistributed over a larger interval1Energy 22π02f ( x ) dx
1960-1980Created a Simplest Elements of a Function Space,Called Atoms By the mathematicians Guido Weiss and Ronald R.Coifman With the goal of finding the atoms for a common functionUsing Wavelets for Numerical Image Processing David Marr developed an effective algorithm using afunction varying in scale in the early 1980sDefined Wavelets in the Context of QuantumPhysics By Grossman and Morlet in 1980
POST-1980An Additional Jump-start By Mallat In 1985, Stephane Mallat discovered somerelationships between quadrature mirror filters,pyramid algorithms, and orthonormal waveletbasesY. Meyer’s First Non-trivial Wavelets Be continuously differentiable Do not have compact supportIngrid Daubechies’ Orthonormal BasisFunctions Based on Mallat's work Perhaps the most elegant, and the cornerstone ofwavelet applications today
MATHEMATICALTRANSFORMATIONWhy To obtain a further information from the signalthat is not readily available in the raw signal.Raw Signal Normally the time-domain signalProcessed Signal A signal that has been "transformed" by any of theavailable mathematical transformationsFourier Transformation The most popular transformation
TIME-DOMAIN SIGNAL110.50.5Magnitude2 HzMagnitudeThe Independent Variable is TimeThe Dependent Variable is the AmplitudeMost of the Information is Hidden in the FrequencyContent0-0.5-100.5010 Hz-0.5-110140.520-0.5-100.5Time1TimeMagnitude20 HzMagnitudeTime0.512 Hz 10 Hz 20Hz0-2-400.5Time1
FREQUENCY TRANSFORMSWhy Frequency Information is Needed Be able to see any information that is notobvious in time-domainTypes of Frequency Transformation Fourier Transform, Hilbert Transform, Shorttime Fourier Transform, WignerDistributions, the Radon Transform, theWavelet Transform
FREQUENCY ANALYSISFrequency Spectrum Be basically the frequency components (spectralcomponents) of that signal Show what frequencies exists in the signalFourier Transform (FT) One way to find the frequency content Tells how much of each frequency exists in a signalX (k 1 ) 1x (n 1) NwN eN 1n 0N 1k 02π jNx (n 1 ) WX (k 1) WknN knN X(f ) x(t ) x(t ) e 2 jπft dt X ( f ) e 2 jπft df
STATIONARITY OF SIGNAL (1)Stationary Signal Signals with frequency content unchangedin time All frequency components exist at all timesNon-stationary Signal Frequency changes in time One example: the “Chirp Signal”
STATIONARITY OF SIGNAL (2)36 0 025 0 0MagnitudeStationaryMagnitude2 Hz 10 Hz 20Hz104 0 03 0 0-12 0 0-21 0 0-300 .20 .4Time0 .60 .801Occur at all times051 01 52 02 5Frequency (Hz)Do not appear at all times2 5 00 .80 .6MagnitudeNonStationary1Magnitude0.0-0.4: 2 Hz 0.4-0.7: 10 Hz 0.7-1.0: 20Hz0 .40 .20-0 .22 0 01 5 01 0 0-0 .4-0 .65 0-0 .8-100 .5Time10051 01 5Frequency (Hz)2 02 5
CHIRP SIGNALSFrequency: 2 Hz to 20 HzFrequency: 20 Hz to 2 HzDifferent in Time 4MagnitudeMagnitude100.5Time1005101520Frequency (Hz)25-100.5Time1005101520Frequency (Hz)Same in Frequency mponentscomponentsoccur?occur? FTFTcancannotnottell!tell!At25
NOTHING MORE, NOTHING LESSFT Only Gives what Frequency ComponentsExist in the SignalThe Time and Frequency Information cannot be Seen at the Same TimeTime-frequency Representation of theSignal is NeededMost of Transportation Signals are Non-stationary.(We need to know whether and also when an incident was happened.)ONE EARLIER SOLUTION: SHORT-TIME FOURIER TRANSFORM (STFT)
SFORT TIME FOURIERTRANSFORM (STFT)Dennis Gabor (1946) Used STFT To analyze only a small section of the signal at atime -- a technique called Windowing the Signal.The Segment of Signal is Assumed StationaryA 3D transform[x(t ) ω (t t′)] eSTFTX(ω ) (t ′, f ) *t j 2 πftdtω(t ) : the window functionA function of timeand frequency
DRAWBACKS OF STFTUnchanged WindowDilemma of Resolution Narrow window - poor frequency resolution Wide window - poor time resolutionHeisenberg Uncertainty Principle Cannot know what frequency exists at what time intervalsVia Narrow WindowThe two figures were from Robi Poliker, 1994Via Wide Window
MULTIRESOLUTION ANALYSIS(MRA)Wavelet Transform An alternative approach to the short time Fouriertransform to overcome the resolution problem Similar to STFT: signal is multiplied with a functionMultiresolution Analysis Analyze the signal at different frequencies with differentresolutions Good time resolution and poor frequency resolution at highfrequencies Good frequency resolution and poor time resolution at lowfrequencies More suitable for short duration of higher frequency; andlonger duration of lower frequency components
ADVANTAGES OF WT OVER STFTWidth of the Window is Changed asthe Transform is Computed forEvery Spectral ComponentsAltered Resolutions are Placed
PRINCIPLES OF WAELETTRANSFORMSplit Up the Signal into a Bunch of SignalsRepresenting the Same Signal, but allCorresponding to Different Frequency BandsOnly Providing What Frequency Bands Existsat What Time Intervals
DEFINITION OF CONTINUOUSWAVELET TRANSFORM1* t τx(t ) ψCWT (τ, s ) Ψ (τ, s ) dtssψxψxTranslationWavelet(The location ofthe window)ScaleMother Wavelet Small wave Means the window function is of finite lengthMother Wavelet A prototype for generating the other windowfunctions All the used windows are its dilated or compressedand shifted versions
SCALEScale S 1: dilate the signal S 1: compress the signalLow Frequency - High Scale - Nondetailed Global View of Signal - SpanEntire SignalHigh Frequency - Low Scale - DetailedView Last in Short TimeOnly Limited Interval of Scales is Necessary
COMPUTATION OF CWTCWT xψ (τ, s ) Ψ xψ (τ, s ) 1sx (t ) ψ *t τdtsStep 1: The wavelet is placed at the beginning of thesignal, and set s 1 (the most compressed wavelet);Step 2: The wavelet function at scale “1” ismultiplied by the signal, and integrated over alltimes; then multiplied by 1 s ;Step 3: Shift the wavelet to t τ , and get thetransform value at t τ and s 1;Step 4: Repeat the procedure until the waveletreaches the end of the signal;Step 5: Scale s is increased by a sufficiently smallvalue, the above procedure is repeated for all s;Step 6: Each computation for a given s fills thesingle row of the time-scale plane;Step 7: CWT is obtained if all s are calculated.
RESOLUTION OF TIME &FREQUENCYBetter terfrequencyresolution;Poor timeresolutionTime Each box represents a equal portion Resolution in STFT is selected once for entire analysis
COMPARSION OFTRANSFORMATIONSFrom http://www.cerm.unifi.it/EUcourse2001/Gunther lecturenotes.pdf, p.10
MATHEMATICAL EXPLAINATION1* t τCWT (τ, s ) Ψ (τ, s ) x(t ) ψdtssψxψx X (T ) ψ τ,s (t )dtψ τ,s (t ) 1t τψssCWT can be regarded as the inner productof the signal with a basis function ψ (t ) τ,s
DISCRETIZATION OF CWTIt is Necessary to Sample the TimeFrequency (scale) Plane.At High Scale s (Lower Frequency f ), theSampling Rate N can be Decreased.The Scale Parameter s is NormallyDiscretized on a Logarithmic Grid.The most Common Value is 2.N 2 s1 s2 N1 f1 f 2 N1SN2432 1688
EFFECTIVE & FAST DWTThe Discretized CWT is not a True DiscreteTransformDiscrete Wavelet Transform (DWT) Provides sufficient information both for analysisand synthesis Reduce the computation time sufficiently Easier to implement Analyze the signal at different frequency bandsSSwith different resolutions Decompose the signal into a coarseAapproximation and detail information1D2A2A3D3D1
SUBBABD CODING ALGORITHMHalves the Time Resolution Only half number of samples resultedDoubles the Frequency Resolution The spanned frequency band halved0-1000 HzX[n]512Filter 1256SSD2A2A3D3Filter 2A1D1A1256D1: 500-1000 Hz128D2: 250-500 Hz128D3: 125-250 HzFilter 364A264A3: 0-125 Hz
DECOMPOSING NONSTATIONARY SIGNALS (1)Signal:0.0-0.4: 20 Hz0.4-0.7: 10 Hz0.7-1.0: 2 HzWavelet: db4Level: 6
DECOMPOSING NONSTATIONARY SIGNALS (2)Signal:0.0-0.4: 2 Hz0.4-0.7: 10 Hz0.7-1.0: 20HzWavelet: db4Level: 6
RECONSTRUCTION (1)What How those components can be assembled back intothe original signal without loss of information? A Process After decomposition or analysis. Also called synthesisHow Reconstruct the signal from the waveletcoefficients Where wavelet analysis involves filtering anddownsampling, the wavelet reconstruction processconsists of upsampling and filtering
RECONSTRUCTION (2)Lengthening a signal component byinserting zeros between samples(upsampling)MATLAB Commands: idwt and waverec;idwt2 and waverec2.
WAVELET BASESTimedomainFrequencydomain-1ω η ηWavelet Basis Functions: Morlet (ω0 frequency) : π 4 e j 0 e222 m i m m!(1 iη) (m 1)Paul (m order ): DOGπ(2m )!DOG (m derivative ):Derivative Of a GaussianM 2 is the Marr or Mexican hat wavelet(- 1)m 1( )d m η2 2m eη1 dΓ m 2
WAVELET FAMILY PROPERTIESPropertymorl mexh meyr haar dbN symN coifNbiorNr.NdrbioNr.NdCrudeInfinitely regularArbitrary regularityCompactly supported orthogonalCompactly supported biothogonalSymmetryAsymmetryNear symmetryArbitrary number of vanishing momentsVanishing moments forExistence ofOrthogonal analysisBiorthogonal analysisExact reconstructionFIR filtersContinuous transformDiscrete transformFast algorithmExplicit expressionComplex valuedComplex continuous transformFIR-based approximationFor splines For splinesgaus dmey cgau cmor fbsp shan
WAVELET SOFTWAREA Lot of Toolboxes and Software havebeen DevelopedOne of the Most Popular Ones is theMATLAB Wavelet lp/toolbox/wavelet/wavelet.html
GUI VERSION IN MATLABGraphical UserInterfacesFrom theMATLAB prompt,type wavemenu,the WaveletToolbox MainMenu appears
OTHER SOFTWARE SOURCESWaveLib [http://www-sim.int-evry.fr/ bourges/WaveLib.html]EPIC [http://www.cis.upenn.edu/ eero/epic.html]Imager Wavelet ions/bobl/wvlt/download/]Mathematica wavelet programs [http://timna.Mines.EDU/wavelets/]Morletpackage [ftp://ftp.nosc.mil/pub/Shensa/]p-wavelets ts/]WaveLab [http://playfair.Stanford.EDU/ wavelab/]Rice Wavelet Tools [http://jazz.rice.edu/RWT/]Uvi Wave Software [http://www.tsc.uvigo.es/ wavelets/uvi wave.html]WAVBOX mpress hresh.html]WPLIB wplib/]W-Transform Matlab Toolbox [ftp://info.mcs.anl.gov/pub/W-transform/]XWPL xwpl/]
WAVELET APPLICATIONSTypical Application Fields Astronomy, acoustics, nuclear engineering, subband coding, signal and image processing,neurophysiology, music, magnetic resonanceimaging, speech discrimination, optics, fractals,turbulence, earthquake-prediction, radar, humanvision, and pure mathematics applicationsSample Applications Identifying pure frequencies De-noising signals Detecting discontinuities and breakdown points Detecting self-similarity Compressing images
DE-NOISING SIGNALSHighestFrequenciesAppear at the Startof The OriginalSignalApproximationsAppear Less andLess NoisyAlso LoseProgressively MoreHigh-frequencyInformation.In A5, About theFirst 20% of theSignal is Truncated
ANOTHER DE-NOISING
DETECTING DISCONTINUITIESAND BREAKDOWN POINTSThe DiscontinuousSignal Consists of aSlow Sine WaveAbruptly Followed bya Medium Sine Wave.The 1st and 2nd LevelDetails (D1 and D2)Show theDiscontinuity MostClearlyThings to beDetected The site of thechange The type of change(a rupture of thesignal, or an abruptchange in its firstor secondderivative) The amplitude ofthe changeDiscontinuityPoints
DETECTING SELF-SIMILARITYPurpose How analysis by waveletscan detect a self-similar,or fractal, signal. The signal here is theKoch curve -- a syntheticsignal that is builtrecursivelyAnalysis If a signal is similar toitself at different scales,then the "resemblanceindex" or waveletcoefficients also will besimilar at different scales. In the coefficients plot,which shows scale on thevertical axis, this selfsimilarity generates acharacteristic pattern.
COMPRESSING IMAGESFingerprints FBI maintains a large databaseof fingerprints — about 30million sets of them. The cost of storing all this dataruns to hundreds of millions ofdollars.Results Values under the threshold areforced to zero, achieving about42% zeros while retainingalmost all (99.96%) the energyof the original image. By turning to wavelets, the FBIhas achieved a 15:1compression ratio better than the more traditionalJPEG compression
IDENTIFYING PUREFREQUENCIESPurpose Resolving a signal into constituentsinusoids of different frequencies The signal is a sum of three puresine wavesAnalysis D1 contains signal componentswhose period is between 1 and 2. Zooming in on detail D1 revealsthat each "belly" is composed of 10oscillations. D3 and D4 contain the medium sinefrequencies. There is a breakdown betweenapproximations A3 and A4 - Themedium frequency been subtracted. Approximations A1 to A3 be used toestimate the medium sine. Zooming in on A1 reveals a periodof around 20.
SUMMARYHistorical Background IntroducedFrequency Domain Analysis Help to See any Information that isnot Obvious in Time-domainTraditional Fourier Transform (FT) cannot Tell where aFrequency Starts and EndsShort-Term Fourier Transform (STFT) Uses Unchanged Windows,cannot Solve the Resolution ProblemContinuous Wavelet Transform (CWT), Uses Wavelets as Windowswith Altered Frequency and Time ResolutionsDiscrete Wavelet Transform (DWT) is more Effective and FasterMany Wavelet Families have been Developed with DifferentPropertiesA lot of Software are available, which Enable more Developmentsand Applications of WaveletWavelet Transform can be used in many Fields includingMathematics, Science, Engineering, Astronomy, This Tutorial does not Cover all the Areas of WaveletThe theories and applications of wavelet is still in developing
REFERENCESMathworks, Inc. Matlab lp/toolbox/wavelet/wavelet.htmlRobi Polikar, The Wavelet Tutorial, http://users.rowan.edu/ polikar/WAVELETS/WTpart1.htmlRobi Polikar, Multiresolution Wavelet Analysis of Event Related Potentials for the Detection of Alzheimer'sDisease, Iowa State University, 06/06/1995Amara Graps, An Introduction to Wavelets, IEEE Computational Sciences and Engineering, Vol. 2, No 2,Summer 1995, pp 50-61.Resonance Publications, Inc. Wavelets. http://www.resonancepub.com/wavelets.htmR. Crandall, Projects in Scientific Computation, Springer-Verlag, New York, 1994, pp. 197-198, 211-212.Y. Meyer, Wavelets: Algorithms and Applications, Society for Industrial and Applied Mathematics,Philadelphia, 1993, pp. 13-31, 101-105.G. Kaiser, A Friendly Guide to Wavelets, Birkhauser, Boston, 1994, pp. 44-45.W. Press et al., Numerical Recipes in Fortran, Cambridge University Press, New York, 1992, pp. 498-499,584-602.M. Vetterli and C. Herley, "Wavelets and Filter Banks: Theory and Design," IEEE Transactions on SignalProcessing, Vol. 40, 1992, pp. 2207-2232.I. Daubechies, "Orthonormal Bases of Compactly Supported Wavelets," Comm. Pure Appl. Math., Vol 41,1988, pp. 906-966.V. Wickerhauser, Adapted Wavelet Analysis from Theory to Software, AK Peters, Boston, 1994, pp. 213-214,237, 273-274, 387.M.A. Cody, "The Wavelet Packet Transform," Dr. Dobb's Journal, Vol 19, Apr. 1994, pp. 44-46, 50-54.J. Bradley, C. Brislawn, and T. Hopper, "The FBI Wavelet/Scalar Quantization Standard for Gray-scaleFingerprint Image Compression," Tech. Report LA-UR-93-1659, Los Alamos Nat'l Lab, Los Alamos, N.M.1993.D. Donoho, "Nonlinear Wavelet Methods for Recovery of Signals, Densities, and Spectra from Indirect andNoisy Data," Different Perspectives on Wavelets, Proceeding of Symposia in Applied Mathematics, Vol 47, I.Daubechies ed. Amer. Math. Soc., Providence, R.I., 1993, pp. 173-205.B. Vidakovic and P. Muller, "Wavelets for Kids," 1994, unpublished. Part One, and Part Two.J. Scargle et al., "The Quasi-Periodic Oscillations and Very Low Frequency Noise of Scorpius X-1 asTransient Chaos: A Dripping Handrail?," Astrophysical Journal, Vol. 411, 1993, L91-L94.M.V. Wickerhauser, "Acoustic Signal Compression with Wave Packets," 1989. Available by TeXing this TeXPaper.
Questions ?
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 .
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
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.
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.
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
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
448 Ma et al.: Interpretation of Wavelet Analysis and its Application in Partial Discharge Detection R&b be (b) Figure 2. Examples of the shape of wavelets.a, db2 wavelet; b, db7 wavelet. signal can be disassembled into a series of scaled and time shifted forms of mother wavelet producing a time-scale
One application of wavelet analysis is the estimation of a sample wavelet spectr um and the subsequent comparison of the sample wavelet spectrum to a background noise spectr um . To mak e such comparison s, one must implement statistical tests. Torrence and Compo (1998) were the first to place wavelet analysis i n a statistical
Algae: (11L) 2. Algae: General characters, economic importance and Classification (Chapman and Chapman, 1973) up to classes. 03L . 3. Study of life cycle of algae with reference to taxonomic position, occurrence, thallus structure, and reproduction of Nostoc, Chara, Sargassum and Batrachospermum . 08 L.
