Daubechies wavelet

Under Daubechies wavelets, named after Ingrid Daubechies, one understands in digital signal processing, a class of orthogonal wavelet functions that have compact support. They are among the most practically used wavelet transformations for the purpose of digital signal analysis and signal compression. Due to their simple implementability means of fast wavelet transform ( FWT ), they are also teaching ( book ) examples of digital signal processing.

• 3.1 Vanishing moments and polynomial approximation
• 3.2 smoothness of the functions
• 3.3 Examples

• 4.1 Orthogonal Wavelets
• 4.2 biorthogonal symmetric wavelets

Description

For the purposes of functional analysis generates the wavelet, together with its integer shifts, and the compressions / dilations of these functions by powers of two as a factor, an orthonormal basis of the Hilbert space L ² (IR), that is, every square integrable function can be decomposed into parts that look similar to the wavelet function. Since 1909, the Haar wavelet, a piecewise constant function, known with this property. It was the merit of I. Daubechies, to have constructed the first is a continuous function with these properties.

There are two finite sequences of real numbers, which can be used as a digital low pass and high pass filters in a filter bank that is part of the FWT for each wavelet. The length N of the filter, also referred to as the number of taps, is part of the description of each DN Daubechies wavelets. In practice, usually the Daubechies wavelets, named D2 -D20 are used. On theoretical grounds only just N = 2A occur. Each wavelet in this class has the maximum number of vanishing moments of A ( in engl. Literature " vanishing moments" ), that is, the wavelet is orthogonal (in the sense of L ² (IR), ie the integral of the product of both functions is zero) for each polynomial of degree at most A-1. For example, D2 ( the Haar wavelet ) and a vanishing moment is perpendicular to all of constant functions, D4 has two such memories, and is perpendicular to all of the linear functions, etc. The number of vanishing moments A is a measure of the quality of a scaling function.

From I. Daubechies biorthogonal wavelets also a class was introduced with similar characteristics. The orthogonality of the generating functions against symmetry is exchanged.

Algebraic conditions

The scaling function in each multi-scale analysis is solution of a fractal functional equation, the refinement equation or two- scale equation is called:

The finite sequence of real numbers scaling sequence or mask is called. The wavelet function is obtained in a similar way as a linear combination

Is called with a suitable finite sequence of real numbers that Waveletfolge or mask.

Is the existence of a continuous solution of the refinement equation is known, then an arbitrarily accurate approximation of these are found by setting up the finite-dimensional linear system of equations, which must comply with the values ​​of the scaling function at integer points. Since this equation system is homogeneous, one adds the condition that the sum of these values ​​will be 1. From the values ​​of the integer points then the values ​​for the multiples of 1 /2, can be found from these values ​​to multiples of 1 /4, etc. by simply inserting. The same applies to the values ​​of the wavelet. In this way, the above graphs were generated.

Orthogonal wavelets

This class of wavelets has the property that the scaling function form, together with its integer shifts, combined with the wavelet function with its integer shifts an orthonormal system in the Hilbert space L ² (IR). It is necessary for this orthogonality that the scaling sequence to all even-numbered shifts perpendicular to their own:

In the orthogonal case, the coefficients of the Waveletfolge arise directly from the coefficients of the scaling sequence after

Sometimes one finds the opposite sign in the literature.

Biorthogonal wavelets

The second, introduced by I. Daubechies together with A. Cohen and Feauveau class are the biorthogonal wavelets. Although these do not have the above-mentioned orthogonality, soft but of this only slightly from. It can be constructed such that the scaling function and the symmetric wavelet is also symmetric or antisymmetric. Here, however, not enough for a pair of generating functions, but it needs two scaling functions, which may create different multi-scale analysis, and accordingly, two different wavelet. The two scaling sequences must now meet for all integer m, the following Biorthogonalitätsbedingung:

If this is fulfilled, the Waveletfolgen arise as

Where N is the length of the scaling sequence to M and the length of the scaling result to be.

