Diskrétní kosinová transformace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
2D DCT (typu II) v porovnání s DFT. DCT koncentruje nejvíce energie na nejnižších frekvencích.

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Formálně je DCT lineární invertovatelná funkce F : RNRN (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 x0, …, xN-1 je transformováno do N reálných čísel X0, …, XN-1 podle jedné z rovnic:

DCT-I[editovat | editovat zdroj]

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} n k \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[editovat | editovat zdroj]

X_k = \sum_{n=0}^{N-1} x_n \cos \left[\frac{\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[editovat | editovat zdroj]

X_k = \frac{1}{2} x_0 + \sum_{n=1}^{N-1} x_n \cos \left[\frac{\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[editovat | editovat zdroj]

X_k = \sum_{n=0}^{N-1} x_n \cos \left[\frac{\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[editovat | editovat zdroj]

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

Vícerozměrné DCT[editovat | editovat zdroj]

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} \left(n_1+\frac{1}{2}\right) k_1 \right] \cos \left[\frac{\pi}{N_2} \left(n_2+\frac{1}{2}\right) k_2 \right]

Výpočet[editovat | editovat zdroj]

Přestože přímá aplikace těchto rovnic může vyžadovat O(N2) 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[editovat | editovat zdroj]

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

Dopředná[editovat | editovat zdroj]

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á[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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

Externí odkazy[editovat | editovat zdroj]