Diplomová práca: Digitálne spracovanie obrazových sekvencií

Obálka zviazanej verzie diplomovej práce

KATEDRA RÁDIOELEKTRONIKY
FAKULTA ELEKTROTECHNIKY A INFORMATIKY
TECHNICKÁ UNIVERZITA KOŠICE

DIPLOMOVÁ PRÁCA
Digitálne spracovanie obrazových sekvencií
Poprad 1995
Tomáš J. Fülöpp

Ďakujem Ing. Michalovi Fedorovi za pomoc a rady, ktoré mi poskytol počas práce na tomto diele.

Čestne prehlasujem, že som túto diplomovú prácu vypracoval celkom samostatne a použil som iba literatúru, ktorú uvádzam v zozname.
Košice 18.4.1995
Tomáš J. Fülöpp

OBSAH

1. ÚVOD

Obrazová informácia, najkomplexneší a najdôležitejší zdroj poznatkov, ktoré je človek schopný vnímať z prostredia, ktoré ho obklopuje, preniká do ľudského mozgu prostredníctvom najdokonalejšieho ľudského zmyslového receptora - okom. Z technického hľadiska je oko akomodatívny optický detektor svetelného žiarenia, s prenosovou rýchlosťou odhadnutou na tri milióny bitov za sekundu (6) a takou vysokou citlivosťou, že dokáže zaregistrovať dopad už jedného jediného fotónu. Priestorovou distribúciou viditeľného svetla odrazeného od - alebo vyžarujúceho z - okolitých predmetov vzniká vnem, ktorý ľudský mozog identifikuje ako obraz so všetkými jeho vlastnosťami, ako sú rozmery, hĺbka a perspektíva, farby, odtiene atď a ich zmeny.

Človek zrakom získava obrazovú informáciu o nejakej udalosti jednak priamo, jednak sprostredkovane. Sprostredkovanú obrazovú informáciu získava okrem iných zdrojov aj z televíznej obrazovky, ktorá využíva ďalšie špecifické vlastnosti ľudského oka - zotrvačnosť, teda fakt, že ak sa obrazy striedajú rýchlosťou väčšou ako približne 20 obrazov za sekundu, človek ich už nevníma ako jednotlivé obrazy, ale ako kontinuálne sa meniacu scénu. Ďalšou špecifickou vlastnosťou oka je jeho obmedzená rozlišovacia schopnosť, vďaka ktorej obraz na obrazovke, ktorý je vlastne maticou diskrétnych bodov rôzneho jasu a farby, na sietnici oka splýva do obrazu s plynulými prechodmi.

Keďže sprostredkovaná obrazová informácia je nesmierne dôležitým informačným prostriedkom, na jej rozvoj sa kladie veľký dôraz. Veľmi perspektívnou oblasťou, v ktorej sa uplatňuje najmodernejšia číslicová technika, je spracovanie obrazu, jeho kódovanie a prenos v digitálnej forme. Kódovaniu, respektíve kompresii obrazu a obrazových sekvencií, som sa venoval v rámci tejto mojej diplomovej práce.

Na začiatku sa zaoberám vlastným významom kódovania, základnými druhmi redundancie a princípmi niektorých kompresných metód, ktoré tieto redundancie minimalizujú. V ďalšej časti nechýba krátky pohľad na nové, perspektívne svetové štandardy pre kompresiu fotografických obrazov a obrazových sekvencií. Ďalej popisujem kompresné metódy vhodné pre obrazové informácie, najmä hierarchickú reprezentáciu a špeciálne kompresiu pomocou kvadrantového stromu obrazu, ktorá sa spomína v zadaní tejto práce. Potom nasleduje popis činnosti a výsledky programu pre kódovanie obrazových sekvencií BF kódom a následné zakódovanie výstupnej informácie pre tento účel vyvinutým kódom RL-BIT.

Orientácia na výskum v oblasti kompresie obrazových sekvencií je v našich podmienkach samozrejme možná len v oblasti programových modelov, pretože pre realizáciu systémov fungujúcich v reálnom čase dosiaľ nie je k dispozícii dostatočne rýchle technické vybavenie.

2. VÝZNAM KÓDOVANIA

Pod číslicovým spracovaním obrazu rozumieme jednak prevod reálneho obrazu do digitálnej podoby, jednak celý rad špeciálnych postupov ako je kolorovanie, filtrovanie, rozpoznávanie a klasifikácia objektov, zmena rozmerov či tvaru. Sem patrí tiež kódovanie a jeho špeciálny prípad, kompresia, ktorou sa budem ďalej zaoberať.

Kódovanie obrazu je transformácia, ktorá je nevyhnutná pre efektívny zápis obrazovej informácie na pamäťové médium (pamäť počítača, disketa, pevný či optický disk apod), alebo na jej prenos spojovými kanálmi v číslicovej podobe. Zvyčajne sa požaduje exaktná, a teda plne reverzibilná transformácia, pri ktorej sa zachováva informačná hodnota každého obrazového bodu, ale v záujme ďalšej redukcie objemu dát sa využívajú i metódy, ktoré nie sú plne reverzibilné, to znamená, že po dekódovaní je obraz rekonštruovaný iba s istým stupňom vernosti. Kódovanie číslicovej reprezentácie obrazu sa rieši ako úloha hľadania optima medzi zmenšením východiskového rozsahu obrazových údajov na jednej strane, a dosiahnutou vernosťou rekonštruovaného obrazu na strane druhej. Zvyčajne je pritom daný typ a prípustná miera skreslenia obrazu, pre ktorú sa hľadá algoritmus minimalizujúci objem obrazových údajov. Pre kódovanie obrazov s týmto zameraním sa používa názov kompresia obrazových údajov (v angliátine sa stretneme s výrazom Image Data Compression).

Kódovacie postupy sú kombinačné, ak na kódovanie stači znalosť zdrojového znaku a sekvenáné, ktoré pri kódovaní využívajú okrem znalosti zdrojového znaku aj informácie z predchádzajúceho procesu kódovania.

Efektívny kód je taký, ktorý na vyjadrenie kódového znaku využíva čo najmenší počet symbolov. Žiadny kód nie je úplne efektívny.

Na vyjadrenie účinnosti kompresie sa používa činiteľ kompresie, čo je parameter vyjadrujúci efekt zhustenia (kompresie) dát a možno ho vyjadriť v tvare Cr = N / Nk, kde N je počet jednotiek (bitov, bytov) nezakódovanej správy a Nk je počet jednotiek zakódovanej správy. Pre efektívne kódovanie musí platiť, že Cr > 1.

Kompresia je principiálne veľmi podobná komunikačnému kanálu v tom, že kóduje sekvenciu bytov do umelého formátu za účelom fyzického zaobchádzania, a neskôr dekóduje kompresovaný obraz naspäť do presnej kópie pôvodného obrazu.

Ako som už spomenul, kompresia je potrebná kvôli zvýšeniu kapacity pamäťových médií a tiež kvôli zvýšeniu rýchlosti prenosových sústav. Prenosové sústavy číslicovej informácie na väášie vzdialenosti sú vo všeobecnosti sériové, takže vyslanie obrazovej informácie znamená vyslanie istej postupnosti impulzov. Rýchlosť je možné zvyšovať tak, že sa zvýši prenosová frekvencia, ale len po hranicu rýchlosti vysielača a prijímača (hraniáná frekvencia prenosovej trasy je v súčasnosti vďaka využitiu optických vlákien menším problémom). Nie nepodstatné sú tu však vysoké náklady spojené s vysokorýchlostnými prenosovými zariadeniami. Kódovanie znamená skrátenie informácie a teda skrátenie doby prenosu pri nezmenenej rýchlosti prenosu.

3. REDUNDANCIA

Kompresia údajov sa dosahuje redukciou irelevancie (nepodstatnej zložky) a redundancie (nadbytočnej zložky) signálu. Redukcia irelevancie v procese efektívneho kódovania signálov je nevratný (ireverzibilný) proces, ktorý znamená informačnú stratu. Kritériom použitého stupňa redukcie irelevancie sú preto vlastnosti prijímača signálov. Redukcia redundancie je oproti tomu proces vratný (reverzibilný), pretože nadbytočná zložka signálu sa môže v prijímači obnoviť, pričom tento proces je nezávislý od vlastností prijímača signálov a nevedie k informačnej strate.

Data uchovávané na diskoch či iných pamäťových médiách, alebo prenášané cez komunikačné kanály v komeráných počítačových systémoch, obsahujú vo všeobecnosti podstatnú redundanciu. Mechanizmus alebo procedúra, ktorá tieto údaje prekóduje za účelom zníženia redundancie, môže dvojnásobiť alebo strojnásobiť hustotu užitočných údajov v danej aplikácii.

Avšak čo sa týka výberu vhodných metód kompresie, existuje niekoľko základných problémov, ktoré dosiaľ zabraňujú rozšíreniu jedinej všeobecnej metódy kompresie. Napríklad (1) pridlhé časy de/kódovania pre väášie objemy dát, (2) väášina kompresných techník nie je dostatočne flexibilná nato, aby uspokojivo spracovala rôzne typy redundancie, (3) bloky kompresovaných údajov s nepredvídateľnými dĺžkami prinášajú problémy spojené s organizáciou uchovávania týchto dát. Každá technika kompresie obsahuje iný súbor takýchto problémov, a preto môže byť aplikovaná iba v systémoch, kde jej nedostatky nespôsobujú kritické problémy.

V komerčných datách je možno rozlíšiť štyri základné typy redundancie. Redundancia sa tu obmedzuje na to, čo je pozorovateľné v datovom toku (bez znalosti spôsobu, ako budú data interpretované). Redundancia vo forme nepoužívaných údajov, alebo špecifické aplikačné korelácie sa tu neuvažujú. Pre dobrú ilustráciu budú typy redundancie budú popísané tak, ako by mohli pozorované v dvoch typoch súborov: v anglických textoch (štatistické údaje o slovenských textoch autor nemal k dispozícii) a v inventárnych záznamoch výroby nejakého podniku. Popísané kategórie redundancie nie sú vzájomne celkom nezávislé - do istej miery sa prekrývajú.

3.1 Rozdelenie znakov

