Dr. Jyrki Alakuijala, Google LLC, 2023-03-09
Zusammenfassung
WebP Lossless ist ein Bildformat für die verlustfreie Komprimierung von ARGB-Bildern. Im verlustfreien Format werden die Pixelwerte genau gespeichert und wiederhergestellt, einschließlich der Farbwerte für vollständig transparente Pixel. Für die Komprimierung der Massendaten werden ein universeller Algorithmus für die sequenzielle Datenkomprimierung (LZ77), die Präfixcodierung und ein Farbcache verwendet. Es wurden Decodierungsgeschwindigkeiten als PNG und eine um 25% dichtere Komprimierung festgestellt, die mit dem heutigen PNG-Format erreicht werden kann.
1 Einleitung
In diesem Dokument wird die Darstellung eines verlustfreien WebP-Images mit komprimierten Daten beschrieben. Sie dient als detaillierte Referenz für die Implementierung eines verlustfreien WebP-Encoders und -Decoders.
In diesem Dokument verwenden wir in großem Umfang die Syntax der Programmiersprache C, um den Bitstream zu beschreiben und das Vorhandensein einer Funktion zum Lesen von Bits, ReadBits(n), anzunehmen. Die Byte werden in der natürlichen Reihenfolge des Streams gelesen, in dem sie enthalten sind, und die Bits jedes Bytes werden in der Reihenfolge der am wenigsten signifikanten Bits gelesen. Wenn mehrere Bits gleichzeitig gelesen werden, wird die Ganzzahl aus den Originaldaten in der ursprünglichen Reihenfolge erstellt. Die höchstwertigen Bits der zurückgegebenen Ganzzahl sind auch die höchstwertigen Bits der ursprünglichen Daten. Die Anweisung
b = ReadBits(2);
ist mit den folgenden beiden Anweisungen äquivalent:
b = ReadBits(1);
b |= ReadBits(1) << 1;
Wir gehen davon aus, dass jede Farbkomponente, d. h. Alpha, Rot, Blau und Grün, in einem 8-Bit-Byte dargestellt wird. Der entsprechende Typ wird als uint8 definiert. Ein ganzes ARGB-Pixel wird durch einen Typ namens uint32 dargestellt. Dabei handelt es sich um eine vorzeichenlose Ganzzahl aus 32 Bit. Im Code, der das Verhalten der Transformationen zeigt, sind diese Werte in den folgenden Bits codiert: Alpha in den Bits 31..24, Rot in den Bits 23..16, Grün in den Bits 15..8 und Blau in den Bits 7..0. Für Implementierungen des Formats kann jedoch intern eine andere Darstellung verwendet werden.
Im Allgemeinen enthält ein verlustfreies WebP-Bild Header-Daten, Transformationsinformationen und tatsächliche Bilddaten. Überschriften enthalten die Breite und Höhe des Bildes. Ein verlustfreies WebP-Bild kann vier verschiedene Arten von Transformationen durchlaufen, bevor es mit einer Entropie codiert wird. Die Transformationsinformationen im Bitstream enthalten die Daten, die zum Anwenden der jeweiligen Umkehrtransformationen erforderlich sind.
2 Nomenklaturen
- ARGB (Farbraum)
- Ein Pixelwert, der aus Alpha-, Rot-, Grün- und Blauwerten besteht.
- ARGB-Bild
- Ein zweidimensionales Array mit ARGB-Pixeln
- Farbcache
- Ein kleines Hash-adressiertes Array, in dem kürzlich verwendete Farben gespeichert werden, um sie mit kürzeren Codes abzurufen.
- Bild zur Farbindexierung
- Ein eindimensionales Bild in Farben, das mit einer kleinen Ganzzahl indexiert werden kann (bis zu 256 in verlustfreier WebP-Datei).
- Farbtransformationsbild
- Ein zweidimensionales Bild mit Teilauflösung mit Daten über Korrelationen von Farbkomponenten.
- Distance Mapping
- Ändert die LZ77-Abstände so, dass sie die kleinsten Werte für Pixel in zweidimensionaler Näherung erhalten.
- Entropiebild
- Ein zweidimensionales Bild mit Teilauflösung, das angibt, welche Entropiecodierung in einem bestimmten Quadrat im Bild verwendet werden soll, d. h., jedes Pixel ist ein Meta-Präfixcode.
- LZ77
- Ein wörterbuchbasierter Komprimierungsalgorithmus für Schiebefenster, der Symbole entweder ausgibt oder als Abfolgen früherer Symbole beschreibt.
- Meta-Präfixcode
- Eine kleine Ganzzahl (bis zu 16 Bit), die ein Element in der Meta-Präfixtabelle indexiert.
- Predictor-Bild
- Ein zweidimensionales Bild mit Teilauflösung, das angibt, welcher räumliche Prädiktor für ein bestimmtes Quadrat im Bild verwendet wird.
- Präfix
- Eine klassische Methode zur Entropiecodierung, bei der für häufigere Codes eine kleinere Anzahl von Bits verwendet wird.
- Präfixcodierung
- Eine Möglichkeit, größere Ganzzahlen zu entropieieren, bei der einige Bits der Ganzzahl mithilfe eines Entropiecodes codiert und die verbleibenden Bits als Rohkodierung codiert werden. Dadurch bleiben die Beschreibungen der Entropiecodes auch bei einem großen Symbolbereich relativ klein.
- Scan-Line-Reihenfolge
- Eine Verarbeitungsreihenfolge von Pixeln (von links nach rechts und von oben nach unten), beginnend mit dem Pixel oben links. Wenn eine Zeile ausgefüllt ist, fahren Sie von der linken Spalte der nächsten Zeile aus fort.
RIFF-Header 3
Am Anfang des Headers befindet sich der RIFF-Container. Diese besteht aus den folgenden 21 Byte:
- Zeichenfolge "RIFF".
- Ein Little-Endian-32-Bit-Wert der Chunk-Länge, d. h. die gesamte Größe des Chunks, der vom RIFF-Header gesteuert wird. Normalerweise entspricht dies der Nutzlastgröße (Dateigröße minus 8 Byte: 4 Byte für die Kennung „RIFF“ und 4 Byte für das Speichern des Werts selbst).
- String „WEBP“ (RIFF-Containername).
- String „VP8L“ (FourCC für verlustfreie codierte Bilddaten).
- Ein Little-Endian-32-Bit-Wert der Anzahl von Byte im verlustfreien Stream.
- 1-Byte-Signatur 0x2f.
Die ersten 28 Bit 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;
Durch die 14-Bit-Genauigkeit für Bildbreite und -höhe wird die maximale Größe eines verlustfreien WebP-Bildes auf 16.384 × 1.6384 Pixel begrenzt.
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 auf dem Bild 255 sind, ansonsten 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 Änderungen der Bilddaten, die die verbleibende symbolische Entropie durch Modellierung von räumlichen und Farbkorrelationen reduzieren können. Sie erhöhen die Dichte der endgültigen Komprimierung.
Ein Bild kann vier Arten von Transformationen durchlaufen. Ein 1-Bit gibt an, dass eine Transformation vorhanden ist. Jede Transformation kann nur einmal verwendet werden. Die Transformationen werden nur für das ARGB-Bild auf Hauptebene verwendet. Die Bilder mit der Unterauflösung (Farbtransformationsbild, Entropiebild und Prädiktorbild) haben keine Transformationen, nicht einmal das 0-Bit, das das Ende der Transformationen angibt.
In der Regel verwendet ein Encoder diese Transformationen, um die Shannon-Entropie im Residuenbild zu reduzieren. Außerdem können die Transformationsdaten auf der Grundlage der Entropieminimierung entschieden 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 zum Anwenden der umgekehrten Transformation erforderlich sind, und hängen vom Transformationstyp ab. Die umgekehrten Transformationen werden in umgekehrter Reihenfolge angewendet, in der sie aus dem Bitstream gelesen werden, d. h. die letzte zuerst.
Als Nächstes beschreiben wir die Transformationsdaten für verschiedene Typen.
4.1 Predictor-Transformation
Mit der Predictor-Transformation kann die Entropie reduziert werden, indem die Tatsache genutzt wird, dass benachbarte Pixel häufig korrelieren. In der Prädiktortransformation wird der aktuelle Pixelwert aus den bereits decodierten Pixeln (in Scanline-Reihenfolge) vorhergesagt und nur der Residuenwert (tatsächlich – vorhergesagt) wird codiert. Die grüne Komponente eines Pixels definiert, welcher der 14 Prädiktoren in einem bestimmten Block des ARGB-Bilds verwendet wird. Der Vorhersagemodus bestimmt die Art der zu verwendenden Vorhersage. Wir teilen das Bild in Quadrate und alle Pixel in einem Quadrat verwenden denselben Vorhersagemodus.
Die ersten 3 Bits Vorhersagedaten definieren die Blockbreite und -höhe in 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 Bildblock. Es handelt sich um ein Bild mit niedriger Auflösung, in dem die grüne Komponente eines Pixels definiert, welcher der 14 Prädiktoren für alle block_width * block_height-Pixel in einem bestimmten Block des ARGB-Bilds verwendet wird. Dieses Bild mit Unterauflösung wird mit denselben Techniken codiert, die in Kapitel 5 beschrieben werden.
Bei der zweidimensionalen Indexierung wird die Anzahl der Blockspalten transform_width verwendet. Für ein Pixel (x, y) kann die entsprechende Filterblockadresse so berechnet werden:
int block_index = (y >> size_bits) * transform_width +
(x >> size_bits);
Es gibt 14 verschiedene Vorhersagemodi. In jedem Vorhersagemodus wird der aktuelle Pixelwert aus einem oder mehreren benachbarten Pixeln vorhergesagt, deren Werte bereits bekannt sind.
Wir haben die Nachbarpixel (TL, T, TR und L) des aktuellen Pixels (P) wie folgt 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
wobei TL oben links, T oben links, TR oben rechts und L für links steht. Zum Zeitpunkt der Vorhersage eines Werts für P wurden alle O-, TL-, T-, TR- und L-Pixel bereits verarbeitet und das P-Pixel und alle X-Pixel sind unbekannt.
Anhand der vorhergehenden benachbarten Pixel sind die verschiedenen Vorhersagemodi so definiert.
| Modus | Vorhergesagter Wert jedes Kanals des aktuellen Pixels |
|---|---|
| 0 | 0xff000000 (repräsentiert eine Volltonfarbe im ARGB-Format) |
| 1 | L |
| 2 | T |
| 3 | TR |
| 4 | TL |
| 5 | Durchschnitt2(Durchschnitt2(L; TR); T) |
| 6 | Durchschnitt2(L; TL) |
| 7 | Durchschnitt2(L; T) |
| 8 | Durchschnitt2(TL; T) |
| 9 | Durchschnitt2(T; TRY) |
| 10 | Average2(Average2(L; TL); Durchschnitt2(T; TR)) |
| 11 | Auswählen(L; T; TL) |
| 12 | ClampAddSubtractFull(L, T, TL) |
| 13 | ClampAddSubtractHalf(Average2(L, T), TL) |
Average2 ist für jede ARGB-Komponente so definiert:
uint8 Average2(uint8 a, uint8 b) {
return (a + b) / 2;
}
Der Predictor „Select“ 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 Verarbeitungsregeln. Wenn eine Vorhersagetransformation unabhängig vom Modus [0..13] für diese Pixel vorhanden ist, ist der vorhergesagte Wert für das ganz links stehende Pixel des Bildes 0xff000000, alle Pixel in der obersten Zeile sind L-Pixel und alle Pixel in der linken Spalte sind T-Pixel.
Die Adressierung des TR-Pixels für Pixel in der Spalte ganz rechts ist außergewöhnlich. Die Pixel in der Spalte ganz rechts werden mithilfe der Modi [0...13] vorhergesagt, genau wie Pixel nicht auf dem Rand. Das Pixel ganz links in derselben Zeile wie das aktuelle Pixel wird stattdessen als TR-Pixel verwendet.
Der endgültige Pixelwert wird ermittelt, indem jeder Kanal des vorhergesagten Werts zum codierten Residuenwert addiert wird.
void PredictorTransformOutput(uint32 residual, uint32 pred,
uint8* alpha, uint8* red,
uint8* green, uint8* blue) {
*alpha = ALPHA(residual) + ALPHA(pred);
*red = RED(residual) + RED(pred);
*green = GREEN(residual) + GREEN(pred);
*blue = BLUE(residual) + BLUE(pred);
}
4.2 Farbtransformation
Das Ziel der Farbtransformation besteht darin, die R-, G- und B-Werte jedes Pixels zu dekorieren. Die Farbtransformation behält den grünen Wert (G) unverändert bei, transformiert den Rotwert (R) basierend auf dem grünen Wert und transformiert den Blauwert (B) basierend auf dem grünen Wert und dann auf den Rotwert.
Wie bei der Predictor-Transformation wird zuerst das Bild in Blöcke unterteilt und für alle Pixel in einem Block wird derselbe Transformationsmodus verwendet. 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 die Definition einer Farbtransformationsdelta. Das Delta der Farbtransformation hängt von ColorTransformElement ab, das für alle Pixel in einem bestimmten Block gleich ist. Das Delta wird während der Farbtransformation subtrahiert. Bei der umgekehrten Farbtransformation werden dann nur diese Deltas addiert.
Die Farbtransformationsfunktion 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 mithilfe einer vorzeichenbehafteten 8-Bit-Ganzzahl berechnet, die eine 3,5-Festpunktzahl und einen vorzeichenbehafteten 8-Bit-RGB-Farbkanal (c) [-128..127] darstellt. Die Definition ist so definiert:
int8 ColorTransformDelta(int8 t, int8 c) {
return (t * c) >> 5;
}
Vor dem Aufruf von ColorTransformDelta() ist eine Konvertierung von der vorzeichenlosen 8-Bit-Darstellung (uint8) in die mit 8-Bit signierte Version (int8) erforderlich. Der vorzeichenbehaftete Wert muss als Zweierkomplementzahl mit 8 Bit interpretiert werden (d. h., uint8-Bereich [128..255] wird dem Bereich [-128..-1] seines konvertierten int8-Werts zugeordnet).
Die Multiplikation muss mit höherer Genauigkeit erfolgen (mit einer Genauigkeit von mindestens 16 Bit). Die Eigenschaft der Vorzeichenerweiterung des Shift-Vorgangs spielt hier keine Rolle. Nur die niedrigsten 8 Bits werden aus dem Ergebnis verwendet und die Verschiebung der Vorzeichenerweiterung und die vorzeichenlose Verschiebung sind miteinander konsistent.
Im Folgenden wird der Inhalt von Farbtransformationsdaten beschrieben, damit bei der Decodierung die umgekehrte Farbtransformation angewendet und die ursprünglichen Rot- und Blauwerte wiederhergestellt werden können. Die ersten 3 Bit der Farbtransformationsdaten enthalten, wie bei der Predictor-Transformation, die Breite und Höhe des Bildblocks in Bits:
int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;
Der verbleibende Teil der Farbtransformationsdaten enthält ColorTransformElement-Instanzen, die jedem Bildblock entsprechen. Jedes ColorTransformElement-'cte' wird als Pixel in einem Bild mit Unterauflösung behandelt, dessen Alpha-Komponente 255, rote Komponente cte.red_to_blue, grüne Komponente cte.green_to_blue und blaue Komponente cte.green_to_red ist.
Während der Decodierung werden ColorTransformElement-Instanzen der Blöcke decodiert und die umgekehrte Farbtransformation wird auf die ARGB-Werte der Pixel angewendet. Wie bereits erwähnt, fügt diese inverse Farbtransformation nur ColorTransformElement-Werte zu den Rot- und Blaukanälen hinzu. Der Alpha- und der grüne Kanal
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 Grüne Transformation subtrahieren
Die Transformation „Grüne subtrahieren“ subtrahiert grüne Werte von Rot- und Blauwerten jedes Pixels. Wenn diese Transformation vorhanden ist, muss der Decoder den grünen Wert sowohl zu den roten als auch zu den blauen Werten addieren. Mit dieser Transformation sind keine Daten verknüpft. Der Decoder wendet die umgekehrte Transformation so an:
void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
*red = (*red + green) & 0xff;
*blue = (*blue + green) & 0xff;
}
Diese Transformation ist redundant, da sie mithilfe der Farbtransformation modelliert werden kann. Da hier jedoch keine zusätzlichen Daten vorhanden sind, kann die Subtraktionsgrün-Transformation mit weniger Bits als eine vollständige Farbtransformation codiert werden.
4.4 Transformation Farbindexierung
Wenn nicht viele eindeutige Pixelwerte vorhanden sind, ist es möglicherweise effizienter, ein Farbindexarray zu erstellen und die Pixelwerte durch die Indexe des Arrays zu ersetzen. Dies wird mit der Farbindexierungstransformation erreicht. Im Kontext der verlustfreien WebP-Codierung wird dies ausdrücklich nicht als Palettentransformation bezeichnet, da in der verlustfreien WebP-Codierung ein ähnliches, aber stärker dynamisches Konzept existiert: der Farbcache.
Die Transformation zur Farbindexierung prüft die Anzahl eindeutiger ARGB-Werte im Bild. Wenn diese Zahl unter einem Grenzwert (256) liegt, wird ein Array dieser ARGB-Werte erstellt, das dann verwendet wird, um die Pixelwerte durch den entsprechenden Index zu ersetzen: Der grüne Kanal der Pixel wird durch den Index ersetzt, alle Alphawerte werden auf 255 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 der Farbindexierung wie folgt:
// 8-bit value for the color table size
int color_table_size = ReadBits(8) + 1;
Die Farbtabelle wird im Bildspeicherformat selbst gespeichert. Um die Farbtabelle zu erhalten, lesen Sie ein Bild ohne RIFF-Header, Bildgröße und Transformationen, wobei eine Höhe von 1 Pixel und die Breite von color_table_size angenommen werden.
Die Farbtabelle ist immer subtraktionscodiert, um die Bildentropie zu reduzieren. Die Deltas der Palettenfarben enthalten in der Regel viel weniger Entropie als die Farben selbst, was zu erheblichen Einsparungen bei kleineren Bildern führt. Bei der Decodierung kann jede endgültige Farbe in der Farbtabelle abgerufen werden, indem die vorherigen Farbkomponentenwerte von jeder ARGB-Komponente separat hinzugefügt und die am wenigsten signifikanten 8 Bit des Ergebnisses gespeichert werden.
Bei der umgekehrten Transformation für das Bild werden einfach die Pixelwerte (die Indizes der Farbtabelle sind) durch die tatsächlichen Farbtabellenwerte ersetzt. Die Indexierung erfolgt anhand der grünen Komponente der ARGB-Farbe.
// Inverse transform
argb = color_table[GREEN(argb)];
Wenn der Index gleich oder größer als color_table_size ist, sollte der Farbwert „argb“ auf „0x00000000“ (transparentes Schwarz) festgelegt werden.
Wenn die Farbtabelle klein ist (gleich oder kleiner als 16 Farben), werden mehrere Pixel zu einem einzelnen Pixel zusammengefasst. Die Pixelbündelung packt mehrere (2, 4 oder 8) Pixel in ein einzelnes Pixel und reduziert entsprechend die Bildbreite. Die Pixel-Bündelung ermöglicht eine effizientere Codierung der gemeinsamen Verteilungsentropie benachbarter Pixel und bietet dem Entropiecode einige arithmetische codierungsähnliche Vorteile. Sie kann jedoch nur verwendet werden, wenn maximal 16 eindeutige Werte vorhanden sind.
color_table_size gibt an, wie viele Pixel kombiniert werden sollen:
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 einen Wert von 0, 1, 2 oder 3. Ein Wert von 0 bedeutet, dass für das Bild keine Pixelbündelung erfolgen soll. Ein Wert von 1 gibt an, dass zwei Pixel kombiniert werden und jedes Pixel einen Bereich von [0...15] hat. Ein Wert von 2 gibt an, dass vier Pixel kombiniert wurden, 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 einen Binärwert.
Die Werte werden wie folgt in die grüne Komponente gepackt:
width_bits= 1: Für jeden x-Wert, wobei x Überprüfung 0 (Mod 2) ist, wird ein grüner Wert bei x in die vier niedrigstwertigen Bits des grünen Werts bei x / 2 und ein grüner Wert bei x + 1 in die vier höchstwertigen Bits des grünen Werts bei x / 2 positioniert.width_bits= 2: Für jeden x-Wert, wobei x 🥳 0 (Mod 4) ist, wird ein grüner Wert bei x in den zwei niedrigstwertigen Bits des grünen Werts bei x / 4 und grüne Werte bei x + 1 bis x + 3 in der Reihenfolge der signifikanteren Bits des grünen Werts bei x / 4 positioniert.width_bits= 3: Für jeden x-Wert, wobei x Übergang 0 (Mod 8) ist, wird ein grüner Wert bei x in das niedrigstwertige Bit des grünen Werts bei x / 8 und grüne Werte bei x + 1 bis x + 7 entsprechend der signifikanteren Bits des grünen Werts bei x / 8 positioniert.
Nach dem Lesen dieser Transformation wird image_width einer Stichprobe von width_bits unterzogen. Dies wirkt sich auf die Größe der nachfolgenden Transformationen aus. Die neue Größe kann mit DIV_ROUND_UP wie zuvor definiert berechnet werden.
image_width = DIV_ROUND_UP(image_width, 1 << width_bits);
5 Bilddaten
Bilddaten sind ein Array von Pixelwerten in Scanzeilenreihenfolge.
5.1 Rollen von Bilddaten
Wir verwenden Bilddaten in fünf verschiedenen Rollen:
- ARGB-Bild: Speichert die tatsächlichen Pixel des Bilds.
- Entropiebild: Speichert die Meta-Präfixcodes (siehe Decodierung von Meta-Präfixcodes).
- Predictor-Image: Speichert die Metadaten für die Predictor-Transformation (siehe Predictor-Transformation).
- Farbtransformationsbild: Erstellt aus
ColorTransformElement-Werten (in "Color Transform" definiert) für verschiedene Blöcke des Bildes. - Bild zur Farbindexierung: Ein Array der Größe
color_table_size(bis zu 256 ARGB-Werte), in dem die Metadaten für die Farbindexierungstransformation gespeichert werden (siehe Transformation zur Farbindexierung).
5.2 Codierung von Bilddaten
Die Codierung der Bilddaten ist unabhängig von ihrer Rolle.
Das Bild wird zuerst in eine Reihe von Blöcken mit fester Größe unterteilt (normalerweise 16 x 16 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 gespeichert wird. Beispielsweise kann ein Encoder ähnliche Blöcke finden, indem er sie anhand ihrer statistischen Attribute gruppiert oder ein Paar zufällig ausgewählter Cluster wiederholt zusammenfügt, wenn die Gesamtmenge der zum Codieren des Bildes erforderlichen Bits reduziert wird.
Jedes Pixel wird mit einer der drei möglichen Methoden codiert:
- Präfix-codierte Literale: Jeder Kanal (Grün, Rot, Blau und Alpha) ist unabhängig entropiecodiert.
- LZ77-Rückwärtsreferenz: Eine Folge von Pixeln wird von einer anderen Stelle im Bild kopiert.
- Farb-Cache-Code: Verwendung eines kurzen multiplikativen Hash-Codes (Farbcache-Index) einer kürzlich gesehenen Farbe.
In den folgenden Unterabschnitten werden diese im Detail beschrieben.
5.2.1 Präfix-codierte Literale
Das Pixel wird als präfixcodierte Werte für Grün, Rot, Blau und Alpha (in dieser Reihenfolge) gespeichert. Weitere Informationen finden Sie in Abschnitt 6.2.3.
5.2.2 LZ77-Rückwärtsreferenz
Rückverweise sind Tupel von length und distance code:
- Länge gibt an, wie viele Pixel in Scanzeilenreihenfolge kopiert werden sollen.
- Der Entfernungscode ist eine Zahl, die die Position eines zuvor gesehenen Pixels angibt, von der die Pixel kopiert werden sollen. Die genaue Zuordnung wird unten beschrieben.
Die Werte für Länge und Entfernung werden mithilfe der LZ77-Präfixcodierung gespeichert.
Die LZ77-Präfixcodierung teilt große Ganzzahlwerte in zwei Teile auf: den Präfixcode und die zusätzlichen Bits. Der Präfixcode wird mit einem Entropiecode gespeichert, während die zusätzlichen Bits unverändert (ohne Entropiecode) gespeichert werden.
Grund: Dieser Ansatz reduziert den Speicherbedarf für den Entropiecode. Außerdem sind große Werte in der Regel selten, sodass für sehr wenige Werte im Bild zusätzliche Bits verwendet werden. Somit führt dieser Ansatz insgesamt zu einer besseren Komprimierung.
In der folgenden Tabelle sind die Präfixe und zusätzlichen Bits für das Speichern verschiedener Wertebereiche aufgeführt.
| Wertebereich | Präfix-Code | 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:
if (prefix_code < 4) {
return prefix_code + 1;
}
int extra_bits = (prefix_code - 2) >> 1;
int offset = (2 + (prefix_code & 1)) << extra_bits;
return offset + ReadBits(extra_bits) + 1;
Entfernungszuordnung
Wie bereits erwähnt, ist ein Entfernungscode eine Zahl, die die Position eines zuvor gesehenen Pixels angibt, von der die Pixel kopiert werden sollen. In diesem Unterabschnitt wird die Zuordnung zwischen einem Entfernungscode und der Position eines vorherigen Pixels definiert.
Abstandscodes, die größer als 120 sind, geben den Pixelabstand in Scanlinienreihenfolge an, mit einem Offset von 120.
Die kleinsten Entfernungscodes [1..120] sind speziell und für eine nahegelegene Nachbarschaft des aktuellen Pixels reserviert. Diese Umgebung besteht aus 120 Pixeln:
- Pixel, die 1 bis 7 Zeilen über dem aktuellen Pixel liegen und bis zu 8 Spalten links vom aktuellen Pixel oder bis zu 7 Spalten rechts vom aktuellen Pixel befinden. [Gesamtzahl solcher Pixel =
7 * (8 + 1 + 7) = 112]. - Pixel, die sich in derselben Zeile wie das aktuelle Pixel befinden und bis zu acht Spalten links vom aktuellen Pixel liegen. [
8solcher Pixel].
Die Zuordnung zwischen dem Entfernungscode distance_code und dem benachbarten Pixelversatz (xi, yi) sieht so aus:
(0, 1), (1, 0), (1, 1), (-1, 1), (0, 2), (2, 0), (1, 2),
(-1, 2), (2, 1), (-2, 1), (2, 2), (-2, 2), (0, 3), (3, 0),
(1, 3), (-1, 3), (3, 1), (-3, 1), (2, 3), (-2, 3), (3, 2),
(-3, 2), (0, 4), (4, 0), (1, 4), (-1, 4), (4, 1), (-4, 1),
(3, 3), (-3, 3), (2, 4), (-2, 4), (4, 2), (-4, 2), (0, 5),
(3, 4), (-3, 4), (4, 3), (-4, 3), (5, 0), (1, 5), (-1, 5),
(5, 1), (-5, 1), (2, 5), (-2, 5), (5, 2), (-5, 2), (4, 4),
(-4, 4), (3, 5), (-3, 5), (5, 3), (-5, 3), (0, 6), (6, 0),
(1, 6), (-1, 6), (6, 1), (-6, 1), (2, 6), (-2, 6), (6, 2),
(-6, 2), (4, 5), (-4, 5), (5, 4), (-5, 4), (3, 6), (-3, 6),
(6, 3), (-6, 3), (0, 7), (7, 0), (1, 7), (-1, 7), (5, 5),
(-5, 5), (7, 1), (-7, 1), (4, 6), (-4, 6), (6, 4), (-6, 4),
(2, 7), (-2, 7), (7, 2), (-7, 2), (3, 7), (-3, 7), (7, 3),
(-7, 3), (5, 6), (-5, 6), (6, 5), (-6, 5), (8, 0), (4, 7),
(-4, 7), (7, 4), (-7, 4), (8, 1), (8, 2), (6, 6), (-6, 6),
(8, 3), (5, 7), (-5, 7), (7, 5), (-7, 5), (8, 4), (6, 7),
(-6, 7), (7, 6), (-7, 6), (8, 5), (7, 7), (-7, 7), (8, 6),
(8, 7)
Der Entfernungscode 1 gibt beispielsweise einen Offset von (0, 1) für das benachbarte Pixel an, also das Pixel über dem aktuellen Pixel (0-Pixel-Differenz in X-Richtung und 1-Pixel-Differenz in Y-Richtung).
Entsprechend gibt der Entfernungscode 3 das Pixel oben links an.
Der Decoder kann den Entfernungscode distance_code so in eine Scanzeilenreihenfolge-dist umwandeln:
(xi, yi) = distance_map[distance_code - 1]
dist = xi + yi * image_width
if (dist < 1) {
dist = 1
}
Dabei ist distance_map die oben genannte Zuordnung und image_width die Breite des Bildes in Pixeln.
5.2.3 Farbcache-Codierung
Der Farbcache speichert eine Reihe von Farben, die kürzlich im Bild verwendet wurden.
Grund:Auf diese Weise kann auf die kürzlich verwendeten Farben manchmal effizienter Bezug genommen werden als mit den anderen beiden Methoden (wie in 5.2.1 und 5.2.2 beschrieben) sie ausgegeben werden.
Farb-Cache-Codes werden so gespeichert. Zuerst gibt es einen 1-Bit-Wert, der angibt, ob der Farb-Cache verwendet wird. Wenn dieses Bit 0 ist, existieren keine Farb-Cache-Codes und werden nicht im Präfixcode übertragen, der die grünen Symbole und die Längen-Präfixcodes decodiert. Wenn dieses Bit jedoch 1 ist, wird als Nächstes die Größe des Farbcache 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 Decodierer müssen für andere Werte einen beschädigten Bitstream angeben.
Ein Farb-Cache ist ein Array der Größe color_cache_size. In jedem Eintrag wird eine ARGB-Farbe gespeichert. Farben werden durch Indexieren nach (0x1e35a7bd * color) >> (32 -
color_cache_code_bits) ermittelt. In einem Farbcache wird nur eine Suche durchgeführt. Es gibt keine Konfliktlösung.
Zu Beginn der Decodierung oder Codierung eines Bildes werden alle Einträge in allen Farbcache-Werten auf null gesetzt. Der Farb-Cache-Code wird zum Zeitpunkt der Decodierung in diese Farbe konvertiert. Der Status des Farbcache wird beibehalten, indem jedes Pixel in der Reihenfolge, in der sie im Stream angezeigt werden, in den Cache eingefügt wird, sei es durch eine Rückwärtsreferenz oder als Literale.
6 Entropiecode
6.1 Übersicht
Die meisten Daten werden mit einem kanonischen Präfixcode codiert. Daher werden die Codes über das Senden der Präfixcodelängen gesendet und nicht die tatsächlichen Postleitzahlen.
Das Format verwendet insbesondere eine räumliche Variantenpräfixcodierung. Mit anderen Worten, verschiedene Blöcke des Bildes können potenziell unterschiedliche Entropiecodes verwenden.
Grund: Verschiedene Bereiche des Bildes können unterschiedliche Eigenschaften haben. Die Verwendung verschiedener Entropiecodes bietet also mehr Flexibilität und möglicherweise eine bessere Komprimierung.
6.2 Details
Die codierten Bilddaten bestehen aus mehreren Teilen:
- Präfixcodes decodieren und erstellen
- Meta-Präfixcodes.
- Entropiecodierte Bilddaten.
Jedem Pixel (x, y) ist ein Satz von fünf Präfixen zugeordnet. Diese Codes sind (in Bitstream-Reihenfolge):
- Präfixcode 1: Wird für den Grünkanal, die Abwärtsreferenzlänge und den Farbcache verwendet.
- Präfixcode #2, #3 und #4: Wird für Rot-, Blau- und Alphakanäle verwendet.
- Präfixcode 5: Wird für die Rückwärtsreferenzentfernung verwendet.
Diese Gruppe wird von nun an als Präfixgruppe bezeichnet.
6.2.1 Präfixcodes decodieren und erstellen
In diesem Abschnitt wird beschrieben, wie die Präfixlängen aus dem Bitstream gelesen werden.
Die Länge der Vorwahl kann auf zwei Arten codiert werden. Die verwendete Methode wird durch einen 1-Bit-Wert angegeben.
- Wenn dieses Bit 1 ist, handelt es sich um einen einfachen Code in Codelänge.
- Wenn dieses Bit 0 ist, ist es ein Code mit normaler Codelänge.
In beiden Fällen kann es ungenutzte Codelängen geben, die immer noch Teil des Streams sind. Dies ist möglicherweise ineffizient, ist aber aufgrund des Formats zulässig. Der beschriebene Baum muss ein vollständiger binärer Baum sein. Ein einzelner Blattknoten wird als vollständiger binärer Baum betrachtet und kann entweder mit dem Code mit der einfachen Codelänge oder mit dem Code mit normaler Codelänge codiert werden. Wenn Sie einen einzelnen Blattknoten mit dem Code mit normaler Codelänge codieren, sind alle Codelängen mit Ausnahme einer Nullen und der Wert des einzelnen Blattknotens wird mit der Länge 1 gekennzeichnet – auch wenn keine Bits verbraucht werden, wenn dieser einzelne Blattknotenbaum verwendet wird.
Einfacher Code mit Codelänge
Diese Variante wird im Sonderfall verwendet, wenn nur ein oder zwei Präfixsymbole im Bereich [0...255] mit der Codelänge 1 liegen. Alle anderen Präfixlä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.
Das erste Symbol wird je nach Wert von is_first_8bits mit 1 oder 8 Bit codiert. Der Bereich ist [0...1] bzw. [0...255]. Es wird immer angenommen, dass das zweite Symbol, falls vorhanden, im Bereich [0...255] liegt und mit 8 Bit codiert ist.
int is_first_8bits = ReadBits(1);
symbol0 = ReadBits(1 + 7 * is_first_8bits);
code_lengths[symbol0] = 1;
if (num_symbols == 2) {
symbol1 = ReadBits(8);
code_lengths[symbol1] = 1;
}
Die beiden Symbole sollten sich unterscheiden. Doppelte Symbole sind zulässig, aber ineffizient.
Hinweis:Ein weiterer Sonderfall tritt auf, wenn alle Präfixlängen Nullen (ein leerer Präfixcode) sind. Ein Präfixcode für die Entfernung kann beispielsweise leer sein, wenn es keine Rückwärtsbezüge gibt. In ähnlicher Weise können die Präfixe für Alpha, Rot und Blau leer sein, wenn alle Pixel mit demselben Meta-Präfixcode mit dem Farbcache erstellt werden. Dieser Fall muss jedoch nicht gesondert behandelt werden, da leere Präfixe so codiert werden können, dass sie ein einzelnes Symbol 0 enthalten.
Normale Codelänge
Die Codelänge des Präfixcodes beträgt 8 Bit und wird 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 mithilfe von Präfixen codiert. Niedrigere Codelängen (code_length_code_lengths) müssen zuerst gelesen werden. Der Rest dieser code_length_code_lengths (gemäß 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);
}
Wenn als Nächstes ReadBits(1) == 0, wird die maximale Anzahl verschiedener Lesesymbole (max_symbol) für jeden Symboltyp (A, R, G, B und Entfernung) auf die jeweilige Alphabetgröße festgelegt:
- G-Kanal: 256 + 24 +
color_cache_size - Andere Literale (A, R und B): 256
- Entfernungscode: 40
Andernfalls ist er 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.
Eine Präfixtabelle wird dann aus code_length_code_lengths erstellt und zum Lesen von bis zu max_symbol Codelängen verwendet.
- Code [0...15] gibt die Literalcodelänge an.
- Wert 0 bedeutet, dass keine Symbole codiert wurden.
- Werte [1...15] geben die Bitlänge des jeweiligen Codes an.
- Code 16 wiederholt den vorherigen Wert ungleich null [3...6]-mal, also
3 + ReadBits(2)-mal. Wenn Code 16 verwendet wird, bevor ein Wert ungleich null ausgegeben wurde, wird der Wert 8 wiederholt. - Code 17 gibt einen Reihe von Nullen der Länge [3...10] aus, also
3 + ReadBits(3)-mal. - Code 18 gibt einen Reihe von Nullen der Länge [11...138] aus, also
11 + ReadBits(7)-mal.
Nachdem die Codelängen gelesen wurden, wird ein Präfixcode für jeden Symboltyp (A, R, G, B und Entfernung) anhand der jeweiligen Alphabetgröße gebildet.
Der Code mit normaler Codelänge muss einen vollständigen Entscheidungsbaum codieren, d. h., die Summe von 2 ^ (-length) für alle Codes ungleich null muss genau eins sein. Es gibt jedoch eine Ausnahme zu dieser Regel, den einzelnen Blattknotenbaum, bei dem der Blattknotenwert mit dem Wert 1 markiert ist und andere Werte 0 s sind.
6.2.2 Meta-Präfixcodes decodieren
Wie bereits erwähnt, ermöglicht das Format die Verwendung verschiedener Präfixe für verschiedene Blöcke des Bildes. Meta-Präfixcodes sind Indexe, mit denen angegeben wird, welche Postleitzahlen in verschiedenen Teilen des Bildes verwendet werden.
Meta-Präfixcodes 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 einen 1-Bit-Wert angegeben werden:
- Wenn dieses Bit null ist, wird überall im Bild nur ein Meta-Präfixcode verwendet. Es werden keine weiteren Daten gespeichert.
- Wenn dieses Bit eins ist, verwendet das Bild mehrere Meta-Präfixcodes. Diese Meta-Präfixcodes werden als Entropiebild gespeichert (siehe unten).
Die roten und grünen Komponenten eines Pixels definieren einen 16-Bit-Meta-Präfixcode, der in einem bestimmten Block des ARGB-Bilds verwendet wird.
Bild: Entropie
Das Entropiebild definiert, welche Präfixe in verschiedenen Teilen des Images verwendet werden.
Die ersten 3 Bits enthalten den Wert prefix_bits. Die Abmessungen des Entropiebilds werden 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 ist DIV_ROUND_UP der zuvor definierten Definition.
Die nächsten Bits enthalten ein Entropiebild 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 können Sie ermitteln, indem Sie den größten Meta-Präfixcode im Entropiebild ermitteln:
int num_prefix_groups = max(entropy image) + 1;
Dabei gibt max(entropy image) den größten Präfixcode an, der im Entropiebild gespeichert ist.
Da jede Präfixcodegruppe fünf Präfixe enthält, ergibt sich die folgende Gesamtzahl:
int num_prefix_codes = 5 * num_prefix_groups;
Bei einem Pixel (x, y) im ARGB-Bild können wir die entsprechenden Präfixcodes wie folgt 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];
Dabei gehen wir von der Existenz der PrefixCodeGroup-Struktur aus, die einen Satz von fünf Präfixen darstellt. Außerdem ist prefix_code_groups ein Array von PrefixCodeGroup (der Größe num_prefix_groups).
Der Decodierer verwendet dann die Präfixcodegruppe prefix_group, um das Pixel (x, y) zu decodieren, wie unter Entropy-codierte Bilddaten decodieren erläutert.
6.2.3 Entropy-codierte Bilddaten decodieren
Für die aktuelle Position (x, y) im Bild identifiziert der Decoder zuerst die entsprechende Präfixcodegruppe (wie im letzten Abschnitt erläutert). Anhand der Präfixcodegruppe wird das Pixel wie folgt gelesen und decodiert.
Lesen Sie als Nächstes das Symbol S aus dem Bitstream mithilfe des Präfixcodes 1 aus. S ist eine beliebige Ganzzahl im Bereich 0 bis (256 + 24 + color_cache_size- 1).
Die Interpretation von S hängt von seinem Wert ab:
- Wenn S < 256
- Verwenden Sie S als grüne Komponente.
- Liest Rot aus dem Bitstream mit Präfix #2.
- Lesen Sie Blau aus dem Bitstream mit Präfix #3.
- Lesen Sie Alpha aus dem Bitstream mit Präfix 4.
- Wenn S >= 256 und S < 256 + 24
- Verwenden Sie S-256 als Längenpräfix.
- Liest zusätzliche Bits für die Länge aus dem Bitstream.
- Bestimmen Sie die Rückwärtsreferenzlänge L aus dem Längenpräfixcode und den gelesenen zusätzlichen Bits.
- Lesen Sie den Präfixcode für die Entfernung aus dem Bitstream mit dem Präfixcode 5.
- Liest zusätzliche Bits für die Entfernung vom Bitstream.
- Bestimmen Sie die Rückwärtsreferenz-Distanz D aus dem Entfernungspräfixcode und den zusätzlichen gelesenen Bits.
- Kopiert L Pixel (in Scanzeilenreihenfolge) aus der Abfolge der Pixel beginnend an der aktuellen Position minus D Pixel.
- Wenn S >= 256 + 24 ist
- Verwenden Sie S - (256 + 24) als Index für den Farbcache.
- Ruft die ARGB-Farbe aus dem Farbcache an diesem Index ab.
7 Gesamtstruktur des Formats
Unten sehen Sie eine Darstellung des Formats in angereicherter Backus-Naur-Form (Augmented Backus Naur Form, ABNF) unter RFC 5234 RFC 7405. Sie deckt nicht alle Details ab. Das Ende des Bilds (EOI) wird nur implizit in die Anzahl der Pixel (image_width * image_height) codiert.
*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