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 Pi je pravdepodobnosť výskytu i-teho znaku zdrojovej abecedy a ni 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.
Aritmetický kód
Ako sme 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 entropii.
Princíp tohto kódu spočíva v rozdelení symbolov do polootvorených intervalov pravdepodobnosti. Symboly sa potom kódujú postupne delením intervalu 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 intervaly 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 pôvodný interval (0, 1> sa skráti na <2/9, 4/9). 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.
Určenie veľkosti aktuálneho intervalu
, kde H je horná L je dolná hranica aktuálneho intervalu a
Určenie hornej hranice po zakódovaní nasledujúceho znaku
Určenie spodnej hranice po zakódovaní nasledujúceho znaku
Po získaní posledného intervalu je výsledným kódom najnižšie číslo tohto intervalu <0.366714; 0.366716) prevedené do binárneho tvaru. 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