Lifting scheme

Lifting sequence consisting of two steps

The lifting scheme is a technique for both designing wavelets and performing the discrete wavelet transform. Actually it is 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.

Factorizes orthogonal and biorthogonal wavelet transforms into elementary spatial operators called lifting. It has two main applications. The first one is an acceleration of the fast wavelet transform algorithm. The filter bank convolution and subsampling operations are factorized into elementary filterings on even and odd samples, which reduces the number of operations by nearly 2. Border treatments are also simplified. This is also called a paraunitary filter bank implementation. The second application is the design of wavelets adapted to multidimensional bounded domains and surfaces, which is not possible with a Fourier transform approach.

The discrete wavelet transform applies several filters separately to the same signal. In contrast to that, for the lifting scheme the signal is divided like a zipper. Then a series of convolution-accumulate operations across the divided signals is applied.

Basics

The simplest version of a forward wavelet transform expressed in the Lifting Scheme is shown in Figure P means predict step, which will considered in isolation. The predict step calculates the wavelet function in the wavelet transform. This is a high pass filter. The update step calculates the scaling function, which results in a smoother version of the data.

As mentioned above the lifting scheme is an alternative technique for performing the DWT using biorthogonal wavelets. In order to perform the DWT using the lifting scheme the corresponding lifting and scaling steps must be derived from the biorthogonal wavelets. The analysis filters of the particular wavelet are first written in polyphase matrix form shown below

$P(z)={\begin{bmatrix}h_{even}(z)&g_{even}(z)\\h_{odd}(z)&g_{odd}(z)\end{bmatrix}}$

${\begin{bmatrix}h_{even}(z)&g_{even}(z)\\h_{odd}(z)&g_{odd}(z)\end{bmatrix}}{\begin{bmatrix}X_{even}(z)\\X_{odd}(z)\end{bmatrix}}={\begin{bmatrix}X_{1,L}(z)\\X_{1,H}(z)\end{bmatrix}}$

$det({\begin{bmatrix}h_{even}(z)&g_{even}(z)\\h_{odd}(z)&g_{odd}(z)\end{bmatrix}})=z^{-m}$

The poly phase matrix is a 2 x 2 matrix containing the analysis low-pass and high-pass filters each split up into their even and odd polynomial coefficients and normalized. From here the matrix is factored into a series of 2 x 2 upper and lower triangular matrices each with diagonal entries equal to 1. The upper triangular matrices contain the coefficients for the predict steps and the lower triangular matrices contain the coefficients for the update steps. A matrix consisting of all O’s with the exception of the diagonal values may be extracted to derive the scaling step coefficients. The poly phase matrix is factored into the form shown in the equation below, a is the coefficient for the predict step and p is the coefficient for the update step.

$P(z)={\begin{bmatrix}1&a(1-z^{-}1)\\0&1\end{bmatrix}}{\begin{bmatrix}1&0\\b(1+z)&1\end{bmatrix}}$

An example of a more complicated extraction having multiple predict and update steps as well as scaling steps is shown below; a is the coefficient for the first predict step, p is the coefficient for the first update step, A, is the coefficient for the second predict step, 5 is the coefficient for the second update step, k1 is the odd sample scaling coefficient, and k 2 is the even sample scaling coefficient.

$P(z)={\begin{bmatrix}1&a(1+z^{-}1)\\0&1\end{bmatrix}}{\begin{bmatrix}1&0\\b(1+z)&1\end{bmatrix}}{\begin{bmatrix}1&c(1+z^{-}1)\\0&1\end{bmatrix}}{\begin{bmatrix}1&0\\d(1+z)&1\end{bmatrix}}{\begin{bmatrix}k1&0\\0&k2\end{bmatrix}}$

According to matrix theory, any matrix having polynomial entries and a determinant of 1 can be factored as described above. Therefore every FTR wavelet or filter bank can be decomposed into a series of lifting and scaling steps. Daubechies and Sweldens discuss lifting step extraction in further detail.

CDF 9/7 filter

A total of four lift steps are required, two predict and two update steps, to perform the proposed modified structure of CDF 9/7 DWT by adapting new scaling values of scaling coefficients of k1 and k2. The coefficients for predict and update steps are enlisted in table I.The predict and update equations for the CDF 9/7 filter are shown below.

$Predict1:odd_{new}=odd_{old}+[a(even_{left}+even_{right})]$

$Update1:even_{new}=even_{old}+[b(odd_{left}+odd_{right})]$

