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 some given support. With each wavelet type of this class, there is a scaling function (also called father wavelet) which generates an orthogonal multiresolution analysis. Image File history File links Please see the file description page for further information. ... Image File history File links Please see the file description page for further information. ... Ingrid Daubechies (born August 17, 1954) is a Belgian physicist and mathematician. ... An orthogonal wavelet is a wavelet where the associated wavelet transform is orthogonal. ... In numerical analysis and functional analysis, a discrete wavelet transform (DWT) is any wavelet transform for which the wavelets are discretely sampled. ... -1...

Properties

In general the Daubechies wavelets are chosen to have the highest number A of vanishing moments, (this does not imply the best smoothness) for given support width N=2A, and among the 2^A−1 possible solutions the one is chosen whose scaling filter has extremal phase. The wavelet transform is also easy to put into practice using the fast wavelet transform. Daubechies wavelets are widely used in solving a broad range of problems, e.g. self-similarity properties of a signal or fractal problems, signal discontinuities, etc. The Fast (Lifting) 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 boundary of the Mandelbrot set is a famous example of a fractal. ...

The Daubechies wavelets are not defined in terms of the resulting scaling and wavelet functions; in fact, they are not possible to write down on closed form. The graphs below are generated using the cascade algorithm, a numeric technique consisting of simply inverse-transforming [1 0 0 0 0 ... ] an appropriate number of times. The cascade algorithm is an interesting numerical method for calculating the basic scaling function or wavelets uses an iterative algorithm, which computes wavelet coefficients at one scale from those at another. ...

scaling and wavelet functions
amplitudes of the frequency spectrum

Note that the spectrums shown here are not the frequency response of the high and low pass filters, but rather the response of the socalled iterated filters obtained by filtering the low pass filter with itself (blue) and with the high pass filter (red). The frequency response for the remaining two iterated filters, i.e. high pass filtered by low and high pass, are not shown here. Image File history File links Please see the file description page for further information. ... Image File history File links Please see the file description page for further information. ... Image File history File links Please see the file description page for further information. ... Image File history File links Please see the file description page for further information. ... Image File history File links Please see the file description page for further information. ... Image File history File links Please see the file description page for further information. ...

Daubechies orthogonal wavelets D2-D20 (even index numbers only) are commonly used. The index number refers to the number N of coefficients. Each wavelet has a number of zero moments or vanishing moments equal to half the number of coefficients. For example, D2 (the Haar wavelet) has one vanishing moment, D4 has two, etc. A vanishing moment limits the wavelet's ability to represent polynomial behaviour or information in a signal. For example, D2, with one moment, easily encodes polynomials of one coefficient, or constant signal components. D4 encodes polynomials with two coefficients, i.e. constant and linear signal components; and D6 encodes 3-polynomials, i.e. constant, linear and quadratic signal components. The Haar wavelet The Haar wavelet is the first known wavelet and was proposed in 1909 by Alfred Haar. ... In mathematics, a polynomial is an expression that is constructed from one or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ... f(x) = x2 - x - 2 In mathematics, a quadratic function is a polynomial function of the form , where a is nonzero. ...

Construction

Both the scaling sequence (Low-Pass Filter) and the wavelet sequence (Band-Pass Filter) (see orthogonal wavelet for details of this construction) will here be normalized to have sum equal 2 and sum of squares equal 2. In some applications, they are normalised to have sum , so that both sequences and all shifts of them by an even number of coefficients are orthonormal to each other. An orthogonal wavelet is a wavelet where the associated wavelet transform is orthogonal. ...

Using the general representation for a scaling sequence of an orthogonal discrete wavelet transform with approximation order A,

, with N=2A, p having real coefficients, p(1)=1 and degree(p)=A-1,

one can write the orthogonality condition as

, or equally as (*),

with the Laurent-polynomial generating all symmetric sequences and X( − Z) = 2 − X(Z). Further, P(X) stands for the symmetric Laurent-polynomial P(X(Z)) = p(Z)p(Z ^{− 1}). Since X(e^iw) = 1 − cos(w) and p(e^iw)p(e ^{− iw}) = | p(e^iw) | ², P takes nonnegative values on the segment [0,2].

