Jyrki Alakuijala, Ph.D., Google LLC, 09-03-2023
Abstract
WebP lossless adalah format gambar untuk kompresi lossless gambar ARGB. Format lossless menyimpan dan memulihkan nilai piksel dengan tepat, termasuk nilai warna untuk piksel yang nilai alfanya 0. Format tersebut menggunakan gambar subresolusi, yang disematkan secara rekursif ke dalam format itu sendiri, untuk menyimpan data statistik tentang gambar, seperti kode entropi yang digunakan, prediktor spasial, konversi ruang warna, dan tabel warna. Algoritma universal untuk kompresi data berurutan (LZ77), coding awalan, dan cache warna digunakan untuk kompresi data massal. Kecepatan decoding yang lebih cepat daripada PNG telah ditunjukkan, serta kompresi 25% lebih padat daripada yang dapat dicapai dengan format PNG saat ini.
1 Pengantar
Dokumen ini menjelaskan representasi data terkompresi dari gambar WebP lossless. File ini dimaksudkan sebagai referensi mendetail untuk implementasi encoder dan decoder WebP lossless.
Dalam dokumen ini, kami secara ekstensif menggunakan sintaksis bahasa pemrograman C untuk mendeskripsikan bitstream dan mengasumsikan keberadaan fungsi untuk membaca bit, ReadBits(n). Byte dibaca dalam urutan alami pada aliran data yang memuatnya, dan bit setiap byte dibaca dalam urutan bit-first yang paling tidak signifikan. Jika beberapa bit dibaca secara bersamaan, bilangan bulat akan dibuat dari data asli dalam urutan aslinya. Bit yang paling signifikan dari bilangan bulat
yang ditampilkan juga merupakan bit yang paling signifikan dari data asli. Sehingga, pernyataan
b = ReadBits(2);
setara dengan dua pernyataan berikut:
b = ReadBits(1);
b |= ReadBits(1) << 1;
Kami berasumsi bahwa setiap komponen warna, yaitu alfa, merah, biru, dan hijau, diwakili menggunakan byte 8 bit. Kita mendefinisikan jenis yang sesuai sebagai uint8. Seluruh piksel ARGB direpresentasikan oleh jenis yang disebut uint32, yang merupakan bilangan bulat tanpa tanda tangan yang terdiri dari 32 bit. Dalam kode yang menunjukkan perilaku transformasi, nilai ini dikodifikasi dalam bit berikut: alfa dalam bit 31..24, merah dalam bit 23..16, hijau dalam bit 15..8, dan biru dalam bit 7..0; namun, implementasi format ini bebas untuk menggunakan representasi lain secara internal.
Umumnya, gambar lossless WebP berisi data header, informasi transformasi, dan data gambar sebenarnya. Header berisi lebar dan tinggi gambar. Gambar lossless WebP dapat melewati empat jenis transformasi yang berbeda sebelum dienkode entropi. Informasi transformasi dalam bitstream berisi data yang diperlukan untuk menerapkan masing-masing transformasi terbalik.
2 Nomenklatur
- ARGB
- Nilai piksel yang terdiri dari nilai alfa, merah, hijau, dan biru.
- Gambar ARGB
- Array dua dimensi yang berisi piksel ARGB.
- cache warna
- Array kecil dengan alamat hash untuk menyimpan warna yang baru-baru ini digunakan agar dapat memanggilnya kembali dengan kode yang lebih pendek.
- gambar pengindeksan warna
- Gambar warna satu dimensi yang dapat diindeks menggunakan bilangan bulat kecil (hingga 256 dalam WebP lossless).
- gambar transformasi warna
- Gambar subresolusi dua dimensi yang berisi data tentang korelasi komponen warna.
- pemetaan jarak
- Mengubah jarak LZ77 agar memiliki nilai terkecil untuk piksel dalam kedekatan dua dimensi.
- gambar entropi
- Gambar subresolusi dua dimensi yang menunjukkan coding entropi mana yang harus digunakan dalam persegi masing-masing dalam gambar, yaitu, setiap piksel adalah kode awalan meta.
- LZ77
- Algoritme kompresi jendela geser berbasis kamus yang memancarkan simbol atau mendeskripsikannya sebagai urutan simbol terdahulu.
- Kode awalan meta
- Bilangan bulat kecil (hingga 16 bit) yang mengindeks elemen dalam tabel awalan meta.
- gambar prediktor
- Gambar subresolusi dua dimensi yang menunjukkan prediktor spasial mana yang digunakan untuk persegi tertentu dalam gambar.
- kode awalan
- Cara klasik untuk melakukan coding entropi dengan jumlah bit yang lebih kecil digunakan untuk kode yang lebih sering.
- coding awalan
- Cara untuk melakukan entropi kode bilangan bulat yang lebih besar, yang mengkodekan beberapa bit bilangan bulat menggunakan kode entropi dan mengkodekan bit yang tersisa secara mentah. Hal ini memungkinkan deskripsi kode entropi tetap relatif kecil meskipun rentang simbol besar.
- urutan pemindaian
- Urutan pemrosesan piksel (kiri ke kanan dan atas ke bawah), mulai dari piksel kiri atas. Setelah satu baris selesai, lanjutkan dari kolom sebelah kiri baris berikutnya.
3 Header RIFF
Bagian awal {i>header<i} berisi penampung RIFF. Proses ini terdiri dari 21 byte berikut:
- String 'RIFF'.
- Nilai kecil 32-bit dari panjang potongan, yang merupakan seluruh ukuran potongan yang dikontrol oleh header RIFF. Biasanya, ini sama dengan ukuran payload (ukuran file minus 8 byte: 4 byte untuk ID 'RIFF' dan 4 byte untuk menyimpan nilai itu sendiri).
- String 'WEBP' (nama penampung RIFF).
- String 'VP8L' (FourCC untuk data gambar dengan enkode lossless).
- Nilai 32-bit kecil-endian dari jumlah byte dalam aliran lossless.
- Tanda tangan 1-byte 0x2f.
28 bit pertama dari bitstream menentukan lebar dan tinggi gambar. Lebar dan tinggi didekode sebagai bilangan bulat 14-bit sebagai berikut:
int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;
Presisi 14-bit untuk lebar dan tinggi gambar membatasi ukuran maksimum gambar WebP lossless hingga 16384hingga 16384 piksel.
Bit alpha_is_used hanya merupakan petunjuk, dan tidak boleh memengaruhi decoding. Nilai ini harus disetel ke 0 jika semua nilai alfa dalam gambar adalah 255, dan 1 jika tidak dalam gambar.
int alpha_is_used = ReadBits(1);
version_number adalah kode 3 bit yang harus diatur ke 0. Nilai lain harus diperlakukan sebagai error.
int version_number = ReadBits(3);
4 Transformasi
Transformasi adalah manipulasi yang dapat dibalik pada data gambar yang dapat mengurangi entropi simbolis yang tersisa dengan memodelkan korelasi spasial dan warna. Filter dapat membuat kompresi akhir lebih padat.
Gambar dapat melalui empat jenis transformasi. Satu bit menunjukkan adanya transformasi. Setiap transformasi hanya diizinkan untuk digunakan satu kali. Transformasi hanya digunakan untuk gambar ARGB level utama; gambar sub-resolusi (gambar transformasi warna, gambar entropi, dan gambar prediktor) tidak memiliki transformasi, bahkan 0 bit yang menunjukkan akhir transformasi.
Biasanya, encoder akan menggunakan transformasi ini untuk mengurangi entropi Shannon pada gambar residual. Selain itu, data transformasi dapat ditentukan berdasarkan meminimalkan entropi.
while (ReadBits(1)) { // Transform present.
// Decode transform type.
enum TransformType transform_type = ReadBits(2);
// Decode transform data.
...
}
// Decode actual image data (Section 5).
Jika ada transformasi, dua bit berikutnya akan menentukan jenis transformasi. Ada empat jenis transformasi.
enum TransformType {
PREDICTOR_TRANSFORM = 0,
COLOR_TRANSFORM = 1,
SUBTRACT_GREEN_TRANSFORM = 2,
COLOR_INDEXING_TRANSFORM = 3,
};
Jenis transformasi diikuti dengan data transformasi. Data transformasi berisi informasi yang diperlukan untuk menerapkan transformasi terbalik dan bergantung pada jenis transformasi. Transformasi terbalik diterapkan dalam urutan terbalik yang dibaca dari bitstream, yaitu yang terakhir terlebih dahulu.
Selanjutnya, kami menjelaskan data transformasi untuk berbagai jenis.
4.1 Transformasi Prediktor
Transformasi prediktor dapat digunakan untuk mengurangi entropi dengan memanfaatkan fakta bahwa piksel di sekitar sering kali berkorelasi. Pada transformasi prediktor, nilai piksel saat ini diprediksi dari piksel yang telah didekode (dalam urutan baris pemindaian) dan hanya nilai residual (aktual - diprediksi) yang dienkode. Komponen hijau dari piksel menentukan mana dari 14 prediktor yang digunakan dalam blok tertentu dari gambar ARGB. Mode prediksi menentukan jenis prediksi yang akan digunakan. Kita membagi gambar menjadi kotak, dan semua piksel dalam persegi menggunakan mode prediksi yang sama.
3 bit pertama data prediksi menentukan lebar dan tinggi blok dalam jumlah bit. Jumlah kolom blok, block_xsize, digunakan dalam pengindeksan dua dimensi.
int size_bits = ReadBits(3) + 2;
int block_width = (1 << size_bits);
int block_height = (1 << size_bits);
#define DIV_ROUND_UP(num, den) (((num) + (den) - 1) / (den))
int block_xsize = DIV_ROUND_UP(image_width, 1 << size_bits);
Data transformasi berisi mode prediksi untuk setiap blok gambar. Ini
adalah gambar subresolusi dengan komponen piksel hijau menentukan mana dari
14 prediktor yang digunakan untuk semua piksel block_width * block_height dalam
blok tertentu gambar ARGB. Gambar subresolusi ini dienkode menggunakan
teknik yang sama seperti yang dijelaskan dalam Bab 5.
Untuk piksel (x, y), pengguna dapat menghitung alamat blok filter masing-masing dengan:
int block_index = (y >> size_bits) * block_xsize +
(x >> size_bits);
Ada 14 mode prediksi yang berbeda. Pada setiap mode prediksi, nilai piksel saat ini diprediksi dari satu atau beberapa piksel tetangga yang nilainya sudah diketahui.
Kita memilih piksel di dekatnya (TL, T, TR, dan L) dari piksel saat ini (P) sebagai berikut:
O O O O O O O O O O O
O O O O O O O O O O O
O O O O TL T TR O O O O
O O O O L P X X X X X
X X X X X X X X X X X
X X X X X X X X X X X
di mana TL berarti kiri atas, T berarti atas, TR berarti kanan atas, dan L berarti kiri. Pada saat memprediksi nilai P, semua piksel O, TL, T, TR, dan L sudah diproses, dan piksel P serta semua piksel X tidak diketahui.
Dengan mempertimbangkan piksel di dekatnya, mode prediksi yang berbeda ditentukan sebagai berikut.
| Mode | Prediksi nilai setiap saluran piksel saat ini |
|---|---|
| 0 | 0xff000000 (mewakili warna hitam solid dalam ARGB) |
| 1 | L |
| 2 | T |
| 3 | TR |
| 4 | TL |
| 5 | Rata-rata2(Rata-Rata2(L, TR), T) |
| 6 | Rata-Rata2(L, TL) |
| 7 | Rata-Rata2(L, T) |
| 8 | Rata-Rata2(TL, T) |
| 9 | Rata-Rata2(T, TR) |
| 10 | Rata-rata2(Rata-rata2(L, TL), Rata-rata2(T, TR)) |
| 11 | Select(L, T, TL) |
| 12 | ClampAddSubtractFull(L, T, TL) |
| 13 | ClampAddSubtractHalf(Rata-Rata2(L, T), TL) |
Average2 ditentukan sebagai berikut untuk setiap komponen ARGB:
uint8 Average2(uint8 a, uint8 b) {
return (a + b) / 2;
}
Prediktor Pilih ditentukan sebagai berikut:
uint32 Select(uint32 L, uint32 T, uint32 TL) {
// L = left pixel, T = top pixel, TL = top-left pixel.
// ARGB component estimates for prediction.
int pAlpha = ALPHA(L) + ALPHA(T) - ALPHA(TL);
int pRed = RED(L) + RED(T) - RED(TL);
int pGreen = GREEN(L) + GREEN(T) - GREEN(TL);
int pBlue = BLUE(L) + BLUE(T) - BLUE(TL);
// Manhattan distances to estimates for left and top pixels.
int pL = abs(pAlpha - ALPHA(L)) + abs(pRed - RED(L)) +
abs(pGreen - GREEN(L)) + abs(pBlue - BLUE(L));
int pT = abs(pAlpha - ALPHA(T)) + abs(pRed - RED(T)) +
abs(pGreen - GREEN(T)) + abs(pBlue - BLUE(T));
// Return either left or top, the one closer to the prediction.
if (pL < pT) {
return L;
} else {
return T;
}
}
Fungsi ClampAddSubtractFull dan ClampAddSubtractHalf dijalankan
untuk setiap komponen ARGB sebagai berikut:
// Clamp the input value between 0 and 255.
int Clamp(int a) {
return (a < 0) ? 0 : (a > 255) ? 255 : a;
}
int ClampAddSubtractFull(int a, int b, int c) {
return Clamp(a + b - c);
}
int ClampAddSubtractHalf(int a, int b) {
return Clamp(a + (a - b) / 2);
}
Ada aturan penanganan khusus untuk beberapa piksel batas. Jika ada transformasi prediksi, terlepas dari mode [0..13] untuk piksel ini, maka prediksi nilai untuk piksel paling atas kiri gambar adalah 0xff000000, semua piksel di baris atas adalah L-piksel, dan semua piksel di kolom paling kiri adalah T-piksel.
Menangani piksel TR untuk piksel di kolom paling kanan sangat luar biasa. Piksel di kolom paling kanan diprediksi menggunakan mode [0..13], seperti piksel yang tidak berada pada batas, tetapi piksel paling kiri pada baris yang sama dengan piksel saat ini digunakan sebagai piksel TR.
Nilai piksel akhir diperoleh dengan menambahkan setiap saluran nilai yang diprediksi ke nilai residual yang dienkode.
void PredictorTransformOutput(uint32 residual, uint32 pred,
uint8* alpha, uint8* red,
uint8* green, uint8* blue) {
*alpha = ALPHA(residual) + ALPHA(pred);
*red = RED(residual) + RED(pred);
*green = GREEN(residual) + GREEN(pred);
*blue = BLUE(residual) + BLUE(pred);
}
4.2 Transformasi Warna
Tujuan transformasi warna adalah untuk mendekorasi hubungan nilai-nilai R, G, dan B dari setiap piksel. Transformasi warna mempertahankan nilai hijau (G) sebagaimana adanya, mengubah nilai merah (R) berdasarkan nilai hijau, dan mengubah nilai biru (B) berdasarkan nilai hijau dan kemudian nilai merah.
Seperti halnya pada transformasi prediktor, pertama-tama gambar dibagi menjadi blok dan mode transformasi yang sama digunakan untuk semua piksel dalam blok. Untuk setiap blok, ada tiga jenis elemen transformasi warna.
typedef struct {
uint8 green_to_red;
uint8 green_to_blue;
uint8 red_to_blue;
} ColorTransformElement;
Transformasi warna sebenarnya dilakukan dengan menentukan delta transformasi warna. Delta transformasi warna bergantung pada ColorTransformElement, yang sama untuk semua piksel dalam blok tertentu. Delta dikurangkan selama transformasi warna. Kemudian, transformasi warna terbalik hanya menambahkan delta tersebut.
Fungsi transformasi warna ditentukan sebagai berikut:
void ColorTransform(uint8 red, uint8 blue, uint8 green,
ColorTransformElement *trans,
uint8 *new_red, uint8 *new_blue) {
// Transformed values of red and blue components
int tmp_red = red;
int tmp_blue = blue;
// Applying the transform is just subtracting the transform deltas
tmp_red -= ColorTransformDelta(trans->green_to_red, green);
tmp_blue -= ColorTransformDelta(trans->green_to_blue, green);
tmp_blue -= ColorTransformDelta(trans->red_to_blue, red);
*new_red = tmp_red & 0xff;
*new_blue = tmp_blue & 0xff;
}
ColorTransformDelta dihitung menggunakan bilangan bulat 8-bit bertanda yang merepresentasikan
angka 3,5 titik tetap dan saluran warna RGB 8-bit bertanda tangan (c) [-128..127]
dan ditentukan sebagai berikut:
int8 ColorTransformDelta(int8 t, int8 c) {
return (t * c) >> 5;
}
Konversi dari representasi 8-bit tanpa tanda tangan (uint8) ke representasi 8-bit yang ditandatangani (int8) diperlukan sebelum memanggil ColorTransformDelta(). Nilai yang ditandatangani
harus ditafsirkan sebagai bilangan pelengkap dua 8-bit (yaitu: rentang uint8
[128..255] dipetakan ke rentang [-128..-1] dari nilai int8 yang dikonversi).
Perkalian harus dilakukan secara lebih presisi (dengan presisi setidaknya 16-bit). Properti ekstensi tanda dari operasi pergeseran tidak penting di sini; hanya 8 bit terendah yang digunakan dari hasil, dan di sana pergeseran ekstensi tanda dan pergeseran yang tidak ditandatangani bersifat konsisten satu sama lain.
Sekarang, kita akan menjelaskan konten data transformasi warna sehingga decoding dapat menerapkan transformasi warna terbalik dan memulihkan nilai merah dan biru yang asli. Tiga bit pertama dari data transformasi warna berisi lebar dan tinggi blok gambar dalam jumlah bit, seperti halnya transformasi prediktor:
int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;
Bagian yang tersisa dari data transformasi warna berisi instance ColorTransformElement, yang sesuai dengan setiap blok gambar. Setiap
ColorTransformElement 'cte' diperlakukan sebagai piksel dalam gambar subresolusi
yang komponen alfanya adalah 255, komponen merah adalah cte.red_to_blue, komponen
hijau adalah cte.green_to_blue, dan komponen biru adalah cte.green_to_red.
Selama decoding, instance ColorTransformElement blok didekode dan
transformasi warna terbalik diterapkan pada nilai ARGB piksel. Seperti
yang disebutkan sebelumnya, transformasi warna terbalik hanya menambahkan
nilai ColorTransformElement ke saluran merah dan biru. Saluran alfa dan hijau
tidak akan diubah.
void InverseTransform(uint8 red, uint8 green, uint8 blue,
ColorTransformElement *trans,
uint8 *new_red, uint8 *new_blue) {
// Transformed values of red and blue components
int tmp_red = red;
int tmp_blue = blue;
// Applying the inverse transform is just adding the
// color transform deltas
tmp_red += ColorTransformDelta(trans->green_to_red, green);
tmp_blue += ColorTransformDelta(trans->green_to_blue, green);
tmp_blue +=
ColorTransformDelta(trans->red_to_blue, tmp_red & 0xff);
*new_red = tmp_red & 0xff;
*new_blue = tmp_blue & 0xff;
}
4.3 Mengurangi Transformasi Hijau
Transformasi hijau mengurangi nilai hijau dari nilai merah dan biru dari setiap piksel. Jika transformasi ini ada, decoder harus menambahkan nilai hijau ke nilai merah dan biru. Tidak ada data yang terkait dengan transformasi ini. Decoder menerapkan transformasi terbalik sebagai berikut:
void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
*red = (*red + green) & 0xff;
*blue = (*blue + green) & 0xff;
}
Transformasi ini redundan, karena dapat dimodelkan menggunakan transformasi warna, tetapi karena tidak ada data tambahan di sini, transformasi pengurangan hijau dapat dikodekan menggunakan lebih sedikit bit daripada transformasi warna full-blown.
4.4 Transformasi Pengindeksan Warna
Jika tidak ada banyak nilai piksel unik, mungkin akan lebih efisien untuk membuat array indeks warna dan mengganti nilai piksel dengan indeks array. Transformasi pengindeksan warna mencapai hal ini. (Dalam konteks WebP lossless, kami secara khusus tidak menyebut ini sebagai transformasi palet karena konsep yang serupa tetapi lebih dinamis ada dalam encoding lossless WebP: cache warna.)
Transformasi pengindeksan warna memeriksa jumlah nilai ARGB unik dalam gambar. Jika angka tersebut di bawah ambang batas (256), array nilai ARGB akan dibuat, yang kemudian digunakan untuk mengganti nilai piksel dengan indeks terkait: saluran hijau piksel diganti dengan indeks, semua nilai alfa disetel ke 255, dan semua nilai merah dan biru ke 0.
Data transformasi berisi ukuran tabel warna dan entri dalam tabel warna. Decoder membaca data transformasi pengindeksan warna sebagai berikut:
// 8-bit value for the color table size
int color_table_size = ReadBits(8) + 1;
Tabel warna disimpan menggunakan format penyimpanan gambar itu sendiri. Tabel warna
dapat diperoleh dengan membaca gambar, tanpa header RIFF, ukuran gambar, dan
transformasi, dengan asumsi tinggi 1 piksel dan lebar color_table_size.
Tabel warna selalu diberi kode pengurangan untuk mengurangi entropi gambar. Delta
warna palet biasanya berisi entropi yang jauh lebih sedikit daripada warna
itu sendiri, sehingga dapat menghemat signifikan untuk gambar yang lebih kecil. Dalam decoding,
setiap warna akhir dalam tabel warna dapat diperoleh dengan menambahkan nilai komponen
warna sebelumnya oleh setiap komponen ARGB secara terpisah, dan menyimpan hasil
8 bit yang paling tidak signifikan.
Transformasi terbalik untuk gambar hanya mengganti nilai piksel (yang merupakan indeks tabel warna) dengan nilai tabel warna sebenarnya. Pengindeksan dilakukan berdasarkan komponen hijau dari warna ARGB.
// Inverse transform
argb = color_table[GREEN(argb)];
Jika indeks sama dengan atau lebih besar dari color_table_size, nilai warna aRGB
harus disetel ke 0x00000000 (hitam transparan).
Jika tabel warna berukuran kecil (sama dengan atau kurang dari 16 warna), beberapa piksel akan dipaketkan menjadi satu piksel. Paket piksel menggabungkan beberapa (2, 4, atau 8) piksel menjadi satu piksel, yang masing-masing mengurangi lebar gambar. Pemaketan piksel memungkinkan coding entropi distribusi gabungan yang lebih efisien pada piksel di dekatnya dan memberikan beberapa manfaat seperti coding aritmetika pada kode entropi, tetapi hanya dapat digunakan jika ada 16 nilai unik atau kurang.
color_table_size menentukan jumlah piksel yang digabungkan:
int width_bits;
if (color_table_size <= 2) {
width_bits = 3;
} else if (color_table_size <= 4) {
width_bits = 2;
} else if (color_table_size <= 16) {
width_bits = 1;
} else {
width_bits = 0;
}
width_bits memiliki nilai 0, 1, 2, atau 3. Nilai 0 menunjukkan tidak ada pemaketan piksel
yang harus dilakukan untuk gambar. Nilai 1 menunjukkan bahwa dua piksel
digabungkan, dan setiap piksel memiliki rentang [0..15]. Nilai 2 menunjukkan bahwa
empat piksel digabungkan, dan setiap piksel memiliki rentang [0..3]. Nilai 3
menunjukkan bahwa delapan piksel digabungkan dan setiap piksel memiliki rentang [0..1],
yaitu nilai biner.
Nilai dikemas ke dalam komponen hijau sebagai berikut:
width_bits= 1: Untuk setiap nilai x, dengan x ≡ 0 (mod 2), nilai hijau di x diposisikan ke dalam 4 bit paling tidak signifikan dari nilai hijau di x / 2, dan nilai hijau pada x + 1 diposisikan ke dalam 4 bit paling signifikan dari nilai hijau di x / 2.width_bits= 2: Untuk setiap nilai x, dengan x ≡ 0 (mod 4), nilai hijau di x diposisikan ke dalam 2 bit yang paling tidak signifikan dari nilai hijau di x / 4, dan nilai hijau pada x + 1 hingga x + 3 diposisikan sesuai dengan bit nilai hijau yang lebih signifikan di x / 4.width_bits= 3: Untuk setiap nilai x, dengan x ≡ 0 (mod 8), nilai hijau di x diposisikan di bit nilai hijau yang paling tidak signifikan pada x / 8, dan nilai hijau pada x + 1 hingga x + 7 diposisikan dalam urutan untuk bit nilai hijau yang lebih signifikan di x / 8.
Setelah membaca transformasi ini, image_width akan disubsampel oleh width_bits. Hal ini
memengaruhi ukuran transformasi berikutnya. Ukuran baru dapat dihitung menggunakan
DIV_ROUND_UP, seperti yang ditentukan sebelumnya.
image_width = DIV_ROUND_UP(image_width, 1 << width_bits);
5 Data Gambar
Data gambar adalah array nilai piksel dalam urutan garis pemindaian.
5.1 Peran Data Gambar
Kami menggunakan data gambar dalam lima peran yang berbeda:
- Gambar ARGB: Menyimpan piksel gambar yang sebenarnya.
- Image entropi: Menyimpan kode awalan meta (lihat "Decoding Kode Awalan Meta").
- Gambar prediktif: Menyimpan metadata untuk transformasi prediktor (lihat "Transformasi Prediktor").
- Gambar transformasi warna: Dibuat oleh nilai
ColorTransformElement(didefinisikan dalam "Transformasi Warna") untuk berbagai blok gambar. - Gambar pengindeksan warna: Array dengan ukuran
color_table_size(hingga 256 nilai ARGB) yang menyimpan metadata untuk transformasi pengindeksan warna (lihat "Color Indexing Transform").
5.2 Encoding Data Gambar
Encoding data gambar tidak bergantung pada perannya.
Pertama-tama, gambar dibagi menjadi satu set blok berukuran tetap (biasanya 16x16 blok). Setiap blok ini dimodelkan menggunakan kode entropinya sendiri. Selain itu, beberapa blok dapat memiliki kode entropi yang sama.
Rasional: Penyimpanan kode entropi akan dikenai biaya. Biaya ini dapat diminimalkan jika blok yang serupa secara statistik berbagi kode entropi, sehingga kode tersebut hanya disimpan sekali. Misalnya, encoder dapat menemukan blok serupa dengan mengelompokkannya menggunakan properti statistiknya atau dengan berulang kali menggabungkan sepasang cluster yang dipilih secara acak saat mengurangi jumlah keseluruhan bit yang diperlukan untuk mengenkode gambar.
Setiap piksel dienkode menggunakan salah satu dari tiga metode yang dapat digunakan:
- Literal kode awal: Setiap saluran (hijau, merah, biru, dan alfa) dikodekan secara entropi secara terpisah.
- Referensi mundur LZ77: Urutan piksel disalin dari tempat lain dalam gambar.
- Kode cache warna: Menggunakan kode hash multiplikatif singkat (indeks cache warna) dari warna yang baru dilihat.
Sub-bagian berikut menjelaskan setiap hal tersebut secara mendetail.
5.2.1 Literal Kode Awal
Piksel disimpan sebagai nilai berkode awalan warna hijau, merah, biru, dan alfa (dalam urutan tersebut). Lihat Pasal 6.2.3 untuk mengetahui detailnya.
5.2.2 Referensi Mundur LZ77
Referensi mundur adalah tupel panjang dan kode jarak:
- Panjang menunjukkan jumlah piksel dalam urutan baris pemindaian yang akan disalin.
- Kode jarak adalah angka yang menunjukkan posisi piksel yang terlihat sebelumnya, tempat piksel yang akan disalin. Pemetaan persisnya dijelaskan di bawah.
Nilai panjang dan jarak disimpan menggunakan Coding awalan LZ77.
Coding awalan LZ77 membagi nilai bilangan bulat besar menjadi dua bagian: kode awalan dan bit tambahan. Kode awalan disimpan menggunakan kode entropi, sedangkan bit tambahan disimpan sebagaimana adanya (tanpa kode entropi).
Rasionale: Pendekatan ini mengurangi persyaratan penyimpanan untuk kode entropi. Selain itu, nilai besar biasanya jarang muncul, sehingga bit tambahan akan digunakan untuk beberapa nilai dalam gambar. Dengan demikian, pendekatan ini menghasilkan kompresi yang lebih baik secara keseluruhan.
Tabel berikut menunjukkan kode awalan dan bit tambahan yang digunakan untuk menyimpan rentang nilai yang berbeda.
| Rentang nilai | Kode awalan | Bit tambahan |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 0 |
| 3 | 2 | 0 |
| 4 | 3 | 0 |
| 5,6 | 4 | 1 |
| 7,8 | 5 | 1 |
| 9,12 | 6 | 2 |
| 13.16 | 7 | 2 |
| ... | ... | ... |
| 3072.4096 | 23 | 10 |
| ... | ... | ... |
| 524289.786432 | 38 | 18 |
| 786433..1048576 | 39 | 18 |
Kode semu untuk mendapatkan nilai (panjang atau jarak) dari kode awalan adalah sebagai berikut:
if (prefix_code < 4) {
return prefix_code + 1;
}
int extra_bits = (prefix_code - 2) >> 1;
int offset = (2 + (prefix_code & 1)) << extra_bits;
return offset + ReadBits(extra_bits) + 1;
Pemetaan Jarak
Seperti yang telah disebutkan sebelumnya, kode jarak adalah angka yang menunjukkan posisi piksel yang terlihat sebelumnya, tempat piksel akan disalin. Subbagian ini menentukan pemetaan antara kode jarak dan posisi piksel sebelumnya.
Kode jarak yang lebih besar dari 120 menunjukkan jarak piksel dalam urutan garis pemindaian, offset 120.
Kode jarak terkecil [1..120] bersifat khusus dan disediakan untuk lingkungan yang dekat dari piksel saat ini. Lingkungan ini terdiri dari 120 piksel:
- Piksel yang berjarak 1 hingga 7 baris di atas piksel saat ini dan merupakan hingga 8 kolom
di sebelah kiri atau hingga 7 kolom di sebelah kanan piksel saat ini. [Total
piksel tersebut =
7 * (8 + 1 + 7) = 112]. - Piksel yang berada di baris yang sama dengan piksel saat ini dan berjarak hingga 8
kolom di sebelah kiri piksel saat ini. [
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 di dekatnya, yaitu piksel di atas piksel saat ini (perbedaan
0 piksel dalam arah X dan perbedaan 1 piksel pada arah Y).
Demikian pula, kode jarak 3 menunjukkan piksel kiri atas.
Decoder dapat mengonversi kode jarak i menjadi jarak urutan garis pemindaian dist
sebagai berikut:
(xi, yi) = distance_map[i - 1]
dist = xi + yi * xsize
if (dist < 1) {
dist = 1
}
dengan distance_map adalah pemetaan yang disebutkan di atas, dan xsize adalah lebar
gambar dalam piksel.
5.2.3 Pengkodean Cache Warna
Cache warna menyimpan serangkaian warna yang baru-baru ini digunakan dalam gambar.
Rasional: Dengan cara ini, warna yang baru-baru ini digunakan terkadang dapat dirujuk secara lebih efisien daripada memunculkannya menggunakan dua metode lainnya (dijelaskan dalam 5.2.1 dan 5.2.2).
Kode cache warna disimpan sebagai berikut. Pertama, ada nilai 1-bit yang menunjukkan apakah cache warna digunakan. Jika bit ini 0, tidak ada kode cache warna dan kode tersebut tidak akan ditransmisikan dalam kode awalan yang mendekode simbol hijau dan kode awalan panjang. Namun, jika bit ini adalah 1, ukuran cache warna akan dibaca berikutnya:
int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;
color_cache_code_bits menentukan ukuran cache warna (1 <<
color_cache_code_bits). Rentang nilai yang diizinkan untuk
color_cache_code_bits adalah [1..11]. Decoder yang mematuhi kebijakan harus menunjukkan
bitstream yang rusak untuk nilai lain.
Cache warna adalah array ukuran color_cache_size. Setiap entri menyimpan
satu warna ARGB. Warna dicari dengan mengindeksnya berdasarkan (0x1e35a7bd * color) >> (32 -
color_cache_code_bits). Hanya satu pencarian yang dilakukan dalam cache warna; tidak ada
penyelesaian konflik.
Pada awal decoding atau encoding gambar, semua entri dalam semua nilai cache warna ditetapkan ke nol. Kode cache warna dikonversi ke warna ini pada waktu decoding. Status cache warna dipertahankan dengan memasukkan setiap piksel, baik yang dihasilkan oleh referensi mundur maupun sebagai literal, ke dalam cache sesuai urutan kemunculannya dalam aliran.
6 Kode Entropi
6.1 Ringkasan
Sebagian besar data dikodekan menggunakan kode awalan kanonis. Oleh karena itu, kode tersebut dikirim dengan mengirimkan panjang kode awalan, berbeda dengan kode awalan yang sebenarnya.
Secara khusus, format tersebut menggunakan coding awalan varian spasial. Dengan kata lain, blok gambar yang berbeda berpotensi menggunakan kode entropi yang berbeda.
Rasional: Area gambar yang berbeda mungkin memiliki karakteristik yang berbeda. Jadi, mengizinkan entropi menggunakan kode entropi yang berbeda akan memberikan fleksibilitas yang lebih besar dan kompresi yang berpotensi lebih baik.
6.2 Rincian
Data gambar yang dienkode terdiri dari beberapa bagian:
- Mendekode dan membuat kode awalan.
- Kode awalan meta.
- Data gambar berkode entropi.
Untuk piksel tertentu (x, y), ada sekumpulan lima kode awalan yang terkait dengannya. Kode ini adalah (dalam urutan bitstream):
- Kode awalan #1: Digunakan untuk saluran hijau, panjang referensi mundur, dan cache warna.
- Kode awalan #2, #3, dan #4: Digunakan masing-masing untuk saluran merah, biru, dan alfa.
- Kode awalan #5: Digunakan untuk jarak referensi mundur.
Selanjutnya, kami menyebut kumpulan tersebut sebagai grup kode awalan.
6.2.1 Mendekode dan Membuat Kode Awalan
Bagian ini menjelaskan cara membaca panjang kode awalan dari bitstream.
Panjang kode awalan dapat dikodekan dengan dua cara. Metode yang digunakan ditetapkan oleh nilai 1-bit.
- Jika bit ini adalah 1, berarti kode panjang kode sederhana.
- Jika bit ini 0, berarti kode panjang kode normal.
Dalam kedua kasus tersebut, mungkin ada panjang kode yang tidak digunakan yang masih menjadi bagian dari aliran. Hal ini mungkin tidak efisien, tetapi diizinkan oleh format. Hierarki yang dijelaskan harus berupa hierarki biner lengkap. Node leaf tunggal dianggap sebagai hierarki biner lengkap dan dapat dienkode menggunakan kode panjang kode sederhana atau kode panjang kode normal. Saat melakukan coding pada satu node leaf menggunakan kode panjang kode normal, semua kecuali satu panjang kode adalah nol, dan nilai node daun tunggal ditandai dengan panjang 1 -- bahkan jika tidak ada bit yang digunakan saat pohon node satu daun tersebut digunakan.
Kode Panjang Kode Sederhana
Varian ini digunakan dalam kasus khusus jika hanya 1 atau 2 simbol awalan yang berada dalam
rentang [0..255] dengan panjang kode 1. Semua panjang kode awalan lainnya
secara implisit adalah nol.
Bit pertama menunjukkan jumlah simbol:
int num_symbols = ReadBits(1) + 1;
Berikut ini adalah nilai simbol.
Simbol pertama ini dikodekan menggunakan 1 atau 8 bit, bergantung pada nilai
is_first_8bits. Rentangnya adalah [0..1] atau [0..255]. Simbol kedua, jika ada, selalu diasumsikan berada dalam rentang [0..255] dan dikodekan menggunakan 8 bit.
int is_first_8bits = ReadBits(1);
symbol0 = ReadBits(1 + 7 * is_first_8bits);
code_lengths[symbol0] = 1;
if (num_symbols == 2) {
symbol1 = ReadBits(8);
code_lengths[symbol1] = 1;
}
Kedua simbol tersebut harus berbeda. Simbol duplikat diizinkan, tetapi tidak efisien.
Catatan: Kasus khusus lainnya adalah jika semua panjang kode awalan adalah nol (kode awalan kosong). Misalnya, kode awalan untuk jarak bisa kosong jika
tidak ada referensi mundur. Demikian pula, kode awalan untuk alfa, merah, dan biru dapat kosong jika semua piksel dalam kode awalan meta yang sama dihasilkan menggunakan cache warna. Namun, kasus ini tidak memerlukan penanganan khusus, karena
kode awalan kosong dapat dikodekan sebagai kode yang berisi satu simbol 0.
Kode Panjang Kode Normal
Panjang kode awalan sesuai 8 bit dan dibaca sebagai berikut.
Pertama, num_code_lengths menentukan jumlah panjang kode.
int num_code_lengths = 4 + ReadBits(4);
Panjang kode itu sendiri dienkode menggunakan kode awalan; panjang kode pada tingkat yang lebih rendah, code_length_code_lengths, harus dibaca terlebih dahulu. Sisa dari code_length_code_lengths itu (sesuai dengan urutan dalam kCodeLengthCodeOrder) adalah nol.
int kCodeLengthCodes = 19;
int kCodeLengthCodeOrder[kCodeLengthCodes] = {
17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
};
int code_length_code_lengths[kCodeLengthCodes] = { 0 }; // All zeros
for (i = 0; i < num_code_lengths; ++i) {
code_length_code_lengths[kCodeLengthCodeOrder[i]] = ReadBits(3);
}
Berikutnya, jika ReadBits(1) == 0, jumlah maksimum simbol baca yang berbeda
(max_symbol) untuk setiap jenis simbol (A, R, G, B, dan jarak) ditetapkan ke
ukuran alfabet:
- Saluran G: 256 + 24 +
color_cache_size - Literal lain (A, R, dan B): 256
- Kode jarak: 40
Jika tidak, ini akan didefinisikan sebagai:
int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);
Jika max_symbol lebih besar dari ukuran alfabet untuk jenis simbol, bitstream tidak akan valid.
Tabel awalan kemudian dibuat dari code_length_code_lengths dan digunakan untuk membaca hingga
panjang kode max_symbol.
- Kode [0..15] menunjukkan panjang kode literal.
- Nilai 0 berarti tidak ada simbol yang dikodekan.
- Nilai [1..15] menunjukkan panjang bit kode masing-masing.
- Kode 16 mengulangi nilai bukan nol sebelumnya [3..6] kali, yaitu,
3 + ReadBits(2)kali. Jika kode 16 digunakan sebelum nilai bukan nol yang dimunculkan, nilai 8 akan diulang. - Kode 17 memunculkan garis dengan panjang nol [3..10], yaitu,
3 + ReadBits(3)kali. - Kode 18 memunculkan garis dengan panjang nol [11..138], yaitu,
11 + ReadBits(7)kali.
Setelah panjang kode dibaca, kode awalan untuk setiap jenis simbol (A, R, G, B, dan jarak) akan dibuat menggunakan ukuran alfabet masing-masing.
Kode Panjang Kode Normal harus mengkodekan pohon keputusan lengkap, yaitu, jumlah 2 ^ (-length) untuk semua kode bukan nol harus tepat satu. Namun, ada
satu pengecualian untuk aturan ini, pohon node daun tunggal, dengan nilai node
leaf ditandai dengan nilai 1 dan nilai-nilai lainnya adalah 0s.
6.2.2 Dekode Kode Awalan Meta
Seperti yang telah disebutkan sebelumnya, format ini memungkinkan penggunaan kode awalan yang berbeda untuk blok gambar yang berbeda. Kode awalan meta adalah indeks yang mengidentifikasi kode awalan yang akan digunakan di berbagai bagian gambar.
Kode awalan meta dapat digunakan hanya jika gambar digunakan dalam peran gambar ARGB.
Ada dua kemungkinan untuk kode awalan meta, yang ditunjukkan oleh nilai 1-bit:
- Jika bit ini nol, hanya ada satu kode awalan meta yang digunakan di mana pun dalam image. Tidak ada lagi data yang disimpan.
- Jika bit ini satu, image menggunakan beberapa kode awalan meta. Kode awalan meta ini disimpan sebagai image entropi (dijelaskan di bawah).
Komponen merah dan hijau dari sebuah piksel menentukan kode awalan meta 16-bit yang digunakan dalam blok tertentu dari gambar ARGB.
Gambar Entropi
Gambar entropi menentukan kode awalan mana yang digunakan di berbagai bagian gambar.
3 bit pertama berisi nilai prefix_bits. Dimensi gambar entropi berasal dari prefix_bits:
int prefix_bits = ReadBits(3) + 2;
int prefix_xsize = DIV_ROUND_UP(xsize, 1 << prefix_bits);
int prefix_ysize = DIV_ROUND_UP(ysize, 1 << prefix_bits);
dengan DIV_ROUND_UP seperti yang ditentukan sebelumnya.
Bit berikutnya berisi gambar entropi dengan lebar prefix_xsize dan tinggi
prefix_ysize.
Penafsiran Kode Awalan Meta
Jumlah grup kode awalan dalam gambar ARGB dapat diperoleh dengan mencari kode awalan meta terbesar dari gambar entropi:
int num_prefix_groups = max(entropy image) + 1;
dengan max(entropy image) menunjukkan kode awalan terbesar yang disimpan dalam image entropi.
Karena setiap grup kode awalan berisi lima kode awalan, jumlah total kode awalan adalah:
int num_prefix_codes = 5 * num_prefix_groups;
Dengan mempertimbangkan piksel (x, y) dalam gambar ARGB, kita bisa memperoleh kode awalan yang sesuai untuk digunakan sebagai berikut:
int position =
(y >> prefix_bits) * prefix_xsize + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[position] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];
tempat kita mengasumsikan keberadaan struktur PrefixCodeGroup, yang mewakili sekumpulan lima kode awalan. Selain itu, prefix_code_groups adalah array dari
PrefixCodeGroup (dengan ukuran num_prefix_groups).
Decoder kemudian menggunakan grup kode awalan prefix_group untuk mendekode piksel
(x, y), seperti yang dijelaskan dalam "Mendekode Data Gambar Entropi".
6.2.3 Mendekode Data Gambar Entropi
Untuk posisi saat ini (x, y) pada gambar, decoder terlebih dahulu mengidentifikasi grup kode awalan yang sesuai (seperti yang dijelaskan di bagian terakhir). Dengan grup kode awalan, piksel akan dibaca dan didekode sebagai berikut.
Selanjutnya, baca simbol S dari
bitstream menggunakan kode awalan #1. Perhatikan bahwa S adalah
bilangan bulat dalam rentang 0 hingga
(256 + 24 + color_cache_size- 1).
Penafsiran S bergantung pada nilainya:
- Jika S < 256
- Gunakan S sebagai komponen hijau.
- Membaca warna merah dari bitstream menggunakan kode awalan #2.
- Membaca warna biru dari bitstream menggunakan kode awalan #3.
- Membaca alfa dari bitstream menggunakan kode awalan #4.
- Jika S >= 256 & S < 256 + 24
- Gunakan S - 256 sebagai kode awalan yang panjang.
- Membaca bit tambahan untuk panjang dari bitstream.
- Tentukan panjang referensi mundur L dari kode awalan yang panjang dan bit tambahan yang dibaca.
- Baca kode awalan jarak dari bitstream menggunakan kode awalan #5.
- Membaca bit tambahan untuk jarak dari bitstream.
- Tentukan jarak referensi mundur D dari kode awalan jarak dan bit tambahan yang dibaca.
- Salin piksel L (dalam urutan garis pemindaian) dari urutan piksel yang dimulai pada posisi saat ini dikurangi D piksel.
- 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 Keseluruhan
Berikut adalah tampilan dalam format dalam Augmented Backus-Naur Form (ABNF) RFC 5234 RFC 7405. Artikel ini tidak mencakup semua detail. Akhir gambar (EOI) hanya dikodekan secara implisit ke dalam jumlah piksel (xsize * ysize).
Perhatikan bahwa *element berarti element dapat diulang 0 kali atau lebih. 5element
berarti element diulang tepat 5 kali. %b merepresentasikan nilai biner.
7.1 Struktur Dasar
format = RIFF-header image-header image-stream
RIFF-header = %s"RIFF" 4OCTET %s"WEBPVP8L" 4OCTET
image-header = %x2F image-size alpha-is-used version
image-size = 14BIT 14BIT ; width - 1, height - 1
alpha-is-used = 1BIT
version = 3BIT ; 0
image-stream = optional-transform spatially-coded-image
7.2 Struktur Transformasi
optional-transform = (%b1 transform optional-transform) / %b0
transform = predictor-tx / color-tx / subtract-green-tx
transform =/ color-indexing-tx
predictor-tx = %b00 predictor-image
predictor-image = 3BIT ; sub-pixel code
entropy-coded-image
color-tx = %b01 color-image
color-image = 3BIT ; sub-pixel code
entropy-coded-image
subtract-green-tx = %b10
color-indexing-tx = %b11 color-indexing-image
color-indexing-image = 8BIT ; color count
entropy-coded-image
7.3 Struktur Data Gambar
spatially-coded-image = color-cache-info meta-prefix data
entropy-coded-image = color-cache-info data
color-cache-info = %b0
color-cache-info =/ (%b1 4BIT) ; 1 followed by color cache size
meta-prefix = %b0 / (%b1 entropy-image)
data = prefix-codes lz77-coded-image
entropy-image = 3BIT ; subsample value
entropy-coded-image
prefix-codes = prefix-code-group *prefix-codes
prefix-code-group =
5prefix-code ; See "Interpretation of Meta Prefix Codes" to
; understand what each of these five prefix
; codes are for.
prefix-code = simple-prefix-code / normal-prefix-code
simple-prefix-code = ; see "Simple Code Length Code" for details
normal-prefix-code = ; see "Normal Code Length Code" for details
lz77-coded-image =
*((argb-pixel / lz77-copy / color-cache-code) lz77-coded-image)
Berikut ini adalah contoh urutan yang mungkin:
RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image