Specyfikacja bezstratnego strumienia bitowego WebP

Jyrki Alakuijala, Ph.D., Google, Inc., 2023-03-09

Streszczenie

WebP bezstratny to format obrazu do bezstratnej kompresji obrazów ARGB. Format bezstratny przechowuje i przywraca wartości pikseli, w tym wartości kolorów w przypadku całkowicie przezroczystych pikseli. Do kompresji danych zbiorczych używany jest uniwersalny algorytm kompresji danych sekwencyjnych (LZ77), kodowanie prefiksowe i pamięć podręczna kolorów. Wykazano, że szybkość dekodowania jest większa niż w przypadku formatu PNG, a kompresja jest o 25% większa niż w przypadku obecnego formatu PNG.

1 Wprowadzenie

Ten dokument opisuje skompresowaną reprezentację danych obrazu WebP bez utraty jakości. Jest to szczegółowy opis implementacji bezstratnego kodera i dekodera WebP.

W tym dokumencie do opisu strumienia bitów używamy w dużej mierze składni języka programowania C i zakładamy istnienie funkcji do odczytywania bitów, ReadBits(n). Bajty są odczytywane w naturalnej kolejności strumienia, w którym się znajdują, a bity każdego bajtu są odczytywane w kolejności od najmniej znaczącego do najbardziej znaczącego. Jeśli odczytanych zostanie kilka bitów jednocześnie, liczba całkowita zostanie utworzona z oryginalnych danych w pierwotnej kolejności. Najważniejsze bity zwróconej liczby całkowitej są też najważniejszymi bitami oryginalnych danych. W związku z tym

b = ReadBits(2);

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

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

Zakładamy, że każdy składnik 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 o nazwie uint32, który jest liczbą całkowitą bez znaku składającą się z 32 bitów. W kodzie pokazującym działanie przekształceń te wartości są zakodowane 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ą wewnętrznie używać innej reprezentacji.

Obraz bezstratny WebP zawiera dane nagłówka, informacje o przekształceniach i rzeczywiste dane obrazu. Nagłówki zawierają szerokość i wysokość obrazu. Obraz bezstratny WebP może przejść 4 rodzaje przekształceń, zanim zostanie zakodowany entropijnie. Informacje o przekształceniu w strumieniu bitów zawierają dane wymagane do zastosowania odpowiednich przekształceń odwrotnych.

2 Nomenklatura

ARGB

Wartość piksela składająca się z wartości alfa, czerwonej, zielonej i niebieskiej.

Obraz ARGB

Dwuwymiarowa tablica zawierająca piksele ARGB.

pamięć podręczna kolorów,

Mała tablica adresowana za pomocą funkcji skrótu do przechowywania ostatnio używanych kolorów, aby można było je przywoływać za pomocą krótszych kodów.

obraz z indeksowaniem kolorów,

Jednowymiarowy obraz kolorów, który można indeksować za pomocą małej liczby całkowitej (do 256 w przypadku bezstratnej kompresji WebP).

przekształcanie obrazu pod kątem koloru,

Dwuwymiarowy obraz o niższej rozdzielczości zawierający dane o korelacji składników koloru.

mapowanie odległości,

Zmienia odległości LZ77, aby uzyskać najmniejsze wartości pikseli w dwuwymiarowej bliskości.

obraz entropii

Dwuwymiarowy obraz o niższej rozdzielczości wskazujący, które kodowanie entropijne powinno być używane w odpowiednim kwadracie na obrazie, tzn. każdy piksel jest kodem metaprefiksu.

LZ77

Algorytm kompresji oparty na słowniku, który wykorzystuje okno przesuwne i emituje symbole lub opisuje je jako sekwencje poprzednich symboli.

kod prefiksu meta

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

obraz predyktora

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

kod prefiksu,

Klasyczny sposób kodowania entropijnego, w którym do częstszych kodów używa się mniejszej liczby bitów.

kodowanie prefiksowe,

Metoda kodowania entropijnego większych liczb całkowitych, która koduje kilka bitów liczby całkowitej za pomocą kodowania entropijnego, a pozostałe bity koduje w formie surowej. Dzięki temu opisy kodów entropii mogą pozostać stosunkowo małe nawet wtedy, gdy zakres symboli jest duży.

kolejność linii skanowania,

