NationMaster - Encyclopedia: Discrete wavelet transform

In numerical analysis and functional analysis, a discrete wavelet transform (DWT) is any wavelet transform for which the wavelets are discretely sampled. Numerical analysis is the study of approximate methods for the problems of continuous mathematics (as distinguished from discrete mathematics). ... Functional analysis is the branch of mathematics, and specifically of analysis, concerned with the study of spaces of functions. ... The wavelet transform is a transformation to basis functions that are localized in scale and in time as well (where the Fourier transform is only localized in frequency, never giving any information about where in space or time the frequency happens). ... In mathematics, wavelets, wavelet analysis, and the wavelet transform refers to the representation of a signal in terms of a finite length or fast decaying oscillating waveform (known as the mother wavelet). ...

The first DWT was invented by the Hungarian mathematician Alfréd Haar. For an input represented by a list of $2 n$ numbers, the Haar wavelet transform may be considered to simply pair up input values, storing the difference and passing the sum. This process is repeated recursively, pairing up the sums to provide the next scale: finally resulting in $2 n - 1$ differences and one final sum. AlfrÃ©d Haar (October 11, 1885 - March 16, 1933) was a Hungarian mathematician. ... The Haar wavelet The Haar wavelet is the first known wavelet and was proposed in 1909 by Alfred Haar. ...

This simple DWT illustrates the desirable properties of wavelets in general. First, it can be performed in $O (n)$ operations; second, it captures not only a notion of the frequency content of the input, by examining it at different scales, but also temporal content, i.e. the times at which these frequencies occur. Combined, these two properties make the Fast wavelet transform (FWT), an alternative to the conventional Fast fourier transform. The Fast (Lifting) Wavelet Transform is a mathematical algorithm designed to turn a waveform or signal in the time domain into a sequence of coefficients based on an orthogonal basis of small finite waves, or wavelets. ... The Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. ...

The most commonly used set of discrete wavelet transforms was formulated by the Belgian mathematician Ingrid Daubechies in 1988. This formulation is based on the use of recurrence relations to generate progressively finer discrete samplings of an implicit mother wavelet function; each resolution is twice that of the previous scale. In her seminal paper, Daubechies derives a family of wavelets, the first of which is the Haar wavelet. Interest in this field has exploded since then, and many variations of Daubechies' original wavelets were developed. Ingrid Daubechies (born August 17, 1954) is a Belgian physicist and mathematician. ... In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ... Daubechies 20 2-d wavelet (Wavelet Fn X Scaling Fn) Named after Ingrid Daubechies, the orthogonal Daubechies wavelets are a class of wavelets characterized by a maximal number of vanishing moments for some given support. ...

Other forms of discrete wavelet transform include the non- or undecimated wavelet transform (where downsampling is omitted), the Newland transform (where an orthonormal basis of wavelets is formed from appropriately constructed top-hat filters in frequency space). Wavelet packet transforms are also related to the discrete wavelet transform. Complex wavelet transform is another form. The Stationary Wavelet Transform (SWT) (also know as the Redundant Wavelet Transform or A Trous Algorithm), is similar to the DWT except the signal is never subsampled and the filters are different for each level of decomposition. ... The Newland transform is a method to create a time-frequency representation that combines advantages of the short-time Fourier transform and the Continuous wavelet transform. ... In linear algebra, two vectors v and w are said to be orthonormal if they are both orthogonal (according to a given inner product) and normalized. ... Frequency domain is a term used to describe the analysis of mathematical functions with respect to frequency. ... Wavelet packet decomposition (WPD) (sometimes known as just wavelet packets) is a wavelet transform where the signal is passed though more filters than the DWT. In the DWT, each level is calculated by passing the previous approximation coefficients though a high and low pass filters. ... The complex wavelet transform is a complex-valued extension to the standard discrete wavelet transform (DWT). ...

The discrete wavelet transform has a huge number of applications in science, engineering, mathematics and computer science. Most notably, it is used for signal coding, to represent a discrete signal in a more redundant form, often as a preconditioning for data compression. In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes. ...

1 Definition
- 1.1 One level of the transform
- 1.2 Cascading and Filter banks
2 Code examples
3 References
4 See also

Definition

One level of the transform

The DWT of a signal $x$ is calculated by passing it through a series of filters. First the samples are passed through a low pass filter with impulse response $g$ resulting in a convolution of the two: The Impulse response from a simple audio system. ... In mathematics and, in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version of g. ...

