Quite OK Image Format
# Quite OK Image Format

Das Quite OK Image Format (QOI, englisch: Bildformat, das ganz okay ist) ist ein Dateiformat zur verlustfrei komprimierten Speicherung von Rastergrafiken. Es wurde ab 2021 von Dominic Szablewski entworfen. Im Gegensatz zu konkurrierenden Formaten wie PNG zeichnet sich QOI gleichzeitig durch eine einfachere und schnellere, aber in vielen Fällen ähnlich effiziente Kompression aus. Es handelt sich um einen offenen Standard mit freier Referenzimplementierung.

## Geschichte

Szablewski veröffentlichte das QOI-Format erstmals mit einem Blogartikel auf seiner Website PhobosLab am 24. November 2021. Er drückte seinen Unmut über existierende Multimedia-Dateiformate aus, die seiner Ansicht nach durch einen Konsortium-Designprozess überaus kompliziert und voller nutzloser Funktionen wären. Als Beispiel führt er dabei das Copyright-Flag im MPEG-1-Header an. Laut eigener Aussage hat Szablewski keine Ahnung von komplexer Datenkompression und QOI sei zufällig aus Experimenten mit einfachen Bildkompressionsverfahren entstanden. Zusammen mit dem Artikel veröffentlichte Szablewski die erste Version der Referenzimplementierung.
Als Folge auf die überraschend guten Ergebnisse des QOI-Formats gab es insbesondere auf Twitter einige Resonanz auf Szablewskis Arbeit. Innerhalb der nächsten Monate entstanden Implementierungen für eine Vielzahl an Programmiersprachen und Anwendungen (siehe Verbreitung). Nach einigen Änderungen, die auf Wünsche der Nutzer eingingen, veröffentlichte Szablewski die finale Spezifikation der Version 1.0 am 1. Mai 2022 auf der neuen, formateigenen Website. Laut Dokumentation der Referenzimplementierung sieht Szablewski QOI als abgeschlossenes Format und hat nicht vor, eine weitere Version zu veröffentlichen.

## Format

QOI ist ein Format zur verlustfreien Kompression von Rastergrafiken, d. h. bei der Speicherung gehen keine Informationen des Bildes verloren. Für die Kompression setzt QOI mehrere Verfahren ein, zwischen denen auf der Ebene einzelner Pixel gewechselt werden kann:
* Wörterbuchkompression
* Delta-Kodierung in einer von mehreren Bittiefen
* Lauflängenkodierung
* unkomprimierte Speicherung einzelner Pixel, falls die vorherigen Verfahren fehlschlagen
QOI unterstützt die Speicherung von Farbbildern beliebiger Größe (bis $2^{32}\times 2^{32}$ Pixel) im RGB- oder RGBA-Format mit 24 bzw. 32 Bit pro Pixel (8 Bit pro Kanal). Der Farbraum ist entweder sRGB oder ein linearer RGB(A)-Farbraum.

### Details

