Hlavní navigace

Systémy iterovaných funkcí a algoritmus náhodné procházky

30. 5. 2006
Doba čtení: 12 minut

Sdílet

V dnešním díle budeme pokračovat v popisu systémů iterovaných funkcí. Ukážeme si způsob vytvoření základního obrazce spolu s pokrytím tohoto obrazce jeho menšími kopiemi. Pak si popíšeme nejjednodušší algoritmus určený pro vykreslování IFS systémů. Jedná se o algoritmus náhodné procházky, někdy také nazývaný chaotická hra.

Obsah

1. Systémy iterovaných funkcí z hlediska matematiky
2. Aplikace transformací v systému iterovaných funkcí
3. Vytvoření základního objektu s jeho pokrytím menšími kopiemi
4. Výpočet transformačních matic
5. Algoritmus náhodné procházky (RWA)
6. Vykreslení IFS systému pomocí algoritmu náhodné procházky – demonstrační příklad
7. Obsah dalšího pokračování tohoto seriálu

1. Systémy iterovaných funkcí z hlediska matematiky

V dalším textu se budeme zabývat pouze těmi systémy iterovaných funkcí IFS, kde jsou mapování typu A → A na množině U (A je v tomto případě podmnožinou množiny U) vyjádřena pomocí lineárních či nelineárních transformací. Každá transformace bude zapsána symbolem φi, kde i značí index (pořadí) transformace. Množina všech transformací bude označena symbolem Φ, tj. Φ={φ1, φ2, … φn }. Systém iterovaných funkcí IFS je, jak si podrobněji řekneme v navazujících kapitolách, tvořen množinou transformací Φ a jejich pravděpodobností Π={π1, π2, … πn }. Použité transformace mohou mít různou podobu. Jedním z příkladů těchto transformací je například inverzní vzorec, jež vychází z iteračního vztahu pro Juliovu množinu (z a c jsou hodnoty ležící v komplexní rovině C):

P(z)=z2+c

Inverzní vzorec má potom tvar:

P-1(z)=(z-c)-2

Řešením předchozí rovnice pro zadané z a c vzniknou díky odmocnině komplexních čísel vždy dvě hodnoty (dva kořeny rovnice), proto se po rozpisu vzorce na dvě větve jedná o systém IFS se dvěma transformacemi. Tento systém je nelineární, protože uvedené transformace jsou taktéž nelineární – postačuje, aby alespoň jedna transformace v systému IFS byla nelineární, aby bylo možné celý systém prohlásit za nelineární.

fractals31_1

Obrázek 1: Systém iterovaných funkcí tvořený rovnicí P-1(z)=(z-c)-2

Pro praktické použití IFS systémů v počítačové grafice však většinou uvažujeme o omezené množině transformací, jedinou praktickou výjimkou z tohoto pravidla jsou fraktály nazývané Fractal Flame (viz další pokračování tohoto seriálu). V dalším textu si ukážeme použití afinních transformací. Afinní transformace mají tu vlastnost, že jsou lineární, to znamená, že při aplikaci této transformace na úsečku, resp. množinu bodů ležících na přímce, bude výsledkem transformace rovněž úsečka (resp. množina bodů, které leží na přímce).

Použití tohoto typu transformací značně zjednoduší veškeré výpočty, které je nutné nad systémem iterovaných funkcí provádět. Transformace musí splňovat ještě jednu podmínku, jež vychází z věty o pevném bodě: musí být kontrakcemi. To znamená, že po aplikaci transformace na dvojici libovolných nestejných bodů v ploše či prostoru, bude nová vzdálenost bodů menší než původní vzdálenost bodů. Tato vlastnost mimo jiné zaručuje, že atraktorem systému iterovaných funkcí nikdy nebude nekonečno. Afinní transformace je možné při respektování předchozích dvou odstavců definovat v Euklidově prostoru následovně:

d(φi (X)-φi (Y)) < s×d(X-Y)

kde:

  • d(X) je Euklidova metrika
  • X a Y jsou libovolné dva body v ploše E2 či prostoru E3
  • φi (X) a φi (Y) jsou body transformované pomocí aplikace transformace φi

