Spezifikation für verlustfreien WebP-Datenstream

Mit Sammlungen den Überblick behalten Sie können Inhalte basierend auf Ihren Einstellungen speichern und kategorisieren.

Jyrki Alakuijala, Ph.D., Google Inc., 19.06.2012

Absätze mit der Kennzeichnung [AMENDED] wurden am 16.09.2014 geändert.

Absätze mit der Kennzeichnung [AMENDED2] wurden am 13.05.2022 geändert.

Absätze mit der Kennzeichnung [AMENDED3] wurden am 21.11.2022 geändert.

Zusammenfassung

WebP Lossless ist ein Bildformat für die verlustfreie Komprimierung von ARGB-Bildern. Im verlustfreien Format werden die Pixelwerte exakt gespeichert und wiederhergestellt, einschließlich der Farbwerte für Pixel, deren Alphawert 0 ist. Das Format verwendet rekursive Bilder, die rekursiv in das Format selbst eingebettet sind, um statistische Daten zu den Bildern zu speichern, z. B. die verwendeten Entropiecodes, räumlichen Predictoren, die Umwandlung von Farbräumen und die Farbtabelle. Für die Komprimierung der Bulk-Daten werden LZ77, Präfixcodierung und ein Farb-Cache verwendet. Die Decodierungsgeschwindigkeiten, die schneller sind als PNG, wurden demonstriert. Außerdem ist die Komprimierung mit 25% dichter komprimiert als mit dem heutigen PNG-Format möglich.

1 Einleitung

In diesem Dokument wird die komprimierte Datendarstellung eines verlustfreien WebP-Images beschrieben. Er ist als detaillierte Referenz für die verlustfreie Encoder- und Decoder-Implementierung des WebP gedacht.

In diesem Dokument wird ausführlich die Programmiersprache C verwendet, um den Bitstream zu beschreiben. Außerdem wird angenommen, dass eine Funktion zum Lesen von Bits vorhanden ist: ReadBits(n). Die Bytes werden in der natürlichen Reihenfolge des Streams gelesen, in dem sie enthalten sind, und die Bits jedes Bytes werden in der Reihenfolge mit der geringsten Signifikanz 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 ursprünglichen Daten. Die Aussage

b = ReadBits(2);

entspricht den folgenden beiden Aussagen:

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

Wir gehen davon aus, dass jede Farbkomponente (z.B. Alpha, Rot, Blau und Grün) mit einem 8-Bit-Byte dargestellt wird. Wir definieren den entsprechenden Typ als uint8. Ein vollständiges ARGB-Pixel wird durch einen Typ namens uint32 dargestellt, eine vorzeichenlose Ganzzahl, die aus 32 Bit besteht. Im Code, der das Verhalten der Transformationen zeigt, wird der Alphawert in den Bits 31..24, dem roten in den Bits 23..16, dem grünen in den Bits 15..8 und dem blauen in den Bits 7.0 codiert. Implementierungen des Formats können jedoch intern in einer anderen Darstellung verwendet werden.