V typickom reťazci znakov sú niektoré znaky používané častejšie ako iné. Napríklad v osembitových ASCII reprezentáciách znakov takmer tri štvrtiny z možných 256 kombinácií zväčša nie sú v súbore použité. V dôsledku toho by z každej osembitovej jednotky mohli byť ušetrené dva bity, čo potom zodpovedá 25% úspore miesta/času. V anglickom texte sa znaky opakujú v dobre dokumentovanom rozdelení (najčastejšie znaky sú "e" a medzera. V inventárnom zázname podniku sú veľmi bežné numerické hodnoty - napríklad binárne údaje alebo desiatkové čísla typické pre daný súbor - sú redundantné, no redundancia sa následkom svojej závislosti na druhu textu výrazne mení. Napríklad identifikácia názvu predajne alfabeticky alebo numericky výrazne posúva znakové rozdelenie v súbore. Podobne rozsah, do ktorého sa popisný text objavuje v inventárnych záznamoch ovplyvní priemerný počet bitov potrebných na jeden znak.

3.2 Opakovanie znakov

Keď nastane prípad opakovania jedného znaku, správa môže byť zvyčajne zakódovaná kompaktnejšie ako len opakovaním symbolu znaku. Takéto reťazce sa v texte nachádzajú len zriedkavo (napríklad ako reťazec medzier či tabelátorov). Avšak vo formátovaných obchodných záznamoch, tabuľkách, sú reťazce medzier či tabelátorov veľmi časté. Inventárny záznam bude často obsahovať medzery v čiastočne zaplnených alfabetických poliach, reťazcoch z núl v desatinných číslach numerických polí, prípadne nulových reťazcoch v nepoužitých poliach. Grafické obrazy, špeciálne čiarové nákresy obchodnej grafiky, sú zväáša vyplnené homogénnymi plochami, ktoré sa dajú dobre kompresovať. (Ako uvidíme neskôr, kódovanie opakujúcich sa symbolov možno úspešne využiť pri kompresii GBW kódu obrazov pri BF kódovaní.)

3.3 Často používané sekvencie

Určité sekvencie znakov sa budú objavovať znova a znova s relatívne vysokou frekvenciou, a preto môžu byť reprezentované pomocou relatívne menšieho množstva bitov na sekvenciu v čase a priestore. V angliátine je napríklad bodka nasledovaná dvomi medzerami častejšia ako väášina iných trojznakových kombinácií, preto by mohla byť kódovaná s použitím menšieho počtu bitov. Mnoho dvojíc písmen, ako napríklad "ze", sú častejšie ako by vyplývalo z pravdepodobností jednotlivých písmen, preto by mohli byť zakódované pomocou menšieho počtu bitov ako majú dva znakové symboly použité spolu. Podobne, páry znakov, ktoré sa objavujú veľmi zriedka, by boli zakódované pomocou veľmi dlhých bitových kombinácií, aby sa bity využívali čo najefektívnejšie. V niektorých textoch sa často používajú určité kľúčové slová. Napríklad slovo "kompresia," ktoré sa často objavuje v tejto práci, by v prípadne kódovania tohto textu mohlo byť nahradené relatívne kratším kódom. (Respektíve, s ohľadom na gramatiku slovenčiny, by sme mohli uvažovať o sekvencii "kompres", ktorá je koreňom ďalších pádov a modifikácií ako "kompresie," "kompresný," "dekompresované" apod.) V inventárnych záznamoch sa veľmi často používajú niektoré identifikátory, ako názvy predajní, alebo tovaru. Numerické polia obsahujú časté sekvencie v tom zmysle, že obsahujú iba sekvencie číslic, bez primiešaných špeciálnych symbolov alebo písmen. Takéto polia môžu byť zakódované pomocou menej ako štyroch bitov na číslicu, zatiaľ čo v texte sú reprezentované piatimi až ôsmimi bitmi.

3.4 Pozičná redundancia

Ak sa určité znaky stabilne opakujú na nejakom predikovateľnom mieste v každom bloku dát, potom sú aspoň čiastočne redundantné. Príkladom tohto je rastrovo scanovaný obrázok obsahujúci vertikálnu čiaru. Vertikálna čiara sa opakuje ako bod na tej istej pozícii v každom scane, a mohla by byť preto zakódovaná kompaktnejšie. V inventárnych súboroch majú určité záznamové polia rovnaké pozície a návestia. Na druhej strane text nemá takmer žiadnu poziánú redundanciu.

Popísané štyri typy redundancií sa do určitej miery prekrývajú. Napríklad mnoho inventárnych numerických polí bude obsahovať prevažne krátke čísla. Tieto by mohli byť skompresované ako malá skupina často používaných sekvencií, ako prípady nulových reťazcov pred hodnotami čisel, ako váženie rozdelenia frekvencie znakov, alebo ako poziáná tendencia, ktorá by zobrala do úvahy, že dané pole bude mať takmer vždy numerické hodnoty s mnohými nulami. Tento typ redundancie teda môže spracovať takmer ktorýkoľvek kompresný mechanizmus.

3.5 Redundancia v obrazových sekvenciách

Pri spracovaní obrazových sekvencií (teda videosignálu) sa využíva redundancia obrazových údajov daná vysokou korelovanosťou po sebe nasledujúcich obrazov. Preto je často výhodné kódovať iba rozdielové (body zmien) informácie po sebe nasledujúcich obrazov. Táto charakteristika sa vzťahuje aj na možnosť predikcie. Napríklad je zrejmé, že obraz s konštantnou hodnotou videosignálu sa dá na základe tejto hodnoty úplne presne predikovať. Na druhej strane náhodné obrazové pole s bielym šumom je celkom nepredikovateľné. V prvom prípade obsahuje obraz maximálnu redundanciu, v druhom žiadnu. Pravda - tieto príklady sú extrémne. V praxi nasleduje v televíznom signále za sebou obrovský počet korelovaných obrazov, počet skokových zmien informácie (napríklad strih vo filme ai) je oproti tomu veľmi malý.

3.6 Iné typy redundancie

Existujú aj iné typy redundancie, napríklad pri digitalizovaných hlasových (hudobných) priebehoch. Údaje obsahujúce digitalizovaný hlasový prejav sú vysoko redundantné, no oveľa viac vo frekvenánej oblasti ako v časovej. Ďalej - niektoré získané datové údaje, ktoré by boli pod hranicou požadovanej presnosti, by mohli byť eliminované. Táto technika je však skôr datovou redukciou ako kompresiou, pretože tu dochádza k ireverzibilnému procesu.

Problematika kategorizácie a charakteristiky jednotlivých typov redundancií je hlbšia, avšak jej presný rozbor nie je predmetom tejto práce. Jej prehľad bol však základom pre nasledovné porovnanie často používaných metód kompresie, ich výhod a nevýhod.

4. TECHNIKY KOMPRESIE

Platí, že každá z metód kompresie je výhodná pre iný typ údajov. Je ovšem veľký problém nájsť spôsob, ktorým by sa dalo vopred predvídať, ktorá metóda kompresie bude pre daný objem údajov optimálna. Existujú špeciálne paralelné hardwarové obrazové systémy, ktoré obraz kódujú naraz viacerými spôsobmi, potom porovnajú výsledky a vyšlú (alebo inak spracujú) naúspornejšie zakódovaný súbor. Netreba vysvetľovať, že je to spôsob značne nevýhodný najmä z hľadiska neúmerne vysokých nákladov na hardware, a tiež preto, lebo podobný systém má svojou špecializáciou značne zúžený okruh využitia; prestáva byť univerzálnym. Zavedenie paralelných obrazových kódovacích systémov má preto opodstatnenie len vo vysoko špecializovaných oblastiach (astronómia, vojenské účely, meteorológia, komunikácia so satelitmi a vesmírnymi sondami ai).

Typ redundancie spracovávaných súborov je možné predvídať len s určitou pravdepodobnosťou.

4.1 ZÁKLADNÉ METÓDY KÓDOVANIA

Všeobecný model efektívneho kódovania signálov sa skladá z troch častí. V prvej sa vytvára vhodná reprezentácia signálu, napríklad postupnosťou transformačných koeficientov pre transformačné kódovanie. Táto operácia je obyčajne reverzibilná. V druhej sa zmenšuje presnosť reprezentácie signálu. Zah¤ňa predovšetkým kvantovanie, amplitúdovú a frekvenánú (sekvenánú) filtráciu. Sú to operácie ireverzibilné. V tretej sa potláča štatistická nadbytočnosť, napríklad Huffmanovým kódovaním. Táto operácia je reverzibilná.

Metódy kódovania delíme na PCM, predikáné, transformačné, hybridné, iterpolačné, extrapolačné a štatistické. Ďalej sú možné rôzne kombinácie a modifikácie týchto základných metód.

Medzi najjednoduchšie metódy patrí PCM. Je reprezentovaná operáciami diskretizácie, kvantovania a kódovania. Môže byť navrhnutá s nemennými alebo premennými parametrami (adaptívna PCM). Jej nevýhodou je, že nevyužíva redundanciu signálov.

Predikáné metódy, známe ako metódy diferenánej pulznej kódovej modulácie (DPCM), využívajú korelovanosť medzi vzorkami signálu. Realizujú sa ako nemenné a adaptívne. Adaptácia sa predovšetkým vzťahuje na predikciu a kvantovanie. Metódy podmieneného doplňovania vzoriek a oneskoreného kódovania sú neparametrické adaptívne metódy. Sú technicky jednoduché a dostatočne účinné. Ich nevýhodou je, že sú málo odolné voči rušeniu.

Transformačné metódy sú najúčinnejšie. Využívajú ortogonálne transformácie. Môžu byť nemenné a adaptívne. Adaptácia spočíva v zmene typu transformácie alebo kritéria pre výber a kvantovanie spektrálnych koeficientov. Sú značne odolné voči rušeniu. Nevýhodou týchto metód je, že sú technicky veľmi zložité.

Kombináciou predchádzajúcich dvoch metód dostávame hybridné metódy. Tieto využívajú jednoduchosť predikáných metód a vysokú účinnosť transformačných metód. Tým sa získa metóda, ktorá je vysoko účinná, odolná voči rušeniu a technicky relatívne jednoduchá. Jej rôzne modifikácie sú odvodené od modifikácií predikáných a transformačných metód.

Ďalšie metódy sú interpolačné a extrapolačné. Pri týchto metódach sa kódujú iba určité vzorky a všetky ostatné sa získavajú buď interpoláciou, alebo extrapoláciou dekódovaných vzoriek. Adaptácia sa prevádza zmenou kritéria pre výber vzoriek alebo algoritmu interpolácie či extrapolácie. Ich účinnosť je približne rovnaká ako pri predikáných, ale menšia ako pri transformačných a hybridných metódach. Sú pomalé a technicky zložité. Používajú sa tam, kde nie je možné kódovať každú vzorku.

Štatistické metódy využívajú nelineárnosť rozdelenia pravdepodobnosti vzoriek. Metóda Huffmanova prideľuje diskrétnym hodnotám kódové slová rôznej dĺžky v závislosti od pravdepodobnosti ich výskytu. Môže byť nemenná, ak sa rozdelenie pravdepodobnosti uvažuje na nekoneánom časovom intervale a adaptívne, ak sa uvažuje na krátkych časových intervaloch. Metóda Shannon-Fanova vychádza z entropie zdroja náhodného signálu. Priraďuje každej realizácii adresu podľa entropickej kódovacej mapy. Je veľmi nepraktická. Obidve metódy sa nepoužívajú samostatne, ale vždy v súvislosti s inými metódami na zvýšenie ich účinnosti.

4.1.1 PREDIKČNÉ KÓDOVANIE
Predikáné kódovanie patrí medzi najviac rozpracované metódy efektívneho kódovania signálov. Kompresia údajov sa tu dosahuje predovšetkým pomocou redukcie štatistickej redundancie reprezentovanej korelovanosťou signálu (zdroja s pamäťou). Typické vlastnosti predikáného kódovania sú jednoduchá technická realizácia, veľmi malá odolnosť voči kanálovým poruchám a značná citlivosť na zmeny štatistických charakteristík vstupných signálov. Rozlišujeme jednorozmerné a mnohorozmerné predikáné metódy kódovania v závislosti od toho, koľko rozmernú predikciu signálov budú používať. Predikáný kóder sa vo všeobecnosti skladá z vysielača (kódovací systém, digitalizátor) a prijímača (dekódovací systém, analogizátor). Základné jednotky vysielača sú: prediktor, kvantizátor, kóder a jednotky prijímača sú: prediktor, dekóder. Na vstup vysielača sa privádza postupnosť vzoriek diskrétneho signálu, pričom hodnoty týchto vzoriek sú predpovedané prediktorom a prenášajú sa iba chybové, rozdielové hodnoty. Ak na vstupe vysielača predpokladáme dvojrozmerný diskrétny signál, dostávame dvojrozmerný predikáný kódovací systém, ktorého činnosť a vlastnosti sú analogické s činnosťou a vlastnosťami jednorozmerného systému. Zovšeobecnením dvojrozmerného systému dostávame mnohorozmerné predikáné kódovacie systémy, ktoré použíajú mnohorozmernú predikciu, pričom na ich vstupe predpokladáme mnohorozmerné diskrétne signály. So vzrastajúcim rozmerom predikcie sa vo všeobecnosti zvyšuje predikáný zisk, a teda aj pomer S/Š, oproti systémom s menším rozmerom predikcie. Vplyvom zvýšenia predikáného zisku sa zväášuje aj redukovaná redundancia, a tak pri zachovaní kvality kódovania môžeme pomocou viacrozmerných predikáných kódovacích systémov dosiahnuť väášiu kompresiu údajov. Technická realizácia viacrozmerných predikáných kódovacích systémov sa však stáva zložitejšiou a kanálové poruchy, voči ktorým sú predikáné systémy málo odolné, sa rozširujú na celé oblasti.

4.1.2 TRANSFORMAČNÉ KÓDOVANIE
Väčšiu kompresiu údajov, najmä pri kódovaní korelovaných signálov, dosahujeme pomocou transformačného kódovania, ktoré používa diskrétne ortogonálne transformácie. Vplyvom kompresie energie v transformovanom bloku sa stávajú spektrálne koeficienty s malou disperziu nepodstatné (irelevantné). Potlačením tejto irelevancie sa dosahuje kompresia údajov. Typické vlastnosti transformačného kódovania sú: vysoká účinnosť kódovania, zložitá technická realizácia, malá citlivosť na zmeny štatistických charakteristík vstupných signálov a rozloženie kvantizačných aj kanálových chýb na celé bloky vzoriek. Rozlišujeme jednorozmerné a mnohorozmerné transformačné metódy kódovania v závislosti od rozmeru použitej diskrétnej ortogonálnej transformácie. Ortogonálna diskrétna tranformácia, ktorá je jadrom procesu transformačného kódovania, je založená na diskrétnych ortogonálnych transformáciách. Medzi základné a najpoužívanejšie diskrétne transformácie patrí Walsh-Hadamardova transformácia, Haarova transfomácia, diskrétna kosínusová transformácia (DCT) a iné.

Jednou z výhod transformačného kódovacieho systému je, že kanálové a kvantizačné chyby sa nerozširujú mimo vektor výstupných vzoriek. To znamená, že ak dôjde k chybe určitého spektrálneho koeficientu nejakého transformovaného vektora vplyvom kvantovania alebo prenosu kanálom, tak táto chyba sa po dekódovaní rozloží na všetky vzorky dekódovaného vektora.

Skreslenie dekódovaného signálu vplyvom kvantizačných a kanálových chýb bude závisieť od typu použitej transformácie a chybných spektrálnych koeficientov. Pravdepodobnosť kanálových chýb spektrálnych koeficientov s nízkymi sekvenciami bude pritom väášia vplyvom veľkého počtu bitov, ktoré sa používajú na ich kódovanie. Pri kódovaní dvojrozmerných korelovaných signálov dosiahneme väášiu kompresiu údajov pomocou dvojrozmerného transformačného kódovacieho systému. Jeho princíp a činnosť je analogická s činnosťou a princípom jednorozmerného transformačného systému, pričom namiesto procesora jednorozmernej diskrétnej ortogonálnej transformácie sa používa procesor dvojrozmernej diskrétnej ortogonálnej transformácie.

4.1.3 HYBRIDNÉ KÓDOVANIE
Jednorozmerné hybridné kódovanie dvojrozmerných korelovaných signálov využíva jednorozmernú diskrétnu ortogonálnu transformáciu na dekoreláciu tohto signálu v horizontálnom smere. Pritom, ako vidno z výsledkov medziblokovej korelačnej analýzy v transformovanom priestore, sa zachováva medzibloková korelácia. Z toho vyplýva, že súbor kódovacích systémov DPCM je výhodné použiť na kódovanie spektrálnych koeficientov za účelom zmenšenia strednej kvadratickej chyby dekódovaného signálu, respektíve na zväášenie kompresie údajov. Dvojrozmerné hybridné kódovanie používa dvojrozmernú diskrétnu ortogonálnu transformáciu na dekoreláciu signálu, ktorý je rozdelený do malých dvojrozmerných blokov (matíc). Pritom v priestore dvojrozmernej diskrétnej ortogonálnej transformácie sa zachováva medzibloková korelácia. Ako aj v prípade jednorozmerného hybridného kódovania, je výhodné kódovať spektrálne koeficienty dvojrozmernej diskrétnej ortogonálnej transformácie pomocou súboru kódovacích systémov DPCM. Princíp a činnosť dvojrozmerného hybridného kódovacieho systému je analogická s princípom a činnosťou jednorozmerného hybridného systému, pričom namiesto procesora jednorozmernej diskrétnej ortogonálnej transformácie sa používa procesor dvojrozmernej diskrétnej ortogonálnej transformácie.

Hybridné metódy kódovania predstavujú kombináciu predikáných a transformačných metód za účelom využitia výhodných vlastností obidvoch metód. Hybridné kódovacie systémy sa svojou účinnosťou a zložitosťou nachádzajú medzi transformačnými a predikánými kódovacími systémami. Pretože kvantizačné a kanálové chyby sú reprezentované v transformovanom priestore, stávajú sa hybridné kódovacie systémy menej citlivými na poruchy v porovnaní s predikánými systémami, ale viacej v porovnaní transformačné systémy. Dosahujú sa dobré kódovacie vlastnosti bez obmedzení, ktorými sa vyznaáujú transformačné a predikáné systémy, ako je napríklad zložitosť transformačného systému a veľmi malá odolnosť predikáných systémov voči kanálovým poruchám.

4.1.4 INTERPOLAČNÉ A EXTRAPOLAČNÉ KÓDOVANIE
Pri interpolačnom a extrapolačnom kódovaní sa kóduje podskupina vzoriek a zvyšné vzorky sa aproximujú. Ak sa na výpočet aproximácie využívajú iba predchádzajúce vzorky, hovoríme o extrapolácii, ak sa využívajú aj nasledujúce vzorky, postup sa oznaáuje ako interpolácia.

Nemennými interpolačnými metódami kódovania sa kóduje vždy nemenná podskupina vzoriek, napríklad každá druhá, alebo každá štvrtá apod., ostatné vzorky sa interpolujú. Kvalita kódovania závisí od počtu a druhu vzoriek, ktoré sa vynechávajú a od algoritmu interpolácie. Ukazuje sa, že interpolácia, ktorá využíva priamku, je dosť efektívna a interpoláciami využívajúcimi polynómy vyšších stupňov sa kvalita kódovania zlepšuje len veľmi málo.

Extrapolačné algoritmy pracujú v porovnaní s interpolačnými algoritmami rýchlejšie, nevnášajú do procesu kódovania (dekódovania) oneskorenie, pretože údaje charakterizujúce aproximačnú krivku pri extrapolácii sú známe už na začiatku extrapolácie, zatiaľ čo pri interpolácii až na konci. Na druhej strane dosahovaná kompresia údajov extrapolačným kódovaním je o niečo nižšia ako interpolačným kódovaním.

4.1.5 ŠTATISTICKÉ KÓDOVANIE
Doposiaľ sme uvažovali rovnomerné kódovanie kvantizačných úrovní kvantizátorov. Ďalšie zvýšenie údajov v týchto systémoch môžeme dosiahnuť pomocou štatistického, nerovnomerného kódovania kvantizačných úrovní. Medzi najznámejšie štatistické metódy kódovania patrí Huffmanova a Shannon-Fanova metóda. Tieto metódy umožňujú znížiť priemerný počet bitov na vzorku asi o 1 bit pri zachovaní pomeru S/Š, respektíve zvýšiť tento pomer o 6 dB pri zachovaní priemerného počtu bitov na vzorku. Nevýhodou nerovnomerného kódovania je, že sa mení rýchlosť prenosu údajov va výstupe kódovacích systémov. Z tohto dôvodu je potrebné medzi výstup kódovacích systémov a vstup číslicového kanálu zaradiť vyrovnávaciu pamäť. To je tiež príčina, prečo sa toto kódovanie málo používa aj napriek svojim výhodám a uprednostňuje sa rovnomerné kódovanie.

Pozrime sa bližšie na najpopulárnejšiu metódu štatistickej kompresie, na Huffmanove kódovanie. Je to premena jednotiek vstupných údajov s konštantnou dĺžkou na symboly s premenlivou dĺžkou. Štandardný Huffmanov kódovací proces predpisuje spôsob, ako vstupným symbolom priradiť kódy tak, aby dĺžka každého kódu v bitoch bola približne log2(pravdepodobnosť symbolu), kde pravdepodobnosť symbolu je relatívna frekvencia existencie daného symbolu (vyjadrená ako pravdepodobnosť). Napríklad ak sada symbolov na vstupe bude tokom jednobytových ASCII znakov (veľmi typický prípad), a ak sa prázdny znak používa v osmine celkového množstva, potom bude prázdny znak zakódovaný do trojbitového symbolu. Ak sa písmeno "z" objavuje iba v 0.1% prípadov, je reprezentované desiatimi bitmi. (V slovenčine by najväáší počet bytov iste pripadol na zriedkavé písmená ako napríklad ô, ä či ¤ (napríklad toto písmeno sa objavuje v celom texte tejto práce iba štyrikrát...).

Pri bežnom využití je veľkosť vstupných symbolov obmedzená veľkosťou prekladovej tabuľky, ktorá je potrebná pre kompresiu. To znamená, že je potrebná tabuľka, ktorá obsahuje každý vstupný symbol a jeho príslušný kód. Ak symbol je jeden osembitový byte (ako je bežné), potom postaáuje tabuľka s 256 položkami. Takáto tabuľka je dosť ekonomická čo sa týka nákladov na uchovanie, ale limituje stupeň dosiahnutej kompresie. Jednoznakové kódovanie si poradí s redundanciou znakového rozdelenia (a), ale nie s inými typmi. Kompresia by sa dala vylepšiť použitím vstupných symbolov, z ktorých každý by mal dva byty, avšak to by vyžadovalo tabuľku s 65,536 položkami, čo by už nemuselo byť efektívne. Rozobranie vstupných dát na symboly, ktoré nie sú bytovo orientované, napríklad na 12-bitové symboly, zvyčajne nezlepší efektívnosť kompresie a skomplikuje celý systém.

Druhý problém ohľadom Huffmanového kódovania spočíva v zložitosti dekompresného procesu. Dĺžka každého kódu, ktorý má byť pri dekompresii preložený do pôvodného, nie je známa predtým, ako sa interpretuje prvých niekoľko bitov. Základná metóda pre interpretáciu je preložiť každý bit v sekvencii a vybrať prekladovú podtabuľku podľa toho, či je bit jedna alebo nula. Z toho vylýva, že tabuľkou je v podstate binárny strom. Operačne sa potom pre každý bit uskutoční logické rozhodovanie. Pri práci s diskovou jednotkou, ktorá má rýchlosť 30Mb/s musí logika dekompresie pracovať takouto, alebo väášou rýchlosťou, aby nedošlo k spomaleniu. Dekompresia touto rýchlosťou je možná, ale nie jednoduchá. Vo všeobecnosti znamená dekompresia s premenlivou dĺžkou symbolov nevýhodu čo sa týka úspory času, miesta v pamäťovom médiu, respektíve prenosovej doby, hlavne ak je objem dát veľký.

Tretím problémom v spojitosti s Huffmanovým kódovaním je fakt, že je potrebné poznať rozdelenie frekvencií preto, aby bolo možné zostaviť tabuľku symbolov. V normálnom prípade jednoznakových symbolov je rozdelenie frekvencie znakov v datovom toku závislé na type súboru. Takéto rozdelenie je známe a pravdepodobne dostatočne stabilné pre anglický (slovenský) text. Jednako však rozdelenia frekvencií znakov sú vysoko špecifické pre daný súbor, ako je objektový kód, zdrojový kód a systémové tabuľky, ktorých rozdelenia sa rôznia. A hoci by aj bolo možné mať sadu prekladových tabuliek, ktoré by obsahovali tieto rôzne prípady, problémy nastávajú v tom, že dekompresor musí používať tú istú sadu tabuliek ako kompresor. Bežným riešením je analyzovať každý datový blok osobitne a vytvoriť jeho vlastnú prekladovú tabuľku. Vtedy je potrebné vykonať dva prechody súborom: (A) spočítať znaky a vytvoriť tabuľku a (B) prejsť druhýkrát a zakódovať súbor podľa jeho tabuľky. Získaná prekladová tabuľka musí byť prepravovaná s kompresovanými datami, čo uberá z efektivity kompresie a/alebo silne obmedzuje veľkosť prekladovej tabuľky. Tento adaptačný prístup je prijateľný vtedy, ak nie sú potrebné vysoké prenosové rýchlosti kompresora a ak datové bloky, ktoré sú kompresované, sú v porovnaní s prekladovou tabuľkou veľmi veľké.

4.1.6 ŠPECIÁLNE TYPY KOMPRESIE
Na ilustráciu ďalších typov kompresie uvediem ešte dve špeciálne techniky - programovú kompresiu a novú LZW metódu kompresie.

PROGRAMOVÁ KOMPRESIA

Hoci programová kompresia nie je určená pre všeobecné použitie, musí tu byť tiež spomenutá. Programovanie sa zvyčajne vykonáva aplikačným programátorom alebo systémovým datovým managementom. Pri formátovaných datových súboroch sa používa niekoľko techník. Nepoužité prázdne alebo nulové miesta sa eliminujú vytvorením polí s premennou dĺžkou a použitím indexovej štruktúry s ukazovateľmi na každú pozíciu poľa. Predikovateľné hodnoty poľa sú kompaktne zakódované pomocou kódovej tabuľky - ako v spomenutom príklade, keď boli názvy predajní zakódované číslami lepšie ako alfabetickými názvami. Každé pole má svoj vlastnú špecializovanú kódovú tabuľku, ktorá zohľadňuje poziánú redundanciu. Keďže programovaná kompresia nedokáže efektívne zvládnuť redundanciu frekvencie znakov, je dobrým doplnkom k Huffmanovému kódovaniu.

Programová kompresia má niekoľko vážnych nevýhod. Prináša zvýšené náklady na vývoj programu; typ použitej dekompresie vyžaduje znalosť štruktúry záznamu a kódovej tabuľky; výber veľkostí polí a kódových tabuliek môže skomplikovať, alebo spomaliť neskoršie zmeny v datovej štruktúre, čo zvýši náklady na údržbu softwaru. A čo je asi najdôležitejšie, programátori sa budú snažiť vyhnúť procesu dekompresie, pretože je pomerne pomalý, a preto budú pracovať priamo s datami v kompresovanom formáte, čo mätie a komplikuje aplikačný program.

ADAPTÍVNA KOMPRESIA

Lempel-Zivove a podobné algoritmy konvertujú reťazce vstupných symbolov s premennou dĺžkou na kódy s pevnou dĺžkou (predikovateľné). Reťazce symbolov sú vybrané tak, aby mali všetky takmer rovnakú pravdepodobnosť výskytu. Následkom toho budú reťazce často sa vyskytujúcich symbolov obsahovať viac symbolov ako reťazec obsahujúci menej frekventované symboly. Táto forma kompresie je efektívna čo sa týka redundancie frekvencie znakov, opakovania sa znakov a často používaných sekvencií. Nie je všeobecne efektívna iba pre poziánú redundanciu. Tento typ algoritmu je adaptívny v tom zmysle, že začina s prázdnou tabuľkou symbolových reťazcov a buduje tabuľku ako počas kompresie, tak počas dekompresie. Sú to procedúry s jedným prechodom súboru, ktoré nevyžadujú žiadnu predoslanú informáciu o štatistike vstupných údajov a svoju funkciu vykonávajú v časoch, ktoré sú úmerné dĺžkam správ. Táto adaptivita zapríčiňuje nízku kompresiu počas úvodnej časti každej správy; preto musí byť súbor dostatočne dlhý nato, aby si procedúra vytvorila dostatočnú "skúsenosť" ohľadom frekvencie symbolov tak, aby bola dosiahnutá dobrá kompresia celej správy. Na druhej strane väášina koneáných implementácií adaptívneho algoritmu stráca schopnosť adaptácie potom, čo sa spracuje určité množstvo správy. Ak správa nie je homogénna a jej charakteristika jej redundancie sa mení, potom účinnosť kompresie klesá, ak dĺžka súboru podstatne prekraáuje adaptívne hranice implementácie kompresie. Táto technika kompresie sa nazýva LZW (Lempel-Ziv-Welch) metóda. Je to variácia Lempel-Zivového algoritmu - udržiava adaptívnu charakteristiku Lempel-Zivovej metódy a zároveň dosahuje kompresné pomery podobné kompresným pomerom v normálnych komeráných počítačových aplikáciách. LZW sa vyznaáuje veľmi jednoduchou logikou, ktorá prináša relatívne nenáročné implementácie a potenciál pre veľmi rýchlu prácu. Typická LZW implementácia potrebuje menej ako tri hodinové cykly na symbol a dosahuje prijateľne dobrú kompresiu správ od dĺžky desaťtisíc znakov.

LZW metóda sa ukazuje ako mimoriadne vhodná pre kompresiu dát pri ich konvenánom uchovávaní v komeráných počítačových systémoch, kde vysoké rýchlosti presunu dát z magnetických diskov vyluáujú dlhé doby de/kompresie, zatiaľčo rôznosť datových typov, ktoré sú spracovávané, nutne vyžaduje adaptívnu techniku. Použitie krátkych segmentov na disku komplikuje použitie adaptívneho prístupu, ale to sa stáva menej dôležitým, keďže dĺžky datových blokov na diskoch narastajú. Zdá sa, že LZW metóda (podrobnejšie o algoritme plus výpis programu viď (8) a (9)) spĺňa tieto požiadaky lepšie ako iné kompresné prístupy.

5. ŠTANDARD KOMPRESIE STATICKÉHO OBRAZU

Pokrok posledného desaťročia priniesol mnoho aplikácií digitálnych obrazov. Ide najmä o zariadenia na snímanie obrazov, uskladňovanie údajov a bitmapové tlačenie a zobrazovanie obrazov. Tieto aplikácie však následkom vysokých nákladov na techniku bývajú špecializované. S výnimkou faksimile sa digitálne obrazy zatiaľ nevyskytujú v bežných výpočtových systémoch v takom rozsahu, ako text a geometrická grafika. Väášina moderného obchodného a užívateľského využitia fotografií a iných typov obrazov prebieha pomocou tradiánejších analógových prostriedkov.

Základnou prekážkou pre mnoho aplikácií je nesmierne množstvo dát, ktoré sú potrebné na priamu reprezentáciu číslicového obrazu. Digitalizovaná verzia jediného farebného obrázku s rozlíšením, aké používa televízia, je reprezentovaná ako jeden milión bytov; pre reprezentáciu rozlíšenia, aké má 35 mm film, je potrebných desať krát také množstvo. Využitie digitálnych obrazov je často znemožnené vysokými nákladmi na uchovávanie dát alebo na prenos, dokonca aj keď zariadenia na snímanie a zobrazovanie obrazov sú celkom dostupné.

Moderná technológia kompresie obrazov ponúka možné riešenie. Najmodernejšie techniky dokážu kompresovať typické obrázky na 1/10 až 1/50 ich pôvodnej veľkosti bez toho, aby viditeľne ovplyvnili kvalitu obrazu. Avšak samotná technológia kompresie nie je postaáujúca. Preto, aby sa aplikácie digitálneho obrazu včitane uchovávania a prenosu dát rozšírili a udomácnili na dnešnom trhu, je potrebná štandardná metóda kompresie obrazov, ktorá by umožnila spoluprácu zariadení rôznych výrobcov. Doporučenie CCITT pre dnes už všadeprítomné faxové prístroje Skupiny 3 je dramatickým príkladom toho, ako môže štandardná metóda kompresie umožniť dôležité aplikácie obrazov. Metóda Skupiny 3 sa však zaoberá výhradne s dvojúrovňovými obrazmi a nezaoberá sa kompresiou fotografických obrazov.

Na problematike ustanovenia prvého medzinárodného štandardu pre kompresiu digitálnych obrazov so spojitou (mnohoúrovňovou) škálou farieb i šedi pracovala niekoľko rokov Spojená skupina fotografických expertov (JPEG). Prívlastok "spojená" dostala skupina kvôli spolupráci medzi CCITT a ISO. Výsledkom niekoľkoročného úsilia je navrhovaný štandard ISO skupiny JTC1/SC2/WG10 a neformálne CCITT SGVIII, bežne však označovaný ako JPEG.

Fotovideotext, DTP, grafické umenie, farebné faksimile, agentúrne sieťové prenosy fotografií, medicínske aplikácie a mnoho iných aplikácií so spojitou úrovňou vyžadujú kompresný štandard preto, aby sa vyvinuli za hranice dnešného požitia. JPEG s podujal na ambicióznu úlohu vývoja kompresného štandardu so všeobecným využitím tak, aby vyhovel potrebám drvivej väášiny aplikácií pracujúcich so statickými mnohoúrovňovými obrazmi.

Ak sa JPEG ujme tak, ako sa predpokladá, nebude to prínos iba pre jednotlivé aplikácie, ale bude umožnená aj výmena obrazov cez aplikačné hranice. Táto árta je veľmi dôležitá, pretože mnoho aplikácií obrazov je implementovaných na nešpecializovaných počítačových systémoch, ktoré sú čoraz viac kompatibilné a prepojené sieťami. Pre aplikácie, ktoré pre dosiahnutie svojich požiadaviek na rýchlosť kompresie a dekompresie vyžadujú špecializované VLSI obvody, prinesie výrazné ekonomické výhody.

Fakt, že niektoré časti štandardu JPEG sa používajú aj pre pohyblivé obrazy (obrazové sekvencie), môže naznačovať, že rozdiel medzi kódovaním statického a pohyblivého obrazu môže byť niekedy umelo vytvorený.

Podrobnejšie o štruktúre a funkciách štandardu JPEG viď (13). Teraz sa krátko pozrieme na ďalší mladý štandard.

6. ŠTANDARD KOMPRESIE POHYBLIVÉHO OBRAZU

Vývoj číslicovej videotechnológie v osemdesiatych rokoch vytvoril možnosti na využitie digitálnej video kompresie v množstve telekomunikačných aplikácií - telekonferencie, digitálne prenosové kódeky (kódek = kóder/dekóder) a video telefóny.

Štandardizácia videokompresných techník sa stala vysoko prioritnou, pretože iba štandard je schopný zredukovať vysoké náklady videokompresných kódekov a vyriešiť kritický problém kompatibility zariadení rôznych výrobcov. Existencia štandardu je často spúšťou pre masovú výrobu VLSI integrovaných obvodov, ktoré sú nutné pre podstatné zníženie nákladov. Ako príklad takéhoto fenoménu, keď štandard stimuloval rast výroby, treba znova spomenúť úžasný rozvoj na trhu s faksimilnými systémami. Digitálny prenos je najdôležitejší pre telekomunikáciu, špeciálne v telefónnej sieti, no videosignál má oveľa širšie uplatnenie než len v telekonferenciách a obrazovej telefónii. Počítačový a telekomunikačný priemysel a elektronický priemysel bežnej spotreby čoraz viac používajú rovnaké techniky, dochádza k podstatnej konvergencii. To neznamená, že počítaá a televízny prijímaá sa čo nevidieť stanú tým istým, ale predsa, techniky konvergujú a - zah¤ňajú videokompresiu. Vo svetle používania rovnakých techník medzi jednotlivými časťami informačného priemyslu sa Medzinárodná organizácia štandardov (ISO) podujala na vývoj štandardu pre video a s tým spojený zvuk pre digitálne záznamové médiá, kde záznamové médium zah¤ňa konvenáné záznamové prístroje CD-ROM, DAT, páskové jednotky, pevné disky, optické disky, rovnako ako telekomunikačné kanály, ako napríkald ISDN a lokálne siete. Toto úsilie je známe ako MPEG - Skupina expertov pre pohyblivý obraz. Aktivita výboru MPEG, ktorá nadviazala na štandard JPEG (mnoho participantov pracovalo v obidvoch skupinách). MPEG obsahuje viac ako len videokompresiu, pretože kompresia pripojeného zvuku a audiovizuálnej synchronizácie nemôžu byť vynechané: MPEG-Video charakterizuje kompresiu videosignálov pri asi 1.5Mbit/s, MPEG-Audio je určený pre kompresiu zvuku pri 64, 128 a 192kbit/s na kanál. MPEG-System uráuje synchronizáciu a multiplex z viacerých audio a video vstupov.

MPEG je rovnako ako štandard JPEG všeobecným a flexibilným nástrojom, ktorý dáva výrobcom dostatočné možnosti kreativity pri zachovaní kompatibility systémov od rôzych výrobcov. Je to umožnené tým, že štandard má mnoho častí, ktoré sa nevyužívajú súčasne - závisí na aplikácii, ktorá časť sa využije. Kompresia nebola jediným kritériom účinnosti MPEG, dôraz bol kladený aj na náhodný prístup (je možné kedykoľvek začať snímať signál), prehľadávanie dopredu/dozadu, spätný beh, audiovizuálnu synchronizáciu, odolnosť voči chybám, oneskorenie kódovania/dekódovania, možnosť editácie, flexibilitu formátu (možnosť ľubovoľného zmenšovania či zväášovania obrazu, obraz v obraze atp), jednoduchosť technickej aplikácie.

MPEG štandard sa takto stáva silným prostriedkom pre masový rozvoj číslicovej videotechniky. Jedná sa o veľmi komplexnú problematiku, bližšie viď (14).

7. METÓDY KOMPRESIE OBRAZU

Kódovanie je iba jednou z operácií v množstve techník použitých pri digitálnom spracovaní obrazu. Preto sa zaviedol pojem reprezenácia obrazu, ktorý má širší význam ako kódovanie. Teda (efektívne) kódovanie je špeciálnym prípadom reprezentácie obrazov. Poznáme reprezentácie heuristické, hierarchické, množinové. Množinové reprezentácie sú založené na poznatkoch z matematickej morfológie a využívajú množinové operácie s obrazom. Heuristické reprezentácie využívajú najmä štatistické vlastnosti obrazov a využívajú základné poznatky z teórie informácií. Hierarchické reprezentácie využívajú topologické vlastnosti a hierarchickú štruktúru obrazov. Kompresia obrazov tvorí zvláštny typ kódovania, ktorý je orientovaný práve na povahu obrazu, ktorou je plocha a dvojrozmerné útvary.

Vo vizuálnej informácii možno vo všeobecnosti rozlíšiť dve základné formy redundancie:

(a) Štatistická redundancia, ktorá vyplýva z určitých typických a vopred známych vlastností obrazov. Napríklad v grafických obrazoch je užitočná informácia zobrazená bielou a pozadie čiernou, teda čierna je dominantná, ale pritom predstavuje redundanciu. Štatistická redundancia sa vyznaáuje tým, že ju možno odstrániť bez toho, aby sa porušil informačný obsah. Jej odstránenie umožňuje spätnú rekonštrukciu obrazu bez skreslenia, táto operácia je reverzibilná.

(b) Subjektívna redundancia vyplýva z toho, že odstránenie určitého informačného obsahu sa neprejaví pri subjektívnom hodnotení rekonštruovaného obrazu. Takéto odstránenie subjektívnej redundancie je na rozdiel od odstránenia štatistickej redundancie operácia ireverzibilná.

7.1 MNOŽINOVÉ REPREZENTÁCIE

Množinové reprezentácie sú metódami, ktoré využívajú transformáciu originálneho obrazu na množinu charakteristických prvkov, ktorá má jednoduchšiu štruktúru. Tieto metódy možno rozdeliť do dvoch skupín - rastová geometria a skelet obrazu.

Rastová geometria sa zakladá na myšlienke rastu obrazca podľa určitých pravidiel. Obrazec sa chápe ako kompaktný zhluk čiernych obrazových prvkov, ktoré možno získať aplikovaním definovaných pravidiel rastu na určité východzie obrazové prvky. Tieto sa oznaáujú ako zdrojové (semenné) obrazové prvky. Tieto zdrojové prvky sú také, z ktorých sa odštartuje proces rastu definovaným pravidlom rastu a z ktorých sa po určitom počte krokov získa daný obrazec. Existuje množstvo druhov zdrojových prvkov, taktiež existuje množstvo spôsobov rastu. Takto získame útvary rôznych tvarov, ktoré pri správnom uplatnení môžu charakterizovať súvislú plochu v obraze. Obraz je potom zakódovaný len ako podoba zdrojových obrazových prvkov, ich súradníc a podmienok ich rastu. Vďaka množstvu variácií rastovej geometrie sa touto metódou dosahuje vynikajúca kompresia obrazov, avšak nároky na dobu spracovania sú zatiaľ neúmerne vysoké. Táto metóda je však veľmi perspektívna.

Reprezentácia skeletom spočíva v kódovaní obrazu množinou bodov, ktoré majú od hraníc obrazca určitú vzdialenosť. Vzdialenosť je daná vzdialenostnou funkciou, tzv. metrikou - napríklad metrikou absolútych vzdialeností, metrikou maximálnych vzdialeností apod. Na výpočet skeletu sa používa aparát matematickej morfológie, ktorá popisuje priradenia jednoduchších množím ku zložitejším množinám, čo následne zjednodušuje kódovanie.

7.2 HEURISTICKÉ REPREZENTÁCIE

Medzi heuristické kódovanie patrí kódovanie štatistické - to je už vyššie popísaný známy Huffmanov, a tiež Shannon-Fanov kód. Ďalej sem patrí blokové kódovanie, čo je exaktné kódovanie, ktoré spočíva v kódovaní obrazovej plochy do blokov buď konštantnej, alebo premenlivej (adaptívnej) veľkosti. Aproximačné blokové kódovanie je už oproti tomu ireverzibilný proces, ktorý spočíva v tom, že blok, ktorý nemá viac ako určitý, zvolený počet čiernych bodov, je klasifikovaný ako biely a závisí na aplikácii, aký stupeň vernosti de/kódovania sa použije.
Medzi heuristické kódovanie patrí aj kódovanie dĺžok úsekov riadku. Toto kódovanie spočíva v tom, že sekvencie rovnakých znakov môžu byť zakódované ako ich počet plus identifikátor opakovaného znaku. Tento prístup je efektívny najmä pri práci s grafickými obrazmi, nemá takmer žiadny význam v texte, v datových súboroch je priemerne účinný. Problém s RL kódovaním pre sekvencie znakov zmiešaných s inými datami je v rozlišovaní kódu počtu znakov a kódu normálnych znakov, pretože obidva môžu nadobudnúť rovnakú hodnotu. Problém má niekoľko riešení, ale každé má niekoľko nevýhod. Napríklad pre každý úsek rovnaký znakov môže byť použitý špeciálny znak ako jeho označenie, čo je dobre možné v ASCII súboroch, ale nie v binárnych súboroch, kde môže byte nadobudnúť ktorúkoľvek z 256 kombinácií. Typicky sú na označenie každého úseku potrebné tri znaky, takže toto kódovanie nie je vhodné použiť pre úseky dlhé tri a menej znakov. RL kódy môžu byť jednorozmerné (lineárne kódy, logaritmické kódy), existujú dvojrozmerné RL kódy, ktoré využívajú aj vertikálnu koreláciu - buď riadok po riadku, alebo sekvenáne riadok po riadku (berie sa do úvahy aj predošlá informácia, využitie predikcie.

7.3 HIERARCHICKÉ REPREZENTÁCIE

Hierarchické reprezentácie obrazu sa zakladajú na princípe rekurzívnej dekompozície priestoru. Dimenzia tohto priestoru uráuje, či sa bude jednať o hierarchickú reprezentáciu bodov, kriviek, plôch či objemov telies. Ak sa na každej úrovni procesu dekompozície získajú rovnaké podmnožiny dát, ide o regulárnu dekompozíciu, ak sú získané data nerovnaké, ide o neregulárnu dekompozíciu. Ak proces dekompozície prebieha iba ak je splnené určité kritérium (napríklad kritérium homogenity obrazu), hovoríme o adaptívnej dekompozícii, teda s premennou hustotou. Naopak, ak proces dekompozície prebieha za každých okolností, ide o neadaptívnu dekompozíciu, teda dekompozíciu s viacnásobnou hustotou.
Najrozpracovanejšie hierarchické reprezenácie obrazu sú pyramidálne reprezentácie (pyramídy) a kvadrantový strom obrazu, ktoré umožňujú realizovať hierarchickú štruktúru obrazovej informácie, a teda sú vhodné na postupný prenos obrazov.
Reprezentácia obrazu pyramídou znamená, že ak máme základný obraz o rozmeroch 2^N * 2^N, potom pyramída je postupnosť, ktorej každý prvok (hladina) je nejakou časťou originálneho obrazu ("základne pyramídy", najnižšej hladiny), pričom každá hladina je odvodená od predošlej určitou (definovanou) operáciou, postupne až po najvyššiu hladinu. Každý obrazový prvok vyššej hladiny je teda výsledkom určitej aritmetickej alebo logickej operácie nad ohraničenou skupinou obrazových prvkov nižšej hladiny. Poznáme viacero typov pyramíd, ako je neprekrývajúca a prekrývajúca sa pyramída, Gaussova pyramída, Laplaceova pyramída.
Reprezentáciu obrazu kvadrantovým stromom obrazu sa budem zaoberať v samostatnej kapitole.

8. KVADRANTOVÝ STROM OBRAZU

Kvadrantový strom obrazu (Quadrant Tree, Quadtree) vznikol ako jeden z možných spôsobov reprezentácie binárnych obrazov, ktoré majú tvar segmentu, pričom pod pojmom segment sa rozumie uzavretý obrazec.
Reprezentácia pomocou kvadrantového stromu obrazu (KSO) sa zakladá na postupnom hierarchickom delení obrazového poľa na kvadranty, ak segment nezaberá celé obrazové pole. Pretože na každej úrovni dekompozície sa získajú rovnaké časti obrazu, ide o regulárnu dekompozíciu. Proces dekompozície prebieha ďalej len v nehomogénnych kvadrantoch, teda v kvadrantoch, ktoré sú "sivé" - obsahujú biele aj čierne obrazové prvky, preto ide o adaptívnu dekompozíciu.
Grafickou interpretáciou tejto dekompozície je strom 4 stupňa, teda kvadrantový strom, v ktorom koreň stromu reprezentuje celé obrazové pole, jednotlivé vetvy stromu reprezentujú dekompozíciu na kvadranty a subkvadranty. Štvorica kvadrantov na ktorejkoľvek a každej úrovni sa čísluje v smere chodu hodinových ručičiek (viď obr. 1 v obrazovej prílohe). Každému kvadrantu obrazového poľa zodpovedá v kvadrantovom strome jeden uzol. Uzly stromu sú buď terminálne (listy stromu), ak reprezentujú biele, respektíve čierne kvadranty, alebo neterminálne (vetvenie), ak reprezentujú nehomogénne, šedé kvadranty (obr. 1). Každý neterminálny uzol sa vetví tak, že je spojený s ďalšími štyrmi uzlami. Neterminálny uzol je otcovským vzhľadom na štyri synovské uzly, ktoré mu prislúchajú. Ak počet všetkých uzlov kvadrantového stromu je M, potom počet terminálnych uzlov T = (3M+1)/4 a počet neterminálnych uzlov je N = (T-1)/3.
Kvadrantový strom obrazu možno reprezentovať dvoma základnými spôsobmi:
Smerníkovou reprezentáciou - v každom uzle je záznam obsahujúci smerník na otcovský uzol, štyri smerníky na synovské uzly a ďalšie informácie o danom uzle, napríklad typ uzla. Ak sú uzly terminálne, potom smerníky na synov sú prázdne, podobne smerník koreňa stromu na otca je prázdny. Smerníková reprezentácia umožňuje prístup k ľubovoľnému uzlu, pohyb medzi ľubovoľnými uzlami, preto je vhodná najmä pre analýzu obrazov. Jej značnou nevýhodou je značne vysoká redundancia, a keďže nás zaujíma efektívna kompresia obrazov, smerníkovou reprezentáciou sa nebudeme bližšie zaoberať.
Druhým spôsobom reprezentácie KSO je bezsmerníková reprezentácia, ktorá môže byť rozdelená do dvoch skupín:
1. Reprezentácie prvej skupiny využívajú skutočnosť, že obraz je súborom terminálnych uzlov, teda kóduje sa ich poloha v obrazovom poli, respektíve v KSO. Do prvej skupiny patrí lineárny kvadrantový strom a kvadrantový kód.
2. Reprezentácie druhej skupiny sa zakladajú na kódovaní KSO prechádzaním stromu v určitom poradí. Do druhej skupiny patrí DF výraz, BF výraz a CD výraz.

8.1 LINEÁRNY KVADRANTOVÝ STROM

Lineárny kvadrantový strom využíva lokalizačný kód, pomocou ktorého sa kóduje každý čierny terminálny uzol kvadrantového stromu. Lokalizačný kód je postupnosť 4 smerových kódov, ktoré lokalizujú cestu od koreňa stromu k danému terminálnemu uzlu kvadrantového stromu. Lineárny kvadrantový strom je hierarchická datová štruktúra, ktorá sa vyznaáuje týmito vlastnosťami:
a) Kódujú sa iba čierne terminálne uzly kvadrantového stromu
b) pri kódovaní sa zachovávajú pravidlá susednosti uzlov v štyroch základných smeroch
c) kóduje sa cesta od koreňa KS k čiernemu terminálnemu uzlu pomocou postupnosti lokalizačných kódov
d) segment binárneho obrazu možno reprezentovať ako súbor lokalizačných kódov.
Hlavné výhody použitia lineárneho KS sú v tom, že (a) zložitosť lineárneho KS a tým aj časové relácie pri analýze obrazu závisia od počtu čiernych terminálnych uzlov KS a (b), že lineárny kvadrantový strom nepoužíva smerníky. Príklad použitia lineárneho kvadrantového stromu si ukážeme na obrázku á. 1 obrazovej prílohy. Lineárny KS potom bude vyzerať tak, ako znázorňuje obrázok á. 2 prílohy. Segment binárneho obrazu možno zapísať ako súbor lokalizačných kódov v tvare (12, 211, 3).

