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 non-unique, 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 two-dimensional wavelet transform performs on an image with N rows and N columns as 2N one-dimensional signal. Traditionally, its lifting-based 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 two-dimensional 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 above-mentioned 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 lifting-based 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 two-dimensional lifting scheme of separable two-dimensional wavelet transform is devised, so that, in comparison with the traditional lifting-based implementation of separable two-dimensional wavelet transform, its multiplication number is reduced greatly.

Based on the symmetric factorization of polyphase matrix and its corresponding lifting-based implementation of biorthogonal wavelet transform, matrix representations of one-dimensional wavelet transform and separable two-dimensional wavelet transform are given.

Furthermore, by analyzing the matrix representation, we propose a novel two-dimensional lifting scheme of biorthogonal wavelet transform and its corresponding two-dimensional integer wavelet transform, where the two-dimensional integer wavelet transform is different from that constructed traditionally by one-dimensional integer wavelet transform. The algorithms are essentially based on one-dimensional filter but operated in two-dimensional space directly, which are different from the implementations of traditional separable two-dimensional wavelet transform and non-separable two-dimensional wavelet transform. In comparison with traditional separable two-dimensional wavelet transform, their multiplication number is reduced greatly.

Experiments on DEM image indicate that, for the popular (5-3) filter, the 2D integer wavelet transform can achieves a little better compression than the classical one.

3. Fast method to compute tensor product 2-d wavelet transforms is presented.

There exist two types of two-dimensional wavelet transform: tensor product 2-D wavelet transform and the usual 2-D wavelet transform (i.e. separable two-dimensional wavelet transform). L level tensor product 2-D wavelet transform means that L level one-dimensional wavelet transform is applied to every line of an image, then, applied to its every column, where L is any non-negative integer. In contrast to the tensor product 2-D wavelet transform, the usual 2-D wavelet transform alternates between row and column of an image, i.e. one-dimensional wavelet transform is first applied successively to every line of the image, and then successively to its every column; this procedure produces a four-band structure corresponding to low and high horizontal and vertical frequencies. The four-band decomposition is then recursively applied to the subband with low horizontal and low vertical frequencies. Both tensor product 2-D wavelet transform and the usual 2-D 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 2-D wavelet transform efficiently by using the usual 2-D wavelet transforms and 1-D wavelet transforms.