Comparative performance evaluation of algorithms for fast computation of the two-dimensional DCT

The implementation of the two-dimensional discrete cosine transform (2D DCT) through the multiple one-dimensional (row-by-column approach) and the direct 2D DCT is studied. It is observed that the execution times on different computer architectures using one-dimensional (1D) algorithms vary significantly although some of the examined algorithms have the same computational complexity (additions and multiplications). The direct 2D DCT outperforms all row-by-column approaches. In addition, the vector-radix pruning method is compared to the row-column pruning method. Properties and advantages of some of the algorithms are also discussed. We have been unable to find in the literature an evaluation of the execution time of the 2D fast cosine transforms (FCT's) as a function of sequence length, when implemented on different computer architectures. This information is extremely useful for choosing an algorithm and a computer that will be used primarily t