Wavelet transform

An example of the 2D discrete wavelet transform that is used in JPEG2000.

In mathematics, a wavelet series is a representation of a square-integrable (real- or complex-valued) function by a certain orthonormal series generated by a wavelet. Nowadays, wavelet transformation is one of the most popular candidates of the time-frequency-transformations. This article provides a formal, mathematical definition of an orthonormal wavelet and of the integral wavelet transform.

Formal definition

A function $\psi\in L^2(\mathbb{R})$ is called an orthonormal wavelet if it can be used to define a Hilbert basis, that is a complete orthonormal system, for the Hilbert space $L^2(\mathbb{R})$ of square integrable functions.

The Hilbert basis is constructed as the family of functions $\{\psi_{jk}: j, k \in \Z\}$ by means of dyadic translations and dilations of $\psi\,$ ,

\psi_{jk}(x) = 2^\frac{j}{2} \psi(2^jx - k)\,

for integers $j, k \in \mathbb{Z}$ .

This family is an orthonormal system if it is orthonormal under the standard inner product $\langle f, g\rangle = \int_{-\infty}^\infty f(x)\overline{g(x)}dx$ on $L^2(\mathbb{R}).$

\langle\psi_{jk},\psi_{lm}\rangle = \delta_{jl}\delta_{km}

where $\delta_{jl}\,$ is the Kronecker delta.

Completeness is satisfied if every function $h \in L^2(\mathbb{R})$ may be expanded in the basis as

h(x) = \sum_{j, k=-\infty}^\infty c_{jk} \psi_{jk}(x)

with convergence of the series understood to be convergence in norm. Such a representation of a function f is known as a wavelet series. This implies that an orthonormal wavelet is self-dual.

Wavelet transform

The integral wavelet transform is the integral transform defined as

\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\,

The wavelet coefficients $c_{jk}$ are then given by

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

Here, $a = 2^{-j}$ is called the binary dilation or dyadic dilation, and $b = k2^{-j}$ is the binary or dyadic position.

Basic idea

The fundamental idea of wavelet transforms is that the transformation should allow only changes in time extension, but not shape. This is effected by choosing suitable basis functions that allow for this. Changes in the time extension are expected to conform to the corresponding analysis frequency of the basis function. Based on the uncertainty principle of signal processing,

\Delta t \Delta \omega \geqq \frac{1}{2}

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 $\Delta t$ .

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-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.

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 $y(t) = \sin(2 \pi f_0 t) + \sin(4 \pi f_0 t) + \sin(8 \pi f_0 t)$ with STFT and wavelet-transformation.

Wavelet compression

Wavelet compression is a form of data compression well suited for image compression (sometimes also video compression and audio compression). Notable implementations are JPEG 2000, DjVu and ECW for still images, CineForm, and the BBC's Dirac. The goal is to store image data in as little space as possible in a file. Wavelet compression can be either lossless or lossy.^[1]

Using a wavelet transform, the wavelet compression methods are adequate for representing transients, 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.

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 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 coefficients as there are pixels in the image (i.e., there is no compression yet since it is only a transform). These coefficients 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 coefficients are quantized and the quantized values are entropy encoded and/or run length encoded.

A few 1D and 2D applications of wavelet compression use a technique called "wavelet footprints".^[2]^[3]

Comparison with wavelet transformation, Fourier transformation and time-frequency analysis

Transformation	Representation	Input
Fourier transform	$f(\xi) = \int_{-\infty}^{\infty} f(x)e^{-2 \pi ix \xi}\, dx$	ξ, frequency
Time-frequency analysis	$X(t, f)$	t, time; f, frequency
Wavelet transform	$X(a,b) = \frac{1}{\sqrt{a}}\int_{-\infty}^{\infty}\overline{\Psi\left(\frac{t - b}{a}\right)} x(t)\, dt$	a, scaling; b, time

Almost in all fields of science where the Fourier transform is a conventional method for analyzing experimental data, the Wavelet transform can be used as a higher quality method for finding quasi-harmonic components in any signals.^[4] Wavelet transform gives a full and precise image of the quasi-harmonic components’ dynamics in signal.^[5]

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,^[6] for fault detection,^[7] for design of low power pacemakers and also in ultra-wideband (UWB) wireless communications.^[8]

(1) Discretizing of the c-τ-axis

Applied the following discretization of frequency and time:

\begin{align} c_n &= c_0^n \\ \tau_m &= m \cdot T \cdot c_0^n \end{align}

Leading to wavelets of the form, the discrete formula for the basis wavelet:

\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]

Such discrete wavelets can be used for the transformation:

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]

(2) Implementation via the FFT (fast Fourier transform)

As apparent from wavelet-transformation representation (shown below)

Y_W(c, \tau) = \frac{1}{\sqrt{c}}\cdot\int_{-\infty}^{\infty} y(k) \cdot \Psi\left(\frac{t - \tau}{c}\right)\, dt

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 $c_n$
Scaling of the wavelet-basis-function by this factor $c_n$ 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_W $(c, \tau)$ for different discrete values of τ and a discrete value of $c_n$
Back to the second step, until all discrete scaling values for $c_n$ are processed

There are large 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.

References

Meyer, Yves (1992). Wavelets and Operators. Cambridge: Cambridge University Press. ISBN 0-521-42000-8.
Chui, Charles K. (1992). An Introduction to Wavelets. San Diego: Academic Press. ISBN 0-12-174584-8.
Akansu, Ali N.; Haddad, Richard A. (1992). Multiresolution Signal Decomposition: Transforms, Subbands, Wavelets. San Diego: Academic Press. ISBN 978-0-12-047141-6.

↑ JPEG 2000, for example, may use a 5/3 wavelet for lossless (reversible) transform and a 9/7 wavelet for lossy (irreversible) transform.
↑ N. Malmurugan, A. Shanmugam, S. Jayaraman and V. V. Dinesh Chander. "A New and Novel Image Compression Algorithm Using Wavelet Footprints"
↑ Ho Tatt Wei and Jeoti, V. "A wavelet footprints-based compression scheme for ECG signals". Ho Tatt Wei; Jeoti, V. (2004). "A wavelet footprints-based compression scheme for ECG signals". 2004 IEEE Region 10 Conference TENCON 2004 A. p. 283. doi:10.1109/TENCON.2004.1414412. ISBN 0-7803-8560-8.
↑ Krantz, Steven G. (1999). A Panorama of Harmonic Analysis. Mathematical Association of America. ISBN 0-88385-031-1.
↑ Drozdov, A. (2014). "Comparison of wavelet transform and fourier transform applied to analysis of non-stationary processes" (PDF). Nanosystems: physics, chemistry, mathematics 5: 363–373.
↑ "Novel method for stride length estimation with body area network accelerometers", IEEE BioWireless 2011, pp. 79-82
↑ Liu, Jie (2012). "Shannon wavelet spectrum analysis on truncated vibration signals for machine incipient fault detection". Measurement Science and Technology 23 (5): 1–11. doi:10.1088/0957-0233/23/5/055604.
↑ Akansu, A. N.; Serdijn, W. A.; Selesnick, I. W. (2010). "Emerging applications of wavelets: A review" (PDF). Physical Communication 3: 1. doi:10.1016/j.phycom.2009.07.001.

External links

Wikimedia Commons has media related to Wavelets.

Amara Graps. "An Introduction to Wavelets".

Robi Polikar (2001-01-12). "The Wavelet Tutorial".