C&F IFS Iterierte Funktionssysteme

[Dipl Phys Ernst Winter]

IFS: Iterierte Funktionensysteme
Die klassischen fraktalen 'Monster'-Kurven können erzeugt werden, indem in jeder Stufe alle Strecken nach der Vorschrift eines Generators durch einen Polygonzug aus kürzeren Strecken ersetzt werden. Durch sukzessives Wiederholen wird das Fraktal angenähert: Fraktal-Generator.
Iterierte Funktionensysteme (IFS) verallgemeinern dieses rekursive Verfahren. Ein Anfangsbild wird in jeder Stufe durch kontrahierende affine Transformationen in eine Reihe von verkleinerten Bildern zerlegt. Das Verfahren wird mit diesen wiederholt, bis das Anfangsbild zur Größe eines Pixels verkleinert und im Bild nicht mehr sichtbar ist. Das Ergebnis ist vom Anfangsbild unabhängig und durch die verwendeten affinen Transformationen eindeutig bestimmt:
IFS beschreiben Bilder durch einen Satz von affinen Transformationen.
Mit wenigen Transformationen können detailreiche Bilder beschrieben werden.
Affine Transformation
Die allgemeinste lineare Transformation des Punktes P(x, y) in den Punkt Q(u, v)
u = a11x + a12y + b1
v = a21x + a22y + b2
bezeichnen wir als affine Transformation. Sie enthält 6 Koeffizienten und bildet Geraden in Geraden ab.
Eine affine Abbildung ist durch die Abbildung von drei Punkten eines Dreiecks eindeutig bestimmt. Dabei kann ein Dreieck auf jedes andere abgebildet werden. Durch eine affine Transformation kann ein Bild skaliert, gescheert, gespiegelt, gedreht und verschoben werden.
Eine affine Abbildung ist kontrahierend, wenn der umbeschriebene Kreis des transformierten Bildes kleiner als der umbeschriebene Kreis des Ausgangsbildes ist.
KonvergenzDie rekursive Erzeugung eines Bildes beginnt mit einem in die Zeichenfläche einbeschriebenem Anfangsbild und endet, wenn das IFS dieses auf die Größe eines Pixels zusammengezogen hat. Beträgt die Kontraktion wie beim Sierpinski-Dreieck 50%, so benötigt man etwa 10 Stufen, die mit erträglichem Aufwand rekursiv gezeichnet werden können.
Bei den Farnen ist in Stufe 10 das verkleinerte Dreieck des Anfangsbildes noch deutlich zu erkennen. Ursache ist die geringere Kontraktion der Bilder, die die Spitze nur auf etwa 85% verkleinert. Mit der Höhe des Anfangsdreiecks h = 524 können wir abschätzen, daß Stufe 39 für das Endbild benötigt wird. Das rekursive Verfahren müßte
M = 1 + 4 + 4^2 + 4^3 + ... + 4^N = (4^(N+1) -1)/3
Dreiecke berechnen. Das sind für N = 39 etwa 3*10^23. Selbst ein Supercomputer, der 1 Million Dreiecke je Sekunde berechnet, würde hierfür 10^10 Jahre (was dem geschätzten Lebensalter unserer Welt entspricht) benötigen. Dieses ist ein Beispiel für ein mathematisch komplexes Problem, das zwar prinzipiell lösbar ist, dessen Lösung jedoch in vielen Fällen am Rechenaufwand scheitert.
Chaos-Spiel
Das Chaos-Spiel nach M.F. Barnsley erzeugt das Bild der IFS als Folge von gesetzten Punkten. Wir beginnen diese Folge mit einem beliebigen Punkt . Mit einem Zufallsgenerator wählen wir eine der Transformationen aus dem IFS aus, mit der wir den Punkt transformieren. Mit diesem Punkt wiederholen wir das Verfahren. Die Menge dieser Punkte nähert das Bild der IFS an.
Das Bild des Sierpinki-Dreiecks ist mit 100000 Punkten nahezu vollkommen. Das Bild des Farns bleibt mit Millionen von Punkten unvollkommen. Durch Wichtung des Zufallsgenerators kann die Zahl der notwendigen Punkte für jedes IFS jedoch drastisch verringert werden.
Obwohl das Problem der 'besten' Optimierung des Zufallsgenerators für ein IFS immer noch ungelöst ist, gibt es Rezepte für die Auswahl 'günstiger' Wahrscheinlichkeiten. Das Programm verwendet ein sehr einfaches Verfahren von Bernslay.