Pravděpodobnosti transformací v systémech iterovaných funkcí

Obsah

1. Výpočet pravděpodobností jednotlivých transformací
2. Výpočet pravděpodobnosti transformace vyjádřením koeficientu kontrakce
3. Výpočet pravděpodobnosti transformace z poměru obsahů generovaných obrazců
4. Výpočet pravděpodobností z poměru obsahů opsaných obdélníků či kvádrů
5. Výpočet pravděpodobností z poměru obsahů opsaných kružnic či koulí
6. Výpočet pravděpodobnosti transformace z koeficientu zkrácení úsečky
7. Uniformní rozdělení pravděpodobností
8. Obsah dalšího pokračování tohoto seriálu

1. Výpočet pravděpodobností jednotlivých transformací

V případě, že jsou zadány všechny lineární transformace systému iterovaných funkcí, pomocí kterých se bude vytvářet fraktální rastrový plošný obrazec či trojrozměrné těleso, musí se v dalším kroku dopočítat k zadané množině transformací Φ={φ₁, φ₂, … φ_n} jim odpovídající množina pravděpodobností Π={π₁, π₂, … π_n}, které určují, s jakou četností budou tyto transformace použity při generování fraktálu (jak již víme z předchozích pokračování tohoto seriálu, jde o transformace afinní a většinou i kontraktivní). Bylo by samozřejmě možné, aby všechny transformace měly pravděpodobnost definitoricky nastavenou, to by ale nebylo výhodné z hlediska rychlosti programového generování fraktálu (viz první tři obrázky představující IFS systém se stejnými transformacemi, ale s odlišně nastavenými pravděpodobnostmi).

Obrázek 1: IFS systém se třemi transformacemi, které mají nastavené pravděpodobnosti na stejné hodnoty {1/3, 1/3, 1/3}

Transformace, které jsou ve velké míře kontrahující, to znamená, že mají nízké hodnoty koeficientů v transformační matici, by iterované body příliš přitahovaly k atraktoru systému. Výsledkem by byl málo rozvinutý fraktál, pro jehož generování v dostatečné vizuální kvalitě by bylo nutné použít příliš vysoký počet iterací. Také množství vygenerovaných souřadnic (a tím i změněných, tj. zapsaných pixelů) by neúměrným způsobem stoupalo – toto zpomalení je ještě více patrné při generování obrazů trojrozměrných IFS systémů, kdy je zapotřebí vygenerovat mnohem větší počet bodů než v případě dvojrozměrném.

Obrázek 2: IFS systém se třemi transformacemi, které mají nastavené pravděpodobnosti na hodnoty {1/5, 2/5, 2/5}

Z tohoto důvodu je vhodné, aby byla jednotlivým lineárním (resp. afinním) transformacím přiřazena určitá pravděpodobnost, s jakou tyto transformace při generování fraktálního obrazce nastanou, přičemž příliš kontrahující transformace budou mít menší pravděpodobnost než transformace kontrahující méně. Při výpočtu pravděpodobností jednotlivých transformací je nutné dbát na to, aby součet všech pravděpodobností byl roven jednotce dle minule uvedeného vztahu. V následujících kapitolách popíšu šest možností, pomocí kterých je možné vypočítat pravděpodobnosti jednotlivých transformací. U každé možnosti bude uvedena také vhodnost jejího použití vzhledem k charakteru vytvářeného fraktálního obrazce. První uvedený způsob je známý a často používaný, další tři způsoby jsou nové – poprvé byly pravděpodobně popsány v mé diplomové práci. Mezi popisované způsoby patří:

1. výpočet pravděpodobnosti transformací vyjádřením koeficientu jejich kontrakce.
2. výpočet pravděpodobnosti transformací z poměru obsahů generovaných obrazců.
3. výpočet pravděpodobnosti transformací z poměru obsahů opsaných obdélníků či kvádrů.
4. výpočet pravděpodobnosti transformací z poměru obsahů opsaných kružnic či koulí.
5. výpočet pravděpodobnosti transformací z koeficientu zkrácení úsečky.
6. uniformní rozdělení jednotlivých pravděpodobností.

