Wavelet
From Wikipedia, the free encyclopedia
In mathematics, wavelets, wavelet analysis, and the wavelet transform refers to the representation of a signal in terms of scaled and translated copies (known as "'daughter wavelets'") of a finite length or fast decaying oscillating waveform (known as the mother wavelet). In formal terms, this representation is a wavelet series representation of a square integrable function with respect to either a complete, orthonormal set of basis functions, or an overcomplete set of frame functions (also known as a Riesz basis), for the Hilbert space of square integrable functions. Note that the wavelets in the JPEG2000 standard are biorthogonal, which means that although the frame is overcomplete, the frame is a tight frame, and the same frame functions (except for conjugation in the case of complex wavelets) are used for both analysis and synthesis, i.e., in both the forward and inverse transform.
Contents |
[edit] Overview
The word wavelet is due to Morlet and Grossmann in the early 1980s. They used the French word ondelette, meaning "small wave". A little later it was transformed into English by translating "onde" into "wave", giving wavelet. Wavelet transforms are broadly classified into the discrete wavelet transform (DWT) and the continuous wavelet transform (CWT). The principal difference between the two is the continuous transform operates over every possible scale and translation whereas the discrete uses a specific subset of all scale and translation values.
[edit] Using wavelet theory
Wavelet theory is extremely applicable to several other subjects. All wavelet transforms may be considered to be forms of time-frequency representation and are, therefore, related to the subject of harmonic analysis. Almost all practically useful discrete wavelet transforms make use of filterbanks containing finite impulse response filters. The wavelets forming a CWT are subject to Heisenberg's uncertainty principle and, equivalently, discrete wavelet bases may be considered in the context of other forms of the uncertainty principle.
[edit] Outline of the wavelet theory
Wavelet transforms are broadly divided into three classes, the continuous wavelet transform, the discretised wavelet transform and multiresolution-based wavelet transforms.
[edit] Continuous wavelet transforms
In the continuous wavelet transform, a given signal of finite energy is projected on a continuous family of frequency bands (or similar subspaces of the function space ), for instance on every frequency band of the form [f,2f] for all positive frequencies f>0. By a suitable integration over all the thus obtained frequency components one can reconstruct the original signal.
The frequency bands or subspaces are scaled versions of a subspace at scale 1. This subspace in turn is in most situations generated by the shifts of one generating function , the mother wavelet. For the example of the scale one frequency band [1,2] this function is
with the (normalized) sinc function. Other example mother wavelets are:
The subspace of scale a or frequency band is generated by the functions (sometimes called baby wavelets)
- ,
where a is positive and defines the scale and b is any real number and defines the shift. The pair (a,b) defines a point in the upper halfplane .
The projection of a function x onto the subspace of scale a has then the form
with wavelet coefficients
- .
For the analysis of the signal x, one can assemble the wavelet coefficients into a scaleogram of the signal.
[edit] Discretized wavelet transforms
It is computationally impossible to analyze a signal using all wavelet coefficients. So one may wonder if it is sufficient to pick a discrete subset of the upper halfplane to be able to reconstruct a signal from the corresponding wavelet coefficients. One such system is the affine system for some real parameters a>1, b>0. The corresponding discrete subset of the halfplane consists of all the points with integers . The corresponding baby wavelets are now given as
- ψm,n(t) = a − m / 2ψ(a − mt − nb).
A sufficient condition for the reconstruction of any signal x of finite energy by the formula
is that the functions form a tight frame of .
[edit] MRA based discrete wavelet transforms
In each instance of the discretised wavelet transform, there are only a finite number of wavelet coefficients for each bounded rectangular region in the upper halfplane. Still, each coefficient requires the evaluation of an integral. To avoid this numerical complexity one needs one auxiliary function, the father wavelet . Further, one has to restrict a to be an integer number. A typical choice is a=2 and b=1. The most famous pair of father and mother wavelets is the Daubechies 4 tap wavelet.
From the mother and father wavelets one constructs the subspaces
- , where φm,n(t) = 2 − m / 2φ(2 − mt − n)
and
- , where ψm,n(t) = 2 − m / 2ψ(2 − mt − n).
From these one requires that the sequence
forms a multiresolution analysis of and that the subspaces are the orthogonal "differences" of the above sequence, that is, Wm ist the orthogonal complement of Vm inside the subspace Vm − 1. In analogy to the sampling theorem one may conclude that the space Vm with sampling distance 2m more or less covers the frequency baseband from 0 to 2 − m − 1. As orthogonal complement, Wm roughly covers the band [2 − m − 1,2 − m].
From those inclusions and orthogonality relations follows the existence of sequences and that satisfy the identities
- and
and
- and .
The second identity of the first pair is a refinement equation for the father wavelet φ. Both pairs of identities form the basis for the algorithm of the fast wavelet transform.
[edit] Mother wavelet
For practical applications one prefers for efficiency reasons continuously differentiable functions with compact support as mother (prototype) wavelet (functions). However, to satisfy analytical requirements (in the continuous WT) and in general for theoretical reasons one chooses the wavelet functions from a subspace of the space . This is the space of measurable functions that are both absolutely and square integrable:
- and .
Being in this space ensures that one can formulate the conditions of zero mean and square norm one:
- is the condition for zero mean, and
- is the condition for square norm one.
For ψ to be a wavelet for the continuous wavelet transform (see there for exact statement), the mother wavelet must satisfy an admissibility criterion (loosely speaking, a kind of half-differentiability) in order to get a stably invertible transform.
For the discrete wavelet transform, one needs at least the condition that the wavelet series is a representation of the identity in the space . Most constructions of discrete WT make use of the multiresolution analysis, which defines the wavelet by a scaling function. This scaling function itself is solution to a functional equation.
In most situations it is useful to restrict ψ to be a continuous function with a higher number M of vanishing moments, i.e. for all integer m<M
Some example mother wavelets are:
The mother wavelet is scaled (or dilated) by a factor of a and translated (or shifted) by a factor of b to give (under Morlet's original formulation):
- .
For the continuous WT, the pair (a,b) varies over the full half-plane ; for the discrete WT this pair varies over a discrete subset of it, which is also called affine group.
These functions are often incorrectly referred to as the basis functions of the (continuous) transform. In fact, as in the continuous Fourier transform, there is no basis in the continuous wavelet transform. Time-frequency interpretation uses a subtly different formulation (after Delprat).
[edit] Comparisons with Fourier
The wavelet transform is often compared with the Fourier transform, in which signals are represented as a sum of sinusoids. The main difference is that wavelets are localized in both time and frequency whereas the standard Fourier transform is only localized in frequency. The Short-time Fourier transform (STFT) is also time and frequency localized but there are issues with the frequency time resolution and wavelets often give a better signal representation using Multiresolution analysis.
The discrete wavelet transform is also less computationally complex, taking O(N) time as compared to O(N log N) for the fast Fourier transform (N is the data size).
[edit] Definition of a wavelet
There are a number of ways of defining a wavelet (or a wavelet family).
[edit] Scaling filter
The wavelet is entirely defined by the scaling filter g - a low-pass finite impulse response (FIR) filter of length 2N and sum 1. In biorthogonal wavelets, separate decomposition and reconstruction filters are defined.
For analysis the high pass filter is calculated as the QMF of the low pass, and reconstruction filters the time reverse of the decomposition.
Daubechies and Symlet wavelets can be defined by the scaling filter.
[edit] Scaling function
Wavelets are defined by the wavelet function ψ(t) (i.e. the mother wavelet) and scaling function φ(t) (also called father wavelet) in the time domain.
The wavelet function is in effect a band-pass filter and scaling it for each level halves its bandwidth. This creates the problem that in order to cover the entire spectrum an infinite number of levels would be required. The scaling function filters the lowest level of the transform and ensures all the spectrum is covered. See [1] for a detailed explanation.
For a wavelet with compact support, φ(t) can be considered finite in length and is equivalent to the scaling filter g.
Meyer wavelets can be defined by scaling functions
[edit] Wavelet function
The wavelet only has a time domain representation as the wavelet function ψ(t).
Mexican hat wavelets can be defined by a wavelet function.
[edit] Applications
Generally, the DWT is used for data compression whereas the CWT is used for signal analysis. Consequently, the DWT is commonly used in engineering and computer science and the CWT is most often used in scientific research. Wavelet transforms are now being adopted for a vast number of different applications, often replacing the conventional Fourier transform. Many areas of physics have seen this paradigm shift, including molecular dynamics, ab initio calculations, astrophysics, density-matrix localisation, seismic geophysics, optics, turbulence and quantum mechanics. Other areas seeing this change have been image processing, blood-pressure, heart-rate and ECG analyses, DNA analysis, protein analysis, climatology, general signal processing, speech recognition, computer graphics and multifractal analysis. In computer vision and image processing, the notion of scale-space representation and Gaussian derivative operators is regarded as a canonical multi-scale representation.
One use of wavelets is in data compression. Like several other transforms, the wavelet transform can be used to transform raw data (like images), then encode the transformed data, resulting in effective compression. JPEG 2000 is an image standard that uses wavelets. For details see wavelet compression.
[edit] History
The development of wavelets can be linked to several separate trains of thought, starting with Haar's work in the early 20th century. Notable contributions to wavelet theory can be attributed to Goupillaud, Grossmann and Morlet's formulation of what is now known as the CWT (1982), Strömberg's early work on discrete wavelets (1983), Daubechies' orthogonal wavelets with compact support (1988), Mallat's multiresolution framework (1989), Delprat's time-frequency interpretation of the CWT (1991), Newland's Harmonic wavelet transform and many others since.
[edit] Time line
- First wavelet (Haar wavelet) by Alfred Haar (1909)
- Since the 1950s: Jean Morlet and Alex Grossmann
- Since the 1980s: Yves Meyer, Stéphane Mallat, Ingrid Daubechies, Ronald Coifman, Victor Wickerhauser,
[edit] Wavelet transforms
There are a large number of wavelet transforms each suitable for different applications. For a full list see list of wavelet-related transforms but the common ones are listed below:
- Continuous wavelet transform (CWT)
- Discrete wavelet transform (DWT)
- Fast wavelet transform (FWT)
- Wavelet packet decomposition (WPD)
- Stationary wavelet transform (SWT)
[edit] List of wavelets
[edit] Discrete wavelets
- Beylkin (18)
- Coiflet (6, 12, 18, 24, 30)
- Daubechies wavelet (2, 4, 6, 8, 10, 12, 14, 16, 18, 20)
- Cohen-Daubechies-Feauveau wavelet (Sometimes referred to as CDF N/P or Daubechies biorthogonal wavelets)
- Haar wavelet
- Symmlet
- Complex wavelet transform
[edit] Continuous wavelets
- Mexican hat wavelet
- Hermitian wavelet
- Hermitian hat wavelet
- Complex mexican hat wavelet
- Morlet wavelet
- Modified Morlet wavelet
- Beta wavelet
- Hilbert-Hermitian wavelet
[edit] See also
- Multiresolution analysis
- Filter banks
- Scale space
- Ultra wideband radio- transmits wavelets.
- short-time Fourier transform
- chirplet transform
- fractional Fourier transform
[edit] References
- Paul S. Addison, The Illustrated Wavelet Transform Handbook, Institute of Physics, 2002, ISBN 0-7503-0692-0
- Ingrid Daubechies, Ten Lectures on Wavelets, Society for Industrial and Applied Mathematics, 1992, ISBN 0-89871-274-2
- P. P. Vaidyanathan, Multirate Systems and Filter Banks, Prentice Hall, 1993, ISBN 0-13-605718-7
- Mladen Victor Wickerhauser, Adapted Wavelet Analysis From Theory to Software, A K Peters Ltd, 1994, ISBN 1-56881-041-5
- Gerald Kaiser, A Friendly Guide to Wavelets, Birkhauser, 1994, ISBN 0-8176-3711-7
- Haar A., Zur Theorie der orthogonalen Funktionensysteme, Mathematische Annalen, 69, pp 331-371, 1910.
- Ramazan Gençay, Faruk Selçuk and Brandon Whitcher, An Introduction to Wavelets and Other Filtering Methods in Finance and Economics, Academic Press, 2001, ISBN 0-12-279670-5
- Donald B. Percival and Andrew T. Walden, Wavelet Methods for Time Series Analysis, Cambridge University Press, 2000, ISBN 0-5216-8508-7
[edit] External links
- Wavelets made Simple
- Wavelet Digest
- Course on Wavelets given at UC Santa Barbara, 2004
- Amara's Wavelet Page
- Wavelet Posting Board
- The Wavelet Tutorial by Polikar (Easy to understand when you have some background with fourier transforms!)
- OpenSource Wavelet C++ Code
- An Introduction to Wavelets
- Wavelets for Kids (PDF file) (Introductory (for very smart kids!))
- Link collection about wavelets
- List of Wavelet resources, libraries and source codes
- Wavelet forums (French) Wavelet forum (English)
- "Biorthogonal sinc wavelets"
- Gerald Kaiser's acoustic and electromagnetic wavelets
- A really friendly guide to wavelets