Discrete cosine transform

From Free net encyclopedia

Image:Phalaenopsis fft dct.png

The discrete cosine transform (DCT) is a Fourier-related 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 type-II DCT, which is often called simply "the DCT"; its inverse, the type-III 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 1 Applications 2 Formal definition 2.1 DCT-I 2.2 DCT-II 2.3 DCT-III 2.4 DCT-IV 2.5 DCT V-VIII 3 Inverse transforms 4 Computation 5 Notes 6 References 7 External links

Applications

The DCT, and in particular the DCT-II, 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 low-frequency components of the DCT, approaching the Karhunen-Loève transform (which is optimal in the decorrelation sense) for signals based on certain limits of Markov processes.

For example, a DCT is used in JPEG image compression, MJPEG, MPEG, and DV video compression. There, the two-dimensional DCT-II of N × N blocks is computed and the results are quantized and entropy coded. In this case, N is typically 8 and the DCT-II formula is applied to each row and column of the block. The result is an 8 × 8 transform coefficient array in which the (0,0) element is the DC (zero-frequency) component and entries with increasing vertical and horizontal index values represent higher vertical and horizontal spatial frequencies.

Image:Example dft dct.svg

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.

DCTs are also closely related to Chebyshev polynomials, and fast DCT algorithms (below) are used in Chebyshev approximation of arbitrary functions by series of Chebyshev polynomials, for example in Clenshaw-Curtis quadrature.

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₀, ..., x_N-1 are transformed into the N real numbers X₀, ..., X_N-1 according to one of the formulas:

DCT-I

<math>X_k = \frac{1}{2} (x_0 + (-1)^k x_{N-1})

+ \sum_{n=1}^{N-2} x_n \cos \left[\frac{\pi}{N-1} n k \right]</math>

Some authors further multiply the x₀ and x_N-1 terms by √2, and correspondingly multiply the X₀ and X_N-1 terms by 1/√2. This makes the DCT-I matrix orthogonal (up to a scale factor), but breaks the direct correspondence with a real-even DFT.

The DCT-I is exactly equivalent (up to an overall scale factor of 2), to a DFT of <math>2N-2</math> real numbers with even symmetry. For example, a DCT-I of N=5 real numbers abcde is exactly equivalent to a DFT of eight real numbers abcdedcb (even symmetry), divided by two. (In contrast, DCT types II-IV involve a half-sample shift in the equivalent DFT.)

Note, however, that the DCT-I is not defined for N less than 2. (All other DCT types are defined for any positive N.)

Thus, the DCT-I corresponds to the boundary conditions: x_n is even around n=0 and even around n=N-1; similarly for X_k.

DCT-II

<math>X_k =

\sum_{n=0}^{N-1} x_n \cos \left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) k \right]</math>

The DCT-II is probably the most commonly used form, and is often simply referred to as "the DCT".

This transform is exactly equivalent (up to an overall scale factor of 2) to a DFT of <math>4N</math> real inputs of even symmetry where the even-indexed elements are zero. That is, it is half of the DFT of the <math>4N</math> inputs <math>y_n</math>, where <math>y_{2n}=0</math>, <math>y_{2n+1} = x_n</math> for <math>0 \leq n < N</math>, and <math>y_{4N-n}=y_n</math> for <math>0 < n < 2N</math>.

Some authors further multiply the X₀ term by 1/√2 (see below for the corresponding change in DCT-III). This makes the DCT-II matrix orthogonal (up to a scale factor), but breaks the direct correspondence with a real-even DFT of half-shifted input.

The DCT-II implies the boundary conditions: x_n is even around n=-1/2 and even around n=N-1/2; X_k is even around k=0 and odd around k=N.

DCT-III

<math>X_k = \frac{1}{2} x_0 +

\sum_{n=1}^{N-1} x_n \cos \left[\frac{\pi}{N} n \left(k+\frac{1}{2}\right) \right]</math>

Because it is the inverse of DCT-II (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₀ term by √2 (see above for the corresponding change in DCT-II). This makes the DCT-III matrix orthogonal (up to a scale factor), but breaks the direct correspondence with a real-even DFT of half-shifted output.

The DCT-III implies the boundary conditions: x_n is even around n=0 and odd around n=N; X_k is even around k=-1/2 and odd around k=N-1/2.

DCT-IV

<math>X_k =

\sum_{n=0}^{N-1} x_n \cos \left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) \left(k+\frac{1}{2}\right) \right]</math>

The DCT-IV matrix is orthogonal (up to a scale factor).

A variant of the DCT-IV, where data from different transforms are overlapped, is called the modified discrete cosine transform (MDCT).

The DCT-IV implies the boundary conditions: x_n is even around n=-1/2 and odd around n=N-1/2; similarly for X_k.

DCT V-VIII

DCT types I-IV are equivalent to real-even DFTs of even order. In principle, there are actually four additional types of discrete cosine transform (Martucci, 1994), corresponding to real-even 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 real-even array, a length-one DFT (odd length) of a single number a, corresponds to a DCT-V of length N=1.)

Inverse transforms

The inverse of DCT-I is DCT-I multiplied by 2/(N-1). The inverse of DCT-IV is DCT-IV multiplied by 2/N. The inverse of DCT-II is DCT-III 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²) operations, it is possible to compute the same thing with only O(N log N) complexity by factorizing the computation similar to the fast Fourier transform (FFT). One can also compute DCTs via FFTs combined with O(N) pre- and post-processing steps.

