QOI – O(n)-verlustfreie Bildkomprimierung

<p>„Quite OK Image“ <br /> - Führt RGB/RGBA-Komprimierung mit einer Größe ähnlich wie PNG aus<br /> → Die Komprimierung ist 20x–50x schneller, das Dekomprimieren 3–4x schneller <br /> → Open-Source-C-Code als Single-Header-Datei mit 300 Zeilen <br /> → Einfache Single-Thread-Implementierung ohne SIMD <br /> - Technische Details <br /> → Bildkodierung/-dekodierung in einem einzigen Durchlauf <br /> → Jedes Pixel wird nur einmal verarbeitet, und jedes Pixel wird mit einer von vier Methoden kodiert <br /> ⇨ Ist es identisch mit dem unmittelbar vorherigen Pixel, wird die Run-Length des vorherigen Pixels erhöht; andernfalls wird das neue Pixel mit einer der drei folgenden Methoden gepackt <br /> ⇨ Ist es identisch mit einem bereits verarbeiteten Pixel, wird der Index dieses Pixels verwendet. Dafür gibt es ein Array für die letzten 64 Pixel<br /> ⇨ Wenn es sich nicht stark vom vorherigen Pixel unterscheidet, werden die RGBA-Differenzwerte gespeichert <br /> ⇨ Wenn die drei vorherigen Methoden fehlschlagen, werden die RGBA-Werte des Pixels gespeichert. Allerdings werden nur die Teile gespeichert, die sich vom vorherigen Pixel unterscheiden </p>

[lifthrasiir]

<p>Etwas überspitzt formuliert ist QOI im Grunde PNG ohne zlib, bei dem nur das Filtering übrig geblieben und dann verbessert worden ist.<br /> <br /> Der von PNG ebenfalls verwendete Kompressionsalgorithmus zlib/gzip/DEFLATE ist zwar weit verbreitet, aber auch sehr alt und daher nicht besonders effizient. Außerdem beruhen zlib und andere Algorithmen aus der LZ77-Familie auf der Grundannahme, dass „unter den zuletzt gesehenen Bytes mehrere aufeinanderfolgende Bytefolgen identisch vorkommen“ (z. B. bei der Eingabe „to be or not to be“ wird ausgenutzt, dass „to be“ zweimal vorkommt). Bei Bilddaten greift diese Annahme jedoch nicht besonders gut. Deshalb verwendet PNG zlib faktisch nur für die Entropiekodierung – also als Ansatz, auf Basis der Wahrscheinlichkeit des nächsten Bytes ohne weiteren zusätzlichen Kontext zu komprimieren – und versucht in einem Vorverarbeitungsschritt mit einfachem Filtering, die an zlib übergebenen Daten möglichst gut an diese Annahme anzupassen; wirklich effizient ist das allerdings nicht.<br /> <br /> Moderne verlustfreie Bildformate verbessern das im Wesentlichen auf zwei Arten: entweder durch bessere Pixelvorhersage als Entsprechung zum Filtering von PNG (etwa durch eine deutlich größere Zahl von Filtertypen oder dadurch, dass auf verschiedene Bildbereiche unterschiedliche Filter angewendet werden) oder durch bessere Entropiekodierung als Entsprechung zu zlib in PNG. Der Ansatz von QOI ist ähnlich, zeichnet sich der Einfachheit halber aber dadurch aus, dass bei der Pixelvorhersage überhaupt keine Pixel oberhalb der aktuellen Position verwendet werden und dass auf Entropiekodierung verzichtet wird, stattdessen mehrere empirisch entwickelte Differenzkodierungen (Delta-Kodierungen) bereitstehen. Vor allem wegen der ersten Eigenschaft ist die Kompressionsrate – unabhängig von der Kompressions-/Dekompressionsgeschwindigkeit – tendenziell sogar schlechter als bei PNG; das ließe sich vermutlich verbessern, wenn man etwas von der Einfachheit opfert.</p>

[xguru]

<p>Oh, danke für die zusätzliche Erklärung. Das ist interessant.</p>

[xguru]

<p>Es dürfte zwar schwer sein, es als Ersatz für andere Formate einzusetzen, aber der Code ist schlicht, und auch die Implementierung wird gut erklärt – daher wirkt es wie unterhaltsamer Code zum Lesen.<br /> https://github.com/phoboslab/qoi/blob/master/qoi.h<br /> </p>