Entwickler-Ecke :: Thema anzeigen - Fraktale Bildkompression

Mathematiker - Mo 29.07.13 22:33
Titel: Fraktale Bildkompression

Hallo,
vor einiger Zeit habe ich unter http://www.femtosoft.biz/fractals/fractal.html eine tolle Delphi-OpenSource-Quelle gefunden, die ich, damit die Oberfläche etwas schöner wird, leicht modifiziert habe.
Der wichtige Algorithmus und seine Umsetzung ist, wie gesagt, nicht von mir, sondern von Femtosoft.

Von Michael Barnsley wurde vor Jahren ein spezielles Verfahren zur Kompression von Darstellungen natürlicher Gebilde auf der Basis von Fraktalen entwickelt.
Dabei wird in den Abbildungen nach wiederkehrenden Strukturen gesucht und diese als Parameter einer affinen Abbildung gespeichert. Die Rekonstruktion des Originalbildes wird durch ein iteriertes Funktionensystem schnell erreicht.

Während das Zeichnen des Bildes relativ schnell erfolgt, ist die Ermittlung der affinen Abbildungen extrem aufwendig. Mit dem Algorithmus von Femtosoft wird das Prinzip demonstriert.

Nach dem Start wird eine Bitmap-Datei geladen. Dieses Bild sollte nicht zu groß sein, da die Umwandlungszeit exponentiell mit der Bildgröße steigt.
In der Umwandlung sucht das Programm die Strukturen in der Abbildung und berechnet Koeffizienten einer zugehörigen affinen Abbildung. Eine kleine Kompressionsrate ergibt qualitativ bessere Ergebnisse, aber auch größere komprimierte Dateien.
Ein fraktal komprimiertes Bild wird in 16 Iterationen wieder erzeugt; hier allerdings nur in Graustufen.
Damit die Dateigröße kleiner wird, komprimiere ich die Koeffizientenliste der affinen Abbildungen mit zlib.

Unter "Beispielen" finden sich ein paar in der Exe enthaltene fraktal komprimierte Abbildungen.

Interessant ist auch, dass beim Entpacken auch eine andere Komprimierungsrate gewählt werden kann: Ein kleinerer Wert verkleinert das Bild, ein höherer liefert eine größere Abbildung.

Vielleicht findet jemand das Verfahren interessant und kann irgendwie eine Beschleunigung von Kompression und Dekompression erreichen.
Ich grübele schon einige Jahre, musste aber bis jetzt aufgegeben, da es mir (noch) zu "kryptisch" ist. Dennoch finde ich die Grundidee faszinierend, wenn gleich die Kompressionsrate hinter der von zip oder jpg zurück bleibt und die Kompressionszeit ... naja

Außer meiner Umsetzung hänge ich auch die Originalquellen an.

Beste Grüße
Mathematiker

MeierZwoo - Di 30.07.13 03:46

Mathematiker hat folgendes geschrieben :

wenn gleich die Kompressionsrate hinter der von zip oder jpg zurück bleibt

ZIP und JPG darf man aber bei Kompression nicht in einem Satz benutzen: ZIP ist ein Archivierungsverfahren, welches das Original exakt wieder herstellt, JPG (und GIF ..) nicht verlustfreie Komprimierungs-Algorithmen, die das Original nicht wieder herstellen können - vielfach nicht einmal ansatzweise.

Die einzigen Grafikformate, welche wie Archive verlustfrei encodet encodet sind, sind TIFF und PNG. Wobei Tiff aber oft größer als das Original wird, wenn von RGB auf CMYK übergegangen wird.

PNG hat auch eine sehr günstige Kompressionsrate sowohl in Bezug auf Zeitverhalten wie auch Dateigröße (Dateigröße ca. wie ZIP gegenüber BMP). Deshalb ist meiner Meinung nach jedes andere Verfahren, welches nicht mindestens die PNG-Werte erreicht uninteressant für praktische Anwendungen. Wobei das Zeitverhalten beim Nachladen von Grafiken die wesentlichste Rolle spielt. Zumal PNG auch lizenzfrei ist und breiteste Unterstützung hat.

:)

Horst_H - Di 30.07.13 10:15

Hallo,

es ist wirklich sehr sehr langsam.
1024x768 in 1h 6min für Kompressionsstufe 2 und 256x192 Pixel in 60 Sekunden bei Kompressionstufe 6.
Ich kann mir jetzt keine Berechnungsbeschleunigung um den Faktor 360 vorstellen, um einigermaßen vernünftige Zeiten hin zu bekommen.Das hätte der "Erfinder" sicher schon probiert.
Lassen sich denn Fraktale gut komprimieren ? :-)

