PNG mit 7-Zip

[eXile]

Dürfte ich fragen, welche PNG-Chunks überhaupt für deine Programme von Interesse sind? Oder andersherum: Was löschst du häufig für Chunks raus?

[Krishty]

Garkeine. Ich optimiere lediglich den IDAT-Chunk, bzw. merge alle IDATs zusammen, falls es mehrere gibt. Wie sie sich mit privaten, also nicht standardisierten Chunks verhalten, kann ich aus dem Stehgreif nicht sagen – aber theoretisch müssten sie die übernehmen.

Die Programme in dem hochgeladenen Paket sind btw ein wenig alt; ich weiß garnicht, ob sie noch laufen (CRT von VS2010-RC und so).

Und ein Rückschlag: Auf einigen Bildern habe ich 11 % größere Ergebnisse als vorher. Also zurück ans Reißbrett.

Sooo. Die Auswahl danach, welcher Filter sich mit allen vorherigen Zeilen zusammen optimal komprimieren lässt, liefert gleiche Ergebnisse wie vorher. Immernoch suboptimal. Wahrscheinlich wird hier die Schere zwischen meiner PPMd-simulierenden Deflate-Kompression und echtem PPMd zu groß – das echte PPMd kann ich nicht benutzen, weil sich damit nur volle Kompressionen durchführen lassen; mittendrin zurückspringen und neu komprimieren (wie bei Deflate) geht aufgrund der Implementierung nicht.

[Krishty]

Ich habe momentan mit etwas größeren Datenmengen zu tun, darum musste ich Anpassungen an ArchiPNG vornehmen: Es gibt nun eine 64-Bit-Version und die Optimierung wird garnicht erst begonnen, falls nicht genügend Adressraum zur Verfügung steht. (Weil ich aber Fragmentierung nicht voraussagen kann, kann es noch immer Abbrüche geben.) Außerdem werden aktuelle Versionen von zlib und libpng genutzt.

Getestet mit 38.400×28.800 Pixeln, 8 Bits pro Pixel (größer ging nicht, da GIMP dann abstürzt) auf einem Core i7 860:
GIMP:. . . . . . . . . 52,1 MiB
OptiPNG*:. . . . . . . 30,3 MiB / 230 min
ArchiPNG:. . . . . . 1044,5 MiB / 124 min
ArchiPNG + 7-Zip:. . . 22,1 MiB / 124 + 4 min **
ArchiPNG + Ultra7z:. . 15,1 MiB / 124 + 159 min ***
* höchste Stufe; manuell das /LARGEADDRESSAWARE-Flag nachgetragen
** PPMd Ultra
*** höchste Stufe; Ergebnis: PPMd:o24:mem29

Die Daten sind noch relativ synthetisch; sobald ich ein richtig fieses reales Szenario abgeschlossen habe, trage ich die Ergebnisse nach. Ich erwarte da weniger krasse Unterschiede.

Irgendwann sattle ich auch mal auf Multi-Threading um … weiterhin wäre es möglich, einen Bruchteil der Daten Ultra7z zu übergeben, damit nur 10 MiB Bruto-Force komprimiert werden müssen um die optimale Methode für das komplette GiB zu finden. Dann kommt man so langsam in Bereiche, in denen es sich lohnt. (Nach dem Motto: eine 100-MiB-Grenze weniger überschritten – eine Stunde weniger Wartezeit bei einem Filehoster.)

ArchiPNG.7z

(156.24 KiB) 403-mal heruntergeladen

Zum Entpacken wird 7-Zip 9.2, zum Ausführen die Visual C++ 2010 SP1-Laufzeitbibliothek benötigt. Benutzung wie immer – Drag'n'Drop und Kommandozeile für PNGs und Verzeichnisse.

[Mr. Heat]

Ich bin leider erst jetzt über diesen interessanten Beitrag gestolpert. Ich habe ein paar Ergänzungen, die ich in einem Blogbeitrag zusammen gefasst habe: www.black-chronos.com/glow/2011/10/png- ... ng-extrem/

Hier meine Gedanken in Kürze:

