Diskrétní kosinová transformace

2D DCT (typu II) v porovnání s DFT. DCT koncentruje nejvíce energie na nejnižších frekvencích.

Diskrétní kosinová transformace (Šablona:Vjazyce2, 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-II (dole) v porovnání s DFT (uprostřed) vstupního signálu (nahoře).

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})+\sum _{n=1}^{N-2}{x}_n\cos \left[\frac{\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=\sum _{n=0}^{N-1}{x}_n\cos \left[\frac{\pi }{N}(n+\frac{1}{2})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+\sum _{n=1}^{N-1}{x}_n\cos \left[\frac{\pi }{N}n(k+\frac{1}{2})\right]$

Protože je to inverzní transformace k DCT-II (až na „měřítko“, Šablona:Vjazyce2), 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=\sum _{n=0}^{N-1}{x}_n\cos \left[\frac{\pi }{N}(n+\frac{1}{2})(k+\frac{1}{2})\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}=\sum _{n_1=0}^{N_1-1}\sum _{n_2=0}^{N_2-1}{x}_{n_1,n_2}\cos \left[\frac{\pi }{N_1}(n_1+\frac{1}{2})k_1\right]\cos \left[\frac{\pi }{N_2}(n_2+\frac{1}{2})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 (Šablona:Vjazyce2, FFT).

Příklad

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

Dopředná

Dopředná (Šablona:Vjazyce2) 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á (Šablona:Vjazyce2) 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

Externí odkazy

• Šablona:Commonscat
• Šablona:En DCT na serveru PlanetMath Šablona:Wayback
• Šablona:En The Discrete Cosine Transform (DCT): Theory and Application Šablona:Wayback
• Šablona:Cs Programujeme JPEG: diskrétní kosinová transformace (DCT) – článek o DCT na root.cz