A new two-dimensional fast cosine transform algorithm

Abstract

A novel algorithm for computing the two-dimensional discrete cosine transform (2-D DCT) is presented. It is based on a one-dimensional fast cosine transform (1-D FCT) algorithm. Instead of computing the 2-D transform using the row-column method, the 1-D algorithm is extended by means of the vector-radix approach. Derivation based on both the sequence splitting and Kronecker matrix product method are discussed. The sequence splitting approach has the advantage that all the underlying operations are shown clearly, while the matrix product representations are more compact and readily generalized to higher dimensions. The bit reversal operations are placed before the recursive additions so that the recursive operations can be performed in a very regular manner. This greatly simplifies the indexing problem in the software implementation of the algorithms. The complexity of the proposed algorithm is described. The vector-radix algorithm saves 25% multiplications as compared with the row-column method.