The fast wavelet transform is a
mathematicalalgorithm 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 transform can be easily extended to multidimensional signals, such as images, where the time domain is replaced with the space domain. This algorithm was introduced in 1989 by
Stéphane Mallat.[1]
It has as theoretical foundation the device of a finitely generated, orthogonal
multiresolution analysis (MRA). In the terms given there, one selects a sampling scale J with
sampling rate of 2J per unit interval, and projects the given signal f onto the space ; in theory by computing the
scalar products
where is the
scaling function of the chosen wavelet transform; in practice by any suitable sampling procedure under the condition that the signal is highly oversampled, so
is the
orthogonal projection or at least some good approximation of the original signal in .
(some coefficients might be zero). Those allow to compute the wavelet coefficients , at least some range k=M,...,J-1, without having to approximate the integrals in the corresponding scalar products. Instead, one can directly, with the help of convolution and decimation operators, compute those coefficients from the first approximation .
Forward DWT
For the
discrete wavelet transform (DWT),
one computes
recursively, starting with the coefficient sequence and counting down from k = J - 1 to some M < J,
or
and
or ,
for k=J-1,J-2,...,M and all . In the Z-transform notation:
The starred Laurent-polynomial denotes the
adjoint filter, it has time-reversed adjoint coefficients, . (The adjoint of a real number being the number itself, of a complex number its conjugate, of a real matrix the transposed matrix, of a complex matrix its hermitian adjoint).
Multiplication is polynomial multiplication, which is equivalent to the convolution of the coefficient sequences.
It follows that
is the orthogonal projection of the original signal f or at least of the first approximation onto the
subspace, that is, with sampling rate of 2k per unit interval. The difference to the first approximation is given by
where the difference or detail signals are computed from the detail coefficients as
with denoting the mother wavelet of the wavelet transform.
Inverse DWT
Given the coefficient sequence for some M < J and all the difference sequences , k = M,...,J − 1, one computes recursively
or
for k = J − 1,J − 2,...,M and all . In the Z-transform notation:
The
upsampling operator creates zero-filled holes inside a given sequence. That is, every second element of the resulting sequence is an element of the given sequence, every other second element is zero or . This linear operator is, in the
Hilbert space, the adjoint to the downsampling operator .
S.G. Mallat "A Theory for Multiresolution Signal Decomposition: The Wavelet Representation" IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 2, no. 7. July 1989.
I. Daubechies, Ten Lectures on Wavelets. SIAM, 1992.
A.N. Akansu Multiplierless Suboptimal PR-QMF Design Proc. SPIE 1818, Visual Communications and Image Processing, p. 723, November, 1992