Spezifikation für WebP Lossless Bitstream

Jyrki Alakuijala, Ph.D., Google LLC, 9. März 2023

Zusammenfassung

WebP Lossless ist ein Bildformat für die verlustfreie Komprimierung von ARGB-Bildern. Im verlustfreien Format werden die Pixelwerte genau gespeichert und wiederhergestellt, einschließlich der Farbwerte für vollständig transparente Pixel. Für die Komprimierung der Bulk-Daten werden ein universeller Algorithmus für die sequentielle Datenkomprimierung (LZ77), die Präfixcodierung und ein Farbcache verwendet. Es wurde gezeigt, dass die Dekodierungsgeschwindigkeit höher als bei PNG ist und die Komprimierung um 25% dichter als beim aktuellen PNG-Format ist.

1 Einleitung

In diesem Dokument wird die komprimierte Darstellung von verlustfreien WebP-Bildern beschrieben. Es dient als detaillierte Referenz für die Implementierung des verlustfreien WebP-Encoders und -Decoders.

In diesem Dokument wird die Syntax der Programmiersprache C verwendet, um den Bitstream zu beschreiben. Außerdem wird davon ausgegangen, dass eine Funktion zum Lesen von Bits, ReadBits(n), vorhanden ist. Die Bytes werden in der natürlichen Reihenfolge des Streams gelesen, der sie enthält, und die Bits jedes Bytes werden in der Reihenfolge „Least Significant Bit First“ (LSB-First) gelesen. Wenn mehrere Bits gleichzeitig gelesen werden, wird die Ganzzahl aus den ursprünglichen Daten in der ursprünglichen Reihenfolge erstellt. Die höchstwertigen Bits der zurückgegebenen Ganzzahl sind auch die höchstwertigen Bits der Originaldaten. Die Aussage

b = ReadBits(2);

entspricht den beiden folgenden Aussagen:

b = ReadBits(1);
b |= ReadBits(1) << 1;

Wir gehen davon aus, dass jede Farbkomponente (Alpha, Rot, Blau und Grün) mit einem 8‑Bit-Byte dargestellt wird. Der entsprechende Typ wird als uint8 definiert. Ein vollständiges ARGB-Pixel wird durch einen Typ namens uint32 dargestellt, der eine vorzeichenlose Ganzzahl mit 32 Bit ist. Im Code, der das Verhalten der Transformationen zeigt, sind diese Werte in den folgenden Bits codiert: Alpha in den Bits 31..24, Rot in den Bits 23..16, Grün in den Bits 15..8 und Blau in den Bits 7..0. Implementierungen des Formats können jedoch intern eine andere Darstellung verwenden.

Ein verlustfreies WebP-Bild enthält im Allgemeinen Header-Daten, Transformationsinformationen und die eigentlichen Bilddaten. Die Header enthalten die Breite und Höhe des Bildes. Ein verlustfreies WebP-Bild kann vor der Entropiecodierung vier verschiedene Arten von Transformationen durchlaufen. Die Transformationsinformationen im Bitstream enthalten die Daten, die zum Anwenden der entsprechenden inversen Transformationen erforderlich sind.

2 Nomenklatur

ARGB

Ein Pixelwert, der aus Alpha-, Rot-, Grün- und Blauwerten besteht.

ARGB-Bild

Ein zweidimensionales Array mit ARGB-Pixeln.

Farb-Cache

Ein kleines Hash-adressiertes Array zum Speichern der zuletzt verwendeten Farben, damit sie mit kürzeren Codes abgerufen werden können.

Bild mit Farbindexierung

Ein eindimensionales Bild mit Farben, das mit einer kleinen Ganzzahl (bis zu 256 bei verlustfreiem WebP) indexiert werden kann.

Bild farblich transformieren

Ein zweidimensionales Bild mit niedriger Auflösung, das Daten zu Korrelationen von Farbkomponenten enthält.

Distanzzuordnung

Ändert LZ77-Abstände so, dass die kleinsten Werte für Pixel in zweidimensionaler Nähe verwendet werden.

Entropiebild

Ein zweidimensionales Bild mit niedriger Auflösung, das angibt, welche Entropiecodierung in einem entsprechenden Quadrat im Bild verwendet werden soll. Das heißt, jedes Pixel ist ein Meta-Präfixcode.

LZ77

Ein auf einem Wörterbuch basierender Gleitfenster-Komprimierungsalgorithmus, der entweder Symbole ausgibt oder sie als Sequenzen vergangener Symbole beschreibt.

Meta-Präfixcode

Eine kleine Ganzzahl (bis zu 16 Bit), die ein Element in der Metapräfixtabelle indexiert.

Vorhersagebild

Ein zweidimensionales Bild mit niedriger Auflösung, das angibt, welcher räumliche Vorhersagealgorithmus für ein bestimmtes Quadrat im Bild verwendet wird.

Präfixcode

Eine klassische Methode für die Entropiecodierung, bei der für häufigere Codes eine geringere Anzahl von Bits verwendet wird.

Präfixcodierung

Eine Möglichkeit, größere Ganzzahlen zu codieren. Dabei werden einige Bits der Ganzzahl mit einem Entropiecode codiert und die verbleibenden Bits werden roh codiert. So können die Beschreibungen der Entropiecodes relativ klein bleiben, auch wenn der Bereich der Symbole groß ist.

Scanline-Reihenfolge

Eine Verarbeitungsreihenfolge von Pixeln (von links nach rechts und von oben nach unten), beginnend mit dem Pixel oben links. Wenn eine Zeile abgeschlossen ist, fahren Sie mit der Spalte ganz links in der nächsten Zeile fort.

3 RIFF-Header

Der RIFF-Container befindet sich am Anfang des Headers. Sie besteht aus den folgenden 21 Byte:

1. String „RIFF“.
2. Ein Little-Endian-Wert mit 32 Bit für die Chunk-Länge, der die Gesamtgröße des Chunks angibt, der vom RIFF-Header gesteuert wird. Normalerweise entspricht dies der Nutzlastgröße (Dateigröße minus 8 Byte: 4 Byte für die „RIFF“-Kennung und 4 Byte zum Speichern des Werts selbst).
3. String „WEBP“ (RIFF-Containername).
4. String „VP8L“ (FourCC für verlustfrei codierte Bilddaten).
5. Ein Little-Endian-32-Bit-Wert für die Anzahl der Byte im verlustfreien Stream.
6. 1-Byte-Signatur 0x2f.

Die ersten 28 Bits des Bitstreams geben die Breite und Höhe des Bildes an. Breite und Höhe werden als 14‑Bit-Ganzzahlen decodiert:

