Fast wavelet transform

Fast wavelet transform

The Fast 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 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" with sampling 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^n

and 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 a Laurent 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 "Md^{(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.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Fast Fourier transform — A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex number arithmetic to group …   Wikipedia

  • Discrete wavelet transform — An example of the 2D discrete wavelet transform that is used in JPEG2000. The original image is high pass filtered, yielding the three large images, each describing local changes in brightness (details) in the original image. It is then low pass… …   Wikipedia

  • Continuous wavelet transform — of frequency breakdown signal. Used symlet with 5 vanishing moments. A continuous wavelet transform (CWT) is used to divide a continuous time function into wavelets. Unlike Fourier transform, the continuous wavelet transform possesses the ability …   Wikipedia

  • Harmonic wavelet transform — In the mathematics of signal processing, the harmonic wavelet transform, introduced by David Edward Newland in 1993, is a wavelet based linear transformation of a given function into a time frequency representation. It combines advantages of the… …   Wikipedia

  • Wavelet — A wavelet is a mathematical function used to divide a given function or continuous time signal into different frequency components and study each component with a resolution that matches its scale. A wavelet transform is the representation of a… …   Wikipedia

  • Wavelet-Transformation — Mit Wavelet Transformation (WT, engl. wavelet transform) wird eine bestimmte Familie von linearen Zeit Frequenz Transformationen in der Mathematik und den Ingenieurwissenschaften (primär: Nachrichtentechnik, Informatik) bezeichnet. Die WT setzt… …   Deutsch Wikipedia

  • Daubechies wavelet — Daubechies 20 2 d wavelet (Wavelet Fn X Scaling Fn) Named after Ingrid Daubechies, the Daubechies wavelets are a family of orthogonal wavelets defining a discrete wavelet transform and characterized by a maximal number of vanishing moments for… …   Wikipedia

  • List of wavelet-related transforms — A list of wavelet related transforms:* Continuous wavelet transform (CWT) * Multiresolution analysis (MRA) * Discrete wavelet transform (DWT) * Fast wavelet transform (FWT) * Complex wavelet transform * Non or undecimated wavelet transform, the… …   Wikipedia

  • Diskrete Wavelet-Transformation — Mit Wavelet Transformation (WT, engl. wavelet transform) wird eine bestimmte Familie von linearen Zeit Frequenz Transformationen in der Mathematik und den Ingenieurswissenschaften (primär: Nachrichtentechnik, Informatik) bezeichnet. Die WT setzt… …   Deutsch Wikipedia

  • Kontiniuierliche Wavelet-Transformation — Mit Wavelet Transformation (WT, engl. wavelet transform) wird eine bestimmte Familie von linearen Zeit Frequenz Transformationen in der Mathematik und den Ingenieurswissenschaften (primär: Nachrichtentechnik, Informatik) bezeichnet. Die WT setzt… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”