Jump to content

Cohen–Daubechies–Feauveau wavelet

From Wikipedia, the free encyclopedia
An example of the 2D wavelet transform that is used in JPEG 2000

Cohen–Daubechies–Feauveau wavelets are a family of biorthogonal wavelets that 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 Le Gall–Tabatabai (LGT) 5/3 wavelet (developed by D. Le Gall and Ali J. Tabatabai)[3][4][5] for lossless compression and a CDF 9/7 wavelet for lossy compression.

Properties

[edit]
  • The primal generator is a B-spline if the simple factorization (see below) is chosen.
  • The dual generator has the highest possible number of smoothness factors for its length.
  • All generators and wavelets in this family are symmetric.

Construction

[edit]

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

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

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

and

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 , there may be up to different factorizations. A simple factorization is and , then the primary scaling function is the B-spline of order A − 1. For A = 1 one obtains the orthogonal Haar wavelet.

Tables of coefficients

[edit]
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

For A = 4 one obtains the 9/7-CDF-wavelet. One gets , this polynomial has exactly one real root, thus it is the product of a linear factor 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

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

[edit]

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 filter bank 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). Similarly, the same wavelet may therefore be referred to as "CDF 5/3" (based on the filter sizes) or "biorthogonal 2, 2" (based on the vanishing moments).

Lifting decomposition

[edit]

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

Even number of smoothness factors

[edit]

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

Then define recursively

The lifting filters are

Conclusively, the interim results of the lifting are

which leads to

The filters and constitute the CDF-n,0 filterbank.

Odd number of smoothness factors

[edit]

Now, let be odd.

Then define recursively

The lifting filters are

Conclusively, the interim results of the lifting are

which leads to

where we neglect the translation and the constant factor.

The filters and constitute the CDF-n,1 filterbank.

Applications

[edit]

The Cohen–Daubechies–Feauveau wavelet and other biorthogonal wavelets have been used to compress fingerprint scans for the FBI.[7] 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).[7] By using wavelets, a compression ratio of around 20 to 1 can be achieved, meaning a 10 MB image could be reduced to as little as 500 kB while still passing recognition tests.[7]

[edit]

References

[edit]
  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. doi:10.1002/cpa.3160450502.
  2. ^ Daubechies, Ingrid (1992). Ten Lectures on wavelets. SIAM. doi:10.1137/1.9781611970104. ISBN 978-0-89871-274-2.
  3. ^ Sullivan, Gary (8–12 December 2003). "General characteristics and design considerations for temporal subband video coding". ITU-T. Video Coding Experts Group. Retrieved 13 September 2019.
  4. ^ Bovik, Alan C. (2009). The Essential Guide to Video Processing. Academic Press. p. 355. ISBN 9780080922508.
  5. ^ Gall, D. Le; Tabatabai, Ali J. (1988). "Sub-band coding of digital images using symmetric short kernel filters and arithmetic coding techniques". ICASSP-88, International Conference on Acoustics, Speech, and Signal Processing. pp. 761–764 vol.2. doi:10.1109/ICASSP.1988.196696. S2CID 109186495.
  6. ^ Thielemann, Henning (2006). "section 3.2.4". Optimally matched wavelets (PhD thesis).
  7. ^ a b c Cipra, Barry Arthur (1994). What's Happening in the Mathematical Sciences (Vol. 2) Parlez-vous Wavelets?. American Mathematical Society. ISBN 978-0821889985.