Discrete cosine transform

The discrete cosine transform (DCT) is an invertible linear mapping $"DCT" : CC^N -> CC^N$ defined by:

$"DCT"(x) = M x$ , where $M in CC^{N \times N}$ , and

$M_{kn} = cos((pi k (2n + 1)) / (2N)).$

The unitary discrete cosine transform is given by multiplying the first row of $M$ by $sqrt(1 / N)$ , and the rest of $M$ by $sqrt(2 / N)$ .

Theory

The unitary DCT has the convenient property of preserving 2-norms. The DCT can be viewed as a change of basis from the standard basis to a cosine basis. The inverse of the DCT is given by $"IDCT" : CC^N -> CC^N$ :

$"IDCT"(x) = M^{-1} x$ , where $M^{-1} in CC^{N \times N}$ ,

$M_{nk}^{-1} = w_n cos((pi k (2n + 1)) / (2N))$ , and

$w_n = ((1 / N, ", for " n = 1), (2 / N, ", otherwise"))$

Real vs complex

Since the matrix $M$ is real, the DCT and IDCT are closed under $RR^n$ . Using the DCT on real vectors is arguably the most common use-case. In this real case the unitary version is called an orthogonal discrete cosine transform.

Applications

The DCT is interesting for the same reasons as the discrete Fourier transform. However, especially when applied to natural images, the DCT has a strong energy compaction property, which means that most of the information (length) of a vector is contained in the first few coefficients. This property has been extensively taken advantage of in image compression.

Practice

Pastel implements efficient $O(n log n)$ algorithms for computing the DCT and the IDCT, when $n$ is a power of two. Both the standard and the orthogonal version are provided, as well as both real and complex versions.

Range algorithms

Pastel also provides the in-place versions of the DCT as range algorithms, so that applying them to arrays is easy.

Discrete cosine transform

Theory

Real vs complex

Applications

Practice

Range algorithms

See also

Files

Discrete cosine transform