Obrázek 3: IFS systém se třemi transformacemi, které mají nastavené pravděpodobnosti na hodnoty {1/10, 9/20, 9/20}

2. Výpočet pravděpodobnosti transformace vyjádřením koeficientu kontrakce

Tento způsob výpočtu pravděpodobností jednotlivých transformací IFS systému patří mezi nejčastěji používané metody pro získání (a pozdější aplikaci) pravděpodobností transformací při vytváření IFS koláží v plošných rastrových obrazcích. Pro běžné typy transformací (zdaleka ne však pro všechny, zejména to neplatí pro mezní a singulární případy) dává tento způsob poměrně dobré výsledky, to znamená, že rozložení pravděpodobností generované tímto vztahem přibližně odpovídá ideálnímu rozložení. Další předností tohoto způsobu výpočtu je jeho jednoduchost, dosti závažnou nevýhodou pak fakt, že některé pravděpodobnosti mohou při výpočtu vycházet nulové – je to dáno způsobem výpočtu koeficientů z transformační matice. To by však znamenalo, že by se daná transformace nepodílela na generování koláže, což je samozřejmě chybné rozhodnutí. Po aplikaci tohoto způsobu je tedy nutné ošetřit nulové pravděpodobnosti a přiřadit jim nějakou minimální nenulovou hodnotu, která je v dalším textu označena symbolem S_ε.

Při odvození vztahu pro výpočet pravděpodobnosti i-té transformace se vychází z použité transformační matice A_i, ze které je vypočten dočasný koeficient kontrakce:

s'_i=a_11i × a_22i – a_12i × a_21i

Poté je zapotřebí ošetřit stav, kdy je některý koeficient kontrakce nastaven na nulovou hodnotu. To se provede tak, že se každá nulová hodnota kontrakce nahradí předem zadanou konstantou S_ε. Pravděpodobnost π_i právě zpracovávané transformace i lze vyjádřit jednoduše:

π_i=s''_i/S

kde hodnota S představuje součet hodnot všech upravených koeficientů kontrakce:

S=∑_i=0^N s''_i

Výše uvedenou metodu je možné použít zejména při práci s plošnými IFS systémy, protože při práci v prostoru mnohdy nastávají problémy s výpočtem koeficientu kontrakce – mnoho koeficientů je po výpočtu nulových či blízkých nule.

Obrázek 4: IFS systém se čtyřmi transformacemi, které mají nastavené pravděpodobnosti na shodné hodnoty {1/4, 1/4, 1/4, 1/4}

3. Výpočet pravděpodobnosti transformace z poměru obsahů generovaných obrazců

Tento způsob výpočtu pravděpodobností jednotlivých transformací spočívá ve výpočtu plochy S_base bázového (základního) objektu tak, jak ho zadal uživatel v interaktivním grafickém editoru. Poté se na vrcholy bázového objektu aplikuje i-tá transformace, pro kterou je pravděpodobnost počítána, a pro nově vygenerované body se vyčíslí plocha nového objektu S_i. Pravděpodobnost dané transformace se spočítá jako poměr obsahů těchto dvou obrazců:

π_i=S_i/S_base

Výpočet obsahu objektu, který je zadán seznamem svých vrcholů, z nichž každý vrchol má souřadnice [x_n, y_n], se provede pomocí algebraického součtu determinantů. Každý determinant je vytvořen z matice čtveřic hodnot, které jsou dány polohou dvou sousedních vrcholů, které leží na hranici objektu:

   | xj  xj+1 |
Dj=|         |
   | yj  yj+1 |

Poslední determinant v řadě uzavírá celou posloupnost:

   | xn  x0 |
Dn=|        |
   | yn  y0 |

Výsledná plocha objektu je potom rovna polovině tohoto součtu:

S=1/2 |D₁+D₂+…+D_n|

