Specyfikacja bezstratnego strumienia bitowego WebP

Dr. Jyrki Alakuijala, Google, Inc., 9.03.2023

Streszczenie

WebP bezstratne to format obrazu przeznaczony do bezstratnej kompresji obrazów ARGB. format bezstratny przechowuje i przywraca dokładnie wartości pikseli, łącznie z dla w pełni 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 skompresowaną reprezentację skompresowanych danych w formacie bezstratnym WebP . Jego zadaniem jest szczegółowe omówienie kodera bezstratnego WebP oraz jak używać dekodera.

W tym dokumencie szeroko zastosowaliśmy składnię w języku programowania C, aby opisać w strumieniu bitów, z założeniem, że istnieje funkcja do odczytu bitów, ReadBits(n) Bajty są odczytywane w naturalnej kolejności strumienia, który je zawiera, a każdy bajt jest odczytywany od najmniej istotnego bitu. Kiedy w tym samym czasie odczytuje 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 2 poniższymi stwierdzeniami:

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. O cały piksel ARGB jest reprezentowany przez typ uint32, który jest nieoznaczonym znakiem składającej się z 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 przekształceniu w strumieniu bitowym zawierają dane wymagane do zastosowania odpowiednich przekształceń odwrotnych.

2 Nazewnictwo

ARGB,
Wartość w pikselach 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 adresem haszowym do przechowywania ostatnio używanych kolorów można je wycofać przy użyciu 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 podrozdzielczości wskazujący, które kodowanie entropijne powinno w odpowiednim kwadratie na obrazie, czyli każdy piksel jest meta kod prefiksu.
LZ77
Oparty na słowniku algorytm kompresji okien przesuwanych, który generuje lub opisuje je jako sekwencje wcześniejszych symboli.
kod prefiksu meta
Mała liczba całkowita (do 16 bitów), która indeksuje element w prefiksie meta tabeli.
obraz prognozy
Dwuwymiarowy obraz podrozdzielczości wskazujący, który prognozator przestrzenny jest w konkretnym kwadracie 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 na entropię kodu na większe liczby całkowite, który koduje kilka bitów liczby całkowitej przy użyciu kodu entropii, a pozostałe bity są kodowane w postaci nieprzetworzonej. 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

Początek nagłówka zawiera kontener RIFF. Są to: kolejne 21 bajtów:

  1. Ciąg „RIFF”.
  2. Małych końców, 32-bitowa wartość długości fragmentu, która stanowi cały rozmiar fragmentu kontrolowanego 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 znaków „VP8L” (FourCC w przypadku danych obrazów w formacie bezstratnym).
  5. 32-bitowa liczba bajtów w formacie 32-bitowym, strumienia bezstratnego.
  6. Podpis 1-bajtowy 0x2f.

Pierwsze 28 bitów strumienia bitowego 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);

Wartość version_number to 3-bitowy kod, który musi mieć wartość 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. Ta może zmniejszyć gęstość końcowej kompresji.

Obraz może być poddawany 4 rodzajom przekształceń. Wartość 1 bitu oznacza wystąpienia transformacji. Każdego przekształcenia można użyć tylko raz. Przekształcenia są używane tylko w przypadku obrazu ARGB na poziomie głównym. Obrazy o niższej rozdzielczości (obraz przekształcenia koloru, obraz entropii i obraz predyktora) nie mają żadnych przekształceń, nawet bit 0 wskazujący koniec przekształceń.

Zwykle koder używa tych przekształceń w celu zmniejszenia entropii Shannona. na obrazie szczątkowym. Dane dotyczące przekształcenia można również ustalić na podstawie entropii do ich minimalizacji.

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 przekształcenia znajdują się dane. Przekształcanie danych zawiera informacje wymagane do zastosowania przekształcenia odwrotnego i zależą od typ przekształcenia. Przekształcenia odwrotne są stosowane w odwrotnej kolejności: są odczytywane ze strumienia bitowego, czyli od ostatniego.

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

4.1 Przekształcenie predyktora

Transformacja predyktora może służyć do zmniejszenia entropii dzięki wykorzystaniu faktu, że sąsiadujące 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, jakiego typu prognozy użyć. Dzielimy obraz na kwadraty, a wszystkie piksele w korzystają z tego samego trybu prognozowania.

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 przekształcenia zawierają tryb prognozowania dla każdego bloku obrazu. it to obraz w podrozdzielczości, na którym zielony komponent piksela określa, który tych 14 prognoz jest używany dla wszystkich block_width * block_height pikseli w obrębie konkretnego bloku obrazu ARGB. Ten obraz w podrozdzielczości jest zakodowany 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ć adres bloku filtra:

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

