Wie ist PNG verlustfrei, wenn es einen Komprimierungsparameter hat?

PNG-Dateien sollen verlustfrei komprimiert werden. Wenn ich mich jedoch in einem Bildeditor wie GIMP befinde und versuche, ein Bild als PNG-Datei zu speichern, wird nach dem Komprimierungsparameter gefragt, der zwischen 0 und 9 liegt das komprimierte Bild, wie macht es PNG verlustfrei?

Erhalte ich nur dann ein verlustfreies Verhalten, wenn ich den Komprimierungsparameter auf 9 setze?

PNG ist verlustfrei. GIMP verwendet in diesem Fall höchstwahrscheinlich einfach nicht das beste Wort. Stellen Sie es sich als "Qualität der Komprimierung" oder mit anderen Worten "Grad der Komprimierung" vor. Bei geringerer Komprimierung erhalten Sie eine größere Datei, die Produktion dauert jedoch kürzer, während bei höherer Komprimierung die Produktion einer kleineren Datei länger dauert. In der Regel erzielen Sie eine geringere Rendite (dh eine geringere Größenverringerung im Vergleich zu der Zeit, die Sie benötigen), wenn Sie die höchsten Komprimierungsstufen erreichen, aber es liegt an Ihnen.

PNG ist komprimiert, aber verlustfrei

Die Komprimierungsstufe ist ein Kompromiss zwischen Dateigröße und Kodierungs- / Dekodierungsgeschwindigkeit. Um dies zu verallgemeinern, haben auch Nicht-Bildformate wie FLAC ähnliche Konzepte.

Unterschiedliche Komprimierungsstufen, gleiche dekodierte Ausgabe

Obwohl die Dateigrößen aufgrund der unterschiedlichen Komprimierungsstufen unterschiedlich sind, ist die tatsächlich decodierte Ausgabe identisch.

Sie können die MD5- Hashes der decodierten Ausgaben mit ffmpegdem MD5-Muxer vergleichen .

Dies zeigt sich am besten an einigen Beispielen:

Erstellen Sie PNG-Dateien:

$ ffmpeg -i input -vframes 1 -compression_level 0 0.png
$ ffmpeg -i input -vframes 1 -compression_level 100 100.png

• Standardmäßig ffmpegwird -compression_level 100für die PNG-Ausgabe verwendet.

Dateigröße vergleichen:

$ du -h *.png
  228K    0.png
  4.0K    100.png

Dekodiere die PNG-Dateien und zeige MD5-Hashes:

$ ffmpeg -loglevel error -i 0.png -f md5 -
3d3fbccf770a51f9d81725d4e0539f83

$ ffmpeg -loglevel error -i 100.png -f md5 -
3d3fbccf770a51f9d81725d4e0539f83

Da beide Hashes identisch sind, können Sie sicher sein, dass die dekodierten Ausgaben (das unkomprimierte, unformatierte Video) exakt gleich sind.

Die PNG-Komprimierung erfolgt in zwei Schritten.

1. Durch die Vorkomprimierung werden die Bilddaten so neu angeordnet, dass sie durch einen Mehrzweck-Komprimierungsalgorithmus besser komprimiert werden können.
2. Die eigentliche Komprimierung wird von DEFLATE durchgeführt, das nach doppelten Byte-Sequenzen sucht und diese durch kurze Token ersetzt.

Da Schritt 2 eine sehr zeit- / ressourcenintensive Aufgabe ist, verwendet die zugrunde liegende zlib-Bibliothek (Kapselung von RAW-DEFLATE) einen Komprimierungsparameter von 1 = Schnellste Komprimierung, 9 = Beste Komprimierung, 0 = Keine Komprimierung. Daher kommt der Bereich 0-9, und GIMP übergibt diesen Parameter einfach an zlib. Beachten Sie, dass Ihr PNG auf Stufe 0 tatsächlich etwas größer ist als die entsprechende Bitmap.