int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;

Die 14-Bit-Präzision für Bildbreite und ‑höhe begrenzt die maximale Größe eines verlustfreien WebP-Bilds auf 16.384 × 16.384 Pixel.

Das Bit „alpha_is_used“ ist nur ein Hinweis und sollte sich nicht auf die Decodierung auswirken. Er sollte auf 0 gesetzt werden, wenn alle Alphawerte im Bild 255 sind, und auf 1, wenn dies nicht der Fall ist.

int alpha_is_used = ReadBits(1);

Die version_number ist ein 3-Bit-Code, der auf 0 gesetzt werden muss. Jeder andere Wert sollte als Fehler behandelt werden.

int version_number = ReadBits(3);

4 Transformationen

Die Transformationen sind umkehrbare Manipulationen der Bilddaten, die die verbleibende symbolische Entropie durch Modellierung von räumlichen und Farbkorrelationen reduzieren können. Sie können die endgültige Komprimierung dichter machen.

Ein Bild kann vier Arten von Transformationen durchlaufen. Ein Bit mit dem Wert 1 gibt an, dass eine Transformation vorhanden ist. Jede Transformation darf nur einmal verwendet werden. Die Transformationen werden nur für das ARGB-Bild auf Hauptebene verwendet. Die Bilder mit niedrigerer Auflösung (Farbtransformationsbild, Entropiebild und Vorhersagebild) haben keine Transformationen, nicht einmal das 0-Bit, das das Ende der Transformationen angibt.

Normalerweise verwendet ein Encoder diese Transformationen, um die Shannon-Entropie im Residualbild zu verringern. Die transformierten Daten können auch auf Grundlage der Entropieminimierung bestimmt werden.

while (ReadBits(1)) {  // Transform present.
  // Decode transform type.
  enum TransformType transform_type = ReadBits(2);
  // Decode transform data.
  ...
}

// Decode actual image data (Section 5).

Wenn eine Transformation vorhanden ist, geben die nächsten zwei Bits den Transformationstyp an. Es gibt vier Arten von Transformationen.

enum TransformType {
  PREDICTOR_TRANSFORM             = 0,
  COLOR_TRANSFORM                 = 1,
  SUBTRACT_GREEN_TRANSFORM        = 2,
  COLOR_INDEXING_TRANSFORM        = 3,
};

Auf den Transformationstyp folgen die Transformationsdaten. „Transform data“ enthält die Informationen, die zum Anwenden der inversen Transformation erforderlich sind, und hängt vom Transformationstyp ab. Die inversen Transformationen werden in der umgekehrten Reihenfolge angewendet, in der sie aus dem Bitstream gelesen werden, d. h. die letzte zuerst.

Als Nächstes beschreiben wir die Transformation von Daten für verschiedene Typen.

4.1 Vorhersagevariablen transformieren

Mit der Vorhersagetransformation kann die Entropie reduziert werden, indem die Tatsache genutzt wird, dass benachbarte Pixel oft korreliert sind. Bei der Vorhersagetransformation wird der aktuelle Pixelwert anhand der bereits decodierten Pixel (in Zeilenreihenfolge) vorhergesagt und nur der Residualwert (tatsächlich – vorhergesagt) wird codiert. Die grüne Komponente eines Pixels definiert, welcher der 14 Vorhersagewerte in einem bestimmten Block des ARGB-Bildes verwendet wird. Der Vorhersagemodus bestimmt den Typ der zu verwendenden Vorhersage. Wir teilen das Bild in Quadrate auf und alle Pixel in einem Quadrat verwenden denselben Vorhersagemodus.

Die ersten 3 Bits der Vorhersagedaten definieren die Blockbreite und ‑höhe in Bit.

int size_bits = ReadBits(3) + 2;
int block_width = (1 << size_bits);
int block_height = (1 << size_bits);
#define DIV_ROUND_UP(num, den) (((num) + (den) - 1) / (den))
int transform_width = DIV_ROUND_UP(image_width, 1 << size_bits);

Die Transformationsdaten enthalten den Vorhersagemodus für jeden Block des Bildes. Es handelt sich um ein Bild mit niedrigerer Auflösung, bei dem die grüne Komponente eines Pixels definiert, welcher der 14 Vorhersagevariablen für alle block_width * block_height-Pixel in einem bestimmten Block des ARGB-Bildes verwendet wird. Dieses Bild mit niedrigerer Auflösung wird mit denselben Techniken codiert, die in Kapitel 5 beschrieben werden.

Die Anzahl der Blockspalten, transform_width, wird für die zweidimensionale Indexierung verwendet. Für ein Pixel (x, y) kann die entsprechende Filterblockadresse so berechnet werden:

int block_index = (y >> size_bits) * transform_width +
                  (x >> size_bits);

Es gibt 14 verschiedene Vorhersagemodi. In jedem Vorhersagemodus wird der aktuelle Pixelwert anhand von einem oder mehreren benachbarten Pixeln vorhergesagt, deren Werte bereits bekannt sind.

Wir haben die benachbarten Pixel (TL, T, TR und L) des aktuellen Pixels (P) so ausgewählt:

O    O    O    O    O    O    O    O    O    O    O
O    O    O    O    O    O    O    O    O    O    O
O    O    O    O    TL   T    TR   O    O    O    O
O    O    O    O    L    P    X    X    X    X    X
X    X    X    X    X    X    X    X    X    X    X
X    X    X    X    X    X    X    X    X    X    X

Dabei steht „TL“ für „oben links“, „T“ für „oben“, „TR“ für „oben rechts“ und „L“ für „links“. Zum Zeitpunkt der Vorhersage eines Werts für P wurden bereits alle O-, TL-, T-, TR- und L-Pixel verarbeitet. Das P-Pixel und alle X-Pixel sind unbekannt.

Angesichts der vorherigen benachbarten Pixel werden die verschiedenen Vorhersagemodi wie folgt definiert.

Average2 wird für jede ARGB-Komponente so definiert:

uint8 Average2(uint8 a, uint8 b) {
  return (a + b) / 2;
}

„Predictor auswählen“ ist so definiert:

uint32 Select(uint32 L, uint32 T, uint32 TL) {
  // L = left pixel, T = top pixel, TL = top-left pixel.

  // ARGB component estimates for prediction.
  int pAlpha = ALPHA(L) + ALPHA(T) - ALPHA(TL);
  int pRed = RED(L) + RED(T) - RED(TL);
  int pGreen = GREEN(L) + GREEN(T) - GREEN(TL);
  int pBlue = BLUE(L) + BLUE(T) - BLUE(TL);

  // Manhattan distances to estimates for left and top pixels.
  int pL = abs(pAlpha - ALPHA(L)) + abs(pRed - RED(L)) +
           abs(pGreen - GREEN(L)) + abs(pBlue - BLUE(L));
  int pT = abs(pAlpha - ALPHA(T)) + abs(pRed - RED(T)) +
           abs(pGreen - GREEN(T)) + abs(pBlue - BLUE(T));

  // Return either left or top, the one closer to the prediction.
  if (pL < pT) {
    return L;
  } else {
    return T;
  }
}

