Spesifikasi Bitstream Lossless WebP

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

Abstrak

WebP lossless adalah format gambar untuk kompresi lossless gambar ARGB. Format tanpa kompresi menyimpan dan memulihkan nilai piksel secara akurat, 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, kita menggunakan sintaksis bahasa pemrograman C secara ekstensif untuk mendeskripsikan bitstream dan mengasumsikan adanya fungsi untuk membaca bit, ReadBits(n). Byte dibaca dalam urutan alami aliran yang berisi byte tersebut, dan bit dari setiap byte dibaca dalam urutan least-significant-bit-first. Saat beberapa bit dibaca secara bersamaan, bilangan bulat dibuat dari data asli dalam urutan asli. Bit yang paling signifikan dari bilangan bulat yang ditampilkan 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. Kita menentukan 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 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.

Secara umum, gambar lossless WebP berisi data header, informasi transformasi, dan data gambar sebenarnya. Header berisi lebar dan tinggi gambar. Gambar lossless WebP dapat melalui empat jenis transformasi sebelum dienkode 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 memanggilnya 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 sub-resolusi 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 terkait dalam gambar, yaitu, setiap piksel merupakan kode awalan.

LZ77

Algoritma kompresi jendela geser berbasis kamus yang memunculkan simbol 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 dengan jumlah bit yang lebih kecil digunakan untuk kode yang lebih sering.

coding 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. 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 payload (ukuran file dikurangi 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 berenkode lossless).
5. Nilai little-endian 32-bit dari jumlah byte dalam streaming 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 lossless WebP ke 16.384✕16384 piksel.

Bit alpha_is_used hanya merupakan petunjuk, dan tidak akan 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 kehadiran transformasi. Setiap transformasi hanya boleh digunakan satu kali. Transformasi hanya digunakan untuk gambar ARGB tingkat utama; gambar sub-resolusi (gambar transformasi warna, gambar entropi, dan gambar prediktor) tidak memiliki transformasi, bahkan bit 0 yang menunjukkan akhir transformasi.

Biasanya, encoder akan menggunakan transformasi ini untuk mengurangi entropi Shannon dalam gambar residu. Selain itu, data transformasi dapat diputuskan berdasarkan pengurangan 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 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 dengan 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, kita akan menjelaskan data transformasi untuk berbagai jenis.

4.1 Transformasi Prediktor

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 kotak, dan semua piksel dalam kotak menggunakan mode prediksi yang sama.

3 bit pertama data prediksi menentukan lebar dan tinggi blok dalam jumlah 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 adalah gambar sub-resolusi dengan komponen hijau piksel menentukan mana dari 14 prediktor yang digunakan untuk semua piksel block_width * block_height dalam blok tertentu dari gambar ARGB. Gambar subresolusi ini dienkode menggunakan teknik yang sama seperti yang dijelaskan dalam Bab 5.

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

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

Ada 14 mode prediksi yang berbeda. Di setiap mode prediksi, output 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

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

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

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 dilakukan 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 yang diprediksi untuk piksel paling kiri atas gambar adalah 0xff000000, semua piksel di baris atas adalah piksel L, dan semua piksel di kolom paling kiri adalah piksel T.

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

Nilai piksel akhir diperoleh dengan menambahkan setiap saluran nilai prediksi ke 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) seperti apa adanya, mengubah nilai merah (R) berdasarkan nilai hijau, dan mengubah nilai biru (B) berdasarkan nilai hijau, lalu berdasarkan nilai merah.

