Ukážková implementácia

 

3.2 Program Graphedit

 

Program Graphedit slúži na prácu s grafmi. Umožňuje jednoduchú interaktívnu vizuálnu editáciu grafu, pridávanie a odoberanie filtrov, spájanie vybraných pinov, nastavovanie parametrov filtrov, uloženie grafu do súboru (aj s nastaveniami filtrov) a jeho opätovné načítanie. Taktiež poskytuje funkcie spúšťania, ukončenia a monitorovania behu grafu. Jednotlivé knižnice filtrov sú pripojiteľné do aplikácie vo forme zásuvných modulov (Plugin DLLs).

 

 

 

 

 

 

Obrázok 9: Program Graphedit.

 

3.3 Triedy filtrov

 

Súborový vstup – výstup:

File input stream – vstup zo súboru, načíta súbor do pamäťového buffra

File output stream – výstup do súboru, uloží pamäťový buffer do súboru

 

Kódovanie a dekódovanie formátov:

Bmp decoder – dekodér súborov BMP, rozdelí obraz vo formáte BMP na farebné roviny R, G a B, podporuje len 24 bitový formát bez kompresie

Bmp encoder – kodér súborov BMP, skombinuje farebné roviny RGB do formátu BMP

 

Zobrazovanie:

RGB display – farebné zobrazovacie okno, okno s tromi vstupmi pre kanály R, G a B

Mono display – monochromatické zobrazovacie okno, okno s jedným mono vstupom, ktorý zobrazuje v odtieňoch šedej

Text display – zobrazovač textovej informácie, dokáže zobraziť celé číslo, desatinné číslo a reťazec znakov

 

Spracovanie farby:

RGB conversion – konverzia farebných modelov z a do farebného modelu RGB

Grayscale conversion – konverzia farebného modelu RGB na šedo tónovú škálu

 

Zmena rozlíšenia:

2:1 reduction / expansion – redukcia alebo expanzia rozlíšenia na polovicu alebo dvojnásobok, ide o rýchlu redukciu priemerovaním a rýchlu expanziu interpoláciou

Crop – orezanie obrazu, vyreže z obrazu istú časť

Resample – zmena rozlíšenia obrazu v ľubovoľnej mierke, prevzorkuje obraz do ľubovoľného rozlíšenia s použitím nastaveného konvolučného filtra

 

Fraktálne kódovanie:

HV encoder – fraktálny kodér založený na horizontálno-vertikálnej schéme

HV decoder – dekodér fraktálne kódovaných dát

 

Práca s pamäťovými bufframi:

Serializer – spájajúci filter, spojí niekoľko pamäťových buffrov do jedného a pridá informáciu o ich usporiadaní

Deserializer – rozdeľujúci filter, rozdelí spojené pamäťové buffre

 

Kódovanie polí celých čísel:

Binary encoder – binárny kodér, binárne zakóduje pole celých čísel použitím iba potrebného počtu bitov

Binary decoder – binárny dekodér, dekóduje binárne zakódované dáta

Huffman encoder – huffmanov kodér, zakóduje pole celých čísel huffmanovým kódom

Huffman decoder – huffmanov dekodér, dekóduje dáta zakódované huffmanovým kódom

 

Meranie:

PSNR enumerator – merač podobnosti dvoch obrazov na základe RMS metriky

 

Bližší popis filtrov a ich nastavení možno nájsť v dokumentácii k jednotlivým filtrom.

 

 

3.4 Trieda HV encoder (fraktálny kodér)

 

Trieda HV encoder je implementáciou horizontálno-vertikálnej schémy fraktálnej transformácie. Vstupom je šedo tónový obraz (v ľubovoľnom dynamickom rozsahu) a výstupom je sada afinných transformácií popisujúca IFS systém, ktorého atraktor je podobný vstupnému obrazu.

 

3.4.1 Transformácie

 

