Specyfikacja bezstratnego strumienia bitowego WebP

Jyrki Alakuijala, Ph.D., Google, Inc., 9.03.2023 r.

Streszczenie

WebP bezstratne to format obrazu przeznaczony do bezstratnej kompresji obrazów ARGB. Bezstratny format przechowuje i przywraca wartości pikseli dokładnie, w tym wartości kolorów w przypadku całkowicie przezroczystych pikseli. Uniwersalny algorytm sekwencyjny kompresja danych (LZ77), kodowanie prefiksu i pamięć podręczna kolorów są wykorzystywane do lub kompresję danych zbiorczych. Dekodowanie działa szybciej niż w przypadku formatu PNG oraz o 25% gęstszej kompresji niż można osiągnąć za pomocą obecnie stosowanego formatu PNG.

1 Wstęp

Ten dokument opisuje reprezentację skompresowanych danych bezstratnego obrazu WebP. Jest to szczegółowy przewodnik po implementacji bezstratnego kodera i dekodera WebP.

W tym dokumencie do opisu strumienia bitów używamy składni języka programowania C i zakładamy istnienie funkcji do odczytu bitów, ReadBits(n). Bajty są odczytywane w naturalnej kolejności strumienia zawierającego i bity każdego bajtu są odczytywane w kolejności od najmniej istotnej wartości. Kiedy jednocześnie wiele bitów, liczba całkowita jest tworzona na podstawie oryginalne dane w oryginalnej kolejności. Najważniejsze bity zwróconego to także najbardziej istotne bity oryginalnych danych. Dlatego instrukcja

b = ReadBits(2);

jest równoważne z tymi 2 oświadczeniami:

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

Zakładamy, że każdy element koloru, czyli alfa, czerwony, niebieski i zielony, jest reprezentowany za pomocą 8-bitowego bajtu. Odpowiedni typ definiujemy jako uint8. Cały piksel ARGB jest reprezentowany przez typ uint32, który jest nieujemną liczbą całkowitą o długości 32 bitów. W kodzie pokazującym działanie przekształceń te wartości są kodowane w następujących bitach: alfa w bitach 31..24, czerwony w bitach 23..16, zielony w bitach 15..8 i niebieski w bitach 7..0. Jednak implementacje formatu mogą używać innej reprezentacji wewnętrznej.

Ogólnie rzecz biorąc, bezstratny obraz WebP zawiera dane nagłówka, informacje o przekształceniu i rzeczywiste dane obrazu. Nagłówki zawierają szerokość i wysokość obrazu. WebP bezstratnego obrazu bezstratnego, który może przejść 4 rodzaje przekształceń, zanim zostanie zakodowana entropia. Informacje o transformacji w bitstręgu zawierają dane wymagane do zastosowania odpowiednich transformacji odwrotnych.

2 Nazewnictwo

ARGB

Wartość piksela składająca się z wartości alfa, czerwonego, zielonego i niebieskiego.

Obraz ARGB

Dwuwymiarowa tablica zawierająca piksele ARGB.

pamięć podręczna kolorów

Mała tablica z adresami szyfrowanymi, w której są przechowywane ostatnio używane kolory, aby można było je przywołać za pomocą krótszych kodów.

obraz indeksowania kolorów

Jednowymiarowy obraz kolorów, który można zindeksować za pomocą małej liczby całkowitej (do 256 w formacie bezstratnym WebP).

obraz z przekształceniem kolorów

Dwuwymiarowy obraz podrozdzielczości, który zawiera dane o korelacjach kolorów.

mapowanie odległości

Zmienia odległości LZ77, by mieć jak najmniejsze wartości w pikselach dwuwymiarowa bliskość.

obraz entropii

Dwuwymiarowy obraz o podwyższonej rozdzielczości, który wskazuje, które kodowanie entropijne należy zastosować w odpowiednim kwadracie na obrazie, czyli że każdy piksel jest kodem prefiksu meta.

LZ77

Oparty na słowniku algorytm kompresji okien przesuwanych, który generuje lub opisuje je jako sekwencje wcześniejszych symboli.

kod metaprefiksu

Mała liczba całkowita (do 16 bitów), która indeksuje element w prefiksie meta tabeli.

obraz predyktora

Dwuwymiarowy obraz o niższej rozdzielczości, który wskazuje, który predykator przestrzenny jest używany w przypadku danego kwadratu na obrazie.

kod prefiksu

Klasyczny sposób kodowania entropii, w którym do rzadszych kodów używana jest mniejsza liczba bitów.

kodowanie prefiksu

Sposób kodowania entropowego większych liczb całkowitych, który polega na zakodowaniu kilku bitów liczby całkowitej za pomocą kodu entropii, a pozostałe bity są kodowane w postaci surowych danych. Dzięki temu opisy kodów entropii są stosunkowo krótkie, nawet jeśli zakres symboli jest duży.

kolejność linii skanowania

Kolejność przetwarzania w pikselach (od lewej do prawej i od góry do dołu), zaczynając do piksela u góry po lewej stronie. Po zakończeniu wiersza przejdź od w lewej kolumnie następnego wiersza.

