Úvod
Pod pojmom obraz môžeme rozumieť priemet reálneho sveta na sietnicu oka, napríklad fotografiu, stránku papiera, či vyrenderovanú scénu na monitore. Matematickým modelom obrazu je spojitá funkcia dvoch premenných - tzv. obrazová funkcia
z=f(x, y). (4.1)
Definičným oborom obrazovej funkcie (4.1) je spojitý interval I z R^2, x a y sú súradnice bodu v 2D, v ktorom funkcia nadobúda hodnoty zo svojho definičného oboru [2]. Z matematického hľadiska táto hodnota môže nadobúdať ľubovoľnú hodnotu, ale v praxi je táto hodnota určená konkrétnou aplikáciou. Najčastejšie je hodnota daná reprezentovaná jedným číslom (jas, intenzita farby,...). V počítačovej grafike sú to najčastejšie hodnoty farieb z modelov RGB, CMY, HSV alebo XYZ. Hodnota predstavuje dôležitú informáciu o danom bode. Ak máme obor hodnôt funkcie dostatočne veľký, tak si môžeme vybrať presnejšiu hodnotu na opísanie bodu. Preto napríklad nám obraz s true color (skutočnými, pravými) farbami nám poskytne viac informácií ako keď by bol len 16 farebný. Najčastejšie sa pracuje s nasledujúcimi farebnými paletami : 256, 65565 a 16,7 milión farieb, prípadne ešte s 256 odtieňmi šedej.
Pri vytváraní obrazu je obor hodnôt funkcie obmedzený nielen vlastnou aplikáciou, ale aj fyzikálnymi vlastnosťami technického zariadenia, ktoré pritom použijeme. Nevýhodou, ktorá vyplýva z matematického modelu a vlastnosti obrazu je skutočnosť, že takmer nikdy nemáme spojitý definičný obor funkcie. Väčšinou používame bodový raster, ktorý sa skladá zo základných obrazových elementov - pixlov. V trojrozmernom priestore je základným objemovým elemtom voxel (pravdepodobne ste sa už stretli s hrami, ktoré používajú voxelovú technológiu napr. Comanche, Outcast,...). Základným elementom textúry je zase texel.
Obrazová funkcia (4.1) je definovaná na podmnožine dvojrozmerného priestoru. Pre jednoduchosť je ale niekedy výhodnejšie ukázať princíp v jednorozmernom definičnom obore. Preto budeme v nasledujúcej časti väčšinou uvažovať o jednorozmernej funkcii.
Digitalizácia
Pri získanavaní digitálneho obrazu nastáva prechod od spojitej funkcie f(x,y) k diskrétnej funkcii D(x,y), a to aj v definičnom obore funkcie f(x,y) a aj v jej obore hodnôt. Tento proces sa nazýva digitalizácia. Skladá sa z dvoch nezávislých častí: kvantovania a vzorkovania.
Kvantovanie
Podstatou kvantovania je diskretizácia hodnôt obrazovej funkcie. Tá sa rozdelí na intervaly, ktorým sa priradí jediná hodnota - zástupca. Ak je dĺžka intervalu konštantná, tak ide o uniformné kvantovanie. Pri neuniformnom kvantovaní sa používa premenlivá dĺžka intervalu. Je vhodné na prevod obrázku s veľkým počtom farieb na farebné obrázky s menším počtom farieb. Spôsob, akým určíme zástupcu intervalu, závisí od použitia obrazu. Môžeme vypočítať priemernú hodnotu z celého intervalu, určiť medián, spriemerovať hraničné hodnoty, atď.
Kvantovaním sa dopúšťame tzv.
kvantizačnej chyby. Príčinou je náhla zmena farieb, ak na intervale,
ktorý diskretizujeme je hladká zmena farieb, túto nahradzujeme jednou vypočítanou
hodnotou. Ak máme plynulý prechod farieb, a ten diskretizujeme,
dostávame skokové prechody, na ktoré je ľudské oko citlivé, a preto táto
chyba pôsobí dosť rušivo. Čiastočne ju môžeme eliminovať neuniformným kvantovaním
s vhodným zástupcom.
Vzorkovanie
Vzorkovaním (sampling) spojitej funkcie f(x,y) môžeme rozumieť zisťovanie hodnôt (vzoriek) v pravidelných intervaloch. Môžeme ním chápať aj prechod od spojitého na diskrétny prípad. Dostaneme tak novú funkciu V(x,y). Pritom využívame fakt, že pixel nie je bod, ale plocha nenulovej veľkosti. Túto plochu nám reprezentuje jedna hodnota. Bodovým vzorkovaním nazývame také vzorkovanie, pri ktorom získavame hodnoty v jednom bode. Pri plošnom vzorkovaní priraďujeme oblasti jedinú hodnotu, najčastejšie priemernú hodnotu oblasti. Táto metóda je ale náročná na výpoče, a preto sa snažíme plošné vzorkovanie aproximovať viacerými bodovými vzorkami a tie spriemerovať.
Sampling applet. Author Štulrajterová Paulína
Fourierova transformácia
Pre jednoduchosť si ukážeme Fourierovu transformáciu na jednorozmernej funkcii f(x). Fourierovým obrazom jednorozmernej funkcie f(x) definovanej na spojitom definičnom obore, budeme chápať komplexnú funkciu F(u), ktorú dostaneme nasledovne :
Inverznú Fourierovu transformáciu definujeme :
,
pričom u je frekvenčná premenná a x je priestorová premenná.
Ak náhodou neviete, čo to je za "znak medzi ležiacimi osmičkami" (volá sa integrál), tak preskočte túto stať a skočte na diskrétnu Fourierovu transformáciu.
Pretože funkcia F(u) je
komplexná, môžeme ju napísať v tvare F(u) = R(u) + i.I(u),
kde R(u) a I(u) sú reálne funkcie reprezentujúce
reálnu a imaginárnu časť.
Často sa používa exponenciálny tvar Fourierovej transformácie :
,
, kde i je komplexná jednotka,
je
Fourierovým spektrom funkcie f(x) a
je
fázový uhol.
Funkcia pre štvorec spektra je 
.
Pretože exponenciálny tvar Fourierovej transformácie sa dosť ťažko počíta, hlavne keď je tam "e na čosi", tak na úpravu používame Eulerovu formulu :
exp (-i2piux) = cos(2piux) -i.sin(2piux)
Teraz rozšírme Fourierovu transformáciu pre funkciu dvoch premenných f(x,y). Nech f(x,y) je spojitá a integrovateľná a F(u,v) je tiež integrovateľná, potom Fourierova transformácia bude
a
,
pričom u a v sú frekvenčné premenné
a x,y sú priestorové premenné a potom
spektrum je: 
,
fázový uhol: 
,
štvorec spektra: 
.
Diskrétna Fourierova transformácia
Pri výpočte jednorozmernej Fourierovej transformácie sme používali spojitú jednorozmernú funkciu f(x) s premennou x, podľa ktorej sme integrovali od mínus nekonečno po plus nekonečno. V praxi však máme danú diskrétnu postupnosť funkčných hodnôt (postupnosť navzorkovaných hodnôt) a na výpočet používame diskrétnu Fourierovu transformáciu.
Pre ľahšie pochopenie si ju ukážeme
na príklade. Predpokladajme, že máme spojitú funkciu f(x). Zoberieme z
nej postupnosť funkčných hodnôt s pravidelných krokom dx, {(f(x0).
f(x0+1.dx), ..., f(x0+N.dx)}.
V prípade grafického obrázku to bude postupnosť funkčných hodnôt jedného riadku. V
prípade spojitej funkcie to bude pravidelné vzorkovanie. Získanú postupnosť
môžeme vyjadriť :
f(x) = f(x0 + x.dx), kde x = 0,1, ..., N,.
Potom diskrétna Fourierova transformácia je :
a 
,
kde u a x = 0, 1, ..., N.
Pre funkciu dvoch premenných definujeme diskrétnu Fourierovu transformáciu :
,
kde u = 0, 1, ..., M,.v = 0, 1, ..., N,
,
kde x = 0, 1, ..., M, a y = 0, 1, ..., N.
Alias a antialiasing
Slovo alias v grafike znamená neželaný optický jav, kaz obrazu [1]. Stretávame sa s ním napríklad pri kreslení úsečiek do rastra. Diagonálna úsečka v štvorcovom rastri sa skladá z rovnakého počtu bodov ako pri jej horizontálnom priemete na os x, čo spôsobuje, že diagonálna úsečka je jasovo redšia a úsečka nevyzerá hladko. Je to spôsobené rastrovaním obrazu.
Antialiasing v počítačovej grafike znamená vyhladzovanie hrán. Na to použijeme metódu vyrovnávania a vyhladzovania, ktorú prvýkrát použili Catmull a Crow. Táto myšlienka spočíva v tom, že obrazový bod má na displeji nenulovú plochu, a preto má aj zobrazený bod v priestore modelu tiež nenulovú plochu. V nasledujúcom applete je zobrazená úsečka nenulovej hrúbky, položená do rastra. Každý štvorec rastra predstavuje jeden obrazový pixel.
Obrazový bod prekrývajúci sa s úsečkou danej hrúbky bude mať intenzitu danú veľkosťou ich prieniku. Časová náročnosť je však pomerne náročná, a preto sa pri vykresľovaní v aplikáciách sa väčšinou povoľuje alebo zakazuje, či má aplikácia antialiasing pri kreslení používať alebo nie.
Kompresia rastrového obrazu
RLE kódovanie
RLE kódovanie je jednoduchá, ale
účinná metóda na kompresiu dát a používa sa napr. pri kódovaní BMP
a PCX súborov.
Metóda na kódovanie binárnej postupnosti, pri ktorej sa kódujú vzdialenosti prechodov postupností núl a jednotiek. Veľmi jednoduchá a efektívna metóda, ktorá vychádza z predpokladu často
sa opakujúcich susedných pixlov. Ako príklad majme postupnosť
7,7,7,7,7,7,7,7,7,7,7,7. Nebolo by lepšie zapísať túto postupnosť ako len
12,7, ktoré by značili počet opakovaní čísla plus samotné číslo.
Máme zakódovať danú postupnosť : 00111111000001100000110011011100011111.
Na začiatku postupnosti je 0, preto postupujeme ďalej až prídeme k prvej 1. Vtedy do výsledného reťazca poznačíme dĺžku núl na začiatku tj. v našom prípade číslo 2.
Aktuálny stav kódovania: sme na bite č. 3 a máme zakódované prvé dva bity. Ideme ďalej v postupnosti, až kým nenarazíme na prvú 0. Tá je na 8. bite. V postupnosti sa vyskytlo 5 jednotiek a toto číslo dáme do výstupného reťazca.
Na konci dostaneme výsledný reťazec: 265252221335. Najväčšie číslo je v ňom 5. Na zápis tohto čísla budeme potrebovať 3. bity. Preto všetky čísla výsledného reťazca prevedieme do binárnej sústavy a pre každé číslo vyhradíme 3 bity. Výsledná postupnosť bude: 010 101 101 010 101 010 010 001 011 011 101. Dĺžka tejto postupnosti je spolu 36 bitov. Pôvodná postupnosť mala dĺžku 38 bitov.
Po pochopení tohto príkladu si ukážme výhody a nevýhody tejto metódy. Všimnite si, že ak v predchádzajúcom príklade by sme do postupnosti pridávali 1 alebo 0 tak, že dĺžka za sebou idúcich 1 alebo 0 by nepresiahla 7, dĺžka výslednej postupnosti sa nebude meniť, pričom dĺžka pôvodnej postupnosti by narastala. V prípade, že postupnosť by obsahovala málo opakujúcich sa hodnôt, dostaneme výslednú postupnosť dlhšiu ako pôvodnú. Postupnosť by mala zápornú kompresiu, a vtedy je dané kódovanie neúčinné a spôsobuje "zápornú" kompresiu.
Huffmanov kód
Huffmanov kód patrí medzi základné bezstratové kódy, pri ktorých nenastáva strata dát [4]. Pretože vychádza z entropie, býva často zaradený medzi entropické kódy. Na kódovanie sa využíva podobný princíp ako Morseova abeceda, kde najviac vyskytujúcim hláskam anglického jazyka je priradený najkratší kód a málo vyskytujúce hlásky majú kód dlhší. Huffmanov kód sa snaží optimálne rozdeliť postupnosti binárnych symbolov podľa početnosti výskytu kódovaných prvkov so snahou priblížiť sa ich entropii.
Definícia:Pre náhodnú premennú f1, f2, ... , fk a pravdepodobnosti p (fi) = pi definujeme entropiu
Príklad :
Majme hodnoty q1, q2, ... , q8 s nasledujúcimi pravdepodobnosťami : p1=0,4 p2=0,08 p3=0,08 p4=0,2 p5=0,12 p6=0,08 p7=0,04 p8=0.
Pre binárne kódovanie ôsmych hodnôt by sme potrebovali 3 bity na každú hodnotu .
Entropia je H = -[0,4.log 2
(0,4) + 3 x 0.08. log
2 (0.08) +
+ 0.2 x log 2
(0.2) + 0.12 x log 2 (0.12) +
+ 0.04 x log 2
(0.04)] =
;
= 2.42 bitu
Huffmanove kódovanie sa snaží
Postup kódovania je nasledovný [4]:
- nájdeme dve najmenšie početnosti a spočítame ich
- vo výsledku z predchádzajúceho kroku nájdeme dve najmenšie početnosti
a spočítame ich
- pokračujeme v predchádzajúcom kroku až po relatívnu početnosť 1
- kódové slová budú zložené z 0 a 1 podľa stromu, ktorý vznikne sčítavaním a to tak, že postupujeme spätne od hodnoty početnosti jedna, kde vľavo bude 1 a vpravo 0, čo sú najvyššie bity a rovnakým postupom vypočítame nižšie bity.
Postup si môžete pozrieť na nasledujúcom applete.
Lempel - Ziv - Welch
Táto metóda (a jej modifikácie) sa používa vo väčšine kompresných programov (ZIP, RAR, ARJ, LHA a i.) a grafickom formáte GIF.
V roku 1977 prišil Lempel a Ziv na novú metódu kódovania dát, ktorú v roku 1984 zdokonalil Welch. Princíp spočíva v nahradení vzoriek vstupných dát binárnymi kódmi premenlivej (väčšinou postupne rastúcej) dĺžky. Vstupné vzorky sa kódujú podľa slovníka, ktorý sa postupne dopĺňa. Dĺžka slovníka je daná počtom bitov použitých pri kódovaní. V prípade, že sa slovník zaplní, zvýšime počet bitov výstupných dát o 1. Takto dosiahneme zväčšenie veľkosť slovníka na dvojnásobok. Pri spracovávaní obrázku s farebným rozlíšením jeden bajt na pixel máme základný slovník o veľkosti 256 (8 bitov). Prvých 256 položiek slovníka (tj. základný slovník) nemusíme zapisovať do výstupných dát, lebo je totožný s hodnotami 0 až 255.
DCT (diskrétna kosínusová transformácia)
Pri kódovaní obrázkov s veľkým počtom farebných prechodov a farieb metódy RLE a LZW nedávajú dobré výsledky. Kvalitné obrázky však majú počet farieb 24 alebo 32 bitov na bod, kde je len málo zhodných susedných bodov (bodov z veľmi malým rozdielom farby, jasu a pod.). Na takéto obrázky sa hodí stratové kódovanie. Pri takomto počte farieb si totiž zníženie kvality veľmi nevšimneme. Kódovanie pomocou DCT (diskrétna kosínusová transformácia) dáva veľmi dobré výsledky. Aj preto je použite pri grafickom formáte JPEG. Pri kódovaní obrázka do JPEG pri 75 percentnom zachovaní pôvodných obrazových dát dostaneme kompresný pomer 1 : 20 až 1 : 25. DCT je vlastne diskrétna Fourierova transformácia, pričom postupnosť funkčných hodnôt sú v tomto prípade obrazové dáta. Na spracovávanie je najprv nutné previesť použitý farebný model (RGB,...) do modelu YCBCR.
Obrázok č. 5.7: JPEG obrázok s kvalitou kompresie 85 percent (hore) a 15 percent (dole).
Ako môžete vidieť na obrázku (5.7), so zvyšovaním stupňa kompresie sa prejavuje štvorcový efekt. Ten je spôsobený rozdeľovaním obrázka na pravidelné štvorce o veľkosti 8x8 a ich postupné spracovanie.
Fraktálna kompresia
Jednou z najperspektívnejších typov modernej kompresie je fraktálna. Túto metódu vymyslel Michael F. Barnsley pri výskume fraktálnych algoritmov. Patrí medzi nesymetrické kompresie, pretože čas medzi kompresiou a dekompresiou je výrazne rozdielny v neprospech času kompresie. Metóda je založená na vyhľadávaní podobnosti, či už tvarových alebo farebných častí, v rôznych častiach komprimovaného obrazu. Matematicky ju môžeme zapísať lineárnou transformáciou:
T[x,z] = [ax + by + e, cx + dy + f ],
pričom je v tom vyjadrené otočenie, zmenšenie a posunutie nájdenej podobnej časti.
Je prekvapivé, že aké množstvo podobných a opakujúcich sa vzoriek a detailov môžeme nájsť v obrázkoch z reálneho sveta i generovaných počítačom. Štandardný súbor na uchovávanie takto komprimovaných obrázkov je formát FIF (Fractal Image Format), v ktorom sú uložené koeficienty podobnosti v komprimovanom tvare. Pri komprimácii sa algoritmus snaží rozdeliť obraz na nerovnaké časti (domény) a tie potom vhodne transformovať na výsledný obraz.
Celková veľkosť komprimovaného súboru je závislá od počtu domén a transformácii použitých na poskladanie obrazu. Tie závisia hlavne od času použitého na hľadanie najlepších transformácii. Časová zložitosť hľadania vhodnej transformácie je mimoriadne náročná a väčšinou sa pri komprimácii fraktálnou kompresiou zadáva maximálny čas, pokiaľ môže algoritmus hľadať najlepšie transformácie. Hľadať takéto transformácie je veľmi náročné aj preto, lebo každý obraz má iné vlastnosti a nie je možné naň aplikovať jednotný postup ako pri predchádzajúcich typoch kódovania. Celková doba fraktálnej kompresie sa pohybuje rádovo v desiatkach minút. Dekompresia je však veľmi rýchla a porovnateľná s predchádzajúcimi typmi kódovania. Pri kódovaní fraktálnou kompresiou dostaneme obraz, ktorý môžeme veľmi dobre zväčšovať, pretože transformácie sú zadané funkciami a tie môžeme iterovať (zväčšovať) do akejkoľvek veľkosti, prakticky bez straty kvality.