HV encoder je kvôli časovej náročnosti prehľadávania obmedzený len na afinné transformácie. HV schéma rozdeľuje obraz na obdĺžnikové bloky. Kvôli tomu je množina afinných transformácie ešte zúžená len na určité vhodné typy. Uvažujeme len tieto typy afinných transformácií: posunutie, škálovanie (kvôli kontraktívnosti len zmenšenie), preklopenie okolo horizontálnej osi (horizontal flip), preklopenie okolo vertikálnej osi (vertical flip), otočenie o 90° doprava a ich kombinácie. Zložením týchto transformácií môžme docieliť otočenie aj o iné uhly (180°, 270°). Týmto sme množinu možných transformácií dostatočne zúžili, čím sme zabezpečili ľahké kódovanie transformácie, ale tiež sme ponechali dostatočnú voľnosť, čím sme pokryli veľkú časť množiny atraktorov. Transformácia je teda určená blokom (pozícia a rozmery), doménou (pozícia a faktory zväčšenia šírky a výšky vzhľadom na veľkosť bloku) a modifikáciou domény (otočenie o 90°, horizontálne a vertikálne preklopenie). Pozícia bloku a domény určuje posúvaciu časť transformácie, faktory zväčšenia šírky a výšky určujú škálovaciu časť transformácie, modifikáciu domény treba uložiť osobitne.

 

Obrázok 10: Použité transformácie: (a) škálovanie, (b) otočenie o 90°doprava,

(c) horizontálne preklopenie, (d) vertikálne preklopenie.

 

Modifikáciu domény zakódujeme tromi bitmi: 1 bit pre otočenie o 90°, 1 bit pre horizontálne preklopenie a 1 bit pre vertikálne preklopenie. Posúvaciu a škálovaciu časť transformácie budeme kódovať iným spôsobom.

 

3.4.2 Nastavenia a parametre

 

Prácu filtra HV encoder môžme ovládať nastavením množiny parametrov pred jeho spustením. Zmenami parametrov je možné ovládať hlavne cieľovú kvalitu výstupu, veľkosť výstupu a čas potrebný na spracovanie. Parametre je možné nastaviť v konfiguračnom dialógu filtra (dvojklikom na box filtra v programe Graphedit).

 

Obrázok 11: Konfiguračný dialóg triedy HV encoder.

 

Compression mode: Mód kompresie alebo voľba kompresného algoritmu. Tu máme na výber či je našim cieľom dosiahnuť stanovenú vernosť (voľba Fidelity) alebo veľkosť (voľba Size). Mód Fidelity neprihliada na množstvo transformácií, ktoré generuje ale snaží sa nájsť pokrytie v nastavenej tolerancii. Mód Size hľadá najlepšie pokrytie s použitím ohraničeného počtu blokov (transformácií), čím zabezpečí, že veľkosť výstupu bude zhora ohraničená.

 

Fidelity mode settings: Nastavenia módu Fidelity.

Error mode: Mód chyby. Algoritmus používa RMS metriku na porovnanie podobnosti medzi pokrývaným blokom a zmenšenou doménou. Voľba Absolute nastaví priamo hodnotu maximálnej povolenej RMS odchýlky (alebo chyby) na hodnotu Max error (). Pri voľbe Quality si algoritmus vypočíta sám maximálnu povolenú odchýlku z dynamického rozsahu vstupného obrazu. Hodnotou Quality () môžme túto toleranciu ovplyvniť. Hodnota 1.0 znamená maximálnu kvalitu (žiadna tolerancia, akceptovaná len RMS odchýlka 0.0 t.j. žiadna chyba), naopak hodnota 0.0 znamená najnižšiu kvalitu. Väčšie hodnoty Quality spôsobia generovanie väčšieho množstva blokov a tým väčšiu vernosť ale aj veľkosť výstupu.

Covering mode: Mód pokrývania. Voľba Best cover dovoľuje algoritmu pokračovať a dokončiť prehľadávanie aj keď už bolo nájdené pokrytie v danej tolerancii. Algoritmus sa snaží nájsť najlepšie pokrytie bloku aj za cenu väčšej časovej náročnosti. Voľba Cover in tolerance túto možnosť nepovoľuje a prehľadávanie sa zastaví pri nájdení prvého pokrytia v danej tolerancii.

