discrete cosine transform

The discrete cosine transforms (DCT) are a family of transforms closely related to the discrete sine transform and the discrete Fourier transform. The DCT-II is the most commonly used form and plays an important role in coding signals and images [2], e.g. in the widely used standard JPEG compression. The discrete cosine transform was first introduced by Ahmed, Natarajan, and Rao [5]. Later Wang and Hunt [6] introduced the set of variants.

The DCT is included in many mathematical packages, such as Matlab, Mathematica and GNU Octave.

1 Definition

The orthonormal variants of the DCT, where $x_{n}$ is the original vector of $N$ real numbers, $C_{k}$ is the transformed vector of $N$ real numbers and $\delta$ is the Kronecker delta, are defined by the following equations:

1.1 DCT-I

$\displaystyle C^{I}_{k}$	$\displaystyle=$	$\displaystyle p_{k}\sum_{n=0}^{N-1}x_{n}q_{n}\cos\frac{\pi nk}{N-1}\quad\quad k% =0,1,2,\dots,N-1$
$\displaystyle p_{k}$	$\displaystyle=$	$\displaystyle\sqrt{\frac{2-\delta_{k,0}-\delta_{k,N-1}}{N-1}}$
$\displaystyle q_{n}$	$\displaystyle=$	$\displaystyle\sqrt{\frac{1}{1+\delta_{n,0}+\delta_{n,N-1}}}$

The DCT-I is its own inverse.

1.2 DCT-II

	$\displaystyle C^{II}_{k}$	$\displaystyle=$	$\displaystyle p_{k}\sum_{n=0}^{N-1}x_{n}\cos\frac{\pi\left(n+\frac{1}{2}\right% )k}{N}\quad\quad k=0,1,2,\dots,N-1$
	$\displaystyle p_{k}$	$\displaystyle=$	$\displaystyle\sqrt{\frac{2-\delta_{k,0}}{N}}$

The inverse of DCT-II is DCT-III.

1.3 DCT-III

$\displaystyle C^{III}_{k}$	$\displaystyle=$	$\displaystyle p\sum_{n=0}^{N-1}x_{n}q_{n}\cos\frac{\pi n\left(k+\frac{1}{2}% \right)}{N}\quad\quad k=0,1,2,\dots,N-1$
$\displaystyle p$	$\displaystyle=$	$\displaystyle\sqrt{\frac{2}{N}}$
$\displaystyle q_{n}$	$\displaystyle=$	$\displaystyle\sqrt{\frac{1}{1+\delta_{n,0}}}$

The inverse of DCT-III is DCT-II.

1.4 DCT-IV

	$\displaystyle C^{IV}_{k}$	$\displaystyle=$	$\displaystyle p\sum_{n=0}^{N-1}x_{n}\cos\frac{\pi\left(n+\frac{1}{2}\right)% \left(k+\frac{1}{2}\right)}{N}\quad\quad k=0,1,2,\dots,N-1$
	$\displaystyle p$	$\displaystyle=$	$\displaystyle\sqrt{\frac{2}{N}}$

The DCT-IV is its own inverse.

1.5 DCT-V

$\displaystyle C^{V}_{k}$	$\displaystyle=$	$\displaystyle p_{k}\sum_{n=0}^{N-1}x_{n}q_{n}\cos\frac{\pi nk}{N-\frac{1}{2}}% \quad\quad k=0,1,2,\dots,N-1$
$\displaystyle p_{k}$	$\displaystyle=$	$\displaystyle\sqrt{\frac{2-\delta_{k,0}}{N-\frac{1}{2}}}$
$\displaystyle q_{n}$	$\displaystyle=$	$\displaystyle\sqrt{\frac{1}{1+\delta_{n,0}}}$

The DCT-V is its own inverse.

1.6 DCT-VI