Die konkrete Funktionsweise des Formats ist so einfach, dass die Spezifikation auf eine DIN-A4-Seite passt. QOI beginnt mit einem 14-Byte-Header der folgenden Form:
| Bytes | 0–3 | 4–7 | 8–11 | 12 | 13 |
| | qoif | Breite in Pixel (Big-endian) | Höhe in Pixel (Big-endian) | Kanäle | Farbraum |
Unterstützte Kanalzahlen sind momentan 3 für RGB und 4 für RGBA. Die unterstützten Farbräume sind 0 für sRGB und 1 für lineares RGB(A).
Die restlichen Bytes kodieren die Pixel des Bilds von links nach rechts, oben nach unten, reihenweise. Als Wörterbuch verwenden Enkoder und Dekoder ein 64-Pixel-Array, in welches ein Pixel (r, g, b, a) mithilfe der Hashfunktion $(3r+5g+7b+11a)\mod 64$ indiziert. Jedes geschriebene oder gelesene Pixel (egal, wie kodiert) wird in das Wörterbuch aufgenommen.
Es gibt sechs verschiedene Chunks genannte Dateneinheiten, die meist ein Pixel kodieren (Ausnahme: Lauflängenkodierung, siehe unten). Chunks beginnen mit einem identifizierenden Tag und beginnen und enden immer an Byte-Grenzen.
Die RGB- oder RGBA-Chunks kodieren ein einzelnes unkomprimiertes Pixel. Dabei ist a=1 für einen RGBA-Chunk, was auch die Größe des Chunks bezeichnet (falls a=1, ist der Chunk 5 Byte groß, andernfalls 4).
RGB / RGBA :
| Byte | 0 | 1 | 2 | 3 | (4) |
| | Tag: 1 1 1 1 1 1 1 a | Rot | Grün | Blau | Alpha (nur falls a=1) |
Der Index-Chunk kodiert ein Pixel, welches im Wörterbuch vorliegt.
INDEX :
| Bit | 7-6 | 5-0 |
| | Tag: 0 0 | 6-Bit Index ins Wörterbuch |
Die Differenz-Chunks kodieren ein Pixel, welches nur geringfügig von seinem Vorgänger abweicht. Die Deltawerte sind Ganzzahlen mit einer Bias von -2 im DIFF-Chunk,-8 in Rot und Blau im LUMA-Chunk, sowie -32 in Grün im LUMA-Chunk. Im LUMA-Chunk werden die Differenzen in Rot und Blau nicht alleinstehend gespeichert, sondern wiederum als Differenz vom Grün-Delta, weshalb sie mit 4 Bit statt 6 Bit auskommen.
DIFF :
| Bit | 7-6 | 5-4 | 3-2 | 1-0 |
| | Tag: 0 1 | Rot-Delta | Grün-Delta | Blau-Delta |
LUMA :
| Byte | 0 | 0 | 1 | 1 |
| Bit | 7-6 | 5-0 | 7-4 | 3-0 |
| | Tag: 1 0 | Grün-Delta | Grün-Delta $-$ Rot-Delta | Grün-Delta $-$ Blau-Delta |
Der Lauflängen-Chunk kodiert eine Reihe an Pixel, die zum vorhergehenden, anders kodierten Pixel identisch sind. Die Lauflänge wird mit einer Bias von -1 gespeichert, da eine Lauflänge von 0 keinen Sinn ergibt. Die Lauflängenwerte 63 und 64 sind nicht zulässig, da somit der Chunk wie der Beginn eines RGB oder RGBA-Chunk aussehen würde.
RUN :
| Bit | 7-6 | 5-0 |
| | Tag: 1 1 | Lauflänge |
Zur Kodierung eines Bilds ins QOI-Format gibt es oft mehrere Möglichkeiten; es können auch alle Pixel unkomprimiert gespeichert werden. Wenn die Chunks jedoch in der Priorität RUN, INDEX, DIFF, LUMA, RGB(A) eingesetzt werden, ergibt sich immer eine optimale Kompression. Daraus folgt eine Laufzeit von linearer Größenordnung (siehe O-Notation) nicht nur für Dekompression, sondern auch für Kompression.

## Vergleich mit PNG

Die von Szablewski durchgeführten Benchmarks auf über 4000 öffentlich verfügbaren Beispieldateien, die die QOI-Referenzimplementierung mit Libpng und stbi vergleichen, kommen zu folgenden Ergebnissen:
* Im Durchschnitt liegt die Kompressionsstärke bei etwa 28 % und damit zwischen dem stark komprimierenden libpng (24 %) und dem mäßig stark komprimierenden stbi (34 %).
* QOI komprimiert Bilder im Schnitt etwa 21× so schnell und dekomprimiert 3,4× so schnell wie die vergleichsweise schnelle stbi-Implementierung.
QOI bietet jedoch im Vergleich zu PNG nur vier mögliche Farbformate; PNG erlaubt indizierte Farben und Graustufen sowie Farbraum-Metadaten. Allgemein sind Metadaten, die über das Farbraum-Byte und die Bildgröße hinausgehen, in QOI nicht speicherbar.

## Verbreitung

Stand Juni 2022 unterstützt keiner der Standard-Bildbetrachter von Android, Windows, macOS oder iOS QOI. Jedoch existieren Plugins und Direktunterstützung für QOI-Dateien in Windows Explorer, üblichen Bildbearbeitungsprogrammen, z. B. GIMP und Paint.NET, und Ansichtsprogrammen, z. B. IrfanView.

### Implementierungen

Die QOI-Referenzimplementierung ist in der Programmiersprache C geschrieben und umfasst etwa 600 Zeilen einschließlich Spezifikation. Sie ist unter der MIT-Lizenz quelloffen verfügbar. Zusätzlich dazu existieren eine Reihe an alternativen Implementierungen in verschiedenen Programmiersprachen.