Vytváření IFS kódu  

     
Úvodní stránka
  
Předchozí kapitola        
   Obsah 
(c)1999,2000
  
Další kapitola    
Pavel Tišnovský
 
E-mail


Obsah

1  Vytváření IFS kódu
    1.1  Základy lineární algebry a maticový počet
        1.1.1  Lineární algebra
        1.1.2  Maticový počet
        1.1.3  Lineární transformace
        1.1.4  Afinní transformace
    1.2  Vytvoření základního objektu a jeho pokrytí
    1.3  Výpočet transformačních matic
        1.3.1  Reprezentace transformace jedinou maticí
        1.3.2  Transformační matice základních transformací
            Posun bodu o vektor [px,py]:
            Změna měřítka s koeficientem Ms:
            Horizontální změna měřítka s koeficientem Mx:
            Vertikální změna měřítka s koeficientem My:
            Horizontální zešikmení (střih) s koeficientem Sx:
            Vertikální zešikmení (střih) s koeficientem Sy:
            Rotace okolo počátku o úhel a:
        1.3.3  Transformační matice složených transformací
            Změna měřítka z bodu [px,py]
            Horizontální změna měřítka z bodu [px,py]
            Vertikální změna měřítka z bodu [px,py]
            Horizontální zešikmení z bodu [px,py]
            Vertikální zešikmení z bodu [px,py]
            Rotace okolo bodu [px,py]
        1.3.4  Aplikace transformací na transformační matice
    1.4  Výpočet pravděpodobnosti jednotlivých transformací
        1.4.1  Výpočet pravděpodobnosti pomocí koeficientu kontrakce
        1.4.2  Výpočet pravděpodobnosti z poměru obsahů generovaných obrazců
        1.4.3  Výpočet pravděpodobnosti z poměru obsahů opsaných obdélníků
        1.4.4  Výpočet pravděpodobnosti z poměru obsahů opsaných kružnic
        1.4.5  Výpočet pravděpodobnosti z koeficientu zkrácení úsečky
        1.4.6  Uniformní rozdělení pravděpodobností
        1.4.7  Zadání pravděpodobností uživatelem
        1.4.8  Závěr
    1.5  Algoritmus výpočtu IFS kódu
        1.5.1  Neformální popis algoritmu
        1.5.2  Zjištění typu transformace

Kapitola 1
Vytváření IFS kódu

1.1  Základy lineární algebry a maticový počet

Při vytváření IFS kódu i pro generování výsledné IFS koláže se používají afinní transformace. Afinní transformace vzniká složením několika lineárních transformací. Afinní transformace lze popsat různě, nejvýhodnější je však popis pomocí matic. Dosahuje se tak výrazného ušetření paměťového místa a současně i zrychlení výpočtu. Proto je potřeba zavést základní pojmy z lineární algebry a z maticového počtu, abychom pochopili další kapitoly.

1.1.1  Lineární algebra

Množina L libovolných prvků (budeme jim říkat vektory) se nazývá lineární prostor, jestliže:

Množina všech uspořádaných n-tic reálných čísel, na které jsou definovány operace sčítání a násobení reálným číslem, se nazývá aritmetický lineární prostor. Jeho prvky se nazývají aritmetické vektory.

1.1.2  Maticový počet

Matice je uspořádané schéma reálných čísel:
A = ć
ç
ç
ç
ç
ç
ç
č
a11
a12
ź
a1n
a21
a22
ź
a2n
:
:
···
:
an1
an2
ź
ann
ö
÷
÷
÷
÷
÷
÷
ř
(1.1)

Toto je matice typu n x n (n je pevně dané přirozené číslo). Matice budeme značit velkými písmeny.

Vektory z aritmetického lineárního prostoru Vn [^a]1* = (a11,a12 ... a1n) se nazývají řádkové vektory nebo řádky matice A.

Vektory z aritmetického lineárního prostoru Vn [^a]*1 = (a11,a21 ...an1) se nazývají sloupcové vektory nebo sloupce matice A.

Sčítání matic: nechť A a B jsou matice typu m x n. Součet matic A+B je matice X, která vznikne součtem daných prvků matice (součtem prvků na stejném místě v matici):

xij = aij+bij  "i,j Î N+.
(1.2)

Sčítání je definováno pouze pro matice stejného typu.

Součin matic: Nechť A je matice typu m x n, B je matice typu n x p. Součin matic A a B je matice typu m x p pro jejíž prvky platí:

