The Lifting Scheme

Wim Sweldens




This page gives an overview of resources related to the lifting scheme.

Sections:

  1. Introduction
  2. Papers on lifting
      - The original lifting papers
      - Tutorial and overview papers
      - Factoring into lifting steps
      - Fast lifting transforms
      - Lifting and Second Generation Wavelets
      - Lifting and adaptive/nonlinear transforms
      - Lifting and multiwavelets
      - Lifting and lossless integer transforms
      - Lifting and multivariate/M-band wavelets
      - Lifting and document compression
      - Lifting and multiple descriptions
      - Lifting and geometric modeling
      - Other
  3. Software implementations of lifting
  4. Hardware implementations of lifting
  5. Books on or with sections on lifting
  6. Links to other lifting pages
  7. Connections with other methods


If you want to be notified of additions to this page please enter your e-mail address below. Your address will be kept confidential and only used for sending updates. Updates happen not more than once a month.
e-mail:
If you want some of your work or pages included in this page, please e-mail to wim@lucent.com.

1. Introduction

This page gives an overview of resources related to the lifting scheme.

Lifting is a mechanism for building wavelets and multiresolution transforms. It is based on a simple observation which is well known in algebra that matrices with a certain block structure have trivial inverses. The main features of lifting are:

Back to top

2. Papers on lifting

    The original lifting papers
  1. W. Sweldens, The Lifting Scheme: A Custom Design Construction of Biorthogonal Wavelets. (ps ps.gz pdf)
    This paper described the first generation (tranlation and dilation construction) case and was written in the fall of 1994.
  2. W. Sweldens, The Lifting Scheme: A Construction of Second Generation Wavelets. (ps ps.gz pdf)
    This paper describes the second generation case and was written in the spring of 1995.

    Back to top

    Tutorial and overview papers
  3. W. Sweldens, The Lifting Scheme: A New Philosophy in Biorthogonal Wavelet Construction (ps ps.gz pdf)
    This is a short conference papers written in the summer of 1995 showing the simplest instances of lifting and how to do the in-place computation.
  4. W. Sweldens and P. Schröder, Building Your Own Wavelets at Home. (ps ps.gz pdf)
    This is a tutorial paper on lifting first written in spring of 1995 and later thoroughly rewritten in the spring of 1996. Probably the best place to start reading about lifting. It handles both the first and second generation setting. It also contains some new material on how to construct wavelets on irregular samples and weighted measures.
  5. I. Daubechies and W. Sweldens, Factoring Wavelet Transforms into Lifting Steps. (ps ps.gz pdf)
    This is an overview papers written in 1996 on how existing factoring techniques connect with lifting and how they speed up the wavelet transforms. Contains many examples of existing wavelet transforms factored into lifting steps. Also contains a introductory section on how lifting connects with other approaches such as ladder structures and multiscale transforms.

    Back to top

    Factoring into lifting steps
  6. Mark Maslen, Factoring Wavelet Transforms. (With Mathematica notebook) (ps.gz pdf nb)
  7. Mark Maslen and Paul Abbott, Automation of the Lifting Factorisation of Wavelet Transforms. (With Mathematica notebook) nb)
  8. Andreas Klappenecker, Matthias Holschneider and Kristin Flornes, Two-Channel Perfect Reconstruction Filter Banks over Commutative Rings. (ps.gz)
  9. Andreas Klappenecker and Matthias Holschneider, A Unified View on Filter Banks . (ps.gz)
  10. A.Petukhov Biorthogonal wavelet bases with rational masks. (ps.gz)

    Back to top

    Fast lifting transforms
  11. T. D. Tran The LiftLT: fast lapped transforms via lifting steps. (ps.gz pdf)
  12. T. D. Tran, The BinDCT: fast multiplierless approximation of the DCT. This paper show how lifting can be used to build fast implementations of the DCT. (ps.gz pdf)
  13. W. Jiang and A. Ortega, Parallel Architecture for the Discrete Wavelet Transform based on the Lifting Factorization. This paper described how to use lifting to build a parallel hardware implementation of the wavelet transform. (ps.gz)
  14. W. Jiang and A. Ortega, Efficient Discrete Wavelet Transform Architectures Based on Filterbank Factorizations. This paper shows how lifting can be used to model the DWT as a finite state machine. This can reduce the memory and communication needed in a hardware implementation. (ps.gz)
  15. Chengjiang Lin, Bo Zhang, Yuan F Zheng, Packed Computation of Integer Wavelet Transform Constructed By Lifting Scheme ICASSP 99, vol. 6, pp. 3177-3180. (pdf.gz)
  16. Julien Reichel, Marcus J. Nadenau & Murat Kunt Row-based wavelet decomposition using the lifting scheme

    Back to top

    Lifting and Second Generation Wavelets
  17. P. Schröder and W. Sweldens, Spherical Wavelets: Efficiently Representing Functions on a Sphere. (ps ps.gz pdf) This paper describes how to use lifting for building wavelets on a sphere. The technique also works for any semi-regular triangulation of a surface.
  18. P. Schröder and W. Sweldens, Spherical Wavelets: Texture Processing. (ps ps.gz pdf) This paper shows how to use spherical wavelets in spherical image processing.
  19. I. Daubechies, I. Guskov, P. Schröder, and W. Sweldens, Wavelets on Irregular Point Sets (ps ps.gz pdf)
  20. I. Daubechies, I. Guskov, W. Sweldens, Commutation for Irregular Subdivision (ps ps.gz pdf)
  21. M. Jansen and A. Bultheel, Smoothing irregularly sampled signals using wavelets and cross validation. (ps.gz) This paper described how to smooth irregularly sampled signals using second generation wavelets built with lifting.
  22. I. Daubechies, I. Guskov, W. Sweldens, Regularity of irregular subdivision (ps ps.gz pdf)

    Back to top

    Lifting and adaptive/nonlinear transforms
  23. Roger Claypoole, Geoffrey M. Davis, Wim Sweldens, and Rich Baraniuk, Nonlinear Wavelet Transforms for Image Coding via Lifting (ps ps.gz pdf)
  24. Roger L. Claypoole and Richard G. Baraniuk, Flexible wavelet transforms using lifting. (ps.Z)
  25. R. Claypoole, G. Davis, W. Sweldens, and R. Baraniuk, Nonlinear wavelet transform for image coding. (ps ps.gz pdf)
  26. R. Claypoole, R. Baraniuk, and R. D. Nowak, Adaptive Wavelet Transforms via Lifting. (ps.gz)
  27. Ward Trappe and KuoJuey Ray Liu, Adaptivity in the Lifting Scheme (ps)
  28. Ward Trappe and Haitao Zheng and KuoJuey Ray Liu, Adaptive Lifting Coding Scheme for Video Scene Changes. (ps.Z)
  29. Henk Heijmans and John Goutsias, Multiresolution Signal Decomposition Schemes: Morphological Wavelets. This paper describes a powerful framework for non-linear morphological wavelet transforms based on lifting. (pdf)

    Back to top

    Lifting and multiwavelets
  30. Say Song Goh, Qingtang Jiang and Tao Xia, Construction of Biorthogonal Multiwavelets Using the Lifting Scheme
  31. R. Turcajová Construction of Symmetric Biorthogonal Multiwavelets by lifting (ps.gz)
  32. Geoffrey M. Davis, Vasia Strela, Radka Turcajova, Multiwavelet construction via the lifting scheme. (ps.gz)
  33. Fritz Keinert, Raising Multiwavelet Approximation Order Through Lifting. (ps.gz pdf)
  34. S. Bacchelli, M. Cotronei and D. Lazzaro An Algebraic Construction of K-balanced Multiwavelets via the Lifting Scheme

    Back to top

    Lifting and lossless integer transforms
  35. Rob Calderbank, Ingrid Daubechies, Wim Sweldens, and Boon-Lock Yeo, Wavelet Transforms that Map Integers to Integers (ps ps.gz pdf)
  36. Carolyn Johnston, The lifting scheme and finite precision error free filter banks SPIE Vol. 2825, pp. 307-314, 1996.
  37. Hongyang Chao and Paul Fisher, An approach of integer reversible wavelet transform for Image Compression (pdf)
  38. S. Dewitte and J. Cornelis. Lossless integer wavelet transform. ()
  39. N. V. Boulgouris and M. G. Strintzis, Reversible Multiresolution Image Coding Based on Adaptive Lifting.
  40. N. V. Boulgouris, D. Tzovaras and M. G. Strintzis, Lossless Image Compression Based on Optimal Prediction, Adaptive Lifting and Conditional Arithmetic Coding.
  41. Adrian Munteanu, Jan Cornelis, Paul Cristea Wavelet lossy and lossless image compression techniques - use of the lifting scheme.
  42. A. Bezerianos1, A. Munteanu1, P. Cristea, and D. Alexopoulos Wavelet Lossless Compression of Coronary Angiographic Images
  43. Adrian Munteanu, Jan Cornelis, Paul Cristea Wavelet Lossless Compression of Coronary Angiographic Images
  44. M. D. Adams and F. Kossentini. Reversible Integer-to-Integer Wavelet Transforms for Image Compression: Performance Evaluation and Analysis
  45. M. D. Adams and F. Kossentini. On the Relationship Between the Overlapping Rounding Transform and Lifting Frameworks for Reversible Subband Transforms (ps.gz)
  46. M. D. Adams and F. Kossentini. Low-Complexity Reversible Integer-to-Integer Wavelet Transforms for Image Coding,
  47. M. D. Adams and F. Kossentini. Evaluation of Reversible Integer-to-Integer Wavelet Transforms for Image Compression
  48. M. D. Adams and F. Kossentini. Performance Evaluation of Reversible Integer-to-Integer Wavelet Transforms for Image Compression (ps.gz)
  49. M. D. Adams and F. Kossentini. Performance Evaluation of Different Reversible Decorrelating Transforms in the JPEG-2000 Baseline System
  50. M. D. Adams and A. Antoniou. A Multi-Transform Approach to Reversible Embedded Image Compression
  51. M. D. Adams and A. Antoniou. Design of Reversible Subband Transforms Using Lifting
  52. M.D. Adams and A. Antoniou. A Comparison of New Reversible Wavelet Transforms for Image Compression

    Back to top

    Lifting and multivariate/M-band wavelets
  53. Jelena Kovacevic and Wim Sweldens, Wavelet families of increasing order in arbitrary dimensions (ps ps.gz pdf)
  54. G. Uytterhoeven and A. Bultheel. The Red-Black wavelet transform. (ps.gz) This papers describes how to build wavelets on the quincunx filter using lifting.
  55. Gouze, Annabelle; Antonini, Marc; Barlaud, Michel, Quincunx filter lifting scheme for image coding Proc. SPIE Vol. 3653, p. 976-988, 1999
  56. Dirk-Jan Ripmeester, Lifting Multivariate Splines
  57. Damiana Lazzara Biorthogonal M-band filter construction using the lifting scheme.
  58. R. Vargic, Lossy image compression using multidimensional wavelets and Lifting scheme .
  59. Radoslav Vargic, Compression of Static Images Using Wavelet Transform and Lifting Scheme (ps ps.gz)

    Back to top

    Lifting and document compression
  60. Léon Bottou, Steven Pigeon. Lossy Compression of Partially Masked Still Images. (.ps.gz).
  61. Léon Bottou, Patrick Haffner, Paul G. Howard, Patrice Simard, Yoshua Bengio, and Yann Le Cun. High Quality Document Image Compression with DjVu. (.ps.gz).
  62. Léon Bottou, Patrick Haffner, Paul G. Howard, Patrice Simard, Yoshua Bengio, and Yann Le Cun, Browsing through High Quality Document Images with DjVu. (.ps.gz).

    Back to top

    Lifting and multiple descriptions
  63. M. Orchard, Y. Wang, V. Vaishampayan, and A. R. Reibman, Multiple Description Coding Using Pairwise Correlating Transforms. (.ps)
    Lifting and geometric modeling
  64. L. Grisoni, Elements of multiresolution in geometric modeling. (.ps.gz) This Phd Thesis (in French) contains a nice introduction to lifting as well as contains extensions of lifting for splines.

    Back to top

    Other
  65. Alexander Stoffel Remarks on the Unsubsampled Wavelet Transform and the Lifting Scheme
  66. Gabriel Fernández, Multiresolution Feature Extraction using Lifting. (ps.gz)
  67. Naofumi Aoki and Kunio Takaya http://www.citr.ece.uvic.ca/pacrim99/Sessions.html
  68. Senthil Periaswamy Detection of microcalcifications in mammograms using hexagonal wavelets.
  69. M. Jansen, G. Uytterhoeven, and A. Bultheel. Image de-noising by integer wavelet transforms and generalized cross validation.
  70. W. C. Shann and J. Tzeng, A scheme to elevate the degree and regularity of biorthogonal wavelets. ps)
  71. W. C. Shann and J. Tzeng, The levering scheme of biorthogonal wavelets. (ps)
  72. A Tassignon, Wavelets in Image Processing.
  73. G. McDarby, C. Heneghan, and B. G. Celler, Customizing a discrete wavelet transfrom filter bank using the lifting scheme for improved compression ratios of an ECG IEEE Engineering in Medicine and Biology Conference, Atlanta, October 1999.
  74. P. Cristea, R. Tuduce, Primal and dual lifting signal flow graphs
  75. I. Tobor, L. Grisoni and C. Schlick, Extensions of the Lifting Scheme for Spline Edition
  76. Senthil Periaswamy, Construction of Hexagonal Wavelets using the Lifting Scheme
  77. Leif Kobbelt and Peter Schröder, A Multiresolution Framework for Vatiational Subdivision. This paper show how to combine lifting with variational subdivision and allows lifting for certain IIR filters. (pdf)
  78. Tzu-Hung Cheng, Chi-Hau Chen, New image-compression algorithm using wavelet analysis SPIE 3387-05, pp.48-55. This paper proposes a new image compression algorithm based on lifting and a modification of 3D subband coding.
  79. K. Anant, F. Dowla, Wavelet design by linear prediction lifting.
  80. Zou, Ning; Liu, Jian; Zhou, Manli, Range image feature extracting method based on wavelet lifting scheme Proc. SPIE Vol. 3862, p. 573-576, 1999
  81. Shangrong Cai, The Lifting Scheme for Biorthogonal Wavelets.
  82. Corey Chang, Wavelet signal processing of digital audio with applications in electro-acoustic music. Chapter 3 of this thesis talks about using lifting and second generation wavelets for denoising of digital audio.
  83. Clemens P. Valens, The fast lifting wavelet transform and its application to maritime radar image processing

    Back to top