Level 9 ist jedoch nur das "Beste", was zlib versuchen wird, und ist immer noch eine Kompromisslösung .
Um wirklich ein Gefühl dafür zu bekommen, wenn Sie bereit sind, 1000-mal mehr Rechenleistung für eine umfassende Suche aufzuwenden, können Sie mit zopfli anstelle von zlib eine um 3-8% höhere Datendichte erzielen .
Die Komprimierung ist immer noch verlustfrei, es ist nur eine optimalere DEFLATE-Darstellung der Daten. Dies nähert sich den Grenzen einer zlib-kompatiblen Bibliothek und ist daher die beste Komprimierung, die mit PNG erzielt werden kann.

Eine Hauptmotivation für das PNG-Format war die Schaffung eines Ersatzes für GIF, der nicht nur kostenlos war, sondern auch in praktisch jeder Hinsicht eine Verbesserung darstellte. Dadurch ist die PNG-Komprimierung völlig verlustfrei - das heißt, die ursprünglichen Bilddaten können Bit für Bit genau rekonstruiert werden - genau wie in GIF und den meisten TIFF-Formen.

PNG verwendet ein zweistufiges Komprimierungsverfahren:

1. Vorkomprimierung: Filterung (Vorhersage)
2. Komprimierung: DEFLATE (siehe Wikipedia )

Der Vorkomprimierungsschritt wird als Filtern bezeichnet. Hierbei handelt es sich um eine Methode zur reversiblen Transformation der Bilddaten, damit die Hauptkomprimierungsmaschine effizienter arbeiten kann.

Betrachten Sie als einfaches Beispiel eine Folge von Bytes, die gleichmäßig von 1 auf 255 ansteigt:

1, 2, 3, 4, 5, .... 255

Da die Sequenz keine Wiederholung enthält, wird sie entweder sehr schlecht oder gar nicht komprimiert. Eine triviale Modifikation der Sequenz - nämlich das erste Byte in Ruhe zu lassen, aber jedes nachfolgende Byte durch den Unterschied zwischen ihm und seinem Vorgänger zu ersetzen - transformiert die Sequenz in eine extrem komprimierbare Menge:

1, 1, 1, 1, 1, .... 1

Die obige Transformation ist verlustfrei, da keine Bytes ausgelassen wurden, und ist vollständig umkehrbar. Die komprimierte Größe dieser Serie wird stark reduziert, aber die ursprüngliche Serie kann immer noch perfekt wiederhergestellt werden.

Tatsächliche Bilddaten sind selten so perfekt, aber das Filtern verbessert die Komprimierung von Graustufen- und Echtfarbenbildern und kann auch bei einigen Palettenbildern hilfreich sein. PNG unterstützt fünf Filtertypen, und ein Encoder kann für jede Pixelzeile im Bild einen anderen Filter verwenden:

Der Algorithmus arbeitet mit Bytes, aber für große Pixel (z. B. 24-Bit-RGB oder 64-Bit-RGBA) werden nur entsprechende Bytes verglichen, was bedeutet, dass die roten Komponenten der Pixelfarben getrennt von den grünen und blauen Pixelkomponenten behandelt werden.

Um den besten Filter für jede Zeile auszuwählen, müsste ein Encoder alle möglichen Kombinationen testen. Dies ist eindeutig unmöglich, da selbst ein Bild mit 20 Zeilen das Testen von mehr als 95 Billionen Kombinationen erfordern würde, wobei das "Testen" das Filtern und Komprimieren des gesamten Bildes umfassen würde.

Komprimierungsstufen werden normalerweise als Zahlen zwischen 0 (keine) und 9 (beste) definiert. Diese beziehen sich auf Kompromisse zwischen Geschwindigkeit und Größe und darauf, wie viele Kombinationen von Zeilenfiltern ausprobiert werden sollen. Bezüglich dieser Komprimierungsstufen gibt es keine Standards. Daher verfügt jeder Bildeditor möglicherweise über eigene Algorithmen, um zu bestimmen, wie viele Filter bei der Optimierung der Bildgröße verwendet werden sollen.

Komprimierungsstufe 0 bedeutet, dass überhaupt keine Filter verwendet werden, was zwar schnell, aber verschwenderisch ist. Höhere Werte bedeuten, dass immer mehr Kombinationen für Bildzeilen ausprobiert werden und nur die besten beibehalten werden.

