Spezifikation für WebP Lossless Bitstream

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

Zusammenfassung

WebP lossless ist ein Bildformat für die verlustfreie Komprimierung von ARGB-Bildern. Die das verlustfreie Format die Pixelwerte genau speichert und wiederherstellt, Farbwerte für vollständig transparente Pixel. Universeller Algorithmus für sequenzielle Datenkomprimierung (LZ77), Präfixcodierung und Farb-Cache Komprimierung der Bulk-Daten. Es wurden Dekodierungsgeschwindigkeiten nachgewiesen, die schneller als bei PNG sind, sowie eine um 25 % höhere Komprimierung als mit dem heutigen PNG-Format.

1 Einleitung

In diesem Dokument wird die Darstellung komprimierter Daten einer verlustfreien WebP-Datei beschrieben. Bild. Es dient als detaillierte Referenz für den verlustfreien WebP-Encoder und Decoder-Implementierung verwenden.

In diesem Dokument verwenden wir die Syntax der Programmiersprache C, um zu beschreiben, und gehen davon aus, dass eine Funktion zum Lesen von Bits vorhanden ist, ReadBits(n) Die Byte werden in der natürlichen Reihenfolge des Streams gelesen, der und die Bits jedes Byte werden in der am wenigsten signifikanten Bit-Erste-Reihenfolge gelesen. Wenn mehrere Bits gleichzeitig gelesen werden, wird die Ganzzahl aus den ursprünglichen Daten in der ursprünglichen Reihenfolge konstruiert. Die höchstwertigen Bits der zurückgegebenen Daten Ganzzahl sind auch die höchstwertigen Bits der Originaldaten. Das heißt, die Anweisung

b = ReadBits(2);

entspricht den beiden folgenden Aussagen:

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

Wir gehen davon aus, dass jede Farbkomponente, d. h. Alpha, Rot, Blau und Grün, mit einem 8-Bit-Byte dargestellt wird. Der entsprechende Typ wird als uint8 definiert. A ein ganzes ARGB-Pixel wird durch einen Typ mit dem Namen uint32 dargestellt, der ein vorzeichenloser bestehend aus 32 Bits. Im Code, der das Verhalten der Transformationen, werden diese Werte in den folgenden Bits kodifiziert: Alpha in Bits. 31..24, rot in den Bits 23..16, grün in den Bits 15..8 und blau in den Bits 7..0; Allerdings Implementierungen des Formats können intern eine andere Darstellung verwenden.

Im Grunde enthält ein verlustfreies WebP-Bild Header-Daten, Transformationsinformationen und die eigentlichen Bilddaten. Überschriften enthalten die Breite und Höhe des Bildes. Ein verlustfreies WebP-Bild kann vier verschiedene Arten von Transformationen durchlaufen, bevor es entropiecodiert wird. Die Transformationsinformationen im Bitstream enthalten die Daten die für die Anwendung der jeweiligen Umkehrtransformationen erforderlich sind.

2. Nomenklatur

ARGB
Ein Pixelwert, der aus Alpha-, Rot-, Grün- und Blauwerten besteht.
ARGB-Bild
Ein zweidimensionales Array mit ARGB-Pixeln.
Farbcache
Ein kleines gehashtes Array zum Speichern kürzlich verwendeter Farben, um mit kürzeren Codes wieder ins Gedächtnis rufen.
Bild zur Farbindexierung
Ein eindimensionales Bild mit Farben, das mithilfe einer kleinen Ganzzahl indexiert werden kann (bis zu 256 in WebP, verlustfrei).
Bild zur Farbtransformation
Ein zweidimensionales Bild mit Teilauflösung, das Daten über Korrelationen von Farbkomponenten.
Entfernungszuordnung
Ändert die LZ77-Abstände so, dass die kleinsten Werte für Pixel in zweidimensionale Nähe.
Entropie-Bild
Ein zweidimensionales Bild mit Teilauflösung, das angibt, welche Entropiecodierung in einem entsprechenden Quadrat im Bild verwendet werden, d. h., jedes Pixel ist ein Meta-Element Präfixcode.
LZ77
Ein wörterbuchbasierter Algorithmus für die gleitende Fensterkomprimierung, der entweder oder als Folge früherer Symbole beschrieben.
Meta-Präfixcode
Eine kleine Ganzzahl (bis zu 16 Bit), die ein Element im Meta-Präfix indexiert Tabelle.
Predictor-Bild
Ein zweidimensionales Bild mit Teilauflösung, das angibt, welcher räumliche Predictor ist für ein bestimmtes Quadrat im Bild verwendet.
Präfixcode
Eine klassische Entropiecodierung, bei der eine kleinere Anzahl von Bits verwendet wird für häufigere Codes.
Präfixcodierung
Eine Möglichkeit, größere Ganzzahlen zu entropie, um einige Bits der Ganzzahl zu codieren mithilfe eines Entropiecodes und codiert die verbleibenden Bits roh. So können Sie dass die Beschreibungen der Entropiecodes relativ klein bleiben, auch wenn Die Auswahl an Symbolen ist groß.
Scanzeilenreihenfolge
Eine Verarbeitungsreihenfolge der Pixel (von links nach rechts und von oben nach unten), beginnend mit dem Pixel oben links. Wenn eine Zeile ausgefüllt ist, fahre mit der in der nächsten Zeile.

