Diskrétní kosinová transformace
Z Wikipedie, otevřené encyklopedie
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é.
Nějběž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“.
Obsah |
[editovat] 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 kodeku JPEG, video kodeku MJPEG, MPEG a DV. Její modifikace jsou použity v audio kodeku AAC, Vorbis a MP3.
[editovat] Definice
Formálně je DCT lineární invertovatelná funkce F : RN -> RN (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 realných čísel x0, …, xN-1 je transformováno do N reálných čísel X0, …, XN-1 podle jedné z rovnic:
[editovat] DCT-I
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).
[editovat] DCT-II
DCT-II je pravděpodobně nějrozšířenější forma a je často uváděna pouze jako „DCT“.
Inverzní transformace k DCT-II je DCT-III násobená 2/N.
[editovat] DCT-III
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.
[editovat] DCT-IV
Inverzní transformace k DCT-IV je DCT-IV násobená 2/N.
[editovat] DCT V-VIII
Tyto varianty se v praxi používají zřídka.
[editovat] 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žné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í:
[editovat] Výpočet
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 (fast Fourier transform, FFT).
[editovat] Příklad
Úseky zdrojového kódu v jazyce C (DCT typu II a typu III):
[editovat] 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;
}
}
[editovat] 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;
}
}
[editovat] Podívejte se také na
- goniometrická funkce kosinus
![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]](../../../math/0/5/7/0579badb31555aef53780b857b4ee6e8.png)
![X_k = \sum_{n=0}^{N-1} x_n \cos \left[\frac{\pi}{N} \left(n+\frac{1}{2}\right) k \right]](../../../math/2/e/6/2e69cef1895db518ab2aa949e21e70f3.png)
![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]](../../../math/9/2/3/9235b7725a3c1579548e481463debdd6.png)
![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]](../../../math/5/4/d/54d336b56085a1c67a3c9a3a864ae18e.png)
![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]](../../../math/e/0/a/e0a88242e1e34beb68f6ddf2d3d08da6.png)