$y[n] = (x * g)[n] = sumlimits_{k = - infty }^infty {x[k] g[n - k]}$

The signal is also decomposed simultaneously using a high-pass filter $h$ . The outputs giving the detail coefficients (from the high-pass filter) and approximation coefficients (from the low-pass). It is important that the two filters are related to each other and they are known as a quadrature mirror filter. In digital signal processing, a quadrature mirror filter is a filter bank which splits an input signal into two bands which are usually then subsampled by a factor of 2. ...

However, since half the frequencies of the signal have now been removed, half the samples can be discarded according to Nyquist’s rule. The filter outputs are then downsampled by 2: Downsampling (or subsampling) is the process of reducing the sampling rate of a signal. ...

$y_{mathrm{low}} [n] = sumlimits_{k = - infty }^infty {x[k] g[2 n - k]}$

$y_{mathrm{high}} [n] = sumlimits_{k = - infty }^infty {x[k] h[2 n - k]}$

This decomposition has halved the time resolution since only half of each filter output characterises the signal. However, each output has half the frequency band of the input so the frequency resolution has been doubled. This is in keeping with the Heisenberg Uncertainty Principle. In quantum physics, the Heisenberg uncertainty principle, sometimes called the Heisenberg indeterminacy principle, expresses a limitation on accuracy of (nearly) simultaneous measurement of observables such as the position and the momentum of a particle. ...

Block diagram of filter analysis

With the downsampling operator $downarrow$ Image File history File links Discrete wavelet transform. ... Downsampling (or subsampling) is the process of reducing the sampling rate of a signal. ...

$(y downarrow k)[n] = y[k n]$

the above summation can be written more concisely.

$y_{mathrm{low}} = (x*g)downarrow 2$

$y_{mathrm{high}} = (x*h)downarrow 2$

However computing a complete convolution $x * g$ with subsequent downsampling would waste computation time.

The Lifting scheme is an optimization where these two computations are interleaved. The Lifting scheme is a technique for performing the Discrete wavelet transform. ...

Cascading and Filter banks

This decomposition is repeated to further increase the frequency resolution and the approximation coefficients decomposed with high and low pass filters and then down-sampled. This is represented as a binary tree with nodes representing a sub-space with a different time-frequency localisation. The tree is known as a filter bank. A filter bank is an array of band-pass filters that separates the input signal into several components, each one carrying a single frequency subband of the original signal. ...

A 3 level filter bank

At each level in the above diagram the signal is decomposed into low and high frequencies. Due to the decomposition process the input signal must be a multiple of $2 n$ where $n$ is the number of levels. Image File history File links wavelet filter bank. ...

For example a signal with 32 samples, frequency range 0 to $f n$ and 3 levels of decomposition, 4 output scales are produced:

Level	Frequencies	Samples
3	$0$ to $f n / 8$	4
3	$f n / 8$ to $f n / 4$	4
2	$f n / 4$ to $f n / 2$	8
1	$f n / 2$ to $f n$	16

Frequency domain representation of the DWT

Image File history File links Freq represnetation of DWT filter bank. ...

Code examples

In its simplest form, the DWT is remarkably easy to compute.

The Haar wavelet in Java: The Haar wavelet The Haar wavelet is the first known wavelet and was proposed in 1909 by Alfred Haar. ... Java is an object-oriented applications programming language developed by Sun Microsystems in the early 1990s. ...

 public static int[] invoke(int[] input){ //WARNING: This will destroy the contents of the input array //This function assumes input.length=2^n, n>1 int[] output = new int[input.length]; for(int length = input.length >> 1; ; length >>= 1){ //length=2^n, WITH DECREASING n for(int i = 0; i < length; i++) { int sum = input[i*2]+input[i*2+1]; int difference = input[i*2]-input[i*2+1]; output[i] = sum; output[length+i] = difference; } if (length == 1) return output; //Swap arrays to do next iteration System.arraycopy(output, 0, input, 0, length<<1); } }

A fast lifting implementation of the discrete biorthogonal CDF 9/7 wavelet transform in C language, used in the JPEG-2000 image compression standard can be found here. The historically first family of biorthogonal wavelets, which was made popular by Ingrid Daubechies. ... JPEG 2000 is a wavelet-based image compression standard. ...

References

Stéphane Mallat, A Wavelet Tour of Signal Processing

Contents

Definition GA_googleFillSlot("encyclopedia_square");

One level of the transform

Cascading and Filter banks

Code examples

References

See also

Definition