Seperti halnya 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 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 dikurangi 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 tanpa tanda tangan 8-bit (uint8) ke representasi bertanda tangan 8-bit (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 pergeseran tidak penting di sini; hanya 8 bit terendah yang digunakan dari hasilnya, dan dalam bit ini, pergeseran ekstensi tanda dan pergeseran tanpa tanda 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. 3 bit pertama data transformasi warna berisi lebar dan tinggi 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 data transformasi warna yang tersisa berisi instance ColorTransformElement, yang sesuai dengan setiap blok gambar. Setiap ColorTransformElement 'cte' diperlakukan sebagai piksel dalam gambar sub-resolusi 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 invers diterapkan pada nilai ARGB piksel. Seperti yang disebutkan sebelumnya, transformasi warna invers hanya menambahkan nilai ColorTransformElement ke saluran merah dan biru. Saluran alfa dan hijau 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 karakter 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, Transformasi hijau dapat dikurangi dikodekan menggunakan lebih sedikit bit daripada transformasi warna {i>full-blown<i}.

4.4 Transformasi Pengindeksan Warna

Jika tidak ada banyak nilai piksel unik, akan lebih efisien untuk membuat array indeks warna dan mengganti nilai piksel dengan indeks array. Transformasi pengindeksan warna akan mencapai hal ini. (Dalam konteks WebP lossless, kami secara khusus tidak menyebutnya 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 berada di bawah nilai minimum (256), angka tersebut akan membuat array nilai ARGB tersebut, yang kemudian digunakan untuk mengganti nilai piksel dengan indeks yang sesuai: 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 dienkode dengan 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 ditetapkan ke 0x00000000 (hitam transparan).

Jika tabel warna kecil (sama dengan atau kurang dari 16 warna), beberapa piksel digabungkan menjadi satu piksel. Penggabungan piksel memaketkan beberapa (2, 4, atau 8) piksel menjadi satu piksel, sehingga mengurangi lebar gambar. 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 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 bahwa tidak ada pengelompokan piksel yang akan 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, 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. Hal 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

Kami 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 dengan ukuran color_table_size (hingga 256 nilai ARGB) 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 sekumpulan blok berukuran tetap (biasanya blok 16x16). 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 yang 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 tersedia:

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

Subbagian berikut menjelaskan setiap detailnya.

5.2.1 Literal yang Di-enkode Awalan

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

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 piksel yang dilihat sebelumnya, tempat piksel akan disalin. Pemetaan yang tepat 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).

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.

Pseudocode 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 sebelumnya terlihat, tempat piksel 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 lingkungan dekat piksel saat ini. Lingkungan ini terdiri dari 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 maksimal 8 kolom di sebelah kiri piksel saat ini. [8 piksel tersebut].

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.

Dekoder dapat mengonversi kode jarak distance_code menjadi jarak urutan garis pemindaian 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.

Alasan: Dengan cara ini, warna yang baru 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 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]. Dekoder yang mematuhi harus menunjukkan bitstream yang rusak untuk nilai lain.

Cache warna adalah array berukuran color_cache_size. Setiap entri menyimpan satu warna ARGB. Warna dicari dengan mengindeksnya menurut (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 nilai cache warna ditetapkan ke nol. Kode cache warna dikonversi ke warna ini pada waktu decoding. Status cache warna dipertahankan dengan menyisipkan setiap piksel, baik yang dihasilkan oleh referensi mundur atau sebagai literal, ke dalam cache dalam urutan yang muncul di aliran.

Kode Entropi 6

6.1 Ringkasan

Sebagian besar data dienkode menggunakan kode awalan kanonis. Oleh karena itu, kode dikirim dengan mengirimkan panjang kode awalan, 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 adalah (dalam urutan bitstream):

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

Mulai sekarang, kita akan menyebut kumpulan 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 bernilai 1, berarti ini adalah kode panjang kode sederhana.
• Jika bit ini bernilai 0, berarti 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 format. 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 membuat kode satu node daun menggunakan kode panjang kode normal, semua panjang kode kecuali satu adalah nol, dan nilai satu node daun ditandai dengan panjang 1 -- meskipun tidak ada bit yang digunakan saat hierarki node daun tunggal tersebut 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 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 dienkode 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; panjang kode level rendah, code_length_code_lengths, harus dibaca terlebih dahulu. code_length_code_lengths lainnya (sesuai 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);
}

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 kode masing-masing.
• Kode 16 mengulangi nilai non-nol sebelumnya [3..6] kali, yaitu, 3 + ReadBits(2) kali. Jika kode 16 digunakan sebelum nilai bukan nol telah dikeluarkan, nilai 8 akan 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 mengenkode hierarki keputusan lengkap, yaitu jumlah 2 ^ (-length) untuk semua kode non-nol harus tepat 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 nol, hanya ada satu kode awalan meta yang digunakan di mana saja dalam gambar. Tidak ada lagi data yang disimpan.
• Jika bit ini adalah salah satunya, gambar akan menggunakan beberapa kode awalan meta. Meta ini kode awalan disimpan sebagai gambar entropi (dijelaskan di bawah).

Komponen merah dan hijau dari 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_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 dalam 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];

dengan asumsi adanya struktur PrefixCodeGroup, yang mewakili kumpulan lima kode awalan. Selain itu, prefix_code_groups adalah array PrefixCodeGroup (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, dekoder pertama-tama mengidentifikasi grup kode awalan yang sesuai (seperti yang dijelaskan di bagian terakhir). 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 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. Baca 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. If 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 panjang dan bit tambahan yang dibaca.
   4. Baca kode awalan jarak dari bitstream menggunakan kode awalan #5.
   5. Baca 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 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