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. Schnellere Decodierung als PNG demonstriert, sowie eine um 25% stärkere Verdichtung, als dies mit im 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. Wann? werden mehrere Bits gleichzeitig gelesen, wird die Ganzzahl aus dem Originaldaten in der ursprünglichen Reihenfolge. 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 Anweisungen:

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 WebP kann ein verlustfreies Bild vier verschiedene Arten von Transformationen durchlaufen, bevor es entropie codiert. 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.

Entfernungskarten

Ä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 von Pixeln (von links nach rechts und von oben nach unten), beginnend vom Pixel oben links. Wenn eine Zeile ausgefüllt ist, fahre mit der Spalte der nächsten Zeile.

3 RIFF-Header

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

1. String 'RIFF'.
2. Ein Little-Endian-32-Bit-Wert der Chunk-Länge, also der gesamten Größe des Blocks, der vom RIFF-Header gesteuert wird. Normalerweise entspricht dies die Nutzlastgröße (Dateigröße minus 8 Byte: 4 Byte für die RIFF-Funktion) ID und 4 Byte zum Speichern des Werts selbst).
3. String "WEBP" (RIFF-Containername).
4. String „VP8L“ (FourCC für verlustfreie 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);

Versionsnummer ist ein 3-Bit-Code, der auf 0 festgelegt 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 Predictor-Transformation

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 zu verwenden. 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 Wert Der Pixelwert wird aus einem oder mehreren benachbarten Pixeln vorhergesagt, deren Werte bereits bekannt.

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. Bei der Zeitpunkt der Vorhersage eines Werts für P sind bereits alle O-, TL-, T-, TR- und L-Pixel bereits verarbeitet wurde und das P-Pixel sowie alle X-Pixel unbekannt sind.

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

Modus	Vorhergesagter Wert jedes Kanals des aktuellen Pixels
0	0xff000000 (steht für durchgehendes Schwarz im ARGB-Farbraum)
1	L
2	T
3	TR
4	TL
5	Average2(Average2(L; TR); T) (Durchschnitt2(L; TR); T)
6	Average2(L; TL)
7	Durchschnitt2(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 Auswahl-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) {
    return L;
  } else {
    return T;
  }
}

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

// 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 der Seite. 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 Predictor-Transformation, wird das Bild Der gleiche Transformationsmodus wird für alle Pixel in einem Block 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. 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;
}

Eine Konvertierung von der unsignierten 8-Bit-Darstellung (uint8) in die 8-Bit-signierte Darstellung. one (int8) ist erforderlich, bevor ColorTransformDelta() aufgerufen wird. 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 dort das Vorzeichen Erweiterungsverschiebungen und vorzeichenlose Verschiebungen sind konsistent.

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 in einem Bild mit Unterauflösung als Pixel behandelt mit Alphakomponente 255, rote Komponente cte.red_to_blue, grün Komponente ist cte.green_to_blue und die blaue Komponente ist cte.green_to_red.

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. Der Alpha- und der grüne bleiben die Kanäle 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

Die Transformation „Grüne Subtraktion“ subtrahiert grüne Werte von den Rot- und Blauwerten für jedes Pixel. 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 wie folgt 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 nicht viele eindeutige Pixelwerte vorhanden sind, ist es möglicherweise effizienter, eine color Index-Array und ersetzen die Pixelwerte durch die Indexe des Arrays. 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.)

Die Farbindexierungstransformation überprüft die Anzahl der eindeutigen ARGB-Werte im Bild. 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 Farbtabellengröße und die Einträge in der Farbe . 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.

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 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 wie folgt in die grüne Komponente gepackt:

• 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 wie zuvor 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), speichern die Metadaten für die Farbindexierungstransformation (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 mehrere Blöcke können dieselben Entropiecodes verwenden.

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. Farb-Cache-Code: Verwendung eines kurzen multiplikativen Hash-Codes (Farb-Cache) Index) einer kürzlich erkannten 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). In Abschnitt 6.2.3 finden Sie Informationen zur Details.

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: das Präfix Code 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 verwendet werden. unterschiedliche Wertebereiche.

Hinweis: Die maximale Länge von Rückwärtsreferenzen ist auf 4.096 begrenzt. Daher werden nur die Die ersten 24 Präfixcodes (mit den entsprechenden zusätzlichen Bits) sind für die Länge aussagekräftig. Werte. Für Entfernungswerte sind jedoch alle 40 Präfixcodes gültig.

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
…	…	…
[phone]	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. Dieser Unterabschnitt definiert die Zuordnung zwischen einem Entfernungscode und der Position eines vorherigen Pixel.

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 bis zu 8 Pixel groß sind Spalten links neben dem aktuellen Pixel. [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)

Beispielsweise gibt der Entfernungscode 1 einen Offset von (0, 1) für den benachbarten Pixel, d. h. das Pixel über dem aktuellen Pixel (0 Pixel und 1 Pixel Differenz in Y-Richtung. In ähnlicher Weise gibt der Abstandscode 3 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. In jedem Eintrag wird ein ARGB-Wert Farbe. Farben werden anhand 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 der 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.

Grund: Verschiedene Bereiche des Bildes können unterschiedliche Eigenschaften haben. Die Möglichkeit, verschiedene Entropiecodes zu verwenden, bietet mehr Flexibilität und 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 Alpha-Kanäle 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 ist angegeben durch einen 1-Bit-Wert.

• 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 . Dies ist möglicherweise ineffizient, ist jedoch durch das 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äfixcode-Längen sind implizit Nullen entspricht.

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]. Die zweite -Zeichen, falls vorhanden, wird immer davon ausgegangen, dass sie sich im Bereich [0...255] befindet und codiert ist. mit 8 Bit.

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. Dieser Fall muss jedoch nicht gesondert behandelt werden, Leere Präfixcodes können so codiert werden, dass sie 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 übrigen Elemente code_length_code_lengths (gemäß Bestellung in kCodeLengthCodeOrder) Nullen sind.

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 das Alphabet 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 ist der Baum mit einem einzelnen Blattknoten, bei dem der Blattknoten Der Wert ist mit dem Wert 1 gekennzeichnet, die anderen Werte sind Nullen.

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äfixcodes dürfen nur verwendet werden, wenn das Bild im role eines ARGB-Bilds.

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

• Wenn dieses Bit null ist, wird nur ein einziger Meta-Präfixcode überall in auf das Bild. Es werden keine weiteren Daten gespeichert.
• Wenn dieses Bit eins ist, verwendet das Image mehrere Meta-Präfixcodes. Diese Meta-Tags Präfixcodes werden als Entropie-Image gespeichert, wie unten beschrieben.

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

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 Meta-Prä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 aus dem Bitstream mit dem Präfixcode #1 aus. 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. Lesen Sie Blau aus dem Bitstream mit dem Präfixcode #3.
   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. Die Rückwärtsreferenzlänge L aus dem Längenpräfixcode und dem die zusätzlichen Bits vorgelesen werden.
   4. Lesen Sie den Entfernungspräfix-Code 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 (Augmented 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 0-mal 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