Maximal diference checking: Kontrola maximálnej odchýlky. Hovorí algoritmu aby udržiaval tiež maximálnu odchýlku bloku v tolerancii (nie len RMS odchýlku). Týmto je udržiavaná vyššia vernosť (väčšinou za cenu zväčšenia veľkosti výstupu). Tento parameter je zatiaľ len v experimentálnom stave a nie je zaručená 100%-ná funkčnosť.

 

Size mode settings: Nastavenia módu Size.

Max number of ranges: Maximálny povolený počet blokov (). Po dosiahnutí nastaveného počtu blokov sa algoritmus zastaví.

 

Search mode: Mód prehľadávania. Určuje akým spôsobom sa budú vyberať domény pre bloky. Momentálne je k dispozícii len voľba Grid search. V móde Grid search sú domény vyberané zaradom z pozícií v mriežke s nastavenou hustotou každých X step pixelov v horizontálnom smere a Y step pixelov vo vertikálnom smere. Tento spôsob prehľadávania je časovo náročný.

 

Ranges: Nastavenia obmedzujúce veľkosť, škálovacie faktory bloku a škálovací faktor domény. Tieto nastavenia sú striktne dodržiavané a ich nevhodné nastavenie môže spôsobiť nedosiahnutie cieľa (t.j. strata cieľovej kvality alebo prekročenie cieľovej veľkosti, v závislosti od nastaveného módu kompresie) alebo nájdenie nevhodného atraktora.

Min range size: Minimálna povolená veľkosť bloku (). Blok, ktorý má obidva rozmery menšie alebo rovné ako nastavená hodnota, už nebude rozdelený na menšie bloky (aj keby to bolo potrebné). Hodnota MinRangeSize=0 znamená neobmedzené delenie bloku (t.j. dovoľuje algoritmu deliť blok až do rozmerov 1x1). Väčšie hodnoty zamedzujú generovaniu malých blokov, ale môžu spôsobiť stratu kvality.

Max range size: Maximálna povolená veľkosť bloku (). Blok, ktorý má aspoň jeden rozmer väčší ako nastavená hodnota, nebude pokrývaný a bude hneď rozdelený na menšie bloky (aj keby počet blokov presiahol povolenú hranicu). Hodnota MaxRangeSize=0 povoľuje neobmedzenú veľkosť bloku. Menšie hodnoty zamedzujú pokrývaniu veľkých blokov (pre ktoré sa väčšinou nenájde vhodné pokrytie), čím sa ušetrí čas, ale môžu spôsobiť generovanie veľkého množstva blokov, čím sa zväčší veľkosť výstupu.

Min range factor: Minimálny pomer veľkosti bloku a domény ().

Max range factor: Maximálny pomer veľkosti bloku a domény (). Tieto dva parametre ovplyvňujú výber domén. Na jednej pozícii sú vybraté domény so všetkými možnými kombináciami škálovacích faktorov, ktoré sú ešte kombinované s otočením (t.j. ak MinRangeFactor=2 a MaxRangeFactor=3 tak na jednej pozícii je vybratých a porovnaných 8 domén škálovaných nasledovne: 2x2, 2x2o, 2x3, 2x3o, 3x2, 3x2o, 3x3, 3x3o, vzhľadom na veľkosť bloku). Veľký rozsah faktorov spôsobí značné predĺženie pokrývania (čas potrebný na pokrytie rastie exponenciálne). Takisto veľké hodnoty faktorov spomaľujú pokrývanie.

Max scale factor: Maximálny povolený škálovací faktor domény (, mal by byť menší ako 1.0 ale nie je to podmienkou). Pri pokrývaní bloku vybratou doménou sa vypočíta najlepší škálovací faktor a posunutie (v jasovej zložke obrazu, nie v priestorovej) pre dosiahnutie minimálnej RMS odchýlky. Ak ale škálovací faktor je väčší ako 1.0 výsledný IFS systém nemusí konvergovať resp. atraktor môže mať neobmedzené rozmery. Preto, ak vypočítaný škálovací faktor je väčší ako nastavená hodnota, pokrytie je odmietnuté.

 

