Theory and Algorithms of Biorthogonal Wavelet Transform Based on Lifting Scheme 
Abstract: 
Factorization of polyphase matrix with a finite filter provides a simple method for deriving the sequence of lifting steps of the corresponding wavelet transform. Because the factorization is fundamentally nonunique, there exist several possible sequences of lifting steps for a given wavelet transform. For a given purpose, how to find a good factorization is still an open problem. A separable twodimensional wavelet transform performs on an image with N rows and N columns as 2N onedimensional signal. Traditionally, its liftingbased implementation does as the same way. Therefore, it is still a challenge to devise a more efficient implementation, which can make full use of correlation between image pixels to reduce its computational number. How to find a wavelet transform, which is similar to separable twodimensional wavelet transform, but possesses higher compression performance? We investigate the theory and algorithms of biorthogonal wavelet transform systematically and deeply, and propose methods to solve the abovementioned problems. Our main contributions include: 
1. For any symmetric biorthogonal filter, how to find a good factorization of a polyphase matrix in the lowest computational complexity is given. Division algorithm for symmetric Laurent polynomials and Euclidean algorithm for finding the greatest common factor for two symmetric Laurent polynomials are given and proved, which are used to find the symmetric factorization of a polyphase matrix and prove its uniqueness for any biorthogonal low pass filter. A general algorithm of symmetric factorization of polyphase matrix with a finite filter is given. Then, a basic algorithm of symmetric factorization of polyphase matrix with a finite biorthogonal filter is proposed, and its efficient algorithm is presented. The symmetric factorization leads to a liftingbased implementation of the biorthogonal wavelet transform. It is proved that the implementation has the lowest computational complexity in all factorizations, and it is equivalent to a matrix transform on finite dimensional vector space. 2. Based on the above optimum factorization, a twodimensional lifting scheme of separable twodimensional wavelet transform is devised, so that, in comparison with the traditional liftingbased implementation of separable twodimensional wavelet transform, its multiplication number is reduced greatly. Based on the symmetric factorization of polyphase matrix and its corresponding liftingbased implementation of biorthogonal wavelet transform, matrix representations of onedimensional wavelet transform and separable twodimensional wavelet transform are given. Furthermore, by analyzing the matrix representation, we propose a novel twodimensional lifting scheme of biorthogonal wavelet transform and its corresponding twodimensional integer wavelet transform, where the twodimensional integer wavelet transform is different from that constructed traditionally by onedimensional integer wavelet transform. The algorithms are essentially based on onedimensional filter but operated in twodimensional space directly, which are different from the implementations of traditional separable twodimensional wavelet transform and nonseparable twodimensional wavelet transform. In comparison with traditional separable twodimensional wavelet transform, their multiplication number is reduced greatly. Experiments on DEM image indicate that, for the popular (53) filter, the 2D integer wavelet transform can achieves a little better compression than the classical one. 3. Fast method to compute tensor product 2d wavelet transforms is presented. There exist two types of twodimensional wavelet transform: tensor product 2D wavelet transform and the usual 2D wavelet transform (i.e. separable twodimensional wavelet transform). L level tensor product 2D wavelet transform means that L level onedimensional wavelet transform is applied to every line of an image, then, applied to its every column, where L is any nonnegative integer. In contrast to the tensor product 2D wavelet transform, the usual 2D wavelet transform alternates between row and column of an image, i.e. onedimensional wavelet transform is first applied successively to every line of the image, and then successively to its every column; this procedure produces a fourband structure corresponding to low and high horizontal and vertical frequencies. The fourband decomposition is then recursively applied to the subband with low horizontal and low vertical frequencies. Both tensor product 2D wavelet transform and the usual 2D wavelet transform can be implemented directly by using lifting scheme, but as our knowledge, the relationship between them has not been discussed and published. Through matrix analysis method, we present a method to compute tensor product 2D wavelet transform efficiently by using the usual 2D wavelet transforms and 1D wavelet transforms.

References: 

[返回] 