Im Wesentlichen enthält ein verlustfreies WebP-Bild Header-, Transformationsinformationen und tatsächliche Bilddaten. Header enthalten die Breite und Höhe des Bildes. Ein verlustfreies WebP-Bild kann vier verschiedene Transformationstypen durchlaufen, bevor es eine Entropie codiert. Die Transformationsinformationen im Bitstream enthalten die Daten, die zum Anwenden der jeweiligen umgekehrten 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 Array mit Hash-Adresse, in dem kürzlich verwendete Farben gespeichert werden, um sie mit kürzeren Codes zurückzurufen.
Bild: Farbindexierung
Eindimensionales Bild mit Farben, die mit einer kleinen Ganzzahl (bis zu 256 in WebP-verlustfrei) indexiert werden können.
Bild zur Farbtransformation
Ein zweidimensionales Bild mit Auflösung, das Daten über Korrelationen von Farbkomponenten enthält.
Distanzzuordnung
Ändert LZ77-Abstände, um die kleinsten Werte für Pixel in 2D-Näherung zu erhalten.
Entropiebild
Ein zweidimensionales Bild mit Auflösung, das angibt, welche Entropiecodierung in einem jeweiligen Quadrat im Bild verwendet werden soll, d.h. jedes Pixel ist ein Meta-Präfixcode.
Präfixcode
Klassische Methode zur Entropiecodierung, bei der eine kleinere Anzahl von Bits für häufigere Codes verwendet wird.
Lz 77
Wörterbuchbasierter Komprimierungsalgorithmus für Schiebefenster, der Symbole ausgibt oder als Sequenzen vergangener Symbole beschreibt.
Metapräfix
Eine kleine Ganzzahl (bis zu 16 Bit), die ein Element in der Metapräfixtabelle indexiert.
Predictor-Bild
Ein zweidimensionales Unterauflösungsbild, das angibt, welcher räumliche Predictor für ein bestimmtes Quadrat im Bild verwendet wird.
Präfixcodierung
Eine Möglichkeit, größere Ganzzahlen zu entkoppeln, die einige Bits der Ganzzahl mithilfe eines Entropiecodes codieren und die verbleibenden Bits rod codieren. Dadurch können die Beschreibungen der Entropiecodes auch dann klein bleiben, wenn die Zahl der Symbole groß ist.
Scan-Zeilenauftrag
Eine Verarbeitungsreihenfolge der Pixel von links nach rechts, von oben nach unten und beginnend vom linken Pixel nach rechts. Fahren Sie nach dem Ausfüllen einer Zeile in der linken Spalte der nächsten Zeile fort.

3 RIFF – Header

Der Anfang des Headers enthält den RIFF-Container. Diese besteht aus den folgenden 21 Byte:

  1. String „RIFF“
  2. Ein kleiner 32-Bit-Blockwert der Blocklänge, die gesamte Größe des Blocks, 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“ (Tag-Block für verlustfreie codierte Bilddaten).
  5. Ein kleiner Endian-32-Bit-Wert der Anzahl von Byte im verlustfreien Stream.
  6. 1-Byte-Signatur 0x2f.

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

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

Die 14-Bit-Dynamik für die Bildgröße begrenzt die maximale Größe eines verlustfreien WebP-Bildes auf 16.384 × 16.384 Pixel.

Das Bit alpha_is_used ist nur ein Hinweis und sollte die Decodierung nicht beeinflussen. Er sollte auf 0 gesetzt werden, wenn alle Alphawerte im Bild 255 sind, und andernfalls auf 1.

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. [GEÄNDERT]

int version_number = ReadBits(3);

4 Transformationen

Transformationen sind reversible Manipulationen der Bilddaten, die die verbleibende symbolische Entropie durch Modellierung von räumlichen und Farbkorrelationen reduzieren können. Transformationen können die endgültige Komprimierung stärker einschränken.

Ein Bild kann vier Arten von Transformationen durchlaufen. Ein 1-Bit gibt die Präsenz einer Transformation an. Jede Transformation darf nur einmal verwendet werden. Die Transformationen werden nur für das ARGB-Bild auf Hauptebene verwendet: Die Bilder mit Unterauflösung haben keine Transformationen, nicht einmal das 0-Bit, das das Ende der Transformationen angibt.

Normalerweise würde ein Encoder diese Transformationen verwenden, um die Shannon-Entropie im Restbild zu reduzieren. Außerdem können die Transformationsdaten auf der Grundlage der Entropieminimierung festgelegt werden.

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

// Decode actual image data (Section 4).

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. Transformationsdaten enthalten die Informationen, die zum Anwenden der umgekehrten Transformation erforderlich sind, und sind vom Transformationstyp abhängig. Als Nächstes beschreiben wir die Transformationsdaten für verschiedene Typen.

4.1 Predictor-Transformation

Die Predictor-Transformation kann verwendet werden, um die Entropie zu reduzieren, indem die Tatsache genutzt wird, dass benachbarte Pixel oft korreliert werden. In der Predictor-Transformation wird der aktuelle Pixelwert aus den bereits decodierten Pixeln (in einer Scanlinienreihenfolge) vorhergesagt und nur der Restwert (tatsächlich – vorhergesagt) wird codiert. Der Vorhersagemodus bestimmt die zu verwendende Art von Vorhersage. Wir teilen das Bild in Quadrate und für alle Pixel in einem Quadrat wird derselbe Vorhersagemodus verwendet.