Equation (*) has one minimal solution for each A, which can be obtained by division in the ring of truncated power series in X,

.

Obviously, this has positive values on (0,2)

The homogeneous equation for (*) is antisymmetric about X=1 and has thus the general solution X^A(X − 1)R((X − 1)²), with R some polynomial with real coefficients. That the sum

P(X) = P_A(X) + X^A(X − 1)R((X − 1)²)

shall be nonnegative on the interval [0,2] translates into a set of linear restrictions on the coefficients of R. The values of P on the interval [0,2] are bounded by some quantity 4^{A − r}, maximizing r results in a linear program with infinitely many inequality conditions.

To solve P(X(Z)) = p(Z)p(Z ^{− 1}) for p one uses a technique called spectral factorization resp. Fejer-Riesz-algorithm. The polynomial P(X) splits into linear factors , N=A+1+2deg(R). Each linear factor represents a Laurent-polynomial that can be factored into two linear factors. One can assign either one of the two linear factors to p(Z), thus one obtains 2^N possible solutions. For extremal phase one chooses the one that has all complex roots of p(Z) inside or on the unit circle and is thus real.

Below are the coefficients for the scaling functions for D2-20. The wavelet coefficients are derived by reversing the order of the scaling function coefficients and then reversing the sign of every second one, (ie. D4 wavelet = {-0.1830127, -0.3169873, 1.1830127, -0.6830127}) Mathematically, this looks like b_k = ( − 1)^ka_{N − 1 − k} where k is the coefficient index, b is a coefficient of the wavelet sequence and a a coefficient of the scaling sequence. N is the wavelet index, ie 2 for D2.

Parts of the construction are also used to derive the biorthogonal Cohen-Daubechies-Feauveau wavelets (CDFs). The Haar wavelet The Haar wavelet is the first known wavelet and was proposed in 1909 by Alfred Haar. ... The historically first family of biorthogonal wavelets, which was made popular by Ingrid Daubechies. ...

Implementation

Here are two, very concise, examples of implementing a Daubechies wavelet transform in Matlab (in this case, Daubechies 4). This implementation use periodization to handle the problem of finite length signals. Other more sophisticated methods are available, but often it is not necessary to use these, as it only affects the very ends of the transformed signal. The periodization is accomplished in the forward transform directly in Matlab vector notation, and the inverse transform by using the cpv() function: MATLAB is a numerical computing environment and programming language. ...

Transform, D4

 s1 = S(1:2:N-1) + sqrt(3)*S(2:2:N); d1 = S(2:2:N) - sqrt(3)/4*s1 - (sqrt(3)-2)/4*[s1(N/2) s1(1:N/2-1)]; s2 = s1 - [d1(2:N/2) d1(1)]; s = (sqrt(3)-1)/sqrt(2) * s2; d = (sqrt(3)+1)/sqrt(2) * d1; 

Inverse transform, D4

 d1 = d / ((sqrt(3)+1)/sqrt(2)); s2 = s / ((sqrt(3)-1)/sqrt(2)); s1 = s2 + cpv(d1,1); S(2:2:N) = d1 + sqrt(3)/4*s1 + (sqrt(3)-2)/4*cpv(s1,-1); S(1:2:N-1) = s1 - sqrt(3)*S(2:2:N); 

cpv() refers to the cyclic permutation of a vector, a non-standard Matlab function (Jensen & la Cour-Harbo, 2001):

 function P = cpv(S, k) if k > 0 P = [S(k+1:end) S(1:k)]; elseif k < 0 P = [S(end+k+1:end) S(1:end+k)]; end 

See also

• Fast wavelet transform

The Fast (Lifting) 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. ...

References

• Jensen; la Cour-Harbo (2001). Ripples in Mathematics. Berlin: Springer, 157-160. ISBN 3-540-41662-5. 

External links

• Ingrid Daubechies: Ten Lectures on Wavelets, SIAM 1992,
• Carlos Cabrelli, Ursula Molter: Generalized Self-similarity", Journal of Mathematical Analysis and Applications, 230: 251 - 260, 1999.

• Hardware implementation of wavelets