World Library  
Flag as Inappropriate
Email this Article

Cohen-Daubechies-Feauveau wavelet

Article Id: WHEBN0002634678
Reproduction Date:

Title: Cohen-Daubechies-Feauveau wavelet  
Author: World Heritage Encyclopedia
Language: English
Subject: JPEG 2000, Biorthogonal wavelets, CDF, Daubechies wavelet, Progressive Graphics File
Collection: Biorthogonal Wavelets
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Cohen-Daubechies-Feauveau wavelet

An example of the 2D wavelet transform that is used in JPEG2000

Cohen-Daubechies-Feauveau wavelet are the historically first family of biorthogonal wavelets, which was made popular by Ingrid Daubechies.[1][2] These are not the same as the orthogonal Daubechies wavelets, and also not very similar in shape and properties. However their construction idea is the same.

The JPEG 2000 compression standard uses the biorthogonal CDF 5/3 wavelet (also called the LeGall 5/3 wavelet) for lossless compression and a CDF 9/7 wavelet for lossy compression.

Contents

  • Properties 1
  • Construction 2
  • Tables of coefficients 3
  • Numbering 4
  • Lifting decomposition 5
    • Even number of smoothness factors 5.1
    • Odd number of smoothness factors 5.2
  • Applications 6
  • External links 7
  • References 8

Properties

  • The primal generator is a B-spline if the simple factorization q_{\mathrm{prim}}(X)=1 (see below) is chosen
  • The dual generator has the maximum number of smoothness factors which is possible for its length.
  • All generators and wavelets in this family are symmetric.

Construction

For every positive integer A there exists a unique polynomial Q_A(X) of degree A − 1 satisfying the identity

\left(1 - \frac{X}{2}\right)^A\,Q_A(X) + \left(\frac{X}{2}\right)^A\,Q_A(2 - X) = 1.

This is the same polynomial as used in the construction of the Daubechies wavelets. But, instead of a spectral factorization, here we try to factor

Q_A(X) = q_{\mathrm{prim}}(X)\,q_{\mathrm{dual}}(X),

where the factors are polynomials with real coefficients and constant coefficient 1. Then,

a_{\mathrm{prim}}(Z) = 2Z^d\,\left(\frac{1 + Z}2\right)^A\,q_{\mathrm{prim}}\left(1 - \frac{Z + Z^{-1}}{2}\right)

and

a_{\mathrm{dual}}(Z) = 2Z^d\,\left(\frac{1 + Z}2\right)^A\,q_{\mathrm{dual}}\left(1 - \frac{Z + Z^{-1}}{2}\right)

form a biorthogonal pair of scaling sequences. d is some integer used to center the symmetric sequences at zero or to make the corresponding discrete filters causal.

Depending on the roots of Q_A(X), there may be up to 2^{A-1} different factorizations. A simple factorization is q_{\mathrm{prim}}(X) = 1 and q_{\mathrm{dual}}(X) = Q_A(X), then the \mathrm{primary} scaling function is the B-spline of order A − 1. For A = 1 one obtains the orthogonal Haar wavelet.

Tables of coefficients

Cohen-Daubechies-Feauveau wavelet 5/3 used in JPEG 2000 standard.

For A=2 one obtains in this way the LeGall 5/3-wavelet:

A QA(X) qprim(X) qdual(X) aprim(Z) adual(Z)
2 1 + X 1 1 + X \frac12(1+Z)^2\,Z \frac12(1+Z)^2\,\left(-\frac12 + 2\,Z - \frac12\,Z^2\right)

For A=4 one obtains the 9/7-CDF-wavelet. One gets Q_4(X)=1 + 2\,X + 5/2\,X^2 + 5/2\,X^3, this polynomial has exactly one real root, thus it is the product of a linear factor 1-c\,X and a quadratic factor. The coefficient c, which is the inverse of the root, has an approximate value of −1.4603482098.

A QA(X) qprim(X) qdual(X)
4 1 + 2\,X + 5/2\,X^2 + 5/2\,X^3 1-c\,X 1 + (c + 2)*\,X + (c^2 + 2*c + 5/2)\,X^2

For the coefficients of the centered scaling and wavelet sequences one gets numerical values in an implementation–friendly form

k Analysis lowpass filter (1/2 adual) Analysis highpass filter (bdual) Synthesis lowpass filter (aprim) Synthesis highpass filter

(1/2 bprim)

−4 0.026748757411 0 0 0.026748757411
−3 −0.016864118443 0.091271763114 −0.091271763114 0.016864118443
−2 −0.078223266529 −0.057543526229 −0.057543526229 −0.078223266529
−1 0.266864118443 −0.591271763114 0.591271763114 −0.266864118443
0 0.602949018236 1.11508705 1.11508705 0.602949018236
1 0.266864118443 −0.591271763114 0.591271763114 −0.266864118443
2 −0.078223266529 −0.057543526229 −0.057543526229 −0.078223266529
3 −0.016864118443 0.091271763114 −0.091271763114 0.016864118443
4 0.026748757411 0 0 0.026748757411

