Math for the people, by the people.

User login

You are here

Home ›

discrete cosine transform

Primary tabs

discrete cosine transform

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.

1 Definition

The orthonormal variants of the DCT, where xnsubscriptxnx_{n} is the original vector of NNN real numbers, CksubscriptCkC_{k} is the transformed vector of NNN real numbers and δδ\delta is the Kronecker delta, are defined by the following equations:

1.1 DCT-I

CkIsubscriptsuperscriptCIk\displaystyle C^{I}_{k} =\displaystyle= pk⁢∑n=0N-1xn⁢qn⁢cos⁡π⁢n⁢kN-1  k=0,1,2,…,N-1formulae-sequencesubscriptpksuperscriptsubscriptn0N1subscriptxnsubscriptqnπnkN1k012normal-…N1\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
pksubscriptpk\displaystyle p_{k} =\displaystyle= 2-δk,0-δk,N-1N-12subscriptδk0subscriptδkN1N1\displaystyle\sqrt{\frac{2-\delta_{{k,0}}-\delta_{{k,N-1}}}{N-1}}
qnsubscriptqn\displaystyle q_{n} =\displaystyle= 11+δn,0+δn,N-111subscriptδn0subscriptδnN1\displaystyle\sqrt{\frac{1}{1+\delta_{{n,0}}+\delta_{{n,N-1}}}}

The DCT-I is its own inverse.

1.2 DCT-II

CkI⁢IsubscriptsuperscriptCIIk\displaystyle C^{{II}}_{k} =\displaystyle= pk⁢∑n=0N-1xn⁢cos⁡π⁢(n+12)⁢kN  k=0,1,2,…,N-1formulae-sequencesubscriptpksuperscriptsubscriptn0N1subscriptxnπn12kNk012normal-…N1\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
pksubscriptpk\displaystyle p_{k} =\displaystyle= 2-δk,0N2subscriptδk0N\displaystyle\sqrt{\frac{2-\delta_{{k,0}}}{N}}

The inverse of DCT-II is DCT-III.

1.3 DCT-III

CkI⁢I⁢IsubscriptsuperscriptCIIIk\displaystyle C^{{III}}_{k} =\displaystyle= p⁢∑n=0N-1xn⁢qn⁢cos⁡π⁢n⁢(k+12)N  k=0,1,2,…,N-1formulae-sequencepsuperscriptsubscriptn0N1subscriptxnsubscriptqnπnk12Nk012normal-…N1\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
pp\displaystyle p =\displaystyle= 2N2N\displaystyle\sqrt{\frac{2}{N}}
qnsubscriptqn\displaystyle q_{n} =\displaystyle= 11+δn,011subscriptδn0\displaystyle\sqrt{\frac{1}{1+\delta_{{n,0}}}}

The inverse of DCT-III is DCT-II.

1.4 DCT-IV

CkI⁢VsubscriptsuperscriptCIVk\displaystyle C^{{IV}}_{k} =\displaystyle= p⁢∑n=0N-1xn⁢cos⁡π⁢(n+12)⁢(k+12)N  k=0,1,2,…,N-1formulae-sequencepsuperscriptsubscriptn0N1subscriptxnπn12k12Nk012normal-…N1\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
pp\displaystyle p =\displaystyle= 2N2N\displaystyle\sqrt{\frac{2}{N}}

The DCT-IV is its own inverse.

1.5 DCT-V

CkVsubscriptsuperscriptCVk\displaystyle C^{V}_{k} =\displaystyle= pk⁢∑n=0N-1xn⁢qn⁢cos⁡π⁢n⁢kN-12  k=0,1,2,…,N-1formulae-sequencesubscriptpksuperscriptsubscriptn0N1subscriptxnsubscriptqnπnkN12k012normal-…N1\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
pksubscriptpk\displaystyle p_{k} =\displaystyle= 2-δk,0N-122subscriptδk0N12\displaystyle\sqrt{\frac{2-\delta_{{k,0}}}{N-\frac{1}{2}}}
qnsubscriptqn\displaystyle q_{n} =\displaystyle= 11+δn,011subscriptδn0\displaystyle\sqrt{\frac{1}{1+\delta_{{n,0}}}}

The DCT-V is its own inverse.

1.6 DCT-VI

