Legendre wavelet

From Wikipedia, the free encyclopedia

Contents

[edit] Legendre wavelets: spherical harmonic wavelets

Compactly supported wavelets derived from Legendre polynomials are termed spherical harmonic or Legendre wavelets [1]. Legendre functions have widespread applications in which spherical coordinate system are appropriate [2-4]. As with many wavelets there is no nice analytical formula for describing these harmonic spherical wavelets. The low-pass filter associated to Legendre multiresolution analysis is a finite impulse response filter (FIR).

Wavelets associated to finite impulse response filters (FIR) are commonly preferred in most applications [3]. An extra appealing feature is that the Legendre filters are linear phase FIR (i.e. multiresolution analysis associated with linear phase filters). These wavelets have been implemented on MatlabTM (wavelet toolbox). Although being compactly supported wavelet, legdN are not orthogonal (but for N=1) (see [5]).

[edit] Legendre multiresolution filters

Associated Legendre polynomials are the colatitudinal part of the spherical harmonics which are common to all separations of Laplace's equation in spherical polar coordinates [2]. The radial part of the solution varies from one potential to another, but the harmonics are always the same and are a consequence of spherical symmetry. Spherical harmonics Pn(z) are solutions of the Legendre 2nd-order differential equation, n integer:

(1-z^2) \frac {d^2y} {dz^2} - 2z \frac {dy} {dz} + n(n+1)y=0

Pn(cosθ) polynomials can be used to define the smoothing filter H(ω) of a multiresolution analysis (MRA) [6]. Since the appropriate boundary conditions for an MRA are | H(0) | = 1 and | H(π) | = 0, the smoothing filter of an MRA can be defined so that the magnitude of the low-pass | H(ω) | can be associated to Legendre polynomials according to: ν = 2n + 1.

|H_{\nu}(\omega)|=| \frac {P_{\nu} ( \cos { \frac {\omega} {2})}} {P_{\nu} \cos (0)}|

Illustrative examples of filter transfer functions for a Legendre MRA are shown in figure 1, for ν=1,3 and 5. A low-pass behaviour is exhibited for the filter H, as expected. The number of zeroes within − π < ω < π is equal to the degree of the Legendre polynomial. Therefore, the roll-off of side-lobes with frequency is easily controlled by the parameter ν.

Figure 1 - Magnitude of the transfer function for Legendre multiresolution smoothing filters. Filter | Hν(ω) | for a few orders: ν=1 (solid line), ν=3 (dot line), and ν=5 (dashdot line).
Figure 1 - Magnitude of the transfer function for Legendre multiresolution smoothing filters. Filter | Hν(ω) | for a few orders: ν=1 (solid line), ν=3 (dot line), and ν=5 (dashdot line).

The low-pass filter transfer function is given by

H_{\nu} (\omega)=-e^{-j \nu \frac {\omega - \pi} {2}} P_{\nu}( \cos (\frac {\omega} {2}))

The transfer function of the high-pass analysing filter Gν(ω) is chosen according to Quadrature mirror filter condition [6,7], yielding:

H_{\nu} (\omega)=-e^{-j {(\nu-2)} \frac {\omega} {2}} P_{\nu}( \sin (\frac {\omega} {2}))

Indeed, | Gν(0) | = 0 and | Gν(π) | = 1, as expected.

[edit] Legendre multiresolution filter coefficients

A suitable phase assignment is done so as to properly adjust the transfer function Hν(ω) to the form H_{\nu} (\omega)= \frac {1} {\sqrt {2}} \sum_{k \in Z} h_k^{\nu} e^{-j \omega k}
The filter coefficients {hk}, k \in Z are given by: \frac {h_k^{\nu}} {\sqrt {2}}= - \frac {1} {2^{2 \nu}}.\binom{2k}{k}.\binom{2 \nu -2k}{\nu -k}
It follows then the symmetry: {h_k^{\nu}}={h_{\nu -k}^{\nu}}. There are just ν + 1 non-zero filter coefficients on Hn(ω), so that the Legendre wavelets have compact support for every odd integer ν.

Table I - Smoothing Legendre FIR filter coefficients for ν=1,3,5 (N is the wavelet order.)
ν = 1 (N=1) ν = 3 (N=2) ν = 5 (N=3)
h0 - \sqrt {2} /2 - 5 \sqrt {2}/16 -63 \sqrt {2} / 256
h1 - \sqrt {2} /2 -3 \sqrt {2} /16 - 35 \sqrt {2} /256
h2 -3 \sqrt {2} /16 -30 \sqrt {2} /256
h3 -5 \sqrt {2} /16 -30 \sqrt {2} /256
h4 -35 \sqrt {2} /256
h5 -63 \sqrt {2} /256
N.B. The minus signal can be suppressed.

