Spesifikasi untuk WebP Streamless WebP

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

Abstract

WebP lossless adalah format gambar untuk kompresi lossless gambar ARGB. Format lossless menyimpan dan memulihkan nilai piksel dengan tepat, termasuk nilai warna untuk piksel yang nilai alfanya 0. Format tersebut menggunakan gambar subresolusi, yang disematkan secara rekursif ke dalam format itu sendiri, untuk menyimpan data statistik tentang gambar, seperti kode entropi yang digunakan, prediktor spasial, konversi ruang warna, dan tabel warna. Algoritma universal untuk kompresi data berurutan (LZ77), coding awalan, dan cache warna digunakan untuk kompresi data massal. Kecepatan decoding yang lebih cepat daripada PNG telah ditunjukkan, serta kompresi 25% lebih padat daripada yang dapat dicapai dengan format PNG saat ini.

1 Pengantar

Dokumen ini menjelaskan representasi data terkompresi dari gambar WebP lossless. File ini dimaksudkan sebagai referensi mendetail untuk implementasi encoder dan decoder WebP lossless.

Dalam dokumen ini, kami secara ekstensif menggunakan sintaksis bahasa pemrograman C untuk mendeskripsikan bitstream dan mengasumsikan keberadaan fungsi untuk membaca bit, ReadBits(n). Byte dibaca dalam urutan alami pada aliran data yang memuatnya, dan bit setiap byte dibaca dalam urutan bit-first yang paling tidak signifikan. Jika beberapa bit dibaca secara bersamaan, bilangan bulat akan dibuat dari data asli dalam urutan aslinya. Bit yang paling signifikan dari bilangan bulat yang ditampilkan juga merupakan bit yang paling signifikan dari data asli. Sehingga, pernyataan

b = ReadBits(2);

setara dengan dua pernyataan berikut:

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

Kami berasumsi bahwa setiap komponen warna, yaitu alfa, merah, biru, dan hijau, diwakili menggunakan byte 8 bit. Kita mendefinisikan jenis yang sesuai sebagai uint8. Seluruh piksel ARGB direpresentasikan oleh jenis yang disebut uint32, yang merupakan bilangan bulat tanpa tanda tangan yang terdiri dari 32 bit. Dalam kode yang menunjukkan perilaku transformasi, nilai ini dikodifikasi dalam bit berikut: alfa dalam bit 31..24, merah dalam bit 23..16, hijau dalam bit 15..8, dan biru dalam bit 7..0; namun, implementasi format ini bebas untuk menggunakan representasi lain secara internal.

Umumnya, gambar lossless WebP berisi data header, informasi transformasi, dan data gambar sebenarnya. Header berisi lebar dan tinggi gambar. Gambar lossless WebP dapat melewati empat jenis transformasi yang berbeda sebelum dienkode entropi. Informasi transformasi dalam bitstream berisi data yang diperlukan untuk menerapkan masing-masing transformasi terbalik.

2 Nomenklatur

ARGB
Nilai piksel yang terdiri dari nilai alfa, merah, hijau, dan biru.
Gambar ARGB
Array dua dimensi yang berisi piksel ARGB.
cache warna
Array kecil dengan alamat hash untuk menyimpan warna yang baru-baru ini digunakan agar dapat memanggilnya kembali dengan kode yang lebih pendek.
gambar pengindeksan warna
Gambar warna satu dimensi yang dapat diindeks menggunakan bilangan bulat kecil (hingga 256 dalam WebP lossless).
gambar transformasi warna
Gambar subresolusi dua dimensi yang berisi data tentang korelasi komponen warna.
pemetaan jarak
Mengubah jarak LZ77 agar memiliki nilai terkecil untuk piksel dalam kedekatan dua dimensi.
gambar entropi
Gambar subresolusi dua dimensi yang menunjukkan coding entropi mana yang harus digunakan dalam persegi masing-masing dalam gambar, yaitu, setiap piksel adalah kode awalan meta.
LZ77
Algoritme kompresi jendela geser berbasis kamus yang memancarkan simbol atau mendeskripsikannya sebagai urutan simbol terdahulu.
Kode awalan meta
Bilangan bulat kecil (hingga 16 bit) yang mengindeks elemen dalam tabel awalan meta.
gambar prediktor
Gambar subresolusi dua dimensi yang menunjukkan prediktor spasial mana yang digunakan untuk persegi tertentu dalam gambar.
kode awalan
Cara klasik untuk melakukan coding entropi dengan jumlah bit yang lebih kecil digunakan untuk kode yang lebih sering.
coding awalan
Cara untuk melakukan entropi kode bilangan bulat yang lebih besar, yang mengkodekan beberapa bit bilangan bulat menggunakan kode entropi dan mengkodekan bit yang tersisa secara mentah. Hal ini memungkinkan deskripsi kode entropi tetap relatif kecil meskipun rentang simbol besar.
urutan pemindaian
Urutan pemrosesan piksel (kiri ke kanan dan atas ke bawah), mulai dari piksel kiri atas. Setelah satu baris selesai, lanjutkan dari kolom sebelah kiri baris berikutnya.

3 Header RIFF