Kolejność przetwarzania pikseli (od lewej do prawej i z góry na dół), zaczynając od lewego górnego piksela. Po ukończeniu wiersza przejdź do lewej kolumny następnego wiersza.

3 Nagłówek RIFF

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

1. Ciąg znaków „RIFF”.
2. Wartość 32-bitowa w formacie little-endian określająca długość fragmentu, czyli jego całkowity rozmiar kontrolowany przez nagłówek RIFF. Zwykle jest to równe rozmiarowi ładunku (rozmiar pliku minus 8 bajtów: 4 bajty na identyfikator „RIFF” i 4 bajty na przechowywanie samej wartości).
3. Ciąg znaków „WEBP” (nazwa kontenera RIFF).
4. Ciąg znaków „VP8L” (FourCC dla danych obrazu zakodowanych bezstratnie).
5. 32-bitowa wartość little-endian określająca liczbę bajtów w strumieniu bezstratnym.
6. 1-bajtowy podpis 0x2f.

Pierwsze 28 bitów strumienia bitów określa szerokość i wysokość obrazu. Szerokość i wysokość są dekodowane jako 14-bitowe liczby całkowite 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 obrazu WebP bez utraty jakości do 16384 × 16384 pikseli.

Bit alpha_is_used jest tylko wskazówką i nie powinien mieć wpływu na dekodowanie. Jeśli wszystkie wartości alfa na obrazie wynoszą 255, powinna być ustawiona na 0, a w pozostałych przypadkach na 1.

int alpha_is_used = ReadBits(1);

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

int version_number = ReadBits(3);

4 przekształcenia

Przekształcenia to odwracalne manipulacje danymi obrazu, które mogą zmniejszyć pozostałą entropię symboliczną poprzez modelowanie korelacji przestrzennych i kolorystycznych. Mogą one zwiększyć stopień kompresji.

Obraz może przejść 4 rodzaje przekształceń. Wartość 1 bit oznacza obecność przekształcenia. Każdej transformacji można użyć tylko raz. Przekształcenia są używane tylko w przypadku obrazu ARGB głównego poziomu. Obrazy o niższej rozdzielczości (obraz przekształcenia kolorów, obraz entropii i obraz predyktora) nie mają przekształceń, nawet 0-bitowego wskaźnika końca przekształceń.

Zwykle koder używa tych przekształceń, aby zmniejszyć entropię Shannona w obrazie resztkowym. Dane przekształcone można też określić 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 przekształcenie jest obecne, kolejne 2 bity określają jego typ. Istnieją 4 rodzaje przekształceń.

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

Po typie przekształcenia następują dane przekształcenia. Transform data zawiera informacje wymagane do zastosowania transformacji odwrotnej i zależy od typu transformacji. Przekształcenia odwrotne są stosowane w odwrotnej kolejności, w jakiej są odczytywane ze strumienia bitów, czyli ostatnie jako pierwsze.

Następnie opisujemy przekształcanie danych różnych typów.

4.1 Przekształcenie predyktora

Transformacja predykcyjna może służyć do zmniejszania entropii poprzez wykorzystanie faktu, że sąsiednie piksele są często skorelowane. W transformacji predykcyjnej bieżąca wartość piksela jest przewidywana na podstawie pikseli, które zostały już zdekodowane (w kolejności linii skanowania), a kodowana jest tylko wartość resztkowa (rzeczywista – przewidywana). Zielony komponent piksela określa, który z 14 predyktorów jest używany w danym bloku obrazu ARGB. Tryb prognozowania określa typ prognozy, która ma być używana. Dzielimy obraz na kwadraty, a wszystkie piksele w kwadracie korzystają z tego samego trybu prognozowania.

Pierwsze 3 bity danych prognozy określają szerokość i wysokość bloku w bitach.

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 przekształcenia zawierają tryb prognozowania dla każdego bloku obrazu. Jest to obraz o niższej rozdzielczości, w którym zielony komponent piksela określa, który z 14 predyktorów jest używany dla wszystkich pikseli block_width * block_height w danym bloku obrazu ARGB. Obraz o niższej rozdzielczości jest kodowany przy użyciu tych samych technik, które opisano w rozdziale 5.

Liczba kolumn bloków, transform_width, jest używana w indeksowaniu dwuwymiarowym. W przypadku piksela (x, y) adres odpowiedniego bloku filtra można obliczyć w ten sposób:

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

