Spezifikation für WebP Lossless Bitstream

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

Zusammenfassung

WebP lossless ist ein Bildformat für die verlustfreie Komprimierung von ARGB-Bildern. 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 komprimierte Datendarstellung eines verlustfreien WebP-Bildes beschrieben. 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 Bytes werden in der natürlichen Reihenfolge des Streams gelesen, der sie enthält, und die Bits jedes Bytes werden in der Reihenfolge vom niedrigstwertigen Bit zum höchstwertigen Bit 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 des zurückgegebenen Ganzzahlwerts sind auch die höchstwertigen Bits der ursprünglichen Daten. Daher gilt:

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. Wir definieren den entsprechenden Typ als uint8. Ein vollständiges ARGB-Pixel wird durch einen Typ namens uint32 dargestellt, eine vorzeichenlose Ganzzahl mit 32 Bit. 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 entsprechenden inversen Transformationen erforderlich sind.

2 Nomenklatur

ARGB

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

ARGB-Bild

Ein zweidimensionales Array mit ARGB-Pixeln.

Farb-Cache

Ein kleines hash-adressiertes Array zum Speichern kürzlich verwendeter Farben, damit sie mit kürzeren Codes abgerufen werden können.

Bild für die Farbindexierung

Ein eindimensionales Farbbild, das mit einer kleinen Ganzzahl indexiert werden kann (bis zu 256 in WebP lossless).

Bild mit Farbtransformation

Ein zweidimensionales Bild mit Teilauflösung, das Daten über Korrelationen von Farbkomponenten.

Entfernungskarten

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

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äfix-Code

Eine kleine Ganzzahl (bis zu 16 Bit), die ein Element im Meta-Präfix indexiert Tabelle.

Bild des Predictors

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 Methode zur Entropiecodierung größerer Ganzzahlen, bei der einige Bits der Ganzzahl mit einem Entropiecode und die verbleibenden Bits als Rohdaten codiert werden. So bleiben die Beschreibungen der Entropiecodes auch bei einem großen Symbolbereich relativ klein.

Scanzeilenauftrag

Eine Verarbeitungsreihenfolge von Pixeln (von links nach rechts und von oben nach unten), beginnend vom Pixel oben links. Sobald eine Zeile fertig ist, fahren Sie 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 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-32-Bit-Wert für die Anzahl der Bytes im verlustfreien Stream.
6. 1-Byte-Signatur 0x2f.

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

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

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

Das Bit „alpha_is_used“ ist nur ein Hinweis und sollte sich nicht auf die Dekodierung 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, mit denen sich der verbleibende symbolische Entropiewert durch Modellierung räumlicher und farblicher Korrelationen reduzieren lässt. Sie kann die endgültige Kompression dichter werden.

Ein Bild kann vier Arten von Transformationen durchlaufen. Ein Bit mit dem Wert 1 gibt die Anwesenheit einer Transformation an. 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 anhand 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 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 die Informationen, die für die Anwendung der inversen Transformation erforderlich sind. Sie hängen vom Transformationstyp ab. Die inversen Transformationen werden in umgekehrter Reihenfolge angewendet, in der sie aus dem Bitstream gelesen werden, also die letzte zuerst.

Als Nächstes werden die Transformationsdaten für verschiedene Typen beschrieben.

4.1 Vorhersagetransformation

Die Predictor-Transformation kann zur Reduzierung der Entropie verwendet werden, indem dass benachbarte Pixel oft korrelieren. Bei der Vorhersagetransformation wird der aktuelle Pixelwert aus den bereits decodierten Pixeln (in Zeilenfolge) vorhergesagt und nur der Residualwert (tatsächlicher Wert – vorhergesagter Wert) 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 Bilds. 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 die entsprechende Filterblockadresse so berechnet werden:

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

Es gibt 14 verschiedene Vorhersagemodi. In jedem Vorhersagemodus wird der aktuelle Pixelwert anhand 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) so ausgewählt:

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

Dabei steht TL für oben links, T für oben, TR für oben rechts und L für links. 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.

Anhand der vorherigen benachbarten Pixel werden die verschiedenen Vorhersagemodi so definiert:

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 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 der Seite. die gleiche Zeile wie das aktuelle Pixel wird als TR-Pixel verwendet.