Bagian awal {i>header<i} berisi penampung RIFF. Proses ini terdiri dari 21 byte berikut:

  1. String 'RIFF'.
  2. Nilai kecil 32-bit dari panjang potongan, yang merupakan seluruh ukuran potongan yang dikontrol oleh header RIFF. Biasanya, ini sama dengan ukuran payload (ukuran file minus 8 byte: 4 byte untuk ID 'RIFF' dan 4 byte untuk menyimpan nilai itu sendiri).
  3. String 'WEBP' (nama penampung RIFF).
  4. String 'VP8L' (FourCC untuk data gambar dengan enkode lossless).
  5. Nilai 32-bit kecil-endian dari jumlah byte dalam aliran lossless.
  6. Tanda tangan 1-byte 0x2f.

28 bit pertama dari bitstream menentukan lebar dan tinggi gambar. Lebar dan tinggi didekode sebagai bilangan bulat 14-bit sebagai berikut:

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

Presisi 14-bit untuk lebar dan tinggi gambar membatasi ukuran maksimum gambar WebP lossless hingga 16384hingga 16384 piksel.

Bit alpha_is_used hanya merupakan petunjuk, dan tidak boleh memengaruhi decoding. Nilai ini harus disetel ke 0 jika semua nilai alfa dalam gambar adalah 255, dan 1 jika tidak dalam gambar.

int alpha_is_used = ReadBits(1);

version_number adalah kode 3 bit yang harus diatur ke 0. Nilai lain harus diperlakukan sebagai error.

int version_number = ReadBits(3);

4 Transformasi

Transformasi adalah manipulasi yang dapat dibalik pada data gambar yang dapat mengurangi entropi simbolis yang tersisa dengan memodelkan korelasi spasial dan warna. Filter dapat membuat kompresi akhir lebih padat.

Gambar dapat melalui empat jenis transformasi. Satu bit menunjukkan adanya transformasi. Setiap transformasi hanya diizinkan untuk digunakan satu kali. Transformasi hanya digunakan untuk gambar ARGB level utama; gambar sub-resolusi (gambar transformasi warna, gambar entropi, dan gambar prediktor) tidak memiliki transformasi, bahkan 0 bit yang menunjukkan akhir transformasi.

Biasanya, encoder akan menggunakan transformasi ini untuk mengurangi entropi Shannon pada gambar residual. Selain itu, data transformasi dapat ditentukan berdasarkan meminimalkan entropi.

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

// Decode actual image data (Section 5).

Jika ada transformasi, dua bit berikutnya akan menentukan jenis transformasi. Ada empat jenis transformasi.

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

Jenis transformasi diikuti dengan data transformasi. Data transformasi berisi informasi yang diperlukan untuk menerapkan transformasi terbalik dan bergantung pada jenis transformasi. Transformasi terbalik diterapkan dalam urutan terbalik yang dibaca dari bitstream, yaitu yang terakhir terlebih dahulu.

Selanjutnya, kami menjelaskan data transformasi untuk berbagai jenis.

4.1 Transformasi Prediktor

Transformasi prediktor dapat digunakan untuk mengurangi entropi dengan memanfaatkan fakta bahwa piksel di sekitar sering kali berkorelasi. Pada transformasi prediktor, nilai piksel saat ini diprediksi dari piksel yang telah didekode (dalam urutan baris pemindaian) dan hanya nilai residual (aktual - diprediksi) yang dienkode. Komponen hijau dari piksel menentukan mana dari 14 prediktor yang digunakan dalam blok tertentu dari gambar ARGB. Mode prediksi menentukan jenis prediksi yang akan digunakan. Kita membagi gambar menjadi kotak, dan semua piksel dalam persegi menggunakan mode prediksi yang sama.

3 bit pertama data prediksi menentukan lebar dan tinggi blok dalam jumlah bit. Jumlah kolom blok, block_xsize, digunakan dalam pengindeksan dua dimensi.

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 block_xsize = DIV_ROUND_UP(image_width, 1 << size_bits);

Data transformasi berisi mode prediksi untuk setiap blok gambar. Ini adalah gambar subresolusi dengan komponen piksel hijau menentukan mana dari 14 prediktor yang digunakan untuk semua piksel block_width * block_height dalam blok tertentu gambar ARGB. Gambar subresolusi ini dienkode menggunakan teknik yang sama seperti yang dijelaskan dalam Bab 5.

Untuk piksel (x, y), pengguna dapat menghitung alamat blok filter masing-masing dengan:

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

Ada 14 mode prediksi yang berbeda. Pada setiap mode prediksi, nilai piksel saat ini diprediksi dari satu atau beberapa piksel tetangga yang nilainya sudah diketahui.

Kita memilih piksel di dekatnya (TL, T, TR, dan L) dari piksel saat ini (P) sebagai berikut:

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

di mana TL berarti kiri atas, T berarti atas, TR berarti kanan atas, dan L berarti kiri. Pada saat memprediksi nilai P, semua piksel O, TL, T, TR, dan L sudah diproses, dan piksel P serta semua piksel X tidak diketahui.

