Spesifikasi Bitstream Lossless WebP

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

Abstrak

WebP lossless adalah format gambar untuk kompresi lossless gambar ARGB. Tujuan format lossless menyimpan dan memulihkan nilai piksel dengan tepat, termasuk nilai warna untuk piksel yang sepenuhnya transparan. Algoritma universal untuk sekuensial kompresi data (LZ77), pengkodean awalan, dan cache warna digunakan untuk kompresi data massal. Kecepatan dekode yang lebih cepat daripada PNG telah serta kompresi 25% lebih padat daripada yang dapat dicapai menggunakan format PNG saat ini.

1 Pengantar

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

Dalam dokumen ini, kami menggunakan sintaks bahasa pemrograman C secara ekstensif untuk menggambarkan bitstream dan mengasumsikan keberadaan fungsi untuk membaca bit, ReadBits(n). Byte dibaca dalam urutan alami dari stream yang berisi mereka, dan bit setiap byte dibaca dalam urutan yang paling tidak signifikan-bit-first. Kapan beberapa bit dibaca pada saat yang sama, integer dibuat dari data asli dalam urutan aslinya. Bit paling signifikan dari data yang ditampilkan bilangan bulat juga merupakan bit yang paling signifikan dari data asli. Dengan demikian, pernyataan

b = ReadBits(2);

setara dengan dua pernyataan di bawah ini:

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

Kita berasumsi bahwa setiap komponen warna, yaitu, {i>alpha<i}, merah, biru, dan hijau, adalah diwakili menggunakan byte 8-bit. Kami menentukan jenis yang sesuai sebagai uint8. J seluruh piksel ARGB diwakili oleh jenis yang disebut {i>uint32<i}, yang merupakan yang terdiri atas 32 bit. Dalam kode yang menunjukkan perilaku transformer, nilai-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 formatnya bebas menggunakan representasi lain secara internal.

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

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 yang diberi alamat hash untuk menyimpan warna yang baru saja digunakan agar dapat mengingatnya 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 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 terkait dalam gambar, yaitu, setiap piksel merupakan kode awalan.
LZ77
Algoritma kompresi jendela geser berbasis kamus yang memberikan hasil atau mendeskripsikannya sebagai urutan simbol sebelumnya.
kode awalan meta
Bilangan bulat kecil (hingga 16 bit) yang mengindeks elemen pada awalan meta tabel sementara.
gambar prediktor
Gambar subresolusi dua dimensi yang menunjukkan prediktor spasial mana yang untuk persegi tertentu dalam gambar.
kode awalan
Cara klasik untuk melakukan coding entropi di mana bit yang digunakan dalam jumlah yang lebih sedikit untuk kode yang lebih sering.
pengkodean awalan
Cara untuk mengkodekan bilangan bulat yang lebih besar dengan entropi, yang mengodekan beberapa bit bilangan bulat menggunakan kode entropi dan mengodifikasi bit{i> <i}yang tersisa, mentah. Hal ini memungkinkan deskripsi kode entropi tetap relatif kecil bahkan ketika rentang simbolnya besar.
urutan pemindaian baris
Urutan pemrosesan piksel (kiri ke kanan dan atas ke bawah), dimulai dari piksel sebelah kiri atas. Setelah baris selesai, lanjutkan dari kolom sebelah kiri dari baris berikutnya.

3 Header RIFF

Bagian awal {i>header<i} memiliki kontainer RIFF. Program ini terdiri dari 21 byte berikut:

  1. String 'RIFF'.
  2. Sebuah nilai {i>small-endian<i}, 32-bit dari panjang potongan, yang merupakan ukuran keseluruhan dari potongan yang dikendalikan oleh {i>header<i} RIFF. Biasanya, ini sama dengan ukuran {i>payload<i} (ukuran file minus 8 byte: 4 byte untuk 'RIFF' dan 4 byte untuk menyimpan nilai itu sendiri).
  3. String 'WEBP' (Nama penampung RIFF).
  4. String 'VP8L' (FourCC untuk data gambar yang dienkode lossless).
  5. Sebuah {i>small-endian<i}, nilai 32-bit dari jumlah byte dalam tanpa kehilangan aliran data.
  6. Tanda tangan 1-byte 0x2f.

