Obsah

Kapitola 1
Systém iterovaných funkcí IFS

1.1  Úvod

V této kapitole se budeme zabývat systémem iterovaných funkcí (IFS). Uvedeme zde teorii pro IFS systémy, způsob vytváření IFS kódu, generování IFS koláží a využití IFS systémů v praxi.

Hlavní pozornost bude věnována různým způsobům vytváření IFS kódu a metodám pro výpočet pravděpodobnosti jednotlivých transformací v IFS systému.

Název IFS je odvozen z anglického názvu Iterated Function System, česky lze tento název přeložit jako systém iterovaných funkcí. První publikace o IFS vydal v roce 1985 Demko a v roce 1987 Barnsley.

IFS je generativní metoda vytváření fraktálů, kterou řadíme mezi deterministické. Algoritmus pro generování IFS fraktálů však může být jak deterministický, tak nedeterministický.

1.2  Matematický popis IFS

Při definici IFS se vychází z teorie pevných bodů, která je aplikací věty o Banachově pevném bodu:

Nechť U je metrický prostor s metrikou d a f je funkce mapující:

Jestliže má funkce bod x₀ takový, že platí:

Potom platí následující věta:

Jestliže je A podmnožinou množiny U a f je taková funkce, která mapuje množinu A do sebe sama, přičemž existuje určitá konstanta d (nazývaná kontrakční faktor), pro kterou platí 0 < d < 1, potom:

Poznámka: d v našem případě znamená vzdálenost, ať už jakkoliv definovanou. Z toho vyplývá, že IFS mohou být definovány nad jakýmkoliv prostorem, který má definován pojem vzdálenosti. Například pro Euklidovu metriku platí:

Po k iteracích potom platí:

Jestliže vezmeme v úvahu tu skutečnost, že kontrakční faktor leží v rozsahu od nuly do jedné, potom limita pro k iterací, pro k blížící se k nekonečnu, je rovna nule, tedy:

Dá se dokázat věta tvrdící, že pevný bod pro danou kontrakci existuje právě jeden. Touto problematikou se zabývá takzvaný teorém pevného bodu.

1.3  Teorém pevného bodu

Teorém pevného bodu:

Jestliže je f kontrakce s kontrakčním faktorem d na A ležící v U, potom existuje právě jeden pevný bod x₀ ležící v A, přičemž

IFS je potom konečná množina kontrakcí definovaných na celém prostoru U, jedná se tedy o funkce mapující U na U (tedy na sebe samu).

Vektor konečných bodů funkcí systému IFS se nazývá atraktor. Tato množina je pro systém F invariantní. Srovnáním rovnic pro IFS transformace a rovnic pro soběpodobnou množinu, dojdeme k závěru, že aplikací IFS vznikne soběpodobná množina. Z těchto rovnic dále vyplývá, že IFS tvoří fraktál.

Určit Hausdorffovu dimenzi tohoto fraktálu lze jen při zadaných transformacích tvořících IFS. Obecně lze však říci, že pro rovinné transformace (tedy pro matice řádu 2) může mít IFS Hausdorffovu dimenzi od 0 (lze vytvořit i jednoduchý bod) do 2 (fraktál pokryje celou rovinu). Atraktor systému (jak dynamického, tak IFS) má tu vlastnost, že k sobě přitahuje iterativní postup, který určuje polohu bodu. Toto je ale logický důsledek kontrakce (jak bude dále řečeno, funkce či transformace tvořící IFS musí být kontrakcemi nebo alespoň identitami).

Je-li v systému atraktor tvořen jediným bodem, libovolný bod při iteracích nezadržitelně konverguje k tomuto atraktoru. Je-li atraktor tvořen množinou více bodů, libovolný bod se při iteracích pohybuje pouze v mezích atraktoru.

Pro IFS však platí, že počáteční bod nemusí ležet uvnitř atraktoru, po několika iteracích se do meze atraktoru dostane. Tato vlastnost podstatně odlišuje IFS od dynamických systémů, kde má volba počáteční podmínky velký význam pro další vývoj systému. Velmi pěknou ukázkou takzvané citlivosti na počáteční podmínky je systém dvou stejně hmotných hvězd, okolo kterých obíhá satelit. Hvězdy jsou v klidu (hypoteticky) a satelit se pohybuje střídavě okolo jedné a druhé. Jeho pohyb však závisí na počáteční poloze a při její nepatrné změně je závratně různý.

1.4  Typy transformací v systému iterovaných funkcí

Systém IFS je tvořen množinou transformací, které mohou mít různou podobu. Jednou z těchto transformací je inverzní vzorec pro Juliovu množinu:

Inverzní vzorec má potom tvar:

Řešením tohoto vzorce jsou vždy dvě hodnoty (dva kořeny rovnice), proto se jedná o IFS se dvěma transformacemi.

Pro běžné použití IFS však uvažujeme pouze omezenou množinu transformací. Tyto transformace označujeme pojmem afinní transformace.

