New polynomial transform algorithm for multidimensional DCT

A new algorithm for the type-II multidimensional discrete cosine transform (MD-DCT) is proposed. Based on the polynomial transform, the rD-DCT with size N-1 X N-2 X ... X N-r, where N-i is a power of 2, can be converted into a series of one-dimensional (I-D) discrete cosine transforms (DCTs), The algorithm achieves considerable savings on the number of operations compared with the row-column method. For example, the number of multiplications for computing an r-dimensional DCT is only 1/r times that needed by the row-column method, and the number of additions is also reduced. Compared with other known polynomial transform algorithms for 2D-DCT and the most recently presented algorithm for MD-DCT, the proposed one uses about the same number of operations. However, advantages such as better computational structure and flexibility in the choice of dimensional sizes can be achieved.