In numerical analysis and functional analysis, a discrete wavelet transform
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.
Examples = Haar wavelets=
The first DWT was invented by Hungarian mathematician Alfréd Haar. For an input
represented by a list of numbers, the Haar wavelet transform may be considered
to 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,
which leads to differences and a final sum.
= Daubechies wavelets= 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.
= The Dual-Tree Complex Wavelet Transform=
The Dual-Tree Complex Wavelet Transform is a relatively recent enhancement to
the discrete wavelet transform, with important additional properties: It is
nearly shift invariant and directionally selective in two and higher dimensions.
It achieves this with a redundancy factor of only substantially lower than
the undecimated DWT. The multidimensional dual-tree ℂWT is
nonseparable but is based on a computationally efficient, separable
filter bank. = Others=
Other forms of discrete wavelet transform include the non- or
undecimated wavelet transform, the Newland transform. Wavelet packet
transforms are also related to the discrete wavelet transform. Complex
wavelet transform is another form. Properties
The Haar DWT illustrates the desirable properties of wavelets in general.
First, it can be performed in 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 an
alternative to the conventional Fast Fourier Transform.
= Time Issues= Due to the rate-change operators in the
filter bank, the discrete WT is not time-invariant but actually very
sensitive to the alignment of the signal in time. To address the time-varying
problem of wavelet transforms, Mallat and Zhong proposed a new algorithm for
wavelet representation of a signal, which is invariant to time shifts.
According to this algorithm, which is called a TI-DWT, only the scale
parameter is sampled along the dyadic sequence 2^j and the wavelet transform
is calculated for each point in time. Applications
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, in
digital communications and many others. It is shown that discrete wavelet
transform is successfully implemented as analog filter bank in biomedical signal
processing for design of low-power pacemakers and also in ultra-wideband
wireless communications. Comparison with Fourier transform
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:, a unit impulse.
The DFT has orthogonal basis: 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:
Wavelets have location – the wavelet corresponds to “left side” if its
coefficient is positive or “right side” if its coefficient is negative, while
the last two wavelets each have support on the left side or the right side.
Sinusoidal waves do not have location – they spread across the whole space – but
do have phase – the second and third waves are translations of each other,
corresponding to being 90° out of phase, like cosine and sine, of which these are
discrete versions. Decomposing the sequence with respect to
these bases yields: The DWT demonstrates the localization:
the term gives the average signal value, the places the signal in the left side
of the domain, and the 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
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 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, it has an error of
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 = One level of the transform=
The DWT of a signal is calculated by passing it through a series of filters.
First the samples are passed through a low pass filter with impulse response
resulting in a convolution of the two: The signal is also decomposed
simultaneously using a high-pass filter . The outputs giving the detail
coefficients and approximation coefficients. It is important that the
two filters are related to each other and they are known as a quadrature
mirror filter. 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 subsampled by 2. In the next
two formulas, the notation is the opposite: g- denotes high pass and h-
low pass as is Mallat's and the common notation:
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.
With the subsampling operator the above summation can be written more
concisely. However computing a complete convolution
with subsequent downsampling would waste computation time.
The Lifting scheme is an optimization where these two computations are
interleaved. = 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. 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 where is the number of
levels. For example a signal with 32 samples,
frequency range 0 to and 3 levels of decomposition, 4 output scales are
produced: Relationship to the Mother Wavelet
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 . In the case of the discrete wavelet transform, the mother wavelet is
shifted and scaled by powers of two where is the scale parameter and is
the shift parameter, both which are integers.
Recall that the wavelet coefficient of a signal is the projection of onto a
wavelet, and let be a signal of length . In the case of a child wavelet in the
discrete family above, Now fix at a particular scale, so that
is a function of only. In light of the above equation, can be viewed as a
convolution of with a dilated, reflected, and normalized version of the
mother wavelet, , sampled at the points . But this is precisely what the detail
coefficients give at level of the discrete wavelet transform. Therefore,
for an appropriate choice of and , 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 . As an example, consider the discrete
Haar wavelet, whose mother wavelet is . Then the dilated, reflected, and
normalized version of this wavelet is , which is, indeed, the highpass
decomposition filter for the discrete Haar wavelet transform
Time Complexity The filterbank implementation of the
Discrete Wavelet Transform takes only O(N) in certain cases, as compared to
O(N log N) for the fast Fourier transform.
Note that if and are both a constant length, then and each take O(N) time.
The wavelet filterbank does each of these two O(N) convolutions, then splits
the signal into two branches of size N/2. But it only recursively splits the
upper branch convolved with . This leads to the following recurrence relation
which leads to an O(N) time for the entire operation, as can be shown by a
geometric series expansion of the above relation.
As an example, the Discrete Haar Wavelet Transform is linear, since in that case
and are constant length 2. Other transforms
The Adam7 algorithm, used for interlacing in the Portable Network
Graphics 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. It thus offers worse frequency behavior, showing artifacts at
the early stages, in return for simpler implementation.
Code example In its simplest form, the DWT is
remarkably easy to compute. The Haar wavelet in Java:
Complete Java code for a 1-D and 2-D DWT using Haar, Daubechies, Coiflet, and
Legendre wavelets is available from the open source project: JWave. Furthermore,
a fast lifting implementation of the discrete biorthogonal CDF 9/7 wavelet
transform in C, used in the JPEG 2000 image compression standard can be found
here. = Example of Above Code=
This figure shows an example of applying the above code to compute the Haar
wavelet coefficients on a sound waveform. This example highlights two
key properties of the wavelet transform: 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 , the coefficients in the range represent a
version of the original signal which is in the pass-band . 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, are
coarser representations of the signal, while ranges to the right represent
finer details. See also
Wavelet Wavelet series
Wavelet compression List of wavelet-related transforms
Notes References