Obsah

Kapitola 1
Generování IFS koláže

1.1  Přehled způsobů generování IFS koláže

Poté, co máme zadané všechny transformace a vypočítané pravděpodobnosti jednotlivých transformací, můžeme vygenerovat výslednou IFS koláž. Pro generování IFS koláže se používají takzvané generativní metody. Tyto metody jsou většinou jednoduché pro implementaci.

Generativních metod pro vytváření IFS koláží je velké množství. My si zde popíšeme čtyři základní metody, které lze dále modifikovat a rozvíjet:

• Náhodná procházka
• Deterministický algoritmus
• Upravený algoritmus pro náhodnou procházku
• Algoritmus pro generování minima pixelů

Takové množství metod bylo vytvořeno proto, že výsledná IFS koláž je fraktálem. Je tedy tvořena nekonečným množstvím bodů. Z toho vyplývá, že pro zobrazení celého fraktálu je zapotřebí nekonečné množství iterací, které budou spočítány v nekonečném čase.

Proto, aby byl čas počítání IFS fraktálu konečný, je zapotřebí provést určitá zjednodušení. Proto se negeneruje nekonečné množství bodů, ale většinou pevně zadaný počet bodů (například 100 000). Výsledkem je tedy přibližný tvar IFS fraktálu.

Výstupní zařízení, na jakém se bude výsledný IFS fraktál generovat, má určitou rozlišovací schopnost. To znamená, že prostor, do kterého se má IFS fraktál mapovat není spojitý, ale diskrétní. Tato skutečnost je použita u některých generativních metod, které zohledňují konečnou rozlišovací schopnost výstupních zařízení. Takové metody tedy pracují s konečnou velikostí pixelu a snaží se negenerovat ty body fraktálu, které již jsou nakresleny (do jednoho pixelu lze mapovat nekonečné množství bodů z určitého intervalu).

Zbývá nám tedy vhodně vybrat takové body, které co nejlépe reprezentují fraktál. Musíme vzít v úvahu dva protichůdné faktory. Jedním z nich je, aby byl čas pro generování fraktálu co nejkratší (musí se tedy minimalizovat počet generovaných bodů). Druhým faktorem je co nejlepší reprezentace výsledného IFS fraktálu (tedy generovat co největší počet bodů).

Pro provedení jedné transformace je zapotřebí provést čtyři násobení a šest sečítání. To není mnoho, ale musíme si uvědomit, že pro jeden obrázek se musí provést přibližně sto tisíc těchto transformací. Takové množství operací může na dnešních počítačích trvat i desítky sekund. Není tedy možné takovým způsobem generovat například videosekvence, kde je potřeba zobrazit minimálně deset snímků za sekundu. Pro tyto aplikace jsou vytvořeny speciální metody.

1.2  Náhodná procházka

Algoritmus náhodné procházky (anglicky random walk) patří mezi nejjednodušší algoritmy pro generování IFS koláží. Jeho výhodou je jednoduchost a malá paměťová náročnost. Mezi jeho nevýhody patří nutnost generování velkého množství bodů pro reprezentaci fraktálu. Některé části fraktálu se generují vícekrát, zatímco některé jen jednou.

Generování IFS fraktálu se nastartuje tak, že se zvolí náhodný bod v rovině. Poloha počátečního bodu nemá na výslednou koláž žádný větší vliv, nemusí tedy nutně ležet uvnitř atraktoru IFS. Poté náhodně vybereme nějakou transformaci W_i. Při výběru transformace musíme přihlédnout k tomu, aby počet použití dané transformace odpovídal její pravděpodobnosti, jinak se bude výsledná koláž generovat neúměrně dlouho. Poté co máme vybranou nějakou transformaci, aplikujeme ji na daný bod. Souřadnice tohoto bodu se změní (bod se transformuje). Na tento nový bod potom iterativně aplikujeme další náhodně vybranou transformaci.

Takto pokračujeme tak dlouho, dokud nedosáhneme zadaného maximálního počtu iterací.