xij = n
ĺ
k = 1 
aik*bkj
(1.3)

Hodnota na pozici i, j ve výsledné matici A.B tedy odpovídá skalárnímu součinu aritmetických vektorů pro i-tý řádek matice A a pro j-tý sloupec matice B. Součin matic A a B je definován pouze v případě, že počet sloupců matice A je roven počtu řádků matice B.

Je důležité si uvědomit, že pro matice platí:
A+B = B+A,
ale nemusí vždy platit:
A*B = B*A.

1.1.3  Lineární transformace

Nechť C je čtvercová matice řádu n. Zobrazení aritmetického lineárního prostoru Vn Ž Vn definované předpisem:

y = Cx
(1.4)

se nazývá lineární transformace ve Vn. Matice C se nazývá matice transformace.

1.1.4  Afinní transformace

Afinní transformace je definována vztahem:

w(X) = AX+B
(1.5)

Jedná se o maticový zápis, tedy:

w: ć
ç
č
x2
y2
ö
÷
ř
= ć
ç
ç
ç
č
a11
a12
a21
a22
ö
÷
÷
÷
ř
* ć
ç
č
x1
y1
ö
÷
ř
+ ć
ç
č
b1
b2
ö
÷
ř
(1.6)

Jednotlivé koeficienty matice A se uplatňují při rotaci, zkosení a změně měřítka, koeficienty matice B při posunutí.

1.2  Vytvoření základního objektu a jeho pokrytí

Objekty, které budeme chtít zobrazit pomocí metody IFS, budeme reprezentovat obrysově. Existují i jiné možnosti reprezentace, například reprezentace plošná, ale u ní je transformační matice rozšířena o změnu barvy a kontrastu. Obrysová reprezentace má tu výhodu, že je jednoduchá jak pro zadávání dat uživatelem, tak i pro uložení dat v paměti počítače.

Práce při návrhu IFS spočívá v tom, že uživatel navrhne základní objekt, což není nic jiného než uspořádaný seznam vrcholů pospojovaných úsečkami. Zde se na uživatele nekladou žádné meze, je možné například vytvořit objekt, který má některé hrany protnuté. Na výsledný IFS nemá tvar základního objektu žádný vliv.

Další činnost, kterou musí uživatel vykonat, je pokrytí nakresleného základního objektu. To se děje tak, že uživatel na základní objekt pokládá objekty vzniklé ze základního objektu lineárními transformacemi. Uživatel tedy vytvoří kopii základního objektu, tu podrobí některé transformaci (nebo i více transformacím) a výsledný objekt potom položí na objekt základní.

Záleží jen na uživateli jak dokonale pokryje základní 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í základního objektu. Určité nepřesnosti jsou způsobeny matematickou chybou (vzhledem k iteračnímu procesu se chyby kumulují) a nedostatečným počtem iterací.

Obrázek 1.1: Ukázka pokrytí základního objektu

Obrázek 1.2: Pokrytí základního objektu s rozšířením dvou transformací

Při neúplném pokrytí 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.

Jestliže uživatel vytvoří transformovaný objekt, jehož transformace není kontrakcí, je na to před vykreslením IFS koláže upozorněn. Program může vygenerovat i obrázek s takovouto transformací. V tomto případě ale již nejde o IFS, protože IFS je definován jako systém, ve kterém jsou funkce mající atraktor. 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 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 (když jsou všechny transformace kontrahující) tento problém samozřejmě nenastává.

Celá práce uživatele při vytváření IFS tedy spočívá v nakreslení základního objektu a v jeho pokrytí. Tomu odpovídá i datová reprezentace v programu. První datovou strukturou je seznam vrcholů základního objektu, druhou datovou strukturou je seznam jednotlivých transformací.

Některé programy na vytváření IFS místo seznamu transformací udržují v paměti seznam vrcholů všech objektů, tedy objektu základního i objektů transformovaných. To má výhodu v rychlejším vykreslování vlastních objektů v editoru. Nevýhodou je nutnost 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á.

1.3  Výpočet transformačních matic

Jak již bylo řečeno, vzorec pro lineární transformaci má tvar:

w: ć
ç
č
x2
y2
ö
÷
ř
= ć
ç
ç
ç
č
a11
a12
a21
a22
ö
÷
÷
÷
ř
* ć
ç
č
x1
y1
ö
÷
ř
+ ć
ç
č
b1
b2
ö
÷
ř
(1.7)