Ich würde vermuten, dass der einfachste Ansatz für die beste Komprimierung darin besteht, jede Zeile mit jedem Filter inkrementell zu komprimieren, das kleinste Ergebnis zu speichern und für die nächste Zeile zu wiederholen. Dies bedeutet, dass das gesamte Bild fünfmal gefiltert und komprimiert wird. Dies kann ein angemessener Kompromiss für ein Bild sein, das viele Male übertragen und decodiert wird. Niedrigere Komprimierungswerte können nach Ermessen des Werkzeugentwicklers weniger bewirken.

Zusätzlich zu Filtern kann die Komprimierungsstufe auch die zlib-Komprimierungsstufe beeinflussen, die eine Zahl zwischen 0 (keine Deflate) und 9 (maximale Deflate) ist. Wie sich die angegebenen 0-9-Stufen auf die Verwendung von Filtern auswirken, die die Hauptoptimierungsfunktion von PNG darstellen, hängt weiterhin vom Entwickler des Tools ab.

Die Schlussfolgerung ist, dass PNG über einen Komprimierungsparameter verfügt, der die Dateigröße erheblich reduzieren kann, ohne dass auch nur ein Pixel verloren geht.

Quellen:

Wikipedia Portable Network Graphics
libpng-Dokumentation Kapitel 9 - Komprimierung und Filterung

OK, ich bin zu spät für das Kopfgeld, aber hier ist trotzdem meine Antwort.

PNG ist immer verlustfrei . Es verwendet einen Deflate / Inflate-Algorithmus, ähnlich wie er in Zip-Programmen verwendet wird.

Der Deflate-Algorithmus durchsucht wiederholte Sequenzen von Bytes und ersetzt diese durch Tags. Die Einstellung für die Komprimierungsstufe gibt an, wie viel Aufwand das Programm benötigt, um die optimale Kombination von Byte-Sequenzen zu finden, und wie viel Speicher dafür reserviert ist. Es ist ein Kompromiss zwischen Zeit und Speichernutzung im Vergleich zur komprimierten Dateigröße. Moderne Computer sind jedoch so schnell und verfügen über genügend Speicher, dass nur die höchste Komprimierungseinstellung verwendet werden muss.

Viele PNG-Implementierungen verwenden die zlib-Bibliothek zur Komprimierung. Zlib hat neun Komprimierungsstufen, 1-9. Ich kenne die Interna von Gimp nicht, aber da es die Komprimierungsstufen 0-9 (0 = keine Komprimierung) hat, würde ich davon ausgehen, dass diese Einstellung einfach die Komprimierungsstufe von zlib auswählt.

Der Deflate-Algorithmus ist ein allgemeiner Komprimierungsalgorithmus , der nicht zum Komprimieren von Bildern entwickelt wurde. Im Gegensatz zu den meisten anderen verlustfreien Bilddateiformaten ist das PNG-Format nicht darauf beschränkt. Die PNG-Komprimierung nutzt das Wissen, dass ein 2D-Bild komprimiert wird . Dies wird durch sogenannte Filter erreicht .

(Filter ist hier eigentlich ein etwas irreführender Begriff. Es ändert den Bildinhalt nicht wirklich, sondern codiert ihn nur anders. Genauere Bezeichnung wäre Delta-Encoder.)

Die PNG-Spezifikation spezifiziert 5 verschiedene Filter (einschließlich 0 = keine). Der Filter ersetzt absolute Pixelwerte durch Abweichungen vom vorherigen Pixel nach links, nach oben, diagonal oder durch Kombinationen davon. Dies kann das Kompressionsverhältnis erheblich verbessern. Jede Scanlinie im Bild kann einen anderen Filter verwenden. Der Encoder kann die Komprimierung optimieren, indem er für jede Zeile den besten Filter auswählt.

Einzelheiten zum PNG-Dateiformat finden Sie unter PNG-Spezifikation .