• Ich habe mir ein Tool geschrieben, dass den Alphakanal in PNG-Dateien säubert. Dort, wo A=0 ist, wird auch R=0, G=0 und B=0 gesetzt. Das macht nicht jedes Programm von Haus aus. Manche hinterlassen in den transparenten Bereichen regelrechten Datenmüll, der die Datei unnötig aufbläht. Die bekannten PNG-Optimierer säubern diese Bereiche bewusst nicht, da dadurch gewissermaßen (man könnte wohl darüber diskutieren) der Dateiinhalt verfälscht werden würde.
• Einen ähnlichen Effekt wie mit deinem ArchiPNG kann man auch erreichen, indem man per Bildbearbeitung viele Einzelbilder in wenigen großen PNG-Bildern zusammen fasst. Das lohnt sich vor allem bei Sprite-Animationen mit sehr vielen kleinen Animationsphasen. Die Einsparung ist natürlich geringer als bei deinen Methoden, es hat aber den Vorteil, dass es die ganze Zeit über "normale" PNG-Dateien bleiben.
• Es lohnt sich, PNGOUT mehrmals mit den Parametern /f0 bis /f5 durchlaufen zu lassen. Meiner Erfahrung nach ist das beinahe immer besser als OptiPNG.

[Tiles]

Ich habe mir ein Tool geschrieben, dass den Alphakanal in PNG-Dateien säubert. Dort, wo A=0 ist, wird auch R=0, G=0 und B=0 gesetzt. Das macht nicht jedes Programm von Haus aus. Manche hinterlassen in den transparenten Bereichen regelrechten Datenmüll, der die Datei unnötig aufbläht. Die bekannten PNG-Optimierer säubern diese Bereiche bewusst nicht, da dadurch gewissermaßen (man könnte wohl darüber diskutieren) der Dateiinhalt verfälscht werden würde.

Es kommt auf den Verwendungszweck an ob die Farbpixel in den transparenten Breichen "Datenmüll" sind oder nicht. Nehmen wir zum Beispiel eine transparente Blatt-Textur für einen Low Poly Baum. Die wird in der Regel mittels Mipmapping kleinerskaliert je weiter weg der Kamerad ist. Und dabei bluten dann diese vorher im transparenten liegenden Pixel in den sichtbaren Bereich rein. Die Pixel werden ja beim kleinerskalieren zusammengemischt. Wenn du im transparenten Bereich nun alles schwarz machst hast du spätestens beim dritten oder vierten Mipmap Bild auch im sichtbaren Bereich alles schwarz. Ich sorge deswegen inzwischen dafür dass die sichtbaren Pixel in den unsichtbaren Bereich fortgeführt werden. Sprich wo es im sichtbaren Bereich grün ist ist auch mein transparenter Bereich im Umfeld davon unter der Haube grün. Natürlich ist meine Textur dadurch etwas grösser. Aber es ist ja für einen guten Zweck :)

[Krishty]

Nehmen wir zum Beispiel eine transparente Blatt-Textur für einen Low Poly Baum. Die wird in der Regel mittels Mipmapping kleinerskaliert je weiter weg der Kamerad ist. Und dabei bluten dann diese vorher im transparenten liegenden Pixel in den sichtbaren Bereich rein. Die Pixel werden ja beim kleinerskalieren zusammengemischt. Wenn du im transparenten Bereich nun alles schwarz machst hast du spätestens beim dritten oder vierten Mipmap Bild auch im sichtbaren Bereich alles schwarz. Ich sorge deswegen inzwischen dafür dass die sichtbaren Pixel in den unsichtbaren Bereich fortgeführt werden. Sprich wo es im sichtbaren Bereich grün ist ist auch mein transparenter Bereich im Umfeld davon unter der Haube grün. Natürlich ist meine Textur dadurch etwas grösser. Aber es ist ja für einen guten Zweck :)

Selber schuld. Dafür gibt es Premultiplied Alpha … ;)

Dieser Punkt hängt sich an der Definition von „verlustfrei“ auf: Für Archivierungsprogramme à 7-Zip bedeutet (imho) verlustfrei, dass die Bilder Bit für Bit identisch mit der Eingabe sind. Für PNG-Optimierer bedeutet verlustfrei, dass die Bild- und Metainformationen erhalten bleiben, obwohl sich die Repräsentation des Containers ändern darf (und sogar soll, wir wollen ihn schließlich kleiner haben).

