Generalized lifting

The (forward) Lifting Scheme transform block diagram.

Generalized lifting scheme was developed by Joel Solé and Philippe Salembier and published in Joel's PhD Thesis.^[1] It is based on classical lifting scheme and generalizes it breaking out a restriction hidden in the scheme structure. Classical lifting scheme has three kind of operations.

1. Lazy wavelet transform splits signal ${\displaystyle f_{j}[n]}$ in two new signals: the odd samples signal denoted by ${\displaystyle f_{j}^{o}[n]}$ and the even samples signal denoted by ${\displaystyle f_{j}^{e}[n]}$.
2. Prediction step its objective is compute a prediction for the odd samples, based on the even samples (or vice versa). This prediction is subtracted from the odd samples creating an error signal ${\displaystyle g_{j+1}[n]}$.
3. Update step This step recalibrates the low frequency branch with some of the energy removed during subsampling. In the case of classical Lifting, this is used in order to "prepare" the signal for the next prediction step. It uses the predicted odd samples ${\displaystyle g_{j+1}[n]}$ to prepare the even ones ${\displaystyle f_{j}^{e}[n]}$ (or vice versa). This update is subtracted from the even samples producing the signal denoted by ${\displaystyle f_{j+1}[n]}$.

The scheme is invertible due to the structure of itself. In the receiver the update step is computed first. Its result is added to the even samples. After that, it's possible to compute exactly the same prediction and add it to the odd samples. In order to recover the original signal, we have to invert the Lazy Wavelet Transform. Generalized lifting scheme has the same three kind of operations. However this scheme avoids the addition-subtraction restriction that offered Classical Lifting. That fact has some consequences. For example, the design of all steps must guarantee the scheme invertibility (not guaranteed if the addition-subtraction restriction is avoided).

Definition

The (forward) Generalized Lifting Scheme transform block diagram.

Generalized lifting scheme is a dyadic transform that follows these rules:

1. Deinterleaves the input into a stream of even-numbered samples and another stream of odd-numbered samples. This is sometimes referred to as a Lazy Wavelet Transform.
2. Computes a Prediction Mapping. This step tries to predict odd samples taking into account the even ones (or vice versa). This a mapping from the space of the samples in ${\displaystyle f_{j}^{e}[n]}$ to the space of the samples in ${\displaystyle g_{j+1}[n]}$. In this case the samples (from ${\displaystyle f_{j}^{e}[n]}$) chosen to be the reference for ${\displaystyle f_{j}^{o}[n]}$ are called the context. It could be expressed as:

   ${\displaystyle \textstyle g_{j+1}[n]=P(f_{j}^{o}[n];f_{j}^{e}[n])}$

3. Computes an Update Mapping. This step tries to update the even samples taking into account the odd predicted samples. It would be a kind of preparation for the next prediction step, if any. It could be expressed:

   ${\displaystyle \textstyle f_{j+1}[n]=U(f_{j}^{e}[n];g_{j+1}[n])}$

Obviously, these mappings cannot be any functions. In order to guarantee the invertibility of the scheme itself, all mappings involved in the transform must be invertible. In case that mappings arise and arrive on finite sets (discrete bounded value signals), this condition is equivalent to saying that mappings are injective (one-to-one). Moreover, if a mapping goes from one set to a set of the same cardinality, it should be bijective.

In the Generalized Lifting Scheme the addition/subtraction restriction is avoided by including this step in the mapping. In this way the Classical Lifting Scheme is generalized.

Design

Some designs have been developed for the prediction-step mapping. The update-step design has not been considered as thoroughly, because it remains to be answered how exactly the update step is useful. The main application of this technique is image compression. There some interesting references such as,^[2][3][4] and.^[5]

References

1. Ph.D. Thesis Dissertation: Optimization and Generalization of Lifting Schemes: Application to Lossless Image Compression
2. Rolon, J. C.; Salembier, P. (Nov 7–9, 2007). "Generalized Lifting for Sparse Image Representation and Coding". Picture Coding Symposiu, PCS 2007.
3. Rolon, J. C.; Salembier, P.; Alameda, X. (Oct 12–15, 2008). "Image Compression with Generalized Lifting and partial knowledge of the signal pdf". International Conference on Image Processing, ICIP'08.
4. Rolon, J. C.; Ortega, A.; Salembier, P. "Modeling of Contours in Wavelet Domain for Generalized Lifting Image Compression". ICASSP 2009 (submitted).
5. Rolon, J. C.; Mendonça, E.; Salembier, P. Generalized Lifting With Adaptive Local pdf estimation for Image Coding.