Anwendungen zu Fraktalen

Fraktale Bildkompression

Die fraktale Bildkompression ist ein Verfahren zur Kompression von Digitalbildern, bei dem die Selbstähnlichkeit in den Bildern benutzt wird.

Entstehung der fraktalen Bildkompression

Bei der SIGGRAPH-Tagung 1985 in Kalifornien erregte Michael Barnsley großes Aufsehen. Es war ihm und seinem Team gelungen, mit Hilfe von vier einfachen affinen Abbildungen ein realistisches Bild von einem Farnblatt zu erzeugen. Barnsley sagte zu seiner Entdeckung: »Das Bild war verblüffend, es stimmte in allen Einzelheiten mit dem Original überein. Kein Biologe hätte Schwierigkeiten, den Farn zu bestimmen.«

Von 1988 bis 1990 entwickelten Michael Barnsley und sein Doktorand Arnaud Jacquin an der mathematischen Fakultät des Georgia Institute of Technology eine Methode der fraktalen Bildkompression, die sogenannten Iterierten Funktionensysteme. Barnsley patentierte 1991 den Algorithmus und gründete am 28. Mai 1991 gemeinsam mit Alan Sloan die Firma »Iterated Systems«. Im Jahr 1997 erwarb die »Altamira Group« die Lizenz an der IFS-Technologie und veröffentlichte die erste Version von Genuine Fractals, ein Programm zur Kompression von Bildern. Das zugrundeliegende Format FIF (Fractal Image Format) erzielte zwar hervorragende Kompressionsraten, die Kodierung war jedoch sehr langsam - zu langsam für die damaligen Computer. Trotzdem gewann die Version 1.0 den »MacWorld Eddy Award« 1997 als bestes grafisches Plug-In. Zudem errang Genuine Fractals PrintPro 1998 erneut einen »Eddy Award«, diesmal in der Kategorie »Best publishing utility«. 1998 entwickelte »Iterated Systems« das Grafikformat STiNG, das auf HAAR-Wavelets basiert. 2001 erwarb LizardTech das Produkt, 2005 schließlich onOne Software. Der Nachfolger von »Iterated Systems«, »MediaBin« wurde inzwischen vom Content-Management-Hersteller Interwoven aufgekauft.
Quellen: World Press Photo und Edgar®Online

Auf IFS basierende Software

Genuine Fractals Print Pro von »onOne Software« stellt in erster Linie das von »Iterated Systems« entwickelte, fraktal arbeitende Kompressionsverfahren zur Verfügung. Als Plug-In integriert es sich in die Öffnen- und Speichern-Als-Dialoge von Adobe Photoshop und unterstützt sowohl die Formate FIF als auch STN. In zweiter Linie ist es ein Skalierungs-und Clippingwerkzeug, denn beim Öffnen des speziellen Dateiformats namens STiNG (Endung .STN) lassen sich Bildausschnitt, gewünschte Auflösung und Bildgröße festlegen. Genuine Fractals ermöglicht es, unabhängig von der Auflösung Bilder beliebiger Größe und Ausdrucke ohne Qualitätsverlust zu erstellen. Bei der Vergrößerung der Auflösung eines Bildes müssen neue Pixel erzeugt werden. Die verwendete Skalierungsmethode bestimmt die Farbwerte dieser neuen Pixel. Die herkömmliche bikubische Interpolation beachtet die Werte umliegender Pixel und generiert angepasste Farbtonwerte. Der von Genuine Fractals verwendete Algorithmus arbeitet anders. Er analysiert ständig abnehmende Größen von Pixelblöcken im Bild und sucht nach sich wiederholenden Mustern unterschiedlicher Größe. Diese als Fraktale bekannten Muster können überall gefunden werden. Zum Beispiel hat ein Fluss-System, das vom Weltraum aus gesehen wird, die gleiche Form wie die Adern in einem Blatt. Beides sind fraktale Muster unterschiedlicher Größe. Diese Technik erlaubt es, Bilder auf bis zu 700% zu vergrößern, ohne dass ein Verlust an Schärfe damit einhergeht. Bei Verwendung von Genuine Fractals erhält man ein neues Bild, das weit mehr dem Original gleicht als eine Vergrösserung im PSD-Format (PhotoShop Document). Auch Microsoft Encarta benutzt das Dateiformat FIF.
Quelle: Ralph Altmann

