Wavelet packet decomposition

Last updated

Originally known as Optimal Subband Tree Structuring (SB-TS) also called Wavelet Packet Decomposition (WPD) (sometimes known as just Wavelet Packets or Subband Tree) is a wavelet transform where the discrete-time (sampled) signal is passed through more filters than the discrete wavelet transform (DWT).

Wavelet function for integral Fourier-like transform

A wavelet is a wave-like oscillation with an amplitude that begins at zero, increases, and then decreases back to zero. It can typically be visualized as a "brief oscillation" like one recorded by a seismograph or heart monitor. Generally, wavelets are intentionally crafted to have specific properties that make them useful for signal processing. Using a "reverse, shift, multiply and integrate" technique called convolution, wavelets can be combined with known portions of a damaged signal to extract information from the unknown portions.

Discrete wavelet transform

In numerical analysis and functional analysis, a discrete wavelet transform (DWT) is any wavelet transform for which the wavelets are discretely sampled. As with other wavelet transforms, a key advantage it has over Fourier transforms is temporal resolution: it captures both frequency and location information.

Contents

Introduction

In the DWT, each level is calculated by passing only the previous wavelet approximation coefficients (cAj) through discrete-time low and high pass quadrature mirror filters. [1] However, in the WPD, both the detail (cDj (in the 1-D case), cHj, cVj, cDj (in the 2-D case)) and approximation coefficients are decomposed to create the full binary tree. [2] [3] [4] [5] [6] [7]

In digital signal processing, a quadrature mirror filter is a filter whose magnitude response is the mirror image around of that of another filter. Together these filters are known as the Quadrature Mirror Filter pair.

Wavelet Packet decomposition over 3 levels. g[n] is the low-pass approximation coefficients, h[n] is the high-pass detail coefficients Wavelets - WPD.png
Wavelet Packet decomposition over 3 levels. g[n] is the low-pass approximation coefficients, h[n] is the high-pass detail coefficients

For n levels of decomposition the WPD produces 2n different sets of coefficients (or nodes) as opposed to (3n + 1) sets for the DWT. However, due to the downsampling process the overall number of coefficients is still the same and there is no redundancy.

From the point of view of compression, the standard wavelet transform may not produce the best result, since it is limited to wavelet bases that increase by a power of two towards the low frequencies. It could be that another combination of bases produce a more desirable representation for a particular signal. The best basis algorithm by Coifman and Wickerhauser [1] finds a set of bases that provide the most desirable representation of the data relative to a particular cost function (e.g. entropy).

Entropy physical property of the state of a system, measure of disorder

In statistical mechanics, entropy is an extensive property of a thermodynamic system. It is closely related to the number Ω of microscopic configurations that are consistent with the macroscopic quantities that characterize the system. Under the assumption that each microstate is equally probable, the entropy is the natural logarithm of the number of microstates, multiplied by the Boltzmann constant kB. Formally,

There were relevant studies in signal processing and communications fields to address the selection of subband trees (orthogonal basis) of various kinds, e.g. regular, dyadic, irregular, with respect to performance metrics of interest including energy compaction (entropy), subband correlations and others. [3] [4] [5] [6] [7]

Discrete wavelet transform theory (continuous in the variable(s)) offers an approximation to transform discrete (sampled) signals. In contrast, the discrete subband transform theory provides a perfect representation of discrete signals. [5]

Applications

Wavelet packets were successfully applied in preclinical diagnosis. [8]

Related Research Articles

Daubechies wavelet

The Daubechies wavelets, based on the work of Ingrid Daubechies, are a family of orthogonal wavelets defining a discrete wavelet transform and characterized by a maximal number of vanishing moments for some given support. With each wavelet type of this class, there is a scaling function which generates an orthogonal multiresolution analysis.

Stéphane Mallat French mathematician

Stéphane Georges Mallat is a French applied mathematician, Professor at College de France and Ecole Normale Superieure. He has made some fundamental contributions to the development of wavelet theory in the late 1980s and early 1990s. He has also done work in applied mathematics, signal processing, music synthesis and image segmentation.

Chirplet transform

In signal processing, the chirplet transform is an inner product of an input signal with a family of analysis primitives called chirplets.

In signal processing, a filter bank is an array of band-pass filters that separates the input signal into multiple components, each one carrying a single frequency sub-band of the original signal. One application of a filter bank is a graphic equalizer, which can attenuate the components differently and recombine them into a modified version of the original signal. The process of decomposition performed by the filter bank is called analysis ; the output of analysis is referred to as a subband signal with as many subbands as there are filters in the filter bank. The reconstruction process is called synthesis, meaning reconstitution of a complete signal resulting from the filtering process.

The Fast Wavelet Transform is a mathematical algorithm designed to turn a waveform or signal in the time domain into a sequence of coefficients based on an orthogonal basis of small finite waves, or wavelets. The transform can be easily extended to multidimensional signals, such as images, where the time domain is replaced with the space domain. This algorithm was introduced in 1989 by Stéphane Mallat.

Embedded Zerotrees of Wavelet transforms (EZW) is a lossy image compression algorithm. At low bit rates, i.e. high compression ratios, most of the coefficients produced by a subband transform will be zero, or very close to zero. This occurs because "real world" images tend to contain mostly low frequency information. However where high frequency information does occur this is particularly important in terms of human perception of the image quality, and thus must be represented accurately in any high quality coding scheme.