Die ersten 3 Bit der Vorhersagedaten definieren die Breite und Höhe des Blocks in Bit. Die Anzahl der Blockspalten, block_xsize, wird bei der zweidimensionalen Indexierung verwendet.

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 block_xsize = DIV_ROUND_UP(image_width, 1 << size_bits);

Die Transformationsdaten enthalten den Vorhersagemodus für jeden Block des Bildes. Alle block_width * block_height Pixel eines Blocks verwenden denselben Vorhersagemodus. Die Vorhersagemodi werden als Pixel eines Bildes behandelt und mit denselben Verfahren codiert, die in Kapitel 5 beschrieben werden.

Für Pixel x, y kann die entsprechende Adresse des Filterblocks so berechnet werden:

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

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

Wir wählen die benachbarten Pixel (TL, T, TR und L) des aktuellen Pixels (P) so aus:

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

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

Angesichts der obigen Nachbarpixel werden die verschiedenen Vorhersagemodi so definiert:

Modus Vorhergesagter Wert jedes Kanals des aktuellen Pixels
0 0xff000000 (darf eine schwarze Farbe in ARGB)
1 L
2 D
3 Türkischen Lira (TRY)
4 TL
5 Durchschnitt2(Durchschnitt2(L; TR); T)
6 Average2(L, TL)
7 Durchschnitt2(L, T)
8 Durchschnitt2(TL; T)
9 Durchschnitt2(T, TR)
10 Durchschnitt2(Durchschnitt2(L; TL); Durchschnitt2(T; TR))
11 Auswählen(L, T, TL)
12 ClampAddSubtractFull(L, T, TL)
13 ClampAddSubtractHalf(Average2(L, T), TL)

Average2 ist für jede ARGB-Komponente wie folgt definiert:

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