Obrázok 12: Veľkosti domén pre MinRangeFactor=2 a MaxRangeFactor=3 (a) pôvodný blok s rozmermi axb. Kombinácie: (b) 2x2 (2ax2b) a 2x2o (2bx2a), (c) 2x3 (2ax3b) a 2x3o (3bx2a), (d) 3x2 (3ax2b) a 3x2o(2bx3a), (e)  3x3 (3ax3b) a 3x3o (3bx3a).

 

Quantization: Nastavenia kvantizácie. Hodnoty škálovacieho faktoru a posunutia vypočítané pri pokrývaní sa ďalej kvantujú lineárnym kvantizátorom a z kvantovaných hodnôt sa vypočíta RMS odchýlka. Väčší počet kvantizačných úrovní dovolí zachovať kvalitu, ale môže zväčšiť veľkosť výstupu. Menší počet úrovní znižuje kvalitu, ale zmenšuje veľkosť výstupu. V istých prípadoch menší počet úrovní môže spôsobiť generovanie väčšieho množstva blokov a tým zväčšiť výstup (hlavne pri vyšších kvalitách, kedy kvantovanie značne zníži kvalitu pokrytia bloku).

Scale levels: Počet kvantizačných úrovní pre škálovací faktor domény ().

Offset levels: Počet kvantizačných úrovní pre posunutie ().

 

Threads: Nastavenia výpočtových vlákien. Trieda HV encoder je navrhnutá a implementovaná s možnosťou spolupráce viacerých výpočtových vlákien, ktoré zabezpečujú paralelné pokrývanie jedného bloku. Týmto dovoľuje využiť možnosti viac jadrových a viac procesorových systémov a urýchliť proces pokrývania. Táto možnosť je v experimentálnom stave a nie je zaručená 100%-ná funkčnosť (odporúčame používať len jedno vlákno kvôli korektnosti výsledkov).

Number of threads: Počet paralelných spolupracujúcich vlákien ().

Thread priority: Nastavenie systémovej priority výpočtových vlákien. Voľba Normal nastaví normálnu prioritu, čo môže spôsobiť dlhšie nereagovanie systému kvôli vyťaženiu procesora. Voľba Idle nastaví prioritu na minimálnu hodnotu, čo zaručí reakcie systému, ale môže skresliť (predĺžiť) merané časy výpočtov.

 

Feedback window: Okno vizualizácie algoritmu. Voľba povolí alebo zakáže zobrazenie vizualizačného okna, cez ktoré je možné monitorovať stav a priebeh algoritmu. Zapnutá vizualizácia môže výrazne spomaliť priebeh pokrývania.

 

3.4.3 Výstupy

 

Obrázok 13: HV encoder.

 

Výstup triedy HV encoder je množina transformácií. Každá transformácia je určená blokom, doménou a modifikáciou domény (kódovanou vyššie uvedeným spôsobom). Trieda poskytuje výstup rozdelený do niekoľkých výstupných štruktúr podľa charakteru výstupnej informácie. Informácie o transformáciách sú rozdelené kvôli ich rôznorodosti. Rôzne časti majú rôzny charakter a je vhodné ich kódovať rôznym spôsobom.

 

Výstupy triedy HV encoder podľa pinov:

HDR (Header): Hlavičková štruktúra. Obsahuje základné informácie o predlohe ako rozlíšenie, dynamický rozsah, niektoré parametre použité pri kódovaní, a dáta potrebné na korektné dekódovanie.

 

SI (Scale Indicies): Kvantované indexy škálovacích faktorov, kódované ako pole celých čísel.

 

OI (Offset Indicies): Kvantované indexy posunutí, kódované ako pole celých čísel.

 

TRN (Transformations): Zakódované informácie o modifikáciách domén, kódované ako pole celých čísel.

 

DP (Domain Positions): Pozície domén predelené hodnotami X step pre x-ovú pozíciu a Y step pre y-ovú pozíciu, kvôli zmenšeniu hodnôt a možnosti efektívnejšieho kódovania. Kódované po dvojiciach ako pole celých čísel.

 

DF (Domain Factors): Škálovacie faktory blokov, kódované po dvojiciach ako pole celých čísel.

 

RP (Range Positions): Pozície blokov, kódované po dvojiciach ako pole celých čísel.

 