3 Nagłówek RIFF

Na początku nagłówka znajduje się kontener RIFF. Składa się z tych 21 bajtów:

1. Ciąg znaków „RIFF”.
2. 32-bitowa wartość w formacie little-endian długości fragmentu, czyli cały rozmiar fragmentu kontrolowany przez nagłówek RIFF. Zwykle jest to równe rozmiarowi danych (rozmiar pliku minus 8 bajtów: 4 bajty na identyfikator „RIFF” i 4 bajty na przechowywanie wartości).
3. Ciąg tekstowy „WEBP” (Nazwa kontenera RIFF).
4. Ciąg tekstowy „VP8L” (FourCC dla bezstratnie zakodowanych danych obrazu).
5. 32-bitowa liczba bajtów w formacie 32-bitowym, strumienia bezstratnego.
6. 1-bajtowy podpis 0x2f.

Pierwsze 28 bitów strumienia bitów określa szerokość i wysokość obrazu. Szerokość i wysokość są dekodowane w postaci 14-bitowych liczb całkowitych w ten sposób:

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

14-bitowa precyzja szerokości i wysokości obrazu ogranicza maksymalny rozmiar Bezstratny obraz WebP do 16 384 × 16384 pikseli.

Bit alpha_is_used to tylko wskazówka i nie powinien wpływać na dekodowanie. Powinna zostanie ustawiona na 0, jeśli wszystkie wartości alfa na obrazie to 255, a w przeciwnym razie na 1.

int alpha_is_used = ReadBits(1);

Parametr version_number to 3-bitowy kod, który musi być ustawiony na 0. Każda inna wartość powinna być traktowane jako błąd.

int version_number = ReadBits(3);

4. Przekształcenia

Przekształcenia to odwracalne modyfikacje danych obrazu, które mogą zmniejszać pozostałej entropii symbolicznej przez modelowanie korelacji przestrzennych i kolorów. Mogą one zwiększyć gęstość końcowej kompresji.

Obraz może być poddawany 4 rodzajom przekształceń. Bit 1 wskazuje obecność przekształcenia. Każdego przekształcenia można użyć tylko raz. przekształcenia są używane tylko w przypadku obrazów ARGB głównego poziomu; obrazy w podrozdzielczości (obraz przekształcenia kolorów, obraz entropii i obraz prognozy) nie mają przekształceń, a nie nawet 0 bitu wskazującego koniec przekształceń.

Zwykle koder używa tych przekształceń w celu zmniejszenia entropii Shannona. na obrazie szczątkowym. Dane do przekształcenia mogą być też określane na podstawie minimalizacji entropii.

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

// Decode actual image data (Section 5).

Jeśli jest dostępne przekształcenie, kolejne 2 bity określają typ przekształcenia. Istnieją 4 typy przekształceń.

enum TransformType {
  PREDICTOR_TRANSFORM             = 0,
  COLOR_TRANSFORM                 = 1,
  SUBTRACT_GREEN_TRANSFORM        = 2,
  COLOR_INDEXING_TRANSFORM        = 3,
};

Po typie transformacji podano dane transformacji. Przekształcanie danych zawiera informacje wymagane do zastosowania przekształcenia odwrotnego i zależą od typ przekształcenia. Odwrotne przekształcenia są stosowane w odwrotnej kolejności, w jakiej są odczytywane z strumienia bitów, czyli najpierw ostatnie.

Opisujemy dane przekształceniowe w przypadku różnych typów.

4.1 Przekształcenie prognozujące

Transformer prognozowania może pomóc w zmniejszeniu entropii przez wykorzystanie faktów że sąsiednie piksele są często ze sobą skorelowane. W przekształceniu prognozy bieżąca wartość pikseli jest przewidywana na podstawie zdekodowanych pikseli (w linii skanowania kolejność), a kodowana jest tylko wartość rezydualna (rzeczywista – prognozowana). Zieleń komponentu piksela określa, który z 14 prognoz jest używany w konkretnego bloku obrazu ARGB. Tryb prognozowania określa typ do użycia z prognozą. Dzielimy obraz na kwadraty, a wszystkie piksele w kwadracie używają tego samego trybu przewidywania.

Pierwsze 3 bity danych prognozy określają szerokość i wysokość bloku w liczbie. z większą liczbą bitów.

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

Dane transformacji zawierają tryb prognozowania dla każdego bloku obrazu. Jest to obraz o niższej rozdzielczości, w którym zielony składnik piksela określa, który z 14 predyktorów jest używany do wszystkich pikseli block_width * block_height w konkretnym bloku obrazu ARGB. Ten obraz o niższej rozdzielczości jest kodowany za pomocą tych samych technik opisanych w rozdziale 5.

Liczba kolumn blokowych (transform_width) jest używana w wymiarze dwuwymiarowym indeksowanie. W przypadku piksela (x, y) można obliczyć odpowiedni blok filtra adres według:

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

Dostępnych jest 14 różnych trybów prognozowania. W każdym trybie przewidywania bieżąca wartość piksela jest przewidywana na podstawie co najmniej 1 sąsiedniego piksela, którego wartości są już znane.

