dr Jyrki Alakuijala, Google, Inc., 2023-03-09
W skrócie
WebP bezstratny to format obrazu umożliwiający bezstratną kompresję obrazów ARGB. Format bezstratny zapisuje i przywraca dokładnie wartości pikseli, w tym wartości kolorów w przypadku w pełni przezroczystych pikseli. Do kompresji danych zbiorczych używany jest uniwersalny algorytm sekwencyjnej kompresji danych (LZ77), kodowanie prefiksów i pamięć podręczna kolorów. Wykazano, że prędkość dekodowania jest większa niż w przypadku formatu PNG, a skompresja mniejsza o 25% niż w przypadku dzisiejszego formatu PNG.
1 Wstęp
Ten dokument opisuje reprezentację skompresowanych danych obrazu bezstratnego WebP. Ten dokument zawiera szczegółowe informacje na temat implementacji bezstratnego kodera i dekodera WebP.
W tym dokumencie intensywnie korzystamy ze składni języka programowania C do opisania strumienia bitowego i zakładamy, że istnieje funkcja do odczytu bitów (ReadBits(n)). Bajty są odczytywane w naturalnej kolejności w strumieniu, który je zawiera, a bity każdego bajtu są odczytywane w kolejności od najmniejszej liczby bitów na początku. Gdy jest odczytywany wiele bitów w tym samym czasie, z oryginalnych danych jest tworzona liczba całkowita w pierwotnej kolejności. Najbardziej istotne bity zwróconej liczby całkowitej są też najbardziej znaczącymi bitami oryginalnych danych. Dlatego oświadczenie
b = ReadBits(2);
jest równoważny z dwoma poniższymi stwierdzeniami:
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 bajta. Odpowiedni typ definiujemy jako uint8. Cały piksel ARGB jest reprezentowany przez typ uint32, który jest nieoznaczoną liczbą całkowitą składającą się z 32 bitów. W kodzie pokazującym zachowanie przekształceń wartości te 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ą wewnętrznie używać innej reprezentacji.
Ogólnie rzecz biorąc, bezstratny obraz WebP zawiera dane nagłówka, informacje dotyczące przekształcenia i rzeczywiste dane obrazu. Nagłówki zawierają szerokość i wysokość obrazu. Przed zakodowaniem entropii obraz bezstratny WebP może przejść 4 różne rodzaje przekształceń. Informacje o przekształceniach w strumieniu bitowym zawierają dane niezbędne do zastosowania odpowiednich przekształceń odwrotnych.
2 Nazewnictwo
- ARGB,
- Wartość w pikselu 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 # # do przechowywania ostatnio używanych kolorów, aby umożliwić ich zapamiętanie przy użyciu krótszych kodów.
- obraz z indeksowaniem kolorów
- Jednowymiarowy obraz kolorów, który można zindeksować za pomocą małej liczby całkowitej (do 256 w ramach bezstratnego WebP).
- obraz z przekształceniem kolorów
- Dwuwymiarowy obraz w podrozdzielczości zawierający dane na temat korelacji komponentów kolorów.
- mapowanie odległości
- Zmienia odległości LZ77 tak, aby wartości w pikselach były jak najmniejsze.
- obraz entropii
- Dwuwymiarowy obraz w podrozdzielczości wskazujący, której entropii należy użyć w odpowiednim kwadracie na obrazie, czyli każdy piksel to kod metaprefiksu.
- LZ77
- Oparty na słowniku algorytm kompresji okien przesuwanych, który emituje symbole lub opisuje je jako sekwencje symboli w przeszłości.
- kod prefiksu meta
- Mała liczba całkowita (do 16 bitów), która indeksuje element w tabeli z metatagami.
- obraz prognozowania
- Dwuwymiarowy obraz w podrozdzielczości wskazujący, która prognoza przestrzenna jest używana w przypadku określonego kwadratu na obrazie.
- kod prefiksu
- Klasyczny sposób kodowania entropii, w którym używana jest mniejsza liczba bitów, aby częściej otrzymywać kody.
- kodowanie z użyciem prefiksów
- Sposób kodowania większych liczb całkowitych, który koduje kilka bitów liczby całkowitej za pomocą kodu entropii i koduje pozostałe nieprzetworzone bity. Dzięki temu opisy kodów entropii są stosunkowo małe, nawet jeśli zakres symboli jest duży.
- skanować zamówienie
- Kolejność przetwarzania pikseli (od lewej do prawej i od góry do dołu), począwszy od piksela od lewej strony. Po wypełnieniu wiersza przejdź dalej w lewej kolumnie następnego wiersza.
3 Nagłówek RIFF
Na początku nagłówka znajduje się kontener RIFF. Składa się to z tych 21 bajtów:
- Ciąg tekstowy „RIFF”.
- 32-bitowa wartość fragmentu, który jest jego całkowitym rozmiarem zależnym od nagłówka RIFF. Zwykle jest to rozmiar ładunku (rozmiar pliku minus 8 bajtów: 4 bajty dla identyfikatora „RIFF” i 4 bajty do przechowywania samej wartości).
- Ciąg tekstowy „WEBP” (nazwa kontenera RIFF).
- Ciąg znaków „VP8L” (FourCC dla danych obrazu w kodowaniu bezstratnym).
- Minimalna 32-bitowa wartość liczby bajtów w strumieniu bezstratnym.
- Jednobajtowy 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 bezstratnego obrazu WebP do 16384 × 16384 pikseli.
Bit alfa_is_used ma tylko wskazówkę i nie powinien mieć wpływu na dekodowanie. Należy go ustawić na 0, jeśli wszystkie wartości alfa na ilustracji mają 255, a w przeciwnym razie na 1.
int alpha_is_used = ReadBits(1);
Wartość parametru version_number to 3-bitowy kod, który musi mieć wartość 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ą przez modelowanie korelacji przestrzennych i kolorowych. Mogą zwiększyć gęstość ostatecznej kompresji.
Obraz może przejść 4 rodzaje przekształceń. Wartość 1 bita wskazuje obecność przekształcenia. Każdego przekształcenia można użyć tylko raz. Przekształcenia są używane tylko w przypadku obrazu ARGB głównego poziomu. Obrazy w podrozdzielczości (obraz z przekształceniem kolorów, obraz entropii i obraz prognostyczny) nie mają żadnych przekształceń, ani nawet bit 0 oznaczający koniec przekształceń.
Zwykle koder używa tych przekształceń, aby zmniejszyć entropię Shannona w obrazie resztkowym. Dane przekształcone można też określać 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 występuje przekształcenie, jego typ jest określony przez kolejne 2 bity. Są 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łcenia. Dane przekształcenia zawierają informacje wymagane do zastosowania przekształcenia odwrotnego i zależą od jego typu. Przekształcenia odwrotne są stosowane w odwrotnej kolejności, w jakiej są odczytywane ze strumienia bitowego, czyli od ostatniego.
Następnie opisujemy dane przekształcenia dla różnych typów.
4.1 Przekształcenie prognozowania
Przekształcenie prognostyczne może służyć do ograniczania entropii, wykorzystując fakt, że sąsiednie piksele są często skorelowane. W przekształceniu prognostycznego bieżąca wartość piksela jest przewidywana na podstawie pikseli, które zostały już zdekodowane (w kolejności linii skanowania), a tylko wartość rezydualna (rzeczywista – prognozowana) jest kodowana. Zielony składnik piksela określa, które z 14 prognoz będą używane w danym bloku obrazu ARGB. Tryb prognozowania określa rodzaj prognozy. Dzielimy obraz na kwadraty i wszystkie piksele w kwadrat korzystają z tego samego trybu prognozowania.
Pierwsze 3 bity danych prognozy określają szerokość i wysokość bloku w liczbie 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 w przypadku każdego bloku obrazu. Jest to obraz w podrozdzielczości, w którym zielony składnik piksela określa, który z 14 prognoz ma być używany dla wszystkich pikseli block_width * block_height w danym bloku obrazu ARGB. Ten obraz w podrozdzielczości jest kodowany przy użyciu tych samych technik, które opisano w Rozdziale 5.
Liczba kolumn blokowych, transform_width, jest używana do indeksowania dwuwymiarowego. W przypadku piksela (x, y) można obliczyć odpowiedni adres bloku filtra za pomocą:
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ść w pikselach jest przewidywana na podstawie co najmniej jednego sąsiedniego piksela, którego wartości są już znane.
Sąsiadujące piksele (TL, T, TR i L) bieżącego piksela (P) zostały wybrane 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 róg, T oznacza górną część, TR – prawy górny róg, a L – lewy. W chwili przewidywania wartości P wszystkie piksele O, TL, T, TR i L zostały już przetworzone, a piksel P i wszystkie piksele X są nieznane.
Biorąc pod uwagę poprzedzające sąsiednie piksele, różne tryby prognozowania są zdefiniowane w ten sposób.
| Tryb | Prognozowana wartość każdego kanału bieżącego piksela |
|---|---|
| 0 | 0xff000000 (reprezentuje jednolitą czerń w ARGB) |
| 1 | L |
| 2 | T |
| 3 | lirach tureckich |
| 4 | TL |
| 5 | Średnia2(Średnia2(L; TR); T) |
| 6 | Średnia2(L; TL) |
| 7 | Średnia2(L; T) |
| 8 | Średnia2(TL; T) |
| 9 | Średnia2(T; TR) |
| 10 | Średnia2(Średnia2(L; TL); Średnia2(T; TR)) |
| 11 | Select(L, T, TL) |
| 12 | ClampAddSubtractFull(L, T, TL) |
| 13 | ClampAddSubtractHalf(Average2(L, T), TL) |
Average2 każdy komponent ARGB jest zdefiniowany w następujący sposób:
uint8 Average2(uint8 a, uint8 b) {
return (a + b) / 2;
}
Prognoza dotycząca wyboru jest definiowana 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);
}
Obowiązują specjalne reguły postępowania z niektórymi pikselami obramowania. W przypadku przekształcenia prognozy niezależnie od trybu [0..13] w przypadku tych pikseli prognozowana wartość piksela znajdującego się w górnej części obrazu to 0xff000000, wszystkie piksele w górnym rzędzie – piksele L, a wszystkie piksele w skrajnej lewej kolumnie mają wartość T pikseli.
Adresowanie pikseli TR dla pikseli w skrajnej kolumnie po prawej stronie jest wyjątkowe. Piksele w skrajnej prawej kolumnie są prognozowane przy użyciu trybów [0..13] (tak samo jak piksele nie sąsiadujące z obramowaniem). Jako piksel TR używany jest piksel najdalej z lewej w tym samym wierszu, w którym znajduje się bieżący piksel.
Ostateczną wartość w pikselach uzyskuje się przez dodanie każdego kanału wartości prognozowanej do zakodowanej wartości resztowej.
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 piksela. Przekształcenie koloru zachowuje wartość zielonego (G) w niezmienionej postaci, przekształca wartość czerwonego (R) na podstawie wartości zielonej i przekształca wartość niebieskiego (B) na podstawie wartości zielonej, a potem na czerwoną.
Tak jak w przypadku przekształcenia prognostycznego, najpierw obraz jest dzielony na bloki i ten sam tryb przekształcania jest stosowany do 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 koloru następuje poprzez zdefiniowanie delta przekształcenia kolorów. Różnica
przekształcenia kolorów zależy od wartości ColorTransformElement, która jest taka sama w przypadku wszystkich pikseli w danym bloku. Delta jest odejmowana
podczas przekształcania kolorów. Odwrotne przekształcenie kolorów dodaje 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 za pomocą 8-bitowej liczby całkowitej, która reprezentuje 3,5-punktową liczbę stałą, oraz 8-bitowy kanał kolorów RGB ze znakiem (c) [-128..127]. Jest on 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 niepodpisanej reprezentacji (uint8) na 8-bitową wersję podpisanego (int8). Wartość ze znakiem powinna być interpretowana jako 8-bitowa liczba uzupełniająca (czyli: zakres uint8 [128..255] jest mapowany na zakres [-128..-1] swojej przekonwertowanej wartości int8).
Mnożenie odbywa się z większą precyzją (z dokładnością co najmniej 16 bitów). Właściwość rozszerzenia znaku operacji shift nie ma tutaj znaczenia. Z wyniku wykorzystywane są tylko 8 najniższych bitów, a przesunięcie rozszerzenia znaku i przesunięcie bez znaku są ze sobą zgodne.
Opisujemy teraz zawartość danych o przekształceniu kolorów, aby dekodowanie mogło zastosować odwrotną transformację kolorów i przywrócić pierwotne wartości czerwonego i niebieskiego. Pierwsze 3 bity danych przekształcenia kolorów zawierają szerokość i wysokość bloku obrazu pod względem liczby bitów, tak jak przekształcenie prognozujące:
int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;
Pozostała część danych przekształcenia kolorów zawiera ColorTransformElementwystąpienia odpowiadające poszczególnym blokom obrazu. Każdy element ColorTransformElement 'cte' jest traktowany jako piksel na obrazie podrzędnym, którego komponent alfa to 255, czerwony – cte.red_to_blue, zielony – cte.green_to_blue, a niebieski – cte.green_to_red.
Podczas dekodowania ColorTransformElement instancje bloków są dekodowane, a dla wartości ARGB pikseli stosowane jest odwrotne przekształcenie kolorów. Jak już wspomnieliśmy, odwrotne przekształcenie kolorów polega na dodaniu wartości ColorTransformElement do kanałów czerwonego i niebieskiego. Kanały alfa i zielone
pozostawiają 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 przekształcenia ekologicznego
Przekształcenie zielonego odejmuje wartości zielone od wartości czerwonego i niebieskiego każdego piksela. Gdy istnieje to przekształcenie, dekoder musi dodać wartość zielonej do wartości czerwonej i niebieskiej. Brak danych powiązanych z tą przekształceniem. Dekoder stosuje odwrotną transformatę 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. Nie ma tu jednak żadnych dodatkowych danych, więc odejmowanie transformacji zielonej można zakodować przy użyciu mniejszej liczby bitów niż pełnowymiarowego przekształcenia koloru.
4.4 Przekształcenie indeksowania kolorów
Jeśli nie ma wielu unikalnych wartości pikseli, lepiej utworzyć tablicę indeksów kolorów i zastąpić wartości pikseli indeksami tablicy. Jest to możliwe dzięki przekształceniu indeksowania kolorów. W kontekście bezstratnego kodowania WebP w szczególności nie nazywamy tego przekształcenia palety, ponieważ w przypadku bezstratnego kodowania WebP istnieje podobna, ale bardziej dynamiczna koncepcja: pamięć podręczna kolorów.
Przekształcenie indeksowania kolorów sprawdza liczbę niepowtarzalnych wartości ARGB w obrazie. Jeśli liczba ta jest poniżej wartości progowej (256), tworzy tablicę z tymi wartościami ARGB, która następnie zostaje użyta do zastąpienia wartości w pikselach odpowiednim indeksem. Zielony kanał pikseli zostaje zastąpiony przez indeks, wszystkie wartości alfa przybierają wartość 255, a wszystkie wartości czerwonego i niebieskiego – 0.
Dane przekształcenia zawierają rozmiar tabeli kolorów i wpisy w tabeli kolorów. 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 w formacie zapisu obrazów. Tabelę kolorów można uzyskać przez odczytanie obrazu bez nagłówka RIFF, jego rozmiaru i przekształceń, przy założeniu, że ma on wysokość 1 piksela i szerokość color_table_size.
W tabeli kolorów jest zawsze kodowana odejmowanie w celu zmniejszenia entropii obrazu. Delty kolorów palety mają zwykle znacznie mniejszą entropię niż same kolory, co prowadzi do znacznego oszczędności przy mniejszych zdjęciach. Podczas dekodowania każdy końcowy kolor z tabeli kolorów można uzyskać, osobno dodając poprzednie wartości komponentu ARGB i zachowując jak najmniej istotne 8 bitów wyniku.
Odwrotna transformata dla obrazu polega po prostu na zastępowanie wartości w pikselach (które są indeksami tabeli kolorów) rzeczywistymi wartościami z tabeli kolorów. Indeksowanie odbywa się na podstawie zielonego komponentu koloru ARGB.
// Inverse transform
argb = color_table[GREEN(argb)];
Jeśli indeks jest równy lub większy niż color_table_size, wartość atrybutu Argb należy ustawić na 0x00000000 (przezroczysta czerń).
Jeśli tabela kolorów jest mała (wynosi mniej niż 16 kolorów), kilka pikseli jest zgrupowanych w jeden piksel. W takim przypadku kilka pikseli (2, 4 lub 8) mieści się w jednym pikselu, co zmniejsza odpowiednio szerokość obrazu. Łączenie pikseli umożliwia wydajniejsze kodowanie wspólnej entropii dystrybucji sąsiadujących pikseli i daje pewne korzyści kodowaniu arytmetycznemu, które są podobne do kodowania arytmetycznego, ale można z niego korzystać tylko w przypadku maksymalnie 16 unikalnych wartości.
color_table_size określa, ile pikseli zostanie połą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 obraz nie jest grupowany. Wartość 1 oznacza, że 2 piksele są połączone, a każdy piksel ma zakres [0...15]. Wartość 2 oznacza, że 4 piksele są połączone, a każdy piksel ma zakres [0..3]. Wartość 3 oznacza, że połączonych 8 pikseli ma zakres [0,.1], czyli wartość binarną.
Wartości są pakowane do zielonego komponentu w taki sposób:
width_bits= 1: dla każdej wartości x, gdzie x ≠ 0 (mod 2), zielona wartość w miejscu x jest umieszczona w 4 najmniej istotnych bitów wartości zielonej w x / 2, a wartość zielona w x + 1 jest umieszczona w 4 najbardziej znaczących bitach wartości zielonej w x / 2.width_bits= 2: dla każdej wartości x, gdzie x ≠ 0 (mod 4), zielona wartość w miejscu x jest umieszczona w 2 najmniej znaczących bitach wartości zielonej w x / 4, a zielone wartości w obszarze x / 4 są ułożone w kolejności 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), zielona wartość w miejscu x jest umieszczana w najmniej znaczącym bitzie wartości zielonej w x / 8, a wartości zielone w obszarze x + 1 do x + 7 są umieszczane w kolejności bardziej znaczących bitów wartości zielonej w x / 8.
Po odczytaniu tego przekształcenia parametr image_width jest podpróbkowany przez parametr width_bits. Wpływa to na rozmiar kolejnych przekształceń. Nowy rozmiar można obliczyć za pomocą parametru DIV_ROUND_UP, tak jak określono wcześniej.
image_width = DIV_ROUND_UP(image_width, 1 << width_bits);
5 Dane obrazu
Dane obrazu to tablica wartości w pikselach w kolejności na linii skanowania.
5.1 Role danych obrazu
Danych obrazu używamy na 5 różnych rolach:
- Obraz ARGB: zapisuje rzeczywiste piksele obrazu.
- Obraz entropii: zapisuje kody metaprefiksów (patrz „Dekodowanie kodów meta prefiksów”).
- Obraz prognozatora: zapisuje metadane przekształcenia prognostycznego (patrz „Przekształcenie prognozujące”).
- Obraz przekształcenia kolorów: tworzony na podstawie wartości
ColorTransformElement(zdefiniowanych w sekcji „Przekształcenie kolorów”) dla różnych bloków obrazu. - Obraz indeksowania kolorów: tablica o rozmiarze
color_table_size(do 256 wartości ARGB) przechowująca metadane przekształcenia indeksowania kolorów (patrz „Przekształcenie indeksowania kolorów”).
5.2 Kodowanie danych obrazu
Kodowanie danych obrazu nie zależy od ich 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 mieć te same kody entropii.
Uzasadnienie: przechowywanie kodu entropii wiąże się z kosztami. Koszt ten można zminimalizować, jeśli statystycznie podobne bloki współdzielą kod entropii, dzięki czemu ten kod zostanie zapisany tylko raz. Koder może na przykład znaleźć podobne bloki, grupując je za pomocą ich właściwości statystycznych lub wielokrotnie złączając parę losowo wybranych klastrów, gdy zmniejsza to łączną liczbę bitów niezbędnych do zakodowania obrazu.
Każdy piksel jest kodowany w jeden z trzech możliwych sposobów:
- Litery z prefiksem: każdy kanał (zielony, czerwony, niebieski i alfa) jest kodowany niezależnie.
- Odwołanie do tyłu LZ77: sekwencja pikseli jest kopiowana z innego miejsca na obrazie.
- Kod pamięci podręcznej kolorów: korzystanie z krótkiego multiplikatywnego kodu skrótu (indeksu pamięci podręcznej kolorów) o ostatnio zaobserwowanym kolorze.
W poniższych podsekcjach szczegółowo opisujemy każdą z nich.
5.2.1 Literały z prefiksem
Piksel jest przechowywany jako kod z prefiksem wartości zielonego, czerwonego, niebieskiego i alfa (w tej kolejności). Szczegółowe informacje znajdziesz w Sekcji 6.2.3.
5.2.2 LZ77 wstecz
Odwołania wsteczne to kropki o długości i kodu odległości:
- Długość wskazuje liczbę pikseli do skopiowania w kolejności linii skanowania.
- Kod odległości to liczba wskazująca położenie wcześniej widocznego piksela, 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 przy użyciu kodowania prefiksu LZ77.
Kodowanie przedrostka 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 niezmienionej postaci (bez kodu entropii).
Uzasadnienie: to podejście zmniejsza ilość miejsca na dane wymaganego przez kod entropii. Duże wartości są zwykle rzadkie, więc dodatkowe bity zostaną użyte w przypadku bardzo małej liczby wartości na obrazie. Takie podejście zapewnia ogólną kompresję.
W tabeli poniżej podano 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..16 | 7 | 2 |
| ... | ... | ... |
| 3072..4096 | 23 | 10 |
| ... | ... | ... |
| 524289..786432 | 38 | 18 |
| 786433..1048576 | 39 | 18 |
Pseudokod pozwalający uzyskać wartość (długość lub odległość) z kodu prefiksu jest taki:
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 już wspomnieliśmy, kod odległości to liczba wskazująca pozycję wcześniej widocznego piksela, z którego zostaną skopiowane piksele. Ta podsekcja definiuje mapowanie między kodem odległości a pozycją poprzedniego piksela.
Kody odległości większe niż 120 pikseli określają odległość w kolejności linii skanowania z przesunięciem o 120.
Najmniejsze kody odległości [1..120] są specjalne i są zarezerwowane dla bliskiej sąsiedztwa bieżącego piksela. Ta okolica składa się ze 120 pikseli:
- Piksele od 1 do 7 wierszy powyżej bieżącego piksela, znajdujące się w maksymalnie 8 kolumnach po lewej lub maksymalnie 7 kolumnach po prawej stronie bieżącego piksela. [Łączna liczba takich pikseli =
7 * (8 + 1 + 7) = 112]. - Piksele w tym samym wierszu co bieżący piksel i znajdujące się maksymalnie 8 kolumn po lewej stronie od bieżącego piksela. [
8takich pikseli].
Mapowanie między kodem odległości distance_code a odsunięciem sąsiedniego piksela (xi, yi) jest takie:
(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 o (0, 1) w przypadku sąsiedniego piksela, czyli o piksel powyżej bieżącego (różnica w kierunku X o 0 pikseli i o 1 piksel w kierunku Y).
Podobnie kod odległości 3 wskazuje piksel w lewym górnym rogu.
Dekoder może przekonwertować kod odległości distance_code na odległość w kolejności 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, a image_width to szerokość obrazu w pikselach.
5.2.3 Kodowanie w pamięci podręcznej
Pamięć podręczna kolorów przechowuje zestaw kolorów, które zostały ostatnio użyte w obrazie.
Uzasadnienie: dzięki temu czasami można bardziej efektywnie używać ostatnio używanych kolorów niż ich emitowanie za pomocą 2 innych metod (opisanych w sekcjach 5.2.1 i 5.2.2).
Kody pamięci podręcznej kolorów są przechowywane w następujący sposób: Po pierwsze dostępna jest wartość 1-bitowa, która wskazuje, czy używana jest pamięć podręczna kolorów. Jeśli ten bit ma wartość 0, nie istnieją kody z pamięci podręcznej kolorów i nie są one przesyłane w kodzie prefiksu dekodującym zielone symbole i kody prefiksów długości. Jeśli jednak ten bit ma wartość 1, rozmiar pamięci podręcznej 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ą w przypadku innych wartości wskazywać uszkodzony strumień bitowy.
Pamięć podręczna kolorów to tablica o rozmiarze color_cache_size. Każdy wpis zawiera jeden kolor
ARGB. Kolory są wyszukiwane przez indeksowanie według atrybutu (0x1e35a7bd * color) >> (32 -
color_cache_code_bits). W pamięci podręcznej kolorów jest wykonywane tylko jedno wyszukiwanie; nie ma konfliktu nazw.
Na początku dekodowania lub kodowania obrazu wszystkie wpisy we wszystkich wartościach pamięci podręcznej kolorów są ustawiane na 0. Kod z pamięci podręcznej kolorów jest konwertowany na ten kolor podczas dekodowania. Stan pamięci podręcznej kolorów jest utrzymywany przez wstawienie do pamięci podręcznej wszystkich pikseli w kolejności, w jakiej występują w strumieniu – niezależnie od tego, czy zostały one utworzone przez odniesienie wsteczne, czy jako literały.
6 Kod entropii
6.1 Omówienie
Większość danych jest kodowana z użyciem kanonicznego kodu prefiksu. Dlatego kody są przesyłane przez wysyłanie długości kodu prefiksu w przeciwieństwie do rzeczywistych kodów prefiksów.
W szczególności format wykorzystuje kodowanie prefiksu opartego na wariantach przestrzennych. Innymi słowy, różne bloki obrazu mogą potencjalnie wykorzystywać różne kody entropii.
Uzasadnienie: poszczególne obszary obrazu mogą mieć różne cechy. Używanie różnych kodów entropii zapewnia więc większą elastyczność i potencjalnie lepszą kompresję.
6.2 Szczegóły
Zakodowane dane obrazu składają się z kilku części:
- Dekodowanie i tworzenie kodów prefiksów.
- Kody meta prefiksów.
- Dane obrazu zakodowane entropią.
Z każdym pikselem (x, y) jest powiązanych 5 kodów prefiksu. Te kody są (w kolejności bitowej):
- Kod prefiksu 1: używany na potrzeby kanału zielonego, długości odwołania wstecznego i pamięci podręcznej kolorów.
- Kod prefiksu #2, #3 i #4: używany odpowiednio dla kanałów czerwonego, niebieskiego i alfa.
- Kod prefiksu 5: używany do określania odległości od początku śledzenia.
Od tej pory ten zestaw będzie określany jako grupa kodów prefiksu.
6.2.1 Dekodowanie i tworzenie kodów prefiksów
Ta sekcja zawiera informacje na temat odczytywania długości kodu prefiksu ze strumienia bitowego.
Długości kodu prefiksu można kodować na 2 sposoby. Użytą metodę określa wartość 1-bitowa.
- 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 strumień może nadal zawierać nieużywane fragmenty kodu. Może to nie być skuteczne, ale zezwala na to format. Opisane drzewo musi być pełnym drzewem binarnym. Węzeł z pojedynczym liściem jest uważany za pełne drzewo binarne i może być kodowany za pomocą prostego kodu długości kodu lub kodu o normalnej długości. Podczas kodowania węzła o pojedynczym liściu przy użyciu kodu o normalnej długości kodu wszystkie fragmenty kodu oprócz jednego mają cyfry zero, a wartość węzła z pojedynczym liściem jest oznaczona liczbą 1 – nawet jeśli nie są wykorzystywane żadne bity, gdy używane jest drzewo węzłów z pojedynczym liściem.
Prosty kod długości kodu
Ten wariant jest używany w szczególnych przypadkach, gdy tylko 1 lub 2 symbole prefiksu mieszczą się w zakresie [0..255] o długości kodu 1. Wszystkie inne długości kodu prefiksu są domyślnie równe zerom.
Pierwszy bit wskazuje liczbę symboli:
int num_symbols = ReadBits(1) + 1;
Poniżej podano wartości symboli.
Ten pierwszy symbol jest kodowany 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, o ile występuje, mieści się zawsze 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;
}
Te symbole powinny się różnić. Zduplikowane symbole są dozwolone, ale nieskuteczne.
Uwaga: inny przypadek specjalne dotyczy sytuacji, gdy wszystkie długości kodu prefiksu wynoszą 0 (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 alfa, czerwonego i niebieskiego mogą być puste, jeśli wszystkie piksele w tym samym kodzie meta prefiksu zostały wygenerowane przy użyciu pamięci podręcznej kolorów. Nie wymaga to jednak specjalnej obsługi, ponieważ puste kody prefiksów mogą być kodowane jako zawierające pojedynczy symbol 0.
Kod o normalnej długości kodu
Długości kodu w prefiksie mieszczą się w 8 bitach i są odczytywane w następujący sposób.
Pierwszy z nich num_code_lengths określa liczbę długości kodu.
int num_code_lengths = 4 + ReadBits(4);
Długości kodów są same kodowane za pomocą kodów prefiksów. Długości kodów niższego poziomu (code_length_code_lengths) trzeba najpierw odczytać. Pozostałe wartości code_length_code_lengths (zgodnie z kolejnością określoną w kCodeLengthCodeOrder) mają wartość zerową.
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 argument ReadBits(1) == 0, maksymalna liczba różnych symboli odczytu (max_symbol) dla każdego typu symbolu (A, R, G, B oraz odległości) jest ustawiana 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 zasada jest definiowana jako:
int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);
Jeśli max_symbol ma większy rozmiar niż rozmiar alfabetu dla danego typu symbolu, strumień bitów jest nieprawidłowy.
Następnie na podstawie code_length_code_lengths jest tworzona tabela z prefiksami i używana do odczytywania kodu o długości do max_symbol.
- Kod [0..15] wskazuje dosłowną długość kodu.
- Wartość 0 oznacza, że symbole nie zostały zakodowane.
- Wartości [1..15] wskazują długość bitów 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 innej niż 0, powtarza się wartość 8. - Kod 17 wyemituje serię zer o długości [3..10], czyli
3 + ReadBits(3)razy. - Kod 18 wyemituje serię zer o długości [11..138], czyli
11 + ReadBits(7)razy.
Po odczytaniu długości kodów tworzone są prefiksy poszczególnych typów symboli (A, R, G, B i odległości) z użyciem odpowiednich rozmiarów alfabetu.
Kod o normalnej długości kodu musi kodować pełne drzewo decyzyjne, czyli suma wartości 2 ^ (-length) dla wszystkich kodów innych niż zero musi wynosić dokładnie 1. Od tej reguły istnieje jednak jeden wyjątek: drzewo węzłów z pojedynczymi liśćmi, w którym wartość węzła liścia jest oznaczona wartością 1, a inne wartości – 0.
6.2.2 Dekodowanie kodów meta prefiksu
Jak już wspomnieliśmy, ten format umożliwia stosowanie różnych kodów prefiksów dla poszczególnych bloków obrazu. Kody prefiksów meta to indeksy identyfikujące kody prefiksów, które mają być używane w różnych częściach obrazu.
Kodów meta przedrostków można używać tylko wtedy, gdy obraz pełni rolę w obrazie ARGB.
Kody meta prefiksów wskazują 1-bitową wartość na 2 sposoby:
- Jeśli ten bit ma wartość zero, w całym obrazie w całym obrazie używany jest tylko 1 kod meta prefiksu. Dane nie są już zapisywane.
- Jeśli ten bit to 1, obraz używa wielu kodów z metatagów. Te kody metaprefiksów są przechowywane jako obraz entropii (opisany poniżej).
Czerwone i zielone komponenty piksela definiują 16-bitowy kod meta prefiksu używany w konkretnym 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 pochodzą 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 wartością zdefiniowaną wcześniej.
Następne bity zawierają entropję o szerokości prefix_image_width i wysokości prefix_image_height.
Interpretacja kodów meta prefiksów
Liczbę grup kodów prefiksów na obrazie ARGB można uzyskać, znajdując największy kod meta prefiksu w obrazie entropii:
int num_prefix_groups = max(entropy image) + 1;
gdzie max(entropy image) wskazuje największy kod prefiksu zapisany w obrazie entropii.
Ponieważ każda grupa kodów prefiksu zawiera 5 kodów prefiksów, łączna liczba tych kodó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 do wykorzystania 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];
Zakładamy w nim istnienie struktury PrefixCodeGroup, która reprezentuje zestaw 5 kodów prefiksów. Poza tym prefix_code_groups jest tablicą PrefixCodeGroup (o rozmiarze num_prefix_groups).
Następnie dekoder używa grupy kodów prefiksu prefix_group do dekodowania piksela (x, y), zgodnie z opisem w sekcji „Dekodowanie danych obrazu zakodowanych w entropii”.
6.2.3 Dekodowanie danych obrazu zakodowanych entropią
Dla bieżącej pozycji (x, y) na obrazie dekoder najpierw identyfikuje odpowiednią grupę kodów prefiksu (zgodnie z opisem w ostatniej sekcji). Z uwzględnieniem grupy kodów prefiksu piksel jest odczytywany i dekodowany w ten sposób.
Następnie odczytaj symbol S ze strumienia bitowego za pomocą kodu prefiksu 1. Pamiętaj, że S to dowolna liczba całkowita z zakresu od 0 do (256 + 24 + color_cache_size- 1).
Interpretacja symbolu S zależy od jego wartości:
- Jeśli S < 256
- Jako zielonego komponentu użyj S.
- Odczytuj dane na czerwono ze strumienia bitów, używając kodu prefiksu nr 2.
- Odczytuj dane na niebiesko ze strumienia bitów, używając kodu prefiksu 3.
- Odczytaj wersję alfa ze strumienia bitowego za pomocą kodu prefiksu nr 4.
- Jeśli S >= 256 & S < 256 + 24
- Jako kodu prefiksu długości użyj S-256.
- Odczytuj dodatkowe bity odpowiadające długości strumienia bitowego.
- Ustal długość odwołania wstecznego L na podstawie kodu prefiksu długości i odczytanych dodatkowych bitów.
- Odczytaj kod prefiksu odległości ze strumienia bitowego za pomocą kodu prefiksu 5.
- Odczytuj dodatkowe bity dotyczące odległości od strumienia bitowego.
- Wyznacz odległość D odniesienia wstecznego od kodu prefiksu odległości i odczytanych dodatkowych bitów.
- Skopiuj piksele L (w kolejności linii skanowania) z sekwencji pikseli zaczynając od bieżącej pozycji minus D pikseli.
- Jeśli S >= 256 + 24
- Użyj S- (256 + 24) jako indeksu w pamięci podręcznej kolorów.
- Pobierz kolor ARGB z pamięci podręcznej kolorów w tym indeksie.
7 Ogólna struktura formatu
Poniżej znajduje się przegląd formatu w rozszerzonej postaci Backusa-Naura (ABNF) RFC 5234 RFC 7405. Nie uwzględnia on wszystkich szczegółów. Koniec obrazu (EOI) jest domyślnie zakodowany w liczbie pikseli (szerokość_obrazu * wysokość_obrazu).
Pamiętaj, że *element oznacza, że element element może być powtórzony 0 lub więcej razy. 5element
oznacza, że element powtarza się dokładnie 5 razy. %b oznacza 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 Przekształceń
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