Diskretna kosinus transformacija

Diskretna kosinus transformacija (DKT) transformiše neki signal sa realnim vrednostima u amplitude osnovnog tona i njegovih harmonika. Ima mnogo sličnosti sa diskretnom Furijeovom transformacijom, a može se posmatrati i kao njen specijalan slučaj. Svoju primenu je našla u mnogim (može se reći: skoro svim) postupcima kompresije, kao što su na primer JPEG, MPEG i drugim. Glavna ideja iza ovih kompresija je dekorelacija informacija između piksela, pošto jedan piksel često može da nam pruži dosta informacija o svom susedu (pogotovo kada je slika „mutnija“, bez oštrih ivica), tj. možemo da pretpostavim sa velikom verovatnoćom vrednost (boju) susednih piksela. U nekim svojim oblicima, DKT se takođe koristi i u MP3 i OGG Vorbis kompresijama.

Definicija

Diskretna kosinus transformacija nekog realnog, diskretnog i jednodimenzionalnog signala $f(x)$ je ovako definisana:

$C(u)=\alpha (u)\sum _{x=0}^{N-1}f(x)\cos \left({\frac {\pi (2x+1)u}{2N}}\right),\quad u=0,1,2,\cdots ,N-1$

Inverzna DKT definisana je slično:

$f(x)=\sum _{u=0}^{N-1}\alpha (u)C(u)\cos \left({\frac {\pi (2x+1)u}{2N}}\right),\quad x=0,1,2,\cdots ,N-1$

Za obe jednačine je $\alpha (u)$ ista funkcija:

$\alpha (u)={\begin{cases}{\sqrt {\frac {1}{N}}}\quad \quad u=0\\{\sqrt {\frac {2}{N}}}\quad \quad u\neq 0\end{cases}}$

Iz same definicije možemo na primer videti da je recimo prvi (nulti) koeficijent ove transformacije donekle jednak središnjoj vrednosti: $C(u=0)={\sqrt {\frac {1}{N}}}\sum _{x=0}^{N-1}f(x)$

Kao i kod diskretne Furijeove transformacije, i ovde su osnovni vektori ortogonalni:

$b_{u}=\left[\cos \left({\frac {\pi (2\cdot 0+1)u}{2N}}\right),\cos \left({\frac {\pi (2\cdot 1+1)u}{2N}}\right),\ldots ,\cos \left({\frac {\pi (2\cdot (N-1)+1)u}{2N}}\right)\right]$

$<b_{j},b_{k}>=0,\quad j\neq k$

$<b_{j},b_{j}>=const$

Pošto su baze jedna u odnosu na drugu ortogonalne, jednu od njih ne možemo da izrazimo u zavisnosti od drugih (ili formalnije: one su linearno nezavisne). Veoma bitna osobina ovakvih baza je što ne zavise uopšte od signala koji želimo da izračunamo. Tako možemo da ih izračunamo pre primene (u slobodno vreme, kada nemamo pametnija posla, na primer), a kada zagusti da ih upotrebimo u jednostavnom proizvodu matrica.

Bacimo malo podrobniji pogled na ove vektore - i šta vidimo? Oni su simetrični, a time je i matrica koja ih predstavlja ortogonalna. Recimo da je $f$ signal koji želimo da transformišemo napisan u obliku vektora. Konkretno, račun izgleda ovako:

$T=A\cdot f\cdot A,\quad a(k,j)=\alpha (j)\sum _{j=0}^{N-1}\cos \left({\frac {\pi (2j+1)k}{2N}}\right)$

$A$ je znači matrica koju koristimo da signal transformišemo. Inverznu DKT možemo takođe napisati u obliku matrica:

$f=A^{-1}\cdot T\cdot A^{-1}$,

a pošto su vektori ortogonalni, ovo je moguće izvršiti još efikasnije koristeći se osobinama ortogonalnih matrica:

$A^{-1}=A^{T}\Rightarrow f=A^{T}TA^{T}$ ($A^{T}$ znači A matrica transponirana).

Dvodimenzionalna transformacija izgleda ovako:

$C(u,v)=\alpha (u)\alpha (v)\sum _{x=0}^{N-1}\sum _{y=0}^{N-1}f(x,y)\cos \left({\frac {\pi (2x+1)u}{2N}}\right)\cos \left({\frac {\pi (2y+1)v}{2N}}\right)$

Inverzna transformacija u dve dimenzije:

$f(x,y)=\sum _{u=0}^{N-1}\sum _{v=0}^{N-1}\alpha (u)\alpha (v)C(u,v)\cos \left({\frac {\pi (2x+1)u}{2N}}\right)\cos \left({\frac {\pi (2y+1)v}{2N}}\right)$

Dvodimenzionalna transformacija poseduje prilično zgodnu osobinu da je možemo razdvojiti, pa prvo transformisti redove te onda kolone:

$C(u,v)=\alpha (u)\alpha (v)\sum _{x=0}^{N-1}\cos \left({\frac {\pi (2x+1)u}{2N}}\right)\sum _{y=0}^{N-1}f(x,y)\cos \left({\frac {\pi (2y+1)v}{2N}}\right)$

Iako je očigledno da svaka tačka ima svoj pandan u koeficijentu, ne treba ih mešati. Koeficijent je „jačina“ talasa i sa konkretnom tačkom nema „direktne“ veze, ali se zato dijagram lepo može predstaviti na slici iste veličine.

Kompresija

Diskretna kosinus transformacija smanjuje korelaciju. Svaki piksel transformisane slike nema skoro nikakve veze sa svojim komšijama. Koeficijente koji su premali ili koji nas ne interesuju možemo da izbacimo i da snmimo samo „interesantne“ (na primer, sortiramo ih po veličini i izbacimo 40% najmanjih). Signal (slika, zvuk itd.) će se zbog toga malo pomutiti (pogotovo ako je reč o visokim frekvencijama, jer su one najčešće zadužene za oštre ivice), ali je zato memorija potrebna za njeno skladištenje vidno umanjena.

Brzo izračunavanje DKT-a

Pomoću diskretne Furijeove transformacije

Jedan od načina da „brzo“ (prigodnije bi ipak bilo reći brže) izračunamo koeficijente diskretne kosinus transformacije je primena već postojećih algoritama za diskretnu Furijeovu transformaciju. Dobar razlog za to je što su takvi algoritmi zbog svoje važnosti uveliko dosta dobro implementirani i rasprostranjeni (u mnogim slučajevima zato ne moramo ni da ih implementiramo, dovoljno je da ih primenimo).

Pogledajmo koja je stoga veza između kosinus i Furijeove transformacije! Diskretna kosinus transformacija nije Furijeova transformacija sa realnim koeficijentima, što se lako da proveriti ako uporedimo njihove matrice. Red signala $f(x)$ možemo napisati kao spajanje parnih i neparnih redova:

${\tilde {f}}(x)=f_{parni}(x)+f_{neparni}(x)$

$f_{parni}(x)=f(2x)={\tilde {f}}(x),\ f_{neparni}(x)=f(2x+1)={\tilde {f}}(N-x-1),\ 0\leq x\leq \left({\frac {N}{2}}\right)-1$

Originalnu sumu za transformaciju možemo razdvojiti na dva dela:

$C(u)=\alpha (u)\left[\sum _{x=0}^{{\frac {N}{2}}-1}f(2x)\cos \left({\frac {\pi (4x+1)u}{2N}}\right)+\sum _{x=0}^{{\frac {N}{2}}-1}f(2x+1)\cos \left({\frac {\pi (4x+3)u}{2N}}\right)\right]$

$=\alpha (u)\left[\sum _{x=0}^{{\frac {N}{2}}-1}f_{parni}(x)\cos \left({\frac {\pi (4x+1)u}{2N}}\right)+\sum _{x=0}^{{\frac {N}{2}}-1}f_{neparni}(x)\cos \left({\frac {\pi (4x+3)u}{2N}}\right)\right]$

$=\alpha (u)\sum _{x=0}^{N-1}{\tilde {f}}(x)\cos \left({\frac {\pi (4x+1)u}{2N}}\right)$

$=\operatorname {Re} \left(\alpha (u)\ \mathrm {e} ^{\frac {-\mathrm {i} \pi u}{2N}}\ \sum _{x=0}^{N-1}{\tilde {f}}(x)e^{\frac {-\mathrm {i} 2\pi ux}{N}}\right)=\operatorname {Re} \left(\alpha (u)\cdot \operatorname {W} _{2N}^{\frac {u}{2}}\cdot \operatorname {DFT} \left\{{\tilde {f}}(x)\right\}_{N}\right)$

Dodatna literatura

• Wen-Hsiung Chen; Smith, C.; Fralick, S. (septembar 1977). „A Fast Computational Algorithm for the Discrete Cosine Transform”. IEEE Transactions on Communications. 25 (9): 1004—1009. doi:10.1109/TCOM.1977.1093941. 
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Section 12.4.2. Cosine Transform”, Numerical Recipes: The Art of Scientific Computing (3rd izd.), New York: Cambridge University Press, ISBN 978-0-521-88068-8, Arhivirano iz originala 11. 08. 2011. g., Pristupljeno 28. 04. 2019 

Primeri

Primer 1

Recimo da smo dobili sledeću sliku: $\rightarrow$

Svaki piksel možemo da predstavimo kao broj od 0 do 254 (1 bajt po tački):