The JPEG 2000 standard used for image compression and the biorthogonal Daubechies-5/3-Wavelet (also known as LeGall-5/3-Wavelet ) for lossless and Daubechies-9/7-Wavelet (also known as Cohen- Daubechies 9 Feauveau / 7 or " CDF 9/7 " or FBI fingerprint - known wavelet ) for lossy compression.

Analytical conditions

Vanishing moments and polynomial approximation

A necessary condition for the existence of an r-times continuously differentiable solution ( r = 0 for only continuous) of the refinement equation is that the polynomial (1 Z) r 1 divides the generating function or Z-transform of the scaling sequence a. A maximum power, so that (1 Z) a is a factor of a ( Z), means of approximation polynomial. It indicates the ability of the scaling function, represent polynomials up to degree A-1 as a linear combination of integer shifts of the scaling function.

• In the biorthogonal case results in a order of approximation A of an equal number A of vanishing moments of the dual wavelets, which it follows that (1 Z) A is a factor of is. Conversely, the order of approximation is equal to the number of à à of vanishing moments of the wavelet.
• In the orthogonal case, tune A and Ã, respectively, as is also and.

Smoothness of the functions

A criterion for the solvability of the refinement equation is the following: we factorization p is a polynomial in Z with p (1 ) = 1, and there is a barrier of the type

Then the refinement equation has a r-times continuously differentiable solution with support in the interval [ 0, N -1], where N = A deg ( p) 1.

Examples

• , To which a constant P (z) = 1 belongs. According to the above must apply n < A-1, that is, the solutions would be at least A-2- times continuously differentiable. In fact, the solutions are but just Schoenberg's B -splines of order A-1, which have a piecewise (A-1 ) th derivative constant, in particular the (A-2 )-th derivative is Lipschitz continuous. The case A = 1, the herrausfällt from this treatment is equal to the index function, and the unit interval, the scaling function of Haar wavelets.
• In the case A = 2 and p is linear, you can start. We determine the Monomkoeffizienten this 3rd order polynomial and implement these four coefficients in the orthogonal condition one, so remains at the end exactly the condition c ² = 3 Substituting the positive root in C, then we obtain the scaling result of the D4 wavelets, see also the table below.

Construction

The Daubechies wavelets correspond to the case of minimum degrees of freedom in determining the scaling effects. On one hand, the minimum length of the N scale sequence are searched for a given number of A Verschwindungsmomenten, on the other hand the maximum number of Verschwindungsmomenten at a given length. In both cases, N = 2A.

Orthogonal wavelets

We use the above factorization scaling result, with p (1) = 1, the orthogonality may also be combined in a Laurent polynomial:

With the abbreviation. This equation is derived from that deg p < A-1 can not work, so at least deg p = A-1 applies, resulting in minimal N = 2 case follows.

We can be multiplied by the inverse power series and break off at the power,

This equation is solvable, their solutions result from a method, the spectral factorization is called. First, the zeros of the right-hand side are determined as a polynomial in u. From this result A - Z 1 quadratic equations with mutually reciprocal solutions, one of which is p ( Z ) is assigned. Thus, 2A-1 possible solutions arise, one can for example decide that, in all the zeros of p ( Z) inside or all outside the unit circle.

In the following table are the resulting consequences for the scaling wavelets D2 -D20, that is, for A = 1 to A = 10 are listed.

The wavelet coefficients can be derived by the order and the sign of every other coefficient is inverted. For D4, this would be, for example, -0.1830127, -0.3169873, 1.1830127, -0.6830127.

Biorthogonal symmetric wavelets

Closely related to the Daubechies wavelets are the Cohen- Daubechies wavelets Feauveau ( CDF wavelets). In contrast to the Daubechies wavelets latter, however, are only pairwise orthogonal ( biorthogonal ), but symmetrical.

CDF wavelets gained notoriety because they are used in the JPEG -2000 standard. Furthermore, the wavelet, which is used in the fingerprint database of the FBI, a CDF wavelet.