Wybraliśmy sąsiednie piksele (TL, T, TR i L) bieżącego piksela (P) jako następujące:

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

gdzie TL oznacza lewy górny, T – górny, TR – prawy górny, a L – lewy. Na czas prognozowania wartości dla P, dla wszystkich pikseli O, TL, T, TR i L, i piksel P i wszystkie piksele X są nieznane.

Na podstawie poprzednich sąsiednich pikseli różne tryby prognozowania są zdefiniowane w ten sposób.

W przypadku każdego komponentu ARGB Average2 jest zdefiniowany w ten sposób:

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

Wybór predyktora jest zdefiniowany w ten sposób:

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

Wykonywane są funkcje ClampAddSubtractFull i ClampAddSubtractHalf dla każdego komponentu ARGB w ten sposób:

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

W przypadku niektórych pikseli obramowania obowiązują specjalne zasady obsługi. Jeśli występuje transformacja predyktora, niezależnie od trybu [0..13] dla tych pikseli, przewidywana wartość lewego górnego piksela obrazu to 0xff000000, wszystkie piksele w górnym rzędzie są pikselem L, a wszystkie piksele w najbardziej lewej kolumnie są pikselem T.

Adresowanie piksela TR w kolumnie z największą liczbą cyfr jest wyjątkowe. Piksele w pierwszej kolumnie po prawej stronie są prognozowane przy użyciu trybów [0..13] tak jak piksele niewidoczne na obramowaniu, ale skrajny lewy piksel na w tym samym wierszu co bieżący piksel jest używany jako piksel TR.

Ostateczna wartość piksela jest uzyskiwana przez dodanie wartości przewidywanej z każdego kanału do zakodowanej wartości resztkowej.

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 Przekształcenie kolorów

Celem przekształcenia kolorów jest dekorowanie wartości R, G i B każdego z nich piksel. Transformacja koloru zachowuje zieloną wartość (G) w niezmienionej postaci, przekształca czerwonego (R) na podstawie wartości zielonej, i przekształca wartość niebieskiej (B) na zielonej wartości, a potem na wartości czerwonej.

Podobnie jak w przypadku przekształcenia predyktora, najpierw obraz jest dzielony na bloki, a w przypadku wszystkich pikseli w bloku jest używany ten sam tryb przekształcenia. Dla: w każdym bloku są trzy rodzaje elementów przekształcania kolorów.

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

Rzeczywista transformacja koloru jest wykonywana przez zdefiniowanie delty transformacji koloru. Wartość delta transformacji koloru zależy od wartości ColorTransformElement, która jest taka sama dla wszystkich pikseli w danym bloku. Delta jest odejmowana podczas transformacji kolorów. Odwrotne przekształcenie kolorów dodaje tylko te delta.

Funkcja przekształcenia koloru jest zdefiniowana w ten sposób:

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

Wartość ColorTransformDelta jest obliczana z użyciem 8-bitowej liczby całkowitej ze znakiem, która reprezentuje Stały, 3,5-punktowy numer i 8-bitowy kanał kolorów RGB (c) [-128..127] i jest zdefiniowany w ten sposób:

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

Konwersja z 8-bitowej reprezentacji bez znaku (uint8) na 8-bitową reprezentację ze znakiem Przed wywołaniem funkcji ColorTransformDelta() wymagana jest wartość 1 (int8). Wartość ze znakiem powinna być interpretowana jako 8-bitowa liczba uzupełniająca dwóch (czyli zakres uint8) [128..255] jest mapowany na zakres [-128..-1] swojej przekonwertowanej wartości int8).

Mnożenie musi być wykonywane z większą dokładnością (co najmniej 16-bitową). Właściwość rozszerzenia znaku w operacji przesunięcia nie ma znaczenia tutaj; z wyniku używane jest tylko 8 najniższych 8 bitów, a w tych bitach tag przesunięcia rozszerzenia znaku i niepodpisanego przesuwania są ze sobą spójne.

Teraz opisujemy zawartość danych transformacji kolorów, aby dekodowanie mogło zastosować odwrotną transformację kolorów i odzyskać oryginalne wartości czerwonego i niebieskiego. Pierwsze 3 bity danych transformacji kolorów zawierają szerokość i wysokość bloku obrazu w liczbie bitów, tak jak w transformacji predyktora:

int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;

Pozostała część danych przekształcenia koloru zawiera: ColorTransformElement odpowiadające poszczególnym blokom obrazu. Każdy element ColorTransformElement 'cte' jest traktowany jako piksel obrazu o niższej rozdzielczości, którego komponent alfa ma wartość 255, komponent czerwony – cte.red_to_blue, komponent zielony – cte.green_to_blue, a komponent niebieski – cte.green_to_red.

Podczas dekodowania dekodowane są ColorTransformElement instancje bloków, a odwrotna transformacja kolorów jest stosowana do wartości ARGB pikseli. Jak wspomnieliśmy wcześniej, ta odwrotna transformacja kolorów polega tylko na dodawaniu wartości ColorTransformElement do kanałów czerwonego i niebieskiego. Alfa i zielony Kanały pozostają bez zmian.

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 Odejmowanie zielonego przekształcenia