Istnieje 14 różnych trybów prognozowania. W każdym trybie prognozowania bieżąca wartość piksela jest przewidywana na podstawie co najmniej jednego 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 róg, T oznacza górny róg, TR oznacza prawy górny róg, a L oznacza lewy górny róg. W momencie przewidywania wartości P wszystkie piksele O, TL, T, TR i L zostały już przetworzone, a piksele P i wszystkie piksele X są nieznane.

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

Tryb Prognozowana wartość każdego kanału bieżącego piksela
0 0xff000000 (reprezentuje jednolity czarny kolor w ARGB).
1 L
2 T
3 lirach tureckich
4 kierownik zespołu
5 Średnia2(Średnia2(L; TR); T)
6 Średnia2(L; TL)
7 Średnia2(L; T)
8 Średnia2(TL, T)
9 Średnia2(T, TR)
10 Średnia2(L; TL); Średnia2(T; TR))
11 Wybierz(L; T; TL)
12 ClampAddSubtractFull(L, T, TL)
13 ClampAddSubtractHalf(Average2(L, T), TL)

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

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

Formuła „Wybierz” 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 dla pikseli w pierwszej kolumnie po prawej stronie to: coś wyjątkowego. 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.

Ostateczną wartość piksela uzyskuje się przez dodanie każdego kanału prognozowanej wartości do zakodowanej wartości rezydualnej.

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.

Tak jak w przypadku przekształcenia prognozy, najpierw obraz jest dzielony na i ten sam tryb przekształcania jest stosowany dla wszystkich pikseli w danym bloku. 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. delta przekształcenia koloru zależy od wartości ColorTransformElement, która jest taka sama wszystkich pikseli w danym bloku. Delta jest odejmowana podczas transformacji kolorów. Odwrotne przekształcenie kolorów dodaje tylko te delta.

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

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.

Opisujemy zawartość danych dotyczących przekształcenia kolorów, dzięki czemu można zastosować dekodowanie odwrotność koloru oraz przywrócenie oryginalnych wartości czerwieni 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 transformacji kolorów zawiera ColorTransformElement instancje odpowiadające każdemu blokowi obrazu. Każdy ColorTransformElement 'cte' jest traktowany jako piksel na obrazie w podrozdzielczości którego komponent alfa to 255, komponent czerwony to cte.red_to_blue, zielony komponent ma wartość cte.green_to_blue, a komponent niebieski to cte.green_to_red.

Podczas dekodowania dekodowane są wystąpienia bloków (ColorTransformElement) odwrotne przekształcenie kolorów jest stosowane do wartości ARGB pikseli. Jako że odwrotne przekształcenie kolorów polega na dodaniu mu ColorTransformElement wartości do czerwonego i niebieskiego kanału. 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 Odejmij transformację zieloną

Odejmowanie zielonego przekształcenia odejmuje wartości zielone od wartości czerwonego i niebieskiego wartości za każdy piksel. Gdy jest dostępne to przekształcenie, dekoder musi dodać zieloną ikonę zarówno na wartości czerwone, jak i niebieskie. Brak powiązanych danych przekształcenie. 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 nadmiarowe, ponieważ można je modelować za pomocą przekształcenia koloru. ponieważ nie ma tu dodatkowych danych, odejmowanie zielonego przekształcenia może jest zakodowana przy użyciu mniejszej liczby bitów niż pełne przekształcenie kolorów.

4.4 Przekształcenie indeksowania kolorów

