**Discrete
Cosine Transform (DCT)**

¡@

The DCT is an orthonormal transform

**y
= Cx ; x = C**^{-1}**y**

defined by [Ahmed, Natarajan and Rao, 1974] [Ahmed and Rao, 1975]

Note that correct to a scaling factor, forward and backward (inverse) transforms have identical transformation kernels. The last equation shows that the basis vectors are sampled cosines which have phase shifts that are not given by an alternating 0 and pattern as in (the sines and cosines of) DFT. The DCT basis vectors are

The attractiveness of the DCT is two-fold : (a) it is nearly optimal with high positive values of adjacent-sample correlation, and (b) it can be computed via the DFT using an FFT algorithm [Ahmed and Rao, 1975] [Chen, Smith and Fralick, 1976] [Elliott and Rao, 1982].

The fast computation
procedure mentioned in (b) consists of extending the input block
of *N* samples to a 2*N*-block with even symmetry,
taking a 2*N*-point DFT, and saving *N* terms in
it. The DFT of a real and symmetric sequence contains only real
coefficients corresponding to the cosine terms of the series. The
extension is defined as

as shown in Figure
TC.3.1.1. The 2*N*-DFT of *x'*(*n*) is

By comparing it with *y(k)*,
it can be seen that

Notice that periodic
extensions which are inherent in DFT operations have smaller
end-effects (caused by discontinuity at the border of one block
and its repetition) in the case of the 2*N*-extension than
DFT operations based on the *N*-block. In DFT, quanization
effects case an exchange of distortion components between the
left and right boundaries. In DCT, such an exchange does not
occur [Tribolet and Crochiere, 1979].

**Figure
TC.3.1.1 **Illustration of end effects in DFT and DCT :
(a) input block of length of *N* ; (b) end effects in DFT
analysis/synthesis; (c) equivalent 2*N*-point data block
for DCT; and (d) end effects in DCT analysis/synthesis [Tribolet
and Crochiere, 1979, IEEE].

¡@

From the
above discussion, it also follows that the DCT can be obtained
with 2*N* log_{2}*N* multiply-add
operations. Slightly more efficient procedures are described in
the literature [Chen, Smith and Fralick, 1976] [Wang, 1983].

¡@

**Two-Dimensional
DCT**

In two dimensions, the DCT can be expressed in the form [Pratt, 1978] [Gonzalez and Wintz, 1977]

where *x*(*m,n*)
is a *N* ¡Ñ*N* field, *k, l, m, n* all range
from 0 to *N*-1. Note that the transformation kernels are
separable, so that the 2-D DCT can be conveniently performed in
two steps, each of which involves a 1-D DCT. As in the
one-dimensional case (Figure TC.3.1.1), DCT coding with an even
symmetry end extension has fewer edge-effect problems than DFT
image coding.