Discrete Cosine Transform Applications Formal Definition

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".

1 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 optimal Karhunen-Loève transform 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 two-dimensional DCT-II of 8x8 blocks is computed and the results are filtered to discard small (difficult-to-see) components. That is, n is 8 and the DCT-II formula is applied to each row and column of the block. The result is an array in which the top left corner is the DC (zero-frequency) component and lower and rightmore entries represent larger vertical and horizontal spatial frequencies. For the chrominance components, n is 16 but the frequency components beyond the first 8 are discarded.

A related transform, the modified discrete cosine transform, or MDCT, is used in AAC, Vorbis, and MP3MP3 (or, more precisely, MPEG-1/2 Audio Layer 3 is an audio compression algorithm capable of greatly reducing the amount of data required to reproduce audio, while sounding like a faithful reproduction of the original uncompressed audio to the listener. audio compression.

DCTs are also widely employed in solving partial differential equationIn mathematics, and in particular calculus, a partial differential equation PDE is an equation involving partial derivatives of an unknown function. The idea is to describe a function indirectly by a relation between itself and its partial derivatives, ras 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.

2 Formal Definition

Formally, the discrete cosine transform is a linearThe word linear comes from the latin word linearis which means created by lines''. In mathematics, a linear function f ''x is one which satisfies the following two properties (but see below for a slightly different usage of the term): Additivity: f ''x +, invertible functionIn mathematics, a function is a relation such that each element of a set (the domain is associated with a unique element of another (possibly the same) set (the codomain not to be confused with the range . The concept of a function is fundamental to virtu F : Rⁿ -> Rⁿ (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 f₀, ..., f_n-1 according to one of the formulas:

2.1 DCT-I

Some authors further multiply the x₀ and x_n-1 terms by √2, and correspondingly multiply the f₀ and f_n-1 terms by 1/√2. This makes the DCT-I matrix orthogonalIn linear algebra, an orthogonal matrix is a square matrix G whose transpose is its inverse, i. This definition can be given for matrices with entries from any field, but the most common case is the one of matrices with real entries, and only that case wi (up to a scale factor), but breaks the direct correspondence with a real-even DFT.

A DCT-I 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 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_k is even around k=0 and even around k=n-1; similarly for f_j.

2.2 DCT-II

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

Some authors further multiply the f₀ term by 1/√2 (see below for the corresponding change in DCT-III). This makes the DCT-II matrix orthogonalIn linear algebra, an orthogonal matrix is a square matrix G whose transpose is its inverse, i. This definition can be given for matrices with entries from any field, but the most common case is the one of matrices with real entries, and only that case wi (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_k is even around k=-1/2 and even around k=n-1/2; f_j is even around j=0 and odd around j=n.

2.3 DCT-III

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 orthogonalIn linear algebra, an orthogonal matrix is a square matrix G whose transpose is its inverse, i. This definition can be given for matrices with entries from any field, but the most common case is the one of matrices with real entries, and only that case wi (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_k is even around k=0 and odd around k=n; f_j is even around j=-1/2 and odd around j=n-1/2.

2.4 DCT-IV

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_k is even around k=-1/2 and odd around k=n-1/2; similarly for f_j.

2.5 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.)

2.6 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 so that the inverse does not require any additional multiplicative factor.

2.7 Computation

Although the direct application of these formulas would require O(n²) 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 post-processing steps.)

3 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.

Digital signal processing

<Hide>

Home > Discrete cosine transform