Dostępnych jest 14 różnych trybów prognozowania. W każdym trybie prognozowania bieżąca wartość piksela jest prognozowana 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) w ten sposób:

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. W momencie przewidywania wartości dla piksela P wszystkie piksele O, TL, T, TR i L są już przetworzone, a piksel P i wszystkie piksele X są nieznane.

Biorąc pod uwagę sąsiednie piksele, różne tryby prognozowania są zdefiniowane w ten sposób:

W przypadku każdego komponentu ARGB wartość Average2 jest definiowana w ten sposób:

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

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

Funkcje ClampAddSubtractFull i ClampAddSubtractHalf są wykonywane w przypadku 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 granicznych obowiązują specjalne zasady obsługi. Jeśli istnieje transformacja predyktora, niezależnie od trybu [0..13] dla tych pikseli, przewidywana wartość dla lewego górnego piksela obrazu to 0xff000000, wszystkie piksele w górnym wierszu to piksele L, a wszystkie piksele w lewej kolumnie to piksele T.

Adresowanie piksela TR w przypadku pikseli w kolumnie najbardziej z prawej strony jest wyjątkowe. Piksele w kolumnie po prawej stronie są przewidywane przy użyciu trybów [0..13], tak samo jak piksele nieznajdujące się na krawędzi, ale jako piksel TR używany jest piksel po lewej stronie w tym samym wierszu co bieżący piksel.

Końcowa wartość piksela jest uzyskiwana przez dodanie każdego kanału przewidywanej wartości 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 usunięcie korelacji między wartościami R, G i B każdego piksela. Transformacja kolorów zachowuje wartość zielonego (G), przekształca wartość czerwonego (R) na podstawie wartości zielonego, a wartość niebieskiego (B) na podstawie wartości zielonego, a następnie czerwonego.

Podobnie jak w przypadku transformacji predykcyjnej obraz jest najpierw dzielony na bloki, a ten sam tryb transformacji jest używany dla wszystkich pikseli w bloku. W przypadku każdego bloku są 3 rodzaje elementów przekształcania kolorów.

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

Rzeczywiste przekształcenie kolorów odbywa się przez zdefiniowanie delty przekształcenia kolorów. Wartość delta transformacji kolorów zależy od parametru ColorTransformElement, który jest taki sam dla wszystkich pikseli w danym bloku. Wartość delta jest odejmowana podczas transformacji kolorów. Odwrócona transformacja kolorów polega na dodaniu tych różnic.

Funkcja przekształcania kolorów 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;
}

ColorTransformDelta jest obliczany przy użyciu 8-bitowej liczby całkowitej ze znakiem reprezentującej liczbę stałoprzecinkową 3,5 i 8-bitowego kanału koloru RGB ze znakiem (c) [-128..127] i jest zdefiniowany w ten sposób:

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

Przed wywołaniem funkcji ColorTransformDelta() wymagana jest konwersja z 8-bitowej reprezentacji bez znaku (uint8) na 8-bitową reprezentację ze znakiem (int8). Wartość ze znakiem należy interpretować jako 8-bitową liczbę w systemie uzupełnień do dwóch (czyli zakres uint8 [128..255] jest mapowany na zakres [-128..-1] przekonwertowanej wartości int8).

Mnożenie należy wykonać z większą precyzją (co najmniej 16-bitową). Własność rozszerzenia znaku operacji przesunięcia nie ma tu znaczenia. Z wyniku używane są tylko 8 najmniej znaczących bitów, a w tych bitach przesunięcie z rozszerzeniem znaku i przesunięcie bez znaku są zgodne.

Teraz opisujemy zawartość danych transformacji kolorów, aby dekodowanie mogło zastosować odwrotną transformację kolorów i przywrócić oryginalne wartości czerwieni i błękitu. Pierwsze 3 bity danych transformacji koloru zawierają szerokość i wysokość bloku obrazu w bitach, podobnie jak transformacja predyktora:

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

Pozostała część danych transformacji kolorów zawiera ColorTransformElement instancji odpowiadających poszczególnym blokom obrazu. Każdy element ColorTransformElement 'cte' jest traktowany jako piksel w obrazie o niższej rozdzielczości, którego komponent alfa to 255, komponent czerwony to cte.red_to_blue, komponent zielony to cte.green_to_blue, a komponent niebieski to cte.green_to_red.