Jedná se o nejpřesnější metodu sloužící k výpočtu pravděpodobností jednotlivých transformací, jejíž nevýhodou je však větší složitost, z čehož plyne i časová náročnost. Také způsob výpočtu ploch obrazce nemusí vždy dát korektní výsledky. To se stane zejména v případě, kdy uživatel zadal určitým způsobem zdeformovaný tvar bázového objektu, který má například dvě shodné hrany. Pro aplikaci systému iterovaných funkcí v prostoru se tento způsob výpočtu pravděpodobností příliš nehodí, protože se vlastní výpočet objemů těles stává příliš komplikovaný – proto byly pro tyto účely vytvořeny další metody popsané v následujících kapitolách.

Obrázek 5: IFS systém se čtyřmi transformacemi, které mají nastavené pravděpodobnosti na hodnoty {1/10, 3/10, 3/10, 3/10}

4. Výpočet pravděpodobností z poměru obsahů opsaných obdélníků či kvádrů

Způsob výpočtu pravděpodobností jednotlivých transformací pomocí vyčíslení poměru obsahů opsaných obdélníků či kvádrů je velmi rychlý, zejména v porovnání s předchozím způsobem. Vypočtené pravděpodobnosti jsou také jednoznačné, proto není zapotřebí ve výpočtech provádět korekce vypočtených hodnot. Nevýhodou je však menší přesnost vypočtených pravděpodobností, přičemž odchylka korektních hodnot od vypočtených pravděpodobností může činit jednotky a v ojedinělých případech až desítky procent.

Nejprve je proveden výpočet minimálních a maximálních souřadnic bázového objektu pomocí následujících vztahů:

x_min = min(x_i)     pro všechna i v rozsahu <1..n>
x_max = max(x_i)
y_min = min(y_i)
y_max = max(y_i)
z_min = min(z_i)
z_max = max(z_i) 

Z vypočtených souřadnic je získána plocha obdélníka (resp. objem kvádru, pokud se pracuje s trojrozměrnými IFS), který je opsán bázovému objektu:

S_obd = (x_max-x_min) × (y_max-y_min)
S_kva = (x_max-x_min) × (y_max-y_min) × (z_max-z_min)

Poté je pro každý vrchol bázového objektu provedena transformace a následně jsou spočítány nové minimální a maximální souřadnice pro transformovaný bázový objekt ([x'_i, y'_i, z'_i]=φ_j([x_i, y_i, z_i])):

x'_min = min(x'_i)    pro všechna i v rozsahu <1..n>
x'_max = max(x'_i)
y'_min = min(y'_i)
y'_max = max(y'_i)
z'_min = min(z'_i)
z'_max = max(z'_i)

V dalším kroku algoritmu je vypočtena plocha obdélníka (resp. objem kvádru), který je opsán transformovanému bázovému objektu:

S'_obdj = (x'_max-x'_min) × (y'_max-y'_min)
S'_kvaj = (x'_max-x'_min) × (y'_max-y'_min) × (z'_max-z'_min)

Výsledná pravděpodobnost j-té transformace je dána vztahem:

π_j=S'_obdj / S_obd

resp.

π_j=S'_kvaj / S_kva

Mohlo by se zdát, že by bylo dostačující vypočítat ohraničující obdélník bázového objektu a souřadnice vrcholů nového obdélníku získat pomocí aplikace transformace. Takový postup by však nedával shodný výsledek, neboť určité transformace (například zkosení apod.) by tento obdélník změnily na jiný tvar a vypočtený obsah S'_j by byl odlišný od S'_obdj.

Obrázek 6: IFS systém se čtyřmi transformacemi, které mají nastavené pravděpodobnosti na hodnoty {4/100, 32/100, 32/100, 32/100}

5. Výpočet pravděpodobnosti z poměru obsahů opsaných kružnic či koulí

Tento způsob výpočtu pravděpodobností jednotlivých transformací se podobá způsobu předchozímu. Základní rozdíl však spočívá v tom, že se neprovádí obalení bázového objektu obdélníkem, ale kružnicí. Pro výpočet pravděpodobnosti se potom porovnají obsahy obalujících kružnic bázového objektu a objektu transformovaného. V případě výpočtu pravděpodobností trojrozměrného systému iterovaných funkcí se místo obalové kružnice používá obalová koule.

