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. As with other wavelet transforms, a key advantage it has over Fourier transforms is temporal resolution: it captures both frequency and location information (location in time).

Applications[edit]

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. Practical applications can also be found in signal processing of accelerations for gait analysis,^[13]^[14] image processing,^[15]^[16] in digital communications and many others.^[17] ^[18]^[19]

It is shown that discrete wavelet transform (discrete in scale and shift, and continuous in time) is successfully implemented as analog filter bank in biomedical signal processing for design of low-power pacemakers and also in ultra-wideband (UWB) wireless communications.^[20]

Sinusoidal waves differ only in their frequency. The first does not complete any cycles, the second completes one full cycle, the third completes two cycles, and the fourth completes three cycles (which is equivalent to completing one cycle in the opposite direction). Differences in phase can be represented by multiplying a given basis vector by a complex constant.

Wavelets, by contrast, have both frequency and location. As before, the first completes zero cycles, and the second completes one cycle. However, the third and fourth both have the same frequency, twice that of the first. Rather than differing in frequency, they differ in location — the third is nonzero over the first two elements, and the fourth is nonzero over the second two elements.

Wavelets are often used to denoise two dimensional signals, such as images. The following example provides three steps to remove unwanted white Gaussian noise from the noisy image shown. Matlab was used to import and filter the image.

The first step is to choose a wavelet type, and a level N of decomposition. In this case biorthogonal 3.5 wavelets were chosen with a level N of 10. Biorthogonal wavelets are commonly used in image processing to detect and filter white Gaussian noise,^[21] due to their high contrast of neighboring pixel intensity values. Using these wavelets a wavelet transformation is performed on the two dimensional image.

Following the decomposition of the image file, the next step is to determine threshold values for each level from 1 to N. Birgé-Massart strategy^[22] is a fairly common method for selecting these thresholds. Using this process individual thresholds are made for N = 10 levels. Applying these thresholds are the majority of the actual filtering of the signal.

The final step is to reconstruct the image from the modified levels. This is accomplished using an inverse wavelet transform. The resulting image, with white Gaussian noise removed is shown below the original image. When filtering any form of data it is important to quantify the signal-to-noise-ratio of the result. In this case, the SNR of the noisy image in comparison to the original was 30.4958%, and the SNR of the denoised image is 32.5525%. The resulting improvement of the wavelet filtering is a SNR gain of 2.0567%.^[23]

It is important to note that choosing other wavelets, levels, and thresholding strategies can result in different types of filtering. In this example, white Gaussian noise was chosen to be removed. Although, with different thresholding, it could just as easily have been amplified.

To illustrate the differences and similarities between the discrete wavelet transform with the discrete Fourier transform, consider the DWT and DFT of the following sequence: (1,0,0,0), a unit impulse.

The DFT has orthogonal basis (DFT matrix):

while the DWT with Haar wavelets for length 4 data has orthogonal basis in the rows of:

(To simplify notation, whole numbers are used, so the bases are orthogonal but not orthonormal.)

Preliminary observations include:

The DWT demonstrates the localization: the (1,1,1,1) term gives the average signal value, the (1,1,–1,–1) places the signal in the left side of the domain, and the (1,–1,0,0) places it at the left side of the left side, and truncating at any stage yields a downsampled version of the signal:

The DFT, by contrast, expresses the sequence by the interference of waves of various frequencies – thus truncating the series yields a low-pass filtered version of the series:

Notably, the middle approximation (2-term) differs. From the frequency domain perspective, this is a better approximation, but from the time domain perspective it has drawbacks – it exhibits undershoot – one of the values is negative, though the original series is non-negative everywhere – and ringing, where the right side is non-zero, unlike in the wavelet transform. On the other hand, the Fourier approximation correctly shows a peak, and all points are within $1/4$ of their correct value, though all points have error. The wavelet approximation, by contrast, places a peak on the left half, but has no peak at the first point, and while it is exactly correct for half the values (reflecting location), it has an error of $1/2$ for the other values.

This illustrates the kinds of trade-offs between these transforms, and how in some respects the DWT provides preferable behavior, particularly for the modeling of transients.

Definition[edit]

One level of the transform[edit]

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:

Relationship to the mother wavelet[edit]

The filterbank implementation of wavelets can be interpreted as computing the wavelet coefficients of a discrete set of child wavelets for a given mother wavelet $\psi (t)$ . In the case of the discrete wavelet transform, the mother wavelet is shifted and scaled by powers of two

$\psi _{j,k}(t)={\frac {1}{\sqrt {2^{j}}}}\psi \left({\frac {t-k2^{j}}{2^{j}}}\right)$

where $j$ is the scale parameter and $k$ is the shift parameter, both of which are integers.

Recall that the wavelet coefficient $\gamma$ of a signal $x(t)$ is the projection of $x(t)$ onto a wavelet, and let $x(t)$ be a signal of length $2^{N}$ . In the case of a child wavelet in the discrete family above,

