Advertisement

Daubechies wavelet

From Academic Kids

Missing image
Daubechies20LowPassHighPass2DFilter.png
Daubechies 20 2-d wavelet (Wavelet Fn X Scaling Fn)

Named after Ingrid Daubechies, the orthogonal Daubechies wavelets are a class of wavelets 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.

Contents

Orthogonal wavelets

The scaling function is a solution to a fractal functional equation, mostly called refinement equation:

<math>\phi(x)=\sum_{k=0}^{N-1} a_k\phi(2x-k)<math>,

where the sequence <math>(a_0,\dots, a_{N-1})<math> of real numbers is called scaling sequence or scaling mask. The wavelet proper is obtained by a similar linear combination,

<math>\psi(x)=\sum_{k=0}^{M-1} b_k\phi(2x-k)<math>,

where the sequence <math>(b_0,\dots, b_{M-1})<math> of real numbers is called wavelet sequence or wavelet mask.

A necessary condition for the orthogonality of the wavelets is, that the scaling sequence is orthogonal to any shifts of it by an even number of coefficients:

<math>\sum_{n\in\Z} a_n a_{n+2m}=2\delta_{m,0}<math>

In this case there is the same number M=N of coefficients in the scaling as in the wavelet sequence, the wavelet sequence can be determined as <math>b_n=(-1)^n a_{N-1-n}<math>. In some cases the opposite sign is chosen.

Biorthogonal wavelets

Another class of wavelets made popular by I. Daubechies are the biorthogonal wavelets. As the name suggests, they are not orthogonal, but they can be constructed to have temporal symmetry. In this case, there are two scaling functions <math>\phi,\tilde\phi<math>, which may generate different multiresolution analyses, and accordingly two different wavelet functions <math>\phi,\tilde\phi<math>. So the numbers M, N of coefficients in the scaling sequences <math>a,\tilde a<math> may differ. The scaling sequences must satisfy the following biorthogonality condition

<math>\sum_{n\in\Z} a_n \tilde a_{n+2m}=2\delta_{m,0}<math>.

Then the wavelet sequences can be determined as <math>b_n=(-1)^n \tilde a_{M-1-n}<math>, n=0,...,M-1 and <math>\tilde b_n=(-1)^n a_{M-1-n}<math>, n=0,....,N-1.

The JPEG 2000 compression standard uses the biorthogonal Daubechies M/N=5/3 wavelet (also called the LeGall 5/3 wavelet) for lossless compression and the Daubechies 9/7 (also known as the Cohen-Daubechies-Feauveau 9/7 or the "CDF 9/7") for lossy compression.

Vanishing moments, polynomial approximation and smoothness

A sufficient condition for the existence of a solution to the refinement equation is, that some power (1+Z)A, A>0, divides the polynomial <math>a(Z):=a_0+a_1Z+\dots+a_{N-1}Z^{N-1}<math> (see Z-transform). The maximally possible power A is called polynomial approximation order (or pol. app. power) number of vanishing moments. It describes the ability to represent polynomials up to degree A-1 with linear combinations of integer translates of the scaling function. In the biorthogonal case, an approximation order A of <math>\phi<math> corresponds to A vanishing moments of the dual wavelet <math>\tilde\psi<math>, that is, the scalar products of <math>\tilde\psi<math> with any polynomial up to degree A-1 are zero. In the opposite direction, the approximation order of <math>\tilde\phi<math> is equivalent to vanishing moments of <math>\psi<math>. In the orthogonal case, A and coincide.

If one decomposes <math>a(Z)=2^{1-A}(1+Z)^Ap(Z)<math>, and the following estimate holds

<math>1\le\sup_{t\in[0,2\pi]}|p(e^{it})|<2^{A-1-n}<math> for some <math>n\in\N<math>,

then the refinement equation has a n times continuously differentiable solution with compact support.

Examples:

  • <math>a(Z)=2^{1-A}(1+Z)^A<math>, that is p(Z)=1, has n<A-1. The solutions are Schoenbergs B-splines of order A-1, where the (A-1)-th derivative is piecewise constant, thus the (A-2)-th is Lipschitz-continuous. A=1 corresponds to the index function of the unit interval.
  • A=2 and p linear may be written as <math>a(Z)=\frac14(1+Z)^2\,((1+Z)+c(1-Z))<math>. Expansion of this degree 3 polynomial and insertion of the 4 coefficients into the orthogonality condition results in c²=3. The positive root gives the scaling sequence of the D4-wavelet, see below.

Orthogonal wavelets with minimal support

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 2A-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-likely properties of a signal or fractal problem, signal discontinuities, etc.

scaling and wavelet functions Missing image
Daubechies4-functions.png


Missing image
Daubechies12-functions.png


Missing image
Daubechies20-functions.png