3. RIFF-Header

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

  1. String „RIFF“
  2. Ein 32-Bit-Wert im Little-Endian-Format für die Größe des Chunks, also die gesamte Größe des Chunks, die vom RIFF-Header gesteuert wird. Normalerweise entspricht dies der Nutzlastgröße (Dateigröße abzüglich 8 Byte: 4 Byte für die RIFF-ID und 4 Byte für das Speichern des Werts selbst).
  3. String "WEBP" (RIFF-Containername).
  4. String „VP8L“ (FourCC für verlustfrei codierte Bilddaten)
  5. Ein Little-Endian-Wert von 32 Bit für die Anzahl der Byte im verlustfreiem Stream.
  6. 1-Byte-Signatur 0x2f.

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

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

Die Genauigkeit von 14 Bit für die Bildbreite und -höhe beschränkt die maximale Größe eines Verlustfreie WebP-Bilder 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, andernfalls auf 1.

int alpha_is_used = ReadBits(1);

Die Versionsnummer 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 reversible Manipulationen der Bilddaten, durch die die verbleibende symbolische Entropie, indem räumliche und Farbkorrelationen modelliert werden. Sie kann die endgültige Kompression dichter werden.

Ein Bild kann vier Arten von Transformationen durchlaufen. Ein 1-Bit gibt an, vorhandenen Transformationen aus. Jede Transformation darf nur einmal verwendet werden. Die Transformationen werden nur für das ARGB-Bild auf Hauptebene verwendet. der Bilder mit Unterauflösung (Farbtransformationsbild, Entropiebild und Prädiktorbild) haben keine Transformationen. und nicht einmal das 0-Bit für das Ende der Transformationen.

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

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 beiden 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 Informationen, die zur Anwendung der Umkehrtransformation erforderlich sind, und hängt von der Transformationstyp. Die inversen Transformationen werden in umgekehrter Reihenfolge angewendet, werden sie aus dem Bitstream gelesen, d. h. die letzte zuerst.

Als Nächstes beschreiben wir die Transformationsdaten für verschiedene Typen.

4.1 Vorhersagetransformation

Die Predictor-Transformation kann zur Reduzierung der Entropie verwendet werden, indem dass benachbarte Pixel oft korrelieren. In der Predictor-Transformation Der aktuelle Pixelwert wird aus den bereits decodierten Pixeln (in Scanlinie) vorhergesagt Reihenfolge) und nur der Restwert (tatsächlich - vorhergesagt) wird codiert. Das grüne -Komponente eines Pixels definiert, welcher der 14 Prädiktoren innerhalb eines bestimmten Block des ARGB-Bildes. Der Vorhersagemodus bestimmt die Art der Vorhersage. Wir teilen das Bild in Quadrate ein und alle Pixel verwenden denselben Vorhersagemodus.

Die ersten 3 Bits an Vorhersagedaten definieren die Blockbreite und -höhe als Zahl. von Bits.

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 ist ein Bild mit Unterauflösung, bei dem die grüne Komponente eines Pixels definiert, Die 14 Predictors werden für alle block_width * block_height-Pixel innerhalb bestimmten Block des ARGB-Bildes. Dieses Bild mit Unterauflösung wird mithilfe von die in Kapitel 5 beschrieben werden.

Die Anzahl der Blockspalten (transform_width) wird bei einer zweidimensionalen Indexierung. Für ein Pixel (x, y) kann der entsprechende Filterblock berechnet werden. Adresse nach:

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