kde xn, yn jsou souřadnice iterovaného bodu. Chceme tedy nalézt koeficienty aij a bi.

Na základní objekt lze aplikovat tyto lineární transformace:

Každá transformace je reprezentována maticí transformace. Matice transformace je matice řádu 3x3 a vzniká vlastně složením matic A a B. Výsledná transformace je vypočtena jako maticový součin jednotlivých základních transformací. Zde je nutno připomenout, že násobení matic není komutativní, což se mimo jiné projevuje tím, že prohozením pořadí dvou transformací vznikne odlišná výsledná transformace.

1.3.1  Reprezentace transformace jedinou maticí

Pro výpočty s afinními transformacemi je někdy výhodné sloučit transformační matici A a translační matici B. Vznikne tak matice řádu 3x3. Také se přehodí pořadí pro násobení matice A s vektorem.

Novou transformační matici budeme nazývat Mx a vzorec pro afinní transformaci nabude tvaru:

w: ^
x2
 
Ž ^
x1
 
*M
(1.8)

Maticový zápis:

w:[x2,y2,1] = [x1,y1,1]* ć
ç
ç
ç
č
a11
a21
0
a12
a22
0
tx
ty
1
ö
÷
÷
÷
ř
(1.9)

V dalším textu budeme všechny transformace zapisovat pouze pomocí této matice Mx.

Maticový zápis můžeme rozepsat na vztahy, které platí pro jednotlivé souřadnice transformovaného bodu:

x2
=
x1*a11+y1*a12+tx
(1.10)
y2
=
x1*a21+y1*a22+ty
(1.11)
1
=
x1*0+y1*0+1*1
(1.12)

Poslední vztah není nutno uvádět, protože se v něm vyskytují pouze konstanty. Tento vztah by byl využit buď při aplikaci nelineární transformace, nebo při aplikaci perspektivního zobrazení.

1.3.2  Transformační matice základních transformací

Posun bodu o vektor [px,py]:

Zápis pomocí souřadnic bodů:
x2
=
x1+px
(1.13)
y2
=
y1+py
(1.14)

Transformační matice:

Mtrans = ć
ç
ç
ç
č
1
0
0
0
1
0
px
py
0
ö
÷
÷
÷
ř
(1.15)

Změna měřítka s koeficientem Ms:

Zápis pomocí souřadnic bodů:
x2
=
x1*Ms
(1.16)
y2
=
y1*Ms
(1.17)

Transformační matice:

Mscale = ć
ç
ç
ç
č
Ms
0
0
0
Ms
0
0
0
1
ö
÷
÷
÷
ř
(1.18)

Horizontální změna měřítka s koeficientem Mx:

Zápis pomocí souřadnic bodů:
x2
=
x1*Mx
(1.19)
y2
=
y1
(1.20)

Transformační matice:

Mhscale = ć
ç
ç
ç
č
Mx
0
0
0
1
0
0
0
1
ö
÷
÷
÷
ř
(1.21)

Vertikální změna měřítka s koeficientem My:

Zápis pomocí souřadnic bodů:
x2
=
x1
(1.22)
y2
=
y1*My
(1.23)

Transformační matice:

Mvscale = ć
ç
ç
ç
č
1
0
0
0
My
0
0
0
1
ö
÷
÷
÷
ř
(1.24)

Horizontální zešikmení (střih) s koeficientem Sx:

Zápis pomocí souřadnic bodů:
x2
=
x1+Sx*y1
(1.25)
y2
=
y1
(1.26)

Transformační matice:

Mhskew = ć
ç
ç
ç
č
1
0
0
Sx
1
0
0
0
1
ö
÷
÷
÷
ř
(1.27)

Vertikální zešikmení (střih) s koeficientem Sy:

Zápis pomocí souřadnic bodů:
x2
=
x1
(1.28)
y2
=
y1+Sy*x1
(1.29)

Transformační matice:

Mvskew = ć
ç
ç
ç
č
1
Sy
0
0
1
0
0
0
1
ö
÷
÷
÷
ř
(1.30)

Rotace okolo počátku o úhel a:

Zápis pomocí souřadnic bodů:
x2
=
x1*cos(a)-y1*sin(a)
(1.31)
y2
=
x1*sin(a)+y1*cos(a)
(1.32)
(1.33)

Transformační matice:

Mrotate = ć
ç
ç
ç
č
cos(a)
sin(a)
0
-sin(a)
cos(a)
0
0
0
1
ö
÷
÷
÷
ř
(1.34)

