Discrete cosine transform

The discrete cosine transform (DCT) is a Fourierrelated transform similar to the discrete Fourier transform (DFT), but using only real numbers. It is equivalent to a DFT of roughly twice the length, operating on real data with even symmetry (since the Fourier transform of a real and even function is real and even), where in some variants the input and/or output data are shifted by half a sample. (There are eight standard variants, of which four are common.)
The most common variant of discrete cosine transform is the typeII DCT, which is often called simply "the DCT"; its inverse, the typeIII DCT, is correspondingly often called simply "the inverse DCT" or "the IDCT".
Two related transforms are the discrete sine transform (DST), which is equivalent to a DFT of real and odd functions, and the modified discrete cosine transform (MDCT), which is based on a DCT of overlapping data.
Contents 
Applications
The DCT, and in particular the DCTII, is often used in signal and image processing, especially for lossy data compression, because it has a strong "energy compaction" property: most of the signal information tends to be concentrated in a few lowfrequency components of the DCT, approaching the KarhunenLoève transform (which is optimal in the decorrelation sense) for signals based on certain limits of Markov processes.
For example, the DCT is used in JPEG image compression, MJPEG video compression, and MPEG video compression. There, the twodimensional DCTII of 8x8 blocks is computed and the results are quantized and entropy coded. In this case, n is typically 8 and the DCTII formula is applied to each row and column of the block. The result is an 8x8 transform coefficient array in which the (0,0) element is the DC (zerofrequency) component and entries with increasing vertical and horizontal index values represent higher vertical and horizontal spatial frequencies.
A related transform, the modified discrete cosine transform, or MDCT, is used in AAC, Vorbis, and MP3 audio compression.
DCTs are also widely employed in solving partial differential equations by spectral methods, where the different variants of the DCT correspond to slightly different even/odd boundary conditions at the two ends of the array.
Formal definition
Formally, the discrete cosine transform is a linear, invertible function F : R^{n} > R^{n} (where R denotes the set of real numbers), or equivalently an n × n square matrix. There are several variants of the DCT with slightly modified definitions. The n real numbers x_{0}, ..., x_{n1} are transformed into the n real numbers f_{0}, ..., f_{n1} according to one of the formulas:
DCTI
 <math>f_j = \frac{1}{2} (x_0 + (1)^j x_{n1})
+ \sum_{k=1}^{n2} x_k \cos \left[\frac{\pi}{n1} j k \right]<math>
Some authors further multiply the x_{0} and x_{n1} terms by √2, and correspondingly multiply the f_{0} and f_{n1} terms by 1/√2. This makes the DCTI matrix orthogonal (up to a scale factor), but breaks the direct correspondence with a realeven DFT.
A DCTI of n=5 real numbers abcde is exactly equivalent to a DFT of eight real numbers abcdedcb (even symmetry), here divided by two. (In contrast, DCT types IIIV involve a halfsample shift in the equivalent DFT.) Note, however, that the DCTI is not defined for n less than 2. (All other DCT types are defined for any positive n.)
Thus, the DCTI corresponds to the boundary conditions: x_{k} is even around k=0 and even around k=n1; similarly for f_{j}.
DCTII
 <math>f_j =
\sum_{k=0}^{n1} x_k \cos \left[\frac{\pi}{n} j \left(k+\frac{1}{2}\right) \right]<math>
The DCTII is probably the most commonly used form, and is often simply referred to as "the DCT".
Some authors further multiply the f_{0} term by 1/√2 (see below for the corresponding change in DCTIII). This makes the DCTII matrix orthogonal (up to a scale factor), but breaks the direct correspondence with a realeven DFT of halfshifted input.
The DCTII implies the boundary conditions: x_{k} is even around k=1/2 and even around k=n1/2; f_{j} is even around j=0 and odd around j=n.
DCTIII
 <math>f_j = \frac{1}{2} x_0 +
\sum_{k=1}^{n1} x_k \cos \left[\frac{\pi}{n} \left(j+\frac{1}{2}\right) k \right]<math>
Because it is the inverse of DCTII (up to a scale factor, see below), this form is sometimes simply referred to as "the inverse DCT" ("IDCT").
Some authors further multiply the x_{0} term by √2 (see above for the corresponding change in DCTII). This makes the DCTIII matrix orthogonal (up to a scale factor), but breaks the direct correspondence with a realeven DFT of halfshifted output.
The DCTIII implies the boundary conditions: x_{k} is even around k=0 and odd around k=n; f_{j} is even around j=1/2 and odd around j=n1/2.
DCTIV
 <math>f_j =
\sum_{k=0}^{n1} x_k \cos \left[\frac{\pi}{n} \left(j+\frac{1}{2}\right) \left(k+\frac{1}{2}\right) \right]<math>
The DCTIV matrix is orthogonal (up to a scale factor).
A variant of the DCTIV, where data from different transforms are overlapped, is called the modified discrete cosine transform (MDCT).
The DCTIV implies the boundary conditions: x_{k} is even around k=1/2 and odd around k=n1/2; similarly for f_{j}.
DCT VVIII
DCT types IIV are equivalent to realeven DFTs of even order. In principle, there are actually four additional types of discrete cosine transform (Martucci, 1994), corresponding to realeven DFTs of logically odd order, which have factors of n+1/2 in the denominators of the cosine arguments. However, these variants seem to be rarely used in practice.
(The trivial realeven array, a lengthone DFT (odd length) of a single number a, corresponds to a DCTV of length n=1.)
Inverse transforms
The inverse of DCTI is DCTI multiplied by 2/(n1). The inverse of DCTIV is DCTIV multiplied by 2/n. The inverse of DCTII is DCTIII multiplied by 2/n (and vice versa).
Like for the DFT, the normalization factor in front of these transform definitions is merely a convention and differs between treatments. For example, some authors multiply the transforms by <math>\sqrt{2/n}<math> so that the inverse does not require any additional multiplicative factor.
Computation
Although the direct application of these formulas would require O(n^{2}) operations, as in the fast Fourier transform (FFT) it is possible to compute the same thing with only O(n log n) complexity by factorizing the computation. (One can also compute DCTs via FFTs combined with O(n) pre and postprocessing steps.)
References
 K. R. Rao and P. Yip, Discrete Cosine Transform: Algorithms, Advantages, Applications (Academic Press, Boston, 1990).
 A. V. Oppenheim, R. W. Schafer, and J. R. Buck, DiscreteTime Signal Processing, second edition (PrenticeHall, New Jersey, 1999).
 S. A. Martucci, "Symmetric convolution and the discrete sine and cosine transforms," IEEE Trans. Sig. Processing SP42, 10381051 (1994).
 Matteo Frigo and Steven G. Johnson: FFTW, http://www.fftw.org/. A free (GPL) C library that can compute fast DCTs (types IIV) in one or more dimensions, of arbitrary size. Also M. Frigo and S. G. Johnson, "The Design and Implementation of FFTW3 (http://fftw.org/fftwpaperieee.pdf)," Proceedings of the IEEE 93 (2), 216231 (2005).
External link
fr:Transforme en cosinus discret ko:이산 코사인 변환 pl:Dyskretna transformata kosinusowa th:การแปลงโคไซน์ไม่ต่อเนื่อง