$\gamma _{jk}=\int _{-\infty }^{\infty }x(t){\frac {1}{\sqrt {2^{j}}}}\psi \left({\frac {t-k2^{j}}{2^{j}}}\right)dt$

Now fix $j$ at a particular scale, so that $\gamma _{jk}$ is a function of $k$ only. In light of the above equation, $\gamma _{jk}$ can be viewed as a convolution of $x(t)$ with a dilated, reflected, and normalized version of the mother wavelet, $h(t)={\frac {1}{\sqrt {2^{j}}}}\psi \left({\frac {-t}{2^{j}}}\right)$ , sampled at the points $1,2^{j},2^{2j},...,2^{N}$ . But this is precisely what the detail coefficients give at level $j$ of the discrete wavelet transform. Therefore, for an appropriate choice of $h[n]$ and $g[n]$ , the detail coefficients of the filter bank correspond exactly to a wavelet coefficient of a discrete set of child wavelets for a given mother wavelet $\psi (t)$ .

As an example, consider the discrete Haar wavelet, whose mother wavelet is $\psi =[1,-1]$ . Then the dilated, reflected, and normalized version of this wavelet is $h[n]={\frac {1}{\sqrt {2}}}[-1,1]$ , which is, indeed, the highpass decomposition filter for the discrete Haar wavelet transform.

The , used for interlacing in the Portable Network Graphics (PNG) format, is a multiscale model of the data which is similar to a DWT with Haar wavelets. Unlike the DWT, it has a specific scale – it starts from an 8×8 block, and it downsamples the image, rather than decimating (low-pass filtering, then downsampling). It thus offers worse frequency behavior, showing artifacts (pixelation) at the early stages, in return for simpler implementation.
See also: Adam7 algorithm

Adam7 algorithm

The multiplicative (or geometric) discrete wavelet transform is a variant that applies to an observation model ${\bf {y}}=f{\bf {X}}$ involving interactions of a positive regular function $f$ and a multiplicative independent positive noise $X$ , with $\mathbb {E} X=1$ . Denote ${\cal {W}}$ , a wavelet transform. Since $f{\bf {X}}=f+{f({\bf {X}}-1)}$ , then the standard (additive) discrete wavelet transform ${\cal {W^{+}}}$ is such that ${\cal {W^{+}}}{\bf {y}}={\cal {W^{+}}}f+{\cal {W^{+}}}{f({\bf {X}}-1)},$ where detail coefficients ${\cal {W^{+}}}{f({\bf {X}}-1)}$ cannot be considered as sparse in general, due to the contribution of $f$ in the latter expression. In the multiplicative framework, the wavelet transform is such that ${\cal {W^{\times }}}{\bf {y}}=\left({\cal {W^{\times }}}f\right)\times \left({\cal {W^{\times }}}{\bf {X}}\right).$ This 'embedding' of wavelets in a multiplicative algebra involves generalized multiplicative approximations and detail operators: For instance, in the case of the Haar wavelets, then up to the normalization coefficient $\alpha$ , the standard ${\cal {W^{+}}}$ approximations (arithmetic mean) $c_{k}=\alpha (y_{k}+y_{k-1})$ and details (arithmetic differences) $d_{k}=\alpha (y_{k}-y_{k-1})$ become respectively geometric mean approximations $c_{k}^{\ast }=(y_{k}\times y_{k-1})^{\alpha }$ and geometric differences (details) $d_{k}^{\ast }=\left({\frac {y_{k}}{y_{k-1}}}\right)^{\alpha }$ when using ${\cal {W^{\times }}}$ .

[25]

Natural signals often have some degree of smoothness, which makes them sparse in the wavelet domain. There are far fewer significant components in the wavelet domain in this example than there are in the time domain, and most of the significant components are towards the coarser coefficients on the left. Hence, natural signals are compressible in the wavelet domain.

The wavelet transform is a multiresolution, bandpass representation of a signal. This can be seen directly from the filterbank definition of the discrete wavelet transform given in this article. For a signal of length $2^{N}$ , the coefficients in the range $[2^{N-j},2^{N-j+1}]$ represent a version of the original signal which is in the pass-band $\left[{\frac {\pi }{2^{j}}},{\frac {\pi }{2^{j-1}}}\right]$ . This is why zooming in on these ranges of the wavelet coefficients looks so similar in structure to the original signal. Ranges which are closer to the left (larger $j$ in the above notation), are coarser representations of the signal, while ranges to the right represent finer details.

Discrete wavelet transform

Applications[edit]

Definition[edit]

One level of the transform[edit]

Relationship to the mother wavelet[edit]

Adam7 algorithm

[25]

Discrete cosine transform

Wavelet

Wavelet transform

Wavelet compression

List of wavelet-related transforms

WaveLab

libdwt

Concise Introduction to Wavelets