Der Select-Predictor 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) {     // \[AMENDED\]
    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 Rahmenpixel gibt es spezielle Verarbeitungsregeln. Wenn es eine Vorhersagetransformation gibt, unabhängig vom Modus [0...13] für diese Pixel, beträgt der vorhergesagte Wert für das Pixel ganz links im Bild 0xff000000, L-Pixel für alle Pixel in der oberen Zeile und T-Pixel für alle Pixel in der Spalte ganz links.

[AMENDED2] Die Behandlung der TR-Pixel für die Pixel in der Spalte ganz rechts ist eine Ausnahme. Die Pixel in der Spalte ganz rechts werden durch Verwendung der Modi [0...13] genau wie Pixel, die sich nicht am Rand befinden, vorhergesagt. Stattdessen wird das Pixel ganz links in derselben Zeile wie das aktuelle Pixel als TR-Pixel verwendet.

4.2 Farbtransformation

[Geändert]2

Das Ziel der Farbtransformation besteht darin, die R-, G- und B-Werte der einzelnen Pixel zu dekorieren. Die Farbtransformation behält den grünen Wert (G) bei, wie er ist, transformiert Rot (R) auf Grün und blau (B) auf Grün und dann auf Rot.

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

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

Die tatsächliche Farbtransformation erfolgt durch Definieren eines Farbtransformationsdeltas. Das Deltatransformationssignal hängt vom ColorTransformElement ab, der für alle Pixel in einem bestimmten Block gleich ist. Das Delta wird während der Farbtransformation subtrahiert. Die umgekehrte Farbtransformation wird dann einfach zu diesen Deltas hinzugefügt.

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 mithilfe einer signierten 8-Bit-Ganzzahl, die eine Zahl mit 3,5 festen Punkten ist, und einem signierten 8-Bit-RGB-Farbkanal (c) [-128..127] berechnet und so definiert:

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

Eine Konvertierung von der nicht signierten 8-Bit-Darstellung (uint8) in die 8-Bit-Signatur (int8) ist vor dem Aufruf von ColorTransformDelta() erforderlich. Sie sollte mit dem 8-Bit-Zweierkomplement durchgeführt werden (d. h., der Uint8-Bereich [128..255] wird dem Bereich [-128..-1] seines konvertierten int8-Werts zugeordnet).

Die Multiplikation sollte mit mehr Genauigkeit (mit mindestens 16-Bit-Dynamik) erfolgen. Die Eigenschaft der Vorzeichenerweiterung des Verschiebungsvorgangs ist hier nicht relevant: Es werden nur die niedrigsten 8 Bit aus dem Ergebnis verwendet und die Verschiebung der Vorzeichenerweiterung und die Verschiebung der vorzeichenbehafteten Zeichen stimmen überein.

Jetzt beschreiben wir den Inhalt der Farbtransformationsdaten, damit die Decodierung die umgekehrte Farbtransformation anwenden und die ursprünglichen roten und blauen Werte wiederherstellen kann. Die ersten 3 Bit der Farbtransformationsdaten enthalten genau wie die Predictor-Transformation die Breite und Höhe des Bildblocks in Anzahl von Bits:

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. ColorTransformElement-Instanzen werden als Pixel eines Bildes behandelt und mit den in Kapitel 5 beschriebenen Methoden codiert.

Bei der Decodierung werden ColorTransformElement-Instanzen der Blöcke decodiert und die umgekehrte Farbtransformation auf die ARGB-Werte der Pixel angewendet. Wie bereits erwähnt, werden bei dieser umgekehrten Farbtransformation den roten und blauen Kanälen ColorTransformElementWerte hinzugefügt. [ÄNDERUNG3]

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 Subtrahierende grüne Transformation

Die grüne Subtraktion wird von den roten und blauen Werten der einzelnen Pixel subtrahiert. Wenn diese Transformation vorhanden ist, muss der Decoder sowohl für Rot als auch für Blau den grünen Wert hinzufügen. Mit dieser Transformation sind keine Daten verknüpft. Der Decoder wendet die umgekehrte 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, aber dennoch häufig nützlich. Da sie die Dynamik der Farbtransformation erweitern kann und hier keine zusätzlichen Daten vorhanden sind, kann die subtrahierende grüne Transformation mit weniger Bits als eine vollfarbige Farbtransformation codiert werden.

4.4 Transformation zur Farbindexierung

Wenn es nicht viele eindeutige Pixelwerte gibt, ist es möglicherweise effizienter, ein Farbindexarray zu erstellen und die Pixelwerte durch die Indizes des Arrays zu ersetzen. Dies erreicht die Transformation mit der Farbindexierung. Im Kontext der verlustfreien WebP nennen wir dies keine Palettentransformation, da ein ähnliches, aber dynamisches Konzept in der verlustfreien WebP-Codierung vorliegt: der Farbcache.

Die Transformation zur Farbindexierung prüft die Anzahl der eindeutigen ARGB-Werte im Bild. Wenn diese Zahl unter einem Grenzwert (256) liegt, wird ein Array dieser ARGB-Werte erstellt. Diese werden dann verwendet, um die Pixelwerte durch den entsprechenden Index zu ersetzen: Der grüne Kanal der Pixel wird durch den Index ersetzt. Alle Alphawerte werden auf 255 gesetzt. Alle roten und blauen Werte werden auf 0 gesetzt.

Die Transformationsdaten enthalten die Farbtabellengröße und die Einträge in der Farbtabelle. Der Decoder liest die Daten der Transformation zur Farbindexierung so:

// 8 bit value for 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, bei einer Höhe von einem Pixel und einer Breite von color_table_size. Die Farbtabelle wird immer subtrahiert, um die Bildentropie zu reduzieren. Die Deltas von Palettenfarben enthalten in der Regel viel weniger Entropie als die Farben selbst, was bei kleineren Bildern zu erheblichen Einsparungen führt. Bei der Decodierung kann jede endgültige Farbe in der Farbtabelle abgerufen werden, indem die vorherigen Farbkomponentenwerte von jeder ARGB-Komponente separat addiert und die niedrigstwertigen acht Bit des Ergebnisses gespeichert werden.

Die umgekehrte Transformation für das Bild ersetzt einfach die Pixelwerte (die Indexe für die Farbtabelle sind) durch die tatsächlichen Farbtabellenwerte. Die Indexierung erfolgt basierend auf 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 RGB-Farbwert auf 0x00000000 (transparent schwarz) festgelegt werden. [GEÄNDERT]

Wenn die Farbtabelle klein ist (gleich oder kleiner als 16 Farben), werden mehrere Pixel zu einem einzelnen Pixel zusammengefasst. Bei der Pixel-Bündelung werden mehrere (2, 4 oder 8) Pixel in ein einzelnes Pixel gepackt, wodurch die Bildbreite reduziert wird. Die Pixel-Bündelung ermöglicht eine effizientere gemeinsame Entropiecodierung der benachbarten Pixel und bietet dem Entropiecode einige arithmetische Codierungsvorteile. Sie kann jedoch nur verwendet werden, wenn 16 oder weniger eindeutige Werte vorliegen.

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. Der Wert 0 gibt an, dass für das Bild keine Pixelbündelung durchgeführt werden muss. Ein Wert von 1 gibt an, dass zwei Pixel zusammengenommen sind und jedes Pixel einen Bereich von [0...15] hat. Ein Wert von 2 bedeutet, dass vier Pixel kombiniert sind und jedes Pixel einen Bereich von [0...3] hat. Ein Wert von 3 gibt an, dass acht Pixel kombiniert sind und jedes Pixel einen Bereich von [0...1] hat, d. h. einen Binärwert.

Die Werte werden wie folgt in die grüne Komponente gepackt:

  • width_bits = 1: Für jeden x-Wert, wobei x ⋅ 0 (Mod 2) ist, wird ein grüner Wert bei x in den 4 niedrigsten Bits des grünen Werts bei x / 2 positioniert, ein grüner Wert bei x / 1 in die 4 signifikanten Bits des grünen Werts bei x / 2.
  • width_bits = 2: Für jeden x-Wert, wobei x = 0 (Mod 4) ist, wird ein grüner Wert bei x in den 2 niedrigsten Bits des grünen Werts bei x / 4 positioniert, grüne Werte bei x + 1 bis x + 3, um die signifikanteren Bits für den grünen Wert bei x / 4 festzulegen.
  • width_bits = 3: Für jeden x-Wert, wobei x 0 (Mod 8) ist, wird ein grüner Wert bei x im niedrigstwertigen Bit des grünen Werts bei x / 8 positioniert, grüne Werte bei x + 1 bis x + 7, um die signifikanteren Bits für den grünen Wert bei x / 8 zu bilden.

5 Bilddaten

Bilddaten sind ein Array von Pixelwerten in der Reihenfolge der Zeilen.

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. Die roten und grünen Komponenten eines Pixels definieren den Metapräfixcode, der in einem bestimmten Block des ARGB-Bilds verwendet wird.
  3. Predictor-Image: Speichert die Metadaten für Predictor Transform. Die grüne Komponente eines Pixels definiert, welcher der 14 Prädikatoren innerhalb eines bestimmten Blocks des ARGB-Bilds verwendet wird.
  4. Bild für die Farbtransformation. Sie wird durch ColorTransformElement-Werte (in Color Transform definiert) für verschiedene Blöcke des Bildes erstellt. Jedes ColorTransformElement 'cte' wird als Pixel behandelt, dessen Alphakomponente 255, die rote Komponente cte.red_to_blue, die grüne Komponente cte.green_to_blue und die blaue Komponente cte.green_to_red ist.
  5. Farbindexierungsbild: ein Array der Größe color_table_size (bis zu 256 ARGB-Werte), in dem die Metadaten für die Color Indexing-Transformation gespeichert werden. Dies wird als Bild mit der Breite color_table_size und der Höhe 1 gespeichert.

5.2 Bilddaten codieren

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

Das Bild wird zuerst in eine Reihe von Blöcken mit fester Größe (in der Regel 16 x 16-Blöcke) unterteilt. Jeder dieser Blöcke wird mithilfe eigener Entropiecodes modelliert. Außerdem können mehrere Blöcke dieselben Entropiecodes haben.

Grund: Das Speichern eines Entropiecodes ist kostenpflichtig. Diese Kosten können minimiert werden, wenn statistisch ähnliche Blöcke einen Entropiecode gemeinsam nutzen und diesen Code nur einmal speichern. Ein Encoder kann beispielsweise ähnliche Blöcke finden, indem er sie mithilfe ihrer statistischen Attribute clustert oder mehrere zufällig ausgewählte Cluster wiederholt verbindet, wenn die Gesamtmenge der für die Codierung des Images erforderlichen Bits reduziert wird.

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

  1. Präfixkodiertes Literal: Jeder Kanal (grün, rot, blau und Alpha) ist unabhängig von der Entropie codiert.
  2. Referenz für LZ77: Eine Reihe von Pixeln wird an einer anderen Stelle im Bild kopiert.
  3. Farbcache-Code: Verwendung eines kurzen multiplikativen Hash-Codes (Farbcache-Index) einer kürzlich gesehenen Farbe.

In den folgenden Unterabschnitten werden diese im Detail beschrieben.

5.2.1 Codierte Literale mit Präfix

Das Pixel wird als Präfix-codierte Werte von Grün, Rot, Blau und Alpha (in dieser Reihenfolge) gespeichert. Weitere Informationen finden Sie in diesem Abschnitt.

5.2.2 LZ77-Rückwärtsreferenz

Rückwärtsverweise sind Tupel aus length und distance code:

  • Länge gibt an, wie viele Pixel in Scan-Zeilenreihenfolge kopiert werden sollen.
  • Der Entfernungscode 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 Werte für Länge und Entfernung werden mithilfe der Präfixcodierung LZ77 gespeichert.

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

Grund: Mit diesem Ansatz wird der Speicherbedarf für den Entropiecode reduziert. Große Werte sind in der Regel selten. Daher werden für sehr wenige Werte im Bild zusätzliche Bits verwendet. Dieser Ansatz führt also insgesamt zu einer besseren Komprimierung.

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

Wertebereich Präfixcode Zusätzliche Bits
1 0 0
2 1 0
3 2 0
4 3 0
5,6 4 1
7..8 5 1
9...12 6 2
13...16 7 2
... ... ...
3072...4096 23 10
... ... ...
524289...786432 38 18
786433...1048576 39 18

Der Pseudocode zum Abrufen eines Werts (Länge oder Entfernung) aus dem Präfixcode lautet wie folgt:

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 Entfernungscode 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 Entfernungscode und der Position eines vorherigen Pixels definiert.

Entfernungscodes über 120 geben die Pixelentfernung in Scanreihenfolge an, die um 120 verschoben ist.

Die kleinsten Entfernungscodes [1..120] sind speziell und werden für eine nahe Nachbarschaft des aktuellen Pixels reserviert. Dieses Viertel besteht aus 120 Pixeln:

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

Die Zuordnung zwischen Entfernungscode i und dem benachbarten Pixelversatz (xi, yi) sieht so aus:

(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 Abstandscode 1 gibt beispielsweise den Versatz von (0, 1) für das benachbarte Pixel an, d. h. das Pixel über dem aktuellen Pixel (0 Pixeldifferenz in X-Richtung und eine Pixeldifferenz in Y-Richtung). Gleichermaßen gibt der Entfernungscode 3 das linke obere Pixel an.

Der Decoder kann einen Entfernungscode i in einen Entfernungsabstand von dist für eine Scanreihenfolge umwandeln:

[ÄNDERUNG3]

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

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

5.2.3 Farb-Cache-Codierung

Der Farbcache speichert eine Reihe von Farben, die kürzlich im Bild verwendet wurden.

Grund: Auf diese Weise können die kürzlich verwendeten Farben manchmal effizienter bezeichnet werden als die beiden anderen Methoden (siehe 5.2.1 und 5.2.2).

Die Cache-Farbcodes werden so gespeichert: Erstens 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 in dem Präfixcode übertragen, der die grünen Symbole und die Längenpräfixcodes decodiert. Wenn dieses Bit jedoch 1 ist, wird die Farbcache-Größe als Nächstes 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 von color_cache durch (1 << color_cache_code_bits). Der Bereich der zulässigen Werte für color_cache_code_bits ist [1–11]. Konforme Decodierer müssen für andere Werte einen beschädigten Bitstream angeben.

Ein Farb-Cache ist ein Array der Größe color_cache_size. Jeder Eintrag speichert eine ARGB-Farbe. Zur Suche nach den Farben werden sie indiziert (0x1e35a7bd * color) >> (32 - color_cache_code_bits). In einem Farb-Cache 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 Farbcachewerten auf null gesetzt. Der Farbcache wird bei der Decodierung in diese Farbe umgewandelt. Der Status des Farbcaches wird durch Einfügen aller Pixel in der Reihenfolge, in der sie im Stream angezeigt werden, entweder durch Rückwärtsverweise oder als Literale, beibehalten.

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 übertragen, im Gegensatz zu den tatsächlichen Präfixcodes.

Im Speziellen wird für das Format Präfixe für einzelne Varianten verwendet. Mit anderen Worten können unterschiedliche Bildblöcke potenziell verschiedene Entropiecodes verwenden.

Grund: Verschiedene Bereiche des Bildes können unterschiedliche Eigenschaften haben. Dadurch bietet sie mehr Flexibilität und möglicherweise eine bessere Komprimierung.

6.2 Details

Die codierten Bilddaten bestehen aus mehreren Teilen:

  1. Präfixcodes decodieren und erstellen [AMENDED2]
  2. Metapräfix-Codes
  3. Entropiecodierte Bilddaten

6.2.1 Präfixcodes decodieren und erstellen

Es gibt mehrere Schritte zum Decodieren der Präfixcodes.

Codelängen decodieren:

In diesem Abschnitt wird beschrieben, wie die Länge des Präfixcodes aus dem Bitstream gelesen wird.

Die Länge des Präfixcodes kann 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 einfachen Code für die Codelänge.
  • Wenn dieses Bit 0 ist, ist dies ein normaler Code für die Codelänge.

In beiden Fällen können noch ungenutzte Codelängen verwendet werden, die noch Teil des Streams sind. Dies kann ineffizient sein, ist jedoch durch das Format zulässig.

(i) Codelänge für den einfachen Code:

[Geändert]2

Diese Variante wird im Sonderfall verwendet, wenn nur ein oder zwei Präfixsymbole im Bereich [0...255] mit der Codelänge 1 enthalten sind. Alle anderen Längen des Präfixcodes sind implizit Nullen.

Das erste Bit gibt die Anzahl der Symbole an:

int num_symbols = ReadBits(1) + 1;

Nachfolgend sind die Symbolwerte aufgeführt.

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

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;
}

Hinweis: Ein weiterer Sonderfall ist, wenn alle Längen von Präfixcodes null sind (leerer Präfixcode). Ein Präfixcode für die Entfernung kann beispielsweise leer sein, wenn keine umgekehrten Verweise vorhanden sind. Ebenso können Präfixcodes für Alpha, Rot und Blau leer sein, wenn alle Pixel im selben Metapräfixcode mithilfe des Farbcaches erstellt werden. In diesem Fall ist jedoch keine besondere Behandlung erforderlich, da leere Präfixcodes als Codes mit einem einzelnen Symbol 0 codiert werden können.

(ii) Codelänge Normalcode:

Die Codelängen des Präfixcodes passen in 8 Bit und werden folgendermaßen gelesen. num_code_lengths gibt zuerst die Anzahl der Codelängen an.

int num_code_lengths = 4 + ReadBits(4);

Wenn num_code_lengths > 19 ist, ist der Bitstream ungültig. [ÄNDERUNG3]

Die Codelängen werden selbst mithilfe von Präfixcodes codiert. Codelängen niedrigerer Ebene (code_length_code_lengths) müssen zuerst gelesen werden. Der Rest dieser code_length_code_lengths (gemäß der Bestellung 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);
}