CkV⁢IsubscriptsuperscriptCVIk\displaystyle C^{{VI}}_{k} =\displaystyle= pk⁢∑n=0N-1xn⁢qn⁢cos⁡π⁢(n+12)⁢kN-12  k=0,1,2,…,N-1formulae-sequencesubscriptpksuperscriptsubscriptn0N1subscriptxnsubscriptqnπn12kN12k012normal-…N1\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
pksubscriptpk\displaystyle p_{k} =\displaystyle= 2-δk,0N-122subscriptδk0N12\displaystyle\sqrt{\frac{2-\delta_{{k,0}}}{N-\frac{1}{2}}}
qnsubscriptqn\displaystyle q_{n} =\displaystyle= 11+δn,N-111subscriptδnN1\displaystyle\sqrt{\frac{1}{1+\delta_{{n,N-1}}}}

The inverse of DCT-VI is DCT-VII.

1.7 DCT-VII

CkV⁢I⁢IsubscriptsuperscriptCVIIk\displaystyle C^{{VII}}_{k} =\displaystyle= pk⁢∑n=0N-1xn⁢qn⁢cos⁡π⁢n⁢(k+12)N-12  k=0,1,2,…,N-1formulae-sequencesubscriptpksuperscriptsubscriptn0N1subscriptxnsubscriptqnπnk12N12k012normal-…N1\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
pksubscriptpk\displaystyle p_{k} =\displaystyle= 2-δk,N-1N-122subscriptδkN1N12\displaystyle\sqrt{\frac{2-\delta_{{k,N-1}}}{N-\frac{1}{2}}}
qnsubscriptqn\displaystyle q_{n} =\displaystyle= 11+δn,011subscriptδn0\displaystyle\sqrt{\frac{1}{1+\delta_{{n,0}}}}

The inverse of DCT-VII is DCT-VI.

1.8 DCT-VIII

CkV⁢I⁢IsubscriptsuperscriptCVIIk\displaystyle C^{{VII}}_{k} =\displaystyle= p⁢∑n=0N-1xn⁢cos⁡π⁢(n+12)⁢(k+12)N+12  k=0,1,2,…,N-1formulae-sequencepsuperscriptsubscriptn0N1subscriptxnπn12k12N12k012normal-…N1\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
pp\displaystyle p =\displaystyle= 2N+122N12\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 N1×N2subscriptN1subscriptN2N_{1}\times N_{2} matrix is given by

Ck1,k2I⁢IsubscriptsuperscriptCIIsubscriptk1subscriptk2\displaystyle C^{{II}}_{{k_{1},k_{2}}} =\displaystyle= pk1⁢pk2⁢∑n1=0N1-1∑n2=0N2-1xn1,n2⁢cos⁡π⁢(n1+12)⁢k1N1⁢cos⁡π⁢(n2+12)⁢k2N2subscriptpsubscriptk1subscriptpsubscriptk2superscriptsubscriptsubscriptn10subscriptN11superscriptsubscriptsubscriptn20subscriptN21subscriptxsubscriptn1subscriptn2πsubscriptn112subscriptk1subscriptN1πsubscriptn212subscriptk2subscriptN2\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.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.
Defines: 
DCT-I, DCT-II, DCT-III, DCT-IV, DCT-V, DCT-VI, DCT-VII, DCT-VIII
Related: 
DiscreteSineTransform, DiscreteFourierTransform2, DiscreteFourierTransform
Synonym: 
DCT, discrete trigonometric transforms
Type of Math Object: 
Definition
Major Section: 
Reference

Mathematics Subject Classification

65T50 Discrete and fast Fourier transforms
42-00 General reference works (handbooks, dictionaries, bibliographies, etc.)

Comments

Submitted by mbutterfield on Wed, 11/02/2005 - 02:19

The discrete cosine transform in two dimensions, for a square matrix, shows the first summation underscript as n=1. Should it be n=0? (which would be consistent with the same formula shown in 'The Data Analysis Briefbook at http://rkb.home.cern.ch/rkb/titleA.html')

Thanks! mb

Subscribe to Comments for "discrete cosine transform"

Info

Owner: stitch
Added: 2002-01-13 - 09:49
Author(s): stitch

Versions

(v18) by stitch 2013-03-22
Powered By: = + + ♡