$\displaystyle C^{VI}_{k}$	$\displaystyle=$	$\displaystyle p_{k}\sum_{n=0}^{N-1}x_{n}q_{n}\cos\frac{\pi\left(n+\frac{1}{2}% \right)k}{N-\frac{1}{2}}\quad\quad k=0,1,2,\dots,N-1$
$\displaystyle p_{k}$	$\displaystyle=$	$\displaystyle\sqrt{\frac{2-\delta_{k,0}}{N-\frac{1}{2}}}$
$\displaystyle q_{n}$	$\displaystyle=$	$\displaystyle\sqrt{\frac{1}{1+\delta_{n,N-1}}}$

The inverse of DCT-VI is DCT-VII.

1.7 DCT-VII

$\displaystyle C^{VII}_{k}$	$\displaystyle=$	$\displaystyle p_{k}\sum_{n=0}^{N-1}x_{n}q_{n}\cos\frac{\pi n\left(k+\frac{1}{2% }\right)}{N-\frac{1}{2}}\quad\quad k=0,1,2,\dots,N-1$
$\displaystyle p_{k}$	$\displaystyle=$	$\displaystyle\sqrt{\frac{2-\delta_{k,N-1}}{N-\frac{1}{2}}}$
$\displaystyle q_{n}$	$\displaystyle=$	$\displaystyle\sqrt{\frac{1}{1+\delta_{n,0}}}$

The inverse of DCT-VII is DCT-VI.

1.8 DCT-VIII

	$\displaystyle C^{VII}_{k}$	$\displaystyle=$	$\displaystyle p\sum_{n=0}^{N-1}x_{n}\cos\frac{\pi\left(n+\frac{1}{2}\right)% \left(k+\frac{1}{2}\right)}{N+\frac{1}{2}}\quad\quad k=0,1,2,\dots,N-1$
	$\displaystyle p$	$\displaystyle=$	$\displaystyle\sqrt{\frac{2}{N+\frac{1}{2}}}$

The DCT-VIII is its own inverse.

2 Two-dimensional DCT

The DCT in two dimensions is simply the one-dimensional transform computed in each row and each column. For example, the DCT-II of a $N_{1}\times N_{2}$ matrix is given by

$\displaystyle C^{II}_{k_{1},k_{2}}$

$\displaystyle=$

$\displaystyle p_{k_{1}}p_{k_{2}}\sum_{n_{1}=0}^{N_{1}-1}\sum_{n_{2}=0}^{N_{2}-% 1}x_{n_{1},n_{2}}\cos\frac{\pi\left(n_{1}+\frac{1}{2}\right)k_{1}}{N_{1}}\cos% \frac{\pi\left(n_{2}+\frac{1}{2}\right)k_{2}}{N_{2}}$

References

1 This entry is based on content from The Data Analysis Briefbook (http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html)
2 A.K. Jain, Fundamentals of Digital Image Processing, Prentice Hall, 1989.
3 Xuancheng Shao, Steven G. Johnson. Type-II/III DCT/DST algorithms with reduced number of arithmetic operations. 2007.
4 Markus Päuschel, José M. F. Mouray. The algebraic approach to the discrete cosine and sine transforms and their fast algorithms. 2006.
5 N. Ahmed, T. Natarajan, and K. R. Rao. Discrete Cosine Transform, IEEE Trans. on Computers, C-23. 1974.
6 Z. Wang and B. Hunt, The Discrete W Transform, Applied Mathematics and Computation, 16. 1985.

Title	discrete cosine transform
Canonical name	DiscreteCosineTransform
Date of creation	2013-03-22 12:11:24
Last modified on	2013-03-22 12:11:24
Owner	stitch (17269)
Last modified by	stitch (17269)
Numerical id	18
Author	stitch (17269)
Entry type	Definition
Classification	msc 65T50
Classification	msc 42-00
Synonym	DCT
Synonym	discrete trigonometric transforms
Related topic	DiscreteSineTransform
Related topic	DiscreteFourierTransform2
Related topic	DiscreteFourierTransform
Defines	DCT-I
Defines	DCT-II
Defines	DCT-III
Defines	DCT-IV
Defines	DCT-V
Defines	DCT-VI
Defines	DCT-VII
Defines	DCT-VIII