amplitudes of the frequency spectrum Missing image
Daubechies4-spectrum.png


Missing image
Daubechies12-spectrum.png


Missing image
Daubechies20-spectrum.png


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 moments, D4 has two moments, etc. A vanishing moment refers to the wavelets ability to represent polynomial behaviour or information in a signal. For example, D2, with one moment, easily encodes polynomials of one coefficient, ie. constant signal components. D4 encodes polynomials of two coefficients, ie constant and linear signal components, D6 encodes 3-polynomials, ie constant, linear and quadratic signal components.

Orthogonal wavelet coefficients

Both the scaling sequence (Low-Pass Filter) and the wavelet sequence (Band-Pass Filter) as used above must be normalized to have sum equal 2 and sum of squares equal 2. In some applications they must be renormalised by a factor <math>\frac{1}{\sqrt{2}} <math> to be orthonormal to each other and all shifts of both by an even number of coefficients. Using the above representation for the scaling sequence, <math>a(Z)=2^{1-A}(1+Z)^Ap(Z)<math>, with N=2A, p(1)=1 and degree(p)=A-1, one can write the orthogonality condition as

<math>a(Z)a(Z^{-1})+a(-Z)a(Z^{-1})=4<math>, ==> <math>(1-u)^A p(Z)p(Z^{-1})=1-u^A\,[p(-Z)p(-Z^{-1})]<math>

with <math>u:=1/4\cdot(2-Z-Z^{-1})<math>. Inversion of truncated power series in u and minimality of degree results in

<math>p(Z)p(Z^{-1})=\sum_{k=0}^{A-1}\left({{-A}\atop{k}}\right)u^k<math>.

To solve this last equation one uses a technique called spectral factorization, that is one decomposes the right side in linear factors in u, each linear factor is a symmetric quadratic factor in Z, one can assign either one of the two linear factors in Z to p(Z), thus one obtains 2A-1 possible solutions. One can choose the one that has all complex roots of p(Z) inside the unit circle.

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 <math>b_k = (-1)^{k} a_{N - 1 - k} <math> 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.

Orthogonal Daubechies coefficients
D2 (Haar) D4 D6 D8 D10 D12 D14 D16 D18 D20
1 0.6830127 0.47046721 0.32580343 0.22641898 0.15774243 0.11009943 0.07695562 0.05385035 0.03771716
1 1.1830127 1.14111692 1.01094572 0.85394354 0.69950381 0.56079128 0.44246725 0.34483430 0.26612218
0.3169873 0.650365 0.8922014 1.02432694 1.06226376 1.03114849 0.95548615 0.8553430 0.74557507
-0.1830127 -0.19093442 -0.03967503 0.19576696 0.44583132 0.66437248 0.82781653 0.92954571 0.97362811
-0.12083221 -0.26450717 -0.34265671 -0.31998660 -0.20351382 -0.02238574 0.18836955 0.39763774
0.0498175 0.0436163 -0.04560113 -0.18351806 -0.31683501 -0.40165863 -0.41475176 -0.35333620
0.0465036 0.10970265 0.13788809 0.1008467 6.68194092e-4 -0.13695355 -0.27710988
-0.01498699 -0.00882680 0.03892321 0.11400345 0.18207636 0.21006834 0.18012745
-0.01779187 -0.04466375 -0.05378245 -0.02456390 0.04345268 0.13160299
4.71742793e-3 7.83251152e-4 -0.02343994 -0.06235021 -0.09564726 -0.10096657
6.75606236e-3 0.01774979 0.01977216 3.54892813e-4 -0.04165925
-1.52353381e-3 6.07514995e-4 0.01236884 0.03162417 0.04696981
-2.54790472e-3 -6.88771926e-3 -6.67962023e-4 5.10043697e-3
5.00226853e-4 -5.54004549e-4 -6.05496058e-3 -0.01517900
9.55229711e-4 2.61296728e-3 1.97332536e-3
-1.66137261e-4 3.25814671e-4 2.81768659e-3
-3.56329759e-4 -9.69947840e-4
-5.5645514e-5 -1.64709006e-4
1.32354367e-4
-1.875841e-5

Biorthogonal symmetric wavelets with minimal support

9/7 Coefficients
k Low Pass High Pass
0 0.6029490182363579 1.115087052456994
+/-1 0.2668641184428723 -0.5912717631142470
+/-2 -0.07822326652898785 -0.05754352622849957
+/-3 -0.01686411844287495 0.09127176311424948
+/-4 0.026748741080976

See also

External links

  • Ingrid Daubechies: Ten Lectures on Wavelets, SIAM 1992,
  • Carlos Cabrelli, Ursula Molter (http://mate.dm.uba.ar/~umolter/pagina_grupo.html): Generalized Self-similarity", Journal of Mathematical Analysis and Applications, 230: 251 - 260, 1999.
Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools