(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (211)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (36)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

discrete cosine transform

(Definition)

The discrete cosine transforms (DCT) are a family of similar 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 complete set of variants.

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

Definition

The orthonormal variants of the DCT, where is the original vector of real numbers, is the transformed vector of real numbers and $\delta$ is the Kronecker delta, are defined by the following equations:

DCT-I

$\displaystyle C^I_k$	$\displaystyle =$	$\displaystyle p_k \sum _{n=0}^{N-1} x_n q_n \cos \frac{\pi n k}{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.

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.

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.

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.

DCT-V

$\displaystyle C^V_k$	$\displaystyle =$	$\displaystyle p_k \sum _{n=0}^{N-1} x_n q_n \cos \frac{\pi n 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,0}}}$

The DCT-V is its own inverse.

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.

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.

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.

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... ...ac{1}{2}\right) k_1}{N_1} \cos \frac{\pi\left( n_2+\frac{1}{2}\right) k_2}{N_2}$

Bibliography

1: This entry is based on content from The Data Analysis Briefbook (http://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.

"discrete cosine transform" is owned by stitch. [ full author list (2) | owner history (1) ]

(view preamble)

Other names:

DCT, discrete trigonometric transforms

Also defines:

DCT-I, DCT-II, DCT-III, DCT-IV, DCT-V, DCT-VI, DCT-VII, DCT-VIII

Log in to rate this entry.
(view current ratings)

Cross-references: matrix, column, row, dimensions, inverse, equations, Kronecker delta, real numbers, vector, orthonormal, Mathematica, MATLAB, images, discrete Fourier transform, Transforms

This is version 14 of discrete cosine transform, born on 2002-01-13, modified 2007-08-22.
Object id is 1469, canonical name is DiscreteCosineTransform.
Accessed 32699 times total.

Classification:

AMS MSC:	42-00 (Fourier analysis :: General reference works )
	65T50 (Numerical analysis :: Numerical methods in Fourier analysis :: Discrete and fast Fourier transforms)

Pending Errata and Addenda

None.[ View all 4 ]

Discussion

forum policy

Interact