8.2 KVADRANTOVÝ KÓD (QC)

Reprezentácia kvadrantovým kódom (Quadcode, QC) používa na vyjadrenie dvojrozmerných súradníc v obrazovom poli jednorozmerný kód, ktorý možno použiť na reprezentáciu kvadrantového stromu obrazu. QC s dĺžkou n možno vyjadriť v tvare q = q1q2q3...qn, kde qi=(0,1,2,3) a i=1,2,3,...n. Každý znak qi v QC reprezentuje operáciu delenia na kvadranty. Postupnosť delenia obrazového poľa je zrejmá z obrázku á. 3. QC reprezentácia síce vychádza z hierarchického adresovania kvadrantov obrazového poľa, ale pri vhodne zvolenom čiselnom vyjadrení sa QC kód zhoduje s lokalizačným kódom, ktorý sa používa v lineárnom kvadrantovom strome.

8.3 DF VÝRAZ

DF výraz už patrí spolu s BF a CD výrazmi do druhej skupiny bezsmerníkových reprezentácií. KSO možno reprezentovať súborom terminálnych a neterminálnych uzlov, ktorý sa získa prechádzaním stromu v určitom poradí. Jednou z možností prechádzania stromu v priamom poradí, ktoré možno popísať tak, že sa vychádza z koreňa stromu, prechádza sa vetvou najviac vľavo, potom ďalšou vetvou až nakoniec sa prechádza vetvou najviac vpravo. Pritom cez každý uzol stromu sa prechádza iba raz. Uvedený spôsob sa oznaáuje ako prechádzanie "najprv hĺbka" so skratkou DF vyplývajúcou z anglického Depth First. Na označenie stavu uzlov KSO si ustanovíme symboly "W"hite pre terminálny biely, "B"lack pre terminálny čierny a "G"ray pre neterminálny, šedý uzol. Pre KSO možno potom prechádzanie DF vyjadriť takto: G - WG - WWBW - G - WG - WBWW - WW - B a DF výraz pre daný obrázok má tvar: (0(0010(0(0100001.
Vlastnosti výrazu DF možno zhrnúť takto:
1. Ak DF výraz obsahuje L symbolov "(", potom počet symbolov "0" a "1" je 3L+1.
2. DF výraz možno získať prechádzaním KSO za predpokladu, že platí B="1", W="0" a G="(". Ak pri konštrukcii DF výrazu vychádzame z obrazových prvkov, potom sa definujú redukáné pravidlá v tvare 0000 -> 0 a 1111 -> 1.
3. Prevod BF výrazu do binárneho tvaru možno realizovať vhodným kódovaním, pričom existuje viacero možností:
"(" "11" "0" "00" "1" "10"
"(" "11" "0" "0" "1" "10"
"(" "11" "0" "0" "1" "10" alebo "1", ak uvedený symbol reprezentuje čierny obrazový prvok.
4. Činiteľ kompresie, ktorý sa dosiahne pomocou reprezentácie DF výrazom závisí od zložitosti obrazu.

Reprezentácia obrazov pomocou DF výrazu predstavuje účinný prostriedok pre spracovanie obrazov a jej vlastnosti možno zhrnúť takto:
1. Umožňuje dosiahnuť väášiu kompresiu dát, ako doposiaľ známe metódy kódovania, čo znamená, že je efektívnou reprezentáciou pre zdrojové kódovanie,
2. zachováva úplnú informáciu o obraze, umožňuje teda exaktnú spätnú rekonštrukciu obrazu dekódovaním,
3. DF výraz je vhodný aj pre analýzu obrazov (výpočet plochy segmentu, ťažiska apod).
Reprezentácia viacúrovňových obrazov pomocou DF kódu môže byť realizovaná tromi základnými spôsobmi:
1. Kódovaním po bitových rovinách - obraz rozložíme na bitové roviny, z ktorých každá obsahuje výhradne bity s váhovou hodnotou rovnou 2^(bitplane). Obrazy v jednotlivých bitových rovinách obsahujú teda okrem farby pozadia iba jednu farbu a je možné ich kódovať DF kódom.
2. Kódovaním G - kvadrantového stromu - je to modifikácia kvadrantového stromu, pre ktorý platia aj analogické pravidlá. Za homogénny kvadrant sa považuje štvorcová časť obrazu s rovnakou jasovou úrovňou. Nehomogénne kvadranty sa delia hierarchickým delením na subkvadranty, pričom delenie môže prebiehať až na úroveň obrazových prvkov. Príklad GKS pre viacúrovňový obraz je znázornený na obrázku á. 4. Počet jasových úrovní je 8, a teda jas každého prvku je reprezentovaný 3 bitmi.
Viacúrovňový obraz možno kódovať DF výrazmi aj tak, že DF výraz sa získa prechádzaním G - kvadrantového stromu metódou DF. DF výraz pre viacúrovňové obrazy označime GDF. Pre daný GKS možno GDF pri vyjadrení jasu jednotlivých listov dekadickou hodnotou zapísať v tvare GDF = ((01113(2323(4456.
3. Kódovaním modifikovaného G - kvadrantového stromu.
Účinnejšou metódou kódovania sa javí metóda generovania GDF tým, že GKS sa upraví metódou, ktorej princíp je zrejmý z obrázku á. 5. Základom tejto metódy je, že vetviace sa uzly nesú informáciu o spoločných bitoch kódových slov na nižších úrovniach. GKS z obr á. 4 sa takto mení na modifikovaný GKS, ktorý je na obr á. 5. GDF pre takýto GKS má potom tvar GDF' = (00(011101101(01011(00000110.
Dá sa dokázať, že pri známej dĺžke kódového slova pre jas obrazových prvkov je GDF jednoznačne dekódovateľný a poskytuje lepšie výsledky v zmysle väášej kompresie dát ako kódovanie po bitových rovinách.

8.4 BF VÝRAZ

Reprezentácia obrazov BF výrazmi sa zakladá na prechádzaní KSO metódou do šírky, ktorá sa oznaáuje ako metóda "najprv plocha" so skratkou BF pochádzajúcou z anglického Breadth First. KSO prechádza po jednotlivých úrovniach, čo pre KSO na obrázku á. 1 možno znázorniť takto:
G
WGGB
WWBWWGWW
WBWW
teda sekvenáne: GWGGBWWBWWGWWWBWW. Naznačený spôsob prechádzania KSO možno algoritmizovať rovnako ako reprezentáciu KSO DF výrazom (podrobnejšie o teórii algoritmizovania viď (2)). Z hľadiska kompresie dát je teda BF výraz ekvivalentný DF výrazu. Ak pre reprezentáciu uzlov KSO použijeme rovnakú symboliku, ako pre DF výraz, potom pre daný obrázok platí:
BF = (0((100100(000100
BF výrazy sa teda líšia iba poradím symbolov, ich počet je však v oboch výrazoch rovnaký, čo vyplýva aj z toho, že obidva výrazy popisujú uzly KSO.
Odlišné poradie symbolov v BF výraze však ponúka možnosti postupného prenosu binárnych obrazov.
Jednotlivé úrovne KSO zodpovedajú rôznym rozlišovacím schopnostiam, čo vyplýva z toho, že uzly na týchto úrovniach reprezentujú kvadranty rôznych veľkostí. Napríklad úroveň 1, ktorá zodpovedá koreňu stromu, reprezentuje celé obrazové pole o rozmere 2^R * 2^R, úroveň 2 reprezentuje kvadranty o rozmere 2^(R-1) * 2^(R-1) ... až napokon úroveň R+1 reprezentuje úroveň obrazových prvkov, ktoré majú rozmer 2^0 * 2^0 = 1 * 1.
Pre obrázok 256 * 256 pixelov existuje teda 9 úrovní:
Úroveň 1 -> 1 kvadrant (256*256)
Úroveň 2 -> 4 kvadranty (128*128)
Úroveň 3 -> 16 kvadrantov (64*64)
Úroveň 4 -> 64 kvadrantov (32*32)
Úroveň 5 -> 256 kvadrantov (16*16)
Úroveň 6 -> 1024 kvadrantov (8*8)
Úroveň 7 -> 4096 kvadrantov (4*4)
Úroveň 8 -> 16384 kvadrantov (2*2)
Úroveň 9 -> 65536 kvadrantov (1*1)
Ich súčet dáva sumu 87381 - to je maximálna možná dĺžka GBW súboru v tom najnepriaznivejšom prípade - ak by totiž v každom bitplane obrazu boli šachovnice s políčkami 256*256 až 1*1 pixelov.
Pri prenose použitím BF výrazu sa najprv prenesú symboly reprezentujúce uzly KSO na úrovni 1, potom na úrovni 2; až v poslednom kroku symboly reprezentujúce obrazové prvky. Pri dekódovaní symbolu G, ktorý vlastne reprezentuje šedý kvadrant, sa daný štvorec nevyfarbuje (má farbu pozadia).
Jednotlivé kroky teda reprezentujú určité aproximácie obrazu a možno ich posudzovať ako obrazy s postupne rastúcou rozlišovacou schopnosťou, pričom v poslednom kroku dostaneme originálny obraz s pôvodnou rozlišovacou schopnosťou. Príklad rekonštrukcie jednoduchého, štvorúrovňového obrazu je na obr á. 6. Povedzme, že obraz má rozmer 256 * 256 pixelov. V prvom kroku sa prenesie symbol G a v kvadrante 256 * 256 sa teda nevykreslí nič. Potom nasledujú 4 symboly BGGW, ktoré reprezentujú 4 kvadranty o rozmere 128 * 128, pričom prvý a posledný reprezentuje jednofarebné kvadranty a druhý a tretí symbol G reprezentuje sivé kvadranty. V ďalšom kroku sa prenáša postupnosť symbolov, ktorá bližšie uráuje práve charakter týchto dvoch šedých kvadrantov: BBWB BGBB, pričom rozmery kvadrantov sú už 64 * 64. Rozlišovacia schopnosť teda vzrástla dvojnásobne. V poslenom treťom kroku sa nakoniec prenáša informácia v rozlíšení 32 * 32, informácia pre posledné G, teda BWBB. Jemnejšie detaily tento náš model nemá.
K BF výrazu sa ešte podrobnejšie vrátim v deviatej kapitole pri popise jeho využitia pre kódovanie reálnych obrazov a sekvencií a pri popise môjho programu, ktorý BF kódovanie zabezpečuje.

8.5 CD VÝRAZ

Reprezentácia CD výrazmi patrí do skupiny bezsmerníkových reprezentácií a zakladá sa na prehľadávaní KSO metódou DF, pričom sa kódujú výluáne terminálne uzly KSO. Kóduje sa farba a hĺbka uzla (CD = Colour Depth). CD výraz pre binárny obraz možno písať v tvare CD = (d1,d1) (b2,d2) ... (bi,di) ... (bT,dT), kde (bi,di) je kód i-tého terminálneho uzla KSO, pričom bi je farba uzla, teda bi=(0,1) a di je úroveň uzla, teda di=(0,1,2,...R) ak raster obrazu je 2^R * 2^R. T je počet terminálnych uzlov KSO.
Pre segment daného obrázku má CD výraz tvar:
CD = (0,1)(0,2)(0,2)(1,2)(0,2)(0,2)(0,3)(1,3)(0,3)(0,3)(0,2)(0,2)(1,1)
Reprezentácia CD výrazmi je kompaktná hierarchická reprezentácia, ktorá umožňuje efektívne kódovanie a má obdobné vlastnosti ako reprezentácia obrazov DF výrazmi. Existuje možnosť transformácie CD výrazov na DF či BF a naopak.

8.6 KÓDOVANIE S FLEXIBILNOU DĹŽKOU BLOKOV

V posledných pár rokoch veľmi vzrástol záujem o algoritmy kódovania s flexibilnou dĺžkou blokov. Je všeobecne známe, že väášina prirodzených obrázkov môže byť rozdelená na časti s jemnými detailami a na časti, kde sú len hrubé detaily. Tradičné využitia kódovacích algoritmov neprispôsobujú veľkosť blokov charakteristikám meniacej sa veľkosti v prirodzených obrázkoch, ale rozdeľujú obrázok do blokov, ktoré majú pevne danú veľkosť.
Bližší pohľad na princíp kódovania s flexibilnou dĺžkou blokov ukazuje, že v súvislosti s algoritmami pre kódovanie s flexibilnou dĺžkou existujú dva hlavné problémy. Prvým problémom je, ako zaáleniť adaptivitu do segmentačného procesu, a druhý je problém rekurzivity poradia algoritmov reprezentácie spodného signálu narastajúcich (rozklad zdola-hore), alebo zmenšujúcich sa (rozklad zhora-dole) blokov.
Umiestnenie blokov rôznej dĺžky v dvojrozmernom priestore si vyžaduje určitú metodiku. Za týmto účelom využíva väášina algoritmov kódovania s flexibilnou dĺžkou blokov kvadrantovú vetvovú štruktúru, alebo jej jednoduché modifikácie. Kvadrantové vetvové štruktúry sú veľmi výkonnou a obľúbenou technikou popisujúcou dvojrozmerné plochy. Keď sa na popis obrázku používa bežný rozklad, obrázok je presegmentovaný na bloky pevnej dĺžky. Každý blok môže byť rozdelený na štyri menšie jednotky, takzvané podbloky. Po každom rozdelení je veľkosť podblokov štvrtinová oproti veľkosti ich predchodcu. Deliaca operácia môže byť mnohokrát rekurzívne opakovaná, až pokiaľ nie je potrebné ďalšie delenie, alebo bola dosiahnutá minimálna možná dĺžka bloku. Každá operácia delenia je sprevádzaná testom. V tomto teste sa rozhoduje, či sú štyri susediace bloky do určitej miery homogénne. Ak je test pozitívny, blok môže byť reprezentovaný jediným súborom parametrov typu obrázku. Ak je test negatívny, vytvoria sa štyri podbloky, a daná časť je reprezentovaná štyrmi nezávislými súbormi parametrov týchto štyroch podblokov. Deliaca operácia vytvára takzvanú 'zhora-dole' vertikálnu konštrukciu kvadrantovej vetvovej štruktúry. Naopak - zlučovacia operácia zodpovedá 'zdola-hore' vertikálnej konštrukcii kvadrantovej vetvovej štruktúry. Pri tejto operácii začiname s elementárnym malým začiatočným blokom, od ktorého smerujeme k blokom väáším pomocou niektorého z testov, ktoré testujú štyri susediace podbloky preto, aby sa mohli zlúčiť do väášieho bloku, ktorý je štyrikrát taký veľký ako jeho predchodcovia.
Na tejto filozofii stavia sľubná metóda kompresie korelovaných obrazov, ktorú rozpracoval Dr. Peter Strobach (3) a (5). Jeho spôsob kódovania je tiež založený na kvadrantovej vetvovej štruktúre a na lineárnom modeli funkcie jasu vo vnútri blokov rôznej veľkosti. Táto metóda využíva rekurzívne kódovacie algoritmy, ktoré redukujú objem úkonov na iba 3 násobenia a 8 sčitaní na jeden pixel, v čom je zahrnutý i rozklad i testovanie homogenity susediacich blokov. Strobachova metóda vykazuje výsledky, ktoré sú porovnateľné s nedávno vyvinutým vektorovým kódovaním s flexibilnou dĺžkou blokov, čo je však nepomerne zložitejšia metóda. Vo svojej súčasnej podobe je táto metóda (nazývaná 'Rekurzívne rozkladové kódovanie s kvadrantovou vetvovou štruktúrou') vhodná ako kódovacia technika v rozmedzí 0.5 - 1.5 bitu na pixel. Podrobnejšie o tomto druhu kódovania viď (3) a (5).

9. PROGRAM PRE BF KÓDOVANIE

V rámci tejto práce som mal za úlohu vytvoriť program v jazyku "C", ktorý by realizoval číslicovú kompresiu obrazových sekvencií s dôrazom na metódy, ktoré na kódovanie využívajú kvadrantový strom obrazu. Do úvahy teda pripadla kompresia obrazu lineárnym kvadrantovým stromom (LKS), kvadrantovým kódom (QC), alebo výrazom DF, BF či CD. Lineárny kvadrantový strom som vylúčil kvôli tomu, že používa lokalizačné kódy, ktoré zväášujú objem dát. To isté platí o QC, ktorý sa veľmi podobá na lineárny kvadrantový strom. Zostával jeden z výrazov - DF, BF alebo CD. Všetky tri tieto výrazy sú len iným zápisom toho istého, medzi týmito kódmi existujú exaktné predvody.
Nakoniec som sa rozhodol pre kódovanie BF a to hlavne preto, lebo na rozdiel od DF a CD, kódovanie s plošnou prioritou umožňuje postupný prenos obrazov, čo je veľmi výhodné pre rýchly sled obrazov v obrazových sekvenciách. DF kódovanie rekonštruuje každý segment, na ktorý sa dostane, od najvyššej úrovne až po úroveň obrazových bodov a CD - hoci kóduje iným spôsobom - má vo svojom princípe tiež hĺbkovú prioritu. BF kód naopak vykresľuje na celú plochu obrazovky najprv najhrubšie časti, ku ktorým sa v ďalších úrovniach pridávajú menšie segmenty a celý obraz sa takto naraz spresňuje, zjemňuje až po najvyššiu úroveň, úroveň jednotlivých pixelov, v ktorej sa zobrazia najjemnejšie detaily.

9.1 POPIS PROGRAMU

Program pre kompresiu a dekompresiu obrazových sekvencií sa skladá z dvoch hlavných častí - kompresnej (dekompozícia) a dekompresnej (kompozícia) - viď výpis programu v prílohe. Jedna od druhej sa líšia v podstate iba opačným smerom činnosti.
Kompresia (dekompozícia) sa skladá z do seba vnorených slučiek, ktoré reprezentujú jednotlivé stále sa zmenšujúce segmenty obrazu. V jadre najvnútornejšej sluáky sa nachádza systém pre zisťovanie farby segmentov (čierna - "B"lack, biela - "W"hite alebo šedá - "G"ray; zisťuje to funkcia GBW). Na každej úrovni kódovania si program zapamätá súradnice šedých segmentov, ku ktorým sa v nasledujúcej, nižšej úrovni dekompozície vráti (k ostatným nie), rozloží ich na elementárnejšie segmenty a tak ďalej. Informácie o segmentoch sa ukladajú nie v tvare tradičného (zátvorkového) BF kódu, ale ako priama postupnosť znakov reprezentujúcich tri možné rôzne stavy - G, B, W (ako bolo naznačené pri popise princípu kvadrantového stromu, viď kap. 8.4), preto som tento medzikód pracovne nazval GBW kódom (vysvetlenie viď nasledovná stať). Takýmto spôsobom sa zakódujú postupne všetky bitové roviny od siedmej - najvyššej (testuje sa stav najvyššieho, siedmeho bitu; MSB = 2^7) po nultú - najnižšiu (testuje sa stav najnižšieho, nultého bitu; LSB = 2^0), na čo slúži ďalšia sluáka, ktorá je nadradená predošlým sluákám. Nakoniec, všetkým týmto sluákám je nadradená posledná sluáka, ktorá zvyšuje poradové číslo obrazu v obrazovej sekvencii, ktorú som používal na testovanie - ide o sekvenciu desiatich reálnych televíznych obrazov (vysoko korelovaných) o rozmere 256 * 256 pixelov a s 256 úrovňami šedi (8 bitplanov) - obrazy znázorňujú muža hovoriaceho do mikrofónu. Výsledkom programu je osem súborov (zodpovedajúcich ôsmim bitovým rovinám) pre každý obraz sekvencie. GBW súbory sú vlastne ASCII postupnosťami GBW kódu. Tieto súbory sa ďalej kódujú RL-BIT kódom pripraveným pre túto aplikáciu (viď ďalej). Počas kódovania (dekompozície) jednotlivých bitových rovín sú na obrazovke zobrazené podoby jednotlivých bitplanov. Pretože kódujeme obrazovú sekvenciu, a teda vysoko korelované obrazy, odskúšal som kódovanie iba rozdielovej informácie, takže zatiaľčo prvý obraz sekvencie je rozložený na celé bitplany, každý ďalší obraz (bitplany) tvoria už len body, ktorých hodnoty sa v danom obraze odlišujú od hodnôt v predošlom obraze.
Proces rekonštukcie obrazu je vlastne obráteným postupom rozkladu. Znovu ide o do seba vnorené sluáky, v jadre ktorých je funkcia na čitanie GBW kódu, pričom sa uchovávajú (vypočítané) súradnice, ktoré boli aktuálne, keď prišiel kód G, teda kód šedého segmentu. Je to potrebné preto, aby sa vedelo, na ktorú pozíciu patrí štvorica menších segmentov, ktoré budú neskôr v GBW kóde nasledovať a ktoré tvoria daný sivý segment. Ak je ktorýkoľvek prvok štvorice G, znovu sa zapamätajú jeho súradnice atď. Program realizuje postupné plošné vykresľovanie a spresňovanie jednotlivých bitplanov a nakoniec spojí všetky bitplany a vykreslí kompletne rekonštruovaný obraz so všetkými 256 odtieňmi. Pozri obrázok á. 9A, 9B a 9C - príklad kompozície siedmeho bitplanu prvého obrázku od úrovne 1 - 256 * 256 pixelov, kedy sa nevykreslí nič, lebo prvý znak GBW súboru je G až po poslednú deviatu úroveň, ktorá zodpovedá štvorcom 1 * 1 pixel, teda jednotlivým obrazovým bodom.
Program pre BF kódovanie, ktorý som vytvoril, zámerne nie je komfortný. Mal by slúžiť ako pomôcka a nástroj pre BF kódovanie, po minimálnych úpravách je využiteľný ako funkcia v akomkoľvek inom programe v jazyku "C". Dôraz bol však kladený na rýchlosť programu, za tým účelom sú v sluákách vložené viaceré testy - napríklad že sa proces delenia na segmenty ukonči hneď ako sa vykreslí posledný G symbol z BF kódu, nie až keď sa ukonči delenie na najmenšie segmenty apod.

9.2 VÝSLEDKY BF KOMPRESIE OBRAZOVÝCH SEKVENCIÍ

Pri prenose obrazov po bitových mapách je informácia obsiahnutá v 0, 1 a 2 bitplane neužitočná, pretože rozmiestnenie segmentov sa podobá náhodnému rozmiestneniu, teda bielemu šumu. Dá sa to dobre pozorovať pri BF kompresii i dekompresii obrazov, keď sa zobrazujú jednotlivé bitové roviny - pozri rozklad reálneho obrazu (prvý obrázok sekvencie) na bitplany - obrázky á. 7A a 7B obrazovej prílohy. Ak by sme uvažovali neexaktnú dekompozíciu, vynechaním (aspoň pri určitých obrazoch) bitplanov 0, 1 a 2 by sa získala veľmi významná úspora prenášaných údajov (biely šum inak znamená najväášie objemy dát - viď Tabuľka 1 a 2), teda aj času prenosu a nárokov na záznamové médiá pri zachovaní nezmenenej subjektívnej kvality obrazu. Aj v tomto prípade sa ukazuje výhoda BF kódu oproti DF a CD, pretože v BF kóde je jednoduchšie vypustiť neužitočné 3 - 4 bitplany, pretože sú to jednoducho posledné za sebou idúce kódy. Naopak, u DF a CD sú tieto neužitočné informácie rozptýlené v celom súbore.

To isté platí aj pre kódy rozdielových obrazov - hoci vo vyšších bitových rovinách je vďaka korelácii obrazov počet zmenených bodov malý, v spomínaných nižších rovinách znovu nastáva efekt bieleho šumu, takže pri bezstratovej kompresii úspora nie je signifikantná - pozri rozklad rozdielového obrazu (druhý obrázok sekvencie vzhľadom na prvý) na bitplany, obrázky á. 8A a 8B.

GBW kód som použil ako medzivýsledok namiesto tradičného BF kódu jednak z dôvodu prehľadnosti a jednoduchosti ladenia programu, a jednak preto, že je svojou povahou viac redundantný ako BF kód a dá sa teda jednoduchšie ďalej kódovať. Hoci je GBW kód iba mezivýsledok a je vysoko redundantný, už on je úsporný pre siedmy bitplán každého obrázku (lebo GBW súbory pre siedmy bitplan sú kratšie ako 8192 B, čo je dĺžka každého bitplánu v pôvodnom obrázku = 65536/8).

GBW kód sa skladá iba z troch rôznych symbolov, pričom často vedľa seba stojí veľké množstvo rovnakých symbolov - najmä v prípade obrazu s jemnými detailami, keď vyššie úrovne sú plné šedej, teda symbolu G, alebo v prípade homogénnych plôch na ktorejkoľvek úrovni. Keďže sú iba tri možnosti vstupného kódu, G, B a W znaky možno zakódovať do dvoch bitov, napríklad G = 11, B = 01 a W = 00. Každý znak by bol teda zakódovaný namiesto bytom len dvomi bitmi, čo znamená (oproti GBW kódu) úsporu 1/4 (25%).

Je však možné dosiahnuť ešte vyššiu kompresiu GBW kódu. Už som spomenul, že GBW kód veľmi často obsahuje dlhé reťazce rovnakých znakov - najmä G. Vyskúšal som preto takéto RL kódovanie vylepšené rozpoznávacou dvojicou bitov 10 (bola nevyužitá), ktorá umožňuje rôzne dĺžky reťazcov kódovať najefektívnejšie:

DĹŽKA

1 ... 2 bity (G: 11, B: 01, W: 00)
2 ... 2 bity -------- // --------
3 ... 2 bity -------- // --------
4-7 ... 7 bitov (10 xx yyy, kde 10 je rozpoznávací znak (ak je iba jeden vieme, že ide o číslo medzi 4 až 7), xx je opakovaný znak (G: 11, B: 01, W: 00) a nasledovné tri bity yyy uráujú počet opakovaní tohto znaku)
8-15 ... 10 bitov (10 10 xx yyyy, už sú tu dva rozpoznávacie znaky 10, takže vieme, že ide o číslo medzi 8 a 15, podobne ďalej)
16-31 ... 13 bitov (10 10 10 xx yyyyy)
32-63 ... 16 bitov (10 10 10 10 xx yyyyyy)
64-127 ... 19 bitov (10 10 10 10 10 xx yyyyyyy)
128-255 ... 22 bitov (10 10 10 10 10 10 xx yyyyyyyy)
256-511 ... 25 bitov (10 10 10 10 10 10 10 xx yyyyyyyyy)
512-1023 ... 28 bitov (10 10 10 10 10 10 10 10 xx yyyyyyyyyy)
1024-2047 ... 31 bitov (10 10 10 10 10 10 10 10 10 xx yyyyyyyyyyy)
2048-4095 ... 34 bitov (10 10 10 10 10 10 10 10 10 10 xx yyyyyyyyyyyy)
4096-8191 ... 37 bitov (10 10 10 10 10 10 10 10 10 10 10 xx yyyyyyyyyyyyy)
8192-16383 ... 40 bitov (10 10 10 10 10 10 10 10 10 10 10 10 xx yyyyyyyyyyyyyy)
16384-32767 ... 43 bitov (10 10 10 10 10 10 10 10 10 10 10 10 10 xx yyyyyyyyyyyyyyy)
32768-65535 ... 46 bitov (10 10 10 10 10 10 10 10 10 10 10 10 10 10 xx yyyyyyyyyyyyyyyy)

Úspora však nebola oveľa vyššia. Pri pátraní po dôvode som si všimol zaujímavú vec (ktorá vlastne vyplýva z podstaty GBW kódu pre BF kódovanie): Každý GBW súbor, GWB kód každého bitplánu, asi v polovici mení charakter - má dve, približne rovnako dlhé, rôzne redundantné časti. Uvedomil som si, že každý GBW súbor je nehomogénny. Pozri výpis GBW kódu šiesteho bitplánu prvého obrázku (23533 B):

I. ČASŤ (1-10303) :

Prvú časť GBW kódu charakterizujú dlhé úseky G prerušované krátkymi úsekmi znakov B a W. Úseky G predstavujú "vnáranie" do hlbších úrovní a sú tým dlhšie, čim rozdrobenejší obraz (jemnejšie detaily až biely šum) je kódovaný. Pre tieto G úseky je jednoznačne najvýhodnejšie spomenuté modifikované RL kódovanie.

Pokiaľ ide o BW úseky, ktoré krátko prerušujú dlhé úseky G, tieto majú v prvej časti GBW súboru maximálne 6 znakov. Ako to vyplýva z princípu BF kódu, v tejto prvej časti musí každá štvorica obsahovať aspoň jedno G. Šesť BW znakov vedľa seba tu nastane jedine v tom prípade, že jedna štorica konči tromi BW a nasledujúca tiež začina tromi. Tieto krátke BW úseky, medzi ktorými bývajú aj jednotlivé G znaky, som sa pokúsil úspornejšie zakódovať. Z troch znakov (GBW) som tvoril n-tice a sledoval, ktorá je najvýhodnejšia pre kódovanie. Prvky sa môžu opakovať, ide teda o variácie s opakovaním r-tej triedy z troch prvkov: V'r(3) = 3^r. Zistil som, že najúčelnejšie je tvoriť pätice (r=5 alebo r=10, 15, 20, ... detto výsledky). Tabuľka variácií má v tomto prípade 3^5=243 prvkov, takže k tomuto počtu hľadáme najbližšie maximálne dvojkové číslo na určitý počet bitov. K 243 sa najviac približuje číslo 255 (teda dvojkovo 11111111). Kým normálne by sme päťicu zakódovali desiatimi bitmi (dva bity na každý znak), na kód variácií 1 až 243 (na prijímacej strane by bola potrebná tabuľka) nám postači osem bitov. Zisk je dva bity na každých päť znakov GBW, teda dva bity na desať bitov - čiže 20%. Toto kódovanie I. časti však nezlepšilo kompresiu. Úspora sa nezvýšila ani aplikovaním tohto kódu pätíc na celý GBW súbor. Úspora sa nezvýšila ani keď som aplikoval RL na dlhé úseky a kódovanie päticami len na krátke GBW úseky - "prerušenia". Možno konštatovať, že kódovanie priraďovaním kódov n-ticiam je pre GBW kód BF súborov reálnych obrazov nevýhodné.

Najlepšie výsledky v prvej časti dáva RL kódovanie - akiste preto, lebo G úseky sú veľmi často prerušované len jedným z iných znakov, napríklad ...GGGGBGGGGGG... takže vytvorenie napríklad pätice BGGGG je menej výhodné ako zakódovanie B pomocou dvoch bitov a nasledovných niekoľko desiatok alebo aj stoviek G vrámci dlhého G-reťazca.

II. ČASŤ (10304-23533):

Druhá časť predstavuje najnižšiu úroveň BF kódu obrazu, preto neobsahuje žiadne G - "znaky ďalšieho vnorenia". Ide teda o sériu výluáne znakov B a W. Keďže ide iba o dva znaky, bezvýhradne najoptimálnejšie je kódovanie každého znaku jedným bitom.

Pri dekompresii takéhoto RL-BIT zakódovaného obrazu samozrejme potrebujeme poznať dĺžku jednotlivých častí. Na začiatok každého súboru musíme teda pripojiť tri byty, ktoré budú obsahovať dĺžku prvého úseku (polohu posledného Géáka od začiatku súboru respektíve prvého od konca súboru). Druhý úsek nasleduje po prvom až do konca súboru.

Kompresiu GBW kódov obrazov pomocou RL-BIT kódu vyjadruje Tabuľka á. 1 a Tabuľka á. 2. Obrázky 2 - 10 sú v Tabuľke á. 1 kódované ako rozdiely voči predchádzajúcim obrázkom, v Tabuľke á. 2 sú všetky obrázky zakódované priamo, nie rozdielovo. Pôvodné obrázky majú veľkosť 65536 bitov, teda spolu 10 * 65536 = 655360 B. Zisk RL-BIT kódu voči pôvodným obrázkom je rozdielovo (1) 14.80 % (558382 B) a nerozdielovo (2) 15.28% (555228 B). Vidíme teda, že rozdielové kódovanie nie je v konečnom dôsledku výhodnejšie. V najlepšom prípade možno uzavrieť, že rozdielové a nerozdielové kódovanie dáva zhruba rovnaké výsledky.

Ak sa pozrieme na dĺžky RL-BIT zakódovaných bitplánov vidíme, že ich veľkosť (vždy 3, 2, 1 a 0 bitplan - takmer biely šum, nízka redundancia) prekraáuje 8192 B, čo je veľkosť, akú má každý bitplan v originálnom obrázku (lebo 65536 / 8 = 8192). Preto som tieto posledné štyri bitplany nezakódoval, iba preniesol z originálu. Zisk (1) sa zvýšil na 21.82% a (2) na 21.89%. Tieto hodnoty sú si ešte podobnejšie ako predtým, takže potvrdzujú uzáver, že rozdielové a nerozdielové kódovanie dáva zhruba rovnaké výsledky.

Pre porovnanie - kompresia RL-BIT aplikovaná na GWB kód je asi o 20% úspornejšia ako pri aplikácii komeráného archiveru LHARC.

Ako som spomínal, bitplany 2 až 0 obsahujú prakticky náhodne usporiadané pixely, ktoré predstavujú najväáší objem dát a pritom sú subjektívne zanedbateľné. Ide o takzvanú irelevanciu (nepodstatnú zložku), ktorú som spomínal v tretej kapitole, respektíve o subjektívnu redundanciu. Hoci sa vylúčením týchto troch bitplanov kódovanie zmení na ireverzibilné, subjektívne hodnotená kvalita sa nezmení. Pri vylúčení bitplanov 2 až 0 dostávame takýto zisk voči pôvodným obrázkom:

ROZDIELOVO (len bitplany 7-3)

SEKV: 1 -> 26050 B
SEKV: 2 -> 28525 B
SEKV: 3 -> 26983 B
SEKV: 4 -> 28749 B
SEKV: 5 -> 27128 B
SEKV: 6 -> 27711 B
SEKV: 7 -> 25863 B
SEKV: 8 -> 25521 B
SEKV: 9 -> 25280 B
SEKV: 10 -> 24813 B
------------------
TOTAL: 266,623 B
GAIN: 59.32 %

NEROZDIELOVO (len bitplany 7-3)

SEKV: 1 -> 26050 B
SEKV: 2 -> 27158 B
SEKV: 3 -> 27152 B
SEKV: 4 -> 26694 B
SEKV: 5 -> 28121 B
SEKV: 6 -> 25813 B
SEKV: 7 -> 26845 B
SEKV: 8 -> 26163 B
SEKV: 9 -> 26113 B
SEKV: 10 -> 26037 B
------------------
TOTAL: 266,146 B
GAIN: 59.39 %

Čiže zisk je v obidvoch prípadoch takmer až 60 percent, čo je už veľmi efektívna kompresia.

Táto aplikácia RL-BIT kódu by určite nebola natoľko efektívna pre CD či DF kód, pretože z princípu DF vyplýva, že má kratšie úseky opakovaných znakov (napríklad dlhý reťazec znakov G charakterizujúci obrazy s jemnými detailami v DF existujú tiež, ale sú poprerušované práve tými detailami, teda na zakódovanie rovnakého počtu znakov G by bolo potrebných viac bitov.

10. ZÁVER

Z povahy stromovej štruktúry kódovania vyplýva, že kompresia je najefektívnejšia pre obrazy s veľkými plochami vyplnenými jednou farbou (odtieňom), a zároveň pre obrazy, ktorých štruktúra je zväáša pravouhlá, pretože deliace sa segmenty obrazu sú štvorcové a dajú sa teda skôr charakterizovať kvadrantovým kódom (netreba prechádzať do nižších úrovní segmentov). Kódovanie systémom kvadrantového stromu by teda bolo ideálne pre rôzne technické nákresy, CAD obrazy, schémy apod.

Ako však ukázali výsledky programu pre BF kódovanie, ktorý som vytvoril v rámci tejto práce, kompresia pomocou kvadrantového stromu obrazu dosahuje dobré výsledky aj pre reálne obrazy (po aplikácii RL-BIT kódu asi 22%). BF kódovanie má okrem rýchlosti veľkú výhodu v tom, že prenáša obraz po častiach tak, že pri rekonštrukcii sa vykresľujú najprv hrubé rysy na celú plochu a neskôr detaily (to má význam pre rýchlo sa striedajúce obrazy sekvencií).

Ukázalo sa, že pri prenose obrazov po bitových mapách je informácia obsiahnutá v druhom až nultom bitplane subjektívne redundantná, pretože rozmiestnenie segmentov sa podobá náhodnému rozmiestneniu, teda bielemu šumu. Ak by sme teda pristúpili na neexaktnú dekompozíciu, vynechaním týchto bitplanov by sme získali veľmi významnú úsporu prenášaných údajov - až 60% (viď tabuľka v kapitole 9.2), teda aj času prenosu a nárokov na záznamové médiá pri zachovaní nezmenenej subjektívnej kvality obrazu.

Zaujímavou vlastnosťou BF kódovania (DF tento rys obsahuje v menšej miere) je, že nezávisí na rastri obrazu, v ktorom sa rekonštruuje, a teda umožňuje zväášovanie alebo zmenšovanie obrazu. Najmä zmenšovanie je zaujímavé - ak máme vytvorený BF kód pri určitom rozmere obrazu, môžeme ho bez problémov aplikovať na ktorýkoľvek menší rozmer (pri splnení podmienky, že vertikálny a horizontálny počet pixelov je rovnaký a je rovný 2^N) a obraz bude vždy ostrý.

Práve z uvedených dôvodov je kvadrantový strom obrazu a špeciálne BF kód perspektívnym nástrojom spracovania obrazových sekvencií.

LITERATÚRA

(1.) Leonid Jaroslavskij & Ivan Bajla: Metódy a systémy číslicového spracovania obrazov. Alfa, Bratislava 1989.
(2.) Doc. Ing. Dušan Levický, CSc.: Telematické systémy, skriptá. Technická univerzita v Košiciach, apríl 1993.
(3.) Peter Strobach: Quadtree-Structured Recursive Plane Decomposition Coding of Images. IEEE Transactions On Signal Processing, Vol. 39, No. 6, June 1991.
(4.) Ing. Ján Mihalík, CSc.: Číslicové spracovanie signálov I. Alfa, Bratislava, február 1988.
(5.) Peter Strobach: Quadtree-Structured Prediction Models for Image Sequence Processing. IEEE Transactions On Pattern And Signal Machine Intelligence, Vol. 11, No. 7, 1989.
(6.) H.B.Barlow: Visual Sensitivity. Physics and Mathematics of the Neurons System, editor M.Conrad et al. Springer-Verlag, Berlin-Heidelberg 1974, p. 198 - 204.)
(7.) M.Ptáček: Digitální zpracování a přenos obrazové informace. NADAS, Praha 1983.
(8.) Mark R. Nelson: LZW Data Compression. In: Dr. Dobb's Journal, October 1989, pages 29 ... 87.
(9.) Terry A. Welch: A Technique for High-Performance Data Compression. COMPUTER, June 1984; pages 8 - 19.
(10.) Roger Hale: image compression using fractals. National Computer Board, Singapore, March 19, 1992; pages 1 - 2.
(11.) A. K. Dewdney: Computer Recreations; pages 15 - 17.
(12.) Ian H. Witten, Radford M. Neal and John G. Cleary - Arithmetic Coding For Data Compression, Communications of the ACM, June 1987, Volume 30, Number 6; pages 520 - 540.
(13.) Gregory K. Wallace: The JPEG Still Picture Compression Standart. Communication Of the ACM, April 1991, Vol. 34, No. 4; pages 31 - 44.
(14.) Didier Le Gall - MPEG: A Video Compression Standart For Multimedia Applications. Communication Of the ACM, April 1991, Vol. 34, No. 4; pages 47 - 58.

ZOZNAM SKRATIEK

ASCII - American Standart Code for Information Interchange (Americký štandardný kód pre výmenu informácií)
BF - Breadth First - hierarchické kódovanie obrazu s prioritou plochy
bitplan - bit plane, bitová rovina (rovina rovnakých bitových váh) obrazu
CCITT - Comité Consulatif International Télégrafique et Téléphonique (Medzinárodný poradný zbor pre telegrafiu a telefóniu)
CD - Colour Depth - hierarchické kódovanie obrazu údajmi farby a hĺbky
DCT - Discrete Cosine Transformation (Diskrétna kosínusová transformácia)
DF - Depth First - hierarchické kódovanie obrazu s prioritou prechodu do hĺbky
DPCM - Differential Pulse Code Modulation (Diferenčná pulzná kódová modulácia)
GWB - medzivýsledný hierarchický kód obrazu zostavený z ASCII znakov "G", "B" a "W"
IEEE - Institute of Electrical and Electronics Engineers (Inštitút inžinierov elektrotechniky a elektroniky)
ISO - International Standarts Organination (Medzinárodná organizácia štandardov)
JPEG - Joint Photographic Experts Group (Spojená skupina fotografických expertov)
KSO - kvadrantový strom obrazu
LSB - Least Significant Bit (bit s najnižšou váhou)
MPEG - Moving picture Experts Group (Skupina expertov pre pohyblivý obraz)
MSB - Most Significant Bit (bit s najvyššou váhou)
PCM - Pulse Code Modulation (Pulzná kódová modulácia)
pixel = picture element (obrazový prvok)
QC - Quadrant Code (Kvadrantový kód)

OBRAZOVÁ PRÍLOHA

VÝPIS PROGRAMU BF-QUADTREE v jazyku "C"

Tomáš Fülöpp
Košice, Slovakia
April 18, 1995

• Commodore Amiga

• Fraktály Benoita Mandelbrota
• Galaxis: A Calendar and Encrypting Program (GFA Basic, Amiga)

• https://www.tuke.sk/