Dengan mempertimbangkan piksel di dekatnya, mode prediksi yang berbeda ditentukan sebagai berikut.

Mode Prediksi nilai setiap saluran piksel saat ini
0 0xff000000 (mewakili warna hitam solid dalam ARGB)
1 L
2 T
3 TR
4 TL
5 Rata-rata2(Rata-Rata2(L, TR), T)
6 Rata-Rata2(L, TL)
7 Rata-Rata2(L, T)
8 Rata-Rata2(TL, T)
9 Rata-Rata2(T, TR)
10 Rata-rata2(Rata-rata2(L, TL), Rata-rata2(T, TR))
11 Select(L, T, TL)
12 ClampAddSubtractFull(L, T, TL)
13 ClampAddSubtractHalf(Rata-Rata2(L, T), TL)

Average2 ditentukan sebagai berikut untuk setiap komponen ARGB:

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

Prediktor Pilih ditentukan sebagai berikut:

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

Fungsi ClampAddSubtractFull dan ClampAddSubtractHalf dijalankan untuk setiap komponen ARGB sebagai berikut:

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

Ada aturan penanganan khusus untuk beberapa piksel batas. Jika ada transformasi prediksi, terlepas dari mode [0..13] untuk piksel ini, maka prediksi nilai untuk piksel paling atas kiri gambar adalah 0xff000000, semua piksel di baris atas adalah L-piksel, dan semua piksel di kolom paling kiri adalah T-piksel.

Menangani piksel TR untuk piksel di kolom paling kanan sangat luar biasa. Piksel di kolom paling kanan diprediksi menggunakan mode [0..13], seperti piksel yang tidak berada pada batas, tetapi piksel paling kiri pada baris yang sama dengan piksel saat ini digunakan sebagai piksel TR.

Nilai piksel akhir diperoleh dengan menambahkan setiap saluran nilai yang diprediksi ke nilai residual yang dienkode.

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 Transformasi Warna

Tujuan transformasi warna adalah untuk mendekorasi hubungan nilai-nilai R, G, dan B dari setiap piksel. Transformasi warna mempertahankan nilai hijau (G) sebagaimana adanya, mengubah nilai merah (R) berdasarkan nilai hijau, dan mengubah nilai biru (B) berdasarkan nilai hijau dan kemudian nilai merah.

Seperti halnya pada transformasi prediktor, pertama-tama gambar dibagi menjadi blok dan mode transformasi yang sama digunakan untuk semua piksel dalam blok. Untuk setiap blok, ada tiga jenis elemen transformasi warna.

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

Transformasi warna sebenarnya dilakukan dengan menentukan delta transformasi warna. Delta transformasi warna bergantung pada ColorTransformElement, yang sama untuk semua piksel dalam blok tertentu. Delta dikurangkan selama transformasi warna. Kemudian, transformasi warna terbalik hanya menambahkan delta tersebut.

Fungsi transformasi warna ditentukan sebagai berikut:

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 dihitung menggunakan bilangan bulat 8-bit bertanda yang merepresentasikan angka 3,5 titik tetap dan saluran warna RGB 8-bit bertanda tangan (c) [-128..127] dan ditentukan sebagai berikut:

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

Konversi dari representasi 8-bit tanpa tanda tangan (uint8) ke representasi 8-bit yang ditandatangani (int8) diperlukan sebelum memanggil ColorTransformDelta(). Nilai yang ditandatangani harus ditafsirkan sebagai bilangan pelengkap dua 8-bit (yaitu: rentang uint8 [128..255] dipetakan ke rentang [-128..-1] dari nilai int8 yang dikonversi).

Perkalian harus dilakukan secara lebih presisi (dengan presisi setidaknya 16-bit). Properti ekstensi tanda dari operasi pergeseran tidak penting di sini; hanya 8 bit terendah yang digunakan dari hasil, dan di sana pergeseran ekstensi tanda dan pergeseran yang tidak ditandatangani bersifat konsisten satu sama lain.

Sekarang, kita akan menjelaskan konten data transformasi warna sehingga decoding dapat menerapkan transformasi warna terbalik dan memulihkan nilai merah dan biru yang asli. Tiga bit pertama dari data transformasi warna berisi lebar dan tinggi blok gambar dalam jumlah bit, seperti halnya transformasi prediktor:

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

Bagian yang tersisa dari data transformasi warna berisi instance ColorTransformElement, yang sesuai dengan setiap blok gambar. Setiap ColorTransformElement 'cte' diperlakukan sebagai piksel dalam gambar subresolusi yang komponen alfanya adalah 255, komponen merah adalah cte.red_to_blue, komponen hijau adalah cte.green_to_blue, dan komponen biru adalah cte.green_to_red.

Selama decoding, instance ColorTransformElement blok didekode dan transformasi warna terbalik diterapkan pada nilai ARGB piksel. Seperti yang disebutkan sebelumnya, transformasi warna terbalik hanya menambahkan nilai ColorTransformElement ke saluran merah dan biru. Saluran alfa dan hijau tidak akan diubah.

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 Mengurangi Transformasi Hijau