RS (Range Sizes): Veľkosti blokov, kódované po dvojiciach ako pole celých čísel.

 

RTD (Range Tree Distancies): Deliace vzdialenosti v strome blokov, kódované traverzom stromu ako pole celých čísel.

 

RTT (Range Tree Types): Typy delení v strome blokov (typ určuje či je blok rozdelený horizontálne alebo vertikálne), kódované traverzom stromu ako pole celých čísel.

 

Všetky výstupné polia celých čísel sú synchronizované, teda paralelným prechodom cez všetky polia dostaneme prislúchajúce informácie o transformáciách. Napr. transformáciu i dostaneme zložením informácií z SI[i], OI[i], TRN[i], DP[2i], DP[2i+1], DF[2i], DF[2i+1], RP[2i], RP[2i+1], RS[2i], RS[2i+1]. Dvojica výstupných polí (RP, RS) obsahuje rovnaké informácie ako dvojica (RTD, RTT), ktoré sú však zapísané rôznou formou. Dvojica (RP, RS) kóduje pozície a veľkosti blokov priamo. Dvojica (RTD, RTT) ich kóduje stromom, ktorý sa vytváral pri výpočte. Pozície a veľkosti blokov môžme rekonštruovať z týchto údajov tak, že znovu vytvoríme strom blokov a vyberieme z neho listové vrcholy. Tieto dve dvojice poskytujú redundantné informácie a preto je vhodné kódovať len jednu z nich. Prvky z dvojice (RP, RS) majú približne rovnaký charakter. Naopak prvky z poľa RTD (vzdialenosti) majú iný charakter ako prvky poľa RTT (typy – čísla 0 a 1). Dvojicu (RTD, RTT) je možné efektívnejšie kódovať a preto budeme používať ďalej len ju.

 

3.4.4 Vizualizácia algoritmu

 

Vizualizácia sa zapne len pri zapnutí voľby Feedback window v konfiguračnom dialógu. Potom môžme v okne sledovať priebeh delenia a pokrývania blokov. V pozadí je zobrazený vstupný obraz. V popredí sa vykresľuje strom blokov. Zelenou farbou sa zobrazujú už pokryté bloky, červenou ešte nepokryté bloky, a žltou blok, ktorý je práve pokrývaný. Modrou farbou sa zobrazujú práve testované domény (môže ich byť aj viac v závislosti od počtu výpočtových vlákien). V záhlaví okna sa zobrazujú štatistické informácie ako počet blokov v zásobníku (RangeStack), počet pokrytých blokov (RangePool), percentuálna kompletnosť operácie (Progress) a korektnosť pokrytia (CC – Correct Cover, ak je hodnota TRUE znamená to, že pokrytie je zatiaľ korektné, ak FALSE, znamená to, že algoritmus bol donútený akceptovať pokrytie bloku, ktoré nevyhovuje nastaveným požiadavkám, napr. bolo potrebné rozdeliť blok ale kvôli jeho malej veľkosti to nebolo dovolené).

 

   

(a)                                                                        (b)

 

   

(c)                                                                        (d)

 

Obrázok 14: Vizualizácia pokrývania (a) priebeh pokrývania v móde Fidelity , (b) ukončené pokrývanie (a), (c) priebeh pokrývania v móde Size , (d) ukončené pokrývanie (c).

 

3.5 Trieda HV decoder (fraktálny dekodér)

 

Trieda HV decoder je implementáciou iteračného dekodéra pre IFS systém popísaný triedou HV encoder. Vstupom je IFS systém zakódovaný vo výstupných štruktúrach triedy HV encoder a výstupom je šedo tónový obraz blízky atraktoru vstupného IFS. Dekódovací proces prebieha v iteráciách, kedy sa aplikujú jednotlivé transformácie na predošlú iteráciu. Ako počiatočný vstup do dekodéra je použitý čierny obraz (obsahujúci len nuly). Iteračným prístupom nie je možné dosiahnuť atraktor, teda výstup je len priblíženie sa k tomuto atraktoru. Vzdialenosť výstupu a atraktora môžeme kontrolovať nastavením parametrov dekodéra.

 

 