Transformacja odejmowania zielonego odejmuje wartości zielonego od wartości czerwonego i niebieskiego każdego piksela. Gdy to przekształcenie jest obecne, dekoder musi dodać wartość zielona do wartości czerwonej i niebieskiej. Z tą transformacją nie są powiązane żadne dane. Dekoder stosuje odwrotną transformację w ten sposób:

void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
  *red  = (*red  + green) & 0xff;
  *blue = (*blue + green) & 0xff;
}

To przekształcenie jest zbędne, ponieważ można je modelować za pomocą przekształcenia koloru, ale ponieważ nie ma tu żadnych dodatkowych danych, można zakodować odjęcie zielonego za pomocą mniejszej liczby bitów niż w przypadku pełnego przekształcenia koloru.

4.4 Transformacja indeksowania kolorów

Jeśli unikalnych wartości pikseli jest niewiele, może być bardziej wydajne utworzenie tablicy indeksów kolorów i zastąpienie wartości pikseli indeksami tablicy. Kolor jest to możliwe dzięki przekształceniu indeksowania. (W kontekście technologii WebP bezstratnej nie nazywaj tego przekształceniem palety, ponieważ podobny, ale bardziej w kodowaniu bezstratnym WebP można zastosować pojęcie dynamicznego: pamięć podręczna kolorów).

Transformacja indeksowania kolorów sprawdza liczbę unikalnych wartości ARGB w obrazie. Jeśli liczba jest poniżej progu (256), tworzy tablicę tych wartości ARGB, która jest następnie używana do zastąpienia wartości pikseli odpowiednim indeksem: zielony kanał pikseli jest zastępowany indeksem, wszystkie wartości alfa są ustawiane na 255, a wszystkie wartości czerwonego i niebieskiego na 0.

Dane przekształcenia zawierają rozmiar tabeli kolorów i wpisy w kolorze tabeli. Dekoder odczytuje dane transformacji indeksowania kolorów w ten sposób:

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

Tabela kolorów jest przechowywana w ramach formatu przechowywania obrazu. Tabela kolorów można uzyskać, odczytując obraz bez nagłówka RIFF, rozmiaru przekształca, przyjmując wysokość 1 piksela i szerokość color_table_size. Tabela kolorów jest zawsze kodowana odejmowaniem, aby zmniejszyć entropię obrazu. Delty kolorów palety mają zwykle znacznie mniejszą entropię niż kolory się, co znacznie oszczędza mniejsze obrazy. Przy dekodowaniu każdy końcowy kolor w tabeli kolorów można uzyskać, dodając poprzedni kolor wartości składowych koloru przez każdy komponent ARGB oddzielnie i z przechowywaniem najmniejszych wartości 8 bitów wyniku.

Odwrotne przekształcenie obrazu polega na zastąpieniu wartości pikseli (co to indeksy do tabeli kolorów) z rzeczywistymi wartościami z tabeli kolorów. Indeksowanie odbywa się na podstawie zielonego składnika koloru ARGB.

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

Jeśli indeks jest równy lub większy od color_table_size, wartość koloru albo powinna mieć wartość 0x00000000 (przezroczysta czerń).

Jeśli tabela kolorów jest mała (maksymalnie 16 kolorów lub mniej), kilka pikseli są połączone w jeden piksel. Pakowanie pikseli polega na łączeniu kilku (2, 4 lub 8) pikseli w jeden piksel, co zmniejsza szerokość obrazu. Pikselowy łączenie w grupy pozwala na bardziej efektywne wspólne kodowanie entropii rozkładu i przylegają do siebie piksele, co przydaje się w przypadku kodowania arytmetycznego. , ale można go użyć tylko wtedy, gdy liczba niepowtarzalnych wartości jest nie większa niż 16.

color_table_size określa, ile pikseli jest łączonych:

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 może mieć wartość 0, 1, 2 lub 3. Wartość 0 oznacza brak piksela dla obrazu. Wartość 1 oznacza, że 2 piksele są łącznie, a każdy piksel ma zakres [0..15]. Wartość 2 oznacza, że przy czym każdy piksel ma zakres [0..3]. Wartość 3 wskazuje, że 8 pikseli jest połączonych, a każdy z nich ma zakres [0..1], czyli wartość binarną.

Wartości są umieszczane w zielonym komponencie w ten sposób:

• width_bits = 1: dla każdej wartości x, gdzie x Љ 0 (mod 2), oznacza kolor zielony jest umieszczona w 4 najmniej istotnych bitach parametru wartości zielonej w miejscu x / 2, a zielona wartość x + 1 4 najważniejsze bity wartości zielonej w miejscu x / 2.
• width_bits = 2: dla każdej wartości x, gdzie x OFFER 0 (mod 4), zielony pod względem x jest umieszczona w 2 najmniej istotnych bitach parametru zielone wartości x / 4, a zielone od x + 1 do x + 3 są umiejscowione w do ważniejszych bitów wartości zielonej w x / 4.
• width_bits = 3: dla każdej wartości x, gdzie x Љ 0 (mod 8), oznacza kolor zielony znajduje się przy najmniejszym istotnym bitzie zielonego x / 8, a zielone wartości od x + 1 do x + 7 są ułożone w kolejności do ważniejszych bitów wartości zielonej w x / 8.