Gruß Horst
P.S.:
Wäre eine jpeg2000 Kompression per Dll nicht eine Alternative.

Mathematiker - Di 30.07.13 11:14

Hallo,

Horst_H hat folgendes geschrieben :

es ist wirklich sehr sehr langsam.

Das ist es, leider. Etwas schneller wäre schön, aber wie?
Leider findet man im Netz auch keine kostenfreien Programme, die das gleiche Verfahren nutzen und mit denen man testen könnte.

Horst_H hat folgendes geschrieben :

Wäre eine jpeg2000 Kompression per Dll nicht eine Alternative.

Die fraktale Komprimierung hat sich nicht durchsetzen können, zu langsam und zu teuer.
Mir geht es eigentlich auch nicht darum, eine "Alternative" für bekannte Komprimierungsarten zu finden. (Ist ja auch nicht möglich) Ich finde nur das Verfahren so faszinierend und beeindruckend(!).
Ich frage mich bei solchen Algorithmen immer: Wie kommt man auf so etwas? Was sind das für Menschen (Nerds?, positiv gemeint), denen das einfällt?

Horst_H hat folgendes geschrieben :

Lassen sich denn Fraktale gut komprimieren ? :-)

Testweise habe ich Barnsleys Farn versucht (320 x 470 Pixel).
farn

Das BMP-Bild hat 77 k, das (schlechte) JPG-Bild 47 k, GIF und PNG nur jeweils 8 k.
Für die fraktale Komprimierung benötigt das Programm in Stufe 2 bei mir eine knappe Minute. Die Datei ist rund 12 k groß, also nicht ganz so schlecht. Beim Entpacken funktionieren auch höhere Kompressionsstufen noch ganz gut.

Beste Grüße
Mathematiker

Mathematiker - Di 30.07.13 15:54

Hallo,

Horst_H hat folgendes geschrieben :

Bei welchen Daten soll es denn besonders gute Kompressionswerte liefern, wen selbst Fraktale nicht besser als verlustloses PNG sind.

Der Name "Fraktale Kompression" bedeutet nicht, dass besonders gut Fraktale komprimiert werden können.
Der Begriff stammt von der Verwendung von Attraktoren iterierter Funktionen-Systeme (IFS) und die haben etwas mit Fraktalen zu tun.
Genau habe ich die Ausführungen unter http://de.wikipedia.org/wiki/Iteriertes_Funktionen-System aber nicht verstanden.

Horst_H hat folgendes geschrieben :

auf den ersten Blick, kommt mir der Ansatz mit Fraktalen auch etwas wirklichkeitsfremd vor.

Und gerade deshalb bin ich von Barnsley und Co. beeindruckt.
Es gibt auch das Beispiel Faktorisierung + elliptische Kurven. Als Mathematik-Interessierter glaubt man auf den ersten Blick auch nicht, dass elliptische Kurven irgendetwas mit der Zerlegung von Zahlen in ihre Primfaktoren zu tun haben können; den Nicht-Interessierten ist es sch...egal. :?
Und herausgekommen ist eines der schnellsten Faktorisierungsverfahren.

Beste Grüße
Mathematiker

Xion - Di 30.07.13 16:08

Mathematiker hat folgendes geschrieben :

Als Mathematik-Interessierter glaubt man auf den ersten Blick auch nicht, dass elliptische Kurven irgendetwas mit der Zerlegung von Zahlen in ihre Primfaktoren zu tun haben können [...]Und herausgekommen ist eines der schnellsten Faktorisierungsverfahren.

Richtig. Der Vorteil an Forschung ist, dass man nicht von der praktischen Anwendbarkeit abhängig ist (mal vom Geldgeber abgesehen, aber dafür gibt's ja Universitäten). Das gilt meiner Meinung nach ganz besonders für die Mathematik und die damit verbundenen Disziplinen (Theoretische Informatik etc).
Meist kommt dann irgendwer aus der Praxis, der ein spezielles Problem lösen möchte, und keinen Schimmer hat wie das gehen sollte. Dann braucht es nur noch einen schlauen Menschen, der die Ergebnisse der Mathematik auf das Problem anwenden kann. Und schon ist die scheinbar sinnlose, abgehobene und wirklichkeitsfremde Theorie doch nicht mehr wirklichkeitsfremd.
Der Computer wurde ja auch nicht an einem Tag erfunden. Ich würde mal behaupten, die meisten Menschen haben Ada Lovelace [https://de.wikipedia.org/wiki/Ada_Lovelace] auch als wirklichkeitsfremd bezeichnet :mrgreen: Und die war noch harmlos im Vergleich zu so manchem Mathematiker...(Geschichte des Dualsystems [http://de.wikipedia.org/wiki/Dualsystem])

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!