3.5.1 Nastavenia a parametre

 

Dekódovací proces môžeme doladiť množinou nastavení dekodéra. Taktiež môžeme zapnúť vizualizáciu práce dekodéra.

 

Obrázok 15: Konfiguračný dialóg triedy HV decoder.

 

Decompression mode: Mód dekompresie. Určuje za akých podmienok sa má dekódovací proces skončiť. Voľba Max iterations () nastaví maximálny povolený počet iterácií. Po dosiahnutí tohto počtu sa proces zastaví. Voľba Max RMS error () nastaví maximálnu povolenú odchýlku od atraktora na danú hodnotu (odchýlku od atraktora môžeme z hora odhadnúť z RMS odchýlky dvoch po sebe idúcich iterácií). Proces končí pri dosiahnutí danej blízkosti k atraktoru. Voľba Quality () nastaví maximálnu povolenú RMS odchýlku od atraktora v závislosti od dynamického rozsahu kódovanej predlohy načítaného z hlavičkovej štruktúry. Hodnota 1.0 znamená najvyššiu kvalitu (žiadna odchýlka od atraktora), hodnota 0.0 znamená najnižšiu kvalitu.

 

Resolution factors: Zmena výstupného rozlíšenia. Výstupné rozlíšenie možno škálovať celočíselnými faktormi v smere x faktorom X () a v smere y faktorom Y ().

 

Post processing: Dodatočné spracovanie. Voľba povolí dodatočné vyhladenie iteračného výstupu. Vyhladenie sa aplikuje na okolie hrán blokov, kvôli zmierneniu nežiaducich blokovitých artefaktov, ktoré vznikajú pri kódovaní v nižších kvalitách.

 

Feedback window: Vizualizačné okno. Voľba zapne vizualizačné okno, v ktorom môžeme sledovať priebeh dekódovacieho procesu a vidieť jednotlivé iterácie. Zapnutá vizualizácia môže výrazne spomaliť dekódovací proces.

 

Draw ranges: Zobrazovanie blokov. Voľba povolí zobrazovanie stromu blokov vstupného IFS vo vizualizačnom okne.

 

 

 

 

3.5.2 Vstupy

 

Obrázok 16: HV decoder.

 

Vstupom dekodéra je IFS systém zakódovaný vo výstupných štruktúrach triedy HV encoder. Na rekonštrukciu IFS systému sú potrebné vstupy HDR, SI, OI, TRN, DP, DF, a jedna z dvojíc (RP,RS) , (RTD,RTT).

 

3.5.3 Vizualizácia algoritmu

 

V okne môžeme sledovať postupnosť iteračných krokov. V záhlaví okna sa zobrazujú priebežné štatistické informácie ako rozlíšenie výstupu, počet blokov (Ranges), iterácia (Iteration), RMS odchýlka od atraktora (RMS) a percentuálna kompletnosť operácie (Progress).

 

   

(a)                                                                        (b)

   

(c)                                                                        (d)

Obrázok 17: Vizualizácia iterovania, iterácia (a) 0, (b) 1, (c) 10. (d) strom blokov.

 

3.6 Kódovanie výstupov triedy HV encoder

 

3.6.1 Triedy Binary encoder a Binary decoder

 

Trieda Binary encoder analyzuje pole celých nezáporných čísel, vypočíta maximálny počet potrebných bitov M na uloženie najväčšieho prvku. Potom prvky poľa uloží do pamäťového buffra v zhustenej podobe použitím M bitov na každý prvok. Trieda Binary decoder dekóduje takto zakódované dáta späť na pole celých čísel.

 

3.6.2 Triedy Huffman encoder a Huffman decoder

 

Trieda Huffman encoder analyzuje pole celých nezáporných čísel, vytvorí frekvenčnú tabuľku znakov a na jej základe vytvorí Huffmanov kód. Potom zakóduje prvky poľa v zhustenej podobe použitím vytvorených kódových slov. Trieda umožňuje analýzu poľa na základe viac prvkových znakov (n-gramov, kedy n po sebe idúcich prvkov poľa tvorí jeden znak), ale v ďalších testoch budeme používať len jednoduché znaky (1-gramy). Trieda Huffman decoder dekóduje takto zakódované dáta späť na pole celých čísel.

 