Wenn ReadBits(1) == 0 ist, ist die maximale Anzahl der verschiedenen Lesesymbole num_code_lengths. Andernfalls ist sie so definiert:

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

Eine Präfixtabelle wird dann aus code_length_code_lengths erstellt und zum Lesen von bis zu max_symbol Codelängen verwendet.

  • Der Code [0...15] gibt die Länge des Literalcodes an.
    • Der Wert 0 bedeutet, dass keine Symbole codiert wurden.
    • Die Werte [1...15] geben die Bitlänge des jeweiligen Codes an.
  • Code 16 wiederholt den vorherigen Wert ungleich [3, 6], d. h. 3 + ReadBits(2) Mal. Wenn Code 16 verwendet wird, bevor ein Wert ungleich null ausgegeben wurde, wird der Wert 8 wiederholt.
  • Code 17 gibt eine Reihe von Nullen aus [3..10], d.h. 3 + ReadBits(3)-mal.
  • Code 18 gibt eine Reihe von Nullen der Länge [11...138] aus, d. h. 11 + ReadBits(7) Mal.

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

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

6.2.2 Metapräfixcodes decodieren

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

Metapräfixcodes können nur dann verwendet werden, wenn das Bild in der Rolle eines ARGB-Bilds verwendet wird.

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

  • Wenn dieses Bit null ist, wird im Bild nur ein einziger Meta-Präfixcode verwendet. Es werden keine Daten mehr gespeichert.
  • Wenn dieses Bit eins ist, verwendet das Image mehrere Metapräfix-Codes. Diese Meta-Präfixcodes werden als Entropiebild gespeichert (siehe unten).