Transformasi hijau mengurangi nilai hijau dari nilai merah dan biru dari setiap piksel. Jika transformasi ini ada, decoder harus menambahkan nilai hijau ke nilai merah dan biru. Tidak ada data yang terkait dengan transformasi ini. Decoder menerapkan transformasi terbalik sebagai berikut:

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

Transformasi ini redundan, karena dapat dimodelkan menggunakan transformasi warna, tetapi karena tidak ada data tambahan di sini, transformasi pengurangan hijau dapat dikodekan menggunakan lebih sedikit bit daripada transformasi warna full-blown.

4.4 Transformasi Pengindeksan Warna

Jika tidak ada banyak nilai piksel unik, mungkin akan lebih efisien untuk membuat array indeks warna dan mengganti nilai piksel dengan indeks array. Transformasi pengindeksan warna mencapai hal ini. (Dalam konteks WebP lossless, kami secara khusus tidak menyebut ini sebagai transformasi palet karena konsep yang serupa tetapi lebih dinamis ada dalam encoding lossless WebP: cache warna.)

Transformasi pengindeksan warna memeriksa jumlah nilai ARGB unik dalam gambar. Jika angka tersebut di bawah ambang batas (256), array nilai ARGB akan dibuat, yang kemudian digunakan untuk mengganti nilai piksel dengan indeks terkait: saluran hijau piksel diganti dengan indeks, semua nilai alfa disetel ke 255, dan semua nilai merah dan biru ke 0.

Data transformasi berisi ukuran tabel warna dan entri dalam tabel warna. Decoder membaca data transformasi pengindeksan warna sebagai berikut:

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

Tabel warna disimpan menggunakan format penyimpanan gambar itu sendiri. Tabel warna dapat diperoleh dengan membaca gambar, tanpa header RIFF, ukuran gambar, dan transformasi, dengan asumsi tinggi 1 piksel dan lebar color_table_size. Tabel warna selalu diberi kode pengurangan untuk mengurangi entropi gambar. Delta warna palet biasanya berisi entropi yang jauh lebih sedikit daripada warna itu sendiri, sehingga dapat menghemat signifikan untuk gambar yang lebih kecil. Dalam decoding, setiap warna akhir dalam tabel warna dapat diperoleh dengan menambahkan nilai komponen warna sebelumnya oleh setiap komponen ARGB secara terpisah, dan menyimpan hasil 8 bit yang paling tidak signifikan.

Transformasi terbalik untuk gambar hanya mengganti nilai piksel (yang merupakan indeks tabel warna) dengan nilai tabel warna sebenarnya. Pengindeksan dilakukan berdasarkan komponen hijau dari warna ARGB.

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

Jika indeks sama dengan atau lebih besar dari color_table_size, nilai warna aRGB harus disetel ke 0x00000000 (hitam transparan).

Jika tabel warna berukuran kecil (sama dengan atau kurang dari 16 warna), beberapa piksel akan dipaketkan menjadi satu piksel. Paket piksel menggabungkan beberapa (2, 4, atau 8) piksel menjadi satu piksel, yang masing-masing mengurangi lebar gambar. Pemaketan piksel memungkinkan coding entropi distribusi gabungan yang lebih efisien pada piksel di dekatnya dan memberikan beberapa manfaat seperti coding aritmetika pada kode entropi, tetapi hanya dapat digunakan jika ada 16 nilai unik atau kurang.

color_table_size menentukan jumlah piksel yang digabungkan:

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 memiliki nilai 0, 1, 2, atau 3. Nilai 0 menunjukkan tidak ada pemaketan piksel yang harus dilakukan untuk gambar. Nilai 1 menunjukkan bahwa dua piksel digabungkan, dan setiap piksel memiliki rentang [0..15]. Nilai 2 menunjukkan bahwa empat piksel digabungkan, dan setiap piksel memiliki rentang [0..3]. Nilai 3 menunjukkan bahwa delapan piksel digabungkan dan setiap piksel memiliki rentang [0..1], yaitu nilai biner.

Nilai dikemas ke dalam komponen hijau sebagai berikut:

  • width_bits = 1: Untuk setiap nilai x, dengan x ≡ 0 (mod 2), nilai hijau di x diposisikan ke dalam 4 bit paling tidak signifikan dari nilai hijau di x / 2, dan nilai hijau pada x + 1 diposisikan ke dalam 4 bit paling signifikan dari nilai hijau di x / 2.
  • width_bits = 2: Untuk setiap nilai x, dengan x ≡ 0 (mod 4), nilai hijau di x diposisikan ke dalam 2 bit yang paling tidak signifikan dari nilai hijau di x / 4, dan nilai hijau pada x + 1 hingga x + 3 diposisikan sesuai dengan bit nilai hijau yang lebih signifikan di x / 4.
  • width_bits = 3: Untuk setiap nilai x, dengan x ≡ 0 (mod 8), nilai hijau di x diposisikan di bit nilai hijau yang paling tidak signifikan pada x / 8, dan nilai hijau pada x + 1 hingga x + 7 diposisikan dalam urutan untuk bit nilai hijau yang lebih signifikan di x / 8.