Das Prinzip der fraktalen Bildkompression

Die Idee beruht auf Iterierten Funktionensystemen. Hier werden komplexe Abbildungen mit einer Menge von affinen Abbildungen des Bildes in sich selbst erstellt. Einfache Beispiele sind zum Beispiel Farne oder Wolken. Sucht man sich ein bestimmtes Merkmal der Wolke heraus, so wird man immer eine Stelle finden können, die dieser sehr ähnelt, und nur ein bisschen größer, gedreht, heller, oder gestaucht ist (siehe Abbildung). Um ein beliebiges Bild konstruieren zu können, muss eine Menge von Flächen (F₁...F_n) gesucht werden, die, wenn sie vereinigt werden, das gesamte Bild abdecken, sich paarweise aber nicht überschneiden dürfen. Für jede dieser Flächen F_i muss eine andere Fläche G_i im Bild gefunden werden, die dieser Fläche möglichst ähnlich sieht. Dabei können Transformationen, wie Kontrast- und Helligkeitsanpassungen, Rotation, Skalierung, ..., vorgenommen werden. Die Suche nach einem möglichst kleinen Satz solcher Flächen mit den dazugehörigen Parametern zur Abbildung ist extrem aufwändig. Die Rekonstruktion eines Bildes erfolgt in Schleifen. Es wird mit einem beliebigen Bild der Zielgröße begonnen. Dann werden alle Abbildungen durchgeführt. Das Ergebnis ist ein Bild, das dem gesuchten Bild etwas ähnlicher sieht. Diese Berechnungen werden so oft durchgeführt, bis keine Verbesserung mehr möglich ist.
Quelle: Wikipedia

Vergleich mit anderen Bildformaten

Originalbild 252.054 Byte	JPG-Bild 70.268 Byte	FIF-Bild 72.403 Byte

Fraktale Grafikformate

Das Grafikformat FIF (Fractal Image Format) ist ein von »Iterated Systems Inc.« entwickeltes Grafikformat, welches auf fraktaler Bildkompression beruht und ein Konkurrenzprodukt gegenüber JPEG darstellen sollte. Trotz einiger Vorteile wie erheblich besserer Skalierbarkeit und etwas höherer Qualität bei gleicher Dateigröße ist das Format gescheitert, da weder Netscape noch Microsoft bereit waren, das Format in ihren Browser zu implementieren, Plug-Ins nur für die Win32-Plattform verfügbar waren und Dateien in diesem Format anfangs nur mit einem relativ teuren Tool der Firma »Iterated Systems« zu bearbeiten waren. Dennoch sind heute viele Grafikprogramme in der Lage, FIF-Grafiken zu dekodieren. Das Plug-In zur Anzeige mit Netscape oder dem Internet-Explorer ist heute jedoch nicht mehr offiziell erhältlich, nur noch auf den FTP-Servern einiger Universitäten ist die letzte Version 1.6 des Fractal Viewer Plug-In zu finden.
Quelle: Wikipedia

Das Grafikformat STiNG (Erweiterung .STN) erlaubt es, ohne Qualitätsverlust die Dateigröße von Bildern erheblich zu verringern. Wenn sich die Größe und die Auflösung eines Bildes für das groß zu druckende Format erhöht, erhöht sich auch die Größe einer Datei. Das kann beim Archivieren zahlreicher derartiger Bilder problematisch werden. Das STiNG-Format löst dieses Problem, indem es die Datei verlustfrei mit Wavelet-Kompression speichert. Ein Zahlenbeispiel: Wird ein Originalbild von 617 KB auf 600% vergrößert, benötigt es als PhotoShop-Dokument (PSD-Format) 46,8 MB Speicherplatz, als verlustfreie STN-Datei nur 15,9 MB. Wenn die Datei mit hohem Kompressionsgrad gespeichert wird, werden gar nur 2,9 MB benötigt, eine Einsparung von 94% gegenüber dem PSD-Format.
Quelle: PhotoshopNews.com