Die Funktionen ClampAddSubtractFull und ClampAddSubtractHalf werden für jede ARGB-Komponente so ausgeführt:

// Clamp the input value between 0 and 255.
int Clamp(int a) {
  return (a < 0) ? 0 : (a > 255) ? 255 : a;
}

int ClampAddSubtractFull(int a, int b, int c) {
  return Clamp(a + b - c);
}

int ClampAddSubtractHalf(int a, int b) {
  return Clamp(a + (a - b) / 2);
}

Für einige Grenzpixel gelten spezielle Regeln. Wenn eine Vorhersagetransformation vorhanden ist, ist der vorhergesagte Wert für das Pixel oben links im Bild unabhängig vom Modus [0..13] für diese Pixel 0xff000000. Alle Pixel in der obersten Zeile sind L-Pixel und alle Pixel in der linken Spalte sind T-Pixel.

Die Behandlung des TR-Pixels für Pixel in der Spalte ganz rechts ist die Ausnahme. Die Pixel in der Spalte ganz rechts werden mit den Modi[0..13]vorhersagt, genau wie Pixel, die nicht am Rand liegen. Das Pixel ganz links in derselben Zeile wie das aktuelle Pixel wird jedoch stattdessen als TR-Pixel verwendet.

Der endgültige Pixelwert wird berechnet, indem jeder Kanal des vorhergesagten Werts zum codierten Residualwert addiert wird.

void PredictorTransformOutput(uint32 residual, uint32 pred,
                              uint8* alpha, uint8* red,
                              uint8* green, uint8* blue) {
  *alpha = ALPHA(residual) + ALPHA(pred);
  *red = RED(residual) + RED(pred);
  *green = GREEN(residual) + GREEN(pred);
  *blue = BLUE(residual) + BLUE(pred);
}

4.2 Farbtransformation

Ziel der Farbtransformation ist es, die R-, G- und B-Werte der einzelnen Pixel zu entkorrelieren. Bei der Farbtransformation wird der grüne (G) Wert beibehalten, der rote (R) Wert basierend auf dem grünen Wert transformiert und der blaue (B) Wert basierend auf dem grünen und dann auf dem roten Wert transformiert.

Wie bei der Vorhersagetransformation wird das Bild zuerst in Blöcke unterteilt und für alle Pixel in einem Block wird derselbe Transformationsmodus verwendet. Für jeden Block gibt es drei Arten von Farbtransformations-Elementen.

typedef struct {
  uint8 green_to_red;
  uint8 green_to_blue;
  uint8 red_to_blue;
} ColorTransformElement;

Die eigentliche Farbtransformation erfolgt durch die Definition eines Farbtransformationsdeltas. Das Farbtransformationsdelta hängt von ColorTransformElement ab, das für alle Pixel in einem bestimmten Block gleich ist. Das Delta wird während der Farbtransformation subtrahiert. Bei der inversen Farbtransformation werden diese Deltas dann einfach addiert.

Die Farbtransformationsfunktion ist so definiert:

void ColorTransform(uint8 red, uint8 blue, uint8 green,
                    ColorTransformElement *trans,
                    uint8 *new_red, uint8 *new_blue) {
  // Transformed values of red and blue components
  int tmp_red = red;
  int tmp_blue = blue;

  // Applying the transform is just subtracting the transform deltas
  tmp_red  -= ColorTransformDelta(trans->green_to_red,  green);
  tmp_blue -= ColorTransformDelta(trans->green_to_blue, green);
  tmp_blue -= ColorTransformDelta(trans->red_to_blue, red);

  *new_red = tmp_red & 0xff;
  *new_blue = tmp_blue & 0xff;
}

ColorTransformDelta wird mit einer vorzeichenbehafteten 8-Bit-Ganzzahl berechnet, die eine Festkommazahl mit 3,5 Stellen und einen vorzeichenbehafteten 8-Bit-RGB-Farbkanal (c) [-128..127] darstellt. Sie wird so definiert:

int8 ColorTransformDelta(int8 t, int8 c) {
  return (t * c) >> 5;
}

Vor dem Aufrufen von ColorTransformDelta() ist eine Konvertierung von der 8‑Bit-Darstellung ohne Vorzeichen (uint8) in die 8‑Bit-Darstellung mit Vorzeichen (int8) erforderlich. Der vorzeichenbehaftete Wert sollte als 8-Bit-Zweierkomplementzahl interpretiert werden. Das heißt, der uint8-Bereich [128..255] wird dem Bereich [–128..–1] des konvertierten int8-Werts zugeordnet.

Die Multiplikation muss mit höherer Genauigkeit (mindestens 16 Bit) erfolgen. Die Vorzeichenerweiterungseigenschaft der Shift-Operation spielt hier keine Rolle. Es werden nur die niedrigsten 8 Bits des Ergebnisses verwendet und in diesen Bits stimmen die Vorzeichenerweiterung und die vorzeichenlose Verschiebung überein.

Nun beschreiben wir den Inhalt der Farbtransformationsdaten, damit bei der Dekodierung die inverse Farbtransformation angewendet und die ursprünglichen Rot- und Blauwerte wiederhergestellt werden können. Die ersten drei Bits der Farbtransformationsdaten enthalten die Breite und Höhe des Bildblocks in Bit, genau wie die Predictor-Transformation:

int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;

Der verbleibende Teil der Farbtransformationsdaten enthält ColorTransformElement Instanzen, die jedem Block des Bildes entsprechen. Jedes ColorTransformElement 'cte' wird als Pixel in einem Bild mit niedrigerer Auflösung behandelt, dessen Alphakomponente 255, rote Komponente cte.red_to_blue, grüne Komponente cte.green_to_blue und blaue Komponente cte.green_to_red ist.

Während der Decodierung werden ColorTransformElement Instanzen der Blöcke decodiert und die inverse Farbtransformation wird auf die ARGB-Werte der Pixel angewendet. Wie bereits erwähnt, werden bei dieser inversen Farbtransformation nur ColorTransformElement-Werte zu den roten und blauen Kanälen hinzugefügt. Die Alpha- und Grünkanäle bleiben unverändert.