Setelah membaca transformasi ini, image_width akan disubsampel oleh width_bits. Hal ini memengaruhi ukuran transformasi berikutnya. Ukuran baru dapat dihitung menggunakan DIV_ROUND_UP, seperti yang ditentukan sebelumnya.

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

5 Data Gambar

Data gambar adalah array nilai piksel dalam urutan garis pemindaian.

5.1 Peran Data Gambar

Kami menggunakan data gambar dalam lima peran yang berbeda:

  1. Gambar ARGB: Menyimpan piksel gambar yang sebenarnya.
  2. Image entropi: Menyimpan kode awalan meta (lihat "Decoding Kode Awalan Meta").
  3. Gambar prediktif: Menyimpan metadata untuk transformasi prediktor (lihat "Transformasi Prediktor").
  4. Gambar transformasi warna: Dibuat oleh nilai ColorTransformElement (didefinisikan dalam "Transformasi Warna") untuk berbagai blok gambar.
  5. Gambar pengindeksan warna: Array dengan ukuran color_table_size (hingga 256 nilai ARGB) yang menyimpan metadata untuk transformasi pengindeksan warna (lihat "Color Indexing Transform").

5.2 Encoding Data Gambar

Encoding data gambar tidak bergantung pada perannya.

Pertama-tama, gambar dibagi menjadi satu set blok berukuran tetap (biasanya 16x16 blok). Setiap blok ini dimodelkan menggunakan kode entropinya sendiri. Selain itu, beberapa blok dapat memiliki kode entropi yang sama.

Rasional: Penyimpanan kode entropi akan dikenai biaya. Biaya ini dapat diminimalkan jika blok yang serupa secara statistik berbagi kode entropi, sehingga kode tersebut hanya disimpan sekali. Misalnya, encoder dapat menemukan blok serupa dengan mengelompokkannya menggunakan properti statistiknya atau dengan berulang kali menggabungkan sepasang cluster yang dipilih secara acak saat mengurangi jumlah keseluruhan bit yang diperlukan untuk mengenkode gambar.

Setiap piksel dienkode menggunakan salah satu dari tiga metode yang dapat digunakan:

  1. Literal kode awal: Setiap saluran (hijau, merah, biru, dan alfa) dikodekan secara entropi secara terpisah.
  2. Referensi mundur LZ77: Urutan piksel disalin dari tempat lain dalam gambar.
  3. Kode cache warna: Menggunakan kode hash multiplikatif singkat (indeks cache warna) dari warna yang baru dilihat.

Sub-bagian berikut menjelaskan setiap hal tersebut secara mendetail.

5.2.1 Literal Kode Awal

Piksel disimpan sebagai nilai berkode awalan warna hijau, merah, biru, dan alfa (dalam urutan tersebut). Lihat Pasal 6.2.3 untuk mengetahui detailnya.

5.2.2 Referensi Mundur LZ77

Referensi mundur adalah tupel panjang dan kode jarak:

  • Panjang menunjukkan jumlah piksel dalam urutan baris pemindaian yang akan disalin.
  • Kode jarak adalah angka yang menunjukkan posisi piksel yang terlihat sebelumnya, tempat piksel yang akan disalin. Pemetaan persisnya dijelaskan di bawah.

Nilai panjang dan jarak disimpan menggunakan Coding awalan LZ77.

Coding awalan LZ77 membagi nilai bilangan bulat besar menjadi dua bagian: kode awalan dan bit tambahan. Kode awalan disimpan menggunakan kode entropi, sedangkan bit tambahan disimpan sebagaimana adanya (tanpa kode entropi).

Rasionale: Pendekatan ini mengurangi persyaratan penyimpanan untuk kode entropi. Selain itu, nilai besar biasanya jarang muncul, sehingga bit tambahan akan digunakan untuk beberapa nilai dalam gambar. Dengan demikian, pendekatan ini menghasilkan kompresi yang lebih baik secara keseluruhan.

Tabel berikut menunjukkan kode awalan dan bit tambahan yang digunakan untuk menyimpan rentang nilai yang berbeda.

Rentang nilai Kode awalan Bit tambahan
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

Kode semu untuk mendapatkan nilai (panjang atau jarak) dari kode awalan adalah sebagai berikut:

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;
Pemetaan Jarak

Seperti yang telah disebutkan sebelumnya, kode jarak adalah angka yang menunjukkan posisi piksel yang terlihat sebelumnya, tempat piksel akan disalin. Subbagian ini menentukan pemetaan antara kode jarak dan posisi piksel sebelumnya.

Kode jarak yang lebih besar dari 120 menunjukkan jarak piksel dalam urutan garis pemindaian, offset 120.

Kode jarak terkecil [1..120] bersifat khusus dan disediakan untuk lingkungan yang dekat dari piksel saat ini. Lingkungan ini terdiri dari 120 piksel:

  • Piksel yang berjarak 1 hingga 7 baris di atas piksel saat ini dan merupakan hingga 8 kolom di sebelah kiri atau hingga 7 kolom di sebelah kanan piksel saat ini. [Total piksel tersebut = 7 * (8 + 1 + 7) = 112].
  • Piksel yang berada di baris yang sama dengan piksel saat ini dan berjarak hingga 8 kolom di sebelah kiri piksel saat ini. [8 piksel tersebut].

