Fraktálová komprese Historie První zmínky o tzv. fraktálové kompresi jsem našel kdysi v bezvadné a dodnes aktuální knížce !!“Grafické formáty“ (Branislav Sobota, Ján Milián, nakl. Kopp), kde však šlo spíše o nadšený úvod a pak příval matematických vzorců, ze kterých se mi ježily vlasy na hlavě (a to mám matematiku rád). Dodatečně bylo řečeno, že fraktálová komprese může obrázky zredukovat násobně lépe, než třeba JPEG, a navíc přináší nezávislost na rozlišení, tedy po zvětšení obrázku nedojde k "pixelaci" a ten bude stále ostrý. Plný zaujetí jsem pročesával internet hrubého času snad celý rok (možná i víc) a za tu dobu našel jen několik prací, několik prográmků a velké množství různých fragmentů. Asi 90% všech zdrojů neustále opakovalo totéž o vysokém kompresním poměru a nekonečném rozlišení, takže pro mne tato kompresní metoda ještě přibrala na tajemnosti. Frustrován jsem našel skutečně jen fragmenty s několika většinou ne moc dobře funkční prográmky, přičemž jediný držitel patentu na fraktálovou kompresi, společnost Iterated Systems, přestala jako taková existovat (polovina zdrojů se odkazovala na stránku www.iterated.com. Bohužel, domovská stránka společnosti už je nenávratně pryč). Nicméně jsem se dostal ke knize Yuvala Fishera: "Fractal Image Compression, Theory and Application", kde bylo vše velmi podrobně probráno a dokonce byl přiložen i zdrojový kód určité implementace fraktálové komprese. Ten byl napsán v jazyce Vannila C pro Unixovou stanici a tak mne čekaly tři drtivé týdny transformace do jazyka C# (!). Po nastudování a pochopení nejdůležitějších kapitol a optimalizovaního kódu (některé pasáže jsem četl snad stokrát, než mi došlo, jak se věci mají) jsem rád, že vám můžu představit fraktálovou kompresi obrazu v českém materiálu a se zaručeně funkčním softwarovým podkladem. Zdrojový kód původních programů enc.c a dec.c od Y. Fishera bylo naštěstí možné jakkoliv šířit i modifikovat bez svolení autora. Intuitivně zodpovím jeden velmi důležitý dotaz: "Proč se zabývat fraktálovou kompresí, když jde sice o zajímavou, ale pro praktickou aplikaci ne zrovna populární metodu?" Když pominu jiná možná využití této metody (porovnávání obrázků, zvětšování bez změny rozlišení,pokročilé odstraňování šumu, odstraňování JPEG artefaktů...), pokládá fraktálová komprese jakýsi základ pro pozdější využití (tedy ne jako samostatná metoda, ale jako součást či nástroj něčeho komplexnějšího). Dnes se v multimédiích uplatňují algoritmy založené na transformacích podle bázových funkcí, ať už jsou to sinové a kosinové transformace (ve standardu JPEG), KarhuenLoéveho t. nebo obecně waveletová (vlnková) transformace (ve standardu JPEG 2000). Všechny tyto metody odstraňují redundanci z obrázku v ryzí podstatě stejným způsobem (aproximací bázovými funkcemi). Jak se zvyšuje kompresní poměr, roste ztráta a u všech zmíněných transformačních algoritmů dochází k rozostřování obrázku. U fraktálové komprese k tomuto defektu nedochází, ovšem ztrácejí se jiné detaily (a některé nepříznivé fraktální artefakty zase místo toho vznikají). Fraktálová komprese odebírá z obrázku druh redundance, kterému se říká soběpodobnost, kdežto transformační metody prostě odebírají nedůležité transformační koeficienty a zjednodušují tak výstupní signál. Tedy, pokud odebereme z obrázku oba typy redundance, jeden založený na frekvenční analýze, druhý na soběpodobnosti, můžeme dosáhnout nikoli kompromisu, ale fúze výhod a tedy lepších výsledků, než u obou metod samostatně. Abychom však pochopili koncepci hybridního algoritmu spojujícího obě metody, musíme pochopit oba přístupy zvlášť. Hybridní algoritmy typu DCT-fraktálová komprese nebo wavelet-fraktálová komprese byly skutečně vypracovány - novinkou je například algoritmus FZW (Fractal Zerotree Wavelet), vlastně původní waveletový koder EZW (Embedded Zerotree Wavelet) vylepšený o fraktálové kódování, jehož autoři zmiňují další možnost takového vylepšení vlnkového kóderu SPIHT (Set Paritioning In Hierarchical Trees, který používá standard JPEG 2000) a tím samotný SPIHT de-facto překonat. Úvahy na toto téma už však musejí být podloženy poměrně rozsáhlými znalostmi jak v počítačové grafice, tak v teorii informace, proto nakousneme jen jedno chutné sousto tohoto obřího koláče. Ačkoliv se fraktálová komprese občas zmiňuje jako "relativně nová metoda", je její zrod vzdálen asi tak stejně, jako zavedení standardu JPEG. Koncem osmdesátých let, konkrétně v roce 1987 publikoval matematik Michael Barnsley své výsledky, kterých dosáhl jednou z implementací fraktálové komprese obrazu. Dosáhl velmi zajímavých výsledků - tuším, že se u některých obrázků dostal až na kompresní poměr 10 000 : 1. Ale Barnsleyho implementace měla několik háčků. Jednak to byla neuvěřitelná časová náročnost jeho metody vycházející z potřeby masivního výpočetního výkonu (ve výše zmíněném případě ho zajišťoval jeden z novějších superpočítačů Cray), kterou trpí ve větší či měnší míře všechny fraktální komprimační metody, ale především nutnost přítomnosti člověka (dokonce kvalifikovaného člověka - proto tento problém dostal název: teorém graduovaného studenta). Jinými slovy bylo potřeba na fraktálovou kompresi každého obrázku zavolat graduovaného studenta, který problému rozuměl - v teorému se dokonce hovoří o zavřených dveřích a studentově několikahodinové práci, asi to má něco do sebe. Tyto problémy tedy činili fraktálovou kompresi nepoužitelnou. V čem byl problém? Každá kompresní metoda je založena na snížení redundance (nadbytečnosti) v datech. Neztrátové metody hledají například delší sekvence stejných prvků, nebo statisticky redukují informaci pro popis frekventovaných prvků, za cenu delšího popisu těch méně častých. Co se týče ztrátové komprimace obrazu, jsou metody fraktálové komprese a JPEG v principu odlišné. JPEG vidí zbytečnou informaci ve funkcích vysokých frekvencí, které mají valný význam pouze na ostrých hranách obrázku, ale jinak jsou v digitální fotografii pro člověka prakticky neviditelné. Fraktálová
komprese je založena na zmíněné soběpodobnosti, což je velmi významná vlastnost přírodních scén. JPEG komprese je rovněž založena na algoritmu, který pracuje v blocích, takže lépe vyjadřuje vztahy mezi nejbližšími pixely (resp. pixely v rámci). Na druhou stranu se u fraktálové komprese počítá s různě velkými bloky, které mohou být třebas na opačných stranách obrázku (odborně se to nazývá odstraňování korelací na velkou vzdálenost). Fraktály a fraktání geometrie Fraktálová komprese se zakládá na fraktálech, a ty jsou definovány matematickým oborem fraktální geometrie. Jejím duchovním otcem je Benoît Mandelbrot, který také zavedl slovo fraktál (vycházel z latinského fractus = zlomit). Fraktály byly v podstatě známé už v antickém řecku, ale pokusy o jejich matematický popis se objevily až během první světové války. Z této doby také pochází matematik Julia a jeho Juliovy množiny. Mandelbrot (mimochodem Juliův žák) se pokoušel tyto množiny sjednodnit v jeden komplexní celek, což se mu podařilo - tento útvar se nazývá Mandelbrotova množina a je to asi nejznámější fraktál:
Mandelbrotova množina Víckrát jsem zmínil termín množina - fraktální geometrie se jako ostatní geometrie zabývá množinami bodů v prostoru. Útvary z takových bodů jsou však klasické Eukleidovské geometrii cizí. Eukleidovská geometrie je ta, kterou se učíme na základní a střední škole. Ta popisuje - stručně řečeno - útvary, které jsme schopni nakreslit pomocí pravítka (trojúhelníku s ryskou) a kružítka. Mandelbrotovi šlo však o to najít vhodnou geometrii pro popis přírody (zabývá se např. distribucí galaxií nebo modelováním zemských terénů). Kulaté a hranaté útvary z klasické geometrie najdete v přírodě spíše vzácněji (krystaly, planety...), ovšem popsat nějak jednoduše Euklidovskou geometrií třeba strom nebo mrak, je vyloučené. Útvary fraktální geometrie - fraktály, se často přírodním objektům velice přibližují. V Euklidovské geometrii má každý útvar tzv. topologickou dimenzi. Bod má topologickou dimenzi nula, přímka jedna, čtverec či kruh dvě, krychle nebo koule tři a tak dále (ano, na sestrojení hyperkrychle si ve čtyřrozměrném prostoru s pravítkem trojúhelníkem vystačíte) - topologická dimenze je tedy nezáporné celé číslo. Fraktální geometrie zavádí ještě takzvanou Haussdorfovu-Bessicovitchovu dimenzi, stručně dimenzi fraktální. Jejím odvozením se nebudu blíže zabývat, ale pokud je pro určitý útvar hodnota této dimenze, která může být dokonce iracionální číslo (!), větší než hodnota dimenze topologické, nazývá se tento útvar fraktál. Může jít třeba o uzavřenou křivku nápadně připomínající pobřeží ostrova. Uzavřená křivka v Euklidovské geometrii objímá nějaký útvar s konečným obsahem. Tento útvar má rovněž konečný obvod (délka křivky). Fraktální křivka je sice uzavřená, ale přitom nekonečně dlouhá. Vzniklý útvar má tedy konečný obsah, ale nekonečný obvod, což je zdánlivě paradoxní. Je to dáno podstatou fraktálů - jejich nekonečnou složitostí. Pokud si vezmeme metrové pravítko a obejdeme s ním pobřeží ostrova, dostaneme nějakou hodnotu. Jestliže uděláme totéž s půlmetrovým pravítkem, naměříme logicky délku o něco větší, protože už musíme obcházet menší balvany, které jsme předtím přešli jedním krokem. S postupným zmenšováním pravítka (zvyšováním přesnosti) se dozvídáme, že délka pobřeží v závislosti na délce pravítka se dá popsat exponenciální funkcí, která má limitu v nekonečnu. K tomuto závěru bychom bezpochyb došli u skutečného pobřeží (ano, pohybujeme se v teoretickém světě, sám nepovažuji nekonečna za v realitě existující). Fraktál je nekonečně složitý, ačkoliv jeho popis je konečný (většinou rovnice nebo soustava rovnic či jako transformační matice, jak se dozvíme později). Často je tento popis docela jednoduchý - Mandelbrotova množina je definována krátkou rovnicí o třech neznámých: - rovnice Složitost vyplívá ze zmíněné soběpodobnosti (self-simliarity), což je podle mého názoru způsob, jakým se přírodě daří vytvářet fascinující útvary jako stromy a kapradiny, ačkoliv k jejich popisu stačí jediná molekula (DNA). Systémy iterovaných funkcí
Místo toho, abychom tedy strom popisovali jako množinu bodů v prostoru, je snažší vytvořit kořen z něhož vyraší dvě až tři větve, přičemž se tento postup rašení aplikuje na každou vzniknuvší větev. Schopnost fraktální geometrie dobře popsat přírodní útvary inspirovala Barnsleyho ke zpracování digitálního obrazu. Nejspíš si řekl, že když lze jednoduchým popisem dostat složitý obrazec, proč pro složité obrazce nenajít nějakým algoritmem jednoduchý popis (slovem jednoduchý se myslí informačně kratší popis, než jaký je třeba na surová rastrová data)? Touto otázkou lze uvést tzv. inverzní problém, který je dodnes nevyřešen. Nabízí se však částečná řešení, která lze realizovat i na běžném PC. Pro nalezení odpovědi je nejdříve třeba si vymezit vhodnou třídu fraktálů, kterými se bude vstupní obrázek aproximovat. Fraktály lze na počítači generovat několika způsoby osvědčenými způsoby, z nichž nejvýznamnějším pro kompresi obrazu jsou IFS (Iterated Function Systems - systémy iterovaných funkcí). IFS je soubor parametrů, které definují afinní (lineární) kontraktivni transformace a jejich množina pak určuje výsledný fraktál. Ve dvou větách jsem teď zavedl několik pojmů, které je třeba přiblížit. Nejlepší příklad asi uvedl Yuval Fischer, který generování fraktálů iterativní (postupnou) metodou přirovnal ke kopírce. Dejme tomu, že máme speciální kopírku, která obrázek na papíře zmenší, zkopíruje na určitá místa (aplikuje transformace) na čistý papír a ten vytiskne. To, co na vyištěném papíře uvidíme je výsledek první iterace - prvního průchodu. Když papír vyšlý z kopírky dáme znovu kopírovat, dostaneme pak výsledek druhé iterace. Po provedení nekonečného množství iterací konverguje obraz na papíře do výsledného atraktoru a pak se už nemění. Atraktor je kýžený fraktál, kterého jsme chtěli dosáhnout. V praxi nemáme čas dělat nekonečně mnoho kopií – vlastně stačí tolik, abychom si už přibývajících detailů nepovšimli, což je překvapivě brzy (po několika iteracích), protože zobrazovací zařízení a naše oči mají konečné rozlišení.
Sierpinského trojúhelník (prvních šest iterací) Na obrázcích je prvních šest iterací při konstruování fraktálu "Sierpinského trojúhelník(y)". Jediné, čím je tento fraktál popsán, jsou tři transformace. Celý obrázek se zmenší na poloviční velikost a jeho tři kopie se umístí do pyramidy, tak jak je to ve druhé iteraci. Tentýž postup se aplikuje opakovaně. V praxi by se opakoval tak dlouho, až by byly trojúhelníčky tak malé, že by je reprezentovaly smotné pixely. Potom už nemá smysl provádět další iterace, protože se obrázek nemění. Z hlediska kopírky je fraktálová komprese přesný opak. Pro daný obrázek máme najít množinu transformací tak, aby kopírka těmito informacemi vygenerovala atraktor co nejpodobnější originálu. Obrázek zakódovaný fraktálovou kompresí nese pouze informaci o transformacích, takže vůbec nezáleží na tom, jaký úvodní obrázek zvolíme (tj. jak potištěný papír do kopírky dáme). V prvním příkladě, kdy je vstupním obrázkem trojúhelník to vypadá, že z něj jen postupně vytěsňujeme prostor. Může však být použit jakýkoliv útvar:
Prvních šest iterací Sierpinského trojúhelníka s pozměněným vstupním obrázkem Další příklad dokazuje, že aplikací stejných pravidel se dostáváme ke stejnému atraktoru, ačkoliv vstupní obrázek je libovolný. V obou příkladech by byly zapotřebí ještě tak dvě nebo tři iterace, abychom se dostali na obvyklé rozlišení obrazovky. Obrázky by byly z tohoto hlediska shodné. Aby bylo zajištěno, že po aplikaci transformací bude obrázek konvergovat do chtěného atraktoru (všechny body budou aplikací transformací putovat do jednoho, tzv. pevného bodu), musí být transformace kontraktivní (zmenšující). Jinými slovy: Kterékoliv dva body se po aplikaci jedné transformace přiblíží k sobě. To znamená, že větší bloky budeme transformovat pouze na menší, přičemž si můžeme dovolit také jejich přetočení (rotation), zkosení (skew) a samozřejmě přesun (translation). V prvních příkladech byly použity tři kontraktivní transformace, vždy šlo pouze o zmenšení (scale transform) a přesun. Popis IFS Pro každý bod při aplikaci afinní transformace platí tato rovnice:
x a b x e W = + , y c d y f což je vlastně totéž, jako bychom napsali:
Wx ( x ) = ax + by + e
Wy ( y ) = cx + dy + f Takto vypadá IFS ve zjednodušené formě (pro černobílé obrázky). Můžeme se pokusit o fraktálovou kompresi obrázku "Sierpinského trojúhelník", tedy naopak se zadaným obrázkem zjistit IFS. Vycházíme-li z tzv. Kolážovacího teorému (Collage theorem), můžeme zjednodušeně říct, že pokud najdeme transformaci W pro obrázek B tak, že B a W(B) jsou velmi podobné, pak atraktor W bude také velmi podobný obrázku B. Fraktálová komprese spočívá ve vhodném rozložení obrázku na nepřekrývající se bloky, tzn. jejich sjednocení je celý obrázek. Pokud je každý z těchto bloků podobný celému obrázku, pak kombinace získaných transformací je IFS originálu. Jinými slovy, zakódování obrázku do IFS spočívá v nalezení kontraktivních afinních transformací w1, w2, ... wn, takže původní obrázek B je sjednocením n podobrázků. Přímá metoda vyhledání IFS je prakticky použitelná pouze jako příklad, protože její realizace vyžaduje právě ono nalezení optimální "koláže", tedy způsobu jak rozložit obrázek tak, aby jeho části byly co nejvíce podobné jemu samotnému. Pokud bychom dokázali inverzní problém vyřešit, zjistili bychom u Sierpinského trojúhelníka, že se skládá ze tří menších trojúhelníků. Jsou to nepřekrývající se bloky a jejich sjednocení dává dohromady celý obrázek. Zároveň je každý malý trojúhelník transformací obrázku celého (jinými slovy: Sierpinského trojúhelník je útvar složený ze tří Sierpinského trojúhelníků poskládaných do pyramidy). Pokud můžeme najít tyto transformace, IFS je souborem transformací pro Sierpinského trojúhelník. Začneme vrcholem trojúhelníka. Známe obecnou rovnici afinní transformace, takže víme, že je třeba odhledat šest neznámých: a, b, c, d, e a f. Nejprve je potřeba najít odpovídající body původního Sierpinského trojúhelníka a vrcholu tohoto trojúhelníka. Jakmile je to jasné z následujícího obrázku, víme že bod (x1, y1) je transformován na (x2', y2') a obdobně pro zbylé dva body (obrázek vle Odvození IFS Sierpinského trojúhelníka
V pravém obrázku jsou souřadnice relativní vůči prvnímu bodu (x1, y1). K získání potřebných hodnot tedy vede těchto šest rovnic:
ax1 + by1 + e = x1' ax2 + by2 + e = x2' ax3 + by3 + e = x3' cx1 + dy1 + f = y1' cx2 + dy2 + f = y2' cx3 + dy3 + f = y3' Za neznámé x,y dosadíme souřadnice významných bodů a dopočítáme výsledné transformace:
x 0.5 0 x 0.5 w1 = + y 0 0.5 y 0.5 x 0.5 0 x 0 w2 = + y 0 0.5 y 0 x 0.5 0 x 1 w3 = + y 0 0.5 y 0 Chaos Game (Hra chaosu) Zda jsou získané údaje o transformacích skutečně korektní, si lze ověřit jedním ze způsobů generování IFS fraktálů. Je to takzvaná hra chaosu (chaos game), lze se také setkak s názvem algoritmus náhodné procházky. Jde o velmi jednoduchý algoritmus. Máme-li n afinních transformací w1, w2, ..., wn. Tyto transformace mají přiřazeny pravděpodobnosti p1, p2, ..., pn, přičemž platí:
p1 + p2 + ... + pn = 1 pi > 0 i = 1, 2,..., n Můžeme tedy přiřadit každé transformaci stejnou pravděpodobnost 1/n (optimální rozložení pravděpodobností je pro ty které fraktály různé). Takto vypadá algoritmus hry chaosu: 1. 2. 3. 4. 5. 6.
Nechť x = 0; y = 0. Vyber k, které bude jedním z čísel 1,2,...,n. Aplikuj transfromaci wk na bod (x, y) pro získání nového bodu (xnew, ynew). Nechť x = xnew; y = ynew. Nakresli bod (x, y). Pokud není dosažen předvolený počet iterací, vrať se ke kroku 2.
Čím více iterací je provedeno, tím lépe je fraktál prokreslen. Tady se ale jedná o průchody typu: nakresli pixel, kdežto v praxi se iterací myslí progresivní prokreslení celého obrázku (aplikace transformací). Aby byl fraktál trochu viditelný, je potřeba velké množství bodů. V uvedeném algoritmu volíme náhodné transformace a ty pak používáme k "odpíchnutí" starého bodu na novou pozici, která se opět stává zdrojovou lokací. Tímto způsobem jsem vytvořil jednu z varitant Slpleenwortovy kapradiny (známé fraktály mívají mnoho názvů, takže se můžeme setkat třeba s názvem: "fraktální kapradina" nebo dokonce "Barnsleyho tráva"): + IFS
varianta Spleenwortovy kapradiny a její IFS Pro vygenerování bylo použito 1 000 000 bodů, což není problém realizovat na výkonném PC (na Intel Celeronu 1.33 GHz trvalo generování jen asi 2 sekundy při použití GDI+). Další způsob generování IFS fraktálů je za pomoci polygonu. Tento postup nezaručuje, že bude vytvořen fraktál (z hlediska zadaných parametrů), ale výsledky jsou mnohdy zajímavé. Tento postup popsal Barnsley v roce 1988 pod názvem Chaos Game. Potřeba jsou dva parametry: n a r. Malé n udává počet stran mnohoúhelníka (nikde není řečeno, že tento polygon musí být rovnostranný, ale měl by být vypuklý - v případě jemného porušení vznikne stejný fraktál, pouze je deformovaný) a r udává zlomek vzálenosti mezi "cestujícím bodem" a pevnými body (vrcholy polygonu). Když chceme například vygenerovat Sierpinského trojúhelník, bude n = 3 a r = 1/2. Rozestavíme tři body tak jak chceme mít trojúhelník postavený a cestující bod dáme kamkoliv dovnitř; zatím pomyslného trojúhelníka. Iterace se realizuje tak, že zvolíme náhodně jeden z pevných bodů a nový bod se nakreslí někam na spojnici cestujícího bodu a zvoleného pevného bodu. Kam, to určuje parametr r. V případě Sierpinského trojúhelníka to bude do středu této úsečky.
Zleva doprava a shora dolů - 10 000, 20 000, 40 000, 80 000 a 160 000 bodů Sierpinského trojúhelníka Aplikace na obrázky Jak bylo řečeno, fraktál Sierpinského trojúhelník se konstruuje pomocí tří transformací:
Afinní transformace pro generování fraktálu Sierpinského trojúhelník
Když generujeme fraktál iterativním postupem, aplikujeme transformaci W na obrázek f. První iterace je tedy W(f), druhá W(W(f)), třetí W(W(W(f))) a tak dále. U fraktálové komprese se transformace provádí z větších bloků do menších - říkáme že větší bloky mapujeme:
Transformace aplikované na obrázek Větší bloky se mohou překrývat, menší nikoliv, což budeme probírat v dalším díle při implementaci prvního (primitivního) koderu. Pro každý menší blok se hledá co možná nejpodobnější větší blok (aby se zajistila kontraktivita). Takové nálezy soběpodobnosti mohou vypadat následovně:
Soběpodobné oblasti v obrázku Lenna Stejně jako při generování fraktálů můžeme použít opravdu jakýkoliv vstupní obrázek a na ten aplikovat iterace. Výstupní kvalita obrázku závisí především na míře podobnosti mezi malými a velkými bloky. Tím, že se kompresní metoda zakládá na fraktálech, dědí zakódované obrázky taky zajímavou vlastnost, tedy lze je dekódovat na libovolném rozlišení bez ztráty detailu. Fraktálové obrázky mají stejně daleko od rastrové i vektorové grafiky (i když mají v podstatě blíže k vektorům), zavádí tedy úplně nové odvětví počítačové grafiky s mnoha praktickými aplikacemi. Primitivní kóder na bázi PIFS Vlastnosti fraktálové komprimace Komprese obrazu pomocí IFS je výpočetně náročný úkol, naopak dekódování je velmi rychlé. Jde tedy o silně asymetrický proces. Snad tento důvod neumožnil větší rozšíření této kompresní metody (je však třeba říci, že byly představeny rychlé metody, například institut v anglickém Bathu představil tzv. BFT - Bath Fractal Transform, zajímavé práce o aplikaci FK v multimédiích vypracoval John Kominek a dobře optimalizovaný algoritmus fungoval v programu Fractal Imager od Iterated Systems, pokoušející se prorazit před standardem JPEG). Druhým důvodem by mohla být nejistá kvalita obrazu. Metodou fraktálové komprese je vhodnější kódovat spíše přírodní scenérie, než interiéry. Ačkoliv je většina digitálních fotografií právě z exteriéru, dávají výrobci přednost standardu JPEG, který je v obou zmíněných ohledech flexibilnější. Žádný z existujících grafických formátů, kromě nestandardizovaného formátu FIF (Fractal Image Format od Iterated Systems) a STN (STiNG od Altamiry, nyní vlastněné spol. LizardTech) neposkytuje nezávislost na rozlišení. JPEG obrázek můžeme dekódovat pouze ve stejném rozlišení, v jakém byl kódován. Pokud ho zvětšíme, budě trpět pixelací (tj. pixely jako čtvercové body se roztáhnou na skutečně viditelné čtverce) nebo po vyhlazení interpolací bude rozmazaný. Obrázek kódovaný pomocí jedné z metod fraktálové komprese je definován množinou transformací a je tedy podle definice fraktál. To ale znamená, že ho lze donekonečna zvětšovat a nikdy neztratíme detaily. Ve skutečnosti fraktálová komprese skutečně přináší nezávislost na rozlišení, ale detaily získané při zvětšení jsou umělé - dopočítané. Podobně jako se u JPEG ztráta projevuje vlněním u hran a blokovitostí, trpí obrázky kódované fraktálovou kompresí různým typem blokových artefaktů (podle použité metody) a vykreslováním neexistujících detailů. S použitím postprocessingových vyhlazovacích algoritmů lze ovšem i tento nešvar napravit a přínosem jsou pak ostré, téměř spojité hrany skoro
jako ve vektorovém obrázku. Tuto vlastnost fraktálové komprese využila spol. Altamira ve svém poměrně dost drahém softwaru Genuine Fractals pro zvětšování obrázků. PIFS - Partitioned Iterated Function Systems Původní Barnsleyho metoda hledání IFS pro celý obrázek byla náročná a vyžadovala asistenci operátora. Barnsleyho žák, Arnaud Jacquin, však přišel s metodou sice o něco slabší co do kompresního poměru, zato však zcela soběstačnou. Její podtstatou je vyhledávat IFS transformace pouze pro části obrázku. Všechny následující metody patří pod tuto obecnější vrstvu, ať už dělí obrázek na stejné, nebo různě velké a různě tvarované bloky. Hledaná transformace obrázku je tedy sjednocením transformací částí obrázku: n
W = ∪ wi ( f ) i =1
Nespornou skutečností zůstává, že fraktálová komprese je ztrátová metoda, což lze pro daný obrázek f aproximovaný transformací W zapsat jako: n
f ≈ W ( f ) = ∪ wi ( f ) i =1
V nejprimitivnější verzi fraktálového kóderu je obrázek rozdělen na malé nepřekrývající se bloky, tzv. ranges (oblastní bloky), které mají většinou velikost 8x8 pixelů. V někerých pracech se fraktálová komprese připodobňuje k tzv. vektorové kvantizaci, což je blízce příbuzná metoda; proto se range bloky občas nazývají vektory. Jejich sjednocením je celý obrázek f. Kromě range bloků pracuje fraktální kóder ještě s předem definovanou množinou doménových bloků, které by se měli (ale nemusejí) více či méně překrývat. Doménové bloky (domains - domény) jsou větší než range bloky, většinou mají 16x16 pixelů, což dává kontraktivní faktor 2 (protože doménové bloky jsou dvakrát větší). Fraktální kóder hledá pro každý oblastní blok co možná nejbližší doménový blok. Slovem nejbližší se však nemyslí číselná vzdálenost mezi souřadnicemi range a domain bloku, ale vzdálenost mezi hodnotami pixelů, tedy podobnost obou bloků. Úkolem fraktálního kóderu je potom najít množinu transformací, kterými namapujeme doménové bloky do oblastních. Kontraktivní faktor musí být větší než jedna, což je zajištěno dvojnásobnou velikostí domén oproti oblastním blokům. Každý bod obrázku má tedy krom své polohy dané souřadnicemi x,y také úroveň světlosti, kterou můžeme interpretovat hodnotou na ose z. Do původní IFS se tedy musí započítat třetí souřadnice, takže v konečném efektu budou z-ovou souřadnici každého bodu transformovat dvě hodnoty. Je to jasový posun (offset - oi) a škálovací faktor (scale - si) pro úpravu kontrastu.
x ai wi y = ci z 0
bi di 0
0 x ei 0 y + fi si z oi
Tento popis je pouze symbolický, existuje řada lepších modelů, kterými se zde nebudeme zabývat. Pro porovnání doménového a oblastního bloku musejí být oba bloky stejně velké, čehož se docílí zmenšením doménového bloku na polovinu. Toto zmenšení lze implementovat dvěma jednoduchými způsoby. Jedním je podvzorkování (subsampling), kdy stačí číst jen jednu hodnotu a ostatních si nevšímat. Tato metoda je rychlá, ale ne tak kvalitní jako určení půměru hodnot čtyř pixelů pro získání hodnoty pixelu ve zmenšeném bloku. Tato metoda se nazývá průměrování (averaging). Je o něco pomalejší, protože je potřeba provádět sčítání a dělení, avšak přináší kvalitnější výsledky (řešení problému s opakovaným průměrováním bude vyloženo při implementaci prvního "vážného" fraktálního kóderu). Když je doménový blok zmenšený, porovná se s oblastním blokem. Rozdílnost těchto bloků určuje střední kvadratická odchylka (RMSE - Root Mean Square Error). Hodnoty pixelů v doméně jsou a, v oblastním bloku b. Pro známé hodnoty posunů jasu a kontrastu (získány metodou nejmenších čtverců) dostaneme minimální odchylku RMS.
RMSE =
n
∑ ( sa + o − b ) i =1
i
i
2
n
s=
n
n
n∑ ai bi − ∑ ai ∑ bi i =1
i =1
i =1
n∑ ai2 − ∑ ai i =1 i =1 n
n
n
o=
2
n
∑ bi − s∑ ai i =1
i =1
n
Platí potom vztah pro výpočet RMSE: n n n n 2 2 b + s s a − 2 a b + 2 o a + o no − 2 bi ∑ ∑ ∑ ∑ i i i i ∑ i i =1 i =1 i =1 i =1 RMSE = i =1 n n
Může nastat zvláštní případ, kdy: 2
n n∑ a − ∑ ai = 0 i =1 i =1 n
2 i
Tento případ je třeba odchytit, jinak není vztah pro jasový posun definován (dělení nulou). Hodnoty s, o jsou v tomto případě:
s=0 n
o=
∑b i =1
i
n
S těmito informacemi jsme již schopni vypočítat odchylku RMS pro každý pár oblast-doména. Prohlédávání všech domén, tedy metoda těžké hrubé síly (heavy brute force) je pro běžné PC časově náročné (někdy se tato metoda nazývá také trefně: Naivní algoritmus), proto se obvykle prohlédávají jen některé domény. Jednou z možností je nastavit určitý práh chyby RMS. Program bude pro každý range blok hledat tak dlouho, dokud nenarazí na doménu s dostatečně malou chybou RMS. Další možností je prohledávat domény ve spirále, nebo v rámci nějaké mřížky. První testovací algoritmy jsou postaveny tak, že zkoušejí určitý počet náhodných domén. Z daného počtu pokusů je vybrán ten, který přinesl nejmenší chybu RMS. Pro lepší výsledky hledání se na doménové bloky zmenšené na velikost oblastních bloků aplikují různé transformace sestávající s překlápění a rotací. Obvykle se počítá s osmi transformacemi při každém porovnání: 1: 2: 3: 4: 5: 6: 7: 8:
identita (žádná transformace) otočení kolem střední vertikální osy bloku otočení kolem střední horizontální osy bloku otočení kolem první diagonály bloku otočení kolem druhé diagonály bloku otočení kolem středu bloku o 90° proti směru hodinových ručiček otočení kolem středu bloku o 180° proti směru hodinových ručiček otočení kolem středu bloku o 90° po směru hodinových ručiček
Dekódování Narozdíl od kódování je aproximace původního obrázku z transformací velmi rychlé. Pro každý oblastní blok je nalezena vhodná transformace, takže při velikosti obrázku 256x256 pixelů a velikosti oblastního bloku 8x8 pixelů máme celkem 1024 transformací. Ty jsou popsány souřadnicemi domény a dvěma hodnotami pro barevné transformace. Jedna iterace se provádí v rámci jedné bitmapy, přičemž nezáleží na tom, jaká data už bitmapa obsahuje. Obecně nejrychlejší konvergence se dosahuje použitím čistě šedé bitmapy (z hlediska metody nejmenších čtverců má šedý pixel nejmenší vzdálenost od všech ostatních barev pixelů), také je možné použít třeba zvětšeninu náhledového obrázku, pokud je dostupný. Procházíme oblastní bloky stejně jako při kódování, ale známe už příslušné transformace, takže stačí načíst doménový blok na známých souřadnicích, zmenšit ho a
aplikovat barevné transformace. To se dělá tak, že hodnotu každého pixelu (intenzitu) vynásobíme škálovacím faktorem s a přičteme jasový posun o. Existují i rychlejší metody, než mapovat jednotlivé doménové bloky do oblastních, které budou uvedeny později, pro jednoduchou implementaci stačí použít toto schéma. Při každé iteraci se zvýší rozlišení dekódovaného obrázku. Po prvním průchodu by měli mít podle naší představy nejdetailnější bloky velikost bloků oblastních, tedy 8x8 pixelů, ovšem doménové bloky se překrývají, takže při dekódování obrázku budou v nižších částech obrázku detailnější oblasti než ve vyšších částech (neplatí to, pokud používáme navíc jeden pomocný obrázek). Zmenšený doménový blok se stane součástí jiného doménového bloku, který se při jiné transformaci zase mapuje, čímž se zvyšuje detail. Nejméně detailní bloky v prvním řádku oblastních bloků mají velikost právě 8x8, při druhém průchodu můžeme počítat s velikostí 4x4 a tak dále, takže pro dekódování obrázku na stejném rozlišení, v jakém byl kódován, je ovykle třeba 4 až 5 iterací, ovšem vhodnější je provádět průchody tak dlouho, až nebude zaznamenána v obrázku žádná změna. Dekódování na vyšším nebo nižším rozlišení znamená jiný počet potřebných průchodů; čím vyšší rozlišení, tím více. Pokud chceme obrázek dekódovat na dvojnásobném rozlišení. Musíme rovněž zdvojnásobit velikost oblastních a doménových bloků. Kontraktivní faktor tedy zůstavá konstantní. Výsledky
Originální obrázek (Lenna), velikost 256x256 pixelů
Náhodná volba domény při 128 pokusech, první 4 iterace
Náhodné volby domény při 1000 pokusech, první 4 iterace
Lehká hrubá síla (doménové bloky se nepřekrývají => 256 porovnání pro každý obl. blok), prvních 5 iterací Fraktální artefakty Protože obrázek zakódovaný fraktálově a je sám podle definice fraktál, lze ho stejně jako jiné fraktály zvětšovat donekonečna bez ztráty detailu. To je na fraktálovém kódování velmi zajímavá vlastnost, ale detaily, které uvidíme při zvětšení nejsou rozhodně těmi detaily, které bychom hledali. Pokud stotisíckrát zvětšíme tvář Lenny na testovacím obrázku, neuvidíme atomy jejího obličeje, ale fraktální, jinak také dopočítané detaily. Pro příklad lze použít malý obrázek o velikosti 16x16 pixelů, který zvětšíme 2x (32x32 bodů), 4x (64x64), 8x (128x128) a 16x (256x256). Velikost oblastních bloků je 2x2, doménové bloky mají velikost 4x4. Po získání transformačních informací můžeme obrázek dekódovat na různých rozlišeních, ale ačkoliv se vždy prokreslí do detailů, nejsou tyto detaily příliš přínosné.
fraktální zoom dodávající fiktivní detaily Tento neduch lze však celkem úspěšně vyhladit pomocí postprocessingových metod. Většina zlomů a diskontinuit, na které je oko velmi citlivé, se projevuje na rozhraních jednotlivých range bloků, proto se vyhlazování realizuje metodou váženého průměru (weighted average), ke které se ještě vrátím. Tím vyhladíme nejnepříjemnější fraktální artefakty a obrázek si přitom může zachovat relativně ostré hrany, které by při použití jiných filtrů pro zvětšování zůstaly rozmazané. Můžeme se podívat na srovnání různých filtrů pro převzorkování (resampling) obrázku do jiného rozlišení.
prosté zvětšení (Box filtr), zvětšení s kubickou interpolací
ShortCut PhotoZoom 1.095, Genuine Fractals PrintPro 3.5, PIFS Menší obrázek obsahuje méně informace a pokud ho zvětšíme, musíme pro zostření nějakou informaci dodat. Při jednoduché interpolaci považujeme pixely za body a vzniklé mezery mezi nimi při zvětšení prokreslíme barevnými přechody. Tím se ovšem pořád nezbavíme "čtveratého" dojmu. Jiný filtr zase obrázek dostatečně vyhladí, aby nebyly vidět žádné čtverečky, ale výsledkem je celkem rozostřený obraz. Jak je vidět, pěkných výsledků bylo dosaženo bikubickým filtrem. Předposlední ukázka je vytvořena za pomoci komerčního softwaru Genuine Fractals PrintPro (pro ukázku verze 3.5 Trial). Spol. LizardTech vyvýjející tento software nabízí skvělé obrázky i při zvětšení na 500% oproti originálu. Vhodný zvětšovací algoritmus by tedy měl umět dopočítat detaily v podobě ostrých přechodů a textur, přitom by však měl být schopný odfiltrovat nežádoucí artefakty. Genuine Fractals tento problém řeší vyhlazením fraktálu přes waveletovou (vlnkovou) transformaci. Poslední obrázek je upravený výsledek Partitioned IFS algorimtu. Úprava spočívala v rozmazání obrázku generovaného transformacemi pomocí gaussovského rozostření s poloměrem 4 (oproti waveletům primitivní, ale ilustrativní způsob). Tento obrázek se ještě prolnul s bikubicky zvětšenou miniaturou v poměru 7:3. Pokročilý kóder na bázi QPIFS (Quadtree Partitioned Iterated Function Systems) Výhodou tohoto algoritmu oproti "naivní" metodě je vyšší rychlost a efektivita. Zrychlení je docíleno pomocí optimalizací, které by bylo možné aplikovat i na původní metodu pracující ve stejně velkých (uniform) blocích, avšak při nižším prahu tolerance má tato metoda jasně navrch. Některé části obrázku (většinou homogenní oblasti nebo delší barevné přechody) je vhodné uzavřít do větších bloků a takto ušetřené místo využít na detailní oblasti, které budou v menších blocích. Vysvětlení, proč malé bloky přinášejí vyšší přesnost může být velmi jednoduché. Je mnohem snazší najít doménový blok 4x4 pixely velký, který je dostatečně podobný oblastnímu bloku o velikosti 2x2 pixely, než najít takovou shodu pro dva velké bloky (více pixelů - menší pravděpodobnost shody).
Dělení obrázku kvadrantovým stromem V kvadrantovém stromu mohou z každého uzlu vycházet čtyři hrany. Kořenem tohoto stromu je obrázek sám a větvení se interpretuje dělením částí obrázku na čtyři stejné části (kvadranty). U stromu si můžeme navolit například minimální a maximální hloubku prohledávání, resp. minimální a maximální velikost range bloků. Začíná se u kořene stromu, tedy u celého obrázku, který postupně dělíme, až se dostaneme na maximální povolenou velikost bloku (resp. minimální hloubku stromu). Celý obrázek nemůžeme považovat za oblastní blok, protože k němu neexistuje žádný takový doménový blok, aby výsledné zobrazení bylo kontraktivní. Jinými slovy je celý obrázek ta největší dostupná doména. Minimálně je tedy potřeba provést alespoň jedno dělení. Každý ze čtyř vzniklých bloků podrobíme porovnávání s doménami. V těch blocích, kde jsme nenašli žádnou doménu s odchylkou splňující zadaný toleranční práh (RMS tolerance), se provede rozdělení a algoritmus může pokračovat rekurzivně. Klasifikace domén Podle pravidel z klasifikace domén můžeme každý doménový blok zařadit do jedné ze tří základních tříd podle uspořádání světlosti kvadrantů a jedné z 24 podtříd podle variance. Existují i jiné typy klasifikačních schémat, kterými se však nebudeme zabývat. Kvůli optimalizaci výpočtu je potřeba zavést klasifikaci doménových bloků, které se budou pro ten který oblastní blok prohledávat. Je totiž důležité najít shody pro největší doménové bloky. Yuval Fisher ve své práci rozděluje doménové knihovny na tři skupiny: D1, D2 a D3 (pro kódování se používá jedna z nich). První má zastoupení všech typů domén přibližně roven. Druhá doménová knihovna obsahuje spíše více velkých domén a méně menších. A konečně třetí knihovna má více menších, a méně větších domén. Čtvercové doménové bloky jsou umístěny tak, že levý horní roh každé domény je umístěn na mřížce definované paremtrem l (lattice), který určuje rozteč mřížky pro jednotlivé skupiny domén: D1 - má mřížku s pevnou roztečí, která je rovna l D2 - má mřížku, jejíž rozteč je rovna velikosti domény dělené l. Proto je zde více menších domén než větších D3 - má mřížku určenou jako výše, jen s opačným vztahem rozteč-velikost. Největší domény mají rozteč mřížky rovnu velikosti nejmenší domény dělené l a naopak. Nejnáročnější částí algoritmu je porovnávání oblastních a doménových bloků. Během kódování klasifikujeme oblastní blok a ten porovnáváme pouze s doménami ve stejné (nebo podobné) skupině. To vede ke značné redukci nutných srovnání, rovněž co se týče započítání rotací a překlápění doménového bloku, jak bude vysvětleno níže. V konečném efektu se počítají pouze dvě upořádání pixelů domény. Čtvercový podobrázek je nejprve rozdělen na čtyři části v pořadí: levá horní, pravá horní, levá spodní, pravá spodní. Pro každý kvadrant spočítáme hodnoty úměrné průměru (A - average) a rozdílu (V - variance). Jestliže hodnoty pixelů v kvadrantu i jsou
r1i , r2i ,..., rni , pak průměr a rozdíl vypočítáme jako n
Ai = ∑ rji j =1
Vi = ∑ ( rji ) − Ai2 n
2
j =1
Čtvercový pod-obrázek je vždy možné orientovat tak, aby světlost kvadrantů byla rozložena jedné z těchto tří pozic:
Světlost kvadrantu znamená průměrnou hodnotu pixelů v něm. Zařazení do základní třídy potom odvodíme logickými vztahy: Hlavní třída 1:
A1 ≥ A2 ≥ A3 ≥ A4 Hlavní třída 2:
A1 ≥ A2 ≥ A4 ≥ A3 Hlavní třída 3:
A1 ≥ A4 ≥ A2 ≥ A3 Každá z těchto 3 hlavních tříd sestává z 24 podtříd, které znamenají 24 uspořádání pro Vi:
Zařazení čtvercového podobrázku do podtřídy podle variance vyplyne ze vztahů:
Vi1 ≥ Vi2 ≥ Vi3 ≥ Vi4
∪ i = {1, 2,3, 4} ∧ ∩ i = ∅ ⇒ N
i
= 4! = 24
Celkem tedy máme 3x24 = 72 tříd. Když dojde k tomu, že hodnota si je záporná, uspořádání tříd výše se mění. Tedy, každá doména je klasifikována ve dvou orientacích, jedna pro kladné si a druhá pro záporné si. Z hlediska lineární regrese metodou nejmenších čtverců je odvození hodnot s, o vlastně odvozením koeficientů lineární funkce popisující přímku, která nejlépe prolíná (fituje) světlosti pixelů v bloku. Jelikož jsou tyto hodnoty pixelů nezáporné (0-255), většinou získáme rovněž kladné parametry s, o. Může však nastat případ, kdy jsou hodnoty pixelů uspořádány sestupně, takže škálovací faktor s bude záporný (offset o musí být kladný, aby alespoň část přímky ležela nad osou) a změní se sklon přímky. V našem algoritmu se potom porovnání realizuje invertováním světlosti kvadrantů (nejsvětlejší se stane nejtmavším a obdobně). Vytvoření pomocných bitmap Další "trik", který vede ke znásobení rychlosti kódování je vytvoření čtyř pomocných bitmap, které dovolí přeskočit opakované průměrování hodnot pixelů. Jedná se o krok, kdy zmenšujeme doménu tak, aby velikostně odpovídala oblastnímu bloku pro porovnání. Existují dva efektivní způsoby, jak zmenšit doménový blok v poměru 1:2. První je rychlý, ale méně kvalitní, nazývá se podvzorkování (subsampling). Na každou čtveřici pixelů doménového bloku připadne jeden pixel oblastního bloku. Při podvzorkování z této čtveřice vybereme právě jeden pixel a ostatních si nevšímáme. Tento jeden pixel je označen za bod ve zmenšené doméně. Podvzorkování je však nejnekvalitnější způsob zmenšování, protože při polovičním zmenšení bere ohled jen na 1:4 obrázku, může tedy vynechat důležité detaily. Na ilustraci jsou vzaty z originálu (obrázek vlevo) čtverečky velikosti 2x2 pixely (čtveřice), přičemž je každý ze čtyř pixelů přiřazen jiné zmenšené bitmapě. Všechny tyto čtyři bitmapy jsou zmenšeny stejnou metodou (podvzorkování), jen s tím rozdílem, že byl použit jiný pixel na jejich sestavení z původní čtveřice.
Rozdíly ve výřezech z těchto bitmap v detailu jsou na úrovni ztráty, která vznikne při použití podvzorkování.
Druhá a kvalitnější metoda pro zmenšování je průměrování (averaging). U fraktálového kódování je porovnávání oblastních a doménových bloků nejopakovanější část algoritmu, při které je třeba domény neustále zmenšovat na úroveň oblastních bloků. U metody podvzorkování je výhodné, že lze data číst přímo z původního obrázku, avšak za cenu určité ztráty. Pokud chceme dosáhnout vyšší kvality kódování, je už procesor odsouzen počítat průměry hodnot každé čtveřice pixelů, což se časově velmi protáhne. Protože se však oblastní bloky porovnávají dokola se stejnými doménami (platí to samozřejmě i v případě klasifikace domén, jen je jich na každý oblastní blok o něco méně), průměrují se opakovaně stejné čtveřice pixelů, což je plýtvání výkonem. Pro kódovaný obrázek přitom stačí vytvořit čtyři pomocné bitmapy, každá o poloviční velikosti, přičemž bude možné průměrné hodnoty číst přímo z nich. Tím dosáhneme prakticky stejného výkonu, jako u podvzorkování, při zvýšení kvality kódování. Zprvu se může zdát, že stačí průměrováním zmenšit pouze originální bitmapu a z ní vše vyčíst. Pokud bychom se však tohoto úkonu dopustili, zase bychom přišli o 3/4 potřebných informací obrázku, jako při podvzorkování. Čtvercové bloky o velikosti 2x2 pixely z originálního, které zmenšujeme na jeden pixel, se nepřekrývají, takže jejich souřadnice jsou [0,0], [2,0], [4,0], [16, 24] ... ... Pokud má doménový blok sudé souřadnice bude každý bod její zmenšeniny obsažen v pomocné bitmapě. Pokud bude mít doménový blok liché souřadnice, bude potřeba udělat průměr čtverečku, který má v originální bitmapě souřadnice např. [1, 1] a ten už v pomocné zmenšené bitmapě započítán není. Ve skutečnosti máme celkem čtyři pomocné bitmapy protože počítáme se čtyřmi kombinacemi souřadnic (sudá - sudá, lichá - sudá, sudá - lichá, lichá - lichá). Opět se může naskytnou myšlenka, proč i tak nepoužít jen jednu pomocnou bitmapu, která by obsahovala průměry všech čtverečků - sudých i lichých. Tato bitmapa by měla oba rozměry o jedna menší (pixely pravého a spodního okraje není s čím zprůměrovat, avšak pro kóder nejsou samy o sobě zapotřebí) a skutečně nic nebrání použít jen jednu. V kódovacím algoritmu bychom však museli dopočítávat souřadnice toho kterého bodu, podle sudosti nebo lichosti souřadnic domény. To s sebou samozřejmě přináší vyšší výpočetní náročnost. Podle souřadnic domény tedy vybereme jednu ze čtyř pomocných bitmap a pixely zmenšeniny vyčeteme bez problémů odsud. Níže vidíme stejný detail z každé bitmapy. Důležité je, že hodnota každého pixelu je "poznamenána" hodnotami pixelů z okolních tří pozic, takže jsou rozdíly postupné, nikoliv nárazové.
x Program a jeho parametry Původní programy Enc a Dec se ovládaly z příkazového řádku, což je pro testování trochu nepohodlné. Vytvořil jsem proto jednoduché GUI, kde nastavíte parametry a spustíte kódování. To probíhá kvůli vysoké výpočetní náročnosti jako separátní vlákno na pozadí a v jeho průběhu vidí uživatel dělení obrázku stejně jako procentuální stav, takže si snadno udělá obrázek o náročnosti a zbývajícím čase. Přesto nemůžeme očekávat, že když bude
prvních 20% trvat 2 sekundy, zbytek potrvá 5x tolik. Čas kódování se nedá přesně odhadnout a závisí na nastavených parametrech a místní komplexitě obrázku. V levé části spodního panelu nastavujeme parametry komprese. Nepsal jsem už dummy proofing, tedy hezky česky: blbuvzdornost, proto pozor na zadávání nesmyslných parametrů. Nejdůležitějším parametrem je "RMS tolerance", která určuje práh pro porovnávání: čím vyšší hodnota, tím nižší kvalita a vyšší komprese. Další kolonky označené "Minimum tree depth" a "Maximum tree depth" značí, v jakém intervalu se má koder nořit do stromu. Minimální hloubka může nabývat hodnot 1-8, stejnětak maximální hloubka - avšak musí platit: maximum > minimum. Hloubka 1 znamená oblastní blok o velikosti 256x256, 2 potom 128x128 a tak dále až do hloubky 8 (bloky 2x2). Menší už nemají smysl, protože by fraktálová interpretace překračovala velikost původního obrázku, byla by porušena kontraktivita a tak by nedošlo ke kompresi (ba naopak). Tři typy doménových knihoven (0, 1, 2) jsem vysvětlil výše, doporučuji použít typ 0, protože vyvažuje velké a malé bloky. Parametr rozteče mřížky (lattice spacing) se dává 1, 2 nebo 4, jinak nemá smysl dávat více, pro vyšší kvalitu je lepší spíše zvýšit hodnotu tolerančního prahu. Údaje maximální (absolutní) hodnoty scaling factoru (škálovacího faktoru, krerý může být i záporný) stejně tak počet přidělených bitů pro tento faktor a offset (jasový posun) mají význam při kvantifikaci údajů na konkrétní počet bitů a případný výstup do souboru. Tyto hodnoty byly zjištěny po mnoha pokusech jako optimální. Rozvinovací nabídka s prohledáváním tříd umožňuje procházet při srovnáních range-domain i domény jiných tříd, než do jakých patří oblastní blok. Při volbě "fullclass search" prohledáme i tři další třídy (odvozené podle světlosti kvadrantů), při "subclass search" potom 24 tříd (odvozených podle variance). Můžeme zvolit i procházení všech tříd (both), ale potom ztrácí klasifikace na významu a algoritmus je velmi pomalý (stejně jako při volbě nevhodné doménové knihovny). Dvě zaškrtávací políčka umožňují nastavit možnost akceptování záporných škálovacích faktorů (mírně pomalejší algoritmus - vyšší kvalita) a průběžného zobrazování dělení obrázku. Po dokončení kódování (které spustíte tlačítkem Encode a přerušíte tlačítkem Stop) můžete provést iteraci klepnutím na tlačítko Iterate. Po několika iteracích zkonverguje obrázek vpravo do výsledného atraktoru, který se podle stanovených parametrů více či méně podobá originálu. Tlačítkem Clear attractor vymažete pravý obrázek, avšak transformační data zůstávájí v paměti, proto můžete testovat iterace i na jiném iniciálním obrázku (kontextové menu vám po klepnutí pravým tlačítkem na ten který obrázek nabídne několik možností, k dispozici jsou 2 originální obrázky a 4 jako výchozí pro aplikaci dekomprese). Tlačítko Set defaults nastaví všechny parametry na výchozí hodnoty. Tlačítko Postprocess provádí vyhlazení atraktoru od nepěkných blokových artefaktů, tlačítkem Save uložíte zkomprimovaný obrázek a tlačítkem Zoom přepínáte rozlišení (de facto velikost) rekonstruovaného obrázku podle faktorů 1, 2, 3, 4 a tak dokola. Pokud program pracuje na pozadí, ovládací prvky jsou vysvícené, tak poznáte, že pracuje. Výstup původního programu je do souboru, moje modifikace ukládá transformace do stromové struktury z tříd (class místo datového typu struct jsem nepoužil jen tak z plezíru, kód se struct nevím proč nebylo možné načíst v samostatné assembly pro fraktálový kodek, na kterém pracuji). Dekodér se nachází ve stejném souboru, jako kóder. Ten převádí stromovou strukturu do jednorozměrného pole (opět ArrayList) a transformace tak jak jsou v poli aplikuje na dekódovaný obrázek (dekódování tedy nemusí být rekurzivní). "Zploštění" (flatten) stromové struktury se provádí po každé iteraci pouze z titulu testovacího programu, jinak stačí metodu FlattenTransforms() provést jen jednou a metodu ApplyTransforms() potom tolikrát, kolik iterací si přejeme. Výsledky Výhodou použití zmíněných optimalizací (ty, které nebyly zmíněny, hovoří samy za sebe v testovacím programu) je možné kódovat i větší obrázky, ačkoliv se testovací program omezuje na velikost 512x512 bodů.
Originální obrázek Lenna (512x512 pixelů) a jeho rozdělení při toleranci e = 4.0
dekódování obrázku Lenna (shora dolů) po 1, 2, 3, 4, 5 a 10 iteracích, původní obrázek byla černá plocha
rozdělení obrázku Lenna při toleranci e = 8.0
Dekódování obrázku Lenna Fraktální zoom S optimalizovanou metodou fraktálové komprese můžeme dosáhnout kvalitní rekonstrukce obrázku i na čtyřnásobném rozlišení, kdy při prostém zvětšení dojde k markantní pixelaci a při jiné než fraktální interpolaci zase k rozostření obrázku. Další zvětšování už odhalí zmíněné fraktální artefakty, ovšem můžeme si pomoci proložením obrázku interpolovanou zvětšeninou (nejlepší výsledky pro zvětšování má bikubický filtr, pro zmenšování filtr Lanczos). Proložení dvou obrázků, tedy průměrování jejich odpovídajících pixelů (tentokrát stačí prostý aritmetický průměr) je lepší než rozmazání čistě fraktální zvětšeniny, protože se v decentnější formě zachovají chtěné ostré partie. V ukázkách je použito čistě fraktální dekódování.
dekódování části obrázku Lenna při různém rozlišení, zleva: 64x64, 128x128, 256x256 pixelů