void InverseTransform(uint8 red, uint8 green, uint8 blue,
                      ColorTransformElement *trans,
                      uint8 *new_red, uint8 *new_blue) {
  // Transformed values of red and blue components
  int tmp_red = red;
  int tmp_blue = blue;

  // Applying the inverse transform is just adding the
  // color transform deltas
  tmp_red  += ColorTransformDelta(trans->green_to_red, green);
  tmp_blue += ColorTransformDelta(trans->green_to_blue, green);
  tmp_blue +=
      ColorTransformDelta(trans->red_to_blue, tmp_red & 0xff);

  *new_red = tmp_red & 0xff;
  *new_blue = tmp_blue & 0xff;
}

4.3 Subtract Green-Transformation

Bei der Transformation „Grün subtrahieren“ werden die Grünwerte von den Rot- und Blauwerten jedes Pixels subtrahiert. Wenn diese Transformation vorhanden ist, muss der Decoder den Grünwert sowohl zum Rot- als auch zum Blauwert hinzufügen. Mit dieser Transformation sind keine Daten verknüpft. Der Decoder wendet die inverse Transformation so an:

void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
  *red  = (*red  + green) & 0xff;
  *blue = (*blue + green) & 0xff;
}

Diese Transformation ist redundant, da sie mit der Farbtransformation modelliert werden kann. Da hier jedoch keine zusätzlichen Daten vorhanden sind, kann die Transformation „Grün subtrahieren“ mit weniger Bits codiert werden als eine vollständige Farbtransformation.

4.4 Transform für die Farbindexierung

Wenn es nicht viele eindeutige Pixelwerte gibt, kann es effizienter sein, ein Farbindex-Array zu erstellen und die Pixelwerte durch die Indexe des Arrays zu ersetzen. Die Farbindexierungstransformation ermöglicht dies. (Im Kontext von verlustfreiem WebP bezeichnen wir dies nicht als Palettentransformation, da es in der verlustfreien WebP-Codierung ein ähnliches, aber dynamischeres Konzept gibt: den Farbcache.)

Bei der Farbindexierungstransformation wird die Anzahl der eindeutigen ARGB-Werte im Bild geprüft. Wenn diese Zahl unter einem Schwellenwert (256) liegt, wird ein Array dieser ARGB-Werte erstellt, mit dem die Pixelwerte durch den entsprechenden Index ersetzt werden: Der grüne Kanal der Pixel wird durch den Index ersetzt, alle Alphawerte werden auf 255 und alle Rot- und Blauwerte auf 0 gesetzt.

Die Transformationsdaten enthalten die Größe der Farbtabelle und die Einträge in der Farbtabelle. Der Decoder liest die Daten der Farbindexierungstransformation so:

// 8-bit value for the color table size
int color_table_size = ReadBits(8) + 1;

Die Farbtabelle wird im Bildspeicherformat selbst gespeichert. Die Farbtabelle kann durch Lesen eines Bildes ohne RIFF-Header, Bildgröße und Transformationen abgerufen werden, wobei die Höhe 1 Pixel und die Breite color_table_size beträgt. Die Farbtabelle ist immer subtraktionscodiert, um die Bildentropie zu verringern. Die Deltas von Palettenfarben enthalten in der Regel viel weniger Entropie als die Farben selbst, was zu erheblichen Einsparungen bei kleineren Bildern führt. Beim Decodieren kann jede endgültige Farbe in der Farbtabelle durch Addition der vorherigen Farbkomponentenwerte für jede ARGB-Komponente separat und Speichern der 8 niedrigstwertigen Bits des Ergebnisses erhalten werden.

Bei der inversen Transformation für das Bild werden die Pixelwerte (die Indexe für die Farbtabelle sind) einfach durch die tatsächlichen Farbtabellenwerte ersetzt. Die Indexierung erfolgt auf Grundlage der grünen Komponente der ARGB-Farbe.

// Inverse transform
argb = color_table[GREEN(argb)];

Wenn der Index gleich oder größer als color_table_size ist, sollte der ARGB-Farbwert auf 0x00000000 (transparentes Schwarz) gesetzt werden.

Wenn die Farbtabelle klein ist (maximal 16 Farben), werden mehrere Pixel zu einem einzelnen Pixel zusammengefasst. Beim Pixel-Bundling werden mehrere (2, 4 oder 8) Pixel zu einem einzigen Pixel zusammengefasst, wodurch sich die Bildbreite entsprechend verringert. Durch das Bündeln von Pixeln kann die Entropiecodierung der gemeinsamen Verteilung benachbarter Pixel effizienter erfolgen. Außerdem bietet es einige Vorteile, die an die arithmetische Codierung erinnern. Es kann jedoch nur verwendet werden, wenn es höchstens 16 eindeutige Werte gibt.

color_table_size gibt an, wie viele Pixel kombiniert werden:

int width_bits;
if (color_table_size <= 2) {
  width_bits = 3;
} else if (color_table_size <= 4) {
  width_bits = 2;
} else if (color_table_size <= 16) {
  width_bits = 1;
} else {
  width_bits = 0;
}

width_bits hat den Wert 0, 1, 2 oder 3. Ein Wert von 0 gibt an, dass für das Bild kein Pixel-Bundling erfolgen soll. Ein Wert von 1 gibt an, dass zwei Pixel kombiniert werden und jedes Pixel einen Bereich von [0..15] hat. Ein Wert von 2 bedeutet, dass vier Pixel kombiniert werden und jedes Pixel einen Bereich von [0..3] hat. Ein Wert von 3 bedeutet, dass acht Pixel kombiniert werden und jedes Pixel einen Bereich von [0..1] hat, also einen binären Wert.

Die Werte werden so in die grüne Komponente gepackt:

• width_bits = 1: Für jeden x-Wert, für den x ≡ 0 (mod 2) gilt, wird ein grüner Wert bei x in den 4 niedrigstwertigen Bits des grünen Werts bei x / 2 und ein grüner Wert bei x + 1 in den 4 höchstwertigen Bits des grünen Werts bei x / 2 positioniert.
• width_bits = 2: Für jeden x-Wert, für den x ≡ 0 (mod 4) gilt, wird ein grüner Wert bei x in den zwei niedrigstwertigen Bits des grünen Werts bei x / 4 positioniert. Die grünen Werte bei x + 1 bis x + 3 werden in der Reihenfolge in den höherwertigen Bits des grünen Werts bei x / 4 positioniert.
• width_bits = 3: Für jeden x-Wert, für den x ≡ 0 (mod 8) gilt, wird ein grüner Wert bei x in das niedrigstwertige Bit des grünen Werts bei x / 8 eingefügt. Die grünen Werte bei x + 1 bis x + 7 werden in der Reihenfolge in die höherwertigen Bits des grünen Werts bei x / 8 eingefügt.

