View source for Wavelet transform

[[File:Jpeg2000 2-level wavelet transform-lichtenstein.png|thumb|300px|An example of the 2D [[discrete wavelet transform]] that is used in [[JPEG2000]].]]
{{broader|Wavelet}}
In  [[mathematics]], a '''wavelet series''' is a representation of a [[square-integrable]] ([[real number|real]]- or [[complex number|complex]]-valued) [[function (mathematics)|function]] by a certain [[orthonormal]] [[series (mathematics)|series]] generated by a [[wavelet]]. This article provides a formal, mathematical definition of an '''orthonormal wavelet''' and of the '''integral wavelet transform'''. 

==Definition==
A function <math>\scriptstyle \psi \,\in\, L^2(\mathbb{R})</math> is called an '''orthonormal wavelet''' if it can be used to define a [[Hilbert space#Orthonormal bases|Hilbert basis]], that is a [[complete space|complete]] [[orthonormality|orthonormal system]], for the [[Hilbert space]] <math>\scriptstyle L^2\left(\mathbb{R}\right)</math> of [[Square-integrable function|square integrable]] functions.

The Hilbert basis is constructed as the family of functions <math>\scriptstyle  \{\psi_{jk}:\, j,\, k \,\in\, \Z\}</math> by means of [[Dyadic transformation|dyadic]] [[translation (geometry)|translation]]s and [[dilation (operator theory)|dilation]]s of <math>\scriptstyle \psi\,</math>,
:<math>\psi_{jk}(x) = 2^\frac{j}{2} \psi\left(2^jx - k\right)\,</math>

for integers <math>\scriptstyle j,\, k \,\in\, \mathbb{Z}</math>.

If under the standard [[inner product]] on <math>\scriptstyle L^2\left(\mathbb{R}\right)</math>,
:<math>\langle f, g\rangle = \int_{-\infty}^\infty f(x)\overline{g(x)}dx</math>

this family is orthonormal, it is an orthonormal system:
:<math>\begin{align}
  \langle\psi_{jk},\psi_{lm}\rangle &= \int_{-\infty}^\infty \psi_{jk}(x)\overline{\psi_{lm}(x)}dx \\
                                    &=\delta_{jl}\delta_{km}
\end{align}</math>

where <math>\scriptstyle \delta_{jl}\,</math> is the [[Kronecker delta]].

Completeness is satisfied if every function <math>\scriptstyle f \,\in\, L^2\left(\mathbb{R}\right)</math> may be expanded in the basis as
:<math>f(x) = \sum_{j, k=-\infty}^\infty c_{jk} \psi_{jk}(x)</math>

with convergence of the series understood to be [[norm (mathematics)#Properties|convergence in norm]]. Such a representation of ''f'' is known as a '''wavelet series'''.  This implies that an orthonormal wavelet is [[dual wavelet|self-dual]].

The '''integral wavelet transform''' is the [[integral transform]] defined as

:<math>\left[W_\psi f\right](a, b) = \frac{1}{\sqrt{|a|}} \int_{-\infty}^\infty \overline{\psi\left(\frac{x-b}{a}\right)}f(x)dx\,</math>

The '''wavelet coefficients''' <math>\scriptstyle c_{jk}</math> are then given by

:<math>c_{jk} = \left[W_\psi f\right]\left(2^{-j}, k2^{-j}\right)</math>

Here, <math>\scriptstyle a \;=\; 2^{-j}</math> is called the '''binary dilation''' or '''dyadic dilation''', and <math>\scriptstyle b \;=\; k2^{-j}</math> is the '''binary''' or '''dyadic position'''.

== Principle ==

The fundamental idea of wavelet transforms is that the transformation should allow only changes in time extension, but not shape.  This is affected by choosing suitable basis functions that allow for this.{{how|date=July 2013}} Changes in the time extension are expected to conform to the corresponding analysis frequency of the basis function. Based on the [[Uncertainty principle#Signal processing|uncertainty principle]] of signal processing,

:<math>\Delta t \Delta \omega \geqq \frac{1}{2}</math>

where t represents time and ω angular frequency (ω = 2πf, where f is temporal frequency).

The higher the required resolution in time, the lower the resolution in frequency has to be. The larger the extension of the analysis windows is chosen, the larger is the value of <math>\scriptstyle \Delta t</math>{{how|date=May 2014}}.

[[File:Basis function with compression factor.jpg|right|430px]]

When Δt is large,
# Bad time resolution
# Good frequency resolution
# Low frequency, large scaling factor

When Δt is small
# Good time resolution
# Bad frequency resolution
# High frequency, small scaling factor

In other words, the basis function Ψ can be regarded as an impulse response of a system with which the function x(t) has been filtered. The transformed signal provides information about the time and the frequency. Therefore, wavelet-transformation contains information similar to the [[Short-time Fourier transform|short-time-Fourier-transformation]], but with additional special properties of the wavelets, which show up at the resolution in time at higher analysis frequencies of the basis function. The difference in time resolution at ascending frequencies for the [[Fourier transform]] and the wavelet transform is shown below. Note however, that the frequency resoultion is decreasing for increasing frequencies while the temporal resolution increases. This consequence of Heisenberg's uncertainty principle is not correctly displayed in the Figure.

[[File:STFT and WT.jpg|center|500px]]

This shows that wavelet transformation is good in time resolution of high frequencies, while for slowly varying functions, the frequency resolution is remarkable.

Another example: The analysis of three superposed sinusoidal signals <math>\scriptstyle y(t) \;=\; \sin(2 \pi f_0 t) \;+\; \sin(4 \pi f_0 t) \;+\; \sin(8 \pi f_0 t)</math> with STFT and wavelet-transformation.

[[File:Analysis of three superposed sinusoidal signals.jpg|center|500px]]

==Wavelet compression==
'''Wavelet compression''' is a form of [[data compression]] well suited for [[image compression]] (sometimes also [[video compression]] and [[audio compression (data)|audio compression]]). Notable implementations are [[JPEG 2000]], [[DjVu]] and [[ECW (file format)|ECW]] for still images, [[CineForm]], and the BBC's [[Dirac (codec)|Dirac]]. The goal is to store image data in as little space as possible in a [[Computer file|file]].  Wavelet compression can be either [[lossless data compression|lossless]] or [[lossy data compression|lossy]].<ref>[[JPEG 2000]], for example, may use a 5/3 wavelet for lossless (reversible) transform and a 9/7 wavelet for lossy (irreversible) transform.</ref> Wavelet coding is a variant of [[discrete cosine transform]] (DCT) coding that uses wavelets instead of DCT's block-based algorithm.<ref name="Hoffman">{{cite book |last1=Hoffman |first1=Roy |title=Data Compression in Digital Systems |date=2012 |publisher=[[Springer Science & Business Media]] |isbn=9781461560319 |page=124 |url=https://books.google.com/books?id=FOfTBwAAQBAJ |quote=Basically, wavelet coding is a variant on DCT-based transform coding that reduces or eliminates some of its limitations. (...) Another advantage is that rather than working with 8 × 8 blocks of pixels, as do JPEG and other block-based DCT techniques, wavelet coding can simultaneously compress the entire image.}}</ref>

Using a wavelet transform, the wavelet compression methods are adequate for representing [[Transient (acoustics)|transient]]s, such as percussion sounds in audio, or high-frequency components in two-dimensional images, for example an image of stars on a night sky. This means that the transient elements of a data signal can be represented by a smaller amount of information than would be the case if some other transform, such as the more widespread [[discrete cosine transform]], had been used.

Discrete wavelet transform has been successfully applied for the compression of electrocardiograph (ECG) signals<ref>A. G. Ramakrishnan and S. Saha, [http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=649997&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F10%2F14156%2F00649997.pdf%3Farnumber%3D649997 "ECG coding by wavelet-based linear prediction,"] ''IEEE Trans. Biomed. Eng.'', Vol. 44, No. 12, pp. 1253-1261, 1977.</ref> In this work, the high correlation between the corresponding wavelet coefficients of signals of successive cardiac cycles is utilized employing linear prediction.
 
Wavelet compression is not good for all kinds of data: transient signal characteristics mean good wavelet compression, while smooth, periodic signals are better compressed by other methods, particularly traditional harmonic compression (frequency domain, as by Fourier transforms and related).

See [https://web.archive.org/web/20100228145846/http://x264dev.multimedia.cx/?p=317 Diary Of An x264 Developer: The problems with wavelets] (2010) for discussion of practical issues of current methods using wavelets for video compression.

===Method===
First a wavelet transform is applied.  This produces as many [[coefficient]]s as there are [[pixel]]s in the image (i.e., there is no compression yet since it is only a transform).  These [[coefficient]]s can then be compressed more easily because the information is statistically concentrated in just a few coefficients.  This principle is called [[transform coding]].  After that, the [[coefficient]]s are [[Quantization (signal processing)|quantized]] and the quantized values are [[entropy encoding|entropy encoded]] and/or [[run-length encoding|run length encoded]].

A few 1D and 2D applications of wavelet compression use a technique called "wavelet footprints".<ref>
 N. Malmurugan, A. Shanmugam, S. Jayaraman and V. V. Dinesh Chander.
 [http://www.acadjournal.com/2005/V14/part6/p1/ "A New and Novel Image Compression Algorithm Using Wavelet Footprints"]
</ref><ref>
 Ho Tatt Wei and Jeoti, V.
 "A wavelet footprints-based compression scheme for ECG signals".
 {{Cite book| doi = 10.1109/TENCON.2004.1414412| year = 2004| last1 = Ho Tatt Wei| volume = A| last2 = Jeoti | first2 = V.| pages = 283 | chapter = A wavelet footprints-based compression scheme for ECG signals| title = 2004 IEEE Region 10 Conference TENCON 2004| isbn = 0-7803-8560-8}}
</ref>

==Comparison with Fourier transform and time-frequency analysis==
{| class="wikitable"
|-
! Transform !! Representation !! Input
|-
| [[Fourier transform]] || <math> \hat f(\xi) = \int_{-\infty}^{\infty} f(x)e^{-2 \pi ix \xi}\, dx</math> || ''ξ'', frequency
|-
| [[Time-frequency analysis]] || <math>X(t, f)</math> || ''t'', time; ''f'', frequency
|-
| Wavelet transform || <math> X(a,b) = \frac{1}{\sqrt{a}}\int_{-\infty}^{\infty}\overline{\Psi\left(\frac{t - b}{a}\right)} x(t)\, dt </math> || ''a'', scaling; ''b'', time
|}
Wavelets have some slight benefits over Fourier transforms in reducing computations when examining specific frequencies. However, they are rarely more sensitive, and indeed, the common [[Morlet wavelet]] is mathematically identical to a [[short-time Fourier transform]] using a Gaussian window function.<ref>{{cite journal|last1=Bruns|first1=Andreas|title=Fourier-, Hilbert- and wavelet-based signal analysis: are they really different approaches?|journal=Journal of Neuroscience Methods|date=2004|volume=137|issue=2|pages=321–332|doi=10.1016/j.jneumeth.2004.03.002|pmid=15262077|url=https://www.ncbi.nlm.nih.gov/pubmed/?term=10.1016%2Fj.jneumeth.2004.03.002}}</ref> The exception is when searching for signals of a  known, non-sinusoidal shape (e.g., heartbeats); in that case, using matched wavelets can outperform standard STFT/Morlet analyses.<ref>{{cite book|last1=Krantz|first1=Steven G.|title=A Panorama of Harmonic Analysis|date=1999|publisher=Mathematical Association of America|isbn=0-88385-031-1}}</ref>

==Other practical applications==
The wavelet transform can provide us with the frequency of the signals and the time associated to those frequencies, making it very convenient for its application in numerous fields. For instance, signal processing of accelerations for gait analysis,<ref>[https://www.youtube.com/watch?v=DTpEVQSEBBk "Novel method for stride length estimation with body area network accelerometers"], ''IEEE BioWireless 2011'', pp. 79-82</ref> for fault detection,<ref>{{ cite journal | title=Shannon wavelet spectrum analysis on truncated vibration signals for machine incipient fault detection| journal=Measurement Science and Technology| year=2012 | last=Liu | volume=23 | issue=5 | pages=1–11 | first1=Jie | doi=10.1088/0957-0233/23/5/055604}}</ref> for design of low power pacemakers and also in ultra-wideband (UWB) wireless communications.<ref>{{Cite journal | doi = 10.1016/j.phycom.2009.07.001| title = Emerging applications of wavelets: A review| journal = Physical Communication| volume = 3| pages = 1| year = 2010| last1 = Akansu | first1 = A. N. | last2 = Serdijn | first2 = W. A. | last3 = Selesnick | first3 = I. W. | url = http://web.njit.edu/~akansu/PAPERS/ANA-IWS-WAS-ELSEVIER%20PHYSCOM%202010.pdf}}</ref>

{{ordered list
| Discretizing of the c-τ-axis

Applied the following discretization of frequency and time:
:<math>\begin{align}
     c_n &= c_0^n \\
  \tau_m &= m \cdot T \cdot c_0^n
\end{align}</math>

Leading to wavelets of the form, the discrete formula for the basis wavelet:
:<math>\Psi(k, n, m) = \frac{1}{\sqrt{c_0^n}}\cdot\Psi\left[\frac{k - m c_0^n}{c_0^n}T\right] = \frac{1}{\sqrt{c_0^n}}\cdot\Psi\left[\left(\frac{k}{c_0^n} - m\right)T\right]</math>

Such discrete wavelets can be used for the transformation:
:<math>Y_{DW}(n, m) = \frac{1}{\sqrt{c_0^n}}\cdot\sum_{k=0}^{K - 1} y(k)\cdot\Psi\left[\left(\frac{k}{c_0^n} - m\right)T\right]</math>

| Implementation via the FFT (fast Fourier transform)

As apparent from wavelet-transformation representation (shown below) 
:<math>Y_W(c, \tau) = \frac{1}{\sqrt{c}}\cdot\int_{-\infty}^{\infty} y(t) \cdot \Psi\left(\frac{t - \tau}{c}\right)\, dt </math>

where c is scaling factor, τ represents time shift factor

and as already mentioned in this context, the wavelet-transformation corresponds to a convolution of a function y(t) and a wavelet-function. A convolution can be implemented as a multiplication in the frequency domain. With this the following approach of implementation results into:
* Fourier-transformation of signal y(k) with the FFT
* Selection of a discrete scaling factor <math>c_n</math>
* Scaling of the wavelet-basis-function by this factor <math>c_n</math> and subsequent FFT of this function
* Multiplication with the transformed signal YFFT of the first step
* Inverse transformation of the product into the time domain results in ''Y<sub>W</sub><math>(c, \tau)</math>'' for different discrete values of τ and a discrete value of <math>c_n</math>
* Back to the second step, until all discrete scaling values for <math>c_n</math>are processed

There are many different types of wavelet transforms for specific purposes. See also a full [[list of wavelet-related transforms]] but the common ones are listed below: [[Mexican hat wavelet]], [[Haar Wavelet]], [[Daubechies wavelet]], triangular wavelet.
}}

==See also==
* [[Continuous wavelet transform]]
* [[Discrete wavelet transform]]
* [[Complex wavelet transform]]
* [[Stationary wavelet transform]]
* [[Dual wavelet]]
* [[Multiresolution analysis]]
* [[MrSID]], the image format developed from original wavelet compression research at [[Los Alamos National Laboratory]] (LANL).
* [[ECW (file format)|ECW]], a wavelet-based [[geospatial]] image format designed for speed and processing efficiency
* [[JPEG 2000]], a wavelet-based [[image compression]] standard
* [[DjVu]] format uses wavelet-based IW44 algorithm for image compression
* [[scaleogram]]s, a type of [[spectrogram]] generated using wavelets instead of a [[short-time Fourier transform]].
* [[Wavelet]]
* [[Haar wavelet]]
* [[Daubechies wavelet]]
* [[Morlet wavelet]]
* [[Gabor wavelet]]
* [[Chirplet transform]]
* [[Time-frequency representation]]
* [[S transform]]
* [[Set partitioning in hierarchical trees]]
* [[Short-time Fourier transform]]

==References==
* {{cite book |first=Yves |last=Meyer |title= Wavelets and Operators |url=https://archive.org/details/waveletsoperator0000meye |url-access=registration |year=1992 |publisher= Cambridge University Press |location=Cambridge |isbn=0-521-42000-8}}
* {{cite book |first=Charles K. |last=Chui |title=An Introduction to Wavelets |year=1992 |publisher=Academic Press |location=San Diego |isbn=0-12-174584-8}}
* {{cite book |first1=Ali N. |last1=Akansu |first2=Richard A. |last2=Haddad|title=Multiresolution Signal Decomposition: Transforms, Subbands, Wavelets |year=1992 |publisher=Academic Press |location=San Diego |isbn=978-0-12-047141-6}}
{{Reflist}}

==External links==
{{Commons category|Wavelets}}
* {{cite web
| author = Amara Graps
| date=  
| title = An Introduction to Wavelets
| url = http://dl.acm.org/citation.cfm?id=615342
}}

* {{cite web|author=Robi Polikar|date=2001-01-12|title=The Wavelet Tutorial|url=http://users.rowan.edu/~polikar/WTtutorial.html}}

* [https://www.scribd.com/document/370574131/Concise-Introduction-to-Wavelets Concise Introduction to Wavelets by René Puchinger]

{{Authority control}}

[[Category:Wavelets]]
[[Category:Functional analysis]]
[[Category:Signal processing]]
[[Category:Image compression]]