Es gibt 14 verschiedene Vorhersagemodi. In jedem Vorhersagemodus wird der aktuelle Pixelwert anhand eines oder mehrerer benachbarter Pixel vorhergesagt, deren Werte bereits bekannt sind.

Wir haben die benachbarten Pixel (TL, T, TR und L) des aktuellen Pixels (P) als folgt:

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. Wenn ein Wert für P vorhergesagt wird, wurden alle O-, TL-, T-, TR- und L-Pixel bereits verarbeitet. Das P-Pixel und alle X-Pixel sind unbekannt.

Angesichts der vorhergehenden benachbarten Pixel sind die verschiedenen Vorhersagemodi wie folgt definiert ist.

Modus Vorhergesagter Wert jedes Kanals des aktuellen Pixels
0 0xff000000 (entspricht der Farbe „Schwarz“ in ARGB)
1 L
2 T
3 TR
4 TL
5 Average2(Average2(L; TR); T) (Durchschnitt2(L; TR); T)
6 Average2(L; TL)
7 Mittelwert2(L, T)
8 Durchschnitt2(TL; T)
9 Average2(T; TR) (Durchschnitt2(T; TR)
10 Durchschnitt2(Durchschnitt2(L; TL); Durchschnitt2(T; TR))
11 Select(L; T; TL)
12 ClampAddSubtractFull(L, T, TL)
13 ClampAddSubtractHalf(Average2(L, T), TL)

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

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

Der Auswahlvorhersagewert 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 Rahmenpixel gelten spezielle Regeln. Wenn es eine Predictor-Transformation unabhängig vom Modus [0...13] für diese Pixel, den Der vorhergesagte Wert für das Pixel ganz links im Bild ist 0xff000000, alle Die Pixel in der obersten Zeile entsprechen L-Pixel und alle Pixel in der Spalte ganz links T-Pixel.

Die Adressierung des TR-Pixels für Pixel in der Spalte ganz rechts außergewöhnlich. Die Pixel in der Spalte ganz rechts werden mithilfe der Modi vorhergesagt. [0...13], genau wie die Pixel nicht am Rand, sondern das Pixel ganz links auf dem die gleiche Zeile wie das aktuelle Pixel wird als TR-Pixel verwendet.

Der endgültige Pixelwert wird ermittelt, indem jeder Kanal des vorhergesagten Werts addiert wird. in den codierten Restwert ein.

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

Das Ziel der Farbtransformation besteht darin, die R-, G- und B-Werte jedes einzelnen Pixel. Die Farbtransformation behält den Grünwert (G) unverändert bei, transformiert den den roten (R)-Wert basierend auf dem grünen Wert und wandelt den blauen (B)-Wert basierend auf den grünen und dann auf den roten Wert.

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 Für jeden Block gibt es drei Typen von Farbtransformationselementen.

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

Die eigentliche Farbtransformation erfolgt durch Definition eines Farbtransformations-Deltas. Die Das Farbtransformationsdelta hängt vom ColorTransformElement ab, der gleich in einem bestimmten Block zu erstellen. Das Delta wird während der Farbtransformation abgezogen. Die umgekehrte Farbtransformation addiert dann nur diese Deltas.

Die Funktion zur Farbtransformation ist wie folgt 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 signierten 8-Bit-Ganzzahl berechnet, die ein 3,5-Festkommazahl und ein vorzeichenbehafteter 8-Bit-RGB-Farbkanal (c) [-128..127] und ist wie folgt definiert:

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

Vor dem Aufruf von ColorTransformDelta() ist eine Umwandlung von der 8‑Bit-Vorzeichenlosen Darstellung (uint8) in die 8‑Bit-Darstellung mit Vorzeichen (int8) erforderlich. Vorzeichenbehafteter Wert sollte als 8-Bit-Zweierkomplementzahl interpretiert werden (d. h.: Uint8-Bereich) [128..255] dem Bereich [-128..-1] des konvertierten int8-Werts zugeordnet ist.

Die Multiplikation muss genauer erfolgen (mit mindestens 16-Bit- Genauigkeit). Die Vorzeichenerweiterungseigenschaft der Shift-Operation spielt keine Rolle hier; werden nur die niedrigsten 8 Bits aus dem Ergebnis verwendet, und in diesen Bits Die Verschiebung der Vorzeichenerweiterung und die Verschiebung ohne Vorzeichen sind einheitlich.

Jetzt beschreiben wir den Inhalt der Farbtransformationsdaten, damit die Decodierung die umgekehrte Farbtransformation durch und stellen die ursprünglichen Rot- und Blauwerte wieder her. Die die ersten 3 Bits der Farbtransformationsdaten enthalten die Breite und Höhe der Bildblock in der Anzahl von Bits, genau wie bei der 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 für jeden Block des Images. Jedes ColorTransformElement 'cte' wird als Pixel in einem Bild mit niedriger Auflösung behandelt, dessen Alpha-Komponente 255, dessen rote Komponente cte.red_to_blue, dessen grüne Komponente cte.green_to_blue und dessen blaue Komponente cte.green_to_red ist.

Während der Decodierung werden ColorTransformElement Instanzen der Blöcke decodiert und wird die umgekehrte Farbtransformation auf die ARGB-Werte der Pixel angewendet. Als die bereits erwähnte Umkehrfunktion ColorTransformElement-Werten für die roten und blauen Kanäle fest. 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 Green-Transformation subtrahieren

Bei der Transformation „Grün subtrahieren“ werden die Grünwerte von den Rot- und Blauwerten jedes Pixels abgezogen. Wenn diese Transformation vorhanden ist, muss der Decoder das grüne den roten und den blauen Wert. Dem sind keine Daten zugeordnet Transformieren. 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, aber Da es hier keine zusätzlichen Daten gibt, kann die Subtraktion-Grün-Transformation codiert mit weniger Bits als eine vollständige Farbtransformation.

4.4 Transformation der Farbindexierung

Wenn es nicht viele eindeutige Pixelwerte gibt, ist es möglicherweise effizienter, ein Farbindex-Array zu erstellen und die Pixelwerte durch die Indizes des Arrays zu ersetzen. Farbe mit der Indexierungs-Transformation. Im Kontext von WebP Lossless nennen Sie dies keine Palettentransformation, da eine ähnliche, gibt es das dynamische Konzept bei der verlustfreien WebP-Codierung: Farbcache.)

