Pod pojmom kompresia potom budeme rozumieť cielenú činnosť, ktorej výsledkom je redukcia objemu dát so zreteľom na maximálne zachovanie informačného obsahu. Inými slovami ide o zmenšenie množstva dát, pričom informácia, ktorú nesú, musí byť zachovaná.  V prípade kompresie obrazov alebo videa hovoríme o videokompresii. V definícii je zámerne použité spojenie „maximálne zachovanie informačného obsahu“. Kompresia totiž môže byť stratová a bezstratová.

Pri bezstratovej videokompresii je požiadavka taká, že po spätnej rekonštrukcii obrazovej informácie musí byť táto identická s pôvodnou. Toto je docielené odstránením irelevancie a redundancie z pôvodného informačného obsahu. Redundancia je nadbytočná informácia, ktorá sa dá obnoviť. Irelevancia je nadbytočná (nepodstatná) informácia, ktorá nemá význam (napr. pri prenose obrazu nemá význam prenášať obraz v spektrálnych oblastiach, ktoré ľudské oko nevidí).  Pri stratovej videokompresii dochádza okrem potlačenia redundancie aj k strate informácie. Typickým príkladom stratového odstránenia redundancie je kvantovanie. Využíva sa tu takzvaná prijateľná úroveň straty informácie, ktorá je vyhodnocovaná subjektívnymi technikami vyhodnocovania kvality. Vo všeobecnosti stratovými technikami je dosiahnutá omnoho väčšia kompresia ako pri bezstratových technikách.

Kompresia sa dosahuje dvoma spôsobmi a v mnohých prípadoch aj ich spojením. Prvým spôsobom je dekorelácia vstupných údajov. Je zrejmé, že vysielané údaje obsahujú veľa redundancie vyplývajúce zo vzájomnej korelovanosti jednotlivých obrazových prvkov (op). Preto je vhodné túto koreláciu odstrániť. Dekoreláciu je možné vykonať pomocou diskrétnych ortogonálnych transformácií (DOT), predikčnými technikami alebo ich hybridnou kombináciou. Druhý spôsob kompresie je zabezpečený efektívnym kódovaním, ktoré spočíva v návrhu takého kódu, ktorý využíva štatistickú závislosť vstupnej postupnosti op. Takéto kódy sa nazývajú kódy s premenlivou dĺžkou kódového slova. Do tejto skupiny kódov patrí napríklad Huffmanov, Shano-Fannov kód alebo aritmetický kód. Na obr. 1 je zobrazený všeobecný kompresný model.

Obr. 1 Všeobecný kompresný model

Z obr. 1 je vidieť, že 3D vizuálna scéna je snímaná (teda vzorkovaná) niektorou z techník snímania obrazu. Uvažujme diskrétne metódy, pri ktorých odpadá nutnosť zaradenia A/D prevodníka. O problematike vzorkovania, ktorá nie je náplňou tohto predmetu sa čitateľ dozvie napr. z tejto literatúry. Následne môže byť tento diskrétny signál dekorelovaný niektorou z techník, ktoré budú náplňou neskorších prednášok. V  procese dekorelácie je signál prevedený do niektorého transformovaného priestoru. Najčastejšie sa stretávame s priestorom predikčných koeficientov (Predikčné kódovanie) alebo s priestorom transformačných koeficientov (Transformačné kódovanie). Nasleduje blok Kvantovania, kde je využitá niektorá z techník kvantovania. Blok kódovania, ktorým sa budeme podrobne zaoberať na tejto prednáške implementuje  prevod kvantovaných hodnôt signálu na kódové slová, ktorých dĺžka môže byť rovnaká pre každú úroveň, alebo sa môže meniť v závislosti od štatistických vlastnosti obrazu. Ak hovoríme o kódovaní v procese kompresie, vždy máme na mysli zdrojové kódovanie. Zdrojové kódovanie si netreba zamieňať s kanálovým kódovaním, ktoré sa v prenose obrazu používa, no nie v súvislosti s kompresiou. V procese dekorelácie sú kvantované hodnoty transformačných koeficientov opätovne prevedené na hodnoty obrazových prvkov, ktoré tvoria maticu rekonštruovaného obrazu.

Kódovanie obrazu

Proces kódovania kvantizačných hodnôt spočíva v priradení binárneho čísla každej kvantizačnej hodnote. Toto priradenie musí byť jednoznačné, t.z. každá kvantizačná hodnota alebo ich postupnosť musí mať jedinečný binárny kód a zároveň binárny kód jednej kvantizačnéj úrovne nesmie byť prefixom kódu inej. V procese kódovania často hovoríme o Zdrojovej abecede, ktorá predstavuje vstupné znaky (kvantizačné úrovne) a kódovej abecede, ktorá obsahuje kódové slová. Kódy môžeme rozdeliť do niekoľkých kategórií.