Der endgültige Pixelwert wird durch Addition der einzelnen Kanäle des vorhergesagten Werts zum codierten Residualwert ermittelt.

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

4.2 Farbtransformation

Ziel der Farbtransformation ist es, die R-, G- und B-Werte der einzelnen Pixel zu dekorrelieren. Bei der Farbtransformation bleibt der Grünwert (G) unverändert. Der Rotwert (R) wird basierend auf dem Grünwert und der Blauwert (B) basierend auf dem Grünwert und dann auf dem Rotwert transformiert.

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

Eine Konvertierung von der unsignierten 8-Bit-Darstellung (uint8) in die 8-Bit-signierte Darstellung. one (int8) ist erforderlich, bevor ColorTransformDelta() aufgerufen wird. Der vorzeichenbehaftete Wert sollte als 8‑Bit-Zahl im Zweierkomplementarformat interpretiert werden. Das bedeutet, dass der Bereich von uint8 [128..255] dem Bereich [−128..−1] des umgewandelten int8-Werts zugeordnet wird.

Die Multiplikation muss mit einer höheren Genauigkeit (mindestens 16 Bit) erfolgen. Die Signaturerweiterungseigenschaft des Verschiebungsvorgangs spielt hier keine Rolle. Es werden nur die niedrigsten 8 Bit des Ergebnisses verwendet. Bei diesen Bits stimmen die Signaturerweiterungsverschiebung und die signaturlose Verschiebung überein.

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 Rest der Farbtransformationsdaten enthält ColorTransformElement Instanzen, die den einzelnen Blöcken des Bildes entsprechen. 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. Wie bereits erwähnt, werden bei dieser Inversionstransformation den Rot- und Blaukanälen nur ColorTransformElement-Werte hinzugefügt. Die Alpha- und Grünkanäle bleiben unverändert.

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

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

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

4.3 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 den grünen Wert sowohl dem roten als auch dem blauen Wert hinzufügen. 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. Da hier jedoch keine zusätzlichen Daten vorhanden sind, kann die Subtraktionsgrün-Transformation mit weniger Bits codiert werden 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. Dies wird durch die Farbindexierungstransformation erreicht. Im Zusammenhang mit WebP Lossless bezeichnen wir dies nicht als Palettentransformation, da es in der verlustfreien WebP-Codierung ein ähnliches, aber dynamischeres Konzept gibt: den 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 Farbtabellengröße und die Einträge in der Farbe . Der Decoder liest die Daten der Farbindextransformation so:

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

Die Farbtabelle wird im Bildspeicherformat selbst gespeichert. Die Farbtabelle kann durch Lesen eines Bildes ohne RIFF-Header, Bildgröße und Transformationen unter der Annahme einer Höhe von 1 Pixel und einer Breite von color_table_size abgerufen werden. Die Farbtabelle wird 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. Dabei werden mehrere (2, 4 oder 8) Pixel zu einem einzigen Pixel zusammengefasst, wodurch die Bildbreite entsprechend reduziert wird. Die Gruppierung von Pixeln ermöglicht eine effizientere gemeinsame Entropiecodierung der Verteilung benachbarter Pixel und bietet dem Entropiecode einige Vorteile, die der arithmetischen Codierung ähneln. Sie kann jedoch nur verwendet werden, wenn es 16 oder weniger eindeutige Werte gibt.

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 gibt an, dass vier Pixel kombiniert werden und jedes Pixel einen Bereich von [0..3] hat. Ein Wert von 3 bedeutet, dass acht Pixel kombiniert werden und jedes Pixel einen Bereich von [0..1] hat, also einen Binärwert.

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

• width_bits = 1: Für jeden x-Wert, wobei x anzupassen 0 (Mod 2) ein grünes Symbol ist der Wert bei x in den 4 niedrigstwertigen Bits des und ein grüner Wert bei x + 1 im 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, bei dem X ≡ 0 (mod 8) ist, wird ein grüner Wert bei X in das niedrigste Bit des grünen Werts bei X/8 eingefügt. Die grünen Werte bei X + 1 bis X + 7 werden in der Reihenfolge in die höherwertigen Bits des grünen Werts bei X/8 eingefügt.