Bei der Farbindextransformation wird die Anzahl der eindeutigen ARGB-Werte im Bild ermittelt. Wenn diese Zahl unter einem Schwellenwert (256) liegt, wird ein Array dieser ARGB-Werte, die dann verwendet werden, um die Pixelwerte durch die entsprechender Index: Der grüne Kanal der Pixel wird durch den sind alle Alphawerte 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 Transformationsdaten zur Farbindexierung so aus:

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

Die Farbtabelle wird im Bildspeicherformat selbst gespeichert. Farbtabelle erhalten Sie, indem Sie ein Bild ohne RIFF-Header, Bildgröße und wird unter der Annahme der Höhe von 1 Pixel und der Breite von color_table_size transformiert. Die Farbtabelle ist immer subtraktiv codiert, um die Bildentropie zu reduzieren. Die Deltas der Farbpaletten enthalten normalerweise viel weniger Entropie als die Farben was zu erheblichen Einsparungen bei kleineren Bildern führt. Beim Decodieren können Sie jede endgültige Farbe in der Farbtabelle abrufen, indem Sie die vorherige Farbe von jeder ARGB-Komponente separat anpassen und die am wenigsten signifikanten 8 Bit aus.

Bei der Umkehrtransformation für das Bild werden einfach die Pixelwerte (die (Indexe zur Farbtabelle) mit den tatsächlichen Werten der Farbtabelle. Die Indexierung basierend auf der Grünkomponente der ARGB-Farbe.

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

Ist der Index gleich oder größer als color_table_size, wird der "argb"-Farbwert verwendet. sollte auf 0x00000000 (transparentes Schwarz) festgelegt sein.

Wenn die Farbtabelle klein ist (mindestens 16 Farben), mehrere Pixel die zu einem einzigen Pixel gebündelt sind. Die Pixel-Bündelung umfasst mehrere (2, 4 oder 8) Pixel in ein einzelnes Pixel umwandeln und dabei die Bildbreite reduzieren. Google Pixel ermöglicht Bündelung eine effizientere Enropiecodierung der gemeinsamen Verteilung von benachbarten Pixeln. Dies bringt einige Vorteile mit der arithmetischen Codierung Entropie-Code, kann aber nur verwendet werden, wenn 16 oder weniger eindeutige Werte vorhanden sind.

Mit color_table_size wird angegeben, 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 bedeutet, dass kein Pixel vorhanden ist. wird für das Bild gebündelt. Der Wert 1 gibt an, dass zwei Pixel kombiniert und jedes Pixel hat einen Bereich von [0 bis 15]. Ein Wert von 2 bedeutet, dass vier Pixel kombiniert, und jedes Pixel hat einen Bereich von [0..3]. Ein Wert von 3 gibt an, dass acht Pixel kombiniert werden und jedes Pixel einen Bereich von [0..1] hat, also ein Binärwert.

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

  • width_bits = 1: Für jeden x-Wert, wobei x Displayanzeige 0 (Mod. 2) ein grünes Symbol darstellt der Wert bei x in den 4 niedrigstwertigen Bits des der grüne Wert bei x / 2 und ein grüner Wert bei x + 1 4 höchstwertige Bits des grünen Werts bei x / 2.
  • width_bits = 2: Für jeden x-Wert, wobei x anzupassen 0 (Mod. 4) ein grünes Symbol ist der Wert bei x in den beiden Bits mit der geringsten Signifikanz des grüner Wert bei x / 4 und grüne Werte bei x + 1 bis x + 3 sind in zu den höherwertigen Bits des grünen Werts bei x / 4.
  • width_bits = 3: Für jeden x-Wert, wobei x anzupassen 0 (Mod. 8) ein grünes Symbol ist Der Wert bei x befindet sich im niedrigstwertigen Bit des grünen Balkens der Wert bei x / 8 und die grünen Werte bei x + 1 bis x + 7 sind in der richtigen Reihenfolge angeordnet. zu den höherwertigen Bits des grünen Werts bei x / 8.

Nach dem Lesen dieser Transformation wird image_width von width_bits in einer Substichprobe erfasst. Dieses beeinflusst die Größe nachfolgender Transformationen. Die neue Größe kann mit DIV_ROUND_UP berechnet werden, wie oben definiert.

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

5 Bilddaten

Bilddaten sind ein Array von Pixelwerten in Scanlinienreihenfolge.

5.1 Rollen von Bilddaten

Wir verwenden Bilddaten in fünf verschiedenen Rollen:

  1. ARGB-Bild: Speichert die tatsächlichen Pixel des Bilds.
  2. Entropie-Image: Speichert die Meta-Präfixcodes (siehe „Decodierung von Meta-Präfixcodes“.
  3. Predictor-Bild: Speichert die Metadaten für die Predictor-Transformation (siehe "Predictor Transform").
  4. Bild zur Farbtransformation: erstellt aus ColorTransformElement-Werten (definiert in "Color Transform") für verschiedene Blöcke des Bildes.
  5. Bild zur Farbindexierung: ein Array der Größe color_table_size (bis zu 256 ARGB-Werte), in der die Metadaten für die Farbindexierungstransformation gespeichert werden (siehe „Color Indexing Transform“) verwenden.

5.2 Codierung von Bilddaten

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

Das Bild wird zunächst in eine Reihe von Blöcken mit fester Größe unterteilt, die normalerweise 16 x 16 Pixel groß sind. Blöcke). Jeder dieser Blöcke wird mit eigenen 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 teilen, wodurch dieser Code nur einmal. Ein Encoder kann beispielsweise ähnliche Blöcke finden, indem er sie gruppiert. durch wiederholtes Verbinden eines Paars zufälliger Werte ausgewählte Cluster, wenn dadurch die Gesamtmenge der für die Codierung erforderlichen Bits reduziert wird. auf das Bild.

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

  1. Präfixcodierte Literale: Jeder Kanal (grün, rot, blau und Alpha) ist entropie codiert.
  2. LZ77-Rückwärtsreferenz: Eine Folge von Pixeln wird von einer anderen Stelle im auf das Bild.
  3. Farbcache-Code: Ein kurzer multiplikativer Hash-Code (Farbcache-Index) einer kürzlich gesehenen Farbe.

In den folgenden Unterabschnitten wird jede dieser Anforderungen ausführlich beschrieben.

5.2.1 Präfix-codierte Literale

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

5.2.2 LZ77-Rückwärtsreferenz

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

  • Die Länge gibt an, wie viele Pixel in der Reihenfolge der Scanzeilen kopiert werden sollen.
  • Der Entfernungscode ist eine Zahl, die die Position eines zuvor gesehenen Pixel, von dem die Pixel kopiert werden sollen. Die genaue Zuordnung ist wie unten beschrieben.

Die Längen- und Entfernungswerte werden mithilfe der 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 als Entropiecode gespeichert, während die zusätzlichen Bits unverändert (ohne Entropiecode) gespeichert werden.

Grund: Dieser Ansatz reduziert den Speicherbedarf für die Entropie. Code. Außerdem sind große Werte meist selten, sodass zusätzliche Bits für sehr nur wenige Werte im Bild. Dieser Ansatz führt also zu einer besseren Komprimierung insgesamt.

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

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: 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 Pixel, von dem die Pixel kopiert werden sollen. In diesem Abschnitt wird die Zuordnung zwischen einem Abstandscode und der Position eines vorherigen Pixels definiert.

Entfernungscodes, die größer als 120 sind, geben die Pixelentfernung in Scanlinienreihenfolge an. um 120 verrechnet.

Die kleinsten Entfernungscodes [1..120] sind speziell und für einen Schließvorgang reserviert. Stadtteil des aktuellen Pixels. Dieser Stadtteil hat 120 Pixel:

  • Pixel, die sich 1 bis 7 Zeilen über dem aktuellen Pixel befinden und bis zu 8 Spalten umfassen bis zu 7 Spalten rechts neben dem aktuellen Pixel. [Gesamt wie Pixel = 7 * (8 + 1 + 7) = 112].
  • Pixel, die sich in derselben Zeile wie das aktuelle Pixel befinden und sich bis zu acht Spalten links vom aktuellen Pixel befinden. [8 solche Pixel].

Zuordnung zwischen dem Entfernungscode distance_code und dem Nachbarpixel Der Offset (xi, yi) lautet 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 Abstandscode 1 gibt beispielsweise einen Versatz von (0, 1) für das benachbarte Pixel an, also das Pixel über dem aktuellen Pixel (0 Pixel Unterschied in X-Richtung und 1 Pixel Unterschied in Y-Richtung). Der Abstandscode 3 gibt das Pixel oben links an.

Der Decoder kann den Entfernungscode distance_code in eine Scanzeilenreihenfolge umwandeln Abstand dist so:

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

Dabei ist distance_map die oben angegebene Zuordnung und image_width die Breite des Bilds in Pixeln.

5.2.3 Farbcache-Codierung

Im Farb-Cache wird eine Reihe von Farben gespeichert, die kürzlich im Bild verwendet wurden.

Grund: Auf diese Weise kann auf die zuletzt verwendeten Farben verwiesen werden. als sie mit den beiden anderen Methoden (siehe 5.2.1 und 5.2.2).

Farbcache-Codes werden wie folgt gespeichert. Erstens gibt es einen 1-Bit-Wert, gibt an, ob der Farb-Cache verwendet wird. Wenn dieses Bit 0 ist, gibt es keine Farb-Cache-Codes existieren, und sie werden nicht in dem Präfixcode übertragen, der den grünen und die Präfixcodes für die Länge. Wenn dieses Bit jedoch 1 ist, hat der Farbcache Größe wird 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 des Farbcache (1 << color_cache_code_bits). Der Bereich der zulässigen Werte für color_cache_code_bits ist [1..11]. Konforme Decoder müssen auf eine Bitstreams für andere Werte.

Ein Farbcache ist ein Array der Größe color_cache_size. Jeder Eintrag speichert eine ARGB-Farbe. Farben werden mithilfe von (0x1e35a7bd * color) >> (32 - color_cache_code_bits) indexiert. 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 Farben werden auf null gesetzt. Der Farb-Cache-Code wird in diese Farbe konvertiert, Decodierungszeit. Der Status des Farb-Cache wird durch Einfügen aller der durch Rückwärtsverweise oder als Literale erzeugt wird, in den Cache in welcher Reihenfolge sie im Stream erscheinen.

6 Entropiecode

6.1 Übersicht

Die meisten Daten werden mit einem kanonischen Präfixcode codiert. Daher werden die Codes übertragen, indem die Präfixcodelängen wie folgt gesendet werden: im Gegensatz zu den tatsächlichen Präfixcodes.

Insbesondere wird beim Format eine räumliche Variantenpräfixcodierung verwendet. In anderen unterschiedliche Blöcke des Bildes können unterschiedliche Entropie enthalten Codes.

Begründung: Unterschiedliche Bereiche des Bildes können unterschiedliche Eigenschaften haben. Die Möglichkeit, verschiedene Entropiecodes zu verwenden, eine potenziell 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, die . Diese Codes sind in Bitstream-Reihenfolge:

  • Präfixcode 1: wird für den grünen Kanal, die Rückwärtsreferenz und Farbcache verwenden.
  • Präfixcode 2, 3 und 4: Wird für Rot-, Blau- und Alphakanal verwendet. .
  • Präfix #5: Wird für die Rückwärtsreferenz auf Entfernung verwendet.

Ab hier wird diese Gruppe als Präfixcodegruppe bezeichnet.

6.2.1 Präfixcodes decodieren und erstellen

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

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, ist es ein Code mit einfacher Codelänge.
  • Wenn dieses Bit 0 ist, ist es ein Code mit normaler Codelänge.

In beiden Fällen kann es nicht verwendete Codelängen geben, die immer noch Teil des . Das ist zwar ineffizient, aber vom Format zulässig. Die beschriebene Baumstruktur muss eine vollständige Binärstruktur sein. Ein einzelner Blattknoten als vollständigen Binärbaum betrachtet und kann entweder mit dem einfachen Codelängencode oder normalen Codelängencode angeben. Beim Codieren eines einzelnen Blattes mit dem Code für die normale Codelänge, wobei alle Codelängen bis auf eine Nullen sind. und der Wert für einen einzelnen Blattknoten mit der Länge 1 gekennzeichnet ist, auch wenn keine Bits werden verbraucht, wenn dieser einzelne Blattknotenbaum verwendet wird.

Code für einfache Codelänge

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

Das erste Bit gibt die Anzahl der Symbole an:

int num_symbols = ReadBits(1) + 1;

Im Folgenden sind die Symbolwerte aufgeführt.

Dieses erste Symbol wird mit 1 oder 8 Bit codiert, je nach is_first_8bits Der Bereich ist [0..1] bzw. [0..255]. Das zweite Symbol, falls vorhanden, wird immer als im Bereich [0..255] liegend 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 zwar zulässig, ineffizient ist.

Hinweis:Ein weiterer Sonderfall ist, wenn alle Präfixcodelängen Nullen sind (ein leerer Präfixcode). Beispielsweise kann ein Präfixcode für Entfernung leer sein, wenn gibt es keine Rückwärtsbezüge. Präfixcodes für Alpha-, Rot- und Blau kann leer sein, wenn alle Pixel innerhalb desselben Metapräfixcodes erzeugt werden. mithilfe des Farb-Cache. In diesem Fall ist jedoch keine spezielle Behandlung erforderlich, da leere Präfixcodes als solche codiert werden können, die ein einzelnes Symbol 0 enthalten.

Code mit normaler Codelänge

Die Codelängen des Präfixcodes passen in 8 Bit und werden wie folgt gelesen. Zuerst gibt num_code_lengths die Anzahl der Codelängen an.

int num_code_lengths = 4 + ReadBits(4);

Die Codelängen werden selbst mit Präfixcodes codiert. niedrigerer Code Längen, code_length_code_lengths, müssen zuerst gelesen werden. Die restlichen code_length_code_lengths (in 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 bei ReadBits(1) == 0 die maximale Anzahl verschiedener gelesener Symbole (max_symbol) wird für jeden Symboltyp (A, R, G, B und Entfernung) auf den Alphabetgröße:

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

Andernfalls werden 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, gibt der Wert Bitstream ist ungültig.

Aus code_length_code_lengths wird dann eine Präfixtabelle erstellt, die zum Lesen bis max_symbol Codelängen.

  • Code [0..15] gibt Literalcodelängen 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 null [3 bis 6] Mal, d. h., 3 + ReadBits(2) Mal. Wenn Code 16 vor einem Wert ungleich null steht ausgegeben wurde, wird der Wert 8 wiederholt.
  • Code 17 sendet eine Reihe von Nullen der Länge [3...10], also 3 + ReadBits(3)-mal.
  • Code 18 sendet eine Reihe von Nullen der Länge [11..138], das heißt, 11 + ReadBits(7) Mal.

Sobald Codelängen gelesen wurden, wird ein Präfixcode für jeden Symboltyp (A, R, G, B und Abstand) wird durch die entsprechende Schriftgröße gebildet.

Der Code für die normale Codelänge muss einen vollständigen Entscheidungsbaum codieren, d. h. die Summe 2 ^ (-length) für alle Codes ungleich null muss genau eins sein. Es gibt jedoch eine Ausnahme von dieser Regel: den Baum mit nur einem Blattknoten, bei dem der Wert des Blattknotens mit „1“ und die anderen Werte mit „0“ gekennzeichnet sind.

6.2.2 Meta-Präfixcodes decodieren

Wie bereits erwähnt, ermöglicht das Format die Verwendung verschiedener Präfixcodes für unterschiedliche Bildblöcke zu erstellen. Meta-Präfixcodes sind Indexe, die angeben, Präfixcodes, die in verschiedenen Teilen des Images verwendet werden.

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

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

  • Wenn dieses Bit den Wert 0 hat, wird im gesamten Bild nur ein Meta-Präfix-Code verwendet. Es werden keine weiteren Daten gespeichert.
  • Wenn dieses Bit eins ist, verwendet das Image mehrere Meta-Präfixcodes. Diese Metapräfix-Codes werden als Entropiebild gespeichert (siehe unten).

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

Entropiebild

Das Entropie-Image definiert, welche Präfixcodes in verschiedenen Teilen des Bild.

Die ersten 3 Bits enthalten den Wert prefix_bits. Die Abmessungen der Entropie Bilder von 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 wurde 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 Metapräfixcodes

Die Anzahl der Präfixcodegruppen im ARGB-Bild lässt sich ermitteln, indem Sie den größten Metapräfixcode aus dem Entropiebild:

int num_prefix_groups = max(entropy image) + 1;

Dabei gibt max(entropy image) den größten im Entropiebild.

Da jede Präfixcodegruppe fünf Präfixcodes enthält, ist die Gesamtzahl der Präfixcodes Codes lautet:

int num_prefix_codes = 5 * num_prefix_groups;

Mit einem Pixel (x, y) im ARGB-Bild erhalten wir das entsprechende Präfix die wie folgt verwendet werden:

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

bei denen wir von einer PrefixCodeGroup-Struktur ausgegangen sind, steht für einen Satz von fünf Präfixcodes. Außerdem ist prefix_code_groups ein Array von PrefixCodeGroup (mit der Größe num_prefix_groups).

Der Decoder verwendet dann die Präfixcodegruppe prefix_group, um das Pixel zu decodieren (x, y), wie unter "Entropie-codiertes Bild decodieren" erläutert. Daten“ hinzu.

6.2.3 Entropie-codierte Bilddaten decodieren

Für die aktuelle Position (x, y) im Bild identifiziert der Decoder zuerst den zugehörigen Präfixcodegruppe (wie im letzten Abschnitt erläutert). In Anbetracht der Präfixcodegruppe wird das Pixel wie folgt gelesen und decodiert.

Lesen Sie als Nächstes das Symbol S mit dem Präfixcode 1 aus dem Bitstream. Beachten Sie, dass S 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 für die grüne Komponente.
    2. Lesen Sie Rot mit Präfixcode #2 aus dem Bitstream.
    3. Lies „blau“ mit dem Präfixcode 3 aus dem Bitstream.
    4. Liest Alpha aus dem Bitstream mit dem Präfixcode #4.
  2. Wenn S >= 256 & S < 256 + 24
    1. Verwenden Sie als Längenpräfixcode S-256.
    2. Liest zusätzliche Bits für die Länge aus dem Bitstream.
    3. Bestimmen Sie die Länge der Rückwärtsreferenz L aus dem Längenpräfixcode und den zusätzlichen gelesenen Bits.
    4. Lesen Sie den Präfixcode für die Entfernung aus dem Bitstream mit dem Präfixcode 5.
    5. Liest zusätzliche Bits für die Entfernung vom Bitstream.
    6. Rückbezugsentfernung D aus dem Entfernungspräfixcode bestimmen und die zusätzlichen Teile gelesen.
    7. L-Pixel (in Scanzeilenreihenfolge) aus der Pixelsequenz kopieren, die an der aktuellen Position minus D Pixel.
  3. Wenn S >= 256 + 24
    1. Verwende S - (256 + 24) als Index für den Farb-Cache.
    2. Ruft die ARGB-Farbe aus dem Farbcache bei diesem Index ab.

7 Gesamtstruktur des Formats

Unten sehen Sie eine Darstellung des Formats als angereicherte Backus-Naur-Form (ABNF) RFC 5234 RFC 7405. Sie deckt nicht alle Details ab. End-of-Image (EOI) wird nur implizit in die Anzahl der Pixel codiert (image_width * image_height).

Beachten Sie, dass *element bedeutet, dass element nicht oder öfter wiederholt werden kann. 5element bedeutet, dass element genau fünfmal wiederholt wird. %b steht für einen Binärwert.

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 eine mögliche Beispielsequenz:

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