Iteriertes Funktionensystem

Methode zum Konstruieren selbstähnlicher Fraktale
(Weitergeleitet von Iteriertes Funktionen-System)

Ein iteriertes Funktionensystem (IFS) ist eine Menge von Funktionen, die denselben Raum als Definitions- und Wertebereich haben und unter Verknüpfung abgeschlossen sind. Also

d. h.

Iterierte Funktionensysteme dienen meist der Konstruktion von Fraktalen, die dann auch als IFS–Fraktale bezeichnet werden. Bekannte Vertreter dieser Klasse von Fraktalen sind das Sierpinski-Dreieck und die Koch-Kurve wie auch die Grenzmengen von Lindenmayer-Systemen.

Diese Art der Fraktalkonstruktion wurde 1981 von John Hutchinson erfunden[1] und später von Michael F. Barnsley mit seinem Buch Fractals Everywhere[2] popularisiert.[3] Dort gab Barnsley auch den Collage-Satz an, welcher die Grundlage der fraktalen Bildkompression bildet. Diese Art, Bilder effizient mittels Datenstrukturen zu kodieren, hat sich jedoch nie richtig durchsetzen können und wird heute im Wesentlichen nur noch als Hybridverfahren in Kombination mit einer Wavelet-Transformation untersucht.

Invariante, selbstähnliche Mengen Bearbeiten

Um für ein IFS Eigenschaften ableiten zu können, muss die Funktionenmenge zusätzliche Voraussetzungen erfüllen. Üblicherweise, wenn von IFS gesprochen wird, werden diese Voraussetzungen stillschweigend als gegeben angenommen. Diese Voraussetzungen sind

  1. dass das IFS endlich erzeugt ist, also endlich viele Funktionen enthält, aus welchen die anderen durch wiederholte (iterierte) Verknüpfung zusammengesetzt werden können,
  2. dass der Raum   ein vollständiger metrischer Raum mit Metrik   ist, und
  3. dass jede Funktion des IFS kontraktiv bezüglich   ist. Mit Voraussetzung 1. reicht es, dies von den Erzeugenden zu verlangen.

Unter diesen Umständen gibt es eine invariante, selbstähnliche Menge  .

  • Die Teilmenge   ist invariant, wenn sie von jeder Funktion des IFS wieder in sich abgebildet wird.
  • Die Teilmenge   ist selbstähnlich, wenn jeder Punkt aus   in der Bildmenge   einer Funktion   liegt.

Selbstähnliche Mengen haben meist keine ganzzahlige Hausdorff-Dimension und werden dann auch als Fraktal bezeichnet, deshalb die Bezeichnung IFS-Fraktal. Man könnte auch weitergehend den Begriff der Selbstähnlichkeit durch die Forderung der Existenz eines IFS definieren.

Existenz und Eindeutigkeit der invarianten Menge Bearbeiten

Mathematisch gesehen handelt es sich bei der Theorie der iterierten Funktionensysteme, wie auch die Begrifflichkeit vermuten lässt, um eine direkte Anwendung des banachschen Fixpunktsatzes, wobei mehrere Funktionen statt einer betrachtet werden und, statt eines eindeutigen Fixpunktes, sich eine invariante, meist fraktale, Teilmenge des Raumes   ergibt. Zur Illustration wird meist das zweidimensionale Einheitsquadrat   mit dem euklidischen Abstand gewählt.

Wir beginnen also mit einer endlichen Menge von Funktionen eines kompakten metrischen Raumes   in sich selbst:

 

von denen wir voraussetzen, dass es eine Kontraktionskonstante   gibt mit

 

Durch Iteration setzen wir   zu einem IFS   fort, es sei

 

und erhalten schließlich

 .

Satz: Sind alle Funktionen   in   kontraktiv, so gibt es eine invariante Teilmenge  , welche die Fixpunktgleichung

 

erfüllt. Für diese gilt:

  • Zu jedem   gibt es genau einen Fixpunkt. Die invariante Menge   ist der topologische Abschluss der Menge aller Fixpunkte
 .
  • Ist   ein beliebiger Punkt, so gilt für den Abstand dieses Punktes
  für jedes  .
Es gilt die Abschätzung  , falls   eine  -fache Verkettung   der Ausgangsfunktionen ist.
  • Damit kann   durch Iteration einer beschränkten Ausgangsmenge
 
beliebig gut angenähert werden.

Der Beweis des Satzes erfolgt dadurch, dass man aus dem metrischen Raum   einen neuen Raum konstruiert, dessen „Punkte“ genau die kompakten Teilmengen von   sind. Hierauf kann man eine Metrik definieren (die Hausdorff-Metrik), bezüglich der dieser Raum vollständig und die Abbildung   eine Kontraktion ist. Dadurch wird der banachsche Fixpunktsatz anwendbar.

Approximation der Grenzmenge Bearbeiten

Chaosspiel Bearbeiten

Die Gestalt der fraktalen Menge   kann durch ein so genanntes Chaosspiel visualisiert werden. Dabei wird zunächst ein Fixpunkt   von   aufgesucht und auf diesen in zufälliger Reihenfolge die definierenden Funktionen angewandt. Als Algorithmus kann dies wie folgt aussehen:

  • Weise 100 mal hintereinander   zu
  • Wiederhole beliebig oft
    • Wähle zufällig ein  
    • Weise   zu
    • Zeichne den Punkt  .