The most efficient algorithms, in principle, are usually those that are specialized directly for the DCT, as opposed to using an ordinary FFT plus O(N) extra operations (see below for an exception). However, even "specialized" DCT algorithms (including all of those that achieve the lowest known arithmetic counts, at least for power-of-two sizes) are typically closely related to FFT algorithms—since DCTs are essentially DFTs of real-even data, one can design a fast DCT algorithm by taking an FFT and eliminating the redundant operations due to this symmetry. This can even be done automatically (Frigo & Johnson, 2005). Algorithms based on the Cooley-Tukey FFT algorithm are most common, but any other FFT algorithm is also applicable. For example, the Winograd FFT algorithm leads to minimal-multiplication algorithms for the DFT, albeit generally at the cost of more additions, and a similar algorithm was proposed by Feig & Winograd (1992) for the DCT. Because the algorithms for DFTs, DCTs, and similar transforms are all so closely related, any improvement in algorithms for one transform will theoretically lead to immediate gains for the other transforms as well (Duhamel & Vetterli, 1990).

While DCT algorithms that employ an unmodified FFT often have some theoretical overhead compared to the best specialized DCT algorithms, the former also have a distinct advantage: highly optimized FFT programs are widely available. Thus, in practice, it is often easier to obtain high performance for general lengths N with FFT-based algorithms. (Performance on modern hardware is typically not dominated simply by arithmetic counts, and optimization requires substantial engineering effort.) Specialized DCT algorithms, on the other hand, see widespread use for transforms of small, fixed sizes such as the <math>8 \times 8</math> DCT-II used in JPEG compression, or the small DCTs (or MDCTs) typically used in audio compression. (Reduced code size may also be a reason to use a specialized DCT for embedded-device applications.)

In fact, even the DCT algorithms using an ordinary FFT are often equivalent to pruning the redundant operations from a larger FFT of real-symmetric data, and they can even be optimal from the perspective of arithmetic counts. For example, a type-II DCT is equivalent to a DFT of size <math>4N</math> with real-even symmetry whose even-indexed elements are zero. One of the most common methods for computing this via an FFT (e.g. the method used in FFTPACK and FFTW) is due to Makhoul (1980), and this method in hindsight can be seen as one step of a radix-4 decimation-in-time Cooley-Tukey algorithm applied to the "logical" real-even DFT corresponding to the DCT II. (The radix-4 step reduces the size <math>4N</math> DFT to four size-<math>N</math> DFTs of real data, two of which are zero and two of which are equal to one another by the even symmetry, hence giving a single size-<math>N</math> FFT of real data plus <math>O(N)</math> butterflies.) Because the even-indexed elements are zero, this radix-4 step is exactly the same as a split-radix step; if the subsequent size-<math>N</math> real-data FFT is also performed by a real-data split-radix algorithm (as in Sorensen et al., 1987), then the resulting algorithm actually matches the lowest published arithmetic count for the power-of-two DCT-II (<math>2 N \log_2 N - N + 2</math> real-arithmetic operationsTemplate:Ref). So, there is nothing intrinsically bad about computing the DCT via an FFT from an arithmetic perspective—it is sometimes merely a question of whether the corresponding FFT algorithm is optimal. (As a practical matter, the function-call overhead in invoking a separate FFT routine might be significant for small <math>N</math>, but this is an implementation rather than an algorithmic question since it can be solved by unrolling/inlining.)

Notes

1. Template:Note The precise count of real arithmetic operations, and in particular the count of real multiplications, depends somewhat on the scaling of the transform definition. The <math>2 N \log_2 N - N + 2</math> count is for the DCT-II definition shown here; two multiplications can be saved if the transform is scaled by an overall <math>\sqrt2</math> factor. Additional multiplications can be saved if one permits the outputs of the transform to be rescaled individually, as was shown by Arai et al. (1988) for the size-8 case used in JPEG.

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, Discrete-Time Signal Processing, second edition (Prentice-Hall, New Jersey, 1999).
• S. A. Martucci, "Symmetric convolution and the discrete sine and cosine transforms," IEEE Trans. Sig. Processing SP-42, 1038-1051 (1994).
• Matteo Frigo and Steven G. Johnson: FFTW, http://www.fftw.org/. A free (GPL) C library that can compute fast DCTs (types I-IV) in one or more dimensions, of arbitrary size. Also M. Frigo and S. G. Johnson, "The Design and Implementation of FFTW3," Proceedings of the IEEE 93 (2), 216–231 (2005).
• E. Feig, S. Winograd. "Fast algorithms for the discrete cosine transform," IEEE Transactions on Signal Processing 40 (9), 2174-2193 (1992).
• P. Duhamel and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," Signal Processing 19, 259–299 (1990).
• John Makhoul, "A fast cosine transform in one and two dimensions," IEEE Trans. Acoust. Speech Sig. Proc. 28 (1), 27-34 (1980).
• H. V. Sorensen, D. L. Jones, M. T. Heideman, and C. S. Burrus, "Real-valued fast Fourier transform algorithms," IEEE Trans. Acoust. Speech Sig. Processing ASSP-35, 849–863 (1987).
• Y. Arai, T. Agui, and M. Nakajima, "A fast DCT-SQ scheme for images," Trans. IEICE 71 (11), 1095–1097 (1988).

External links

• Template:Planetmath reference
• Some code in various forms
• The Discrete Cosine Transform (DCT): Theory and Applicationde:Diskrete Kosinustransformation

es:Transformada de coseno discreta fr:Transformée en cosinus discret ja:離散コサイン変換 ko:이산 코사인 변환 pl:Dyskretna transformata kosinusowa ru:Дискретное косинусное преобразование sr:Дискретна косинус трансформација th:การแปลงโคไซน์ไม่ต่อเนื่อง zh:离散余弦变换