Nach dem Lesen dieser Transformation wird image_width von width_bits in einer Substichprobe erfasst. Dies wirkt sich auf die Größe nachfolgender Transformationen aus. 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 Zeilenfolge.

5.1 Rollen von Bilddaten

Wir verwenden Bilddaten in fünf verschiedenen Rollen:

1. ARGB-Bild: Hier werden die tatsächlichen Pixel des Bilds gespeichert.
2. Entropiebild: Hier werden die Meta-Präfix-Codes gespeichert (siehe „Dekodierung von Meta-Präfix-Codes“).
3. Predictor-Bild: Speichert die Metadaten für die Predictor-Transformation (siehe "Predictor Transform").
4. Bild mit Farbtransformation: Wird mit ColorTransformElement-Werten (definiert unter Farbtransformation) für verschiedene Blöcke des Bildes erstellt.
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 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 anhand ihrer statistischen Eigenschaften clustert oder wiederholt zwei zufällig ausgewählte Cluster zusammenführt, wenn dadurch die Gesamtzahl der Bits reduziert wird, die zum Codieren des Bilds erforderlich sind.

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

1. Präfixcodierte Literale: Jeder Kanal (grün, rot, blau und Alpha) wird unabhängig voneinander mithilfe von Entropie codiert.
2. LZ77-Rückwärtsreferenz: Eine Pixelsequenz wird von einer anderen Stelle im Bild kopiert.
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äfixcodierte Literale

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

5.2.2 LZ77-Rückwärtsreferenz

Rückwärtsverweise sind Tupel aus Länge und Abstandscode:

• 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 Abstandswerte werden mit 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 mit einem Entropiecode gespeichert, während die zusätzlichen Bits unverändert (ohne Entropiecode) gespeichert werden.

Begründung: Mit diesem Ansatz wird der Speicherbedarf für den Entropiecode reduziert. Außerdem sind große Werte in der Regel selten, sodass zusätzliche Bits für sehr wenige Werte im Bild verwendet würden. 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.

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

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;

Entfernungskarte

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.

Abstandscodes größer als 120 geben den Pixelabstand in der Scanzeilenreihenfolge an, verschoben um 120.

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 und bis zu 8 Spalten links oder bis zu 7 Spalten rechts vom aktuellen Pixel befinden. [Anzahl solcher Pixel insgesamt = 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].

Die Zuordnung zwischen dem Abstandscode distance_code und dem Offset des benachbarten Pixels (xi, yi) ist folgende:

(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). 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
}

wobei distance_map die oben angegebene Zuordnung und image_width die Breite des Bildes in Pixeln ist.

5.2.3 Farb-Cache-Codierung

Im Farbcache werden Farben gespeichert, die in letzter Zeit im Bild verwendet wurden.

Begründung: Auf diese Weise können die zuletzt verwendeten Farben manchmal effizienter referenziert werden, als wenn sie mit den beiden anderen Methoden (beschrieben in 5.2.1 und 5.2.2) gesendet werden.

Farbcache-Codes werden so 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, wird als Nächstes die Größe des Farbcaches 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 Farbcaches (1 << color_cache_code_bits). Der zulässige Bereich für color_cache_code_bits ist [1..11]. Konforme Decoder müssen bei anderen Werten einen beschädigten Bitstream anzeigen.

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

Zu Beginn der Decodierung oder Codierung eines Bildes werden alle Einträge in allen Farben werden auf null gesetzt. Der Farbcache-Code wird bei der Dekodierung in diese Farbe umgewandelt. 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 durch Senden der Präfixcodelängen übertragen, im Gegensatz zu den tatsächlichen Präfixcodes.

Insbesondere wird dabei die räumlich variable Prä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.
• Vorangestellte Ziffern 2, 3 und 4: Werden jeweils für den Rot-, Blau- und Alphakanal verwendet.
• Präfixcode 5: Wird für die Rückwärtsreferenz verwendet.