3. Software

  1. LiftPack
    This free C software package was written by Gabriel Fernández, Senthil Periaswamy, and Wim Sweldens at the University of South Carolina. It implements biorthogonal wavelets transforms with boundary treatment for arbitrary size images. It uses the in-place organization of wavelet coefficients. It does not do integer-to-integer computations. There are about 200 beta testers of LiftPack. Details are described in the paper LIFTPACK: A Software Package for Wavelet Transforms using Lifting (G. Fernández, S. Periaswamy, W. Sweldens)
    Liftpack home page

  2. WAILEE
    WAILI is a free C++ wavelet transform library that uses integer wavelet transforms based on the lifting scheme. It includes some basic image processing operations and forms the backbone of more complex image processing operations. This software package was written by Geert Uytterhoeven, Filip Van Wulpen, and Maarten Jansen at the Department of Computer Science of the Katholieke Universiteit Leuven, Belgium. Details are described in the paper WAILI: Wavelets with Integer Lifting. (G. Uytterhoeven, F. Van Wulpen, M. Jansen, D. Roose, and A. Bultheel).
    WAILEE home page

  3. SD: Spherical Wavelet Transforms
    SD is a free C++ software package for displaying and manipulating subdivision structures. The software is built on the Open Inventor library. It has the capability to perform and interactively display wavelet transforms of spherical data sets. This package grew out of software written by Peter Schröder and Wim Sweldens for wavelets on the sphere.
    SD Home page.

  4. MT-WICE Photo
    Mt-Wice Photo is a tool for image compression which uses the lifting scheme. It claims better quality than JPEG and many other wavelet based image compression products.
    MT-WICE Photo homepage

  5. JPEG 2000 Wavelet Demo using lifting
    This Java applet implements a forward and backward wavelet transform defined in the MPEG4 standard Version 1 (ISO/IEC JTC/SC29/WG11 N1902, Fribourg, Oct. 1997, Paragraph 10 Annex A Coding transforms). The wavelet transform is implemented by means of the lifting scheme.

  6. The lifting applet
    Mike Astle and Dae Kung at Caltech wrote a very nice applet illustrating the principle of lifting. Source code available.
    The lifting applet

  7. Roger Claypoole matlab lifting programs
    Roger Clayporl wrote a number of Matlab routines for lifting both for predict first and update first.

  8. ATT's DjVU
    DjVU is a document compression method developed at ATT that works 5 to 10 times better than JPEG. It is based on lifting. Roger
    DvVU home page (demo, papers, downloads)