Da es praktisch unendlich viele Kombinationen gibt, können nicht alle ausprobiert werden. Daher wurden verschiedene Arten von Strategien entwickelt, um eine wirksame Kombination zu finden. Die meisten Bildbearbeiter versuchen wahrscheinlich nicht einmal, die Filter zeilenweise zu optimieren, sondern verwenden lediglich feste Filter (höchstwahrscheinlich Paeth).

Ein Kommandozeilenprogramm pngcrush versucht verschiedene Strategien, um das beste Ergebnis zu erzielen . Die Größe von PNG-Dateien, die mit anderen Programmen erstellt wurden, kann erheblich reduziert werden. Bei größeren Bildern kann dies jedoch einige Zeit in Anspruch nehmen. Siehe Source Forge - pngcrush .

Komprimierungsgrad in verlustfreien Sachen ist immer nur der Handel mit codierten Ressourcen (normalerweise Zeit, manchmal auch RAM) im Vergleich zur Bitrate. Qualität ist immer 100%.

Natürlich können verlustfreie Kompressoren NIEMALS eine tatsächliche Kompression garantieren . Zufällige Daten sind inkompressibel, es gibt kein zu findendes Muster und keine Ähnlichkeit. Shannon Informationstheorie und all das. Der springende Punkt bei der verlustfreien Datenkomprimierung ist, dass Menschen normalerweise mit nicht zufälligen Daten arbeiten. Für die Übertragung und Speicherung können wir sie jedoch auf so wenige Bits wie möglich komprimieren. Hoffentlich so nah wie möglich an der Kolmogorov-Komplexität des Originals.

Egal, ob es sich um generische Zip- oder 7z-Daten, PNG-Bilder, Flac-Audio oder H.264-Video (im verlustfreien Modus) handelt, es ist dasselbe. Bei einigen Komprimierungsalgorithmen, wie z. B. lzma (7zip) und bzip2, erhöht das Hochdrehen der Komprimierungseinstellung die CPU-Zeit des DECODERS (bzip2) oder häufiger nur die benötigte RAM-Größe (lzma und bzip2 und h.264 mit mehr Referenzrahmen). . Häufig muss der Decoder mehr decodierte Ausgabe im RAM speichern, da das Decodieren des nächsten Bytes auf ein Byte verweisen kann, das vor vielen Megabytes decodiert wurde (z. B. würde ein Videoframe, das demjenigen vor einer halben Sekunde am ähnlichsten ist, mit Verweisen auf 12 Frames zurück codiert ). Dasselbe gilt für bzip2 und die Auswahl einer großen Blockgröße, aber das dekomprimiert auch langsamer. lzma hat ein Wörterbuch mit variabler Größe, und Sie könnten Dateien erstellen, für die 1 erforderlich wäre.

Erstens ist PNG immer verlustfrei. Das scheinbare Paradoxon beruht auf der Tatsache, dass zwei verschiedene Arten der Komprimierung möglich sind (für jede Art von Daten): verlustbehaftet und verlustfrei.

Die verlustfreie Komprimierung komprimiert die Daten (dh die Dateigröße) mithilfe verschiedener Tricks, wobei alles erhalten bleibt und keine Annäherung erfolgt. Infolgedessen ist es möglich, dass verlustfreie Komprimierung überhaupt nicht in der Lage ist, Dinge zu komprimieren. (Technisch gesehen können Daten mit hoher Entropie für verlustfreie Methoden nur sehr schwer oder gar nicht komprimierbar sein.) Eine verlustbehaftete Komprimierung nähert sich den tatsächlichen Daten an, die Approximation ist jedoch unvollständig.

Hier ist ein triviales Beispiel für verlustfreie Komprimierung: Wenn Sie ein Bild aus 1.000 schwarzen Pixeln haben, können Sie anstelle des 1000-fachen Speicherns des Schwarzwerts einen Zählwert (1000) und einen Schwarzwert speichern und so 1000 Pixel komprimieren. " Bild "in nur zwei Zahlen. (Dies ist eine rohe Form einer verlustfreien Komprimierungsmethode, die als Lauflängencodierung bezeichnet wird.)