Pemetaan antara kode jarak i dan offset piksel di dekatnya (xi, yi) adalah sebagai berikut:

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

Misalnya, kode jarak 1 menunjukkan offset (0, 1) untuk piksel di dekatnya, yaitu piksel di atas piksel saat ini (perbedaan 0 piksel dalam arah X dan perbedaan 1 piksel pada arah Y). Demikian pula, kode jarak 3 menunjukkan piksel kiri atas.

Decoder dapat mengonversi kode jarak i menjadi jarak urutan garis pemindaian dist sebagai berikut:

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

dengan distance_map adalah pemetaan yang disebutkan di atas, dan xsize adalah lebar gambar dalam piksel.

5.2.3 Pengkodean Cache Warna

Cache warna menyimpan serangkaian warna yang baru-baru ini digunakan dalam gambar.

Rasional: Dengan cara ini, warna yang baru-baru ini digunakan terkadang dapat dirujuk secara lebih efisien daripada memunculkannya menggunakan dua metode lainnya (dijelaskan dalam 5.2.1 dan 5.2.2).

Kode cache warna disimpan sebagai berikut. Pertama, ada nilai 1-bit yang menunjukkan apakah cache warna digunakan. Jika bit ini 0, tidak ada kode cache warna dan kode tersebut tidak akan ditransmisikan dalam kode awalan yang mendekode simbol hijau dan kode awalan panjang. Namun, jika bit ini adalah 1, ukuran cache warna akan dibaca berikutnya:

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

color_cache_code_bits menentukan ukuran cache warna (1 << color_cache_code_bits). Rentang nilai yang diizinkan untuk color_cache_code_bits adalah [1..11]. Decoder yang mematuhi kebijakan harus menunjukkan bitstream yang rusak untuk nilai lain.

Cache warna adalah array ukuran color_cache_size. Setiap entri menyimpan satu warna ARGB. Warna dicari dengan mengindeksnya berdasarkan (0x1e35a7bd * color) >> (32 - color_cache_code_bits). Hanya satu pencarian yang dilakukan dalam cache warna; tidak ada penyelesaian konflik.

Pada awal decoding atau encoding gambar, semua entri dalam semua nilai cache warna ditetapkan ke nol. Kode cache warna dikonversi ke warna ini pada waktu decoding. Status cache warna dipertahankan dengan memasukkan setiap piksel, baik yang dihasilkan oleh referensi mundur maupun sebagai literal, ke dalam cache sesuai urutan kemunculannya dalam aliran.

6 Kode Entropi

6.1 Ringkasan

Sebagian besar data dikodekan menggunakan kode awalan kanonis. Oleh karena itu, kode tersebut dikirim dengan mengirimkan panjang kode awalan, berbeda dengan kode awalan yang sebenarnya.

Secara khusus, format tersebut menggunakan coding awalan varian spasial. Dengan kata lain, blok gambar yang berbeda berpotensi menggunakan kode entropi yang berbeda.

Rasional: Area gambar yang berbeda mungkin memiliki karakteristik yang berbeda. Jadi, mengizinkan entropi menggunakan kode entropi yang berbeda akan memberikan fleksibilitas yang lebih besar dan kompresi yang berpotensi lebih baik.

6.2 Rincian

Data gambar yang dienkode terdiri dari beberapa bagian:

  1. Mendekode dan membuat kode awalan.
  2. Kode awalan meta.
  3. Data gambar berkode entropi.

Untuk piksel tertentu (x, y), ada sekumpulan lima kode awalan yang terkait dengannya. Kode ini adalah (dalam urutan bitstream):

  • Kode awalan #1: Digunakan untuk saluran hijau, panjang referensi mundur, dan cache warna.
  • Kode awalan #2, #3, dan #4: Digunakan masing-masing untuk saluran merah, biru, dan alfa.
  • Kode awalan #5: Digunakan untuk jarak referensi mundur.

Selanjutnya, kami menyebut kumpulan tersebut sebagai grup kode awalan.

6.2.1 Mendekode dan Membuat Kode Awalan

Bagian ini menjelaskan cara membaca panjang kode awalan dari bitstream.

Panjang kode awalan dapat dikodekan dengan dua cara. Metode yang digunakan ditetapkan oleh nilai 1-bit.

  • Jika bit ini adalah 1, berarti kode panjang kode sederhana.
  • Jika bit ini 0, berarti kode panjang kode normal.

Dalam kedua kasus tersebut, mungkin ada panjang kode yang tidak digunakan yang masih menjadi bagian dari aliran. Hal ini mungkin tidak efisien, tetapi diizinkan oleh format. Hierarki yang dijelaskan harus berupa hierarki biner lengkap. Node leaf tunggal dianggap sebagai hierarki biner lengkap dan dapat dienkode menggunakan kode panjang kode sederhana atau kode panjang kode normal. Saat melakukan coding pada satu node leaf menggunakan kode panjang kode normal, semua kecuali satu panjang kode adalah nol, dan nilai node daun tunggal ditandai dengan panjang 1 -- bahkan jika tidak ada bit yang digunakan saat pohon node satu daun tersebut digunakan.