1.3.3  Transformační matice složených transformací

Tyto transformace vzniknou složením základních transformací. Operace se provede maticovým vynásobením matic jednotlivých transformací. Zde uvedené transformace jsou potřebné pro praktickou aplikaci základních transformací, neboť umožňují interaktivní zadávání transformací.

Jako příklad uveďme rotaci okolo zadaného bodu. Tato transformace je složená a má větší praktický význam, než základní transformace rotace okolo počátku, neboť ji lze aplikovat na libovolnou množinu bodů v ploše.

U složených transformací uvedeme pouze transformační matici, protože vzorce pro jednotlivé body lze jednoduše odvodit přímo z této matice.

Změna měřítka z bodu [px,py]

MscaleP = ć
ç
ç
ç
č
M
0
0
0
M
0
px(1-M)
py(1-M)
1
ö
÷
÷
÷
ř
(1.35)

Horizontální změna měřítka z bodu [px,py]

MHscaleP = ć
ç
ç
ç
č
Mx
0
0
0
1
0
px(1-Mx)
0
1
ö
÷
÷
÷
ř
(1.36)

Vertikální změna měřítka z bodu [px,py]

MVscaleP = ć
ç
ç
ç
č
1
0
0
0
My
0
0
py(1-My)
1
ö
÷
÷
÷
ř
(1.37)

Horizontální zešikmení z bodu [px,py]

MHskewP = ć
ç
ç
ç
č
1
1
0
Sx
1
0
-pxSx
0
1
ö
÷
÷
÷
ř
(1.38)

Vertikální zešikmení z bodu [px,py]

MVskewP = ć
ç
ç
ç
č
1
Sy
0
0
1
0
0
-pySy
1
ö
÷
÷
÷
ř
(1.39)

Rotace okolo bodu [px,py]

MrotateP = ć
ç
ç
ç
č
cos(a)
sin(a)
0
-sin(a)
cos(a)
0
px(1-cos(a))+pysin(a)
py(1-cos(a))-pxsin(a)
1
ö
÷
÷
÷
ř
(1.40)

1.3.4  Aplikace transformací na transformační matice

Pokud máme aplikovat nějakou transformaci na již existující transformační matici, musíme provést maticový součin mezi starou transformační maticí a maticí reprezentující danou transformaci. Nebudeme zde uvádět všechny možnosti, které mohou nastat, ale předvedeme pouze princip. Půjde o provedení transformace změny měřítka na starou transformační matici.

V dalších vzorcích bude A stará transformační matice, Aó nová transformační matice a Mscale matice reprezentující změnu měřítka.

Změna měřítka o koeficient Ms:

Aó = A*Mscale ć
ç
ç
ç
č
a11
a21
0
a12
a22
0
tx
ty
1
ö
÷
÷
÷
ř
* ć
ç
ç
ç
č
Ms
0
0
0
Ms
0
(1-M)*xs
(1-M)*ys
1
ö
÷
÷
÷
ř
(1.41)
Aó = ć
ç
ç
ç
č
a11*M
a21*M
0
a12*M
a22*M
0
tx*M+(1-M)*xs
ty*M+(1-M)*ys
1
ö
÷
÷
÷
ř
(1.42)

1.4  Výpočet pravděpodobnosti jednotlivých transformací

Jestliže už známe všechny transformace, které budou vytvářet IFS fraktál, zbývá nám ještě dopočítat k zadaným transformacím jim odpovídající pravděpodobnosti, s jakou budou tyto transformace použity při generování. Bylo by samozřejmě možné, aby všechny transformace měly stejnou pravděpodobnost, to by ale nebylo výhodné z hlediska generování fraktálu. Transformace, které jsou hodně kontrahující, to znamená, že mají nízké koeficienty v transformační matici, by iterované body příliš přitahovaly k atraktoru. Výsledkem by byl málo rozvinutý fraktál, pro jehož generování by bylo nutno použít příliš vysoký počet iterací.

Proto je vhodné, aby byla jednotlivým transformacím přiřazena určitá pravděpodobnost, s jakou tyto transformace nastanou, přičemž hodně kontrahující transformace budou mít menší pravděpodobnost než transformace kontrahující méně. Při výpočtu pravděpodobností musíme dbát na to, aby součet všech pravděpodobností byl roven jedné.

V tomto programu je použito 7 možností, jak vypočítat pravděpodobnosti jednotlivých transformací:

1.4.1  Výpočet pravděpodobnosti pomocí koeficientu kontrakce