28 bit pertama dari bitstream menentukan lebar dan tinggi gambar. Lebar dan tinggi diterjemahkan 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 lossless WebP ke 16384✕16384 piksel.

Bit alpha_is_used hanyalah petunjuk, dan tidak boleh memengaruhi decoding. Seharusnya diatur ke 0 jika semua nilai alfa adalah 255 dalam gambar, dan 1 jika sebaliknya.

int alpha_is_used = ReadBits(1);

Version_number adalah kode 3 bit yang harus ditetapkan ke 0. Nilai lainnya harus dianggap sebagai error.

int version_number = ReadBits(3);

4 Transformasi

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

Gambar dapat melalui empat jenis transformasi. 1 bit menunjukkan bahwa keberadaan sebuah transformasi. Setiap transformasi hanya boleh digunakan satu kali. Tujuan transformasi hanya digunakan untuk gambar ARGB level utama; gambar subresolusi (gambar transformasi warna, gambar entropi, dan gambar prediktor) tidak memiliki transformasi, bahkan tidak ada 0 bit yang menunjukkan akhir transformasi.

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

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

// Decode actual image data (Section 5).

Jika terdapat sebuah transformasi, maka dua bit berikutnya akan menentukan jenis transformasi tersebut. Ada empat jenis transformasi.

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

Jenis transformasi diikuti oleh data transformasi. {i>Transform data<i} berisi informasi yang diperlukan untuk menerapkan transformasi terbalik dan tergantung pada jenis transformasi. Transformasi terbalik diterapkan dalam urutan terbalik yang mereka dibaca dari bitstream, yaitu, yang terakhir terlebih dahulu.

Selanjutnya, kami menjelaskan data transformasi untuk berbagai jenis.

4.1 Transformasi Prediktif

Transformasi prediktor dapat digunakan untuk mengurangi entropi dengan memanfaatkan fakta {i>pixel<i} yang berdekatan sering kali berkorelasi. Dalam transformasi prediktor, nilai piksel saat ini diprediksi dari piksel yang sudah didekode (dalam garis pemindaian urutan) dan hanya nilai residu (aktual - prediksi) yang dienkode. Hijau piksel mendefinisikan mana dari 14 prediktor yang digunakan dalam dalam blok gambar ARGB tertentu. Mode prediksi menentukan jenis prediksi yang akan digunakan. Kita membagi gambar menjadi beberapa persegi, dan semua {i>pixel<i} dalam menggunakan mode prediksi yang sama.

Tiga bit pertama data prediksi menentukan lebar dan tinggi blok dalam angka bit.

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

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

Jumlah kolom blok, transform_width, digunakan dalam dua dimensi pengindeksan. Untuk piksel (x, y), kita dapat menghitung blok filter masing-masing alamat dengan:

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

Ada 14 mode prediksi yang berbeda. Di setiap mode prediksi, nilai nilai piksel diprediksi dari satu atau beberapa piksel tetangga yang yang sudah Anda ketahui.

Kami memilih piksel tetangga (TL, T, TR, dan L) dari piksel saat ini (P) sebagai berikut ini:

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. Di waktu memprediksi nilai untuk P, semua piksel O, TL, T, TR dan L sudah diproses, dan piksel P serta semua piksel X tidak diketahui.

Dengan piksel tetangga sebelumnya, mode prediksi yang berbeda didefinisikan sebagai berikut.

Mode Nilai prediksi setiap saluran dari piksel saat ini
0 0xff000000 (mewakili warna hitam solid dalam ARGB)
1 L
2 S
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 Pilih(L, T, TL)
12 ClampAddSubtractFull(L, T, TL)
13 ClampAddSubtractHalf(Average2(L, T), TL)

Average2 ditentukan sebagai berikut untuk setiap komponen ARGB:

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