Ich zähle den Alphakanal durchaus zu den Bildinformationen. Die Entscheidung, ob ein voll transparenter Pixel keinen Farbwert hat oder doch, setzt eine Interpretation voraus, die über die Kompetenzen des Containers hinausgeht: Ein PNG-Optimierer kann und darf sich nicht anmaßen, zu urteilen, wofür das Bild später verwendet wird. Falls das Tool hingegen genau auf deinen Verwendungszweck zugeschnitten ist (und dadurch über ausreichendes Wissen über deine Interpretation verfügt), kannst du das natürlich als verlustfrei durchgehen lassen, da diese Bildinformation für deinen Zweck nicht mehr relevant ist.

Die Entfernung der Farbwerte von transparenten Pixel fällt für mich also nicht mehr unter Verlustfreiheit generischer PNG-Optimierung. Wenn man mal so weit ist öffnen sich zwar ganz andere Tore (z.B. das Quantisieren von Echtfarb-PNGs auf optimale Paletten, wie es PNGQuant tut); allerdings sind dann alle Kompressionsergebnisse auf einen Schlag degradiert: Da man nun in einer Liga mit anderen verlustbehafteten Kompressionsmethoden wie JPG oder Wavelet-Kodierern spielt, muss man auch ähnliche Kompressionsraten erbringen … und das bedeutet ein bis drei Bits pro Pixel bei guter visueller Qualität. Da kommt man mit PNG nicht ran.

Zu guter Letzt: Gimp bietet bspw. an, transparente Farbwerte zu entfernen. Das ist fast perfekt, weil es die Entscheidung, ob sie benötigt werden, zum Künstler verschiebt. (Besser wäre nur noch, das den Nutzer der Grafik entscheiden zu lassen.)

[Tiles]

Selber schuld. Dafür gibt es Premultiplied Alpha … ;)

Och, nicht jede Gameengine kann Premultiplied. Unity kann aber premultiplied Alpha. Und trotzdem siehst du es da sehr schön. Auch premultiplied ist also kein Allheilmittel :)

[Krishty]

Dann läuft da irgendwas falsch … Premultiplied funktioniert.

[Mr. Heat]

Es gibt leider Bildbearbeitungen, die in den transparenten Bereichen nur undefinierten Müll speichern. Diesen Müll zu entsorgen, zähle ich als verlustfrei. ;-) Aber natürlich kann ein Tool nicht entscheiden, ob es Müll ist.

Aufmerksam geworden bin ich darauf, weil mir an den Transparenzkanten von linear interpolierten Texturen weiße Pixel entgegen flackerten. Der transparente Bereich war aus irgend einem Grund weiß gefüllt. Das Säuberungs-Tool habe ich mir zuerst nur deshalb geschrieben. In meinem Fall (im dunklen Setting von Glow) hat eine simple schwarze Füllung das Problem schon gelöst. Quasi nebenbei hat das die PNGs besser komprimierbar gemacht.

Ideal wäre es, wenn das Tool die sichtbaren RGB-Werte drei Quadratpixel weit in den unsichtbaren Bereich hinein interpoliert und nur den Rest einfarbig füllt. Am besten mit dem Median aller Randpixel. So weit musste ich es aber gar nicht treiben. Schwarz hat mir wie gesagt gereicht.

[Krishty]

… oder auf Premultiplied Alpha umsteigen und die Kopfschmerzen vergessen ohne Komprimierbarkeit einzubüßen ;)

[Tiles]

Hm, ich will eigentlich nicht deinen Thread hijacken. Das Thema Premultiplied Alpha könnte man glatt vereinzeln. Jedenfalls siehts bei mir so wie im Bild aus. Ein transparentes rotes Kugelbild als Grasersatz. Einmal mit schwarzem unsichtbaren Hintergrund, einmal mit einem unsichtbaren Hintergrund der vom sichtbaren Bereich in den unsichtbaren erweitert wird. Sprich ich hab ne rote Kugel, und die setzt sich im unsichtbaren Bereich fort. Wie du sehr schön siehst schimmert beim linken Bildteil das Schwarz wunderbar durch. Das ist mein Kugelgras mit dem schwarzen Hintgergrund. Die rechte Hälfte nutzt die Textur mit dem erweiterten roten Hintergrund.