Rovnomerné kódy - kódy s pevnou dĺžkou kódového slova

Tieto kódy priradia každému znaku zdrojovej abecedy kód rovnakej dĺžky. Pri týchto kódoch teda nedochádza k žiadnej kompresii. Ide napríklad o BCD (binárny kód) alebo Grayov kód, ktorý má oproti BCD kódu výhodu v tom, že kódové slová nasledujúce za sebou sa líšia iba v jednom bite. V tab. 1 je zobrazená kódová abeceda s dĺžkou slova 3 bity pre BCD a Grayov  kód.

Nerovnomerné kódy - kódy s premenlivou dĺžkou kódového solova

Tieto kódy zohľadňujú štatistické vlastnosti zdrojovej abecedy a predstavujú kompresné kódovanie. Hovoríme, že sú to entropické kódy. Ich podstata spočíva v tom, že znakom zdrojovej abecedy, ktoré sa vyskytujú často, budú priradené krátke kódové slová a znakom, ktoré sa vyskytujú zriedkavo, zasa dlhšie kódové slová. Vo výsledku vypočítaná stredná dĺžka kódového slova pre celý zakódovaný obraz bude menšia oproti tomu, ak by bol použitý rovnomerný kód. Medzi nerovnomernými kódmi majú významné miesto tzv. prefixové kódy. Každé prefixové kódovanie je jednoznačne dekódovateľné, to je aj dôvod, prečo sú prefixové kódy také významné. To, čo ich však odlišuje od ostatných jednoznačne dekódovateľných kódov, je fakt, že sú to jediné kódy, ktoré je možné dekódovať znak po znaku od začiatku. Takže hocijakú správu môžeme dekódovať už počas jej prijímania, nie je nutné poznať celú správu. Medzi najznámejšie nerovnomerné kódy patrí Huffmanov a Shannon-Fanov kód.  Pred samotným popisom uvedených kódov je však potrebné zadefinovať pojem stredná dĺžka kódového slova, entrópia, účinnosť kódu, redukovaná redundancia . 

Strednú dĺžku kódového slova vypočítame ako:

kde P_i je pravdepodobnosť výskytu i-teho znaku zdrojovej abecedy a n_i je dĺžka kódového slova priradeného danému znaku, N je počet prvkov zdrojovej abecedy.

Pod pojmom entrópia rozumieme stredné množstvo informácie pripadajúce na jeden znak. Entrópiou nultého rádu je potom určená minimálna stredná dĺžka kódového slova. To znamená, že pri daných štatistických vlastnostiach obrazu nie je možné použiť kód s kratšou strednou dĺžkou ako je daná entrópiou nultého radu. Entropia je veľmi významný parameter v oblasti kompresie a kryptografie.

Účinnosť kódovania vyhodnocujeme pomerom medzi entrópiou nultého rádu a dosiahnutou strednou dĺžkou kódového slova.

Redukovaná redundancia predstavuje rozdiel medzi dĺžkou kódového slova rovnomerného kódu (rk) v prípade jeho použitia a strednou dĺžkou kódového slova nerovnomerného kódu . Vyjadruje teda stredné množstvo ušetrených bitov.

Je nutné poznamenať, že kódovací systém používajúci prefixový kód musí mať na výstupe zaradenú pamäť (buffer), aby sa zabezpečila konštantná prenosová rýchlosť. 

Aritmetický kód - kódovanie

Ako sme si ukázali, použitím prefixových kódov je možné dosiahnuť kompresiu údajov. Nevýhodou týchto kódov je, že symboly sa musia kódovať pomocou celočíselného počtu bitov. Tento nedostatok odstraňuje aritmetický kód, ktorý sa strednou dĺžkou kódového slova ešte viac približuje entrópii.

Princíp tohto kódu spočíva v rozdelení symbolov do polootvorených intervalov pravdepodobnosti. Symboly sa potom kódujú postupne delením ceklého intervalu pravdepodobností <0, 1) na menšie subintervaly. Pre nami uvažovaný príklad (obr. 3) najprv preusporiadame maticu obrazových prvkov na vektor symbolov takto : CEB EEE ADC. Jednotlivým symbolom  potom pridelíme subintervaly pravdepodobnosti takto:

Proces kódovania začína privedením prvého znaku na vstup kodéra. Prvý znak C je z intervalu <2/9, 4/9) to znamená, že z pôvodného intervalu pravdepodovností <0, 1) sa vyberie subinterval <2/9, 4/9). Tento "nový" interval sa rozdelí na subintervaly úmerne zodpovedajúcim pravdepodobnostiam symbolov (viď Obr.7). Príchodom ďalšieho znaku E sa tento interval skráti nasledovne. Spodnú hranicu nového intervalu určíme ako súčet spodnej hranice aktuálneho intervalu a súčinu rozsahu aktuálneho intervalu a spodnej hranice aktuálne kódovaného prvku. Teda pre 2. znak E spodná hranica bude 2/9 + [(4/9-2/9).5/9] = 28/81=0.345679. Hornu hranicu určíme ako súčet spodnej hranice aktuálneho intervalu a súčinu rozsahu aktuálneho intervalu a hornej hranice aktuálne kódovaného prvku. Teda horná hranica bude 2/9 + [(4/9-2/9).9/9] =4/9=0.444444. Nový interval ktorý kóduje dvojicu znakov CE je (0.345679, 0.444444>. Ďalší prvok v poradí je B, ktorý sa zakóduje do intervalu (0.356653, 0.367627>.  Rovnakým postupom  sa zakódujú aj ostatné symboly. Tento postup možno zhrnúť do algoritmu pozostávajúceho z troch krokov. Graficky je tento postup zobrazený na obr. 6.

Po získaní posledného intervalu je výsledným kódom  číslo patriace do tohto intervalu <0.366714; 0.366716) prevedené do binárneho tvaru (môže a nemusí to byť dolná hranica výsledného intervalu pravdepodobností). Počet potrebných bitov je daný ako rozdiel hraníc výsledného intervalu alebo súčin pravdepodobnosti všetkých kódovaných znakov

Aritmetický kód - dekódovanie

Algoritmus aritmetického dekódovania je opačný proces ku kódovaniu. Zakódovanú správu  0.0101110111100000101 prevedieme naspäť do desiatkovej sústavy. Pretože sme použili dolnú hranicu na vytvorenie výsledného kódového slova, potom zodpovedajúce desatinné číslo je 0.366714. Dekodér musí poznať aj  pravdepodobnosti symbolov. Tak ako pri kódovaní, jednotkový interval rozdelíme na subintervaly tak, aby ich veľkosť bola proporcionálna s pravdepodobnosťou výskytu jednotlivých op. Vidíme, že toto desatinné číslo vpadne do subintervalu, ktorý reprezentuje prvok C. Potom odčítame dolnú hranicu prvku C, čím získame číslo 0.144492, ktoré vydelíme šírkou intervalu pre prvok C, t.j. 0.144492 : (2/9). Tak dostaneme novú hodnotu 0.650214 , ktorá vpadá do intervalu pre prvok s označením E . Takto pokračujeme ďalej, kým dekódujeme celú zakódovanú správu.

Stavový binárny aritmetický kód

Ako je už z názvu zrejmé, stavový AK sa aplikuje na binárne obrazy. Pre kódovanie obrazov s bitovou hĺbkou väčšou ako 1b je potrebné tieto obrazy previesť na bitové roviny a tieto kódovať samostatne. Na strane prijímača sa po dekódovaní všetkých rovín zostaví výsledný multi-úrovňový obraz. 

Pri stavovom binárnom aritmetickom kódovaní (SBAK) je estimácia pravdepodobnosti obrazového prvku (op) vykonávaná na základe informácie o stave viacerých okolitých op. Rozloženie skúmaných op v estimátore určuje šablóna. Šablóna určuje rozloženie jednotlivých predchádzajúcich op voči aktuálnemu op a jej tvar môže byť ľubovoľný, ale musí byť v súlade s postupom kódovania jednotlivých op binárneho obrazu. To znamená, že ak obraz sa kóduje po riadkoch z ľavého horného rohu smerom k pravému dolnému rohu obrazu, tak všetky op šablóny musia ležať pred alebo nad aktuálnym op. Výsledkom analýzy je určenie viacej pravdepodobnej hodnoty, resp. menej pravdepodobnej hodnoty pre jednotlivé stavy šablóny. Pritom pod stavom sa rozumie možná kombinácia op obrazu v šablóne.

Obr. 8 Tvary šablóny pre JBIG algoritmus (X - bod šablóny O - pozícia kódovaného op)

Ak sú určené pravdepodobnosti jednotlivých stavov, ďalej sa postupuje analogicky ako pri „klasickom“ aritmetickom kódovaní. Najprv sa však zistí zodpovedajúci stav a podľa jeho pravdepodobností sa rozdeľuje aktuálny interval na dielčie subintervaly pravdepodobnosti.

Pulzne kódová modulácia (PCM)

Kódovací systém, ktorý neaplikuje algoritmy dekorelácie a symboly kóduje pomocou rovnomerného kódu nazývame PCM systém. Tento systém prakticky nedosahuje žiadnu kompresiu údajov, resp. len kompresiu zavedenú kvantizáciou. Tento systém sa však v začiatkoch telekomunikačných služieb využíval a dnes ho považujeme za referenčný kódovací systém. Efektivitu ostatných systémov budeme vyhodnocovať na základe porovnania s týmto systémom.