Nachdem diese Transformation gelesen wurde, wird image_width durch width_bits unterabgetastet. Dies wirkt sich auf die Größe nachfolgender Transformationen aus. Die neue Größe kann mit DIV_ROUND_UP berechnet werden, wie bereits definiert.

image_width = DIV_ROUND_UP(image_width, 1 << width_bits);

5 Bilddaten

Bilddaten sind ein Array von Pixelwerten in Scanzeilenreihenfolge.

5.1 Rollen von Bilddaten

Wir verwenden Bilddaten in fünf verschiedenen Rollen:

1. ARGB-Bild: Speichert die tatsächlichen Pixel des Bildes.
2. Entropiebild: Speichert die Meta-Präfixcodes (siehe „Decoding of Meta Prefix Codes“).
3. Predictor-Bild: Speichert die Metadaten für die Predictor-Transformation (siehe Predictor-Transformation).
4. Bild für Farbtransformation: Wird anhand von ColorTransformElement-Werten erstellt, die in „Farbtransformation“ für verschiedene Blöcke des Bildes definiert sind.
5. Farbindizierungsbild: Ein Array mit der Größe von color_table_size (bis zu 256 ARGB-Werte), in dem die Metadaten für die Farbindizierungstransformation gespeichert sind (siehe „Farbindizierungstransformation“).

5.2 Codierung von Bilddaten

Die Codierung von Bilddaten ist unabhängig von ihrer Rolle.

Das Bild wird zuerst in eine Reihe von Blöcken mit fester Größe unterteilt (in der Regel 16 × 16). Jeder dieser Blöcke wird mit eigenen Entropie-Codes modelliert. Außerdem können mehrere Blöcke dieselben Entropiecodes verwenden.

Begründung:Das Speichern eines Entropiecodes verursacht Kosten. Diese Kosten können minimiert werden, wenn statistisch ähnliche Blöcke einen Entropiecode gemeinsam nutzen, sodass dieser Code nur einmal gespeichert wird. Ein Encoder kann beispielsweise ähnliche Blöcke finden, indem er sie anhand ihrer statistischen Eigenschaften clustert oder indem er wiederholt ein zufällig ausgewähltes Clusterpaar zusammenführt, wenn dadurch die Gesamtzahl der Bits reduziert wird, die zum Codieren des Bildes erforderlich sind.

Jedes Pixel wird mit einer der drei möglichen Methoden codiert:

1. Präfixcodierte Literale: Jeder Kanal (Grün, Rot, Blau und Alpha) wird unabhängig entropiecodiert.
2. LZ77-Rückwärtsreferenz: Eine Sequenz von Pixeln wird von einer anderen Stelle im Bild kopiert.
3. Farb-Cache-Code: Verwendung eines kurzen multiplikativen Hash-Codes (Farb-Cache-Index) einer kürzlich gesehenen Farbe.

In den folgenden Unterabschnitten werden die einzelnen Schritte detailliert beschrieben.

5.2.1 Präfixcodierte Literale

Das Pixel wird als präfixcodierte Werte für Grün, Rot, Blau und Alpha (in dieser Reihenfolge) gespeichert. Weitere Informationen finden Sie im Abschnitt 6.2.3.

5.2.2 LZ77-Rückwärtsreferenz

Rückwärtsreferenzen sind Tupel aus Länge und Distanzcode:

• „Länge“ gibt an, wie viele Pixel in Scanline-Reihenfolge kopiert werden sollen.
• Der Distanzcode ist eine Zahl, die die Position eines zuvor gesehenen Pixels angibt, von dem die Pixel kopiert werden sollen. Die genaue Zuordnung wird unten beschrieben.

Die Längen- und Distanzwerte werden mit LZ77-Präfixcodierung gespeichert.

Bei der LZ77-Präfixcodierung werden große Ganzzahlwerte in zwei Teile unterteilt: den Präfixcode und die zusätzlichen Bits. Der Präfixcode wird mit einem Entropiecode gespeichert, während die zusätzlichen Bits unverändert (ohne Entropiecode) gespeichert werden.

Begründung: Durch diesen Ansatz wird der Speicherbedarf für den Entropiecode reduziert. Außerdem sind große Werte in der Regel selten, sodass zusätzliche Bits nur für sehr wenige Werte im Bild verwendet würden. Insgesamt führt dieser Ansatz zu einer besseren Komprimierung.

In der folgenden Tabelle sind die Präfixcodes und zusätzlichen Bits aufgeführt, die zum Speichern verschiedener Wertebereiche verwendet werden.

Der Pseudocode zum Abrufen eines Längen- oder Distanzwerts aus dem Präfixcode sieht so aus:

if (prefix_code < 4) {
  return prefix_code + 1;
}
int extra_bits = (prefix_code - 2) >> 1;
int offset = (2 + (prefix_code & 1)) << extra_bits;
return offset + ReadBits(extra_bits) + 1;

Entfernungszuordnung

Wie bereits erwähnt, ist ein Distanzcode eine Zahl, die die Position eines zuvor gesehenen Pixels angibt, von dem die Pixel kopiert werden sollen. In diesem Unterabschnitt wird die Zuordnung zwischen einem Distanzcode und der Position eines vorherigen Pixels definiert.

Distanzcodes, die größer als 120 sind, geben den Pixelabstand in Scanline-Reihenfolge an, der um 120 versetzt ist.

Die kleinsten Distanzcodes [1..120] sind speziell und für eine enge Nachbarschaft des aktuellen Pixels reserviert. Diese Umgebung besteht aus 120 Pixeln:

• Pixel, die 1 bis 7 Zeilen über dem aktuellen Pixel liegen und bis zu 8 Spalten links oder bis zu 7 Spalten rechts vom aktuellen Pixel entfernt sind. [Anzahl solcher Pixel insgesamt = 7 * (8 + 1 + 7) = 112].
• Pixel, die sich in derselben Zeile wie das aktuelle Pixel befinden und bis zu 8 Spalten links davon liegen. [8 such pixels].

Die Zuordnung zwischen dem Distanzcode distance_code und dem benachbarten Pixel-Offset (xi, yi) ist wie folgt:

(0, 1),  (1, 0),  (1, 1),  (-1, 1), (0, 2),  (2, 0),  (1, 2),
(-1, 2), (2, 1),  (-2, 1), (2, 2),  (-2, 2), (0, 3),  (3, 0),
(1, 3),  (-1, 3), (3, 1),  (-3, 1), (2, 3),  (-2, 3), (3, 2),
(-3, 2), (0, 4),  (4, 0),  (1, 4),  (-1, 4), (4, 1),  (-4, 1),
(3, 3),  (-3, 3), (2, 4),  (-2, 4), (4, 2),  (-4, 2), (0, 5),
(3, 4),  (-3, 4), (4, 3),  (-4, 3), (5, 0),  (1, 5),  (-1, 5),
(5, 1),  (-5, 1), (2, 5),  (-2, 5), (5, 2),  (-5, 2), (4, 4),
(-4, 4), (3, 5),  (-3, 5), (5, 3),  (-5, 3), (0, 6),  (6, 0),
(1, 6),  (-1, 6), (6, 1),  (-6, 1), (2, 6),  (-2, 6), (6, 2),
(-6, 2), (4, 5),  (-4, 5), (5, 4),  (-5, 4), (3, 6),  (-3, 6),
(6, 3),  (-6, 3), (0, 7),  (7, 0),  (1, 7),  (-1, 7), (5, 5),
(-5, 5), (7, 1),  (-7, 1), (4, 6),  (-4, 6), (6, 4),  (-6, 4),
(2, 7),  (-2, 7), (7, 2),  (-7, 2), (3, 7),  (-3, 7), (7, 3),
(-7, 3), (5, 6),  (-5, 6), (6, 5),  (-6, 5), (8, 0),  (4, 7),
(-4, 7), (7, 4),  (-7, 4), (8, 1),  (8, 2),  (6, 6),  (-6, 6),
(8, 3),  (5, 7),  (-5, 7), (7, 5),  (-7, 5), (8, 4),  (6, 7),
(-6, 7), (7, 6),  (-7, 6), (8, 5),  (7, 7),  (-7, 7), (8, 6),
(8, 7)

Der Distanzcode 1 gibt beispielsweise einen Offset von (0, 1) für das benachbarte Pixel an, d. h. das Pixel über dem aktuellen Pixel (0 Pixel Unterschied in X-Richtung und 1 Pixel Unterschied in Y-Richtung). Entsprechend gibt der Distanzcode 3 das Pixel oben links an.

Der Decoder kann einen Distanzcode distance_code in eine Distanz dist in Scanline-Reihenfolge umwandeln:

(xi, yi) = distance_map[distance_code - 1]
dist = xi + yi * image_width
if (dist < 1) {
  dist = 1
}

Dabei ist distance_map die oben genannte Zuordnung und image_width die Breite des Bildes in Pixeln.

5.2.3 Farb-Cache-Codierung

Im Farbcache wird eine Reihe von Farben gespeichert, die zuletzt im Bild verwendet wurden.

Begründung:Auf diese Weise kann auf die zuletzt verwendeten Farben manchmal effizienter verwiesen werden, als wenn sie mit den beiden anderen Methoden (beschrieben in 5.2.1 und 5.2.2) ausgegeben werden.

Farb-Cache-Codes werden so gespeichert: Zuerst gibt es einen 1-Bit-Wert, der angibt, ob der Farbcache verwendet wird. Wenn dieses Bit 0 ist, sind keine Farbcache-Codes vorhanden und sie werden nicht im Präfixcode übertragen, der die grünen Symbole und die Längenpräfixcodes decodiert. Wenn dieses Bit jedoch 1 ist, wird als Nächstes die Größe des Farbzwischenspeichers gelesen:

int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;

color_cache_code_bits definiert die Größe des Farb-Cache (1 << color_cache_code_bits). Der Bereich der zulässigen Werte für color_cache_code_bits ist [1..11]. Konforme Decoder müssen für andere Werte einen beschädigten Bitstream angeben.

Ein Farb-Cache ist ein Array der Größe color_cache_size. In jedem Eintrag wird eine ARGB-Farbe gespeichert. Farben werden durch Indexierung nach (0x1e35a7bd * color) >> (32 - color_cache_code_bits) abgerufen. In einem Farbcache wird nur eine Suche durchgeführt. Es gibt keine Konfliktlösung.

Zu Beginn der Decodierung oder Codierung eines Bildes werden alle Einträge in allen Farbcache-Werten auf null gesetzt. Der Farbcache-Code wird bei der Dekodierung in diese Farbe umgewandelt. Der Status des Farb-Cache wird beibehalten, indem jedes Pixel, unabhängig davon, ob es durch Rückwärtsreferenzierung oder als Literal erzeugt wurde, in der Reihenfolge, in der es im Stream erscheint, in den Cache eingefügt wird.

6 Entropiecode

6.1 Übersicht

Die meisten Daten werden mit einem kanonischen Präfixcode codiert. Daher werden die Codes durch Senden der Präfixcodelängen anstelle der tatsächlichen Präfixcodes übertragen.

Insbesondere wird das räumlich variable Präfixcodierungsverfahren verwendet. Mit anderen Worten: Für verschiedene Blöcke des Bildes können potenziell unterschiedliche Entropiecodes verwendet werden.

Begründung: Verschiedene Bereiche des Bildes können unterschiedliche Merkmale aufweisen. Die Verwendung verschiedener Entropiecodes bietet also mehr Flexibilität und potenziell eine bessere Komprimierung.

6.2 Details

Die codierten Bilddaten bestehen aus mehreren Teilen:

1. Präfixcodes decodieren und erstellen
2. Meta-Präfixcodes.
3. Entropiecodierte Bilddaten.

Für jedes Pixel (x, y) gibt es eine Reihe von fünf Präfixcodes. Diese Codes sind (in Bitstream-Reihenfolge):

• Präfixcode 1: Wird für den grünen Kanal, die Länge der Rückwärtsreferenz und den Farbcache verwendet.
• Präfixcode 2, 3 und 4: Wird für den Rot-, Blau- und Alphakanal verwendet.
• Präfixcode 5: Wird für die Distanz zur Rückwärtsreferenz verwendet.

Im Folgenden bezeichnen wir diese Gruppe als Präfixcodegruppe.

6.2.1 Decodieren und Erstellen der Präfixcodes

In diesem Abschnitt wird beschrieben, wie Sie die Präfixcodelängen aus dem Bitstream lesen.

Die Präfixcodelängen können auf zwei Arten codiert werden. Die verwendete Methode wird durch einen 1-Bit-Wert angegeben.

• Wenn dieses Bit 1 ist, handelt es sich um einen Code mit einfacher Codelänge.
• Wenn dieses Bit 0 ist, handelt es sich um einen Code mit normaler Codelänge.