Jelikož první bod nemusí nutně ležet v atraktoru IFS, je nutné několik prvních iterací počátečního bodu nezobrazovat, protože první iterované body neleží v atraktoru IFS. Z teorie IFS systémů, kterou jsme uvedli v předchozích kapitolách, vyplývá, že se systém automaticky dostane po několika iteracích do atraktoru IFS, z něhož se již nemůže dostat.

Při generování IFS koláže tímto algoritmem vidíme, že se obrázek jakoby vynořuje z mlhy. Kvalitu výsledného obrázku lze ovlivnit zadáním maximálního počtu iterací, které se mají provést. Malý počet iterací způsobuje, že je obrázek složený z malého počtu bodů a tím pádem je hůře viditelný. Příliš velký počet iterací naopak způsobuje dlouhou dobu generování výsledné IFS koláže.

Pro první náhled na IFS koláž vystačíme s 1 000 iteracemi, ale pro generování obrázků, které se mají tisknout ve vysokém rozlišení, je zapotřebí 100 000 až 1 000 000 iterací. Doba generování se u tohoto počtu iterací pohybuje řádově v desítkách sekund.

Počátečních iterací (tedy iterací, které se nevykreslují) stačí zadat několik desítek. Po tomto počtu iterací se bod nachází uvnitř atraktoru IFS.

Počáteční bod se většinou volí tak, aby ležel v počátku. Jak již víme, na jeho poloze výsledný tvar IFS koláže nezávisí.

1.2.1  Algoritmus náhodné procházky

1. nastav počáteční bod x₀ na souřadnice [0,0]
2. for i=1 to (maximální počet iterací) do
3. náhodně vygeneruj číslo p ležící mezi nulou a jedničkou
4. podle tohoto čísla najdi transformaci W_i
5. aplikuj transformaci W_i na bod x_i a vypočti nový bod x_i+1
6. bod x_i+1 bude novým výchozím bodem pro další transformaci
7. if je dosažen zadaný počet počátečních iterací then vykresli bod x_i
8. endfor {opakuj body 2-4 do chvíle, kdy se dosáhne maximálního počtu iterací}
9. end.

1.3  Deterministický algoritmus

Deterministický algoritmus pro generování IFS koláže (anglicky Deterministic Iteration Algorithm - DIA) pracuje na odlišném principu než algoritmus pro náhodnou procházku, který jsme si popsali v předchozí podkapitole.

Zatímco se v algoritmu pro náhodnou procházku iteruje vždy jen jeden bod, v deterministickém algoritmu se pro iteraci použije množina bodů. Také se již nemusí počítat s pravděpodobnostmi jednotlivých transformací, poněvadž se na množinu bodů aplikují vždy všechny transformace.

Z toho vyplývá i název tohoto algoritmu. Zatímco předchozí algoritmus používal náhodná čísla a byl tedy stochastický, tento algoritmus používá pro výpočet všechny transformace najednou. To mimo jiné znamená, že se nemusí nějakým způsobem vybírat určitá transformace.

Generování se nastartuje tak, že se náhodně zvolí několik bodů v rovině. Poloha těchto bodů nemá (stejně jako v předchozím algoritmu) vliv na tvar výsledného fraktálu. Na tuto množinu bodů postupně aplikujeme všechny transformace, které tvoří IFS systém. Všechny body, které vzniknou při těchto transformacích, tvoří množinu pro další iteraci.

1.3.1  Zápis deterministického algoritmu pro generování IFS koláží

Stejně jako v minulém případě, i zde použijeme zápis algoritmu pomocí pseudokódu:

1. vyber inicializační množinu bodů X₀
2. for i=1 to (maximální počet iterací) do
3. for k=1 to N do
4. pro každý bod x Î X_i-1 do
5. X_i = X_i Čw_k(x)
6. endfor k
7. endfor i
8. end.

V prvním bodě náhodně vybereme množinu bodů. Bod může být jeden, protože po první aplikaci transformací se tato množina zvětší.