A multiresolution analysis (MRA) or multiscale approximation (MSA) is the design method of most of the practically relevant discrete wavelet transforms (DWT) and the justification for the algorithm of the fast wavelet transform (FWT). It was introduced in this context in 1988/89 by Stephane Mallat and Yves Meyer and has predecessors in the microlocal analysis in the theory of differential equations and the pyramid methods of image processing as introduced in 1981/83 by Peter J. Burt, Edward H. Adelson and James L. Crowley.

In signal processing, the second-generation wavelet transform (SGWT) is a wavelet transform where the filters are not designed explicitly, but the transform consists of the application of the Lifting scheme. Actually, the sequence of lifting steps could be converted to a regular discrete wavelet transform, but this is unnecessary because both design and application is made via the lifting scheme. This means that they are not designed in the frequency domain, as they are usually in the classical transforms such as the DWT and CWT). The idea of moving away from the Fourier domain was introduced independently by David Donoho and Harten in the early 1990s.


The Stationary wavelet transform (SWT) is a wavelet transform algorithm designed to overcome the lack of translation-invariance of the discrete wavelet transform (DWT). Translation-invariance is achieved by removing the downsamplers and upsamplers in the DWT and upsampling the filter coefficients by a factor of in the th level of the algorithm. The SWT is an inherently redundant scheme as the output of each level of SWT contains the same number of samples as the input – so for a decomposition of N levels there is a redundancy of N in the wavelet coefficients. This algorithm is more famously known as "algorithme à trous" in French which refers to inserting zeros in the filters. It was introduced by Holschneider et al.

The complex wavelet transform (CWT) is a complex-valued extension to the standard discrete wavelet transform (DWT). It is a two-dimensional wavelet transform which provides multiresolution, sparse representation, and useful characterization of the structure of an image. Further, it purveys a high degree of shift-invariance in its magnitude, which was investigated in. However, a drawback to this transform is that it exhibits redundancy compared to a separable (DWT).

Wavelet transform mathematical technique used in data compression and analysis

In mathematics, a wavelet series is a representation of a square-integrable function by a certain orthonormal series generated by a wavelet. This article provides a formal, mathematical definition of an orthonormal wavelet and of the integral wavelet transform.

Lifting scheme

The lifting scheme is a technique for both designing wavelets and performing the discrete wavelet transform (DWT). In an implementation, it is often worthwhile to merge these steps and design the wavelet filters while performing the wavelet transform. This is then called the second-generation wavelet transform. The technique was introduced by Wim Sweldens.

Ali N. Akansu is a Turkish American scientist best known for his seminal contributions to the theory and applications of sub-band and wavelet transforms.

A binomial QMF – properly an orthonormal binomial quadrature mirror filter – is an orthogonal wavelet developed in 1990.

Contourlets form a multiresolution directional tight frame designed to efficiently approximate images made of smooth regions separated by smooth boundaries. The contourlet transform has a fast implementation based on a Laplacian pyramid decomposition followed by directional filterbanks applied on each bandpass subband.

Wavelets are often used to analyse piece-wise smooth signals. Wavelet coefficients can efficiently represent a signal which has led to data compression algorithms using wavelets. Wavelet analysis is extended for multidimensional signal processing as well. This article introduces a few methods for wavelet synthesis and analysis for multidimensional signals. There also occur challenges such as directivity in multidimensional case.

References

  1. 1 2 Coifman RR & Wickerhauser MV, 1992. Entropy-Based Algorithms for Best Basis Selection, IEEE Transactions on Information Theory, 38(2).
  2. Daubechies, I. (1992), Ten lectures on wavelets, SIAM
  3. 1 2 A.N. Akansu and Y. Liu, On Signal Decomposition Techniques, (Invited Paper), Optical Engineering Journal, special issue Visual Communications and Image Processing, vol.30, pp. 912-920, July 1991.
  4. 1 2 H. Caglar, Y. Liu and A.N. Akansu, Statistically Optimized PR-QMF Design, Proc. SPIE Visual Communications and Image Processing, vol. 1605, pp. 86-94, 1991.
  5. 1 2 3 A.N. Akansu and R.A. Haddad, Multiresolution Signal Decomposition: Transforms, Subbands, and Wavelets. Boston, MA: Academic Press, ISBN   978-0-12-047141-6, 1992.
  6. 1 2 A. Benyassine and A.N. Akansu, Performance Analysis and Optimal Structuring of Subchannels for Discrete Multitone Transceivers , Proc. IEEE Proc. IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1456-1459, April 1995.
  7. 1 2 M.V. Tazebay and A.N. Akansu, Adaptive Subband Transforms in Time-frequency Excisers for DSSS Communications Systems, IEEE Trans. Signal Process., vol. 43, pp. 2776-2782, Nov. 1995.
  8. Zhang, Y.; Dong, Z. (2015). "Preclinical Diagnosis of Magnetic Resonance (MR) Brain Images via Discrete Wavelet Packet Transform with Tsallis Entropy and Generalized Eigenvalue Proximal Support Vector Machine (GEPSVM)". Entropy. 17 (4): 1795–1813. Bibcode:2015Entrp..17.1795Z. doi:10.3390/e17041795.