Anmerkung:

  1. Es ist in den ersten, blinden, Iterationen unwesentlich, welche Funktion gewählt wird, da in jedem Schritt der Abstand zur fraktalen Menge   reduziert wird. Ist z. B. die Kontraktionskonstante   und die Grundmenge   das Einheitsquadrat, welches mit 1024×1024 Pixeln dargestellt wird, so ist bereits nach 12 blinden Iterationen der Fehler unter die Pixelgröße gesunken.
  2. Es werden im Allgemeinen bessere Darstellungen erzielt, wenn die Wahrscheinlichkeit des Aufrufs jeder der Funktionen   in etwa proportional zum Volumen von   ist.

Rekursion Bearbeiten

Eine weitere Möglichkeit der Darstellung, vorzugsweise für die affinen Fraktale, ist die rekursive Approximation der Menge  . Dies wird meist anschaulich mittels eines Fotokopierers erklärt: Man macht verschiedene Verkleinerungen eines Ausgangsbildes, fixiert diese nach Vorschrift auf einem neuen Blatt und benutzt dieses dann als Ausgangsbild des nächsten Schrittes.

Auch die Turtle-Grafik, die zur Konstruktion der L-Systeme verwendet wird, folgt einer ähnlichen Idee.

Als Algorithmus braucht man dazu eine rekursiv aufrufbare Funktion, welche die Zuordnung   bei einer beliebigen Menge   realisiert. Die Implementierung benötigt einen Stackspeicher, in welchem das jeweils aktuelle Koordinatensystem als affine Koordinatentransformationen festgehalten wird. Damit ergibt sich als Algorithmus

 
Das Koch-Fraktal in den Rekursionstiefen 0 bis 5

 :

  • Falls  
    • zeichne die Basisfigur (z. B. eine Strecke, einen Buchstaben, ein schwarzes Rechteck)
  • sonst:
    • Für   bis  
      • Lege aktuelles Koordinatensystem auf Stack ab
      • Transformiere das aktuelle Koordinatensystem entsprechend  
      • Rufe   auf
      • Stelle Koordinatensystem vom Stack wieder her

Fraktal:

  • Rufe   auf (10 als Beispiel)

Beispiele für iterierte Funktionensysteme Bearbeiten

Affine Abbildungen Bearbeiten

Die erzeugenden Funktionen des IFS seien affine Abbildungen des zweidimensionalen Einheitsquadrates in sich selbst. Jede Funktion   ist gegeben durch eine 2×2–Matrix   und einen Verschiebungsvektor  .

Das Koch-Fraktal wird z. B. von folgendem System von 2 Funktionen erzeugt:

  •  ,
  •  

Die klassische Methode zur Erzeugung der Koch-Kurve benutzt 4 Funktionen

  •  
  •  
  •  
  •  

Das rechtwinklige Sierpinski-Dreieck wird erzeugt von

  •  
  •  
  •  

Collagen Bearbeiten

Grundlage für die Begeisterung für solche IFS–Fraktale war das Collage–Theorem von Barnsley. Es besagt, dass jede kompakte Menge – jede Gestalt – durch ein IFS–Fraktal beliebig genau angenähert werden kann. Die Grundlage dafür sind folgende Beobachtungen:

1. Jede endliche Menge ist ein IFS–Fraktal. Die zugehörigen Funktionen sind diejenigen konstanten Funktionen, welche den gesamten Raum auf jeweils einen der endlich vielen Punkte abbilden.

2. Jede kompakte Menge   hat für jedes   ein  -Netz, wird also durch endlich viele Kugeln vom Radius   überdeckt.

⇒ Das IFS–Fraktal der Kugelmittelpunkte enthält die Ausgangsmenge in einer  -Umgebung

Anschaulicher: Haben wir in einem 100×100–Pixelbild eine Figur von 500 schwarzen Pixelpunkten, so können wir das Bild um den Faktor 100 auf die Größe eines Pixels verkleinern und mit diesem einen schwarzen Punkt dann wieder die Figur malen, indem wir ihn auf jeden der zugehörigen 500 Pixel abbilden. Diese Vorgehensweise ist bei weitem nicht optimal, hier wäre das einfache Speichern der Positionen der 500 Pixel einfacher. Aber wenn wir für den gleichen Zweck mit nur fünf Abbildungen auskämen, wäre eine Datenreduktion erzielt.

Wir sind auch nicht auf einfache Schwarzweißbilder eingeschränkt. Bei einem Graustufenbild kann der Grad der Schwärzung als dritte Koordinate des Punktes aufgefasst werden, es ergibt sich eine kompakte Fläche im dreidimensionalen Raum, auf welche wieder das Collage–Theorem angewendet werden kann. Mit systematischen Verfahren zur Konstruktion eines IFS–Fraktals mit möglichst wenigen Funktionen befasst sich die Fraktale Bildkompression sowie die Fraktale Tonkompression.

Weblinks Bearbeiten

Commons: Iterierte Funktionensysteme – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise Bearbeiten

  1. John E. Hutchinson: Fractals and self similarity. In: Indiana University Mathematics Journal. Band 30, Nr. 5, 1981 (semanticscholar.org [PDF; 483 kB]).
  2. Michael Barnsley: Fractals Everywhere. Academic Press, 1988, ISBN 978-0-12-079062-3.
  3. Mario Peruggia: Discrete Iterated Function Systems. Taylor & Francis, CRC Press, 1993, ISBN 978-0-429-06536-1, S. ix,xi, doi:10.1201/9781439864708.