[edit] MATLAB implementation of Legendre wavelets

Legendre wavelets can be easily loaded into the MatLab wavelet toolbox -- The m-files to allow the computation of Legendre wavelet transform, details and filter are (freeware) available [8]. The finite support width Legendre family is denoted by legd (short name). Wavelets: 'legdN'. The parameter N in the legdN family is found according to 2N=ν+1 (length of the MRA filters).
Legendre wavelets can be derived from the low-pass reconstruction filter by an iterative procedure (the cascade algorithm). The wavelet has compact support and finite impulse response AMR filters (FIR) are used (table 1). The first wavelet of the Legendre's family is exactly the well-known Haar wavelet. Figure 2 shows an emerging pattern that progressively looks like the wavelet's shape.

Figure 2 - Shape of Legendre Wavelets of degree ν=3 (legd2) derived after 4 and 8 iteration of the cascade algorithm, respectively. Shape of Legendre Wavelets of degree ν=5 (legd3) derived by the cascade algorithm after 4 and 8 iterations of the cascade algorithm, respectively.
Figure 2 - Shape of Legendre Wavelets of degree ν=3 (legd2) derived after 4 and 8 iteration of the cascade algorithm, respectively. Shape of Legendre Wavelets of degree ν=5 (legd3) derived by the cascade algorithm after 4 and 8 iterations of the cascade algorithm, respectively.

The Legendre wavelet shape can be visualised using the wavenemu command of Matlab. Figure 3 shows legd8 wavelet displayed using MatLabTM. Legendre Polynomials are also associated with windows families [9].

Figure 3 - legd8 wavelet display over MatlabTM using the wavemenu command.
Figure 3 - legd8 wavelet display over MatlabTM using the wavemenu command.

[edit] A naïve image processing application

2-dimensional Legendre transform (2D-legdN) for image analysis is promptly available. Interesting effects have been observed in multiresolution decomposition of hand-drawn images such as illustrated in figure 4.

Figure 4 - Reconstruction of a hand-drawn draft using 2D-legd2. (a) Original (b) Reconstructed image from 1-level wavelet decomposition.
Figure 4 - Reconstruction of a hand-drawn draft using 2D-legd2. (a) Original (b) Reconstructed image from 1-level wavelet decomposition.

[edit] Legendre wavelet packets

Wavelet packets (WP) systems derived from Legendre wavelets can also be easily accomplished. Figure 5 illustrates the WP functions derived from legd2.

Figure 5 - Legendre (legd2) Wavelet Packets W system functions: WP from 0 to 9.
Figure 5 - Legendre (legd2) Wavelet Packets W system functions: WP from 0 to 9.

[edit] References

  • [1] M.M.S. Lira, H.M. de Oliveira, M.A. Carvalho Jr, R.M.C.Souza, Compactly Supported Wavelets Derived from Legendre Polynomials: Spherical Harmonic Wavelets, In: Computational Methods in Circuits and Systems Applications, N.E. Mastorakis, I.A. Stahopulos, C. Manikopoulos, G.E. Antoniou, V.M. Mladenov, I.F. Gonos Eds., WSEAS press, pp.211-215, 2003. ISBN: 960-8052-88-2. Available at http://www2.ee.ufpe.br/codec/Legendre_WSEAS.PDF
  • [2] I.S. Gradshteyn and I.M. Ryzhik, Table of Integrals, Series, and Products, 4th Ed., New York: Academic Press, 1965.
  • [3] A. A. Colomer and A. A. Colomer, Adaptive ECG Data Compression Using Discrete Legendre Transform, Digital Signal Processing, 7, 1997, pp.222–228.
  • [4] A.G. Ramm, A.I. Zaslavsky, X-Ray Transform, the Legendre Transform, and Envelopes, J. of Math. Analysis and Appl., 183, pp.528-546, 1994.
  • [5] C. Herley, M. Vetterli, Orthogonalization of Compactly Supported Wavelet Bases, IEEE Digital Signal Process. Workshop, 13-16 Sep., pp.1.7.1-1.7.2, 1992.
  • [6] S. Mallat, A Theory for Multiresolution Signal Decomposition: The Wavelet Representation, IEEE Trans. Pattern Analysis and Machine Intelligence, 11, July pp.674-693, 1989.
  • [7] M. Vetterli, C. Herly, Wavelets and Filter Banks: Theory and Design, IEEE Trans. on Acoustics, Speech, and Signal Processing, 40, 9, p.2207, 1992.
  • [9] M. Jaskula, New Windows Family Based on Modified Legendre Polynomials, IEEE Instrum. And Measurement Technol. Conf., Anchorage, AK, May, 2002, pp. 553-556.