Ich scheine mich übrigens geirrt zu haben. Unity scheint doch kein Premultiplied Alpha zu können. In der Manual steht nur was von Straight Alpha Blending und dass man die Farben extenden muss. Womit wir wieder beim Thema nicht jede Engine kann Premultiplied Alpha wären :)

[Chromanoid]

Ich hätte sonst gedacht, dass einfach die Render-Reihenfolge falsch ist bzw. kein Z-Sorting betrieben wird. Aber hier liegt das ja wirklich am fehlenden vormultiplizieren :).

[Mr. Heat]

Dank http://blog.rarepebble.com/111/premulti ... in-opengl/ habe ich es jetzt verstanden. Ich war verwirrt, weil Vormultiplizieren allein ja erst recht schwarze Ränder erzeugen würde. Genau das macht es ja: Transparente Pixel werden um so mehr abgedunkelt, je transparenter sie sind. Das ergibt nur Sinn, wenn man vormultiplizierte Texturen mit einer anderen Blend-Funktion auf den Bildschirm bringt (bei OpenGL GL_ONE, GL_ONE_MINUS_SRC_ALPHA).

Und da sind wir zurück beim Thema: Vormultiplizierte Texturen lassen sich besser PNG-komprimieren, weil die leeren Bereiche wirklich leer (mit 0,0,0 gefüllt) sind.

[Tiles]

Mich würde da jetzt noch interessieren wie sich das Mipmapping im direkten Vergleich zwischen Premultiplied und der alten Technik von wegen Farben in den transparenten Bereich erweitern auswirkt. Gibts da nen sichtbaren Unterschied?

[Schrompf]

Rein mathematisch müsste das Ergebnis identisch sein. Es kann sein, dass aufgrund der begrenzten Genauigkeit leichte Fehler reinkommen, aber die beschränken sich ja prinzipiell auf die nahezu durchsichtigen Bereiche, in der Praxis müsste also kein Unterschied erkennbar sein.

[Tiles]

Danke :)

[Krishty]

Ich versuche gerade, eines meiner selbstgeschriebenes PNG-Tools, das nur an andere Tools weiterdirigiert, durch eine Stapelverarbeitungsdatei zu ersetzen. Weil, den Quelltext habe ich 2009 mit Framework-Abhängigkeiten geschrieben und ich kann und will ihn heute nicht mehr kompilierfähig haben. Stapelverarbeitungsdatei geht hingegen immer.

Mann ist das eine Scheiße mit den ganzen Tools. Nach Updates funktioniert die Optimierung nicht mehr so gut; Dateien werden geschrieben obwohl größer; Graustufen werden zu Paletten umgewandelt; blabla.

Falls irgendwann irgendjemand mit Interesse und Zeit und Hirn mein Gejammer liest – so hat ein vernünftiger PNG-Optimizer zu arbeiten, der fünf Tools auf einmal ersetzen müsste:

• LZ77 ist eine scheiß Kompression. Man kann nicht wie bei LZMA fette, aber redundante Eingaben einfach wegkomprimieren. Die Eingabe hat möglichst schlank zu sein, und das bedeutet Color Space Reduction: Leere Alphakanäle löschen. Von RGB zu Graustufen konvertieren, falls möglich. Oder von RGBA zu Graustufen und Alpha. Oder zu Paletten. Die Bitmap muss so winzig wie möglich sein. Ich benutze OptiPNG dafür. Nicht wie TruePNG  – das zerstört in der Standardeinstellung Pixel mit Null-Alpha (gibt einen netten Schub bei der Kompression und netten Haarverlust bei den Anwendern).
   
• Wenn man die Wahl zwischen zwei Formaten gleicher Farbtiefe hat (bspw. 8-Bit-Graustufen <=> 123 Paletteneinträge): Erstmal beide Verzweigungen weiterverfolgen. Kann man mit einer einfachen Stapelverarbeitunsgdatei leider nicht; dafür sind die nicht meta genug. Meh.
   
