 Any discrete wavelet transform with finite filters can be decomposed into a finite sequence of simple filtering steps (lifting steps). This decomposition corresponds to a factorization of the polyphase matrix of the wavelet filters into elementary matrices. The decomposition asymptotically reduces the computational complexity of the transform by a factor two. The lifting scheme allows the construction of an integer version of every wavelet transform. The decomposition was introduced by W. Sweldens. Until recently, all studies dealing with the two-dimensional discrete wavelet transform (DWT) considered only separable calculation schedules — the convolution and lifting schemes. Besides these, there are many other schemes. For example, the polyconvolution scheme falls right between the convolution and lifting. Moreover, corresponding separable parts can be merged into joint non-separable units, which halves the number of steps. An optimization strategy then leads to a reduction in the number of arithmetic operations. The non-separable schemes outperform their separable counterparts in cases where an exchange of intermediate results is expensive. This family of second-generation wavelets is constructed using a robust data-prediction lifting scheme. The support of these wavelets is constructed based on the edge content of the image and avoids having pixels from both sides of an edge. Multi-resolution analysis, based on these new edge-avoiding wavelets, shows a better decorrelation of the data compared to common linear translation-invariant multi-resolution analyses. The wavelets allow nonlinear data-dependent multi-scale edge-preserving image filtering and processing at computation times which are linear in the number of image pixels. The new wavelets encode, in their shape, the smoothness information of the image at every scale. This decomposition was introduced by R. Fattal. Classical one-dimensional wavelet transforms can be extended to more dimensions using tensor products, yielding a separable multi-dimensional transform. A disadvantage of this technique is the introduction of an anisotropy in the wavelet decomposition. In the two-dimensional case, a tensor product wavelet transform will favor horizontal, vertical and diagonal features of the original data. The red-black wavelet transform is a kind of second generation wavelets on a rectangular grid — more specifically, on a quincunx lattice — constructed using the lifting scheme. This transform was introduced by G. Uytterhoeven.
X-lets X-lets are directional or geometric extensions of the two-dimensional wavelet concept. They allow an almost optimal non-adaptive sparse representation of objects with edges. Some of these transforms require non-separable operations; some of them are highly redundant. The others are separable or critically sampled. The X-lets comprises steerable wavelets, curvelets, contourlets, shearlets, wedgelets, beamlets, bandlets, wave atoms, and many others.