3.7 Iné použité triedy

 

3.7.1 RGB conversion (zmena farebného modelu)

 

Trieda slúžiaca na konverziu farebných modelov z a do farebného modelu RGB. Dokáže pracovať s farebnými modelmi HSV (HSB), HLS, HSI, YUV (PAL), YUV (SECAM), YIQ, YCbCr, YCC (Kodak), CMY, CMYK, CIE XYZ, CIE Lab a CIE Luv. Vstupom je trojica šedo tónových rovín reprezentujúca RGB model a výstupom je n-tica šedo tónových rovín reprezentujúca výstupný model (alebo opačne, podľa zvoleného smeru prevodu). V ďalších testoch budeme používať hlavne model YCbCr.

 

 

 

3.7.2 Grayscale conversion (šedo tónový prevod)

 

Trieda slúži na konverziu farebného modelu RGB na šedo tónovú škálu. Poskytuje dve metódy prevodu farby na úrovne šedej: maximovú a trilineárnu kombináciu (s nastaviteľnými aj preddefinovanými koeficientmi).

 

3.7.3 2:1 reduction / expansion (redukcia rozlíšenia)

 

Trieda poskytuje redukciu rozlíšenia na polovicu. Vstupom je šedo tónový obraz. Redukciu môžme robiť v horizontálnom smere, vertikálnom smere alebo oboch (v tomto prípade sa objem vstupného obrazu zredukuje až na 1/4 pôvodnej veľkosti). Redukujeme jednoduchým priemerovaním dvojíc alebo štvoríc pixelov. Taktiež môžme robiť inverznú operáciu – expanziu rozlíšenia na dvojnásobok (v prípade oboch smerov až na štvornásobok). Expandujeme jednoduchou interpoláciou chýbajúcich hodnôt.

 

3.7.4 PSNR enumerator (merač PSNR)

 

Trieda poskytujúca štatistické informácie o podobnosti dvoch vstupných šedo tónových obrazov. Poskytuje hodnoty PSNR (Peek Signal to Noise Ratio) vychádzajúcu z dynamického rozsahu vstupných obrazov, RMS odchýlku (Root Mean Square), MD (Maximal Diference) – maximálnu odchýlku pixelov na rovnakej pozícii, AD (Average Diference) – priemernú odchýlku pixelov na rovnakej pozícii.

Výsledky a porovnanie

 

V tejto časti opíšeme a vyhodnotíme niekoľko testov.

 

Všetky časové údaje boli merané na systéme s procesorom AMD AthlonXP 2800+ (jadro Barton, 2250 MHz, 512 kB cache), a pamäťou 512 MB (DDR, 432 MHz). V tejto časti budeme pod pojmom Lena24bit rozumieť testovací farebný obraz Lena o rozmeroch 512 x 512 pixelov a farebnej hĺbke 8bit na každú farebnú zložku (v móde RGB888) a veľkosti 786 486 bajtov (v BMP formáte) a pod pojmom Lena8bit obraz Lena24bit spracovaný filtrom Grayscale conversion na šedo tónový obraz hĺbky 8bit o veľkosti 262 162 bajtov (Y zložka v modeli YCbCr).

 

4.1 Test farebného modelu YCbCr v módoch 4:4:4, 4:2:2 a 4:1:1

 

Tento test sa zameriava na farebný model YCbCr v rôznych módoch. Vstupom budú farebné roviny Y, Cb, Cr. V móde 4:4:4 nebudeme robiť žiadnu redukciu, v móde 4:2:2 zredukujeme roviny Cb a Cr na polovicu veľkosti vo vertikálnom smere, a v móde 4:1:1 zredukujeme roviny Cb a Cr na štvrtinu veľkosti (preto označenie 4:1:1, zo štvorca 2x2 pixely vyberieme štyri vzorky Y, jednu Cb a jednu Cr). Redukciu budeme robiť triedou 2:1 reduction / expansion. Prevedieme testy s profilom HVE-P1 s rôznymi úrovňami kvality. Použijeme testovací obraz Lena24bit.

 