Po odczytaniu tej transformacji image_width jest próbkowany z wysokośći width_bits. To wpływa na rozmiar kolejnych przekształceń. Nowy rozmiar można obliczyć za pomocą parametru DIV_ROUND_UP, zdefiniowanego wcześniej.

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

5. Dane obrazu

Dane obrazu to tablica wartości pikseli w kolejności wierszy skanowania.

5.1 Rola danych obrazu

Danych obrazów używamy w ramach 5 różnych ról:

1. Obraz ARGB: przechowuje rzeczywiste piksele obrazu.
2. Obraz entropii: przechowuje kody prefiksów meta (patrz „Odkodowanie kodów prefiksów meta”).
3. Obraz predyktora: przechowuje metadane transformacji predyktora (patrz „Transformacja predyktora”).
4. Obraz przekształcenia koloru: utworzony przez wartość ColorTransformElement (zdefiniowany w funkcji „Przekształcenie kolorów”) dla różnych brył obrazu.
5. Obraz indeksowania kolorów: tablica o rozmiarze color_table_size (maksymalnie 256 ARGB), w którym są przechowywane metadane do przekształcenia indeksowania kolorów (patrz: „Przekształcenie indeksowania kolorów”).

5.2 Kodowanie danych obrazu

Kodowanie danych obrazu jest niezależne od jego roli.

Najpierw obraz dzieli się na zestaw bloków o stałym rozmiarze (zazwyczaj 16 x 16). Każdy z tych bloków jest modelowany za pomocą własnych kodów entropii. Oprócz tego: kilka bloków może mieć ten sam kod entropii.

Uzasadnienie: przechowywanie kodu entropii wiąże się z kosztami. Koszt ten można zminimalizować jeśli statystycznie podobne bloki mają wspólny kod entropii, przez co ten kod jest przechowywany tylko raz. Koder może na przykład znaleźć podobne bloki przez grupowanie ich za pomocą ich właściwości statystycznych lub przez wielokrotne łączenie pary losowych cząsteczek wybranych klastrów, gdy zmniejsza to łączną liczbę bitów niezbędnych do zakodowania zdjęcia.

Każdy piksel jest kodowany za pomocą jednej z 3 możliwych metod:

1. Literaly z zakodowanym prefiksem: każdy kanał (zielony, czerwony, niebieski i alfa) jest kodowany entropijnie niezależnie.
2. Odwołania wsteczne LZ77: sekwencja pikseli zostaje skopiowana z innego miejsca na obrazie.
3. Kod pamięci podręcznej kolorów: krótki kod haszujący mnożnikowy (indeks pamięci podręcznej kolorów) ostatnio widzianego koloru.

W następnych podrozdziałach znajdziesz szczegółowe informacje na ich temat.

5.2.1 Literaly z zakodowanym prefiksem

Piksel jest przechowywany jako wartości zakodowane za pomocą prefiksów: zielony, czerwony, niebieski i alfa (w tej kolejności). Szczegółowe informacje znajdziesz w sekcji 6.2.3.

5.2.2 Odwołania wsteczne LZ77

Odwołania wsteczne to krotki określające długość i kod odległości:

• Wartość wskazuje, ile pikseli w kolejności wierszy skanowania ma zostać skopiowane.
• Kod odległości to liczba wskazująca pozycję wcześniej widzianego piksela, z którego mają być kopiowane piksele. Dokładne mapowanie opisane poniżej.

Wartości długości i odległości są przechowywane za pomocą kodowania z prefiksem LZ77.

Kodowanie z prefiksem LZ77 dzieli duże liczby całkowite na 2 części: prefiks kod i dodatkowe bity. Kod prefiksu jest przechowywany za pomocą kodu entropii, a dodatkowe bity są przechowywane w niezmienionej postaci (bez kodu entropii).

Uzasadnienie: to podejście zmniejsza wymagania dotyczące miejsca na dane dla kodu entropii. Duże wartości występują zwykle rzadko, więc dodatkowe bity byłyby używane do bardzo niewielu wartości na obrazie. Takie podejście zapewnia lepszą kompresję i ogólne.

W tabeli poniżej znajdują się kody prefiksów i dodatkowe bity używane do przechowywania różnych zakresów wartości.

Pseudokod służący do uzyskania wartości (długości lub odległości) z kodu prefiksu:

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;

Wyznaczanie odległości

Jak już wspomnieliśmy, kod odległości to liczba wskazująca położenie wcześniej widzianego piksela, z którego mają być kopiowane piksele. W tym podrozdziale definiuje się mapowanie między kodem odległości a pozycją poprzedniego piksela.

Kody odległości większe niż 120 oznaczają odległość w pikselach w kolejności linii skanowania przesuniętych o 120.