Tato volba je používána ve všech programech, které umožňují modelovat a generovat IFS koláže. Pro běžné typy transformací dává dobré výsledky, to znamená, že rozložení pravděpodobností generované tímto vztahem, přibližně odpovídá ideálnímu rozložení.

Výhodou této metody je její jednoduchost, nevýhodou to, že některé pravděpodobnosti mohou vyjít nulové. To by znamenalo, že by se daná transformace nepodílela na generování fraktálu. Po aplikaci této metody tedy musíme ošetřit nulové pravděpodobnosti a přiřadit jim nějakou minimální nenulovou hodnotu.

Vyjdeme z transformační matice M, ze které spočítáme koeficient kontrakce podle vztahu:

koeficienti = a11i*a22i-a12i*a21i
(1.43)

Pravděpodobnost dané transformace i potom vypočteme jednoduše:

pi = koeficienti
(1.44)

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

Tato volba spočítá plochu základního objektu tak, jak ho zadal uživatel. Potom se na vrcholy základního objektu aplikuje daná transformace a pro nově vygenerované body se spočítá plocha nového objektu. Pravděpodobnost dané transformace se spočítá pomocí obsahů těchto dvou obrazců:

pi = plocha obrazce i
plocha zakladniho obrazce
(1.45)

Jde o nejpřesnější metodu pro výpočet pravděpodobností. Její nevýhodou je velká složitost z čehož plyne i časová náročnost. Také způsob výpočtu ploch obrazce nemusí vždy dát správné výsledky. To se stane v případě, kdy uživatel zadal určitým způsobem zdeformovaný tvar základního objektu, který má například dvě shodné hrany.

Výpočet obsahu objektu, který je zadaný seznamem svých vrcholů, z nichž každý vrchol má souřadnice [xn,yn], se provede pomocí algebraického součtu determinantů. Každý determinant je tvořen čtveřicí čísel, které jsou dány polohou dvou sousedních vrcholů na hranici objektu. Výsledná plocha je potom rovna polovině tohoto součtu:

P = 1
2
|D1+D2+...+Dn|
(1.46)

Di = ę
ę
ę
xi
xi+1
yi
yi+1
ę
ę
ę
(1.47)

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

Dn = ę
ę
ę
xn
x0
yn
y0
ę
ę
ę
(1.48)

1.4.3  Výpočet pravděpodobnosti z poměru obsahů opsaných obdélníků

Nejprve se vypočítají minimální a maximální souřadnice základního objektu:

xmin
=
min(xi)  "i Î < 1..n >
(1.49)
xmax
=
max(xi)  "i Î < 1..n >
(1.50)
ymin
=
min(yi)  "i Î < 1..n >
(1.51)
ymax
=
max(yi)  "i Î < 1..n >
(1.52)
(1.53)

Z těchto souřadnic se získá plocha obdélníka, který je opsaný základnímu objektu:

Sobd = (xmax-xmin)*(ymax-ymin)
(1.54)

Poté se pro každý vrchol základního objektu provede transformace a spočtou se nové minimální a maximální souřadnice pro transformovaný základní objekt:

xminó
=
min(xió)  "i Î < 1..n >
(1.55)
xmaxó
=
max(xió)  "i Î < 1..n >
(1.56)
yminó
=
min(yió)  "i Î < 1..n >
(1.57)
ymaxó
=
max(yió)  "i Î < 1..n >
(1.58)
(1.59)

Vypočteme plochu obdélníku, který je opsaný transformovanému objektu:

Sobdó = (xmaxó-xminó)*(ymaxó-yminó)
(1.60)

Výsledná pravděpodobnost dané transformace je dána vztahem:

pi = Sobdió
Sobd
(1.61)

Mohlo by se zdát, že by stačilo vypočítat ohraničující obdélník základního objektu a souřadnice vrcholů nového obdélníku získat transformací. Takový postup by nedával správný výsledek, neboť určité transformace by tento obdélník změnily na jiný tvar a vypočtený obsah by byl odlišný.

Tato metoda není tak přesná jako metoda předchozí. Její výhodou je jednoduchá implementace a jednoznačnost výsledků.

1.4.4  Výpočet pravděpodobnosti z poměru obsahů opsaných kružnic

Tato metoda se podobá metodě předchozí. Základní rozdíl je v tom, že se neprovádí obalení základního objektu obdélníkem ale kružnicí. Pro výpočet pravděpodobnosti se potom porovnají obsahy obalujících kružnic základního objektu a objektu transformovaného.

