An algorithm for a fast two-dimensional discrete cosine transform

The authors present an algorithm for the implementation of the two-dimensional discrete cosine transform (DCT) for 2ⁿ×2ⁿ data points. This algorithm is based on a recently published fast one-dimensional DCT algorithm. The new algorithm is recursive, fast, and numerically stable. The two-dimensional decomposition in this new algorithm is based on the vector-radix approach. In this approach, the data matrix is partitioned into four subblocks, each of which, after some processing is transformed by a lower order DCT. The results from the lower order transforms are then combined to form the desired two-dimensional DCT. The overall complexity of the new transform is compared in terms of the number of multiplications and additions required to perform the two-dimensional DCT with those of a row/column implementation using the fast one-dimensional transform