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 - kódovanie
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.
,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
Kde N je optimálna dĺžka zakódovanej postuppnosti, Pi sú pravdepodobnosti prvkov, Hh a Dh sú horná a dolná hranica výsledného intervalu.
Prevod Prevod desatinného čísla na binárne môžeme vykonať pomocou algoritmu na obr. 6.
Pere analyzovaný príklad môžeme písať:
1: 0.366714 . 2 = 0.7334280
2: 0.733428 . 2 = 1.466856
3: 0.466856 . 2 = 0.933712
...
19: ...
Výpočet končí keď získame posledné binárne číslo teda po 19-tich iteráciách. Výsledné binárne číslo bude: 0.0101110111100000101. Pre proces dekódovania je potrebné aby na strane dekodéra boli známe pravdepodobnosti symbolov zdrojovej abecedy a tiež musí byť známa dĺžka postupnosti.
Obr. 6 Algoritmus prevodu desatinného čísla na binárny tvar
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 teda 0.144492 : (2/9), tak dostaneme novú hodnotu 0.650214 , ktorá zodpovedá prvku 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 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. 7 Tvary šablóny pre JBIG algoritmus (X - bod šablóny O - pozícia kódovaného op)
Ak sú určené pravdepodobnosti, ď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.
Widget Connector | ||
---|---|---|
|
Widget Connector | ||
---|---|---|
|
Widget Connector | ||
---|---|---|
|