15   15   16   17   36   64   98  100  102   91   58   32   16   15   15   15
13   13   21   62  126  152  146  117  113  129  113   82   38   17   13   13
13   20   76  130  123  102   98   94  103   97   69   61   63   48   16   13
14   51  106  111  106   92   94  106  105   60   48   53   67   89   32   13
27   88   93  117  119  123  138  142  105   92   95   89  126   74   53   18
49  106   75   79  116  123  148  140  100   94   65   42   68   84   74   26
65  111   96   64   97  116  133   94   58   71   61   43   46   71   89   37
68   79   87   72  103  113   97   65   38   38   39   45   39   44   59   41
73   87   96   98   61  115  127   92   54   35   31   51   65   51   50   34
78  123   93  121   62   92  140  179  160   79   54   62   56   54   47   31
48  128  110  116  100  109  152  191  169   98   85  110   78   81   47   22
25  105  129  117  162  143  161  153  111   77   83  114  127  110   47   15
13   39   99  142  134  156  156  141  129  116   91   72   81   54   23   11
13   16   56  122  157  174  177  184  175  152  137  125   82   33   15   13
13   13   16   47  108  153  170  174  169  159  136   85   33   15   13   13
13   14   14   15   28   50   77   95   92   73   47   25   14   13   13   14

Odgovarajuća matrica sa transformacijama za gorenavedenu sliku je:

 c =
 Kolone od 1 do 9 
      1261.81        -89.77       -111.26         60.40       -211.55         38.55         -6.57         50.41       -107.94
       185.28         -6.28        -85.36         25.34        -19.40         -6.97        -26.57         -6.15         -5.93
      -459.28         96.04       -207.56        -37.82         62.54        -36.87         22.57        -79.14        110.33
      -127.61        -10.48         22.63         14.02         22.99        -32.78         42.07         20.15        -10.29
       -33.75        -21.63          6.19         -6.48        123.49        -21.04         76.51         44.30        -43.36
        53.28         -7.03        -59.99         -2.59          5.94         12.59         32.83          4.98         16.12
       -79.28          3.98         68.84        -30.48         79.04         67.65        -48.17         -8.62        -28.65
       -28.00         24.26         41.93        -26.95         -1.08         15.87        -17.47        -13.94        -14.03
       -27.19        -19.87         32.59         31.43        -22.00        -39.76        -22.72         23.78         -3.44
        -4.52         -0.61          0.31         -2.70          9.35         -3.92         -7.20          6.88        -11.51
       -16.76         10.45         23.71         -0.64          2.73          0.33        -35.53          9.55         18.84
       -14.34         -5.74          4.75         11.88         24.15         -6.16        -31.85          7.85          4.19
       -19.91         -5.55         18.52          4.68         -4.06        -11.17        -20.09         -3.31         14.38
       -10.55          6.96          5.49        -23.66          3.02         25.10         -6.49         -8.63         13.34
        -6.59          4.23         14.09          2.61         -0.29         10.38         -0.84        -29.07          2.24
        -3.29          5.56          5.68         -8.23         -4.67          8.90          1.45         -7.65          7.80
  
 Kolone od 10 do 16 
        12.67        -71.27        -15.16        -28.12        -14.84         24.63          1.72
       -12.99         11.97          1.35         -2.38          7.39         -6.12         -4.09
        -4.73         56.27         25.48         23.37         -8.47         15.60         -0.03
        17.96          6.11        -12.49          2.70          5.69         11.16         10.13
         9.49         44.42          7.37         -9.81         17.71        -30.34         -5.89
        -5.45        -28.14         15.10         -8.73        -24.92          7.11         -4.06
        -8.69        -55.78        -20.41        -18.60         -3.73         -6.31          3.11
        -6.35          6.11          5.61          3.06         10.40        -11.85        -14.25
         0.90          4.13        -16.92         20.55         10.17         16.37        -12.18
        -1.43         11.08         -1.77          1.72          2.76         -0.82          3.25
       -28.03         11.14          7.63          4.37          9.73          1.41         16.25
        -1.55         12.57         -5.11          2.74         -0.30         -4.75          9.78
        11.08          7.05          3.36         -0.87         -3.00        -10.38         -4.98
        -3.88        -12.27         -0.19         -2.17          0.41          7.98          2.57
        19.26         -3.34          9.12          3.06        -11.28         -5.90        -11.63
         4.16         -3.32          3.24         -4.36         -1.08          5.12         -2.76

Krajnje je očigledno koji su koeficijenti najvažniji. Kada bi želeli da kompresujemo sliku, mogli bi da izbacimo na primer sve koeficijente čija je apsolutna vrednost manja od 100 ili relativna vrednost od najvećeg koeficijenta manja od 60%, te da zaokružimo sve na cele brojeve i da ih onda pomoću nekog od postupaka kodiramo. Takvu transformisanu „sliku“ (pošto više nije reč o slici već o njenim koeficijentima!) šaljemo kroz kanal, a na drugoj strani je „otpakujemo“ i shodno tome vršimo inverznu transformaciju.

Primer 2

Predstavljene su sledeće slike sa odgovarajućim koeficijentima (koristi se logaritmička skala i apsolutna vrednost svakog koeficijenta):

 $\rightarrow$ 

 $\rightarrow$