From Wikipedia, the free encyclopedia
Дискретна косинус трансформација (ДКТ) трансформише неки сигнал са реалним вредностима у амплитуде основног тона и његових хармоника. Има много сличности са дискретном Фуријеовом трансформацијом, а може се посматрати и као њен специјалан случај. Своју примену је нашла у многим (може се рећи: скоро свим) поступцима компресије, као што су на пример JPEG, MPEG и другим. Главна идеја иза ових компресија је декорелација информација између пиксела, пошто један пиксел често може да нам пружи доста информација о свом суседу (поготово када је слика „мутнија“, без оштрих ивица), тј. можемо да претпоставим са великом вероватноћом вредност (боју) суседних пиксела. У неким својим облицима, ДКТ се такође користи и у MP3 и OGG Vorbis компресијама.
Дискретна косинус трансформација неког реалног, дискретног и једнодимензионалног сигнала је овако дефинисана:
Инверзна ДКТ дефинисана је слично:
За обе једначине је иста функција:
Из саме дефиниције можемо на пример видети да је рецимо први (нулти) коефицијент ове трансформације донекле једнак средишњој вредности:
Као и код дискретне Фуријеове трансформације, и овде су основни вектори ортогонални:
Пошто су базе једна у односу на другу ортогоналне, једну од њих не можемо да изразимо у зависности од других (или формалније: оне су линеарно независне). Веома битна особина оваквих база је што не зависе уопште од сигнала који желимо да израчунамо. Тако можемо да их израчунамо пре примене (у слободно време, када немамо паметнија посла, на пример), а када загусти да их употребимо у једноставном производу матрица.
Бацимо мало подробнији поглед на ове векторе - и шта видимо? Они су симетрични, а тиме је и матрица која их представља ортогонална. Рецимо да је сигнал који желимо да трансформишемо написан у облику вектора. Конкретно, рачун изгледа овако:
је значи матрица коју користимо да сигнал трансформишемо. Инверзну ДКТ можемо такође написати у облику матрица:
а пошто су вектори ортогонални, ово је могуће извршити још ефикасније користећи се особинама ортогоналних матрица:
Дводимензионална трансформација изгледа овако:
Инверзна трансформација у две димензије:
Дводимензионална трансформација поседује прилично згодну особину да је можемо раздвојити, па прво трансформисти редове те онда колоне:
Иако је очигледно да свака тачка има свој пандан у коефицијенту, не треба их мешати. Коефицијент је „јачина“ таласа и са конкретном тачком нема „директне“ везе, али се зато дијаграм лепо може представити на слици исте величине.
Дискретна косинус трансформација смањује корелацију. Сваки пиксел трансформисане слике нема скоро никакве везе са својим комшијама. Коефицијенте који су премали или који нас не интересују можемо да избацимо и да снмимо само „интересантне“ (на пример, сортирамо их по величини и избацимо 40% најмањих). Сигнал (слика, звук итд.) ће се због тога мало помутити (поготово ако је реч о високим фреквенцијама, јер су оне најчешће задужене за оштре ивице), али је зато меморија потребна за њено складиштење видно умањена.
Један од начина да „брзо“ (пригодније би ипак било рећи брже) израчунамо коефицијенте дискретне косинус трансформације је примена већ постојећих алгоритама за дискретну Фуријеову трансформацију. Добар разлог за то је што су такви алгоритми због своје важности увелико доста добро имплементирани и распрострањени (у многим случајевима зато не морамо ни да их имплементирамо, довољно је да их применимо).
Погледајмо која је стога веза између косинус и Фуријеове трансформације! Дискретна косинус трансформација није Фуријеова трансформација са реалним коефицијентима, што се лако да проверити ако упоредимо њихове матрице. Ред сигнала можемо написати као спајање парних и непарних редова:
Оригиналну суму за трансформацију можемо раздвојити на два дела:
Рецимо да смо добили следећу слику:
Сваки пиксел можемо да представимо као број од 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%, те да заокружимо све на целе бројеве и да их онда помоћу неког од поступака кодирамо. Такву трансформисану „слику“ (пошто више није реч о слици већ о њеним коефицијентима!) шаљемо кроз канал, а на другој страни је „отпакујемо“ и сходно томе вршимо инверзну трансформацију.
Представљене су следеће слике са одговарајућим коефицијентима (користи се логаритмичка скала и апсолутна вредност сваког коефицијента):
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.