Najmniejsze kody odległości [1..120] są specjalne i zarezerwowane dla sąsiedztwa bieżącego piksela. Ta okolica składa się z 120 pikseli:

• piksele znajdujące się 1–7 wierszy powyżej bieżącego piksela i do 8 kolumn w lewo lub do 7 kolumn w prawo od bieżącego piksela; [Łącznie takie piksele = 7 * (8 + 1 + 7) = 112].
• Piksel znajdujący się w tym samym wierszu co bieżący piksel i maksymalnie 8 kolumn w lewo od niego. [8 takich pikseli].

Mapowanie między kodem odległości distance_code a sąsiednim pikselem przesunięcie (xi, yi) wygląda tak:

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

Na przykład kod odległości 1 wskazuje przesunięcie wynoszące (0, 1) dla sąsiadujący piksel, czyli piksel powyżej bieżącego (piksela 0 różnica w kierunku osi X i 1 pikselowa różnica w kierunku osi Y). Podobnie kod odległości 3 wskazuje lewy górny piksel.

Dekoder może przekonwertować kod odległości distance_code na kolejność skanowania wiersza odległość dist w następujący sposób:

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

gdzie distance_map to mapowanie podane powyżej, a image_width to szerokość obrazu w pikselach.

5.2.3 Kodowanie kolorów w pamięci podręcznej

Pamięć podręczna kolorów przechowuje zestaw kolorów, które zostały ostatnio użyte na obrazie.

Uzasadnienie: dzięki temu ostatnio używane kolory mogą być nazywane niż ich emitowanie przy użyciu dwóch pozostałych metod (opisanych w 5.2.1 i 5.2.2).

Kody pamięci podręcznej kolorów są przechowywane w następujący sposób. Po pierwsze, mamy 1-bitową wartość, wskazuje, czy używana jest pamięć podręczna kolorów. Jeśli ten bit ma wartość 0, kody pamięci podręcznej kolorów nie są wyświetlane. i nie są przesyłane w kodzie prefiksu, który dekoduje zielony symboli i kodów długości. Jeśli jednak ten bit ma wartość 1, rozmiar pamięci podręcznej kolorów jest odczytywany w kolejności:

int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;

color_cache_code_bits określa rozmiar pamięci podręcznej kolorów (1 << color_cache_code_bits). Zakres dozwolonych wartości dla color_cache_code_bits to [1..11]. Zgodne dekodery muszą wskazywać uszkodzonego strumienia bitowego dla innych wartości.

Pamięć podręczna kolorów to tablica o rozmiarze color_cache_size. Każdy wpis przechowuje jeden kolor ARGB. Kolory są wyszukiwane przez indeksowanie według (0x1e35a7bd * color) >> (32 - color_cache_code_bits). W pamięci podręcznej kolorów wykonywane jest tylko jedno wyszukiwanie; nie ma rozwiązywanie konfliktów.

Na początku dekodowania lub kodowania obrazu wszystkie wartości w wszystkich wartościach koloru w pamięci podręcznej są ustawione na zero. Kod koloru pamięci podręcznej jest konwertowany na ten kolor w momencie dekodowania. Stan pamięci podręcznej kolorów jest utrzymywany przez wstawianie do pamięci podręcznej każdego piksela, niezależnie od tego, czy jest on generowany przez odwołanie wsteczne, czy jako literał, w kolejności, w jakiej pojawia się w strumieniu.

6 kodów entropii

6.1 Omówienie

Większość danych jest kodowana z wykorzystaniem kanonicznego kodu prefiksu. Dlatego kody są przesyłane przez wysłanie długości prefiksów kodu, a nie samych prefiksów kodu.

W szczególności format wykorzystuje kodowanie z prefiksem wariantu przestrzennego. Innymi słowy, różne bloki obrazu mogą potencjalnie używać różnych kodów entropii.

Uzasadnienie: różne obszary obrazu mogą mieć różne cechy. Zezwolenie im więc na stosowanie różnych kodów entropii zapewnia większą elastyczność i potencjalnie lepszą kompresję.

6.2 Szczegóły

Zakodowane dane obrazu składają się z kilku części:

1. dekodowanie i tworzenie kodów prefiksów;
2. Kody prefiksów meta.
3. Dane obrazu zakodowane entropijnie.

W przypadku dowolnego piksela (x, y) jest zestaw 5 kodów prefiksów. Są to następujące kody (w kolejności bitów strumieniowych):

• Kod prefiksu 1: używany w przypadku kanału zielonego, długości odwołania wstecznego i pamięci podręcznej kolorów.
• Kod prefiksu 2, #3 i 4: używany w przypadku kanałów czerwonego, niebieskiego i alfa, .
• Kod prefiksu 5: służy do określania odległości wstecznej.

Od tego momentu ten zestaw nazywamy grupą kodu prefiksu.

6.2.1 Dekodowanie i tworzenie kodów prefiksów

W tej sekcji opisano, jak odczytać długości kodów prefiksów z strumienia bitów.

Długości kodów prefiksów mogą być kodowane na dwa sposoby. Używana metoda jest określona za pomocą wartości 1-bitowej.