Podczas dekodowania dekodowane są ColorTransformElement wystąpienia bloków i na wartości ARGB pikseli stosowana jest odwrotna transformacja kolorów. Jak wspomnieliśmy wcześniej, ta odwrotna transformacja kolorów polega na dodaniu wartości ColorTransformElement do kanałów czerwonego i niebieskiego. Kanały alfa i zielony 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 Odejmij przekształcenie zieleni

Przekształcenie „Odejmij zielony” odejmuje wartości zieleni od wartości czerwieni i niebieskiego każdego piksela. Gdy to przekształcenie jest obecne, dekoder musi dodać wartość koloru zielonego do wartości koloru czerwonego i niebieskiego. Z tą transformacją nie są powiązane żadne dane. Dekoder stosuje transformację odwrotną w ten sposób:

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

Ta transformacja jest zbędna, ponieważ można ją modelować za pomocą transformacji koloru, ale ponieważ nie ma tu dodatkowych danych, transformację odejmowania zieleni można zakodować przy użyciu mniejszej liczby bitów niż pełną transformację koloru.

4.4 Transformacja indeksowania kolorów

Jeśli nie ma wielu unikalnych wartości pikseli, bardziej efektywne może być utworzenie tablicy indeksu kolorów i zastąpienie wartości pikseli indeksami tablicy. Możesz to osiągnąć za pomocą przekształcenia indeksowania kolorów. (W kontekście bezstratnej kompresji WebP nie nazywamy tego przekształceniem palety, ponieważ w bezstratnym kodowaniu WebP istnieje podobna, ale bardziej dynamiczna koncepcja: pamięć podręczna kolorów).

Transformacja indeksowania kolorów sprawdza liczbę unikalnych wartości ARGB w obrazie. Jeśli ta liczba jest mniejsza niż próg (256), tworzy tablicę tych wartości ARGB, która jest następnie używana do zastępowania wartości pikseli odpowiednim indeksem: kanał zielony pikseli jest zastępowany indeksem, wszystkie wartości alfa są ustawiane na 255, a wszystkie wartości czerwone i niebieskie na 0.

Przekształcone dane zawierają rozmiar tabeli kolorów i wpisy w tabeli kolorów. 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 formacie przechowywania obrazu. Tabelę kolorów można uzyskać, odczytując obraz bez nagłówka RIFF, rozmiaru obrazu i transformacji, przy założeniu, że wysokość wynosi 1 piksel, a szerokość – color_table_size. Tabela kolorów jest zawsze kodowana przez odejmowanie, aby zmniejszyć entropię obrazu. Deltowe wartości kolorów palety zawierają zwykle znacznie mniejszą entropię niż same kolory, co w przypadku mniejszych obrazów pozwala uzyskać znaczną oszczędność miejsca. Podczas dekodowania każdy kolor końcowy w tabeli kolorów można uzyskać, dodając poprzednie wartości komponentów kolorów do każdego komponentu ARGB osobno i zapisując 8 najmniej znaczących bitów wyniku.

Transformacja odwrotna w przypadku obrazu polega po prostu na zastąpieniu wartości pikseli (które są indeksami w tabeli kolorów) 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 niż color_table_size, wartość koloru ARGB powinna być ustawiona na 0x00000000 (przezroczysta czerń).

Gdy tabela kolorów jest mała (zawiera nie więcej niż 16 kolorów), kilka pikseli jest łączonych w jeden piksel. Łączenie pikseli polega na łączeniu kilku (2, 4 lub 8) pikseli w jeden, co odpowiednio zmniejsza szerokość obrazu. Łączenie pikseli umożliwia bardziej wydajne wspólne kodowanie entropijne sąsiednich pikseli i zapewnia pewne korzyści podobne do kodowania arytmetycznego, ale można go używać tylko wtedy, gdy jest 16 lub mniej unikalnych wartości.

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 ma wartość 0, 1, 2 lub 3. Wartość 0 oznacza, że w przypadku obrazu nie należy łączyć pikseli. Wartość 1 oznacza, że 2 piksele są połączone, a każdy piksel ma zakres [0..15]. Wartość 2 oznacza, że łączone są 4 piksele, a każdy piksel ma zakres [0..3]. Wartość 3 oznacza, że połączonych jest 8 pikseli, a każdy piksel ma zakres [0..1], czyli wartość binarną.