Entropiebild:

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

Die ersten 3 Bit enthalten den Wert prefix_bits. Die Abmessungen des Entropiebildes werden von prefix_bits abgeleitet.

int prefix_bits = ReadBits(3) + 2;
int prefix_xsize = DIV_ROUND_UP(xsize, 1 << prefix_bits);
int prefix_ysize = DIV_ROUND_UP(ysize, 1 << prefix_bits);

wobei DIV_ROUND_UP zuvor definiert ist.

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

Interpretation von Metapräfixcodes:

Mit jedem Pixel (x, y) sind fünf Präfixcodes verknüpft. Diese Codes sind (in Bitstream-Reihenfolge):

  • Präfixcode 1: wird für den grünen Kanal, die Rückwärtsreferenzlänge und den Farbcache verwendet
  • Präfixcode 2, 3 und 4: Wird für rote, blaue und Alphakanäle verwendet.
  • Präfixcode 5: Wird für die umgekehrte Entfernung verwendet.

Von jetzt an bezeichnen wir diese Gruppe als Präfix-Codegruppe.

Die Anzahl der Präfixcodegruppen im ARGB-Bild kann ermittelt werden, indem der größte Meta-Präfixcode im Entropiebild ermittelt 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, beträgt die Gesamtzahl der Präfixcodes:

int num_prefix_codes = 5 * num_prefix_groups;

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

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

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

Der Decodierer verwendet dann die Präfixcodegruppe prefix_group, um das Pixel (x, y) zu decodieren, wie im nächsten Abschnitt beschrieben.

6.2.3 Entropiecodierte Bilddaten decodieren

[Geändert]2

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

Lesen Sie das nächste 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. Rot mit dem Präfixcode 2 aus dem Bitstream lesen.
    3. Lesen Sie Blau aus dem Bitstream mit dem Präfixcode 3.
    4. Lesen Sie Alpha aus dem Bitstream mit dem Präfixcode 4.
  2. wenn S >= 256 && S < 256 + 24
    1. Verwenden Sie S – 256 als Präfix für die Länge.
    2. Zusätzliche Bits für Länge aus dem Bitstream lesen.
    3. Bestimme die Rückwärtsreferenzlänge L aus dem Präfixcode für die Länge und die zusätzlichen gelesenen Bits.
    4. Distanzpräfixcode mit dem Präfixcode 5 aus dem Bitstream lesen.
    5. Lies zusätzliche Bits für die Entfernung vom Bitstream.
    6. Bestimme die umgekehrte Entfernung D vom Code für den Entfernungspräfix und die zusätzlichen gelesenen Bits.
    7. Kopieren Sie die L-Pixel (in Scanlinienreihenfolge) aus der Sequenz der Pixel vor den D-Pixeln.
  3. wenn S >= 256 + 24
    1. Verwende S - (256 + 24) als Index im Farbcache.
    2. Ruft eine ARGB-Farbe aus dem Farbcache an diesem Index ab.

7 Gesamtstruktur des Formats

Unten sehen Sie eine Darstellung des Formats in Augmented Backus-Naur Form (ABNF). Sie umfassen nicht alle Details. Das Ende des Bildes (EOI) wird nur implizit in die Anzahl der Pixel codiert (xsize × ysize).

7.1 Grundstruktur

format       = RIFF-header image-size image-stream
RIFF-header  = "RIFF" 4OCTET "WEBP" "VP8L" 4OCTET %x2F
image-size   = 14BIT 14BIT ; width - 1, height - 1
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

[Geändert]2

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    =  code-length-code encoded-code-lengths
code-length-code      =  ; see section "Normal Code Length Code"

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

Mögliche Beispielsequenz:

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