• Jeśli ten bit ma wartość 1, oznacza to, że jest to prosty kod długości kodu.
• Jeśli ten bit ma wartość 0, jest to kod o normalnej długości kodu.

W obu przypadkach mogą istnieć nieużywane długości kodu, które nadal są częścią tagu . Może to być nieskuteczne, ale format dozwolony ze względu na ten format. Opisane drzewo musi być kompletnym drzewem binarnym. Jeden węzeł liścia to uważane za kompletne drzewo binarne i można je zakodować za pomocą prostego lub zwykłej długości kodu. Przy kodowaniu pojedynczego liścia przy użyciu kodu o normalnej długości kodu, ale tylko jednej długości kodu liczone są zera, a wartość węzła pojedynczego liścia jest oznaczona długością równą 1 – nawet jeśli nie zużywane są bity, gdy używane jest to jednoliściowe drzewo węzła.

Prosty kod długości

Ten wariant jest używany w przypadku szczególnym, gdy w zakresie [0..255] z długością kodu 1 występuje tylko 1 lub 2 symbole prefiksu. Wszystkie inne długości prefiksów są domyślnie zerami.

Pierwszy bit określa liczbę symboli:

int num_symbols = ReadBits(1) + 1;

Poniżej podano wartości symboli.

Pierwszy symbol jest zakodowany za pomocą 1 lub 8 bitów, w zależności od wartości is_first_8bits Zakres to odpowiednio [0..1] lub [0..255]. Drugi symbol, jeśli występuje, jest zawsze zdefiniowany w zakresie [0..255] i zakodowany za pomocą 8 bitów.

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

Te 2 symbole powinny być różne. Symbole mogą się powtarzać, ale nieefektywne.

Uwaga: innym szczególnym przypadkiem jest sytuacja, gdy wszystkie długości prefiksów kodu są równe 0 (pusty prefiks kodu). Na przykład kod prefiksu odległości może być pusty, jeśli nie ma odniesień wstecznych. Podobnie kody prefiksów dla alfa, czerwieni i niebieskiego mogą być puste, jeśli wszystkie piksele w ramach tego samego kodu meta prefiksu są tworzone za pomocą pamięci podręcznej kolorów. W tym przypadku nie trzeba się nią zajmować, bo puste kody prefiksów mogą być kodowane jako zawierające pojedynczy symbol 0.

Kod o normalnej długości

Długość kodu prefiksu mieści się w 8 bitach i jest odczytywana w ten sposób: Po pierwsze, num_code_lengths określa liczbę długości kodu.

int num_code_lengths = 4 + ReadBits(4);

Długości kodów są kodowane za pomocą kodów prefiksów. Najpierw muszą zostać odczytane długości kodów na niższym poziomie, code_length_code_lengths. Pozostałe code_length_code_lengths (zgodnie z zamówieniem w kCodeLengthCodeOrder) wynosi zero.

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

Następnie, jeśli ReadBits(1) == 0, maksymalna liczba różnych odczytanych symboli (max_symbol) dla każdego typu symbolu (A, R, G, B i odległość) jest ustawiona na rozmiar alfabetu:

• Kanał G: 256 + 24 + color_cache_size
• Inne wartości dosłowne (A, R i B): 256
• Kod odległości: 40

W przeciwnym razie jest on zdefiniowany jako:

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

Jeśli max_symbol jest większa niż rozmiar alfabetu dla typu symbolu, bitstream jest nieprawidłowy.

Następnie na podstawie code_length_code_lengths jest tworzona tabela prefiksów i używana do odczytu do max_symbol długości kodu.

• Kod [0..15] wskazuje dosłowną długość kodu.
  • Wartość 0 oznacza, że nie zakodowano żadnych symboli.
  • Wartości [1..15] wskazują liczbę bitów odpowiedniego kodu.
• Kod 16 powtarza poprzednią wartość niezerową [3..6] razy, czyli 3 + ReadBits(2) razy. Jeśli kod 16 jest używany przed wartością inną niż 0 została wysłana wartość 8, powtórzona.
• Kod 17 emituje ciąg zer o długości [3..10], czyli 3 + ReadBits(3) razy.
• Kod 18 tworzy serię zer o długości [11..138], czyli 11 + ReadBits(7) razy.

Po odczytaniu długości kodu prefiks dla każdego typu symboli (A, R, G, B, odległość) powstaje przy użyciu odpowiednich rozmiarów alfabetu.

Kod normalnej długości kodu musi zakodować pełne drzewo decyzyjne, czyli sumę 2 ^ (-length) w przypadku wszystkich kodów innych niż 0 musi mieć dokładnie 1. Jest jednak jeden wyjątek od tej reguły: drzewo z jednym węzłem liściastym, w którym wartość węzła liściastego jest oznaczona wartością 1, a inne wartości – wartościami 0.

6.2.2 Dekodowanie kodów prefiksów meta

Jak już wspomnieliśmy, format pozwala na używanie różnych kodów prefiksów różne bloki obrazu. Kody prefiksów meta to indeksy określające, których kodów prefiksów należy używać w różnych częściach obrazu.