Wartości są pakowane w zielony komponent w ten sposób:

• width_bits = 1: dla każdej wartości x, gdzie x ≡ 0 (mod 2), wartość zielona w punkcie x jest umieszczana w 4 najmniej znaczących bitach wartości zielonej w punkcie x / 2, a wartość zielona w punkcie x + 1 jest umieszczana w 4 najbardziej znaczących bitach wartości zielonej w punkcie x / 2.
• width_bits = 2: dla każdej wartości x, gdzie x ≡ 0 (mod 4), wartość koloru zielonego w punkcie x jest umieszczana w 2 najmniej znaczących bitach wartości koloru zielonego w punkcie x / 4, a wartości koloru zielonego w punktach x + 1 do x + 3 są umieszczane w kolejności w bardziej znaczących bitach wartości koloru zielonego w punkcie x / 4.
• width_bits = 3: dla każdej wartości x, gdzie x ≡ 0 (mod 8), wartość zielona w punkcie x jest umieszczana w najmniej znaczącym bicie wartości zielonej w punkcie x / 8, a wartości zielone w punktach od x + 1 do x + 7 są umieszczane w kolejności w bardziej znaczących bitach wartości zielonej w punkcie x / 8.

Po zastosowaniu tej transformacji wartość image_width jest próbkowana z częstotliwością width_bits. Określa rozmiar kolejnych przekształceń. Nowy rozmiar można obliczyć za pomocą wzoru DIV_ROUND_UP, zgodnie z definicją podaną wcześniej.

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

5. Dane obrazów

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

5.1 Rola danych obrazu

Dane obrazów wykorzystujemy w 5 różnych rolach:

1. Obraz ARGB: zawiera rzeczywiste piksele obrazu.
2. Obraz entropii: przechowuje kody prefiksów meta (patrz „Dekodowanie kodów prefiksów meta”).
3. Obraz predyktora: przechowuje metadane przekształcenia predyktora (patrz „Przekształcenie predyktora”).
4. Obraz przekształcony pod względem kolorów: utworzony na podstawie wartości ColorTransformElement (zdefiniowanych w „Przekształceniu kolorów”) dla różnych bloków obrazu.
5. Obraz indeksowania kolorów: tablica o rozmiarze color_table_size (maksymalnie 256 wartości ARGB), która przechowuje metadane 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.

Obraz jest najpierw dzielony na zestaw bloków o stałym rozmiarze (zwykle 16 x 16). Każdy z tych bloków jest modelowany przy użyciu własnych kodów entropii. Poza tym kilka bloków może współdzielić te same kody entropii.

Uzasadnienie: przechowywanie kodu entropii wiąże się z kosztami. Ten koszt można zminimalizować, jeśli podobne statystycznie bloki mają wspólny kod entropii, dzięki czemu kod ten jest przechowywany tylko raz. Na przykład koder może znajdować podobne bloki, grupując je na podstawie ich właściwości statystycznych lub wielokrotnie łącząc parę losowo wybranych klastrów, gdy zmniejsza to ogólną liczbę bitów potrzebnych do zakodowania obrazu.

Każdy piksel jest kodowany jedną z 3 możliwych metod:

1. Literały z kodowaniem prefiksowym: każdy kanał (zielony, czerwony, niebieski i alfa) jest kodowany entropijnie niezależnie.
2. Odwołanie wsteczne LZ77: sekwencja pikseli jest kopiowana z innego miejsca w obrazie.
3. Kod pamięci podręcznej kolorów: używa krótkiego multiplikatywnego kodu skrótu (indeks pamięci podręcznej kolorów) ostatnio widzianego koloru.

W podsekcjach poniżej znajdziesz szczegółowe informacje o każdym z nich.

5.2.1 Literały z kodowaniem prefiksowym

Piksel jest przechowywany jako wartości zielonego, czerwonego, niebieskiego i alfa (w tej kolejności) zakodowane za pomocą kodowania prefiksowego. Szczegółowe informacje znajdziesz w sekcji 6.2.3.

5.2.2 Odwołanie wsteczne LZ77

Odwołania wsteczne to krotki składające się z długości i kodu odległości:

• Długość określa, ile pikseli w kolejności linii skanowania ma zostać skopiowanych.
• Kod odległości to liczba wskazująca pozycję wcześniej widzianego piksela, z którego mają być kopiowane piksele. Dokładne mapowanie opisano poniżej.