(a)

(b)

Obrázok 21: Zapojenie filtrov pre farebný model YCbCr v módoch (a) 4:4:4 (b) 4:2:2 a 4:1:1.

 

Graf 7: Porovnanie módov YCbCr 4:4:4, 4:2:2 a 4:1:1.

 

 

 

Tabuľka 7: Výsledky pre farebný model YCbCr v módoch 4:4:4, 4:2:2 a 4:1:1.

 

Z grafu 7 vidíme, že mód 4:4:4 dosahuje vysokú vernosť, ale za cenu nízkej úrovne kompresie. Mód 4:2:2 dosahuje nižšiu vernosť, ale so značne lepšou kompresiou a mód 4:1:1 dosahuje len jemne menšiu vernosť s ešte lepšou kompresiou. Mód 4:1:1 dosahuje aj značne vyššiu rýchlosť, kvôli tomu, že spracúva menší objem dát. Z testovaných módov je teda najvýhodnejší mód 4:1:1 pretože poskytuje najlepšiu kompresiu s nepoznateľným zhoršením kvality oproti módom 4:4:4 a 4:2:2.

 

 

4.2 Dekódovanie, konvergencia a kvalita výstupu

 

V tomto teste zistíme vplyv dodatočného vyhladenia obrazu na kvalitu. Pozrieme sa aj na rýchlosť konvergencie postupnosti iteračných krokov. Vychádzať budeme z obrazu Lena8bit zakódovaného v rôznych stupňoch kvality. Vstupom pre test iteračnej postupnosti bude obraz Lena8bit zakódovaný profilom HVE-P1(99,5%).

 

Graf 4: Vplyv dodatočného vyhladenia na RMS odchýlku pre rôzne stupne kvality.

 

Z grafu 4 vidíme, že pri vyšších kompresných pomeroch vyhladenie dokáže jemne zlepšiť kvalitu obrazu, ale naopak, pri nižších, kvalitu výrazne zhoršuje.

 

Graf 5: Konvergencia postupnosti iterácií.

 

Z grafu 5 vidíme, že iteračný proces rýchlo konverguje. Rozdiel medzi 5. a 6. iteráciou už nie je pozorovateľný voľným okom. Väčšinou stačí do 10 iterácií na dostatočné priblíženie sa k atraktoru.

 

   

(a)                                                                        (b)

   

(c)                                                                        (d)

   

(e)                                                                        (f)

Obrázok 19: Postupnosť iterácií. Iterácia (a) 0, (b) 1, (c) 2, (d) 3, (e) 4, (f) 5.

 

4.3 Porovnanie so známymi formátmi

 

Porovnáme známe formáty a metódy kompresie často používané v praxi. Zo všetkých formátov sme vybrali zástupcov obrazových kompresorov so stratovou aj bezstratovou kompresiou (JPEG, JPEG2000, PNG, Targa, TIFF, GIF), ako aj zástupcov klasických dátových bezstratových kompresorov (RAR, ZIP). Vstupom bol obraz Lena24bit. Merali sme dosiahnutú kompresiu a kvalitu pre rôzne nastavenia kodérov (väčšinou to bol koeficient kvality alebo úroveň kompresie).

 

Graf 9: Porovnanie formátov.

 

Z grafu 9 je zrejmé, že najlepšiu kompresiu pri zachovaní kvality poskytuje formát JPEG2000 (založený na waveletovej transformácii), ktorý poskytuje aj možnosť bezstratovej kompresie. Ďalším v poradí je starší formát JPEG (založený na kosínusovej transformácii), ktorý je predchodcom formátu JPEG2000. Z bezstratových formátov najlepšie výsledky dosahuje JPEG2000, o trochu horšie výsledky poskytuje PNG a RAR. Niektoré formáty pri istých nastaveniach objem dát dokonca zväčšili (TIFF). Fraktálna metóda v tejto implementácii dosahuje o niečo nižšiu kvalitu obrazu pri rovnakých stupňoch kompresie v porovnaní s formátom JPEG, ku ktorému je najbližšie.