Biorthogonal nearly coiflet basis

From HandWiki

In applied mathematics, biorthogonal nearly coiflet bases are wavelet bases proposed by Lowell L. Winger. The wavelet is based on biorthogonal coiflet wavelet bases, but sacrifices its regularity to increase the filter's bandwidth, which might lead to better image compression performance.

Motivation

Nowadays, a large amount of information is stored, processed, and delivered, so the method of data compressing — especially for images — becomes more significant. Since wavelet transforms can deal with signals in both space and frequency domains, they compensate for the deficiency of Fourier transforms and emerged as a potential technique for image processing.[1]

Traditional wavelet filter design prefers filters with high regularity and smoothness to perform image compression.[2] Coiflets are such a kind of filter which emphasizes the vanishing moments of both the wavelet and scaling function, and can be achieved by maximizing the total number of vanishing moments and distributing them between the analysis and synthesis low pass filters. The property of vanishing moments enables the wavelet series of the signal to be a sparse presentation, which is the reason why wavelets can be applied for image compression.[3] Besides orthogonal filter banks, biorthogonal wavelets with maximized vanishing moments have also been proposed.[4] However, regularity and smoothness are not sufficient for excellent image compression.[5] Common filter banks prefer filters with high regularity, flat passbands and stopbands, and a narrow transition zone, while Pixstream Incorporated proposed filters with wider passband by sacrificing their regularity and passband flatness.[5]

Theory

The biorthogonal wavelet base contains two wavelet functions, [math]\displaystyle{ \psi(t) }[/math] and its couple wavelet [math]\displaystyle{ \tilde{\psi}(t) }[/math], while [math]\displaystyle{ \psi(t) }[/math] relates to the lowpass analysis filter [math]\displaystyle{ H0 }[/math] and the high pass analysis filter [math]\displaystyle{ G0 }[/math]. Similarly, [math]\displaystyle{ \tilde{\psi}(t) }[/math] relates to the lowpass synthesis filter [math]\displaystyle{ \tilde{H}0 }[/math] and the high pass synthesis filter [math]\displaystyle{ \tilde{G0} }[/math]. For biorthogonal wavelet base, [math]\displaystyle{ H0 }[/math] and [math]\displaystyle{ \tilde{G0} }[/math] are orthogonal; Likewise, [math]\displaystyle{ G0 }[/math] and [math]\displaystyle{ {\tilde {H0}} }[/math] are orthogonal, too.

In order to construct a biorthogonal nearly coiflet base, the Pixstream Incorporated begins with the (max flat) biorthogonal coiflet base.[5] Decomposing and reconstructing low-pass filters expressed by Bernstein polynomials ensures that the coefficients of filters are symmetric, which benefits the image processing: If the phase of real-valued function is symmetry, than the function has generalized linear phase, and since the human eyes are sensitive to symmetrical error, wavelet base with linear phase is better for image processing application.[1]

Recall that the Bernstein polynomials are defined as below:

[math]\displaystyle{ B^n_k(x)=(^n_k)x^k(1-x)^{n-k} \text{ for } k=1,2,\ldots,n, }[/math]

which can be considered as a polynomial f(x) over the interval [math]\displaystyle{ x\in[0,1] }[/math].[6] Besides, the Bernstein form of a general polynomial is expressed by

[math]\displaystyle{ H1(x)=\sum^n_{k=0}d(k)(^n_k)x^k(1-x)^{n-k}, }[/math]

where d(i) are the Bernstein coefficients. Note that the number of zeros in Bernstein coefficients determines the vanishing moments of wavelet functions.[7] By sacrificing a zero of the Bernstein-basis filter at [math]\displaystyle{ \omega=\pi }[/math] (which sacrifices its regularity and flatness), the filter is no longer coiflet but nearly coiflet.[5] Then, the magnitude of the highest-order non-zero Bernstein basis coefficient is increased, which leads to a wider passband. On the other hand, to perform image compression and reconstruction, analysis filters are determined by synthesis filters. Since the designed filter has a lower regularity, worse flatness and wider passband, the resulting dual low pass filter has a higher regularity, better flatness and narrower passband. Besides, if the passband of the starting biorthogonal coiflet is narrower than the target synthesis filter G0, then its passband is widened only enough to match G0 in order to minimize the impact on smoothness (i.e. the analysis filter H0 is not invariably the design filter). Similarly, if the original coiflet is wider than the target G0, than the original filter's passband is adjusted to match the analysis filter H0. Therefore, the analysis and synthesis filters have similar bandwidth.

The ringing effect (overshoot and undershoot) and shift-variance of image compression might be alleviated by balancing the passband of the analysis and synthesis filters. In other word, the smoothest or highest regularity filters are not always the best choices for synthesis low pass filters.

Drawback

The idea of this method is to obtain more free parameters by despairing some vanishing elements. However, this technique cannot unify biorthogonal wavelet filter banks with different taps into a closed-form expression based on one degree of freedom.[8]

References

  1. 1.0 1.1 Ke, Li. "The Correlation between the Wavelet Base Properties and Image Compression". 2007 International Conference on Computational Intelligence and Security Workshops. 
  2. Villasenor, John (August 1995). "Wavelet filter evaluation for image compression". IEEE Transactions on Image Processing 4 (8): 1053–60. doi:10.1109/83.403412. PMID 18291999. Bibcode1995ITIP....4.1053V. 
  3. http://users.ece.utexas.edu/~bevans/students/phd/dong_wei/phd.pdf
  4. Tian, J (1997). "Coifman Wavelet Systems: Approximation, Smoothness, and Computational Algorithms". in M. Bristeau. Computational Science for the 21st Century. New York: Wiley. pp. 831–840. 
  5. 5.0 5.1 5.2 5.3 L. Winger, Lowell (2001). "Biorthogonal nearly coiflet wavelets for image compression". Signal Processing: Image Communication 16 (9): 859–869. doi:10.1016/S0923-5965(00)00047-3. 
  6. "The Bernstein Basis". Pythagorean-Hodograph Curves: Algebra and Geometry Inseparable. Geometry and Computing. 1. 2008. pp. 249–260. doi:10.1007/978-3-540-73398-0_11. ISBN 978-3-540-73397-3. https://link.springer.com/content/pdf/10.1007%2F978-3-540-73398-0_11.pdf. 
  7. Yang, X (January 2011). "General framework of the construction of biorthogonal wavelets based on Bernstein bases: theory analysis and application in image compression". IET Computer Vision 5 (1): 50–67. doi:10.1049/iet-cvi.2009.0083. 
  8. Liu, Zaide (2007). "Parametrization construction of biorthogonal wavelet filter banks for image coding". Signal, Image and Video Processing 1: 63–76. doi:10.1007/s11760-007-0001-z.