Viele in der Natur vorkommende Strukturen weisen eine starke Selbstähnlichkeit auf. Beispiele dafür sind Gebirgsformationen, Meeresküsten oder Blätter von Pflanzen. Solche in sich wiederholende Muster, die quasi beim Hereinzoomen immer wieder zutage treten, lassen sich ausnutzen, wenn man ein umfangreiches Gebilde durch ein kleines Erzeugendensystem darstellen möchte. Sogenannte Iterierte Funktionensysteme sind z.B. in der Lage, mit wenigen Regeln komplexe und natürlich aussehende Bilder zu generieren. Abbildung 7 zeigt das Blatt eines Farns, welches durch die wiederholte Anwendung von vier affinen Abbildungen entstanden ist.
Bild 7: Farn mit Selbstähnlichkeit
|
Nach dieser Vorlage ist die Idee der fraktalen Kompression entstanden. Ausgehend von einer gescannten Bildvorlage werden Regelmäßigkeiten und Selbstähnlichkeiten gesucht und dadurch der Bildinhalt als Fixpunkt eine iterierten Anwendung von Transformationsmatrizen definiert.
In stark vereinfachter Form läuft das Verfahren folgendermaßen ab: Zunächst wird das Bild in sogenannte Domainblöcke partitioniert. Zu jedem Domainblock wird nun ein Rangeblock gesucht, dessen Abbild unter einer affinen Abbildung dem Inhalt des Domainblocks möglichst nahe kommt. Erforderlich für diesen Schritt ist natürlich die Wahl einer geeigneten Metrik, die den Abstand von zwei Pixelmengen definiert. Affine Abbildungen erlauben einfache geometrische Transformationen wie Drehung, Skalierung und Translation. Je nach zugestandener Zeitvorgabe kann der Suchalgorithmus mehr oder weniger viele Rangeblockpositionen mit mehr oder weniger vielen affinen Abbildungen ausprobieren. Zur Vereinfachung beschränkt er sich auf eine feste Zahl möglicher Transformationsmatritzen sowie feste Rangeblockgrößen, die an den Eckpunkten eines 2-dimensionalen Gitters fester Gittergröße positioniert sind.
Abbildung 8 zeigt, wie die Vorlage G zunächst mit 4 Domainblöcken überdeckt wird und dann der Inhalt jedes Domainblocks durch eine affine Transformation des zugehörigen Rangeblocks dargestellt wird (in diesem Beispiel sind zufällig alle Rangeblöcke identisch).
Bei der Dekompression eines fraktalen Bildes werden nun, beginnend mit einem zufälligen Bildinhalt, die Transformationsmatritzen solange angewendet, bis sich keine Änderung gegenüber der Vorgängeriteration mehr ergibt. Gewisse mathematische Randbedingungen, die bei der Wahl der Matritzen einzuhalten sind, garantieren, daß es einen Fixpunkt gibt, auf den das Verfahren konvergiert.
Kompressionsrate 72:1 |
Kompressionsrate 71:1 |
Das Verfahren sieht auf den ersten Blick wie eine typisch akademische Spielerei aus, bei der ein recht eleganter Algorithmus zwar (verblüffenderweise) eine gegebene Vorlage reproduzieren kann, aber ohne praktischen Nutzen scheint. Weit gefehlt ! Die entscheidende Überlegenheit zu den konventionellen Bildkompressionsverfahren liegt in der Auflösungsunabhängigkeit. Nach dem Digitalisieren der Vorlage ist der Bildinhalt in eine Menge von Transformationsmatritzen gegossen. Diese können bei ihrer iterierten Anwendung Bilder jeder gewünschten Auflösung erzeugen, da sie jedes Bildstück nicht durch endlich viele Pixel beschreiben, sondern durch mathematische Beziehungen. Daher läßt sich aus demselben fraktalen Bild sowohl ein briefmarkengroßes Thumbnail als auch ein hochwertiges Poster generieren. Insbesondere kann man in ein fraktales Bild beliebig hereinzoomen, ohne daß die gefürchteten Klötzchen entstehen. Abbildung 9 zeigt, daß das generierte Bild qualitativ besser sein kann als die eingescannte Vorlage, weil die durch das Digitalisieren entstandenen Rasterpunkte im Fixpunkt der Transformationen weggemittelt werden.
Fraktal komprimierte Bilder haben sich in den Web-Browsern bisher nicht durchsetzen können. Zum einen, weil der Komprimierungsaufwand deutlich höher ist als bei GIF und JPEG. Zum andern kann der Vorteil der Auflösungsunabhängigkeit erst dann voll ausgespielt werden, wenn ein analoges Foto (hinter einer analogen Linse), ohne den Umweg über das digitale Abtasten direkt in die beschreibenden Transformationsmatritzen umgewandelt werden könnte.
924 Pixel