$Predict2:odd_{new}=odd_{old}+[c(even_{left}+even_{right})]$

$Scaleodd:odd_{new}=[k1*odd_{old}]$

$Scaleeven:even_{new}=[k2*_{e}ven{old}]$

The floor function is used for all the predict, update and scale equations to provide an integer-to integer transform.The CDF 9/7 DWT consists of four lifting steps and two scaling steps. The first lifting step (predict step 1) is applied to the original row of samples and the results then safely overwrite the odd samples in the original signal for use in the next lifting step.

Properties

Perfect reconstruction
- Every transform by the lifting scheme can be inverted.
- Every perfect reconstruction filter bank can be decomposed into lifting steps by the Euclidean algorithm.
- That is, "lifting decomposable filter bank" and "perfect reconstruction filter bank" denotes the same.
Every two perfect reconstructable filter banks can be transformed into each other by a sequence of lifting steps. (If $P$ and $Q$ are polyphase matrices with the same determinant, the lifting sequence from $P$ to $Q$ , is the same as the one from the lazy polyphase matrix $I$ to $P^{{-1}}\cdot Q$ .)
Speedup by a factor of two. This is only possible because lifting is restricted to perfect reconstruction filterbanks. That is, lifting somehow squeezes out redundancies caused by perfect reconstructability.
In place: The transformation can be performed immediately in the memory of the input data with only constant memory overhead.
Non-linearities: The convolution operations can be replaced by any other operation. For perfect reconstruction only the invertibility of the addition operation is relevant. This way rounding errors in convolution can be tolerated and bit-exact reconstruction is possible. However the numeric stability may be reduced by the non-linearities. This must be respected if the transformed signal is processed like in lossy compression.Although every reconstructable filter bank can be expressed in terms of lifting steps, a general description of the lifting steps is not obvious from a description of a wavelet family. However, for instance for simple cases of the Cohen-Daubechies-Feauveau wavelet, there is an explicit formula for their lifting steps. (See the respective article)
Increasing Vanishing Moments, Stability, and Regularity

A lifting modifies biorthogonal filters in order to increase the number of vanishing moments of the resulting biorthogonal wavelets, and hopefully their stability and regularity. Increasing the number of vanishing moments decreases the amplitude of wavelet coefficients in regions where the signal is regular, which produces a more sparse representation. However, increasing the number of vanishing moments with a lifting also increases the wavelet support,which is an adverse effect that increases the number of large coefficients produced by isolated singularities. Each lifting step maintains the filter biorthogonality but provides no control on the Riesz bounds and thus on the stability of the resulting wavelet biorthogonal basis. When a basis is orthogonal then the dual basis is equal to the original basis. Having a dual basis that is similar to the original basis is therefore an indication of stability. As a result,stability is generally improved when dual wavelets have as much vanishing moments as original wavelets and a support of similar size. This is why a lifting procedure also increases the number of vanishing moments of dual wavelets. It can also improve the regularity of the dual wavelet. A lifting design is computed by adjusting the number of vanishing moments. The stability and regularity of the resulting biorthogonal wavelets are measured a posteriori, hoping for the best. This is the main weakness of this wavelet design procedure.

Generalized Lifting

Main article: Generalized Lifting

The Generalized Lifting Scheme is a derivative of the Lifting Scheme, in which the addition and subtraction operations are absorbed into the update and prediction steps, respectively. These steps can be any (invertible) mapping, leading to a more general lifting scheme.

Applications

Wavelet transform with integer values: WAILI
Fourier transform with bit-exact reconstruction: Soontorn Oraintara, Ying-Jui Chen, Truong Q. Nguyen: Integer Fast Fourier Transform
Construction of wavelets with a required number of smoothness factors and vanishing moments
Construction of wavelets matched to a given pattern: Henning Thielemann: Optimally matched wavelets
Implementation of the Discrete Wavelet Transform in JPEG 2000

External links

A comprehensive introduction to the Fast Lifting Wavelet Transform
Ingrid Daubechies, Wim Sweldens: Factoring Wavelet Transforms into Lifting Steps
Introduction to The Lifting Scheme
The Lifting Scheme: A Construction of Second Generation Wavelets
Stéphane Mallat: A Wavelet Tour of Signal Processing
Modified Adaptive Lifting Structure Of CDF 9/7 Wavelet With Spiht For Lossy Image Coding Sanjay H. Dabhole

This article is issued from Wikipedia - version of the 11/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.