Diskrétní kosinová transformace

Kategorie: Nezařazeno (celkem: 23162 referátů a seminárek)

Informace o referátu:

Příbuzná témata



Diskrétní kosinová transformace

2D DCT (typu II) v porovnání s DFT. DCT koncentruje nejvíce energie na nejnižších frekvencích.
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é.

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

Aplikace

DCT-II (dole) v porovnání s DFT (uprostřed) vstupního signálu (nahoře).
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 kodeku JPEG, video kodeku MJPEG, MPEG a DV. Její modifikace jsou použity v audio kodeku AAC, Vorbis a MP3.

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:

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} n k 
ight]

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} left(n+frac{1}{2}
ight) k 
ight]

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 left(k+frac{1}{2}
ight) 
ight]

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 = sum_{n=0}^{N-1} x_n cos left[frac{pi}{N} left(n+frac{1}{2}
ight) left(k+frac{1}{2}
ight) 
ight]

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

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).

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



Nový příspěvek


Ochrana proti spamu. Kolik je 2x4?



Na-mobil.cz

Spřátelené weby

Přidat stránku k oblíbeným

Nejnovější v diskusi

Diskusní fórum »

TIP: Chcete zkrátit dlouho chvíli sobě nebo blízkému?
Klikněte na Puzzle-prodej.cz a vyberte si z 5000 motivů skladem!
TIP: Hračky a hry za dobré ceny?
Klikněte na Hračky obchod.cz a vyberte si z tisícovky hraček skladem!