Numbering

There are two concurring numbering schemes for wavelets of the CDF family.

  • the number of smoothness factors of the lowpass filters, or equivalently the number of vanishing moments of the highpass filters, e.g. 2,2
  • the sizes of the lowpass filters, or equivalently the sizes of the highpass filters, e.g. 5,3

The first numbering was used in Daubechies' book Ten lectures on wavelets. Neither of this numbering is unique. The number of vanishing moments does not tell about the chosen factorization. A filterbank with filter sizes 7 and 9 can have 6 and 2 vanishing moments when using the trivial factorization, or 4 and 4 vanishing moments as it is the case for the JPEG 2000 wavelet. The same wavelet may therefore be referred to as "CDF 9/7" (based on the filter sizes) or "biorthogonal 4.4" (based on the vanishing moments).

Lifting decomposition

For the trivially factorized filterbanks a lifting decomposition can be explicitly given.[3]

Even number of smoothness factors

Let n be the number of smoothness factors in the B-spline lowpass filter, which shall be even.

Then define recursively

\begin{align} a_0 &= \frac{1}{n} \\ a_m &= \frac{1}{(n^2 - 4\cdot m^2)\cdot a_{m - 1}} \end{align}

The lifting filters are

s_{m}(z) = a_m\cdot(2\cdot m + 1)\cdot(1 + z^{(-1)^m})

Conclusively the interim results of the lifting are

\begin{align} x_{-1}(z) &= z \\ x_{0}(z) &= 1 \\ x_{m + 1}(z) &= x_{m - 1}(z) + a_m\cdot(2\cdot m + 1)\cdot(z + z^{-1}) \cdot z^{(-1)^m} \cdot x_{m}(z) \end{align}

which leads to

x_{n/2}(z) = 2^{-n/2} \cdot (1 + z)^n \cdot z^{n/2 \bmod 2 - n/2}

The filters x_{n/2} and x_{n/2-1} constitute the CDF-n,0 filterbank.

Odd number of smoothness factors

Now, let n be odd.

Then define recursively

\begin{align} a_0 &= \frac{1}{n} \\ a_m &= \frac{1}{(n^2 - (2\cdot m - 1)^2)\cdot a_{m - 1}} \end{align}

The lifting filters are

s_{m}(z) = a_m\cdot((2\cdot m + 1) + (2\cdot m - 1)\cdot z) / z^{m \bmod 2}

Conclusively the interim results of the lifting are

\begin{align} x_{-1}(z) &= z \\ x_{0}(z) &= 1 \\ x_{1}(z) &= x_{-1}(z) + a_0\cdot x_0(z) \\ x_{m + 1}(z) &= x_{m - 1}(z) + a_m\cdot((2\cdot m + 1)\cdot z + (2\cdot m - 1)\cdot z^{-1}) \cdot z^{(-1)^m} \cdot x_{m}(z) \end{align}

which leads to

x_{(n + 1)/2}(z) \sim (1 + z)^n

where we neglect the translation and the constant factor.

The filters x_{(n + 1)/2} and x_{(n - 1)/2} constitute the CDF-n,1 filterbank.

Applications

The Cohen-Daubechies-Feauveau wavelet and other biorthogonal wavelets have been used to compress fingerprint scans for the FBI.[4] A standard for compressing fingerprints in this way was developed by Tom Hopper (FBI), Jonathan Bradley (Los Alamos National Laboratory) and Chris Brislawn (Los Alamos National Laboratory).[4] By using wavelets, a compression ratio of around 20 to 1 can be achieved, meaning a 10MB image could be reduced to as little as 500KB while still passing recognition tests.[4]

External links

  • JPEG 2000: How does it work?
  • Fast discrete CDF 9/7 wavelet transform source code in C language (lifting implementation) at the Wayback Machine (archived March 5, 2012)
  • CDF 9/7 Wavelet Transform for 2D Signals via Lifting: Source code in Python

References

  1. ^ Cohen, A.; Daubechies, I.; Feauveau, J. -C. (1992). "Biorthogonal bases of compactly supported wavelets". Communications on Pure and Applied Mathematics 45 (5): 485–560.  
  2. ^ Daubechies, Ingrid (1992). Ten Lectures on wavelets. SIAM. 
  3. ^ Thielemann, Henning (2006). "section 3.2.4". Optimally matched wavelets (PhD thesis). 
  4. ^ a b c Cipra, Barry (1994). What's Happening in the Mathematical Sciences (Vol.2) Parlez-vous Wavelets?. American Mathematical Society. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.