Jeśli nie ma wielu unikalnych wartości pikseli, lepszym rozwiązaniem może być utworzenie indeks kolorów i zastąp wartości pikseli indeksami tej tablicy. Do tego służy transformacja indeksowania kolorów. (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 . Jeśli ta liczba nie przekracza progu (256), tworzy tablicę tych ARGB, które są następnie używane do zastąpienia wartości pikseli przez odpowiedni indeks: zielony kanał pikseli jest zastępowany indeksu, wszystkie wartości alfa są ustawione 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 przekształcenia indeksowania kolorów w następujący sposób:

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

Tabela kolorów jest przechowywana z użyciem tego formatu. 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 za pomocą odejmowania w celu zmniejszenia entropii 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. Zestaw pikseli obejmuje kilka pikseli (2, 4 lub 8) na jeden piksel, co odpowiednio zmniejszy 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 mają zostać połączone:

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

Wartości są spakowane do komponentu zielonego w taki 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 przeczytaniu tego przekształcenia wartość image_width jest próbkowana według parametru width_bits. Ten 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 graficzne

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: zapisuje rzeczywiste piksele obrazu.
  2. Obraz entropii: zapisuje kody prefiksów meta (zobacz „Dekodowanie kodów prefiksów meta”).
  3. Obraz prognozy: przechowuje metadane przekształcenia prognozowanego (patrz „Przekształcenie prognozujące”).
  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.

Obraz jest najpierw dzielony na zbiór bloków o stałym rozmiarze (zwykle o wymiarach 16 x 16) bloki). 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. Można je zminimalizować, jeśli statystycznie podobne bloki mają ten sam kod entropii, dzięki czemu kod ten 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 par 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 trzech możliwych metod:

  1. Literały zakodowane z prefiksem: każdy kanał (zielony, czerwony, niebieski i alfa) jest kodowana entropią niezależnie.
  2. Odwołanie wsteczne LZ77: sekwencja pikseli jest kopiowana z innego miejsca w zdjęcia.
  3. Kod pamięci podręcznej kolorów: użycie krótkiego zwielokrotnienia kodu haszującego (pamięć podręczna kolorów) indeksu ) ostatnio oglądanego koloru.

W poniższych podsekcjach szczegółowo opisujemy każdy z tych sposobów.

5.2.1 Literały zakodowane z prefiksem

Piksel jest zapisywany jako poprzedzone prefiksem wartości kolorów zielonego, czerwonego, niebieskiego i alfa (w to zamówienie). Szczegółowe informacje znajdziesz w sekcji 6.2.3.

5.2.2 LZ77 Odniesienia wsteczne

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

  • Długość określa, ile pikseli w kolejności linii skanowania ma zostać skopiowane.
  • Kod odległości to liczba określająca pozycję piksel, z którego mają zostać skopiowane piksele. Dokładne mapowanie zostało 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 formie (bez kodu entropii).

Uzasadnienie: to podejście zmniejsza wymagania dotyczące przechowywania entropii. w kodzie. 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.

Poniższa tabela zawiera kody prefiksów i dodatkowe bity używane do przechowywania różnych zakresów wartości.

Zakres wartości Kod prefiksu Dodatkowe bity
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... 7 2
… ... …
3072..4096 23 10
… ... …
524289..786432 38 18
786433..1048576 39 18

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 wspomnieliśmy wcześniej, kod odległości jest liczbą wskazującą pozycję widziany wcześniej piksel, z którego mają zostać skopiowane 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 wskazują odległość w pikselach w kolejności wierszy skanowania. przesunięcie 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].
  • Maksymalna liczba pikseli, które są w tym samym wierszu co bieżący piksel, wynosi maksymalnie 8 kolumn po lewej stronie bieżącego piksela. [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 z pamięci podręcznej kolorów

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, pamięć podręczna kolorów rozmiar jest odczytywany dalej:

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 przez (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 wpisy we wszystkich kolorach wartości pamięci podręcznej są ustawione na zero. Kod z pamięci podręcznej koloru jest konwertowany na ten kolor przy czas dekodowania. Stan pamięci podręcznej kolorów jest utrzymywany przez wstawienie każdego niezależnie od tego, czy jest on generowany przez odwołanie wsteczne, czy jako literały, do pamięci podręcznej w kolejności, w jakiej pojawiają się w strumieniu.

Kod entropii 6

6.1 Omówienie

Większość danych jest kodowana z wykorzystaniem kanonicznego kodu prefiksu. Dlatego też są przesyłane, wysyłając długości kodów z prefiksami: zamiast rzeczywistych kodów prefiksów.

W szczególności format wykorzystuje kodowanie prefiksów wariantów przestrzennych. W innym słowa, poszczególne bloki obrazu mogą opisywać różną entropię kodami.

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

6.2 Szczegóły

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

  1. Dekodowanie i tworzenie kodów prefiksów.
  2. Metakody prefiksów.
  3. Dane obrazów zakodowane entropią.

Dla każdego piksela (x, y) istnieje zestaw pięciu kodów prefiksów powiązanych z . 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: używany do określania odległości w odniesieniu do tyłu.

Odtąd będziemy nazywać ten zbiór grupą kodów prefiksów.

6.2.1 Dekodowanie i tworzenie kodów prefiksów

Ta sekcja zawiera informacje na temat odczytywania długości kodu prefiksu z strumienia bitowego.

Długości kodów prefiksów mogą być kodowane na dwa sposoby. Użyta metoda jest określona jako wartość 1-bitową.

  • Jeśli ten bit ma wartość 1, 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 szczególnych przypadkach, gdy występują tylko 1 lub 2 symboly prefiksu. zakres [0..255] o długości kodu 1. 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 przedstawiono 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]. Druga (jeśli występuje) zawsze zakłada się, że mieści się on w zakresie [0..255] i jest zakodowany przy użyciu 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;
}

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