Prediktor Select didefinisikan 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 prediktor, terlepas dari mode [0..13] untuk piksel ini, nilai prediksi untuk piksel paling kiri atas gambar adalah 0xff000000, semuanya {i>pixel<i} pada baris atas adalah L-piksel, dan semua {i>pixel<i} di kolom paling kiri adalah T-piksel.

Mengatasi TR-piksel untuk {i>pixel<i} di kolom paling kanan adalah luar biasa. Piksel pada kolom paling kanan diprediksi menggunakan mode [0..13], sama seperti piksel yang tidak berada di pembatas, tetapi piksel paling kiri di baris yang sama dengan piksel saat ini alih-alih digunakan sebagai piksel TR.

Nilai piksel akhir diperoleh dengan menambahkan setiap saluran dari nilai yang diprediksi pada nilai residu 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 dari transformasi warna adalah untuk menghiasi nilai-nilai R, G, dan B dari masing-masing piksel. Transformasi warna mempertahankan nilai hijau (G) apa adanya, mengubah merah (R) berdasarkan nilai hijau, dan mengubah nilai biru (B) berdasarkan pada nilai hijau dan kemudian pada nilai merah.

Seperti halnya pada transformasi prediktor, pertama-tama gambar dibagi menjadi blok, dan mode transformasi yang sama digunakan untuk semua {i>pixel<i} dalam sebuah blok. Sebagai 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 yang sebenarnya dilakukan dengan menentukan delta transformasi warna. Tujuan delta transformasi warna bergantung pada ColorTransformElement, yang sama untuk semua {i>pixel<i} dalam blok tertentu. Delta dikurangkan selama transformasi warna. Selanjutnya, transformasi warna terbalik akan 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 tangan yang mewakili Nomor 3.5-fixed-point dan saluran warna RGB 8-bit bertanda (c) [-128..127] dan didefinisikan sebagai berikut:

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

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

Perkalian harus dilakukan dengan menggunakan lebih presisi (dengan setidaknya 16-bit presisi). Properti ekstensi tanda dari operasi shift tidak menjadi masalah di sini; hanya 8 bit terendah yang digunakan dari hasil, dan ada tanda pergeseran ekstensi dan penyimpangan yang tidak ditandatangani konsisten satu sama lain.

Sekarang, kita akan menjelaskan isi data transformasi warna sehingga decoding dapat diterapkan transformasi warna terbalik dan memulihkan nilai merah dan biru asli. Tujuan 3 bit pertama dari data transformasi warna berisi lebar dan tinggi dari blok gambar dalam jumlah bit, seperti 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 ColorTransformElement yang sesuai, yang sesuai dengan setiap blok gambar. Masing-masing ColorTransformElement 'cte' diperlakukan sebagai piksel dalam gambar subresolusi dengan komponen alfa adalah 255, komponen merah adalah cte.red_to_blue, hijau komponennya adalah cte.green_to_blue, dan komponen biru adalah cte.green_to_red.

Selama dekode, ColorTransformElement instance blok didekode dan transformasi warna terbalik diterapkan pada nilai ARGB {i>pixel<i}. Sebagai yang disebutkan sebelumnya, transformasi warna invers hanya menambahkan Nilai ColorTransformElement ke saluran merah dan biru. Alfa dan hijau {i>channel<i} dibiarkan apa adanya.

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

Pengurangan transformasi hijau akan mengurangi nilai hijau dari nilai merah dan biru dari setiap piksel. Jika transformasi ini ada, decoder perlu menambahkan elemen hijau nilai untuk nilai merah dan biru. Tidak ada data yang terkait dengan ini transformasi. 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, turunkan {i>green transform <i}di mana dikodekan menggunakan lebih sedikit bit daripada transformasi warna {i>full-blown<i}.

4.4 Transformasi Pengindeksan Warna

Jika tidak ada banyak nilai piksel yang unik, mungkin akan lebih efisien untuk membuat array indeks warna dan mengganti nilai piksel dengan indeks array. Warna transformasi pengindeksan yang akan mencapainya. (Dalam konteks WebP lossless, kita secara khusus jangan menyebutnya sebagai transformasi palet karena kemiripan tetapi lebih konsep dinamis ada dalam encoding lossless WebP: cache warna.)