Druhý bod představuje smyčku, která se provede tolikrát, kolik je zadaných iterací. Zde poznamenejme, že počet iterací v tomto algoritmu může být menší než počet iterací v předchozím algoritmu. Zatímco v předchozím algoritmu se s každou iterací vygeneroval pouze jeden bod, v tomto algoritmu se bodů vygeneruje více a jejich počet dokonce exponenciálně stoupá.

V třetím bodu je smyčka, která se provede pro každou transformaci, které tvoří IFS systém. Tato smyčka, na rozdíl od předchozího algoritmu, je deterministická, proto je celý algoritmus deterministický.

Ve čtvrtém a pátém bodu se na každý bod z množiny aplikují všechny transformace. Nové body se vloží do nové množiny, zatímco stará množina se zruší.

Tento algoritmus generuje výsledný fraktál rychleji, protože pro vykreslení potřebuje méně iterací než je tomu u předchozího algoritmu. Velkou nevýhodou je spotřeba paměti. Pro každou iteraci se generuje nová množina bodů. Tato množina se s každou iterací exponenciálně zvětšuje.

Jestliže má IFS systém pouze dvě transformace a začínáme s jedním počátečním bodem, budou potom v množině po první iteraci body dva, po druhé iteraci body čtyři atd. Pro větší počet transformací je samozřejmě tento růst ještě prudčí.

Tato vlastnost se musí obejít buď tím, že nastavíme relativně malý počet iterací, nebo omezíme velikost množiny X_i.

1.4  Úprava algoritmu pro náhodnou procházku

Tato metoda v sobě spojuje některé výhody algoritmu pro náhodnou procházku a deterministického algoritmu. Algoritmus pracuje tak, že v každé iteraci se iterovaný bod podrobí všem transformacím, ale jen jedna z nich se použije pro další iteraci.

Výhodou tohoto algoritmu je stejná paměťová náročnost, jakou má algoritmus pro náhodnou procházku a poměrně rychlé generování výsledného fraktálu.

Tuto metodu lze také s výhodou použít v případě, že potřebujeme generovat pouze výřez z celého fraktálu.

1.4.1  Zápis upraveného algoritmu pro náhodnou procházku

Zápis algoritmu pomocí pseudokódu:

1. vyber počáteční bod x₀
2. for i=1 to (maximální počet iterací) do
3. for k=1 to N do
4. pro bod x_i do
5. x_i+1 = w_k(x_i)
6. endfor k
7. pro další iteraci náhodně vyber bod z množiny transformovaných bodů
7. endfor i
8. end.

Algoritmus je v mnohém podobný klasickému algoritmu pro náhodnou procházku. Jediná změna spočívá v tom, že se v každé iteraci provedou všechny transformace, takže se výsledný fraktál generuje mnohem rychleji.

Při výběru transformace pro další iteraci je vhodné zohlednit velikost kontrakce všech transformací.

Z toho, že se pro další iteraci vybere pouze jedna transformace, vyplývá, že tento algoritmus není deterministický.

1.5  Algortimus pro generování minima pixelů

Problém všech předchozích metod pro generování IFS koláže spočívá v tom, že se tyto algoritmy snaží konstruovat (zobrazit) výsledný fraktál přesně, zatímco je potřeba zobrazit jen určitou reprezentativní část fraktálu.

Tato část fraktálu je konečná (to znamená, že je tvořena konečným počtem bodů), proto může být zobrazena v konečném čase. Přesně to dělá algoritmus pro generování minima pixelů (anglicky The Minimal Plotting Algorithm - MPA). Efektivita tohoto algoritmu spočívá v tom, že pracuje přímo s pixely a ne s body.

Bod je nekonečně malý a může mít libovolné souřadnice. To znamená, že mezi dvěma body leží nekonečné množství dalších bodů, které mají odlišné souřadnice. Naproti tomu má pixel určitou velikost a leží v diskrétním prostoru. Mezi dvěma pixely leží pouze konečné množství pixelů.

Tento rozdíl mezi matematickým bodem a pixelem je použit ve více grafických algoritmech, například v algoritmu pro odstranění aliasingu. Použijeme ho i v tomto algoritmu.