Střed obalující kružnice v ploše (resp. koule v prostoru) se vypočítá jako aritmetický průměr souřadnic vrcholů bázového objektu:

x_s=1/n × ∑_i=1ⁿ x_i
y_s=1/n × ∑_i=1ⁿ y_i
z_s=1/n × ∑_i=1ⁿ z_i
 

Pro výpočet obsahu obalující kružnice je nutné znát i její poloměr, který se vypočte jako maximální vzdálenost středu obalující kružnice a souřadnic vrcholů bázového objektu:

radius_kruznice=max(((x_s-x_i)²+(y_s-y_i)²)^1/2)

kde x_i a y_i jsou souřadnice i-tého vrcholu bázového objektu. Obsah obalující kružnice se nyní vypočte snadno:

S_kruznice=π × radius²_kruznice

Pro obalující kouli v prostoru platí podobné vztahy jako pro kružnici:

radius_koule=max(((x_s-x_i)²+(y_s-y_i)²+(z_s-z_i)²)^1/2)
S_koule=4/3 × π × radius³_koule

Ve druhém kroku se nejprve provede transformace všech vrcholů bázového objektu. Dále jsou vypočteny souřadnice středu nové kružnice (resp. koule v prostoru):

x'_s=1/n × ∑_i=1ⁿ x'_i
y'_s=1/n × ∑_i=1ⁿ y'_i
z'_s=1/n × ∑_i=1ⁿ z'_i

Následně je zjištěn poloměr kružnice, která obaluje tento nový objekt vzniklý transformací v ploše:

radius'_kruzni­ce=max(((x'_s-x'_i)²+(y'_s-y'_i)²)^1/2)

kde x'_i a y'_i jsou souřadnice i-tého vrcholu transformovaného objektu. Obsah nové obalující kružnice je vypočten pomocí vztahu:

S'_kruznice=π × radius'²_kruzni­cei

Výsledná i-tá pravděpodobnost dané transformace IFS systému je dána vztahem:

π_i=S'_kruznice­i/S_kruznice

Pro obalující kouli v prostoru je situace obdobná:

radius'_koule=max(((x'_s-x'_i)²+(y'_s-y'_i)²+(z'_s-z'_i)²)^1/2)
S'_koule=4/3 × π × radius'³_koule
π_i=S'_koulei/S_kou­le

Tato metoda má podobné vlastnosti jako metoda předchozí. Výsledky se samozřejmě mohou lišit, neboť se jedná o odlišný způsob výpočtu. Předností této metody je, že se počítají korektně i ty transformace, u kterých dochází ke značnému zmenšení jedné souřadnice (například horizontální změna měřítka s malým faktorem zvětšení). U předchozí metody by obsah transformovaného obdélníku byl blízký nule, ale v metodě obalových kružnic/koulí se díky způsobu výpočtu poloměru transformované kružnice či koule dosáhne uspokojivých výsledků.

Obrázek 7: IFS systém se čtyřmi transformacemi, u nichž je snížen koeficient kontrakce

6. Výpočet pravděpodobnosti transformace z koeficientu zkrácení úsečky

Tento způsob využívá pro výpočet pravděpodobností transformací v systému iterovaných funkcí takzvaný koeficient zkrácení úsečky. Pro zjednodušení výpočtů neuvažuji v dalším textu libovolnou úsečku, ale úsečku, která vychází z bodu P₀=[0,0] do bodu P₁=[1,1] v ploše, nebo z bodu P₀=[0,0,0] do bodu P₁=[1,1,1] v prostoru. V tomto případě lze vzorec pro výpočet pravděpodobnosti i-té transformace přímo bez dalších komplikací odvodit. Nejprve si rozepišme zadané hodnoty, které získáme z bodů P₀ a P₁:

x₀=0
y₀=0
z₀=0
x₁=1
y₁=1
z₁=1 

Hodnoty vypočtené po aplikaci transformace specifikované transformační maticí A:

x'₀=a₁₁x₀+a_12­y₀+a₁₃z₀+t_x
y'₀=a₂₁x₀+a_22­y₀+a₂₃z₀+t_y
z'₀=a₃₁x₀+a_32­y₀+a₃₃z₀+t_z
x'₁=a₁₁x₁+a_12­y₁+a₁₃z₁+t_x
y'₁=a₂₁x₁+a_22­y₁+a₂₃z₁+t_y
z'₁=a₃₁x₁+a_32­y₁+a₃₃z₁+t_z 

Do těchto vztahů dosadíme hodnoty bodů P₀=[x₀, y₀, z₀]=[0,0,0] a P₁=[x₁, y₁, z₁]=[1,1,1]:

x'₀=a₁₁0+a₁₂0­+a₁₃0+t_x=t_x
y'₀=a₂₁0+a₂₂0­+a₂₃0+t_y=t_y
z'₀=a₃₁0+a₃₂0­+a₃₃0+t_z=t_z
x'₁=a₁₁1+a₁₂1­+a₁₃1+t_x=a₁₁+a₁₂+a₁₃+t_x
y'₁=a₂₁1+a₂₂1­+a₂₃1+t_y=a₂₁+a₂₂+a₂₃+t_y
z'₁=a₃₁1+a₃₂1­+a₃₃1+t_z=a₃₁+a₃₂+a₃₃+t_z 

Délka netransformované úsečky v prostoru je rovna:

d³=((x₁-x₀)²+(y₁-y₀)²+(z₁-z₀)²)^1/2=((1–0)²+(1–0)²+(1–0)²)^1/2=3^1/2

Pro úsečku v ploše E² platí obdobný vztah:

d²=((x₁-x₀)²+(y₁-y₀)²)^1/2= =((1–0)²+(1–0)²)^1/2=2^1/2

Délka transformované úsečky se v prostoru vypočítá pomocí transformovaných bo­dů:

d'³=((x₁‚-x₀‘)²+(y₁‚-y₀‘)²+(z₁‚-z₀‘)²)^1/2=
=((a₁₁+a₁₂+a_1­3+t_x-t_x)² +(a₂₁+a₂₂+a_23­+t_y-t_y)² +(a₃₁+a₃₂+a_33­+t_z-t_z)²)^1/2=
=((a₁₁+a₁₂+a_1­3)²+(a₂₁+a₂₂+a₂₃)²+(a₃₁+­a₃₂+a₃₃)²)^1/2

Pro délku transformované úsečky v rovině pak platí obdobný vztah:

d'²=((x₁‚-x₀‘)²+(y₁‚-y₀‘)²)^1/2=
=((a₁₁+a₁₂+t_x-t_x)² +(a₂₁+a₂₂+t_y-t_y)²)^1/2=
=((a₁₁+a₁₂)²+­(a₂₁+a₂₂)²)^1/2

Pravděpodobnost dané transformace π_i se vypočte jako podíl těchto dvou délek:

