Diskrétní kosinová transformace

Diskrétní kosinová transformace (anglicky discrete cosine transform, zkratka DCT) je diskrétní transformace podobná diskrétní Fourierově transformaci (DFT), ale produkující pouze reálné koeficienty. Je jednou z mnoha transformací příbuzných Fourierově transformaci. Existuje 8 standardních variant DCT, z nichž 4 jsou běžně používané.

Nejběžnější varianta diskrétní kosinové transformace je DCT typu II, která je často nazývána pouze „DCT“. K ní inverzní transformace je DCT typu III, také rovněž často nazývána pouze „inverzní DCT“ nebo zkratkou „IDCT“.

Aplikace

DCT je často používána při zpracování signálu a obrazu, obzvláště pro ztrátovou kompresi. Je například použita v obrazovém formátu JPEG, formátech MJPEG, MPEG a DV. Její modifikace jsou použity v audio formátech AAC, Vorbis a MP3.

Definice

Formálně je DCT lineární invertovatelná funkce F : R^N → R^N (kde R značí množinu reálných čísel); nebo ekvivalentně čtvercová matice N × N. Existuje několik variant DCT s mírně modifikovanou definicí. N reálných čísel x₀, …, x_N-1 je transformováno do N reálných čísel X₀, …, X_N-1 podle jedné z rovnic:

DCT-I

$X_k=\frac{1}{2}(x_0+(-<!--\; -\; -->1{)}^k{x}_{N-<!--\; -\; -->1})+\underset{n=1}{\overset{N-<!--\; -\; -->2}{\sum <!--\; \sum \; -->}}{x}_n\cos <!--\; \; -->\left[\frac{\mathrm{\pi <!--\; \pi \; -->}}{N-<!--\; -\; -->1}nk\right]$

DCT-I není definována pro N < 2. (Všechny ostatní typy DCT jsou definovány pro libovolné N.)

Inverzní transformace k DCT-I je DCT-I násobená 2/(N-1).

DCT-II

$X_k=\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_n\cos <!--\; \; -->\left[\frac{\mathrm{\pi <!--\; \pi \; -->}}{N}\left(n+\frac{1}{2}\right)k\right]$

DCT-II je pravděpodobně nejrozšířenější forma a je často uváděna pouze jako „DCT“.

Inverzní transformace k DCT-II je DCT-III násobená 2/N.

DCT-III

$X_k=\frac{1}{2}{x}_0+\underset{n=1}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_n\cos <!--\; \; -->\left[\frac{\mathrm{\pi <!--\; \pi \; -->}}{N}n\left(k+\frac{1}{2}\right)\right]$

Protože je to inverzní transformace k DCT-II (až na „měřítko“, anglicky scale factor), je tato forma někdy uváděna pouze jako „inverzní DCT“ („IDCT“).

Inverzní transformace k DCT-III je DCT-II násobená 2/N.

DCT-IV

$X_k=\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_n\cos <!--\; \; -->\left[\frac{\mathrm{\pi <!--\; \pi \; -->}}{N}\left(n+\frac{1}{2}\right)\left(k+\frac{1}{2}\right)\right]$

Inverzní transformace k DCT-IV je DCT-IV násobená 2/N.

DCT V-VIII

Tyto varianty se v praxi používají zřídka.

Vícerozměrné DCT

Vícerozměrná transformace (transformace vícerozměrné funkce) může být spočítána jako série jednorozměrných transformací postupně v každém rozměru. Pro 2D například nejprve po řádcích a pak po sloupcích (nebo naopak).

2D DCT-II je například dána rovnicí:

$X_{k_1,k_2}=\underset{n_1=0}{\overset{N_1-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\underset{n_2=0}{\overset{N_2-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_{n_1,n_2}\cos <!--\; \; -->\left[\frac{\mathrm{\pi <!--\; \pi \; -->}}{N_1}\left(n_1+\frac{1}{2}\right)k_1\right]\cos <!--\; \; -->\left[\frac{\mathrm{\pi <!--\; \pi \; -->}}{N_2}\left(n_2+\frac{1}{2}\right)k_2\right]$

Výpočet

Přestože přímá aplikace těchto rovnic může vyžadovat O(N²) operací, je možné spočítat stejnou transformaci pouze se složitostí O(N log N) použitím rychlé Fourierovy transformace (anglicky fast Fourier transform, FFT).

Příklad

Úseky zdrojového kódu v jazyce C (DCT typu II a typu III):

Dopředná

Dopředná (anglicky forward) 1D DCT (typu II):

void fct(const double *input, double *output)
{
	for(int h=0; h<LENGTH; h++)
	{
		double sum = 0;
		for(int j=0; j<LENGTH; j++)
		{
			double xk = input[j];
			double c = (M_PI/LENGTH)*h*(j+0.5);
			sum += xk*cos(c);
		}
		output[h] = sum;
	}
}

Zpětná

Zpětná (anglicky inverse) 1D DCT (typu III):

void ict(const double *input, double *output)
{
	for(int h=0; h<LENGTH; h++)
	{
		double sum = 0;
		for(int j=1; j<LENGTH; j++)
		{
			double xk = input[j];
			double c = (M_PI/LENGTH)*j*(h+0.5);
			sum += xk*cos(c);
		}
		sum += 0.5*input[0];
		sum *= 2/(double)LENGTH;
		output[h] = sum;
	}
}

Související články

• goniometrická funkce kosinus
• diskrétní vlnková transformace

Reference

V tomto článku byl použit překlad textu z článku Discrete cosine transform na anglické Wikipedii.

Externí odkazy

• Obrázky, zvuky či videa k tématu Diskrétní kosinová transformace na Wikimedia Commons
• (anglicky) DCT na serveru PlanetMath Archivováno 22. 6. 2011 na Wayback Machine.
• (anglicky) The Discrete Cosine Transform (DCT): Theory and Application Archivováno 28. 5. 2008 na Wayback Machine.
• (česky) Programujeme JPEG: diskrétní kosinová transformace (DCT) – článek o DCT na root.cz