Uwaga: innym szczególnym przypadkiem jest sytuacja, w której wszystkie długości kodu prefiksu mają wartość 0 (kod pusty kod prefiksu). 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ą generowane 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 normalnej długości kodu

Długości kodu prefiksu mieszczą się w 8 bitach i są odczytywane w następujący sposób. Najpierw 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. kod niższego poziomu długości, code_length_code_lengths, muszą najpierw zostać przeczytane. Pozostałe wartości w polu code_length_code_lengths (w kolejności z pola 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 do odczytu (max_symbol) dla każdego typu symbolu (A, R, G, B i odległość) jest ustawiony na wielkość 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 ona definiowana w ten sposób:

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

Jeśli max_symbol jest większy niż rozmiar alfabetu dla danego typu symbolu, Parametr 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łowne długości kodów.
    • 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 znakiem innym niż 0 zostaje wyemitowana 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 o normalnej długości musi kodować pełne drzewo decyzyjne, czyli suma wartości 2 ^ (-length) dla wszystkich niezerowych kodów musi wynosić 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 metaprefiksów to indeksy identyfikujące które kodów prefiksów używanych 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.

Istnieją 2 możliwości kodów prefiksów meta, które są wskazywane za pomocą wartości 1-bitowej:

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

Czerwone i zielone komponenty piksela określają 16-bitowy kod metaprefiksu używany w konkretnego bloku obrazu ARGB.

Obraz entropii

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 obraz pochodzi z 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 z pliku entropii:

int num_prefix_groups = max(entropy image) + 1;

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

Każda grupa kodów prefiksów zawiera pięć kodów prefiksów, więc łączna liczba prefiksów Kody to:

int num_prefix_codes = 5 * num_prefix_groups;

Na podstawie piksela (x, y) w obrazie ARGB możemy uzyskać odpowiednie kody prefiksów do użycia 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 zakładamy istnienie struktury PrefixCodeGroup, która reprezentuje zbiór 5 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 obrazów zakodowanych entropią

W bieżącej pozycji (x, y) na obrazie dekoder najpierw identyfikuje odpowiedniej grupy 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 z bitowego strumienia za pomocą kodu prefiksu 1. Pamiętaj, że S to dowolna liczba całkowita z zakresu 0–(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 dane ze strumienia bitowego na czerwono przy użyciu kodu prefiksu nr 2.
    3. Odczytuj kolor niebieski ze strumienia bitowego za pomocą kodu prefiksu 3.
    4. Odczytaj wersję alfa ze strumienia bitowego przy użyciu kodu prefiksu 4.
  2. Jeśli S >= 256 & S < 256 + 24
    1. Jako kodu prefiksu długości użyj kodu S-256.
    2. Odczytaj dodatkowe bity odpowiadające danej długości ze strumienia bitowego.
    3. Określ długość wstecznej L na podstawie kodu prefiksu długości oraz żeby odczytać dodatkowe informacje.
    4. Odczytaj kod prefiksu odległości z bitowego strumienia za pomocą kodu prefiksu 5.
    5. odczytaj dodatkowe bity dla odległości z bitowego strumienia danych.
    6. Wyznacz odległość wsteczną D na podstawie kodu prefiksu odległości i odczytane dodatkowe informacje.
    7. Skopiuj piksele L (w kolejności wierszy skanowania) z sekwencji pikseli rozpoczynających się w bieżącej pozycji minus 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 obejmują one wszystkich szczegółów. Koniec obrazu (EOI) jest domyślnie zakodowany w postaci liczby 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 to wartość binarna.

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