Recursive fast computation of the two-dimensional discrete cosine transform
Resource
Vision, Image and Signal Processing, IEE Proceedings-
Journal
Vision, Image and Signal Processing, IEE Proceedings-
Pages
-
Date Issued
1999-02
Date
1999-02
Author(s)
Fang, W.H.
Hu, N.C.
Shih, S.K.
DOI
1350-245X
Abstract
An efficient algorithm is presented for computing the two-dimensional discrete cosine transform (2-D DCT) whose size is a power of a prime. Based on a generalised 2-D to one-dimensional (1-D) index mapping scheme, the proposed algorithm decomposes the 2-D DCT outputs into three parts. The first part forms a 2-D DCT of a smaller size. The remaining outputs are further decomposed into two parts, depending on the summation of their indices. The latter two parts can be reformulated as a set of circular correlation (CC) or skew-circular correlation (SCC) matrix–vector products by utilising the recently addressed maximum coset decomposition. Such a decomposition procedure can be repetitively carried out for the 2-D DCT of the first part, resulting in a sequence of CC and SCC matrix–vector products of various sizes. Employing fast algorithms for the computation of these CC/SCC operations can substantially reduce the numbers of multiplications compared with those of the conventional row–column decomposition approach. In the special case where the data size is a power of two, the proposed algorithm can be further simplified, calling for computations comparable with those of previous works.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
00766330.pdf
Size
756.7 KB
Format
Adobe PDF
Checksum
(MD5):38b73672268e9690d766e75e61a3a155