Kode Panjang Kode Sederhana

Varian ini digunakan dalam kasus khusus jika hanya 1 atau 2 simbol awalan yang berada dalam rentang [0..255] dengan panjang kode 1. Semua panjang kode awalan lainnya secara implisit adalah nol.

Bit pertama menunjukkan jumlah simbol:

int num_symbols = ReadBits(1) + 1;

Berikut ini adalah nilai simbol.

Simbol pertama ini dikodekan menggunakan 1 atau 8 bit, bergantung pada nilai is_first_8bits. Rentangnya adalah [0..1] atau [0..255]. Simbol kedua, jika ada, selalu diasumsikan berada dalam rentang [0..255] dan dikodekan menggunakan 8 bit.

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

Kedua simbol tersebut harus berbeda. Simbol duplikat diizinkan, tetapi tidak efisien.

Catatan: Kasus khusus lainnya adalah jika semua panjang kode awalan adalah nol (kode awalan kosong). Misalnya, kode awalan untuk jarak bisa kosong jika tidak ada referensi mundur. Demikian pula, kode awalan untuk alfa, merah, dan biru dapat kosong jika semua piksel dalam kode awalan meta yang sama dihasilkan menggunakan cache warna. Namun, kasus ini tidak memerlukan penanganan khusus, karena kode awalan kosong dapat dikodekan sebagai kode yang berisi satu simbol 0.

Kode Panjang Kode Normal

Panjang kode awalan sesuai 8 bit dan dibaca sebagai berikut. Pertama, num_code_lengths menentukan jumlah panjang kode.

int num_code_lengths = 4 + ReadBits(4);

Panjang kode itu sendiri dienkode menggunakan kode awalan; panjang kode pada tingkat yang lebih rendah, code_length_code_lengths, harus dibaca terlebih dahulu. Sisa dari code_length_code_lengths itu (sesuai dengan urutan dalam kCodeLengthCodeOrder) adalah nol.

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

Berikutnya, jika ReadBits(1) == 0, jumlah maksimum simbol baca yang berbeda (max_symbol) untuk setiap jenis simbol (A, R, G, B, dan jarak) ditetapkan ke ukuran alfabet:

  • Saluran G: 256 + 24 + color_cache_size
  • Literal lain (A, R, dan B): 256
  • Kode jarak: 40

Jika tidak, ini akan didefinisikan sebagai:

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

Jika max_symbol lebih besar dari ukuran alfabet untuk jenis simbol, bitstream tidak akan valid.

Tabel awalan kemudian dibuat dari code_length_code_lengths dan digunakan untuk membaca hingga panjang kode max_symbol.

  • Kode [0..15] menunjukkan panjang kode literal.
    • Nilai 0 berarti tidak ada simbol yang dikodekan.
    • Nilai [1..15] menunjukkan panjang bit kode masing-masing.
  • Kode 16 mengulangi nilai bukan nol sebelumnya [3..6] kali, yaitu, 3 + ReadBits(2) kali. Jika kode 16 digunakan sebelum nilai bukan nol yang dimunculkan, nilai 8 akan diulang.
  • Kode 17 memunculkan garis dengan panjang nol [3..10], yaitu, 3 + ReadBits(3) kali.
  • Kode 18 memunculkan garis dengan panjang nol [11..138], yaitu, 11 + ReadBits(7) kali.

Setelah panjang kode dibaca, kode awalan untuk setiap jenis simbol (A, R, G, B, dan jarak) akan dibuat menggunakan ukuran alfabet masing-masing.

Kode Panjang Kode Normal harus mengkodekan pohon keputusan lengkap, yaitu, jumlah 2 ^ (-length) untuk semua kode bukan nol harus tepat satu. Namun, ada satu pengecualian untuk aturan ini, pohon node daun tunggal, dengan nilai node leaf ditandai dengan nilai 1 dan nilai-nilai lainnya adalah 0s.

6.2.2 Dekode Kode Awalan Meta

Seperti yang telah disebutkan sebelumnya, format ini memungkinkan penggunaan kode awalan yang berbeda untuk blok gambar yang berbeda. Kode awalan meta adalah indeks yang mengidentifikasi kode awalan yang akan digunakan di berbagai bagian gambar.

Kode awalan meta dapat digunakan hanya jika gambar digunakan dalam peran gambar ARGB.

Ada dua kemungkinan untuk kode awalan meta, yang ditunjukkan oleh nilai 1-bit:

  • Jika bit ini nol, hanya ada satu kode awalan meta yang digunakan di mana pun dalam image. Tidak ada lagi data yang disimpan.
  • Jika bit ini satu, image menggunakan beberapa kode awalan meta. Kode awalan meta ini disimpan sebagai image entropi (dijelaskan di bawah).

Komponen merah dan hijau dari sebuah piksel menentukan kode awalan meta 16-bit yang digunakan dalam blok tertentu dari gambar ARGB.

Gambar Entropi

Gambar entropi menentukan kode awalan mana yang digunakan di berbagai bagian gambar.

3 bit pertama berisi nilai prefix_bits. Dimensi gambar entropi berasal dari prefix_bits:

int prefix_bits = ReadBits(3) + 2;
int prefix_xsize = DIV_ROUND_UP(xsize, 1 << prefix_bits);
int prefix_ysize = DIV_ROUND_UP(ysize, 1 << prefix_bits);

dengan DIV_ROUND_UP seperti yang ditentukan sebelumnya.

Bit berikutnya berisi gambar entropi dengan lebar prefix_xsize dan tinggi prefix_ysize.

Penafsiran Kode Awalan Meta

Jumlah grup kode awalan dalam gambar ARGB dapat diperoleh dengan mencari kode awalan meta terbesar dari gambar entropi:

int num_prefix_groups = max(entropy image) + 1;

dengan max(entropy image) menunjukkan kode awalan terbesar yang disimpan dalam image entropi.

Karena setiap grup kode awalan berisi lima kode awalan, jumlah total kode awalan adalah:

int num_prefix_codes = 5 * num_prefix_groups;

Dengan mempertimbangkan piksel (x, y) dalam gambar ARGB, kita bisa memperoleh kode awalan yang sesuai untuk digunakan sebagai berikut:

int position =
    (y >> prefix_bits) * prefix_xsize + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[position] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];

tempat kita mengasumsikan keberadaan struktur PrefixCodeGroup, yang mewakili sekumpulan lima kode awalan. Selain itu, prefix_code_groups adalah array dari PrefixCodeGroup (dengan ukuran num_prefix_groups).

Decoder kemudian menggunakan grup kode awalan prefix_group untuk mendekode piksel (x, y), seperti yang dijelaskan dalam "Mendekode Data Gambar Entropi".

6.2.3 Mendekode Data Gambar Entropi

Untuk posisi saat ini (x, y) pada gambar, decoder terlebih dahulu mengidentifikasi grup kode awalan yang sesuai (seperti yang dijelaskan di bagian terakhir). Dengan grup kode awalan, piksel akan dibaca dan didekode sebagai berikut.

Selanjutnya, baca simbol S dari bitstream menggunakan kode awalan #1. Perhatikan bahwa S adalah bilangan bulat dalam rentang 0 hingga (256 + 24 + color_cache_size- 1).

Penafsiran S bergantung pada nilainya:

  1. Jika S < 256
    1. Gunakan S sebagai komponen hijau.
    2. Membaca warna merah dari bitstream menggunakan kode awalan #2.
    3. Membaca warna biru dari bitstream menggunakan kode awalan #3.
    4. Membaca alfa dari bitstream menggunakan kode awalan #4.
  2. Jika S >= 256 & S < 256 + 24
    1. Gunakan S - 256 sebagai kode awalan yang panjang.
    2. Membaca bit tambahan untuk panjang dari bitstream.
    3. Tentukan panjang referensi mundur L dari kode awalan yang panjang dan bit tambahan yang dibaca.
    4. Baca kode awalan jarak dari bitstream menggunakan kode awalan #5.
    5. Membaca bit tambahan untuk jarak dari bitstream.
    6. Tentukan jarak referensi mundur D dari kode awalan jarak dan bit tambahan yang dibaca.
    7. Salin piksel L (dalam urutan garis pemindaian) dari urutan piksel yang dimulai pada posisi saat ini dikurangi D piksel.
  3. Jika S >= 256 + 24
    1. Gunakan S - (256 + 24) sebagai indeks ke dalam cache warna.
    2. Mendapatkan warna ARGB dari cache warna pada indeks tersebut.

7 Struktur Format Keseluruhan

Berikut adalah tampilan dalam format dalam Augmented Backus-Naur Form (ABNF) RFC 5234 RFC 7405. Artikel ini tidak mencakup semua detail. Akhir gambar (EOI) hanya dikodekan secara implisit ke dalam jumlah piksel (xsize * ysize).

Perhatikan bahwa *element berarti element dapat diulang 0 kali atau lebih. 5element berarti element diulang tepat 5 kali. %b merepresentasikan nilai biner.

7.1 Struktur Dasar

format        = RIFF-header image-header image-stream
RIFF-header   = %s"RIFF" 4OCTET %s"WEBPVP8L" 4OCTET
image-header  = %x2F image-size alpha-is-used version
image-size    = 14BIT 14BIT ; width - 1, height - 1
alpha-is-used = 1BIT
version       = 3BIT ; 0
image-stream  = optional-transform spatially-coded-image

7.2 Struktur Transformasi

optional-transform   =  (%b1 transform optional-transform) / %b0
transform            =  predictor-tx / color-tx / subtract-green-tx
transform            =/ color-indexing-tx

predictor-tx         =  %b00 predictor-image
predictor-image      =  3BIT ; sub-pixel code
                        entropy-coded-image

color-tx             =  %b01 color-image
color-image          =  3BIT ; sub-pixel code
                        entropy-coded-image

subtract-green-tx    =  %b10

color-indexing-tx    =  %b11 color-indexing-image
color-indexing-image =  8BIT ; color count
                        entropy-coded-image

7.3 Struktur Data Gambar

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)

Berikut ini adalah contoh urutan yang mungkin:

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