Jyrki Alakuijala, Ph.D., Google LLC, 09-03-2023
Abstrak
WebP lossless adalah format gambar untuk kompresi lossless gambar ARGB. Format lossless menyimpan dan memulihkan nilai piksel secara tepat, termasuk nilai warna untuk piksel yang nilai alfanya 0. Format ini menggunakan gambar subresolusi, yang secara rekursif disematkan ke dalam format itu sendiri, untuk menyimpan data statistik tentang gambar, seperti kode entropi yang digunakan, prediktor spasial, konversi ruang warna, dan tabel warna. LZ77, coding awalan, dan cache warna digunakan untuk kompresi data massal. Kecepatan dekode yang lebih cepat daripada PNG telah ditunjukkan, serta kompresi yang lebih padat 25% daripada yang dapat dicapai menggunakan format PNG hari ini.
1 Pengantar
Dokumen ini menjelaskan representasi data terkompresi dari gambar lossless WebP. Ini dimaksudkan sebagai referensi detail untuk implementasi encoder dan decoder WebP WebP.
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 dari aliran yang berisi
nya, dan bit setiap byte dibaca dalam urutan bit 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. Jadi, pernyataan
b = ReadBits(2);
setara dengan dua pernyataan di bawah ini:
b = ReadBits(1);
b |= ReadBits(1) << 1;
Kami berasumsi bahwa setiap komponen warna, yaitu alfa, merah, biru, dan hijau, diwakili menggunakan byte 8 bit. Kami menentukan jenis yang sesuai sebagai uint8. Piksel seluruh ARGB direpresentasikan oleh jenis yang disebut uint32, bilangan bulat tanpa tanda yang terdiri dari 32 bit. Dalam kode yang menunjukkan perilaku transformasi, nilai alfa dikodifikasikan dalam bit 31..24, merah dalam bit 23..16, hijau dalam bit 15..8 dan biru dalam bit 7..0, tetapi implementasi format bebas menggunakan representasi lain secara internal.
Secara umum, gambar lossless WebP berisi data header, informasi transformasi, dan data gambar yang sebenarnya. Header berisi lebar dan tinggi gambar. Gambar lossless WebP dapat melewati empat jenis transformasi berbeda sebelum dienkode dengan 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 yang di-hash untuk menyimpan warna yang baru-baru ini digunakan, agar dapat memanggilnya dengan kode yang lebih pendek.
- gambar pengindeksan warna
- Gambar satu dimensi warna 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 piksel terkecil dalam kedekatan 2D.
- gambar entropi
- Gambar subresolusi dua dimensi yang menunjukkan coding entropi mana yang harus digunakan dalam setiap persegi pada gambar, yaitu setiap piksel adalah kode awalan meta.
- kode awalan
- Cara klasik untuk melakukan coding entropi di mana jumlah bit yang lebih kecil digunakan untuk kode yang lebih sering.
- LZ77
- Algoritme kompresi jendela geser berbasis kamus yang menampilkan simbol atau mendeskripsikannya sebagai urutan simbol sebelumnya.
- 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.
- coding awalan
- Cara untuk melakukan entropi pada bilangan bulat yang lebih besar yang mengkodekan beberapa bit bilangan bulat menggunakan kode entropi dan mengodifikasi bit yang tersisa. Hal ini memungkinkan deskripsi kode entropi tetap relatif kecil meskipun rentang simbol besar.
- urutan pemindaian
- Urutan pemrosesan piksel, dari kiri ke kanan, dari atas ke bawah, yang dimulai dari piksel kiri ke atas, yang dilanjutkan ke kanan. Setelah baris selesai, lanjutkan dari kolom sebelah kiri baris berikutnya.
3 Header RIFF
Bagian awal header memiliki penampung RIFF. Ini terdiri dari 21 byte berikut:
- String "RIFF"
- Nilai 32 bit kecil untuk panjang blok, yakni seluruh ukuran blok yang dikontrol oleh header 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).
- String "WEBP" (nama container RIFF).
- String "VP8L" (tag potongan untuk data gambar berenkode lossless).
- Nilai sedikit byte 32 bit untuk jumlah byte dalam aliran lossless.
- Tanda tangan satu byte 0x2f.
28 bit pertama 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 hingga 16384✕16384 piksel.
Bit alpha_is_used hanya berupa petunjuk, dan tidak akan memengaruhi decoding. Nilai ini harus ditetapkan 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 diperlakukan 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 membuat model korelasi spasial dan warna. Transformasi dapat membuat kompresi akhir lebih padat.
Gambar dapat melalui empat jenis transformasi. 1 bit menunjukkan adanya transformasi. Setiap transformasi hanya boleh digunakan sekali. Transformasi hanya digunakan untuk gambar ARGB level utama: gambar subresolusi tidak memiliki transformasi, bahkan 0 bit yang menunjukkan akhir transformasi.
Encoder biasanya menggunakan transformasi ini untuk mengurangi entropi Shannon dalam gambar sisa. Selain itu, data transformasi dapat ditentukan berdasarkan minimisasi entropi.
while (ReadBits(1)) { // Transform present.
// Decode transform type.
enum TransformType transform_type = ReadBits(2);
// Decode transform data.
...
}
// Decode actual image data (Section 4).
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. Selanjutnya, kita akan menjelaskan data transformasi untuk berbagai jenis.
4.1 Transformasi Prediktor
Transformasi prediktor dapat digunakan untuk mengurangi entropi dengan memanfaatkan fakta bahwa piksel yang berdekatan sering berkorelasi. Dalam transformasi prediktor, nilai piksel saat ini diprediksi dari piksel yang sudah didekode (dalam urutan garis pemindaian) dan hanya nilai residu (sebenarnya - diprediksi) yang dienkode. Mode prediksi menentukan jenis prediksi yang akan digunakan. Kami membagi gambar menjadi persegi 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. Semua piksel block_width * block_height blok menggunakan mode prediksi yang sama. Mode prediksi diperlakukan sebagai piksel gambar dan dienkode menggunakan teknik yang sama seperti yang dijelaskan dalam Bab 5.
Untuk piksel x, y, seseorang dapat menghitung alamat blok filter yang terkait dengan:
int block_index = (y >> size_bits) * block_xsize +
(x >> size_bits);
Ada 14 mode prediksi yang berbeda. Dalam setiap mode prediksi, nilai piksel saat ini diprediksi dari satu atau beberapa piksel di dekatnya yang nilainya sudah diketahui.
Kami memilih piksel yang berdekatan (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
dengan TL berarti kiri atas, T atas, TR kanan atas, L piksel kiri. Pada saat memprediksi nilai untuk P, semua piksel O, TL, T, TR dan L telah diproses, dan piksel P dan semua piksel X tidak diketahui.
Mengingat piksel di atas, mode prediksi yang berbeda ditentukan sebagai berikut.
| Mode | Prediksi nilai setiap saluran piksel saat ini |
|---|---|
| 0 | 0xff000000 (merepresentasikan warna hitam solid dalam ARGB) |
| 1 | L |
| 2 | T |
| 3 | TR |
| 4 | TL |
| 5 | Rata-Rata2(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 | Rata2(Rata2(L, TL), Rata2(T, TR)) |
| 11 | Pilih(L, T, TL) |
| 12 | ClampAddSubtractFull(L, T, TL) |
| 13 | ClampAddSubtractHalf(Rata2(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 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 prediksi, terlepas dari mode [0..13] untuk piksel ini, nilai prediksi untuk piksel paling kiri atas gambar adalah 0xff000000, piksel L untuk semua piksel di baris atas, dan T-piksel untuk semua piksel di kolom paling kiri.
Menangani TR-pixel untuk piksel di kolom paling kanan adalah pengecualian. Piksel pada kolom paling kanan diprediksi menggunakan mode [0..13], sama seperti piksel yang tidak berada di batas, tetapi piksel paling kiri pada baris yang sama dengan piksel saat ini akan digunakan sebagai TR-piksel.
4.2 Transformasi Warna
Tujuan dari transformasi warna adalah untuk mendekorasi ulang nilai R, G, dan B dari setiap piksel. Transformasi warna mempertahankan nilai hijau (G) apa adanya, berubah menjadi merah (R) berdasarkan hijau dan berubah menjadi biru (B) berdasarkan hijau lalu berdasarkan merah.
Seperti yang terjadi pada transformasi prediktor, pertama-tama gambar dibagi menjadi beberapa blok dan mode transformasi yang sama digunakan untuk semua piksel dalam satu 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. Delta transformasi warna bergantung pada ColorTransformElement, yang sama untuk semua piksel dalam blok tertentu. Delta dikurangi selama
transformasi warna. Transformasi warna terbalik kemudian 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 mewakili
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 yang tidak ditandatangani (uint8) ke yang ditandatangani
8-bit (int8) diperlukan sebelum memanggil ColorTransformDelta(). Hal ini harus
dilakukan menggunakan pelengkap dua 8-bit (yaitu: rentang uint8 [128..255] dipetakan ke rentang [-128..-1] dari nilai int8 yang dikonversi).
Perkalian harus dilakukan dengan lebih presisi (setidaknya 16-bit). Properti ekstensi tanda dari operasi shift tidak berpengaruh di sini: hanya 8 bit terendah yang digunakan dari hasil, dan di sana pergeseran ekstensi tanda dan pergeseran yang tidak ditandatangani konsisten satu sama lain.
Sekarang kita menjelaskan konten data transformasi warna sehingga decoding dapat menerapkan transformasi warna terbalik dan memulihkan nilai merah dan biru asli. 3 bit pertama dari data transformasi warna berisi lebar dan tinggi blok gambar dalam jumlah bit, sama seperti transformasi prediktor:
int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;
Bagian selanjutnya dari data transformasi warna berisi instance ColorTransformElement
yang sesuai dengan setiap blok gambar. Instance ColorTransformElement
diperlakukan sebagai piksel gambar dan dienkode menggunakan metode
yang dijelaskan dalam Bab 5.
Selama decoding, instance ColorTransformElement blok didekode dan
transformasi warna terbalik diterapkan pada nilai ARGB piksel. Seperti
disebutkan sebelumnya, transformasi warna terbalik tersebut hanya menambahkan
nilai ColorTransformElement ke saluran merah dan biru.
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 Kurangi Transformasi Hijau
Transformasi pengurangan hijau mengurangi nilai hijau dari nilai merah dan biru setiap piksel. Jika transformasi ini ada, decoder perlu menambahkan nilai hijau ke merah dan biru. Tidak ada data yang terkait dengan transformasi ini. Dekoder 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 yang dikurangi dapat dikodekan menggunakan lebih sedikit bit daripada transformasi warna lengkap.
4.4 Transformasi Pengindeksan Warna
Jika tidak banyak nilai piksel unik, mungkin akan lebih efisien untuk membuat array indeks warna dan mengganti nilai piksel dengan indeks array. Transformasi pengindeksan warna mencapai tujuan ini. (Dalam konteks WebP lossless, kami secara khusus tidak menyebutnya 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 berada di bawah nilai minimum (256), sistem 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; semua nilai merah dan biru menjadi 0.
Data transformasi berisi ukuran tabel warna dan entri di tabel warna. Decoder membaca data transformasi pengindeksan warna sebagai berikut:
// 8 bit value for 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 anggap tinggi satu piksel dan lebar color_table_size.
Tabel warna selalu diberi kode pengurangan untuk mengurangi entropi gambar. Delta warna palet biasanya jauh lebih sedikit entropi daripada warna itu sendiri, yang menyebabkan penghematan signifikan untuk gambar yang lebih kecil. Dalam mendekode,
setiap warna akhir dalam tabel warna dapat diperoleh dengan menambahkan
nilai komponen warna sebelumnya oleh setiap komponen ARGB secara terpisah, dan menyimpan
8 bit hasil yang paling tidak signifikan.
Transformasi terbalik untuk gambar hanya mengganti nilai piksel (yang merupakan indeks pada 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 atau lebih besar dari color_table_size, nilai warna metadata
harus ditetapkan ke 0x00000000 (hitam transparan).
Jika tabel warna berukuran kecil (sama dengan atau kurang dari 16 warna), beberapa piksel akan digabungkan ke dalam satu piksel. Paket piksel menggabungkan beberapa (2, 4, atau 8) piksel menjadi satu piksel, sehingga mengurangi lebar gambar. Pemaketan Pixel memungkinkan coding entropi distribusi bersama yang lebih efisien dari piksel tetangga, dan memberikan beberapa manfaat seperti coding aritmetika pada kode entropi, tetapi hanya dapat digunakan jika ada maksimal 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 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 dengan x ≡ 0 (mod 2), nilai berwarna hijau pada x diposisikan ke dalam 4 bit yang paling tidak signifikan dari nilai hijau di x / 2, nilai berwarna hijau di x + 1 diposisikan ke dalam 4 bit yang paling signifikan dari nilai hijau di x / 2.width_bits= 2: untuk setiap nilai x dengan x ≡ 0 (mod 4), nilai berwarna hijau pada x diposisikan ke dalam 2 bit yang paling tidak signifikan dari nilai hijau di x / 4, nilai hijau di x + 1 sampai x + 3 diposisikan untuk bit yang lebih signifikan dari nilai hijau di x / 4.width_bits= 3: untuk setiap nilai x dengan x ≡ 0 (mod 8), nilai berwarna hijau di x diposisikan pada bit paling kecil dari nilai hijau pada x / 8, nilai hijau pada x + 1 hingga x + 7 diposisikan untuk bit yang lebih signifikan dari nilai hijau pada x / 8.
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 berbeda:
- Gambar ARGB: Menyimpan piksel gambar yang sebenarnya.
- Gambar entropi: Menyimpan kode awalan meta. Komponen merah dan hijau piksel menentukan kode awalan meta yang digunakan dalam blok gambar ARGB tertentu.
- Gambar prediktif: Menyimpan metadata untuk Transformasi Predictions. Komponen hijau piksel menentukan mana dari 14 prediktor yang digunakan dalam blok tertentu dari gambar ARGB.
- Gambar transformasi warna. Kode ini dibuat oleh nilai
ColorTransformElement(ditentukan dalam Transformasi Warna) untuk berbagai blok gambar. SetiapColorTransformElement'cte'diperlakukan sebagai piksel yang komponen alfanya adalah255, komponen merah adalahcte.red_to_blue, komponen hijau adalahcte.green_to_blue, dan komponen biru adalahcte.green_to_red. - Gambar pengindeksan warna: Array berukuran
color_table_size(hingga 256 nilai ARGB) yang menyimpan metadata untuk Transformasi Pengindeksan Warna. Ini disimpan sebagai gambar dengan lebarcolor_table_sizedan tinggi1.
5.2 Encoding Data Gambar
Encoding data gambar tidak bergantung pada perannya.
Gambar ini pertama-tama dibagi menjadi satu set blok ukuran tetap (biasanya blok 16x16). Setiap blok ini dimodelkan menggunakan kode entropi masing-masing. Selain itu, beberapa blok dapat memiliki kode entropi yang sama.
Rasional: Menyimpan kode entropi akan dikenai biaya. Biaya ini dapat diminimalkan jika blok yang serupa secara statistik berbagi kode entropi, sehingga hanya menyimpan kode satu kali. Misalnya, encoder dapat menemukan blok serupa dengan mengelompokkannya menggunakan properti statistik, atau dengan menggabungkan secara berulang sepasang cluster yang dipilih secara acak saat mengurangi jumlah keseluruhan bit yang diperlukan untuk mengenkode gambar.
Setiap piksel dienkode menggunakan salah satu dari tiga kemungkinan metode:
- Literal kode awalan: setiap saluran (hijau, merah, biru, dan alfa) dikodekan secara entropi secara independen;
- Referensi mundur LZ77: urutan piksel disalin dari tempat lain dalam gambar; atau
- Kode cache warna: menggunakan kode hash perkalian pendek (indeks cache warna) dari warna yang baru dilihat.
Sub-bagian berikut menjelaskan setiap detail tersebut secara mendetail.
5.2.1 Awalan Literal Kode
Piksel disimpan sebagai nilai berkode awalan hijau, merah, biru, dan alfa (dalam urutan tersebut). Lihat Bagian 6.2.3 untuk mengetahui detailnya.
5.2.2 Referensi Mundur LZ77
Referensi mundur adalah tuple panjang dan kode jarak:
- Panjang menunjukkan berapa banyak piksel dalam urutan baris pemindaian yang akan disalin.
- Kode jarak adalah angka yang menunjukkan posisi piksel yang terlihat sebelumnya, tempat piksel akan disalin. Pemetaan persisnya dijelaskan di bawah.
Nilai panjang dan jarak disimpan menggunakan pengkodean 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 apa adanya (tanpa kode entropi).
Rationale: Pendekatan ini mengurangi persyaratan penyimpanan untuk kode entropi. Selain itu, nilai besar biasanya jarang terjadi, 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 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 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 disebutkan sebelumnya, kode jarak adalah angka yang menunjukkan posisi piksel yang terlihat sebelumnya, tempat piksel akan disalin. Sub-bagian ini menentukan pemetaan antara kode jarak dan posisi piksel sebelumnya.
Kode jarak yang lebih besar dari 120 menunjukkan jarak piksel dalam urutan baris pemindaian, offset dengan 120.
Kode jarak terkecil [1..120] adalah khusus, dan dicadangkan untuk lingkungan dekat piksel saat ini. Lingkungan ini terdiri dari 120 piksel:
- Piksel yang berada 1 hingga 7 baris di atas piksel saat ini, dan 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 hingga 8 kolom di sebelah kiri piksel saat ini. [
8piksel 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 piksel di dekatnya, yaitu piksel di atas piksel saat ini (perbedaan 0 piksel dalam arah X dan 1 piksel dalam arah Y).
Demikian pula, kode jarak 3 menunjukkan piksel kiri atas.
Decoder dapat mengonversi kode jarak i menjadi jarak urutan baris 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 tercantum di atas dan xsize adalah lebar
gambar dalam piksel.
5.2.3 Coding Cache Warna
Cache warna menyimpan kumpulan 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 bernilai 0, tidak ada kode cache warna, dan tidak dikirimkan 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 color_cache sebesar (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 oleh (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 saat mendekode. Status cache warna dipertahankan dengan memasukkan setiap piksel, baik yang dihasilkan melalui referensi mundur maupun sebagai literal, ke dalam cache sesuai urutan munculnya dalam aliran.
6 Kode Entropi
6.1 Ringkasan
Sebagian besar data dikodekan menggunakan kode awalan kanonis. Oleh karena itu, kode dikirimkan dengan mengirimkan panjang kode awalan, bukan kode awalan yang sebenarnya.
Secara khusus, format ini menggunakan pengkodean awalan varian spasial. Dengan kata lain, blok gambar yang berbeda berpotensi menggunakan kode entropi yang berbeda.
Rasional: Area gambar yang berbeda dapat memiliki karakteristik yang berbeda. Jadi, mengizinkan mereka untuk menggunakan kode entropi yang berbeda memberikan lebih banyak fleksibilitas dan kemungkinan kompresi yang lebih baik.
6.2 Detail
Data gambar yang dienkode terdiri dari beberapa bagian:
- Mendekode dan membuat kode awalan
- Kode awalan meta
- Data gambar berentropi
6.2.1 Decoding dan Membangun Kode Awalan
Ada beberapa langkah dalam mendekode kode awalan.
Mendekode Panjang Kode:
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, ini adalah kode panjang kode sederhana, dan
- Jika bit ini adalah 0, nilainya adalah kode panjang kode normal.
Dalam kedua kasus tersebut, mungkin ada panjang kode yang tidak digunakan yang masih menjadi bagian dari streaming. Ini mungkin tidak efisien, tetapi diizinkan oleh formatnya. Pohon yang dideskripsikan harus berupa pohon biner yang lengkap. Node daun tunggal dianggap sebagai pohon biner lengkap dan dapat dienkode menggunakan kode panjang kode sederhana atau kode panjang kode normal. Saat melakukan coding node daun tunggal menggunakan kode panjang kode normal, semua kecuali satu panjang kode harus nol, dan nilai node daun tunggal ditandai dengan panjang 1 -- meskipun tidak ada bit yang digunakan saat pohon node daun tunggal tersebut digunakan.
(i) Kode Panjang Kode Sederhana:
Varian ini digunakan dalam kasus khusus jika hanya ada 1 atau 2 simbol awalan yang berada dalam rentang [0..255] dengan panjang kode 1. Semua panjang kode awalan lainnya secara implisit bernilai nol.
Bit pertama menunjukkan jumlah simbol:
int num_symbols = ReadBits(1) + 1;
Berikut adalah nilai simbol.
Simbol pertama ini dikodekan menggunakan 1 atau 8 bit tergantung pada nilai
is_first_8bits. Rentangnya masing-masing 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;
}
Catatan: Kasus khusus lainnya adalah saat 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 yang kosong dapat dikodekan sebagai kode yang berisi satu simbol 0.
(ii) Kode Panjang Kode Normal:
Panjang kode awalan kode dalam 8 bit dan dibaca sebagai berikut.
Pertama, num_code_lengths menentukan jumlah panjang kode.
int num_code_lengths = 4 + ReadBits(4);
Jika num_code_lengths > 19, bitstream tidak valid.
Panjang kode sendiri dienkode menggunakan kode awalan: panjang kode
level bawah, 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 adalah
num_code_lengths. Jika tidak, ini akan didefinisikan sebagai:
int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);
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 dikeluarkan, nilai 8 akan diulang. - Kode 17 memunculkan empat angka nol [3..10], yaitu
3 + ReadBits(3)kali. - Kode 18 memunculkan empat angka nol [11..138], yaitu,
11 + ReadBits(7)kali.
Setelah panjang kode dibaca, kode awalan untuk setiap jenis simbol (A, R, G, B, jarak) dibentuk menggunakan ukuran alfabetnya masing-masing:
- Saluran G: 256 + 24 +
color_cache_size - literal lainnya (A,R,B): 256
- kode jarak: 40
Kode Panjang Kode Normal harus mengkodekan pohon keputusan lengkap, yaitu, jumlah
2 ^ (-length) untuk semua kode bukan nol harus persis satu. Namun, ada satu pengecualian untuk aturan ini, pohon node daun tunggal, dengan nilai node daun ditandai dengan nilai 1 dan nilai lainnya adalah 0.
6.2.2 Dekode 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 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 gambar. Tidak ada data lagi yang disimpan.
- Jika bit ini adalah satu, gambar akan menggunakan beberapa kode awalan meta. Kode awalan meta ini disimpan sebagai gambar entropi (dijelaskan di bawah).
Gambar entropi:
Gambar entropi menentukan kode awalan yang digunakan di berbagai bagian gambar, seperti yang dijelaskan di bawah.
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 adalah seperti yang ditentukan awal.
Bit berikutnya berisi gambar entropi dengan lebar prefix_xsize dan tinggi
prefix_ysize.
Penafsiran Kode Awal Meta:
Untuk piksel tertentu (x, y), ada lima kode awalan yang terkait dengannya. Kode berikut 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.
- Kode awalan #5: digunakan untuk jarak referensi mundur.
Selanjutnya, kita merujuk pada kumpulan ini sebagai grup kode awalan.
Jumlah grup kode awalan dalam gambar ARGB dapat diperoleh dengan menemukan 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 kode awalan adalah:
int num_prefix_codes = 5 * num_prefix_groups;
Dengan piksel (x, y) dalam gambar ARGB, kita dapat 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];
dengan asumsi adanya struktur PrefixCodeGroup, yang
mewakili kumpulan 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 di bagian berikutnya.
6.2.3 Decoding Data Gambar Berenkode Entropi
Untuk posisi saat ini (x, y) dalam gambar, decoder terlebih dahulu mengidentifikasi grup kode awalan yang sesuai (seperti yang dijelaskan di bagian terakhir). Mengingat grup kode awalan, piksel dibaca dan didekode sebagai berikut:
Baca simbol S berikutnya 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:
- jika S < 256
- Gunakan S sebagai komponen hijau.
- Baca merah dari bitstream menggunakan kode awalan #2.
- Baca biru dari bitstream menggunakan kode awalan #3.
- Baca alfa dari bitstream menggunakan kode awalan #4.
- jika S >= 256 && S < 256 + 24
- Gunakan S - 256 sebagai kode awalan panjang.
- Membaca bit ekstra untuk panjang dari bitstream.
- Tentukan panjang referensi mundur L dari kode awalan panjang dan bit tambahan.
- Membaca kode awalan jarak dari bitstream menggunakan kode awalan #5.
- Membaca bit tambahan untuk jarak dari bitstream.
- Tentukan jarak referensi D ke belakang dari kode awalan jarak dan bit tambahan dibaca.
- Salin piksel L (dalam urutan baris pemindaian) dari urutan piksel sebelum piksel D.
- jika S >= 256 + 24
- Gunakan S - (256 + 24) sebagai indeks ke dalam cache warna.
- Mendapatkan warna ARGB dari cache warna pada indeks tersebut.
7 Struktur Format Secara Keseluruhan
Di bawah ini adalah format dalam Augmented Backus-Naur Form (ABNF). Halaman ini tidak mencakup semua detail. Akhir gambar (EOI) hanya dikodekan secara implisit ke jumlah piksel (xsize * ysize).
7.1 Struktur Dasar
format = RIFF-header image-header image-stream
RIFF-header = "RIFF" 4OCTET "WEBP" "VP8L" 4OCTET %x2F
image-header = 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)
Kemungkinan contoh urutan:
RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image