Wartości długości i odległości są przechowywane przy użyciu kodowania prefiksowego LZ77.

Kodowanie prefiksowe LZ77 dzieli duże wartości całkowite na 2 części: kod prefiksu i dodatkowe bity. Kod prefiksu jest przechowywany za pomocą kodu entropii, a dodatkowe bity są przechowywane w postaci, w jakiej występują (bez kodu entropii).

Uzasadnienie: to podejście zmniejsza wymagania dotyczące miejsca na dane w przypadku kodu entropii. Duże wartości są zwykle rzadkie, więc dodatkowe bity byłyby używane w przypadku bardzo niewielu wartości na obrazie. Dzięki temu podejście to zapewnia lepszą kompresję.

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

Pseudokod do uzyskania wartości (długości lub odległości) z kodu prefiksu jest następujący:

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;

Mapowanie odległości

Jak wspomnieliśmy wcześniej, kod odległości to liczba wskazująca pozycję wcześniej widzianego piksela, z którego mają być kopiowane piksele. W tym podrozdziale określono 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ętą o 120.

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

• Piksele, które znajdują się od 1 do 7 rzędów powyżej bieżącego piksela i do 8 kolumn po lewej stronie lub do 7 kolumn po prawej stronie bieżącego piksela. [Łączna liczba takich pikseli = 7 * (8 + 1 + 7) = 112].
• Piksele, które znajdują się w tym samym wierszu co bieżący piksel i są oddalone od niego o maksymalnie 8 kolumn w lewo. [8 takie piksele].

Mapowanie między kodem odległości distance_code a przesunięciem sąsiedniego piksela (xi, yi) jest następujące:

(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 oznacza przesunięcie o (0, 1) w przypadku sąsiedniego piksela, czyli piksela znajdującego się nad bieżącym pikselem (różnica 0 pikseli w kierunku X i 1 piksel w kierunku Y). Podobnie kod odległości 3 wskazuje piksel w lewym górnym rogu.

Dekoder może przekształcić kod odległości distance_code na odległość w kolejności linii skanowania dist w ten sposób:

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

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

5.2.3 Kodowanie pamięci podręcznej kolorów

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

Uzasadnienie: w ten sposób można czasami odwoływać się do ostatnio używanych kolorów bardziej efektywnie niż w przypadku dwóch pozostałych metod (opisanych w sekcjach 5.2.1 i 5.2.2).

Kody pamięci podręcznej kolorów są przechowywane w ten sposób: Najpierw jest 1-bitowa wartość, która wskazuje, czy używana jest pamięć podręczna kolorów. Jeśli ten bit ma wartość 0, nie ma kodów pamięci podręcznej kolorów i nie są one przesyłane w kodzie prefiksu, który dekoduje zielone symbole i kody prefiksu długości. Jeśli jednak ten bit ma wartość 1, odczytywana jest następna wartość: rozmiar pamięci podręcznej kolorów:

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]. Dekodery zgodne z tym standardem muszą w przypadku innych wartości wskazywać uszkodzony strumień bitów.

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

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

6 Kod entropijny

6.1 Przegląd

Większość danych jest kodowana za pomocą kanonicznego kodu prefiksowego. Dlatego kody są przesyłane przez wysyłanie długości kodów prefiksów, a nie rzeczywistych kodów prefiksów.

W szczególności format ten wykorzystuje przestrzennie zmienne kodowanie prefiksowe. 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. Umożliwienie im korzystania z 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.

Z każdym pikselem (x, y) powiązany jest zestaw 5 kodów prefiksowych. Kody te (w kolejności strumienia bitów) to:

• Kod prefiksu 1: używany w przypadku zielonego kanału, długości odniesienia wstecznego i pamięci podręcznej kolorów.
• Kody prefiksów 2, 3 i 4: używane odpowiednio w przypadku kanałów czerwonego, niebieskiego i alfa.
• Kod prefiksu 5: używany w przypadku odległości odniesienia wstecznego.

Od tej pory będziemy nazywać ten zbiór grupą kodów prefiksów.

6.2.1 Dekodowanie i tworzenie kodów prefiksowych

W tej sekcji opisujemy, jak odczytywać długości kodów prefiksów ze strumienia bitów.