In beiden Fällen kann es ungenutzte Codelängen geben, die weiterhin Teil des Streams sind. Das ist zwar möglicherweise ineffizient, aber im Format zulässig. Der beschriebene Baum muss ein vollständiger binärer Baum sein. Ein einzelner Blattknoten wird als vollständiger binärer Baum betrachtet und kann entweder mit dem einfachen oder dem normalen Codelängencode codiert werden. Wenn Sie einen einzelnen Blattknoten mit dem normalen Codelängen-Code codieren, sind alle Codelängen bis auf eine null. Der Wert des einzelnen Blattknotens wird mit der Länge 1 gekennzeichnet, auch wenn bei Verwendung dieses einzelnen Blattknotenbaums keine Bits verbraucht werden.

Einfacher Code für die Codelänge

Diese Variante wird im Sonderfall verwendet, wenn nur 1 oder 2 Präfixsymbole im Bereich [0..255] mit der Codelänge 1 vorhanden sind. Alle anderen Präfixcodelängen sind implizit null.

Das erste Bit gibt die Anzahl der Symbole an:

int num_symbols = ReadBits(1) + 1;

Im Folgenden finden Sie die Symbolwerte.

Das erste Symbol wird je nach Wert von is_first_8bits mit 1 oder 8 Bit codiert. Der Bereich ist [0..1] bzw. [0..255]. Das zweite Symbol, falls vorhanden, wird immer im Bereich [0..255] angenommen und mit 8 Bits codiert.

int is_first_8bits = ReadBits(1);
symbol0 = ReadBits(1 + 7 * is_first_8bits);
code_lengths[symbol0] = 1;
if (num_symbols == 2) {
  symbol1 = ReadBits(8);
  code_lengths[symbol1] = 1;
}

Die beiden Symbole sollten sich unterscheiden. Doppelte Symbole sind zulässig, aber ineffizient.

Hinweis:Ein weiterer Sonderfall ist, wenn alle Präfixcodelängen Nullen sind (ein leerer Präfixcode). Ein Präfixcode für die Entfernung kann beispielsweise leer sein, wenn keine Rückwärtsreferenzen vorhanden sind. Entsprechend können Präfixcodes für Alpha, Rot und Blau leer sein, wenn alle Pixel innerhalb desselben Meta-Präfixcodes mit dem Farbcache erzeugt werden. Dieser Fall erfordert jedoch keine besondere Behandlung, da leere Präfixcodes als Codes mit einem einzelnen Symbol 0 codiert werden können.

Normal Code Length Code

Die Codelängen des Präfixcodes passen in 8 Bits und werden so gelesen: Zuerst gibt num_code_lengths die Anzahl der Codelängen an.

int num_code_lengths = 4 + ReadBits(4);

Die Codelängen selbst werden mit Präfixcodes codiert. Die Codelängen auf niedrigerer Ebene, code_length_code_lengths, müssen zuerst gelesen werden. Die restlichen code_length_code_lengths (entsprechend der Reihenfolge in kCodeLengthCodeOrder) sind Nullen.

int kCodeLengthCodes = 19;
int kCodeLengthCodeOrder[kCodeLengthCodes] = {
  17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
};
int code_length_code_lengths[kCodeLengthCodes] = { 0 };  // All zeros
for (i = 0; i < num_code_lengths; ++i) {
  code_length_code_lengths[kCodeLengthCodeOrder[i]] = ReadBits(3);
}

Als Nächstes wird, falls ReadBits(1) == 0, die maximale Anzahl der verschiedenen gelesenen Symbole (max_symbol) für jeden Symboltyp (A, R, G, B und Entfernung) auf die Alphabetgröße festgelegt:

• G-Kanal: 256 + 24 + color_cache_size
• Andere Literale (A, R und B): 256
• Entfernungscode: 40

Andernfalls wird sie so definiert:

int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);

Wenn max_symbol größer als die Größe des Alphabets für den Symboltyp ist, ist der Bitstream ungültig.

Anschließend wird aus code_length_code_lengths eine Präfixtabelle erstellt, mit der bis zu max_symbol Code-Längen gelesen werden können.

• „Code [0..15]“ gibt die tatsächlichen Codelängen an.
  • Der Wert 0 bedeutet, dass keine Symbole codiert wurden.
  • Werte [1..15] geben die Bitlänge des jeweiligen Codes an.
• Mit Code 16 wird der vorherige Wert ungleich null [3..6] Mal wiederholt, d. h. 3 + ReadBits(2) Mal. Wenn Code 16 verwendet wird, bevor ein Wert ungleich null ausgegeben wurde, wird der Wert 8 wiederholt.
• Bei Code 17 wird eine Reihe von Nullen der Länge [3..10] ausgegeben, d. h. 3 + ReadBits(3) Mal.
• Bei Code 18 wird eine Reihe von Nullen der Länge [11..138] ausgegeben, d. h. 11 + ReadBits(7) Mal.

Nachdem die Codelängen gelesen wurden, wird für jeden Symboltyp (A, R, G, B und Distanz) ein Präfixcode mit den jeweiligen Alphabetgrößen gebildet.

Der Code für die normale Codelänge muss einen vollständigen Entscheidungsbaum codieren. Das bedeutet, dass die Summe von 2 ^ (-length) für alle Codes ungleich null genau eins sein muss. Es gibt jedoch eine Ausnahme von dieser Regel: den Baum mit einem einzelnen Blattknoten. Hier wird der Wert des Blattknotens mit 1 und andere Werte mit 0 gekennzeichnet.

6.2.2 Decodierung von Meta-Präfixcodes

Wie bereits erwähnt, können für verschiedene Blöcke des Bildes unterschiedliche Präfixcodes verwendet werden. Meta-Präfixcodes sind Indexe, die angeben, welche Präfixcodes in den verschiedenen Teilen des Bildes verwendet werden sollen.

Meta-Präfixcodes dürfen nur verwendet werden, wenn das Bild in der Rolle eines ARGB-Bildes verwendet wird.

Es gibt zwei Möglichkeiten für die Meta-Präfixcodes, die durch einen 1-Bit-Wert angegeben werden:

• Wenn dieses Bit null ist, wird im gesamten Bild nur ein Meta-Präfixcode verwendet. Es werden keine weiteren Daten gespeichert.
• Wenn dieses Bit „1“ ist, verwendet das Bild mehrere Meta-Präfixcodes. Diese Meta-Präfixcodes werden als Entropiebild (siehe unten) gespeichert.

Die roten und grünen Komponenten eines Pixels definieren einen 16-Bit-Meta-Präfixcode, der in einem bestimmten Block des ARGB-Bildes verwendet wird.

Entropiebild