Podle velikosti koeficientu kontrakce s je pak možné určit typ použité transformace φi:

  • s<1  :  φi je lineární či nelineární transformace zmenšení (kontrakce)
  • s=1  :  φi je symetrie (například se může jednat o rotaci či zrcadlení)
  • s>1  :  φi je lineární či nelineární transformace zvětšení (expanze)

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 bez ohledu na jejich polohu a orientaci.

Afinní transformace lze popsat matematicky různým způsobem, nejvýhodnější však bývá popis pomocí transformačních matic, popř. i vektorů posunu. Při programové implementaci se tak dosahuje výrazného ušetření paměťového místa a současně i urychlení výpočtů. Transformace je v ploše E2 popsána maticí U o velikosti 2×2 prvky a vektorem posunu V se dvěma prvky, v Euklidově prostoru E3 se jedná o matici velikosti 3×3 prvky, vektor posunu má délku tři prvky. Při současné aplikaci transformace posunu (translace) lze afinní transformaci zapsat v maticovém tvaru následovně:

w(X)=UX+V

Jednotlivé koeficienty matice U se uplatňují při aplikaci transformace rotace, zkosení a změně měřítka jak v horizontálním, tak i ve vertikálním směru. Koeficienty vektoru V jsou použity při posunu (translaci).

K množině zobrazení Φ={φ1, φ2, … φn } náleží ještě množina pravděpodobností Π={π1, π2, … πn }, πi>0. Pro tyto pravděpodobnosti musí dále platit podmínka jednotkového součtu:

i=1nπi=1

Množina Φ je průměrně kontraktivní, pokud platí následující podmínka (jedná se o mírnější podmínku, než je výše uvedená podmínka kontrakce všech transformací):

s1π1× s2π2× … snπn < 1 

Zjednodušeně je možné říci, že čím větší je pravděpodobnost nějaké transformace φi, tím větší musí být i její míra kontrakce. Platí-li předchozí vztahy, potom uspořádanou dvojici:

IFS = (Φ, Π) = ({φ1, φ2, … φn }, {π1, π2, … πn })

nazveme systémem iterovaných funkcí – IFS.

fractals31_2

Obrázek 2: Model větvičky vytvořený pomocí IFS systému se třemi afinními transformacemi

2. Aplikace transformací v systému iterovaných funkcí

první kapitole jsme si řekli, že u systémů iterovaných funkcí většinou uvažujeme použití afinních transformací. Ty mohou být popsány různým způsobem, většinou se však používají transformační matice a vektory posunu, protože každou afinní transformaci je možné vyjádřit vzorcem w(X)=UX+V. Transformační matici U a vektor posunu V je dále možné sloučit do jediné transformační matice T, jejíž velikost se však zvětší: v rovině půjde o matici 3×3 prvky, v prostoru o matici 4×4 prvky. Při aplikaci této transformační matice se využívají takzvané homogenní souřadnice, tj. k původním souřadnicím [x,y] resp. [x,y,z] přibývá souřadnice w. Aplikace transformace na bod [x,y,w] resp. [x,y,z,w] je při použití homogenních souřadnic velmi jednoduchá:

[x',y',w']=T[­x,y,w]T   (v rovině)
[x',y',z',w']­=T[x,y,z,w]T   (v prostoru)

Vzhledem k tomu, že se za poslední souřadnici w dosazuje jednotka (alespoň v případě IFS systémů), platí:

[x',y',1]=T[x­,y,1]T   (v rovině)
[x',y',z',1]T[x,y,z,1]T   (v prostoru)

Z předchozích dvou vztahů nutně plyne, že poslední řádek matice T musí obsahovat hodnoty [0, 0, 1] nebo [0, 0, 0, 1], tj. v operační paměti je při praktické implementaci nutné ukládat o jeden řádek číselných hodnot méně, což je zcela jistě užitečné, a to jak z hlediska paměťových nároků (zejména při fraktální kompresi), tak i kvůli redukci počtu aritmetických operací násobení a sčítání. Prakticky to znamená, že v rovině je transformace popsána pomocí šesti číselných hodnot a v prostoru pomocí čísel dvanácti. V šesté kapitole bude uveden demonstrační příklad, ve kterém budou jednotlivé transformace IFS systému popsány právě pomocí transformačních matic T, resp. těchto transformačních matic bez jejích posledních řádků.

fractals31_3

Obrázek 3: Fraktální drak vytvořený systémem iterovaných funkcí

3. Vytvoření základního objektu s jeho pokrytím menšími kopiemi

Velkou předností systémů iterovaných funkcí je možnost jejich interaktivního návrhu, při kterém uživatel nemusí pracovat pouze s numerickými hodnotami, ale s geometrickými tvary. Plošné či prostorové objekty, které budou tvořit základ pro generování fraktálních objektů pomocí systémů iterovaných funkcí, je vhodné reprezentovat obrysově. Existují i jiné možnosti reprezentace základního objektu, například reprezentace plošná, u níž je transformační matice rozšířena o změnu barvy a kontrastu, avšak obrysová reprezentace má tu výhodu, že je jednoduchá jak pro interaktivní zadávání dat uživatelem, tak i pro uložení dat v operační paměti počítače.

Práce uživatele při návrhu fraktálního obrazce pomocí systému iterovaných funkcí spočívá v tom, že uživatel navrhne bázový (základní) objekt, což není nic jiného než uspořádaný seznam vrcholů navzájem pospojovaných úsečkami. Zde se na uživatele nekladou žádné meze, je možné například vytvořit objekt, který má některé své hrany proťaty. Na výsledný fraktální objekt nemá tvar základního objektu žádný vliv, jedná se pouze o vizuální pomůcku pro uživatele.

Další činnost, kterou musí uživatel vykonat, je takzvané pokrytí nakresleného bázového objektu. To se provádí postupným pokládáním objektů, vzniklých ze základního objektu aplikací lineárních transformací, na objekt bázový. Uživatel nejprve vytvoří kopii bázového objektu, tu podrobí některé transformaci (nebo i více transformacím, ty se totiž dají složit do transformace jediné) a výsledný objekt potom položí na objekt bázový.

Záleží pouze na uživateli, jak dokonale pokryje bázový objekt. Při dokonalém pokrytí (to znamená, že se transformované objekty budou dotýkat přesně hranami a nebudou se překrývat) bude výsledná IFS koláž přesnou kopií bázového objektu. Určité nepřesnosti jsou způsobeny matematickou chybou (vzhledem k iteračnímu procesu se chyby kumulují), nedostatečným počtem provedených iterací, nebo chybným výpočtem pravděpodobností jednotlivých transformací.

Při neúplném pokrytí bázového objektu vznikají ve výsledné IFS koláži prázdná místa, což může v některých případech vytvořit zajímavý motiv. Jestliže se naopak transformované objekty překrývají, má to za následek pomalejší vykreslování IFS koláže v důsledku toho, že jsou některé části koláže neustále překreslovány a generované body (pixely) se navzájem překrývají. Tento problém je patrný zejména při vytváření trojrozměrných objektů, protože se objekt může skládat z mnoha ploškových elementů – (surfelů), které se mohou navzájem překrývat či protínat. Tyto surfely je nutné ve fázi postprocessingu odstranit. Ukázka fraktálních obrazců vygenerovaných z bázového objektu s překrývajícími se kopiemi je zobrazena na následujícím obrázku.

fractals31_4

Obrázek 4: IFS vytvořený z bázového objektu s překrývajícími se kopiemi

Jestliže uživatel vytvoří transformovaný objekt, jehož transformace není kontrakcí, musí na tuto skutečnost být před vygenerováním IFS koláže upozorněn. Program může vygenerovat i obrázek či trojrozměrný objekt s takovouto transformací. V tomto případě ale již nejde o IFS, protože IFS je definován jako systém, v jehož množině transformací jsou funkce mající atraktor – viz též předchozí vztahy vyjadřující kontrakci. Funkce, která není kontrakcí, nemá atraktor (ve skutečnosti je atraktorem nekonečno, myšleno ve smyslu dvou dimenzí). Problémem zde může být, že při generování IFS koláže s nekontrahující transformací může nastat aritmetická chyba v důsledku přetečení výsledku transformace. V případě regulárních IFS systémů, ve kterých jsou všechny transformace kontrahující, tento problém již z principu nenastává.

4. Výpočet transformačních matic

Jak jsme se dozvěděli v předchozí kapitole, spočívá veškerá práce uživatele při vytváření IFS systému v nakreslení bázového objektu (či vytvoření objemového modelu trojrozměrného tělesa) a v jeho následném pokrytí menšími transformovanými kopiemi původního tvaru. Tomu odpovídá i datová reprezentace v aplikacích pracujících s IFS systémy. První datovou strukturou je seznam vrcholů bázového objektu, druhou datovou strukturou je seznam jednotlivých transformací.

Některé aplikace určené pro vytváření a editaci IFS systémů místo seznamu transformací udržují v operační paměti seznam vrcholů všech objektů, tedy objektu bázového i objektů transformovaných. To má výhodu v rychlejším vykreslování vlastních objektů v editoru. Nevýhodou je nutnost zpětného výpočtu transformačních matic při generování IFS. Diskutabilní je paměťová náročnost. První metoda je příznivější v případě, že základní objekt má více než šest vrcholů, v opačném případě je lepší metoda druhá. Při vytváření objemového modelu trojrozměrného tělesa je samozřejmě použito velké množství vrcholů, proto je výhodnější uchovávat v operační paměti „pouze“ seznam transformací.

Uchování seznamu transformací má i tu přednost, že se nemusí provádět výpočet transformačních matic, neboť samotná transformace je transformační maticí reprezentována. V případě, že si aplikace pamatuje pouze seznam vrcholů základního objektu i objektu transformovaného, je zapotřebí transformační matici spočítat. K tomu dostačují v rovině pouze tři vrcholy, protože počet souřadnic tří vrcholů [x1, y1], [x2, y2] a [x3, y3] odpovídá počtu prvků transformační matice T, jejichž hodnoty jsou hledány. Jestliže známe souřadnice vrcholů původního objektu i objektu transformovaného, je možné vytvořit následující systém šesti rovnic o šesti neznámých t0,0, t1,0, t2,0, t0,1, t1,1 a t2,1, který je možné v netriviálních případech jednoznačně vyřešit:

x'1=t0,0 x1+t­1,0 y1+t2,0
y'1=t0,1 x1+t­1,1 y1+t2,1
x'2=t0,0 x2+t­1,0 y2+t2,0
y'2=t0,1 x2+t­1,1 y2+t2,1
x'3=t0,0 x3+t­1,0 y3+t2,0
y'3=t0,1 x3+t­1,1 y3+t2,1
 

fractals31_5

Obrázek 5: Variace na téma binárního stromu

5. Algoritmus náhodné procházky (RWA)

Algoritmus náhodné procházky (RWA – Random Walk Algorithm) patří mezi nejjednodušší algoritmy pro generování fraktálních objektů pomocí systémů iterovaných funkcí. Jeho předností 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é pouze jednou a při malém počtu iterací může dokonce docházet k tomu, že se některé části fraktálu nevykreslí.

Generování IFS fraktálu se nastartuje tak, že se zvolí náhodný bod P0 v rovině E2 či prostoru E3. Poloha počátečního bodu nemá na výslednou koláž žádný větší vliv, nemusí tedy nutně ležet uvnitř atraktoru systému iterovaných funkcí. Poté je náhodně vybrána nějaká transformace φi z množiny Φ. Při výběru transformace je nutné přihlédnout k tomu, aby počet použití dané transformace odpovídal její pravděpodobnosti πi, jinak se bude výsledná koláž generovat neúměrně dlouho. Poté, co byla některá transformace vybrána, je možné ji aplikovat na daný bod. Souřadnice tohoto bodu se změní (bod se podrobní transformaci). Na tento nový bod je posléze iterativně aplikována další náhodně vybraná transformace. Iterace probíhají tak dlouho, dokud není dosaženo zadaného maximálního počtu iterací.

Jelikož první bod P0 nemusí nutně ležet v atraktoru IFS, je nutné několik prvních iterací počátečního bodu nezobrazovat. Z teorie IFS systémů, kterou jsem uvedl v předchozích kapitolách, vyplývá, že se systém automaticky dostane po několika iteracích do svého atraktoru, v němž již setrvá. Kvalitu výsledného fraktálního objektu 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. V programovacím jazyce C lze algoritmus náhodné procházky pro generování IFS koláže napsat následovně:

//-----------------------------------------------------------------------------
// Překreslení systému iterovaných funkcí IFS - fraktálu kapradiny
//-----------------------------------------------------------------------------
void recalcIFS(pixmap *pix,                     // pixmapa pro vykreslování
                  int    maxiter,               // maximální počet iterací
                  double scale,                 // měřítko obrazce
                  double xpos,                  // posun obrazce
                  double ypos)
{
    float  t[4][2][3];                          // transformační matice
    float  p[4];                                // vektor pravděpodobnosti transformací

    int    iter=0;                              // počitadlo iterací
    int    threshold=10;                        // hranice počtu iterací pro vykreslování

    float  x, y, hlp;                           // poloha iterovaného bodu
    float  pp;                                  // pravděpodobnost pro výběr transformace
    float  sum;
    int    k;                                   // číslo vybrané transformace

    // transformační matice a vektor pravděpodobnosti transformací pro fraktální kapradinu
    t[0][0][0]= 0.000;   t[0][0][1]= 0.000;   t[0][0][2]= 0.000;
    t[0][1][0]= 0.000;   t[0][1][1]= 0.160;   t[0][1][2]= 0.000;

    t[1][0][0]= 0.200;   t[1][0][1]=-0.260;   t[1][0][2]= 0.000;
    t[1][1][0]= 0.230;   t[1][1][1]= 0.220;   t[1][1][2]= 1.600;

    t[2][0][0]=-0.150;   t[2][0][1]= 0.280;   t[2][0][2]= 0.000;
    t[2][1][0]= 0.260;   t[2][1][1]= 0.240;   t[2][1][2]= 0.440;

    t[3][0][0]= 0.850;   t[3][0][1]= 0.040;   t[3][0][2]= 0.000;
    t[3][1][0]=-0.040;   t[3][1][1]= 0.850;   t[3][1][2]= 1.600;

    p[0]=0.01;
    p[1]=0.07;
    p[2]=0.08;
    p[3]=0.84;

    x=0;                                        // nastavení počáteční polohy bodu
    y=0;                                        // v rovině
    srand(0);
    xpos+=pix->width/2;                         // posun do středu okna
    ypos+=pix->height/2;
    while (iter++<maxiter*100) {                // iterační smyčka
        pp=(float) random (255) / 255.0;        // p leží v rozsahu 0.0-1.0
        k=0;                                    // proměnná cyklu vyhledání transformace
        sum=0;
        while (sum<=pp) {                       // podle hodnoty náhodného čísla
            sum=sum+p[k];                       // vybrat transformaci
            k++;
        }                                       // k určuje index transformace
        k--;                                    // úprava hodnoty k ze smyčky while
        hlp=t[k][0][0]*x+t[k][0][1]*y+t[k][0][2]; // provedení vybrané
        y  =t[k][1][0]*x+t[k][1][1]*y+t[k][1][2]; // transformace
        x  =hlp;
        if (iter > threshold)                   // je-li dosaženo hranice iterací
            putpixel(pix, x*scale+xpos, y*scale+ypos, 0xff, 0xff, 0xff); // vykreslení pixelu
    }
} 
fractals31_6

Obrázek 6: Telefonní šňůra

6. Vykreslení IFS systému pomocí algoritmu náhodné procházky – demonstrační příklad

Výše uvedená funkce recalcIFS() je implementována v dnešním demonstračním příkladu, po jehož spuštění se vykreslí fraktální obrázek kapradiny. Pomocí klávesnice je možné měnit maximální počet iterací a také s obrázkem pohybovat, popř. měnit jeho zvětšení. Screenshot z demonstračního příkladu je ukázán na sedmém obrázku.

fractals31_7

Obrázek 7: Screenshot demonstračního příkladu 31.1

root_podpora

7. Obsah dalšího pokračování tohoto seriálu

V následující části tohoto seriálu si popíšeme několik způsobů, pomocí nichž je možné vypočítat pravděpodobnosti jednotlivých transformací, tj. množinu Π={π1, π2, … πn }. Korektně nastavené a následně použité pravděpodobnosti transformací totiž mohou vést k urychlení vykreslení IFS systému, zejména při použití výše uvedeného algoritmu náhodné procházky.

fractals31_8

Obrázek 8: I sněhovou vločku Helge von Kocha je možné popsat pomocí IFS systémů, tentokrát je poněkud netypicky ztvárněna

Byl pro vás článek přínosný?

Autor článku

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.