Back to top

4. Hardware

  1. ESA chip
    ESA (European Space Agency) is developing space qualified data compression chipsusing a compression algorithm partially based on lifting. This concept has been submitted for CCSDS standardisation.
    ESA chip
  2. Versatility Stressmark Initial Implementation Specification
    A lifting based hardware implementation of a video encoder. HSRA
  3. E-vue E-vue is a spinoff from the Sarnoff that produces MPEG4 compliant technology developed by the Multimedia Technology Lab at Sarnoff. They are looking at implementing the lifting algorithm for the still image encoder and decoder and a product based on this should be coming out at the end of the year. E-vue
Back to top

5. Books on or with sections on lifting

  1. Ripples in Mathematics This elementary book gives an easy read introduction to wavelets entirely based on lifting. It grew out of notes aimed at students at the engineering colleges in Denmark. The only required background is high school mathematics.
  2. A Wavelet Tour of Signal Processing (Stephane Mallat).
    Section 7.4.4 gives a very nice overview of lifting including some of the second generation stuff.
  3. Introduction to Wavelets and Wavelet Transforms: A Primer (C. Sidney Burrus, Ramesh A. Gopinath, and Haitao Guo).
    Section 7.3 contains a short introduction to lifting with several examples.
  4. The World According to Wavelets (Barbara Hubbard).
    Chapter 19 of the second editions contains a short, but very nice non mathematical description of lifting and second generation wavelets.
  5. Wavelets and Filter Banks and Matlab software (Gilbert Strang and Truong Nguyen).
    In the original edition, Section 6.5 briefly describes lifting. The new edition has an entire appendix (D) on lifting. It contains a beautiful introduction in the typical very readable "Strang" style.
  6. Wavelets for Computer Graphics:Theory and Applications (Eric Stollnitz, Tony DeRose, and David Salesin).
    Section 7.4.4 contains a brief description of lifting and dual lifting. Caution: The term "lazy wavelet" use used here in a different way than usual. Normally the lazy wavelet transform is the one that splits samples into "even" and "odd", i.e., subsampling. Here lazy is used for a transform that consists of only one predict step.
  7. Linear Algebra, Rational Approximation and Orthogonal Polynomials (A. Bultheel and M. Van Barel).
    Section 8.4 talks about the lifting scheme.
Back to top

6. Web links

Back to top

7. Connection with other methods and predecessors of lifting

The lifting scheme was developed in 1994 inspired by the work of Donoho on interpolating wavelets and the work of Lounsbery, Warren, & Derose on multiresolution surfaces. Since then many connections between lifting and other methods (some of them much older than 94) have been established. The lifting scheme relies fundamentally on a simple algebraic property concerning the inverse of matrices with a certain block structure:
  [ I A ]  [ I  -A]     [ I 0 ] 
  [ 0 I ]  [ 0   I]  =  [ 0 I ]. 
It is clear that the algebra behind lifting is not novel and has been used in very many algorithms before the word lifting was even coined in 1994. In fact the algebraic structure behind lifting can be traced back to the 2000 year old Euclidean algorithm. As usual, nil nove sub sole. The only novelty that can be claimed is the insight that this structure can be used to build second generation and nonlinear wavelet transforms. In this section we give an overview of other methods that are closely related to lifting. An interesting aspect is that while we now know that all these papers can be seen as predecessors to lifting, most of them were written independently.
Wim Sweldens