Střed obalující kružnice se vypočítá jako aritmetický průměr souřadnic vrcholů základního objektu:

xs
=
1
n
n
ĺ
i = 1 
xi
(1.62)
ys
=
1
n
n
ĺ
i = 1 
yi
(1.63)

Pro výpočet obsahu obalující kružnice potřebujeme znát i její poloměr. Poloměr se vypočte jako maximální vzdálenost středu obalující kružnice a souřadnic vrcholů základního objektu:

radius = max(   _______________
Ö(xs-xi)2+(ys-yi)2
 
)  "i Î < 1..n >
(1.64)

kde xi a yi jsou souřadnice i-tého vrcholu základního objektu.

Obsah obalující kružnice se nyní vypočte snadno:

Skruz = 2*p*radius
(1.65)

V druhém kroku nejprve provedeme transformaci všech vrcholů základního objektu. Dále zjistíme souřadnice středu nové kružnice:

xsó
=
1
n
n
ĺ
i = 1 
xió
(1.66)
ysó
=
1
n
n
ĺ
i = 1 
yió
(1.67)

Potom vypočteme poloměr kružnice, která obaluje tento nový objekt:

radiusó = max(   ___________________
Ö(xsó-xió)2+(ysó-yió)2
 
)  "i Î < 1..n >
(1.68)

kde xió a yió jsou souřadnice i-tého vrcholu transformovaného objektu.

Obsah nové obalující kružnice:

Skruzó = 2*p*radiusó
(1.69)

Výsledná pravděpodobnost dané transformace je dána:

pi = Skruzió
Skruz
(1.70)

Tato metoda má stejné vlastnosti jako metoda předchozí. Výsledky se samozřejmě mohou lišit, neboť jde o odlišný způsob výpočtu. Výhodou je, že se počítají správně 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 obdélníku byl blízký nule, ale v této metodě se díky způsobu výpočtu poloměru dosáhne uspokojivých výsledků.

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

Tato metoda využívá pro výpočet pravděpodobnosti koeficient zkrácení úsečky. Pro zjednodušení výpočtů neuvažujeme libovolnou úsečku. Výpočet se provede pro úsečku, která vychází z bodu [0,0] do bodu [1,1]. V tomto případě lze vzorec pro výpočet pravděpodobnosti i-té transformace přímo odvodit.

Zadané hodnoty:

x0
=
0
(1.71)
y0
=
0
(1.72)
x1
=
1
(1.73)
y1
=
1
(1.74)

Hodnoty vypočtené po aplikaci transformace:

x0ó
=
a11x0+a12y0+tx
(1.75)
y0ó
=
a21x0+a22y0+ty
(1.76)
x1ó
=
a11x1+a12y1+tx
(1.77)
y1ó
=
a21x1+a22y1+ty
(1.78)

Do těchto vztahů dosadíme hodnoty x0,x1,y0 a y1:

x0ó
=
a110+a120+tx = tx
(1.79)
y0ó
=
a210+a220+ty = ty
(1.80)
x1ó
=
a111+a121+tx = a11+a12+tx
(1.81)
y1ó
=
a211+a221+ty = a21+a22+ty
(1.82)

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

d
=
  _______________
Ö(x1-x0)2+(y1-y0)2
 
=
(1.83)
=
  ___________
Ö(1-0)2+(1-0)2
 
= Ö2
(1.84)

Délka transformované úsečky se vypočítá pomocí transformovaných bodů:

dó
=
  ___________________
Ö(x1ó-x0ó)2+(y1ó-y0ó)2
 
=
(1.85)
=
Ö
(a11+a12+tx-tx)2+(a21+a22+ty-ty)2
 
=
(1.86)
=
Ö
(a11+a12)2+(a21+a22)2
 
=
(1.87)
=
Ö
a112+2a11a12+a122+a212+2a21a22+a222
 
=
(1.88)
=
Ö
a112+a122+a212+a222+2a11a12+2a21a22
 
(1.89)

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

pi
=
dó
d
(1.90)
pi
=
Ö
a112+a122+a212+a222+2a11a12+2a21a22
 

Ö2
(1.91)
pi
=
  ć
 ú
Ö

a112+a122+a212+a222
2
+a11a12+a21a22
 
(1.92)

