- Fast wavelet transform
The Fast Wavelet Transform is a mathematical
algorithm designed to turn awaveform or signal in thetime domain into asequence of coefficients based on anorthogonal basis of small finite waves, orwavelets . The transform can be easily extended to multidimensional signals, such as images, where the time domain is replaced with the space domain.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" withsampling rate of 2J per unit interval, and projects the given signal "f" onto the space V_J; in theory by computing the scalar products:s^{(J)}_n:=2^J langle f(t),phi(2^J t-n) angle,
where phi is the "scaling function" of the chosen wavelet transform; in praxis by any suitable sampling procedure under the condition, that the signal is highly oversampled, so:P_J [f] (x):=sum_{nin} s^{(J)}_n,phi(2^Jx-n)is the
orthogonal projection or at least some good approximation of the original signal in V_J.The MRA is characterised by its scaling sequence
:a=(a_{-N},dots,a_0,dots,a_N) or, as
Z-transform , a(Z)=sum_{n=-N}^Na_nZ^nand its wavelet sequence
:b=(b_{-N},dots,b_0,dots,b_N) or b(Z)=sum_{n=-N}^Nb_nZ^n
(some coefficients might be zero). Those allow to compute the wavelet coefficients d^{(k)}_n, 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 s^{(J)}.
Forward DWT
One computes recursively, starting with the coefficient sequence s^{(J)} and counting down from "k=J-1" down to some "M
:s^{(k)}_n:=frac12 sum_{m=-N}^N a_m s^{(k+1)}_{2n+m} or s^{(k)}(Z):=(downarrow 2)(a^*(Z)cdot s^{(k+1)}(Z))and :d^{(k)}_n:=frac12 sum_{m=-N}^N b_m s^{(k+1)}_{2n+m} or d^{(k)}(Z):=(downarrow 2)(b^*(Z)cdot s^{(k+1)}(Z)), for "k=J-1,J-2,...,M" and all nin. In the Z-transform notation::* The downsampling operator downarrow 2) reduces an infinite sequence, given by its
Z-transform , which is simply aLaurent series , to the sequence of the coefficients with even indices, downarrow 2)(c(Z))=sum_{kin}c_{2k}Z^k. :* The starred Laurent-polynomial a^*(Z) denotes the adjoint filter, it has "time-reversed" adjoint coefficients, a^*(Z)=sum_{-N}^N a_n^*Z^{-n}. (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
:P_k [f] (x):=sum_{nin} s^{(k)}_n,phi(2^kx-n)
is the orthogonal projection of the original signal "f" or at least of the first approximation P_J [f] (x) onto the
subspace V_k, that is, with sampling rate of 2k per unit interval. The difference to the first approximation is given by:P_J [f] (x)=P_k [f] (x)+D_k [f] (x)+dots+D_{J-1} [f] (x),
where the difference or detail signals are computed from the detail coefficients as
:D_k [f] (x):=sum_{nin} d^{(k)}_n,psi(2^kx-n),
with psi denoting the "mother wavelet" of the wavelet transform.
Inverse DWT
Given the coefficient sequence s^{(M)} for some "M
d^{(k)}, "k=M,...,J-1", one computes recursively:s^{(k+1)}_n:=sum_{k=-N}^N a_k s^{(k)}_{2n-k}+sum_{k=-N}^N b_k d^{(k)}_{2n-k} or s^{(k+1)}(Z)=a(Z)cdot(uparrow 2)(s^{(k)}(Z))+b(Z)cdot(uparrow 2)(d^{(k)}(Z))for "k=J-1,J-2,...,M" and all nin. In the Z-transform notation::* The upsampling operator uparrow 2) 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 uparrow 2)(c(Z)):=sum_{nin}c_nZ^{2n}. This linear operator is, in the Hilbert space ell^2(,R), the adjoint to the downsampling operator downarrow 2).ee also
*
Lifting scheme References
Wikimedia Foundation. 2010.