Długości kodów prefiksów można kodować na 2 sposoby. Używana metoda jest określana przez 1-bitową wartość.

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

W obu przypadkach mogą występować niewykorzystane długości kodu, które nadal są częścią strumienia. Może to być nieefektywne, ale jest dozwolone w tym formacie. Opisane drzewo musi być pełnym drzewem binarnym. Pojedynczy węzeł liścia jest uważany za pełne drzewo binarne i może być kodowany za pomocą prostego lub normalnego kodu długości. Podczas kodowania pojedynczego węzła liścia za pomocą kodu o normalnej długości wszystkie długości kodu z wyjątkiem jednej są zerami, a wartość pojedynczego węzła liścia jest oznaczona długością 1 – nawet jeśli podczas używania tego pojedynczego drzewa węzła liścia nie są zużywane żadne bity.

Kod długości prostego kodu

Ten wariant jest używany w szczególnym przypadku, gdy w zakresie [0..255] znajdują się tylko 1 lub 2 symbole prefiksu o długości kodu 1. Wszystkie inne długości kodów prefiksów są domyślnie równe zero.

Pierwszy bit wskazuje liczbę symboli:

int num_symbols = ReadBits(1) + 1;

Oto wartości symboli.

Pierwszy symbol jest kodowany przy użyciu 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, zawsze przyjmuje się w zakresie [0..255] i koduje się go 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;
}

Oba symbole powinny być różne. Zduplikowane symbole są dozwolone, ale nieefektywne.

Uwaga: innym szczególnym przypadkiem jest sytuacja, w której wszystkie długości kodów prefiksów są zerami (pusty kod prefiksu). Na przykład kod prefiksu dla odległości może być pusty, jeśli nie ma odwołań wstecznych. Podobnie kody prefiksów dla kanałów alfa, czerwonego i niebieskiego mogą być puste, jeśli wszystkie piksele w ramach tego samego kodu metaprefiksu są generowane przy użyciu pamięci podręcznej kolorów. Nie wymaga to jednak specjalnego traktowania, ponieważ puste kody prefiksów można kodować jako kody zawierające pojedynczy symbol 0.

Kod o normalnej długości

Długości kodów prefiksów mieszczą się w 8 bitach i są odczytywane 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 prefiksowych. Najpierw trzeba odczytać długości kodów niższego poziomu, code_length_code_lengths. Pozostałe elementy code_length_code_lengths (zgodnie z kolejnością w polu kCodeLengthCodeOrder) to zera.

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 symboli odczytu (max_symbol) dla każdego typu symbolu (A, R, G, B i odległość) jest ustawiana na rozmiar alfabetu:

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

W przeciwnym razie jest on definiowany jako:

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

Jeśli wartość max_symbol jest większa niż rozmiar alfabetu dla danego typu symbolu, strumień bitów jest nieprawidłowy.

Następnie z code_length_code_lengths tworzona jest tabela prefiksów, która służy do odczytywania długości kodu do max_symbol.

• Kod [0..15] wskazuje dosłowne długości kodu.
  • Wartość 0 oznacza, że nie zakodowano żadnych symboli.
  • Wartości [1..15] wskazują długość bitową odpowiedniego kodu.
• Kod 16 powtarza poprzednią wartość niezerową [3..6] razy, czyli 3 + ReadBits(2) razy. Jeśli kod 16 zostanie użyty przed wyemitowaniem wartości różnej od zera, powtórzona zostanie wartość 8.
• Kod 17 emituje ciąg zer o długości [3..10], czyli 3 + ReadBits(3) razy.
• Kod 18 emituje ciąg zer o długości [11..138], czyli 11 + ReadBits(7) razy.

Po odczytaniu długości kodów tworzony jest kod prefiksu dla każdego typu symbolu (A, R, G, B i odległość) przy użyciu odpowiednich rozmiarów alfabetów.

Kod długości kodu normalnego musi kodować pełne drzewo decyzyjne, tzn. suma wartości2 ^ (-length) dla wszystkich kodów o wartości różnej od zera musi wynosić dokładnie jeden. Istnieje jednak jeden wyjątek od tej reguły – drzewo z jednym węzłem liścia, w którym wartość węzła liścia jest oznaczona wartością 1, a pozostałe wartości to 0.

6.2.2 Dekodowanie kodów prefiksów meta

