Kompresia a všeobecný kompresný model

Kompresia je v súčasnosti veľmi žiadaná. Na kvalitu služieb sprostredkúvajúcich multimediálny obsah sú kladené stále vyššie požiadavky. Jednou z týchto požiadaviek je aj rýchlosť sprostredkovania multimediálneho obsahu a následne efektívne využitie úložného priestoru. Tieto požiadavky sú však v konflikte so súčasným trendom poskytovania informačného obsahu vysokým objemom. K týchto naplneniu požiadaviek účinne napomáha kompresia. Pred zavedením definície pre kompresiu je potrebné definovať pojem Informácia a správa.

• Informácia je to súbor nových poznatkov o určitej udalosti, objekte, procese a má náhodný charakter. Materiálnym nosičom informácie je signál a ten slúži na jej prenos v priestore a čase.

• Správa je vo všeobecnosti všetko, čo podlieha prenosu od odosielateľa k príjemcovi (napr. hovor, text, obraz). Správa je vhodnou formou vyjadrená informácia. Pri prenose obrazov správa predstavuje časovú (pri videu) alebo priestorovú zmenu (video aj statický obraz) jasu prvkov obrazu.

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á 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 sa baví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 úrovne nesmie byť prefixom kódu inej úrovne. 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 entopické 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 ak sa vypočíta stredná dĺžka kódového slova pre celý zakódovaný obraz bude menšia ako by tomu bolo 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, entropia, úč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.

Pod pojmom entropia rozumieme stredné množstvo informácie. Entropiou 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á entropiou nultého radu. Entropia je veľmi významný parameter v oblasti kompresie a kryptografie.

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

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