The Discrete Cosine Transform and Its Impact on Visual Compression: Fifty Years From Its Invention

Compression is essential for efficient storage and transmission of signals. One powerful method for compression is through the application of orthogonal transforms, which convert a group of N data samples into a group of N transform coefficients. In transform coding, the N samples are first transformed, and then the coefficients are individually quantized and entropy coded into binary bits. The transform serves two purposes: one is to compact the energy of the original N samples into coefficients with increasingly smaller variances so that removing smaller coefficients have negligible reconstruction errors, and another is to decorrelate the original samples so that the coefficients can be quantized and entropy coded individually without losing compression performance. The Karhunen–Loève transform (KLT) is an optimal transform for a source signal with a stationary covariance matrix in the sense that it completely decorrelates the original samples, and that it maximizes energy compaction (i.e., it requires the fewest number of coefficients to reach a target reconstruction error). However, the KLT is signal dependent and cannot be computed with a fast algorithm.

Compression is essential for efficient storage and transmission of signals. One powerful method for compression is through the application of orthogonal transforms, which convert a group of N data samples into a group of N transform coefficients. In transform coding, the N samples are first transformed, and then the coefficients are individually quantized and entropy coded into binary bits. The transform serves two purposes: one is to compact the energy of the original N samples into coefficients with increasingly smaller variances so that removing smaller coefficients have negligible reconstruction errors, and another is to decorrelate the original samples so that the coefficients can be quantized and entropy coded individually without losing compression performance. The Karhunen–Loève transform (KLT) is an optimal transform for a source signal with a stationary covariance matrix in the sense that it completely decorrelates the original samples, and that it maximizes energy compaction (i.e., it requires the fewest number of coefficients to reach a target reconstruction error). However, the KLT is signal dependent and cannot be computed with a fast algorithm.

In January 1974, Ahmed et al. published an article titled “The Discrete Cosine Transform” (DCT) [1]. This seminal article introduced a signal-independent transform, called the DCT, which uses real basis functions from the family of discrete Chebyshev polynomials. The DCT was shown, via numerical examples, to have an energy compaction performance almost as good as the KLT, superior to other well-known signal-independent transforms including the discrete Fourier transform (DFT), Haar transform, and Walsh–Hadamard transform for signals that can be modeled as a first-order Markov process with a correlation coefficient close to one. Furthermore, if the source can be modeled as a Gaussian process, the DCT leads to a rate-distortion bound similar to using the KLT, lower than the DFT. The article also showed that the N point DCT can be obtained from the real part of a modified 2N point DFT of the zero-extended signal, and thus can be computed efficiently using the fast Fourier transform (FFT) algorithm. The basic research work and events that led to the development of the DCT were summarized in an article titled “How I Came Up With the Discrete Cosine Transform,” by Ahmed in 1991 [2], which reveals that the DCT was first conceived by him in 1972. The DCT was also introduced in a book coauthored by Ahmed and Rao [3].