Kurzes Update (vor allem mit Bezug auf die wochenlange Optimierung von PNGs) und Zusammenfassung meiner Posts auf encode.su:
PNG-Optimierungs-Tools haben üblicherweise einen Parameter, mit dem man steuern kann, wie viel Rechenleistung man in die Optimierung stecken will.
Den braucht man, weil die Optimierung nicht effizient berechenbar ist, und Brute Force würde die gesamte Rechenleistung der Welt nicht reichen um die perfekte Kompression für ein kleines PNG zu berechnen.
Das ist wiederum so, weil die Kompressionsmethode –
Deflate – häufigen Zeichen kürzere Bitfolgen zuordnet als seltenen (Huffman). Wenn wir nun vor der Entscheidung stehen, ob wir
„Banana“ in
Ban-an-a zerstückeln oder in
Ba-na-na oder in
B-a-n-a-n-a spielt es eine große Rolle, wie häufig
B, a, n, Ba, na, Ban, und
na in der gesamten Umgebung vorkommen. Aber noch kniffliger: Wenn wir uns für eine Möglichkeit entscheiden, steigt die Häufigkeit der gewählten Symbole, und das ändert möglicherweise wieder ihre Längen in Bits. Jede Entscheidung ändert also
alles. Und das kriegt man n ur via Heuristik unter Kontrolle.
Okay. Man würde nun erwarten, dass die Datei umso kleiner wird, je länger man rechnet. Mit der Zeit auf X und der Größe auf Y sollten wiederholte Optimierungen – mit immer längerer Laufzeit – also so aussehen:
Da ist Rauschen drin weil a) Heuristik oft richtig liegt aber manchmal eben auch daneben und b) Zeitmessung auf Computern mindestens so schwierig ist wie perfekte Kompression.
Nun habe ich ECT (das Arbeitspferd hinter meiner PNG-Optimierung) über
Lenna laufen lassen, und bekam stattdessen das hier:
Okaaaaaay. Also habe ich beschlossen, mehr Messwerte hinzuzufügen. Bis rauf zu 200 Iterationen und mehr (Papa’s Best Optimizer nutzt 600). Außerdem mehrere Block-Split-Iterationen im Vergleich (Block Splits sind Stellen, an denen man die Kompression bewusst unterbricht und den Kompressor leert – bspw. wenn Text von Englisch zu Chinesisch wechselt – damit die Wahrscheinlichkeiten und Vorhersagen des alten Modells keine teuren Fehlvorhersagen für die neuen, kontextuell unterschiedlichen Daten verursachen).
Fuck! Die Kurve sollte nie, nie,
nie nach oben gehen! Das sagt uns quasi: Wenn wir ECT für 0,5 s laufen lassen (nämlich mit drei Iterationen), bekommen wir bessere Kompression hin als mit allen anderen Kompressionsstufen danach; egal, wie lange sie laufen.
Vielleicht war Lenna auch nur eine schlechte Wahl, denn PNG ist ja eher für Grafik als für Fotos. Also habe ich mir das Wikipedia-Logo geschnappt, und … gleicher Mist:
Okay. Quelltext angeschaut, aber … nichts kapiert. Gehen wir systematisch ran.
Die PNG-Kompression geschieht in zwei Stufen: Erst laufen Filter über das Bild, die die darüberliegende Zeile und alle Pixel links einbeziehen (oft eine einfache Subtraktion). Dadurch wird das zweidimensionale Problem zu einem eindimensionalen reduziert, und regelmäßige Farbverläufe produzieren bspw. nur noch einen konstanten Zahlenstrom, der sich dann super komprimieren lässt.
Danach erst kommt die Deflate-Kompression, die ich oben erwähnte.
Also habe ich die PNGs synthetisch verändert, so dass sie ungefiltert sind – wie normale Bitmaps (war ganz einfach via
lodepng) – und ECTs Filterung abgeschaltet (
--reuse). Falls es ein Filterproblem ist, sollten wir die Delle nun wieder sehen. Falls es ein Deflate-Problem ist, nicht.
Und wenn ich eh schon diesen riesen Aufwand betreibe, kann ich ja direkt alle anderen PNG-Tools hinzufügen und deren Leistung mit messen.
Und damit das fair ist, kompiliere ich sie alle selber für’s selbe Ziel (64-Bit-Windows) mit dem selben Compiler (Visual Studio 2019) aus dem aktuellen Trunk und packe sie in DLLs (um Namenskollisionen zwischen den Quelldateien zu vermeiden, sind ja alle unter einander gebrancht) und starte sie aus dem selben Prozess. Das wären:
- ZopfliPNG, Googles PNG-Optimizer aus ihrem Zopfli-Projekt.
- advpng, das PNGs sowohl mit 7-Zips Deflate-Kompressor optimieren kann als auch mit Zopfli.
- Leanify, das ZoplfiPNG um eigene Optimierungen ergänzt.
- … und eben ECT.
Ich wollte auch gern
pngout ausprobieren, aber das ist closed source.
OptiPNG nutzt die normale Zlib und ist deshalb nicht gut genug für den Vergleich.
Ergebnis:
Wir sehen ungefähr ein Promille der Größe im Graph; die Größenunterschiede sind also für Normal-User nicht dramatisch. Für Kompressionsanalyse jedoch schon.
7-Zip war so schlecht, dass es nicht sichtbar ist. Ich kann mir nicht erklären, warum – möglicherweise eine veraltete Version oder ein Bug.
ZopfliPNG und advpng schneiden ungefähr gleich ab, abgesehen von unterschiedlicher Anlaufzeit.
Leanify schlägt ZopfliPNG bei kurzer Laufzeit; danach ist es mal besser und mal schlechter.
Und ECT … rockt alles. ECT ist *viel* schneller als alle anderen. ECT komprimiert *viel* besser als alle anderen.
In jedem Einzelnen Lauf.
Wir sehen auch keine Delle – der Bug mit der Delle lag also in der Filterung. Wir sehen aber ebenso, dass ECT sich unberechenbar verhält.
Wir sehen aber auch, dass wir nach tagelanger Laufzeit keine Verbesserung erwarten können, sondern dass ECT recht schnell am Limit ist. Das ist ein Signal an meinen Optimizer.
Nun habe ich die Benchmarks auf anderen Bildern wiederholt, und ECT rockt sie jedes Mal in Grund und Boden. Jedoch … bei
einem Comic:
WTF. WHAT THE ACTUAL FUCK. Bei 61 Iterationen ist ECT plötzlich 10× langsamer als bei 60. Dann probierte ich
die Transparenz-Demo von Wikipedia aus und … 61 Iterationen waren ZWEITAUSEND MAL LANGSAMER als 60. Kein Witz. Ich kann auch keinen Graph zeigen, weil sich alles im Pixel ganz links abspielt und die Kurve dann nach ganz rechts springt weil ECT statt zehn Sekunden plötzlich einen halben Tag läuft.
Ich spreche gerade mit den Entwicklern der Tools. Sobald sich das alles klärt, wird es im Optimizer nachgebessert …