Kodów metaprefiksów można używać tylko wtedy, gdy obraz jest używany w role obrazu ARGB.

Metaprefiksy mogą mieć 2 możliwości (1-bitowe) wartość:

• Jeśli ten bit ma wartość zero, wszędzie w argumencie jest używany tylko jeden kod prefiksu meta zdjęcia. Nie są już przechowywane żadne dane.
• Jeśli ten bit ma wartość 1, obraz używa wielu kodów prefiksów meta. Te metakody prefiksów są przechowywane jako obraz entropii (opisany poniżej).

Czerwony i zielony składnik piksela definiują 16-bitowy kod prefiksu meta używany w określonym bloku obrazu ARGB.

Entropia obrazu

Obraz entropii określa, które kody prefiksów są używane w różnych częściach kodu .

Pierwsze 3 bity zawierają wartość prefix_bits. Wymiary entropii obrazu są uzyskiwane na podstawie prefix_bits:

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

gdzie DIV_ROUND_UP jest określone wcześniej.

Kolejne bity zawierają obraz entropii o szerokości prefix_image_width i wysokości prefix_image_height.

Interpretacja kodów prefiksów meta

Liczba grup prefiksów kodu w pliku ARGB może zostać uzyskana przez znalezienie największego metaprefiksu kodu w pliku entropii:

int num_prefix_groups = max(entropy image) + 1;

gdzie max(entropy image) oznacza największy kod prefiksu zapisany w obrazie entropii.

Każda grupa prefiksów zawiera 5 prefiksów, więc łączna liczba prefiksów to:

int num_prefix_codes = 5 * num_prefix_groups;

Biorąc pod uwagę piksel (x, y) na obrazie ARGB, możemy uzyskać odpowiedni prefiks należy używać w następujący sposób:

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

w którym zakładamy, że ma strukturę PrefixCodeGroup, która reprezentuje zestaw pięciu kodów prefiksów. Ponadto prefix_code_groups to tablica PrefixCodeGroup (o rozmiarze num_prefix_groups).

Dekoder używa następnie grupy kodów prefiksu prefix_group do dekodowania piksela (x, y), jak wyjaśniono w części „Dekodowanie obrazu zakodowanego entropią Dane”.

6.2.3 Dekodowanie danych obrazu zakodowanego entropijnie

W przypadku bieżącej pozycji (x, y) na obrazie dekoder najpierw identyfikuje odpowiednią grupę kodu prefiksu (jak opisano w poprzedniej sekcji). W zależności od grupy kodu prefiksu piksel jest odczytywany i dekodowany w ten sposób:

Następnie odczytaj symbol S ze strumienia bitowego przy użyciu kodu prefiksu nr 1. Pamiętaj, że S to dowolna liczba całkowita z zakresu 0–(256 + 24 + color_cache_size- 1).

Interpretacja S zależy od jego wartości:

1. Jeśli S < 256
   1. Jako komponent zielony użyj S.
   2. Odczytaj dane ze strumienia bitowego na czerwono przy użyciu kodu prefiksu nr 2.
   3. Odczytaj niebieski kolor z bitstremułu za pomocą kodu prefiksu #3.
   4. Odczytaj wersję alfa ze strumienia bitowego przy użyciu kodu prefiksu 4.
2. Jeśli S >= 256 & Nd < 256 + 24
   1. Jako kodu prefiksu długości użyj kodu S-256.
   2. odczytaj dodatkowe bity długości z bitowego strumienia danych;
   3. Określ długość odwołania wstecznego L na podstawie kodu prefiksu długości i dodatkowych odczytanych bitów.
   4. Odczytaj kod prefiksu odległości z bitowego strumienia za pomocą kodu prefiksu 5.
   5. odczytaj dodatkowe bity, aby określić odległość od bitowego strumienia danych.
   6. Określ odległość D od poprzedniego odwołania na podstawie kodu prefiksu odległości i dodatkowych odczytanych bitów.
   7. Skopiuj L pikseli (w kolejności linii skanowania) z sekwencji pikseli zaczynając od bieżącej pozycji pomniejszonej o D pikseli.
3. Jeśli S >= 256 + 24
   1. Użyj znaków S- (256 + 24) jako indeksu w pamięci podręcznej kolorów.
   2. Pobierz kolor ARGB z pamięci podręcznej kolorów pod tym indeksem.

7 Ogólna struktura formatu

Poniżej znajduje się omówienie formatu w rozszerzonej notacji Backusa-Naura (ABNF) RFC 5234 RFC 7405. Nie obejmuje on wszystkich szczegółów. Koniec obrazu (EOI) jest zakodowany tylko pośrednio w liczbie pikseli (image_width * image_height).

Pamiętaj, że *element oznacza, że element element może się powtarzać 0 lub więcej razy. 5element oznacza, że element element jest powtórzony dokładnie 5 razy. %b reprezentuje wartość binarną.

7.1 Podstawowa struktura

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 Struktura transformacji

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 Struktura danych zdjęć

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)

Oto przykładowa sekwencja:

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