Transformasi pengindeksan warna memeriksa jumlah nilai ARGB unik di gambar. Jika angka itu di bawah ambang batas (256), ia akan membuat susunannya Nilai ARGB, yang kemudian digunakan untuk mengganti nilai piksel dengan indeks yang sesuai: saluran hijau dari piksel diganti dengan semua nilai alfa diatur ke 255, dan semua nilai merah dan biru menjadi 0.

Data transformasi berisi ukuran tabel warna dan entri dalam warna tabel sementara. 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 {i>header<i} RIFF, ukuran gambar, dan transformasi, dengan asumsi tinggi 1 piksel dan lebar color_table_size. Tabel warna selalu berkode pengurangan untuk mengurangi entropi gambar. Delta warna palet biasanya mengandung lebih sedikit entropi daripada warna sendiri, sehingga dapat menghemat secara signifikan untuk gambar yang lebih kecil. Dalam decoding, setiap warna akhir dalam tabel warna bisa diperoleh dengan menambahkan warna nilai komponen warna dengan setiap komponen ARGB secara terpisah dan menyimpan 8 bit yang signifikan.

Transformasi terbalik untuk gambar hanya mengganti nilai piksel (yang adalah indeks tabel warna) dengan nilai tabel warna yang 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 diatur ke 0x00000000 (hitam transparan).

Jika tabel warna kecil (sama dengan atau kurang dari 16 warna), beberapa piksel digabungkan menjadi satu piksel. Paket paket piksel (2, 4, atau 8) {i>pixel<i} menjadi satu {i>pixel<i}, yang mengurangi lebar gambar masing-masing. Piksel memungkinkan pengkodean entropi distribusi gabungan yang lebih efisien untuk piksel yang berdekatan dan memberikan beberapa manfaat seperti pengkodean aritmatika pada kode entropi, tetapi hanya dapat digunakan jika ada 16 nilai unik atau kurang.

color_table_size menentukan berapa banyak 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 piksel pemaketan harus dilakukan untuk gambar. Nilai 1 menunjukkan bahwa dua {i>pixel<i} adalah 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 {i>pixel<i} digabungkan dan setiap piksel memiliki rentang [0..1], yaitu, nilai biner.

Nilai tersebut dikemas ke dalam komponen hijau sebagai berikut:

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

Setelah membaca transformasi ini, image_width diambil sampelnya oleh width_bits. Ini memengaruhi ukuran transformasi berikutnya. Ukuran baru dapat dihitung menggunakan DIV_ROUND_UP, seperti yang dijelaskan sebelumnya.

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

5 Data Gambar

Data gambar adalah array nilai piksel dalam urutan baris pemindaian.

5.1 Peran Data Gambar

Kita menggunakan data gambar dalam lima peran yang berbeda:

  1. Gambar ARGB: Menyimpan piksel gambar yang sebenarnya.
  2. Gambar entropi: Menyimpan kode awalan meta (lihat "Decoding Kode Awalan Meta").
  3. Gambar prediktif: Menyimpan metadata untuk transformasi prediktor (lihat "Transformasi Prediktif").
  4. Gambar transformasi warna: Dibuat oleh nilai ColorTransformElement (ditentukan dalam "Transformasi Warna") untuk blok yang berbeda gambar.
  5. Gambar pengindeksan warna: Array berukuran color_table_size (hingga 256 ARGB nilai) yang menyimpan metadata untuk transformasi pengindeksan warna (lihat "Transformasi Pengindeksan Warna").

5.2 Encoding Data Gambar

Encoding data gambar tidak bergantung pada perannya.

Gambar pertama-tama dibagi menjadi satu set blok berukuran tetap (biasanya 16x16 blok). Masing-masing blok ini dimodelkan menggunakan kode entropinya sendiri. Selain itu, beberapa blok mungkin memiliki kode entropi yang sama.