Afinní transformace mají tu vlastnost, že jsou lineární, to znamená, že při aplikaci takovéto transformace na úsečku vyjde rovněž úsečka. Použití tohoto typu transformací značně zjednoduší všechny výpočty, které budeme provádět s IFS množinou.

Transformace musí splňovat ještě jednu podmínku, musí být kontrakcemi. To znamená, že po aplikaci transformace na libovolné dva body, bude nová vzdálenost bodů menší než původní vzdálenost bodů. Tato vlastnost nám mimo jiné zaručuje, že atraktorem množiny IFS nikdy nebude nekonečno.

Transformace v Euklidově prostoru definujeme takto:

kde d(X) je Euklidova metrika, X a Y jsou libovolné dva body a f(X) a f(Y) jsou transformované body.

Podle velikosti koeficientu s pak určujeme typ transformace jako:

• s < 1 : f je zmenšení (kontrakce)
• s = 1 : f je symetrie
• s > 1 : f je zvětšení (extrakce)

Z hlediska těchto vlastností není důležitá poloha transformované množiny. Za identické se například pokládají dvě stejně dlouhé úsečky, ať leží kdekoli.

K množině zobrazení S = {f₁,f₂,...f_n} náleží ještě množina pravděpodobností P = {p₁,p₂,...p_n}, p_i > 0. Pro tyto pravděpodobnosti musí platit podmínka jednotkového součtu:

Množina S je průměrně kontraktivní, pokud platí podmínka:

Platí-li předchozí vztah, potom uspořádanou dvojici

1.5  Využití IFS v praxi

Systémy iterovaných funkcí tvoří velmi důležitou skupinu lineárních deterministických fraktálů. Jejich nejdůležitější aplikací je v současné době takzvaná fraktální komprese dat.

Jak už bylo dříve řečeno, první publikace o IFS publikoval Demko v roce 1985 a Barnsley v roce 1987. V obou publikacích autoři předkládají praktický návod, jak používat IFS pro generování textur. IFS se skutečně používají pro tuto činnost a to i v běžných aplikacích, jako jsou například počítačové hry.

Později se metoda IFS ukázala jako mimořádně výhodná pro kompresi dat, jelikož jedna transformace je v tomto případě zapsána pouze pomocí osmi čísel (šest čísel na zapsání transformace a dvě čísla na změnu kontrastu a jasu). Metodu IFS využívá mimo jiné i grafický formát FIF. V porovnání s ostatními grafickými formáty dosahuje většinou lepších výsledků, nebo výsledků alespoň srovnatelných se ztrátovou metodou JPEG (komprese pomocí IFS je také ztrátová metoda). Tento grafický formát se bohužel moc nerozšířil, protože algoritmus komprese je patentovaný.

Způsob komprese v grafickém formátu typu FIF je patentovaný firmou Iteration Systems, která také dodává hardwarové akcelerátory ve formě zásuvných karet do počítačů. Dekompresní algoritmy jsou dostatečně rychlé pro programovou implementaci a jsou volně dostupné. Například pro HTML prohlížeč Netscape existuje plug-in modul pro zobrazování obrázků typu FIF. Velkou výhodou tohoto formátu je možnost zobrazení obrázku ve velkém zvětšení bez viditelné ztráty kvality.

Měl jsem možnost vyzkoušet program na kompresi pomocí IFS vyvinutý pro studijní účely (šlo o diplomovou práci jednoho italského studenta), a mohu tvrdit, že komprese je při dobře nastavených parametrech až 1:100. Obrázek o velikosti 256x256 pixelů v 256 odstínech šedi se komprimoval asi 15 minut na počítači vybaveném procesorem 486DX2 na 66Mhz se zabudovaným matematickým koprocesorem. Při hardwarové akceleraci se čas komprese pohybuje řádově v sekundách.

Třetí možností, kde lze využít IFS, je konstrukce trojdimenzionálních objektů, například stromů či rostlin, s následnou možností vizualizace. V této oblasti se využívá jak systém IFS tak i L-systémy. Každý z těchto systémů se hodí k něčemu jinému. Pomocí L-systémů lze vytvářet polygonové objekty pro možnost dalšího zpracování v CAD systému.

IFS naopak tvoří jednotlivé body, proto je vhodný například pro programy, které podporují složitější entity, jako jsou například koule či bloby (příkladem takového programu může být například raytracer POVRay). Souřadnice bodů vygenerovaných pomocí IFS je potom použita jako střed zobrazované koule.

Zde je opět vidět pěkné využití fraktálů v počítačové grafice, jelikož ruční modelování stromu v CAD systému by bylo nesmírně pracné a dosažené výsledky by většinou neodpovídaly námaze. Jednotlivé body vygenerované pomocí IFS lze také použít jako generující body pro systémy částic (particles), kde umožňují například simulaci růstu rostlin.

Obsah