Дискретна косинус трансформација

Из пројекта Википедија

Дискретна косинус трансформација (ДКТ) трансформише неки сигнал са реалним вредностима у амплитуде основног тона и његових хармоника. Има много сличности са дискретном Фуријеовом трансформацијом, а може се посматрати и као њен специјалан случај. Своју примену је нашла у многим (може се рећи: скоро свим) поступцима компресије, као што су на пример JPEG, MPEG и другим. Главна идеја иза ових компресија је декорелација информација између пиксела, пошто један пиксел често може да нам пружи доста информација о свом суседу (поготово када је слика "мутнија", без оштрих ивица), тј. можемо да претпоставим са великом вероватноћом вредност (боју) суседних пиксела. У неким својим облицима, ДКТ се такође користи и у MP3 и OGG Vorbis компресијама.

Садржај

1 Дефиниција
2 Компресија
3 Брзо израчунавање ДКТ-а
- 3.1 Помоћу дискретне Фуријеове трансформације
4 Примери
- 4.1 Пример 1
- 4.2 Пример 2

[уреди] Дефиниција

Дискретна косинус трансформација неког реалног, дискретног и једнодимензионалног сигнала $f (x)$ је овако дефинисана:

$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$

Инверзна ДКТ дефинисана је слично:

$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$

За обе једначине је $α(u)$ иста функција:

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

Из саме дефиниције можемо на пример видети да је рецимо први (нулти) коефицијент ове трансформације донекле једнак средишњој вредности: $C(u=0) = \sqrt{ \frac{1}{N}} \sum_{x=0}^{N-1} f(x)$

Као и код дискретне Фуријеове трансформације, и овде су основни вектори ортогонални:

$b_u = \left [ \cos \left ( \frac{\pi (2\cdot0+1) u }{2N} \right ), \cos \left ( \frac{\pi (2\cdot1+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 > = c o n s t

Пошто су базе једна у односу на другу ортогоналне, једну од њих не можемо да изразимо у зависности од других (или формалније: оне су линеарно независне). Веома битна особина оваквих база је што не зависе уопште од сигнала који желимо да израчунамо. Тако можемо да их израчунамо пре примене (у слободно време, када немамо паметнија посла, на пример), а када загусти да их употребимо у једноставном производу матрица.

Бацимо мало подробнији поглед на ове векоторе - и шта видимо? Они су симетрични, а тиме је и матрица која их представља симетрична. Рецимо да је $f$ сигнал који желимо да трансформишемо написан у облику вектора. Конкретно, рачун изгледа овако:

$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$ је значи матрица коју користимо да сигнал трансформишемо. Инверзну ДКТ можемо такође написати у облику матрица:

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

а пошто су вектори ортогонални, ово је могуће извршити још ефикасније користећи се особинама ортогоналних матрица:

$A^{-1} = A^T \Rightarrow f = A^T T A^T$ (

A T

значи А матрица транспонирана).

Дводимензионална трансформација изгледа овако:

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

Инверзна трансформација у две димензије:

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

Дводимензионална трансформација поседује прилично згодну особину да је можемо раздвојити, па прво трансформисти редове те онда колоне:

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

Иако је очигледно да свака тачка има свој пандан у коефицијенту, не треба их мешати. Коефицијент је "јачина" таласа и са конкретном тачком нема "директне" везе, али се зато дијаграм лепо може представити на слици исте величине.

[уреди] Компресија

Дискретна косинус трансформација смањује корелацију. Сваки пиксел трансформисане слике нема скоро никакве везе са својим комшијама. Коефицијенте који су премали или који нас не интересују можемо да избацимо и да снмимо само "интересантне" (на пример, сортирамо их по величини и избацимо 40% најмањих). Сигнал (слика, звук итд.) ће се због тога мало помутити (поготово ако је реч о високим фреквенцијама, јер су оне најчешће задужене за оштре ивице), али је зато меморија потребна за њено складиштење видно умањена.

[уреди] Брзо израчунавање ДКТ-а

[уреди] Помоћу дискретне Фуријеове трансформације

Један од начина да "брзо" (пригодније би ипак било рећи брже) израчунамо коефицијенте дискретне косинус трансформације је примена већ постојећих алгоритама за дискретну Фуријеову трансформацију. Добар разлог за то је што су такви алгоритми због своје важности увелико доста добро имплементирани и распрострањени (у многим случајевима зато не морамо ни да их имплементирамо, довољно је да их применимо).

Погледајмо која је стога веза између косинус и Фуријеове трансформације! Дискретна косинус трансформација није Фуријеова трансформација са реалним коефицијентима, што се лако да проверити ако упоредимо њихове матрице. Ред сигнала $f (x)$ можемо написати као спајање парних и непарних редова:

$\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$

Оригиналну суму за трансформацију можемо раздвојити на два дела:

$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 u x}{N} } \right ) = \operatorname{Re} \left ( \alpha(u) \cdot \operatorname{W}_{2N}^{ \frac{u}{2} } \cdot \operatorname{DFT} \left \{ \tilde f(x) \right \}_{N} \right )$

[уреди] Примери

[уреди] Пример 1

Рецимо да смо добили следећу слику: $\rightarrow$

Сваки пиксел можемо да представимо као број од 0 до 254 (1 бајт по тачки):

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

Одговарајућа матрица са трансформацијама за горенаведену слику је:

 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

Крајње је очигледно који су коефицијенти најважнији. Када би желели да компресујемо слику, могли би да избацимо на пример све коефицијенте чија је абсолутна вредност мања од 100 или релативна вредност од највећег коефицијента мања од 60%, те да заокружимо све на целе бројеве и да их онда помоћу неког од поступака кодирамо. Такву трансформисану "слику" (пошто више није реч о слици већ о њеним коефицијентима!) шаљемо кроз канал, а на другој страни је "отпакујемо" и сходно томе вршимо инверзну трансформацију.