Alasan: Menyimpan kode entropi akan menimbulkan biaya. Biaya ini dapat diminimalkan jika blok yang serupa secara statistik berbagi kode entropi, sehingga menyimpan kode tersebut hanya sekali. Misalnya, encoder dapat menemukan blok serupa dengan mengelompokkannya menggunakan sifat statistiknya atau dengan berulang kali menggabungkan cluster yang dipilih saat mengurangi jumlah keseluruhan bit yang diperlukan untuk gambar tersebut.

Setiap piksel dienkode menggunakan salah satu dari tiga metode yang tersedia:

  1. Literal berkode awalan: Setiap saluran (hijau, merah, biru, dan alfa) kode entropi secara independen.
  2. Referensi mundur LZ77: Urutan piksel disalin dari tempat lain di gambar tersebut.
  3. Kode cache warna: Menggunakan kode hash perkalian singkat (cache warna ) warna yang baru dilihat.

Subbagian berikut menjelaskan setiap hal tersebut secara mendetail.

5.2.1 Literal Kode Awalan

Piksel disimpan sebagai nilai berkode awalan hijau, merah, biru, dan alfa (di urutan tersebut). Lihat Bagian 6.2.3 untuk spesifikasi pendukung.

5.2.2 Referensi Mundur LZ77

Referensi mundur adalah tuple dengan panjang dan kode jarak:

  • Panjang menunjukkan jumlah piksel dalam urutan baris pemindaian yang akan disalin.
  • Kode jarak adalah angka yang menunjukkan posisi yang sebelumnya terlihat {i>pixel<i}, tempat piksel akan disalin. Pemetaan yang tepat adalah dijelaskan di bawah.

Nilai panjang dan jarak disimpan menggunakan coding awalan LZ77.

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

Alasan: Pendekatan ini mengurangi persyaratan penyimpanan untuk entropi pada kode sumber. Juga, nilai besar biasanya jarang, jadi bit tambahan akan digunakan untuk sedikit nilai pada gambar. Sehingga, 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 ekstra
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 sebuah nilai (panjang atau jarak) dari kode awalan adalah sebagai berikut berikut ini:

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 disebutkan sebelumnya, kode jarak adalah angka yang menunjukkan posisi {i>pixel<i} yang sebelumnya terlihat, dari mana piksel tersebut akan disalin. Subbagian ini mendefinisikan pemetaan antara kode jarak dan posisi kode sebelumnya piksel.

Kode jarak yang lebih besar dari 120 menunjukkan jarak {i>pixel<i} dalam urutan garis pindai, dengan offset sebesar 120.

Kode jarak terkecil [1..120] bersifat khusus dan dicadangkan untuk sekitar piksel saat ini. Lingkungan ini terdiri atas 120 piksel:

  • Piksel yang memiliki 1 hingga 7 baris di atas piksel saat ini dan memiliki hingga 8 kolom di sebelah kiri atau hingga 7 kolom di sebelah kanan {i>pixel<i} saat ini. [Total piksel tersebut = 7 * (8 + 1 + 7) = 112].
  • Piksel yang berada di baris yang sama dengan piksel saat ini dan berukuran hingga 8 kolom di sebelah kiri piksel saat ini. [8 piksel seperti itu].