Das Entropiebild definiert, welche Präfixcodes in den verschiedenen Teilen des Bildes verwendet werden.

Die ersten 3 Bits enthalten den Wert prefix_bits. Die Dimensionen des Entropiebilds werden aus prefix_bits abgeleitet:

int prefix_bits = ReadBits(3) + 2;
int prefix_image_width =
    DIV_ROUND_UP(image_width, 1 << prefix_bits);
int prefix_image_height =
    DIV_ROUND_UP(image_height, 1 << prefix_bits);

Dabei ist DIV_ROUND_UP wie zuvor definiert.

Die nächsten Bits enthalten ein Entropiebild mit der Breite prefix_image_width und der Höhe prefix_image_height.

Interpretation von Meta-Präfixcodes

Die Anzahl der Präfixcodegruppen im ARGB-Bild kann ermittelt werden, indem der größte Meta-Präfixcode aus dem Entropiebild gesucht wird:

int num_prefix_groups = max(entropy image) + 1;

Dabei gibt max(entropy image) den größten Präfixcode an, der im Entropiebild gespeichert ist.

Da jede Präfixcodegruppe fünf Präfixcodes enthält, ergibt sich die Gesamtzahl der Präfixcodes aus:

int num_prefix_codes = 5 * num_prefix_groups;

Wenn wir einen Pixel (x, y) im ARGB-Bild haben, können wir die entsprechenden Präfixcodes so abrufen:

int position =
    (y >> prefix_bits) * prefix_image_width + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[position] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];

Dabei haben wir die Existenz der PrefixCodeGroup-Struktur angenommen, die eine Reihe von fünf Präfixcodes darstellt. prefix_code_groups ist ein Array von PrefixCodeGroup (mit der Größe num_prefix_groups).

Der Decoder verwendet dann die Präfixcodegruppe prefix_group, um das Pixel (x, y) zu decodieren, wie in „Entropiecodierte Bilddaten decodieren“ beschrieben.

6.2.3 Entropiecodierte Bilddaten decodieren

Für die aktuelle Position (x, y) im Bild identifiziert der Decoder zuerst die entsprechende Präfixcodegruppe (wie im letzten Abschnitt beschrieben). Anhand der Präfix-Codegruppe wird das Pixel so gelesen und decodiert:

Lesen Sie als Nächstes das Symbol S aus dem Bitstream mit dem Präfixcode 1. S ist eine beliebige Ganzzahl im Bereich von 0 bis (256 + 24 + color_cache_size- 1).

Die Interpretation von S hängt von seinem Wert ab:

1. Wenn S < 256
   1. Verwenden Sie „S“ als grüne Komponente.
   2. Lesen Sie „Rot“ aus dem Bitstream mit dem Präfixcode 2.
   3. Lesen Sie Blau aus dem Bitstream mit dem Präfixcode 3.
   4. Lesen Sie den Alphawert aus dem Bitstream mit dem Präfixcode 4.
2. Wenn S >= 256 und S < 256 + 24
   1. Verwenden Sie S – 256 als Längenpräfixcode.
   2. Zusätzliche Bits für die Länge aus dem Bitstream lesen.
   3. Bestimmen Sie die Länge der Rückwärtsreferenz L aus dem Längenpräfixcode und den gelesenen zusätzlichen Bits.
   4. Lesen Sie den Distanzpräfixcode aus dem Bitstream mit dem Präfixcode 5.
   5. Zusätzliche Bits für die Entfernung aus dem Bitstream lesen.
   6. Bestimme den Backward-Reference-Abstand D aus dem Distance-Präfixcode und den gelesenen zusätzlichen Bits.
   7. Kopiere L Pixel (in Scanline-Reihenfolge) aus der Pixelsequenz, die an der aktuellen Position minus D Pixel beginnt.
3. Wenn S >= 256 + 24
   1. Verwenden Sie S – (256 + 24) als Index für den Farbcache.
   2. Ruft die ARGB-Farbe aus dem Farbcache an diesem Index ab.

7 Gesamtstruktur des Formats

Nachfolgend finden Sie eine Beschreibung des Formats in der angereicherten Backus-Naur-Form (Augmented Backus-Naur Form, ABNF) RFC 5234 RFC 7405. Sie enthält nicht alle Details. Das EOI (End-of-Image) wird nur implizit in die Anzahl der Pixel (image_width * image_height) codiert.

*element bedeutet, dass element nicht oder mehrere Male wiederholt werden kann. 5element bedeutet, dass element genau fünfmal wiederholt wird. %b steht für einen binären Wert.

7.1 Grundstruktur

format        = RIFF-header image-header image-stream
RIFF-header   = %s"RIFF" 4OCTET %s"WEBPVP8L" 4OCTET
image-header  = %x2F image-size alpha-is-used version
image-size    = 14BIT 14BIT ; width - 1, height - 1
alpha-is-used = 1BIT
version       = 3BIT ; 0
image-stream  = optional-transform spatially-coded-image

7.2 Struktur von Transformationen

optional-transform   =  (%b1 transform optional-transform) / %b0
transform            =  predictor-tx / color-tx / subtract-green-tx
transform            =/ color-indexing-tx

predictor-tx         =  %b00 predictor-image
predictor-image      =  3BIT ; sub-pixel code
                        entropy-coded-image

color-tx             =  %b01 color-image
color-image          =  3BIT ; sub-pixel code
                        entropy-coded-image

subtract-green-tx    =  %b10

color-indexing-tx    =  %b11 color-indexing-image
color-indexing-image =  8BIT ; color count
                        entropy-coded-image

7.3 Struktur der Bilddaten

spatially-coded-image =  color-cache-info meta-prefix data
entropy-coded-image   =  color-cache-info data

color-cache-info      =  %b0
color-cache-info      =/ (%b1 4BIT) ; 1 followed by color cache size

meta-prefix           =  %b0 / (%b1 entropy-image)

data                  =  prefix-codes lz77-coded-image
entropy-image         =  3BIT ; subsample value
                         entropy-coded-image

prefix-codes          =  prefix-code-group *prefix-codes
prefix-code-group     =
    5prefix-code ; See "Interpretation of Meta Prefix Codes" to
                 ; understand what each of these five prefix
                 ; codes are for.

prefix-code           =  simple-prefix-code / normal-prefix-code
simple-prefix-code    =  ; see "Simple Code Length Code" for details
normal-prefix-code    =  ; see "Normal Code Length Code" for details

lz77-coded-image      =
    *((argb-pixel / lz77-copy / color-cache-code) lz77-coded-image)

Hier ist ein Beispiel für eine mögliche Sequenz:

RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image