π_i³=(d'³)/(d^3­)=
=((a₁₁+a₁₂+a_1­3)²+(a₂₁+a₂₂+a₂₃)²+(a₃₁+­a₃₂+a₃₃)²)^1/2/(3^1/2)=
=[((a₁₁+a₁₂+a­₁₃)²+(a₂₁+a₂₂+a₂₃)²+(a_31­+a₃₂+a₃₃)²)/3]^1/2
π_i²=(d'²)/(d^2­)=
=((a₁₁+a₁₂)²+­(a₂₁+a₂₂)²)^1/2/(2^1/2)= [((a₁₁+a₁₂)²+­(a₂₁+a₂₂)²)/2]^1/2 

Tato metoda je pro výpočet velmi jednoduchá, přináší však také některé nevýhody. První nevýhodu způsobuje fakt, že úsečka je jednorozměrná. To znamená, že pravděpodobnost je přímo úměrná změně délky úsečky. Přesnější (resp. relevan­tnější) výsledky dávají metody, které pravděpodobnost počítají jako změnu obsahu či objemu nějakého útvaru. Rozdíl je tedy v lineárním, kvadratickém či kubickém poměru. Například transformace, která provede zmenšení objektu na polovinu bude mít pravděpodobnost rovnu 1/2. Budeme-li však pravděpodobnost počítat některou z předchozích metod, vyjde tato pravděpodobnost rovna 1/4 či 1/8. Tyto hodnoty jsou přesnější, neboť bázový objekt je v ploše pokryt čtyřmi objekty a v prostoru dokonce objekty osmi, z nichž každý je zmenšen na polovinu.

Druhou nevýhodou této metody je, že vyjadřuje zkrácení jen jedné pevně dané úsečky. To může způsobit chyby v případě, že daná transformace změní tvar tělesa v jiném směru, než jaký má tato úsečka. Pro ilustraci můžeme zadat transformaci, která nejprve otočí objekt o 45 stupňů doprava, potom provede horizontální změnu měřítka a následně objekt otočí o 45 stupňů doleva. Můžeme se přesvědčit, že zatímco tvar objektu se změní, délka úsečky zůstane konstantní. Bylo by tedy vhodnější, aby se spočítala změna délky různě orientovaných úseček. Problém nastává v případě, kdy je zapotřebí spočítat výslednou pravděpodobnost transformace v systému iterovaných funkcí. Poměr zkrácení všech úseček by se měl zprůměrovat, přičemž se musí použít geometrický průměr, ne průměr aritmetický.

Pro co nejpřesnější výpočet je možné jednu úsečku nahradit vektorem s pevně danou délkou, který se otáčí okolo středu. Při jedné otočce vektoru se tedy vypočítá obsah kružnice o poloměru rovném délce vektoru. Musí se provést integrace, aby se zjistil obsah této kružnice. Pro zjištění pravděpodobnosti transformace v prostoru je výpočet komplikovanější, proto ho zde neuvádím:

obsah=∫₀^2π(cos­²φ+sin²φ)^1/2 dφ

Poté se vypočte obsah objektu, který vznikne rotací vektoru po provedené transformaci. Obecně musí vyjít elipsa (resp. v prostoru elipsoid):

obsah'=∫₀^2π((c­os φ×a₁₁+sin φ×a₁₂+t_x)²+(c­os φ×a₂₁+sin φ×a₂₂+t_y)²)^1/­2 dφ

Výsledná pravděpodobnost se potom opět vypočte z poměru těchto dvou ploch:

π_i=obsah'/obsah

Jak je z předchozích vztahů patrné, tento způsob výpočtu pravděpodobnosti je velmi komplikovaný a časově náročný – ve skutečnosti se totiž pomocí integrálu zpřesnily předchozí dvě metody, které vyjadřovaly vzájemný poměr objemů či obsahů obalových těles. Popisovaná úprava přitom neodstraňuje základní nevýhodu této metody, tj. lineární závislost pravděpodobnosti na změně měřítka.

Obrázek 8: Struktura vytvořená pomocí IFS systému

7. Uniformní rozdělení pravděpodobností

Při použití této metody výpočtu pravděpodobností jednotlivých transformací se pravděpodobnost jedné transformace v systému iterovaných funkcí vypočte jako převrácená hodnota počtu transformací:

π_i=1/n pro všechna i z rozsahu <1­..n>

kde n je počet všech transformací. Všechny transformace tedy mají přiřazenu stejnou pravděpodobnost. Obecně má tato volba za následek nerovnoměrné rozložení hustoty bodů ve výsledném fraktálu. To je důsledkem toho, že více kontrahující transformace k sobě také více přitahují generované body. Tyto body se potom více „hromadí“ na místech, kde je aplikována daná transformace. Pro trojrozměrné fraktální objekty je tato metoda nevhodná, protože v některých místech prostoru může značně narůstat počet navzájem se překrývajících surfelů, které je zapotřebí odstranit při konečné úpravě (postprocessingu) modelu scény.

Obrázek 9: Další struktura vytvořená pomocí IFS systému

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

V následujícím pokračování tohoto seriálu krátce zhodnotíme vlastnosti metod pro výpočet pravděpodobností jednotlivých transformací a posléze si popíšeme další algoritmy, pomocí nichž je možné generovat obrázky IFS systémů (algoritmus náhodné procházky totiž zdaleka není jediným algoritmem, který je pro výpočet IFS možné použít).

Obrázek 10: IFS systém s krystalickou strukturou