Jak wspomnieliśmy wcześniej, format ten umożliwia używanie różnych kodów prefiksów w przypadku różnych bloków obrazu. Kody przedrostków meta to indeksy określające, które kody przedrostków mają być używane w różnych częściach obrazu.

Kody prefiksów meta mogą być używane tylko wtedy, gdy obraz jest używany w roli obrazu ARGB.

Kody prefiksu meta mogą mieć 2 wartości, które są wskazywane przez 1-bitową wartość:

• Jeśli ten bit ma wartość zero, w całym obrazie używany jest tylko jeden kod prefiksu meta. Żadne inne dane nie są przechowywane.
• Jeśli ten bit ma wartość 1, obraz używa wielu kodów prefiksów metadanych. Te kody metadanych są przechowywane jako obraz entropii (opisany poniżej).

Komponenty czerwony i zielony piksela określają 16-bitowy kod prefiksu meta używany w określonym bloku obrazu ARGB.

Obraz entropii

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

Pierwsze 3 bity zawierają wartość prefix_bits. Wymiary obrazu entropii są określane 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 zdefiniowane 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

Liczbę grup kodów prefiksów na obrazie ARGB można uzyskać, znajdując największy kod prefiksu meta na obrazie entropii:

int num_prefix_groups = max(entropy image) + 1;

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

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

int num_prefix_codes = 5 * num_prefix_groups;

Mając piksel (x, y) na obrazie ARGB, możemy uzyskać odpowiednie kody prefiksów, które można wykorzystać w ten 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];

gdzie założyliśmy istnienie struktury PrefixCodeGroup, która reprezentuje zbiór 5 kodów prefiksów. prefix_code_groups to tablica elementów typu PrefixCodeGroup (o rozmiarze num_prefix_groups).

Dekoder używa następnie grupy kodów prefiksowych prefix_group do dekodowania piksela (x, y), jak wyjaśniono w artykule „Dekodowanie danych obrazu zakodowanych entropijnie”.

6.2.3 Dekodowanie danych obrazu zakodowanych entropijnie

W przypadku bieżącej pozycji (x, y) na obrazie dekoder najpierw identyfikuje odpowiednią grupę kodów prefiksów (jak wyjaśniono w ostatniej sekcji). Biorąc pod uwagę grupę kodów prefiksu, piksel jest odczytywany i dekodowany w ten sposób:

Następnie odczytaj symbol S ze strumienia bitów za pomocą kodu prefiksowego 1. Pamiętaj, że S to dowolna liczba całkowita z zakresu od 0 do (256 + 24 + color_cache_size- 1).

Interpretacja wartości S zależy od jej wartości:

1. Jeśli S < 256
   1. Użyj S jako komponentu zielonego.
   2. Odczytaj czerwony z bitstreamu za pomocą kodu prefiksowego 2.
   3. Odczytaj niebieski z bitstreamu za pomocą kodu prefiksowego 3.
   4. Odczytaj wartość alfa ze strumienia bitów za pomocą kodu prefiksowego 4.
2. Jeśli S >= 256 i S < 256 + 24
   1. Użyj S - 256 jako kodu prefiksu długości.
   2. Odczytaj dodatkowe bity długości ze strumienia bitów.
   3. Określ długość odwołania wstecznego L na podstawie kodu prefiksu długości i odczytanych dodatkowych bitów.
   4. Odczytaj kod prefiksu odległości ze strumienia bitów za pomocą kodu prefiksu 5.
   5. Odczytaj dodatkowe bity odległości ze strumienia bitów.
   6. Określ odległość odwołania wstecznego D na podstawie kodu prefiksu odległości i odczytanych dodatkowych bitów.
   7. Skopiuj L pikseli (w kolejności linii skanowania) z sekwencji pikseli zaczynającej się od bieżącej pozycji minus D pikseli.
3. Jeśli S >= 256 + 24
   1. Użyj 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 znajdziesz format w rozszerzonej notacji Backusa-Naura (ABNF) RFC 5234 RFC 7405. Nie zawiera ona wszystkich szczegółów. Koniec obrazu (EOI) jest kodowany tylko pośrednio w liczbie pikseli (image_width * image_height).

Pamiętaj, że *element oznacza, że element może się powtarzać 0 lub więcej razy. 5element oznacza, że znak element powtarza się 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 obrazu

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