Fraktale Bildkompression

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

1988 legten Michael F. Barnsley und Alan D. Sloan die theoretischen Grundlagen der fraktalen Bildkompression, die erste Implementierung stammte allerdings von Barnsleys Doktoranden Arnaud Jacquin 1992.

Prinzip

Die Idee beruht auf einer bestimmten Sorte von Fraktalen, den Attraktoren iterierter Funktionen-Systeme (IFS). Hier werden komplexe Abbildungen mit einer Menge von affinen Abbildungen des Bildes in sich selbst erstellt.

Einfache Beispiele sind 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.

Um ein beliebiges Bild konstruieren zu können, muss eine Menge von Flächen ($F_{1}...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.

Zu beachten ist, dass der Inhalt der Flächen $G_{i}$ größer als der Inhalt der Flächen $F_{i}$ ist.

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.

Fractal Image Format (FIF)

Fractal Image Format ist ein von Iterated Systems entwickeltes Grafikformat, welches auf fraktaler Bildkompression beruht und gegen JPEG ausgerichtet war. Trotz einiger Vorteile wie erheblich besserer Skalierbarkeit und etwas höherer Qualität bei gleicher Dateigröße, ist das Format trotz einiger kleinerer Erfolge gescheitert. Einige der Gründe dafür waren, dass weder Netscape noch Microsoft bereit waren, das Format in ihren Browser zu implementieren, Plug-Ins abseits der Win32-Plattform nicht verfügbar waren (abseits von Windows war zunächst die Anzeige gar nicht möglich) und Dateien in diesem Format anfangs nur mit einem relativ teuren Tool der Firma Iterated zu bearbeiten waren. Dennoch sind heute viele Grafikprogramme in der Lage, FIF-Grafiken zumindest zu dekodieren. Das Plug-in zur Anzeige mit Netscape oder Internet-Explorer ist heute jedoch nicht mehr offiziell erhältlich. Auf den FTP-Servern einiger Universitäten ist die letzte Version 1.6 des Fractal Viewer Plug-In noch zu finden und arbeitet auch mit den neuesten Versionen von Netscape, Opera und Internet Explorer korrekt zusammen. Es ist in der Lage, FIF-Grafiken auch als Vollbild anzuzeigen oder innerhalb der Webseite zu skalieren.

Siehe auch

• Wavelet-Kompression
• JPEG
• Fraktale Tonkompression

Literatur

• Michael F. Barnsley, Lyman P. Hurd, Louisa F. Anson: Fractal image compression. AK Peters/CRC Press 1993, ISBN 1568810008.
• Yuval Fisher: Fractal image compression: theory and application. Springer 1995, ISBN 0387942114.
• Michael F. Barnsley, Lyman P. Hurd: Bildkompression mit Fraktalen. Vieweg+Teubner 1996, ISBN 3528054646.
• Yuval Fisher (Hrsg.): Fractal image encoding and analysis (NATO ASI Series F: Computer and Systems Sciences, Vol. 159). Springer 1998, ISBN 3540631968, ISBN 3642083242.

Weblinks

• http://www-lehre.informatik.uni-osnabrueck.de/~mm/skript/5_6_Fraktale_Kompression.html Vorlesungsskript
• http://www-lehre.inf.uos.de/wp/2000/mm05/meinMaster/Vortrag/
• http://inls.ucsd.edu/~fisher/Fractals/ Yuval Fishers Fraktalcodierungsseite (englisch)