Lifting scheme

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.

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 basic idea of lifting is the following:If a pair of filters $(h,g)$ is "complementary",that is it allows for "perfect reconstruction",then for every filter $s$the pair $(h\text{'},g)$ with $h\text{'}(z)\; =\; h(z)\; +\; s(z^2)cdot\; g(z)$ allows for perfect reconstruction, too.Of course, this is also true for every pair $(h,g\text{'})$ of the form $g\text{'}(z)\; =\; g(z)\; +\; t(z^2)cdot\; h(z)$.The converse is also true:If the filterbanks $(h,g)$ and $(h\text{'},g)$ allow for perfect reconstruction,then there is a unique filter $s$ with $h\text{'}(z)\; =\; h(z)\; +\; s(z^2)cdot\; g(z)$.

Each such transform of the filterbank (or the respective operation in a wavelet transform) is called a lifting step.A sequence of lifting steps consists of alternating lifts,that is, once the lowpass is fixed and the highpass is changed and in the next step the highpass is fixed and the lowpass is changed.Successive steps of the same direction can be merged.

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,an explicit decomposition for a family of wavelets is only known for the Cohen-Daubechies-Feauveau wavelet, so far.

Applications

* Wavelet transform with integer values: [http://www.cs.kuleuven.ac.be/~wavelets/ WAILI]
* Fourier transform with bit-exact reconstruction: Soontorn Oraintara, Ying-Jui Chen, Truong Q. Nguyen: [http://www-ee.uta.edu/msp/pub/Journaintfft.pdf 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: [http://www.math.uni-bremen.de/zetem/DFG-Schwerpunkt/rpwaft2006/talks/thielemann.pdf Optimally matched wavelets]
* Implementation of the Discrete Wavelet Transform in JPEG 2000

External links

* [http://perso.wanadoo.fr/polyvalens/clemens/lifting/lifting.html A comprehensive introduction to the Fast Lifting Wavelet Transform]
*Ingrid Daubechies, Wim Sweldens: [http://www.wavelet.org/phpBB2/viewtopic.php?t=3276 Factoring Wavelet Transforms into Lifting Steps]