Tato metoda je jednoduchá pro výpočet, ale má některé nevýhody. První nevýhodou je, že úsečka je jednorozměrná. To znamená, že pravděpodobnost je přímo úměrná změně délce úsečky. Přesnější výsledky dávají metody, které pravděpodobnost počítají jako změnu obsahu nějakého útvaru. Rozdíl je tedy v lineárním či kvadratické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. Tato hodnota je přesnější, neboť základní objekt pokryjeme čtyřmi objekty, z nichž každý je zmenšený na polovinu.

Druhou nevýhodou této metody je, že počítá 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ě, že chceme spočítat výslednou pravděpodobnost. 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 aritmetický.

Pro co nejpřesnější výpočet můžeme 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 tedy provést integrace, aby se zjistil obsah této kružnice:

obsah = ó
ő
2p

0 
Ö
cos2f+sin2f
 
 df
(1.93)

Poté se vypočte obsah objektu, který vznikne rotací vektoru po transformaci. Obecně musí vyjít elipsa:

obsahó = ó
ő
2p

0 
Ö
(cosf*a11+sinf*a12+tx)2+(cosf*a21+sinf*a22+ty)2
 
 df
(1.94)

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

pi = obsahó
obsah
(1.95)

Jak je z předchozích vztahů vidět, tento způsob výpočtu pravděpodobnosti je velmi komplikovaný a časově náročný. Přitom neodstraňuje základní nevýhodu této metody, tj. lineární závislost pravděpodobnosti na změně měřítka.

1.4.6  Uniformní rozdělení pravděpodobností

Pravděpodobnost jedné transformace je v tomto případě rovna:

pi = 1
n
 "i Î < 1..n >
(1.96)
kde n je počet všech transformací.

Všechny transformace tedy mají 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.

1.4.7  Zadání pravděpodobností uživatelem

V tomto případě jednotlivé pravděpodobnosti zadává přímo uživatel. Program potom zajistí, aby byl součet všech pravděpodobností roven jedné a aby žádná pravděpodobnost nebyla nulová.

Při tomto způsobu zadávání pravděpodobností můžeme otestovat, jaký fraktál bude generován při různých poměrech jednotlivých pravděpodobností. Z výsledků můžeme vidět, že se tvar výsledného fraktálu nezmění. Změní se jen hustota bodů na některých místech fraktálu.

Můžeme tedy učinit závěr, že transformační matice udává tvar výsledného fraktálu a pravděpodobnost transformace udává hustotu bodů při aplikaci této transformace.

1.4.8  Závěr

V této části jsme popsali některé možnosti výpočtu pravděpodobností jednotlivých transformací. Je nutné připomenout, že zatímco transformační matice je přesně zadaná a odpovídá tomu, co zadal uživatel, výpočet pravděpodobnosti není jednoznačný.

První nejednoznačnost vyplývá z vlastního výpočtu pravděpodobnosti. V tomto případě je nejpřesnější metoda, která porovná plochu základního objektu a transformovaného objektu. Tato metoda počítá přímo ze zadaných dat základního objektu (souřadnice vrcholů) a ne pouze z transformačních matic.

Druhá nejednoznačnost nastane, není-li základní objekt zcela přesně pokryt transformovanými objekty. V tom případě nebude po základním výpočtu součet všech pravděpodobností roven jedné. Program samozřejmě provede takovou úpravu, aby byl součet roven jedné, jinak by nebylo možné provést generování IFS koláže.

Problémem však je, jak upravit jednotlivé pravděpodobnosti, aby byl součet jednotkový. Můžeme část zbývající do jedné rozdělit rovnoměrně mezi všechny pravděpodobnosti, nebo můžeme rozdělení provést tak, že zohledníme hodnotu jednotlivých pravděpodobností. Žádná z těchto možností není přesná, neboť u špatně provedeného pokrytí základního objektu neexistuje přesný vztah mezi transformací a její pravděpodobností. Tento vztah platí pouze u přesného pokrytí, tj. transformované objekty úplně pokryjí základní objekt, přičemž se tyto objekty navzájem nepřekrývají.

Všechny tyto skutečnosti se musí zohlednit při porovnávání pravděpodobností, které vznikly výpočtem podle různých metod.

1.5  Algoritmus výpočtu IFS kódu

1.5.1  Neformální popis algoritmu

Algoritmus výpočtu IFS kódu je v tomto programu velmi jednoduchý, protože jsou v programu přímo uloženy jednotlivé transformace. Není tedy nutno pro každé zobrazení IFS koláže počítat koeficienty transformační matice. Algoritmus tedy může vypadat následovně:

Výpočet sumy pravděpodobností je nutný, aby se zaručilo, že součet všech pravděpodobností v IFS bude roven jedné. To se provede tak, že se spočítá suma všech vypočítaných pravděpodobností. Obecně může vyjít libovolné kladné reálné číslo. Touto sumou potom podělíme jednotlivé pravděpodobnosti. Po této operaci je nová suma všech pravděpodobností rovna jedné, tak jak to vyžaduje vykreslovací algoritmus i definice IFS.

1.5.2  Zjištění typu transformace

Zajímavý je bod 3, který zjišťuje, zda je daná transformace kontrakcí. Transformace mohou být, jak již bylo řečeno, obecně trojího druhu:

Kontrahující transformace je taková transformace, která po provedení operace na úsečku zkrátí její délku. Úsečku si můžeme představit jako dva body, jejichž vzdálenost měříme. Po provedení transformace se musí tato vzdálenost zmenšit.

Extrahující transformace naopak úsečku natahuje, to znamená, že se body od sebe vzdalují. Symetrie je na hranici mezi kontrakcí a extrakcí, zachovává tedy délku úsečky i vzdálenosti jednotlivých bodů. Mění se tedy pouze poloha těchto bodů v rovině a jejich vzájemná orientace.

Typ transformace můžeme vypočítat přímo z transformační matice M dané transformace pomocí jednoduchého vztahu:

koeficient = a11a22-a12a21
(1.97)

Hodnota koeficientu udává, o jaký typ transformace se jedná:

Z definice IFS plyne, že transformace použité v IFS mohou být pouze kontrakcemi, v krajním případě symetriemi. Uživatel má možnost otestovat jím zadané transformace, do jakých kategorií patří. Lze generovat i fraktál, který obsahuje extrakci, pak už to však není IFS, protože neodpovídá definici (také nemusí jít o fraktál, protože zde může být atraktorem pouze nekonečno). Může nastat i matematická chyba v programu v důsledku počítání s příliš velkými čísly. V každém případě je však možnost práce s extrakcemi umožněna, protože jde o program určený k studijní činnosti a ne o komerční produkt chráněný proti všem špatným vstupům.

Obsah

1  Vytváření IFS kódu
    1.1  Základy lineární algebry a maticový počet
        1.1.1  Lineární algebra
        1.1.2  Maticový počet
        1.1.3  Lineární transformace
        1.1.4  Afinní transformace
    1.2  Vytvoření základního objektu a jeho pokrytí
    1.3  Výpočet transformačních matic
        1.3.1  Reprezentace transformace jedinou maticí
        1.3.2  Transformační matice základních transformací
            Posun bodu o vektor [px,py]:
            Změna měřítka s koeficientem Ms:
            Horizontální změna měřítka s koeficientem Mx:
            Vertikální změna měřítka s koeficientem My:
            Horizontální zešikmení (střih) s koeficientem Sx:
            Vertikální zešikmení (střih) s koeficientem Sy:
            Rotace okolo počátku o úhel a:
        1.3.3  Transformační matice složených transformací
            Změna měřítka z bodu [px,py]
            Horizontální změna měřítka z bodu [px,py]
            Vertikální změna měřítka z bodu [px,py]
            Horizontální zešikmení z bodu [px,py]
            Vertikální zešikmení z bodu [px,py]
            Rotace okolo bodu [px,py]
        1.3.4  Aplikace transformací na transformační matice
    1.4  Výpočet pravděpodobnosti jednotlivých transformací
        1.4.1  Výpočet pravděpodobnosti pomocí koeficientu kontrakce
        1.4.2  Výpočet pravděpodobnosti z poměru obsahů generovaných obrazců
        1.4.3  Výpočet pravděpodobnosti z poměru obsahů opsaných obdélníků
        1.4.4  Výpočet pravděpodobnosti z poměru obsahů opsaných kružnic
        1.4.5  Výpočet pravděpodobnosti z koeficientu zkrácení úsečky
        1.4.6  Uniformní rozdělení pravděpodobností
        1.4.7  Zadání pravděpodobností uživatelem
        1.4.8  Závěr
    1.5  Algoritmus výpočtu IFS kódu
        1.5.1  Neformální popis algoritmu
        1.5.2  Zjištění typu transformace


File translated from TEX by TTH, version 2.25.
On 16 Nov 1999, 22:40.


Předchozí kapitola Další kapitola Obsah Úvodní stránka Domácí stránka E-mail