Pro reprezentaci fraktálu použijeme bitmapu, kam se bude výsledný fraktál zobrazovat. Jako pomocný datový typ bude sloužit fronta, ve které budou uloženy adresy jednotlivých pixelů. V tomto algoritmu je ukládání adres pixelů do fronty méně paměťově náročné, než ukládání do zásobníku.

1.5.1  Zápis algoritmu pro generování minima pixelů v IFS fraktálu

Zápis tohoto algoritmu bude proveden v pseudokódu, který je podobný programovacímu jazyku Pascal:

1. najdi pevné body pro všechny transformace w_k
2. vykresli pixely, které korespondují s těmito body
3. proveď inicializaci fronty s pomocí adres těchto pixelů
4. repeat
5. vezmi adresu pixelu ze začátku fronty
6. for k=1 to N do
7. proveď transformaci w_k(p)
8. tento bod zaokrouhli tak, aby korespondoval s jedním pixelem
9. if bod nebyl nikdy vykreslen then
10.vykresli tento bod
11.přidej adresu tohoto bodu na konec fronty
12.end if
13.end for k
14.until fronta není prázdná
15.end.

Velkou výhodou tohoto algoritmu je, že se každý pixel na obrazovce vykreslí pouze jednou. Také se dosáhlo toho, že pro jednou počítaný bod se nebudou provádět žádné další transformace. Z výše uvedeného vyplývá, že algoritmus v konečné době skončí, neboť i v nejhorším případě se provede vygenerování pouze všech pixelů na obrazovce. Má-li tedy obrazovka rozlišení 800x600 pixelů, provede se maximálně 800*600=480000 iterací.

Proto je tento algoritmus nejefektivnější, to znamená, že generuje výsledný fraktál s minimálním počtem bodů. Také paměťové nároky nejsou velké. Vedle bitmapy potřebujeme navíc pouze frontu s adresami pixelů. Jedno místo ve frontě bude mít velikost 4 byte, což není mnoho.

První nevýhodou tohoto algoritmu je nutnost pro každý počítaný pixel hledat jeho protějšek ve frontě. To zapříčiní zkomplikování výpočtů a tím i prodloužení celkové doby generování celého fraktálu.

Druhou nevýhodou je, že tento algoritmus je určen pouze pro generování celého fraktálu. Chceme-li generovat pouze výřez z fraktálu, stává se tento algoritmus neefektivní, protože bude počítat i body ležící mimo obrazovku.

Tuto nevýhodu má i deterministický algoritmus, kde také není možné efektivně generovat výřez z fraktálu.

1.6  Závěrečné porovnání algoritmů pro generování IFS koláže

Algoritmy pro generování IFS koláže můžeme porovnávat podle více hledisek. Můžeme například uvažovat čas potřebný pro vygenerování IFS koláže, nebo spotřebu paměti při běhu programu.

Z hlediska paměťových nároků je nejvýhodnější algoritmus pro náhodnou procházku, nebo jeho upravená verze. Tyto algoritmy pracují přímo z výslednou bitmapou a jediná další potřebná paměťová struktura je poloha iterovaného bodu.

Uspořádání algoritmů podle spotřeby paměti:

• Algoritmus pro náhodnou procházku a jeho upravená verze (nejmenší nároky)
• Algoritmus pro generování minima pixelů
• Deterministický algoritmus (největší paměťové nároky)

Z hlediska rychlosti je nejvýhodnější algoritmus pro vykreslení minima pixelů. Tento algoritmus má také tu výhodu, že vždy skončí v konečném čase. Proto se používá i pro kódování videa v případech, kdy je zadána nízká propustnost datového kanálu. I při nízkých bitových rychlostech se s tímto algoritmem dosahuje poměrně kvalitního videa, které stačí například pro provozování videotelefonů.

Uspořádání algoritmů podle rychlosti:

• Algoritmus pro generování minima pixelů (nejrychlejší)
• Deterministický algoritmus
• Upravený algoritmus pro náhodnou procházku
• Algoritmus pro náhodnou procházku (nejpomalejší)

Výběr nejvhodnější metody tedy není jednoznačný, neboť závisí na aplikaci, kde se budou IFS koláže používat.

Obsah