Ab jetzt 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ängen der Präfixcodes können 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, wird jedoch durch das Format erlaubt. Die beschriebene Baumstruktur muss eine vollständige Binärstruktur sein. Ein einzelner Blattknoten gilt als vollständiger Binärbaum und kann entweder mit dem einfachen Codelängencode oder dem normalen Codelängencode codiert werden. 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 in dem Sonderfall verwendet, wenn nur ein oder zwei Präfixsymbole im Bereich [0..255] mit einer Codelänge von 1 vorhanden sind. 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 je nach Wert von is_first_8bits mit 1 oder 8 Bits codiert. Der Bereich ist jeweils [0..1] oder [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 zulässig, aber ineffizient.

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. Ebenso können Präfixcodes für Alpha, Rot und Blau leer sein, wenn alle Pixel innerhalb desselben Meta-Präfixcodes mit dem Farbcache erstellt werden. Dieser Fall erfordert jedoch keine spezielle Behandlung, 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 so gelesen: Mit num_code_lengths wird zuerst die Anzahl der Codelängen angegeben.

int num_code_lengths = 4 + ReadBits(4);

Die Codelängen selbst werden mit Präfixcodes codiert. Codelängen der unteren Ebene, 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 die Größe des Alphabets für den Symboltyp ist, ist der Bitstream ungültig.

Anschließend wird eine Präfixtabelle aus code_length_code_lengths erstellt, die zum Lesen von bis zu max_symbol Codelängen verwendet wird.

• „Code [0..15]“ gibt die Längen von Literalcodes an.
  • Der Wert 0 bedeutet, dass keine Symbole codiert wurden.
  • Die Werte [1..15] geben die Bitlänge des jeweiligen Codes an.
• Mit Code 16 wird der vorherige Wert, der ungleich 0 ist, [3..6]-mal, also 3 + ReadBits(2)-mal, wiederholt. 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 gibt eine Folge von Nullen der Länge [11..138] aus, also 11 + ReadBits(7) Mal.

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

Der Code für die normale Codelänge muss einen vollständigen Entscheidungsbaum codieren. Das bedeutet, dass die Summe von 2 ^ (-length) für alle Codes ungleich Null genau 1 sein muss. 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 verschiedene Blöcke des Bildes. 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, 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 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ä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 einer Breite von prefix_image_width und einer Höhe von prefix_image_height.

Interpretation von Meta-Präfix-Codes

Die Anzahl der Präfixcodegruppen im ARGB-Bild lässt sich ermitteln, indem der größte Meta-Präfixcode aus dem Entropiebild ermittelt wird:

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;

Für ein Pixel (x, y) im ARGB-Bild können wir die entsprechenden Präfixcodes so erhalten:

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äfix-Codegruppe prefix_group, um das Pixel (x, y) zu decodieren, wie im Abschnitt Entropiecodierte Bilddaten decodieren erläutert.

6.2.3 Dekodieren von entropiecodierten Bilddaten

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

Lesen Sie als Nächstes das Symbol S aus dem Bitstream mit dem Präfixcode #1. 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 als grüne Komponente.
   2. Lies „rot“ aus dem Bitstream mit dem Präfixcode 2.
   3. Lesen Sie Blau aus dem Bitstream mit dem Präfixcode #3.
   4. Lies Alpha mit dem Präfixcode 4 aus dem Bitstream.
2. Wenn S >= 256 & S < 256 + 24
   1. Verwenden Sie „S-256“ als Längenpräfixcode.
   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 Entfernungspräfixcode aus dem Bitstream mit dem Präfixcode #5.
   5. Liest zusätzliche Bits für die Entfernung vom Bitstream.
   6. Bestimmen Sie den Rückwärtsverweiseabstand D anhand des Präfixcodes für den Abstand und der zusätzlichen gelesenen Bits.
   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. ARGB-Farbe aus dem Farbcache an diesem Index abrufen.

7 Gesamtstruktur des Formats

Unten sehen Sie eine Darstellung des Formats als angereicherte Backus-Naur-Form (ABNF) RFC 5234 RFC 7405. Es werden nicht alle Details abgedeckt. Das Ende des Bildes (End of Image, EOI) ist nur implizit in der Anzahl der Pixel (image_width * image_height) codiert.

Hinweis: *element bedeutet, dass element nicht oder mehrere Male wiederholt werden kann. 5element bedeutet, dass element genau fünfmal wiederholt wird. %b steht für einen Binä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 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