Pemetaan antara kode jarak distance_code dan piksel di dekatnya offset (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 yang berdekatan, yaitu piksel di atas piksel saat ini (0 piksel perbedaan arah X dan selisih 1 piksel dalam arah Y). Demikian pula, kode jarak 3 menunjukkan piksel kiri atas.

Decoder dapat mengonversi kode jarak distance_code menjadi urutan baris pemindaian jarak dist sebagai berikut:

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

dengan distance_map adalah pemetaan yang disebutkan di atas, dan image_width adalah lebarnya gambar dalam {i>pixel<i}.

5.2.3 Pengkodean Cache Warna

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

Argumentasi: Dengan cara ini, warna yang baru-baru ini digunakan terkadang dapat dirujuk ke lebih efisien daripada memunculkannya menggunakan dua metode lain (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 adalah 0, tidak ada kode cache warna ada, dan tidak ditransmisikan dalam kode awalan yang mendekode kode hijau simbol dan kode awalan panjang. Namun, jika bit ini adalah 1, cache warna {i>size<i} dibaca selanjutnya:

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 patuh harus menunjukkan bitstream yang rusak untuk nilai-nilai lain.

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

Di awal decoding atau encoding gambar, semua entri dalam semua warna nilai {i>cache <i} diatur ke nol. Kode cache warna dikonversi ke warna ini di waktu dekode. Status cache warna dipertahankan dengan memasukkan setiap piksel, baik yang dihasilkan dengan mereferensikan mundur atau sebagai literal, ke dalam cache di urutan kemunculannya dalam aliran.

6 Kode Entropi

6.1 Ikhtisar

Sebagian besar data dikodekan menggunakan kode awalan kanonis. Oleh karena itu, kode tersebut dikirimkan dengan mengirimkan panjang kode awalan, sebagai bukan kode awalan yang sebenarnya.

Secara khusus, format tersebut menggunakan coding awalan varian spasial. Di blok gambar yang berbeda berpotensi menggunakan entropi yang berbeda kode program.

Argumentasi: Area gambar yang berbeda mungkin memiliki karakteristik yang berbeda. Jadi, memungkinkan mereka untuk menggunakan kode entropi yang berbeda memberikan lebih banyak fleksibilitas dan kompresi yang lebih baik.

6.2 Detail

Data gambar yang dienkode terdiri dari beberapa bagian:

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

Untuk setiap piksel (x, y), ada kumpulan lima kode awalan yang terkait dengan anotasi. Kode ini (dalam urutan bitstream):

  • Kode awalan #1: Digunakan untuk saluran hijau, panjang referensi mundur, dan {i>color cache<i}.
  • Kode awalan #2, #3, dan #4: Digunakan untuk saluran merah, biru, dan alfa, secara berurutan.
  • Kode awalan #5: Digunakan untuk jarak referensi mundur.

Mulai sekarang, kami menyebut set ini sebagai grup kode awalan.

6.2.1 Decoding 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 dengan nilai 1-bit.

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

Dalam kedua kasus tersebut, mungkin ada panjang kode yang tidak terpakai yang masih menjadi bagian dari feed Anda. Hal ini mungkin tidak efisien, tetapi diizinkan oleh formatnya. Hierarki yang dijelaskan harus berupa pohon biner lengkap. Sebuah {i>node<i} daun tunggal adalah dianggap sebagai pohon biner lengkap dan dapat dienkode menggunakan metode kode panjang kode atau kode panjang kode normal. Saat melakukan coding untuk satu leaf node yang menggunakan kode panjang kode normal, semuanya kecuali satu panjang kode adalah nol, dan nilai simpul daun tunggal ditandai dengan panjang 1 -- bahkan ketika tidak bit dipakai saat pohon node leaf tunggal digunakan.

Kode Panjang Kode Sederhana

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

Bit pertama menunjukkan jumlah simbol:

int num_symbols = ReadBits(1) + 1;

Berikut ini adalah nilai simbolnya.

Simbol pertama ini dikodekan menggunakan 1 atau 8 bit, tergantung pada nilai is_first_8bits. Rentangnya adalah [0..1] atau [0..255], masing-masing. Yang kedua jika ada, selalu diasumsikan berada dalam rentang [0..255] dan berkode 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 boleh kosong jika tidak ada referensi mundur. Demikian pula, kode awalan untuk alfa, merah, dan biru boleh kosong jika semua piksel dalam kode awalan meta yang sama dibuat menggunakan cache warna. Namun, kasus ini tidak memerlukan penanganan khusus, kode awalan kosong dapat dikodekan sebagai kode yang berisi satu simbol 0.

Kode Panjang Kode Normal

Panjang kode awalan sesuai dalam 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; kode di tingkat yang lebih rendah panjang, code_length_code_lengths, harus dibaca terlebih dahulu. Sisanya code_length_code_lengths (sesuai dengan pesanan 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);
}

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

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

Jika tidak, hal 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 valid.

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

  • Kode [0..15] menunjukkan panjang kode literal.
    • Nilai 0 berarti tidak ada simbol yang dikodekan.
    • Nilai [1..15] menunjukkan panjang bit dari masing-masing kode.
  • Kode 16 mengulangi nilai bukan nol sebelumnya [3..6] kali, yaitu, 3 + ReadBits(2) kali. Jika kode 16 digunakan sebelum angka bukan nol telah dimunculkan, nilai 8 diulang.
  • Kode 17 memunculkan deretan angka nol dengan panjang [3..10], yaitu 3 + ReadBits(3) kali.
  • Kode 18 memancarkan beruntun 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) dibentuk menggunakan ukuran alfabet masing-masing.