• Filter für geringste Entropie optimieren. Das ist eine haarige Angelegenheit und da gibt es Millionen Veröffentlichungen drüber. Aber: Das ist nicht zwingend statisch. Die beste Wahl kann sich im Nachhinein noch ändern. Fast alle PNG-Optimizer da draußen optimieren einmal die Filter und kümmern sich dann nur noch um LZ77. Da kommt dann so ein Müll bei raus wie TruePNG ist besser als OptiPNG (http://css-ig.net/png-tools-overview). Bullshit. Weil ihr PNGOut mit /f6 ausführt bleiben die Filter starr und darum optimiere ich nach fünf Jahren immernoch jedem Möchtegern-PNG-Optimizer da draußen die Hosen runter. Hier immernoch OptiPNG.
   
• Dann kommt die Optimierung des LZ77. 99 % des Weges kann mit mit Ken Silvermans PNGOut schaffen. Das ist und bleibt die Nummer Eins auf dem Gebiet; und jeder große PNG-Optimizer benutzt es. Wer absolut sicher gehen will, sollte es mit allen sechs Filtereinstellungen aufrufen (die meisten benutzen nur eine).
   
  In dieser Hinsicht wäre es toll, wenn jemand cblooms Entwürfe für Optimal Parse ausprobieren würde. Er berichtet ja so schön abfällig über alles andere da draußen:

  [Zopfli, die Spitze der ZIP-Kodierer] seems to be pretty straightforward, it's an optimal parser + huff reset searcher. There are various other prior tools to do this (kzip,deflopt,defluff,etc). It's missing some of the things that I've written about before here, such as methods of dealing with the huff-parse feedback; the code looks pretty clean, so if you want a good zip-encoder code it looks like a good place to start.

• Danach geht es an die Huffman Codes. Hier fallen die letzten Millionstel der Datei; das ist allerdings auch der Bereich, in dem sich unter professionellen Tools die Sieger entscheiden. Ursprünglich bin ich hier nur mit DeflOpt rangegangen; aber eigentlich müsste man in einer Schleife fünf Mal defluff und ein Mal DeflOpt laufen lassen und abbrechen, wenn der Durschnitt der letzten 10 Durchläufe kein neues globales Minimum erreicht hat. Wieder so gut wie unmöglich in Stapelverarbeitung.

Off-Topic:
Ich hasse diese Typen, die irgendwo noch ein paar Bits aus den Huffmans rauskitzeln, aber dann niemandem sagen, wie sie das geschafft haben.

Bei PNGOUT ist es noch halbwegs verständlich, weil eine Version kommerziell von einer Firma verkauft wird, an der Ken Silverman teilhat – schlicht der Wille nach Geld. Okay – von irgendwas müssen wir alle unseren Arsch am Kacken halten; und wenn man ein Experte ist und was Einzigartiges hat, kann man es sich auch bezahlen lassen. Zumal man die Technologie bei Bedarf lizensieren kann (PNGOUT / KZIP license).

DeflOpt ist in der Hinsicht toll:

I found that one of the ideas I used in BJWFlate was not used by any other zipper. Even if another zipper could compress a file to a size that was smaller than what BJWFlate did, I could still apply that idea to that other zipper's ZIP file and make it smaller.
[…]
I got into an agreement with someone else who would take over DeflOpt because he "would create Linux executables and maintain the project from then on". Obviously, that never happened. Never heard from him again after a few initial emails and a few emails after I had sent him the source code... . I am ready now (meaning 2012) to take back ownership of my program. Any lawyers around to give me free advice? ;)

Zwinker-Smiley! Statt der Welt zu erzählen, was es war, wolltest du was Besonderes sein und hast es für dich behalten. Nein doch nicht – du warst blöd genug, jemand Fremdem die Quelltexte anzuvertrauen, und jetzt weiß keiner mehr, bei wem die Rechte liegen. Zwinker-Smiley! Anstatt dass jetzt alle LZ-Datenströme der Welt ein paar Bytes kleiner werden, nehmen zwei starrsinnige Narren dieses Geheimnis mit ins Grab. Zwinker-Smiley!

Wie bei defluff. Ist es Abandonware. Fick-fack-fantastisch! Ich hoffe, der Autor fühlt sich dadurch sehr besonders; denn das ist er auch. Es ersetzt Wiederholungen durch Literalwiederholungen, aber … mehr weiß keiner; und wenn man es jemals rausfinden will, wird man alle Vermutungen implementieren und testen; oder das Programm rückentwickeln müssen. Toller Dienst an der Menschheit.