The LiftLT: fast lapped transforms via lifting steps

This paper introduces a class of multi-band linear phase lapped biorthogonal transforms with fast, VLSI-friendly implementations via lifting steps called the LiftLT. The transform is based on a lattice structure which robustly enforces both linear phase and perfect reconstruction properties. The lattice coefficients are parameterized as a series of lifting steps, providing fast, efficient in-place computation of the transform coefficients. Our main motivation of the new transform is its application in image and video coding. Comparing to the popular 8×8 DCT, the 8×16 LiftLT only requires 1 more multiplication, 22 more additions, and 6 more shifting operations. However, image coding examples show that the LiftLT is far superior than the DCT in both objective and subjective coding performance. Thanks to properly designed overlapping basis functions, the LiftLT can completely eliminate annoying blocking artifacts. In fact, the novel LT´s coding performance consistently surpasses that of the much more complex 9/7-tap biorthogonal wavelet with floating-point coefficients. More importantly, the transform´s block-based nature facilitates one-pass sequential block coding, region-of-interest coding/decoding as well as parallel processing.