Kode Panjang Kode Normal harus mengkodekan pohon keputusan lengkap, yaitu, jumlah dari 2 ^ (-length) untuk semua kode selain nol harus sama persis dengan satu. Namun ada satu pengecualian untuk aturan ini, pohon {i>node<i} daun tunggal, tempat {i>node<i} daun nilai ditandai dengan nilai 1 dan nilai lainnya adalah 0s.

6.2.2 Decoding Kode Awalan Meta

Seperti 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 hanya dapat digunakan saat gambar digunakan di peran gambar ARGB.

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

  • Jika bit ini adalah nol, hanya ada satu kode awalan meta yang digunakan di mana-mana di gambar tersebut. Tidak ada lagi data yang disimpan.
  • Jika bit ininya satu, gambar akan menggunakan beberapa kode awalan meta. Meta ini kode awalan disimpan sebagai gambar entropi (dijelaskan di bawah).

Komponen merah dan hijau dari sebuah {i>pixel<i} mendefinisikan kode awalan meta 16-bit yang digunakan dalam blok gambar ARGB tertentu.

Gambar Entropi

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

3 bit pertama berisi nilai prefix_bits. Dimensi entropi gambar berasal dari 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);

dengan DIV_ROUND_UP seperti yang didefinisikan sebelumnya.

Bit berikutnya berisi gambar entropi dengan lebar prefix_image_width dan tinggi prefix_image_height.

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 di gambar entropi.

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

int num_prefix_codes = 5 * num_prefix_groups;

Mempertimbangkan piksel (x, y) dalam gambar ARGB, kita dapat memperoleh awalan yang sesuai kode yang akan digunakan sebagai berikut:

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

di mana kita telah mengasumsikan keberadaan struktur PrefixCodeGroup, yang mewakili satu set dari lima kode awalan. Selain itu, prefix_code_groups adalah array PrefixCodeGroup (dengan ukuran num_prefix_groups).

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

6.2.3 Dekode Data Gambar Berkode Entropi

Untuk posisi saat ini (x, y) dalam gambar, decoder terlebih dahulu mengidentifikasi grup kode awalan yang sesuai (seperti yang dijelaskan di bagian sebelumnya). Mengingat kelompok kode awalan, piksel dibaca dan didekode sebagai berikut.

Selanjutnya, baca simbol S dari bitstream menggunakan kode awalan #1. Perhatikan bahwa S adalah bilangan bulat apa pun di 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. Baca warna merah dari bitstream menggunakan kode awalan #2.
    3. Baca warna biru dari bitstream menggunakan kode awalan #3.
    4. Baca alfa dari bitstream menggunakan kode awalan #4.
  2. Jika S >= 256 & S < 256 + 24
    1. Gunakan S - 256 sebagai kode awalan panjang.
    2. Membaca bit tambahan untuk panjangnya dari bitstream.
    3. Tentukan panjang referensi mundur L dari kode awalan bit tambahan yang dibaca.
    4. Baca kode awalan jarak dari bitstream menggunakan kode awalan #5.
    5. Membaca bit ekstra untuk jarak dari bitstream.
    6. Tentukan jarak referensi mundur D dari kode awalan jarak dan bit ekstra 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 Keseluruhan Format

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

Perhatikan bahwa *element berarti element dapat diulang 0 kali atau lebih. 5element berarti element diulang tepat 5 kali. %b mewakili 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