Fast Algorithms for Multidimensional DCT-to-DCT Computation Between a Block and Its Associated Subblocks

摘要

In this paper, we first propose an efficient algorithm for computing one-dimensional (1-D) discrete cosine transform (DCT) for a signal block, given its two adjacent subblocks in the DCT domain and then introduce several algorithms for the fast computation of multidimensional (m-D) DCT with size N_(1) X N_(2) X ... X N_(m) given 2~(m) subblocks of DCT coefficients with size N_(1)/2 X N_(2)/2 X ... X N_(m)/2, where N_(i)(i velence 1, 2,..., m) are powers of 2. Obviously, the row-column method, which employs the most efficient algorithms along each dimension, reduces the computational complexity considerably, compared with the traditional method, which employs only the one-dimensional (1-D) fast DCT and inverse DCT (IDCT) algorithms. However, when m >= 2, the traditional method, which employs the most efficient multidimensional DCT/IDCT algorithms, has lower computational complexity than the row-column method. Besides, we propose a direct method by dividing the data into 2~(m) parts for independent fast computation, in which only two steps of r-dimensional (r velence 1, 2,..., m) IDCT and additional multiplications and additions are required. If all the dimensional sizes are the same, the number of multiplications required for the direct method is only (2~(m) - 1)/m2~(m-1) times of that required for the row-column method, and if N >= 2~(2~(m-1)), the computational efficiency of the direct method is surely superior to that of the traditional method, which employs the most efficient multidimensional DCT/IDCT algorithms.