Jyrki Alakuijala, Ph.D., Google, Inc., 09-03-2023
Abstrak
WebP lossless adalah format gambar untuk kompresi lossless gambar ARGB. Format tanpa kehilangan data menyimpan dan memulihkan nilai piksel secara persis, termasuk nilai warna untuk piksel yang sepenuhnya transparan. Algoritma universal untuk kompresi data berurutan (LZ77), pengodean awalan, dan cache warna digunakan untuk kompresi data massal. Kecepatan decoding yang lebih cepat daripada PNG telah ditunjukkan, serta kompresi yang 25% lebih padat daripada yang dapat dicapai menggunakan format PNG saat ini.
1 Pengantar
Dokumen ini menjelaskan representasi data terkompresi dari gambar WebP lossless. Dokumen ini dimaksudkan sebagai referensi mendetail untuk penerapan encoder dan dekoder WebP lossless.
Dalam dokumen ini, kita banyak menggunakan sintaksis bahasa pemrograman C untuk menjelaskan bitstream dan mengasumsikan keberadaan fungsi untuk membaca bit, ReadBits(n). Byte dibaca dalam urutan alami aliran yang memuatnya, dan bit setiap byte dibaca dalam urutan bit paling tidak signifikan terlebih dahulu. Jika
beberapa bit dibaca secara bersamaan, bilangan bulat dibuat dari
data asli dalam urutan aslinya. Bit paling signifikan dari bilangan bulat yang ditampilkan juga merupakan bit paling signifikan dari data asli. Jadi, pernyataan
b = ReadBits(2);
setara dengan dua pernyataan di bawah:
b = ReadBits(1);
b |= ReadBits(1) << 1;
Kita mengasumsikan bahwa setiap komponen warna, yaitu alpha, merah, biru, dan hijau, direpresentasikan menggunakan byte 8-bit. Kita mendefinisikan jenis yang sesuai sebagai uint8. Seluruh piksel ARGB diwakili oleh jenis yang disebut uint32, yang merupakan bilangan bulat tidak bertanda 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, penerapan format bebas menggunakan representasi lain secara internal.
Secara umum, gambar WebP lossless berisi data header, informasi transformasi, dan data gambar sebenarnya. Header berisi lebar dan tinggi gambar. Gambar lossless WebP dapat melalui empat jenis transformasi yang berbeda sebelum dienkode entropi. Informasi transformasi dalam bitstream berisi data yang diperlukan untuk menerapkan transformasi invers yang sesuai.
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 yang dialamatkan hash kecil untuk menyimpan warna yang baru saja digunakan agar dapat dipanggil kembali dengan kode yang lebih pendek.
- gambar pengindeksan warna
- Gambar satu dimensi dari warna yang dapat diindeks menggunakan bilangan bulat kecil (hingga 256 dalam WebP lossless).
- mengubah warna gambar
- 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 pengodean entropi mana yang harus digunakan dalam masing-masing persegi di gambar, yaitu setiap piksel adalah kode awalan meta.
- LZ77
- Algoritma kompresi jendela geser berbasis kamus yang memancarkan simbol atau mendeskripsikannya sebagai urutan simbol sebelumnya.
- kode awalan meta
- Bilangan bulat kecil (hingga 16 bit) yang mengindeks elemen dalam tabel awalan meta.
- gambar prediksi
- Gambar subresolusi dua dimensi yang menunjukkan prediktor spasial mana yang digunakan untuk persegi tertentu dalam gambar.
- kode awalan
- Cara klasik untuk melakukan pengodean entropi di mana sejumlah kecil bit digunakan untuk kode yang lebih sering.
- pengodean awalan
- Cara untuk mengodekan entropi bilangan bulat yang lebih besar, yang mengodekan beberapa bit bilangan bulat menggunakan kode entropi dan mengodekan bit yang tersisa secara mentah. Hal ini memungkinkan deskripsi kode entropi tetap relatif kecil meskipun rentang simbolnya besar.
- urutan garis pemindaian
- Urutan pemrosesan piksel (kiri ke kanan dan atas ke bawah), dimulai dari piksel kiri atas. Setelah baris selesai, lanjutkan dari kolom sebelah kiri baris berikutnya.
3 Header RIFF
Awal header memiliki penampung RIFF. Ini terdiri dari 21 byte berikut:
- String 'RIFF'.
- Nilai panjang potongan 32-bit little-endian, yang merupakan ukuran keseluruhan potongan 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 penampung RIFF).
- String 'VP8L' (FourCC untuk data gambar yang dienkode lossless).
- Nilai 32-bit little-endian dari jumlah byte dalam streaming 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 menjadi 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 dalam gambar adalah 255, dan 1 jika tidak.
int alpha_is_used = ReadBits(1);
version_number adalah kode 3 bit yang harus disetel ke 0. Nilai lainnya harus diperlakukan sebagai error.
int version_number = ReadBits(3);
4 Transformasi
Transformasi adalah manipulasi data gambar yang dapat dibalikkan yang dapat mengurangi entropi simbolik yang tersisa dengan memodelkan korelasi spasial dan warna. Dapat membuat kompresi akhir lebih padat.
Gambar dapat melalui empat jenis transformasi. 1 bit menunjukkan keberadaan transformasi. Setiap transformasi hanya dapat digunakan satu kali. Transformasi hanya digunakan untuk gambar ARGB tingkat utama; gambar subresolusi (gambar transformasi warna, gambar entropi, dan gambar prediksi) tidak memiliki transformasi, bahkan 0 bit yang menunjukkan akhir transformasi.
Biasanya, encoder akan menggunakan transformasi ini untuk mengurangi entropi Shannon dalam gambar residual. 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 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 invers diterapkan dalam urutan terbalik yang dibaca dari bitstream, yaitu yang terakhir terlebih dahulu.
Selanjutnya, kita akan menjelaskan transformasi data untuk berbagai jenis.
4.1 Transformasi Prediktor
Transformasi prediktor dapat digunakan untuk mengurangi entropi dengan memanfaatkan fakta bahwa piksel yang berdekatan sering kali berkorelasi. Dalam transformasi prediktor, nilai piksel saat ini diprediksi dari piksel yang sudah didekode (dalam urutan garis pemindaian) dan hanya nilai residual (aktual - prediksi) yang dienkode. Komponen hijau 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 beberapa 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. Gambar ini adalah gambar subresolusi yang komponen hijaunya menentukan prediktor 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), orang 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. Dalam setiap mode prediksi, nilai piksel saat ini diprediksi dari satu atau beberapa piksel di sekitarnya yang nilainya sudah diketahui.
Kami memilih piksel di sekitarnya (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 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, berbagai mode prediksi ditentukan sebagai berikut.
| Mode | Nilai yang diprediksi untuk setiap saluran piksel saat ini |
|---|---|
| 0 | 0xff000000 (mewakili warna hitam solid dalam ARGB) |
| 1 | L |
| 2 | T |
| 3 | TR |
| 4 | TL |
| 5 | Average2(Average2(L, TR), T) |
| 6 | Average2(L, TL) |
| 7 | Rata-rata2(L, T) |
| 8 | Average2(TL, T) |
| 9 | Average2(T, TR) |
| 10 | Average2(Average2(L, TL), Average2(T, TR)) |
| 11 | Select(L, T, TL) |
| 12 | ClampAddSubtractFull(L, T, TL) |
| 13 | ClampAddSubtractHalf(Average2(L, T), TL) |
Average2 ditentukan sebagai berikut untuk setiap komponen ARGB:
uint8 Average2(uint8 a, uint8 b) {
return (a + b) / 2;
}
Prediktor Select didefinisikan sebagai berikut:
uint32 Select(uint32 L, uint32 T, uint32 TL) {
// L = left pixel, T = top pixel, TL = top-left pixel.
// ARGB component estimates for prediction.
int pAlpha = ALPHA(L) + ALPHA(T) - ALPHA(TL);
int pRed = RED(L) + RED(T) - RED(TL);
int pGreen = GREEN(L) + GREEN(T) - GREEN(TL);
int pBlue = BLUE(L) + BLUE(T) - BLUE(TL);
// Manhattan distances to estimates for left and top pixels.
int pL = abs(pAlpha - ALPHA(L)) + abs(pRed - RED(L)) +
abs(pGreen - GREEN(L)) + abs(pBlue - BLUE(L));
int pT = abs(pAlpha - ALPHA(T)) + abs(pRed - RED(T)) +
abs(pGreen - GREEN(T)) + abs(pBlue - BLUE(T));
// Return either left or top, the one closer to the prediction.
if (pL < pT) {
return L;
} else {
return T;
}
}
Fungsi ClampAddSubtractFull dan ClampAddSubtractHalf 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.
Penanganan piksel TR untuk piksel di kolom paling kanan sangat baik. Piksel di kolom paling kanan diprediksi menggunakan mode [0..13], 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 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 menghilangkan korelasi 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, lalu berdasarkan nilai merah.
Seperti halnya transformasi prediktor, pertama-tama gambar dibagi menjadi 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 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 invers 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 merepresentasikan bilangan titik tetap 3,5 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 tidak bertanda 8-bit (uint8) ke representasi bertanda 8-bit (int8) diperlukan sebelum memanggil ColorTransformDelta(). Nilai bertanda
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 menggunakan presisi yang lebih tinggi (dengan presisi minimal 16-bit). Properti ekstensi tanda operasi shift tidak penting di sini; hanya 8 bit terendah yang digunakan dari hasilnya, dan dalam bit ini, pergeseran ekstensi tanda dan pergeseran yang tidak bertanda 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 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 subresolusi
yang komponen alfanya adalah 255, komponen merahnya adalah cte.red_to_blue, komponen
hijaunya adalah cte.green_to_blue, dan komponen birunya 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 inversi tersebut 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 Kurangi Transformasi Hijau
Transformasi kurangi hijau mengurangi nilai hijau dari nilai merah dan biru setiap piksel. Jika transformasi ini ada, dekoder perlu 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 berlebihan, karena dapat dimodelkan menggunakan transformasi warna, tetapi karena tidak ada data tambahan di sini, transformasi hijau kurang dapat dikodekan menggunakan lebih sedikit bit daripada transformasi warna yang lengkap.
4.4 Transformasi Pengindeksan Warna
Jika tidak banyak nilai piksel unik, akan lebih efisien untuk membuat array indeks warna dan mengganti nilai piksel dengan indeks array. Transformasi pengindeksan warna mencapai hal ini. (Dalam konteks lossless WebP, kami secara khusus tidak menyebutnya sebagai transformasi palet karena konsep serupa, tetapi lebih dinamis ada dalam encoding lossless WebP: cache warna.)
Transformasi pengindeksan warna memeriksa jumlah nilai ARGB unik dalam gambar. Jika jumlah tersebut di bawah nilai minimum (256), kode 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 ditetapkan ke 255, dan semua nilai merah dan biru ditetapkan 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 dikodekan dengan pengurangan untuk mengurangi entropi gambar. Delta warna palet biasanya berisi entropi yang jauh lebih kecil daripada warna itu sendiri, sehingga menghasilkan penghematan yang signifikan untuk gambar yang lebih kecil. Dalam decoding,
setiap warna akhir dalam tabel warna dapat diperoleh dengan menambahkan nilai komponen warna
sebelumnya berdasarkan setiap komponen ARGB secara terpisah dan menyimpan 8 bit hasil yang
paling tidak signifikan.
Transformasi terbalik untuk gambar hanyalah mengganti nilai piksel (yang merupakan indeks ke tabel warna) dengan nilai tabel warna yang sebenarnya. Pengindeksan dilakukan berdasarkan komponen hijau 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 mengemas beberapa (2, 4, atau 8) piksel menjadi satu piksel, sehingga mengurangi lebar gambar. Penggabungan piksel memungkinkan pengodean entropi distribusi bersama yang lebih efisien dari piksel yang berdekatan dan memberikan beberapa manfaat seperti pengodean 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 penggabungan
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 hijau di x diposisikan ke dalam 4 bit paling tidak signifikan dari nilai hijau di x / 2, dan nilai hijau di 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 paling tidak signifikan dari nilai hijau di x / 4, dan nilai hijau di x + 1 hingga x + 3 diposisikan secara berurutan ke bit yang lebih signifikan dari nilai hijau di x / 4.width_bits= 3: Untuk setiap nilai x, dengan x ≡ 0 (mod 8), nilai hijau di x diposisikan ke bit paling tidak signifikan dari nilai hijau di x / 8, dan nilai hijau di x + 1 hingga x + 7 diposisikan secara berurutan ke bit yang lebih signifikan dari nilai hijau di x / 8.
Setelah membaca transformasi ini, image_width akan di-subsample 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 sebenarnya dari gambar.
- Gambar entropi: Menyimpan kode awalan meta (lihat "Decoding of Meta Prefix Codes").
- Gambar prediktor: Menyimpan metadata untuk transformasi prediktor (lihat "Transformasi Prediktor").
- Gambar transformasi warna: Dibuat oleh nilai
ColorTransformElement(ditetapkan di "Transformasi Warna") untuk berbagai blok gambar. - Gambar pengindeksan warna: Array berukuran
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 serangkaian blok berukuran tetap (biasanya blok 16x16). Setiap blok ini dimodelkan menggunakan kode entropinya sendiri. Selain itu, beberapa blok dapat menggunakan 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 kode tersebut hanya disimpan satu kali. Misalnya, encoder dapat menemukan blok serupa dengan mengelompokkannya menggunakan properti statistiknya atau dengan berulang kali menggabungkan sepasang cluster yang dipilih secara acak jika hal itu mengurangi jumlah bit keseluruhan yang diperlukan untuk mengenkode gambar.
Setiap piksel dienkode menggunakan salah satu dari tiga kemungkinan metode:
- Literal yang dikodekan dengan awalan: Setiap saluran (hijau, merah, biru, dan alfa) dikodekan dengan entropi secara terpisah.
- Referensi mundur LZ77: Urutan piksel disalin dari tempat lain dalam gambar.
- Kode cache warna: Menggunakan kode hash perkalian singkat (indeks cache warna) dari warna yang baru saja dilihat.
Subbagian berikut menjelaskan setiap hal tersebut secara mendetail.
5.2.1 Literal yang Dikodekan dengan Awalan
Piksel disimpan sebagai nilai yang dikodekan dengan awalan hijau, merah, biru, dan alfa (dalam urutan tersebut). Lihat Bagian 6.2.3 untuk detailnya.
5.2.2 Referensi Mundur LZ77
Referensi mundur adalah tuple panjang dan kode jarak:
- Panjang menunjukkan jumlah piksel dalam urutan garis pemindaian yang akan disalin.
- Kode jarak adalah angka yang menunjukkan posisi piksel yang sebelumnya terlihat, yang akan disalin pikselnya. Pemetaan persisnya dijelaskan di bawah.
Nilai panjang dan jarak disimpan menggunakan pengodean awalan LZ77.
Pengodean awalan LZ77 membagi nilai bilangan bulat besar menjadi dua bagian: kode awalan dan bit ekstra. Kode awalan disimpan menggunakan kode entropi, sedangkan bit tambahan disimpan apa adanya (tanpa kode entropi).
Alasan: Pendekatan ini mengurangi persyaratan penyimpanan untuk kode entropi. Selain itu, nilai besar biasanya jarang terjadi, sehingga bit tambahan akan digunakan untuk sangat sedikit 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 berbagai rentang nilai.
| 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 disebutkan sebelumnya, kode jarak adalah angka yang menunjukkan posisi piksel yang sebelumnya terlihat, yang akan disalin pikselnya. 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, diimbangi dengan 120.
Kode jarak terkecil [1..120] bersifat khusus dan dicadangkan untuk lingkungan terdekat 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 distance_code dan offset piksel
tetangga (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 (perbedaan 0 piksel
dalam arah X dan perbedaan 1 piksel dalam arah Y).
Demikian pula, kode jarak 3 menunjukkan piksel kiri atas.
Dekoder dapat mengonversi kode jarak distance_code ke 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 lebar gambar dalam piksel.
5.2.3 Pengodean Cache Warna
Cache warna menyimpan sekumpulan warna yang baru-baru ini digunakan dalam gambar.
Alasan: Dengan cara ini, warna yang baru saja digunakan terkadang dapat dirujuk secara lebih efisien daripada memancarkannya 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, dan kode tersebut 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 cache warna (1 <<
color_cache_code_bits). Rentang nilai yang diizinkan untuk color_cache_code_bits adalah [1..11]. Dekoder yang sesuai harus menunjukkan bitstream yang rusak untuk nilai lainnya.
Cache warna adalah array berukuran 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 atau 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 ditransmisikan dengan mengirimkan panjang kode awalan, bukan kode awalan yang sebenarnya.
Secara khusus, format ini menggunakan pengodean awalan varian spasial. Dengan kata lain, blok gambar yang berbeda berpotensi menggunakan kode entropi yang berbeda.
Alasan: Area gambar yang berbeda mungkin memiliki karakteristik yang berbeda. Jadi, mengizinkan mereka 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 yang dienkode entropi.
Untuk setiap piksel (x, y), ada serangkaian 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 untuk saluran merah, biru, dan alfa, masing-masing.
- Kode awalan #5: Digunakan untuk jarak referensi mundur.
Mulai sekarang, kita menyebut kumpulan ini sebagai grup kode awalan.
6.2.1 Mendekode dan Membangun Kode Awalan
Bagian ini menjelaskan cara membaca panjang kode awalan dari bitstream.
Panjang kode awalan dapat dikodekan dengan dua cara. Metode yang digunakan ditentukan oleh nilai 1-bit.
- Jika bit ini adalah 1, maka ini adalah kode panjang kode sederhana.
- Jika bit ini adalah 0, maka kode tersebut adalah kode panjang kode normal.
Dalam kedua kasus tersebut, mungkin ada panjang kode yang tidak digunakan yang masih menjadi bagian dari streaming. Hal ini mungkin tidak efisien, tetapi diizinkan oleh format. Pohon yang dijelaskan harus berupa pohon biner penuh. Satu node daun dianggap sebagai pohon biner penuh dan dapat dienkode menggunakan kode panjang kode sederhana atau kode panjang kode normal. Saat mengodekan satu node daun menggunakan kode panjang kode normal, semua panjang kode kecuali satu adalah nol, dan nilai node daun tunggal ditandai dengan panjang 1 -- bahkan saat tidak ada bit yang digunakan saat pohon node daun tunggal tersebut digunakan.
Kode Panjang Kode Sederhana
Varian ini digunakan dalam kasus khusus saat hanya ada 1 atau 2 simbol awalan 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 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 harus berbeda. Simbol duplikat diizinkan, tetapi tidak efisien.
Catatan: Kasus khusus lainnya adalah saat panjang kode awalan semua adalah nol (kode awalan
kosong). Misalnya, kode awalan untuk jarak dapat 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 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 tingkat yang lebih 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) ditetapkan ke ukuran alfabetnya:
- Channel G: 256 + 24 +
color_cache_size - Literal lainnya (A, R, dan B): 256
- Kode jarak: 40
Jika tidak, nilai ini ditentukan 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 panjang kode max_symbol.
- Kode [0..15] menunjukkan panjang kode literal.
- Nilai 0 berarti tidak ada simbol yang telah dikodekan.
- Nilai [1..15] menunjukkan panjang bit dari masing-masing kode.
- Kode 16 mengulangi nilai bukan nol sebelumnya [3..6] kali, yaitu,
3 + ReadBits(2)kali. Jika kode 16 digunakan sebelum nilai bukan nol dipancarkan, nilai 8 akan diulang. - Kode 17 memancarkan deretan nol dengan panjang [3..10], yaitu
3 + ReadBits(3)kali. - Kode 18 memancarkan deretan nol dengan panjang [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 mengodekan hierarki keputusan lengkap, yaitu, jumlah
2 ^ (-length) untuk semua kode bukan nol harus tepat satu. Namun, ada satu pengecualian untuk aturan ini, yaitu 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 yang disebutkan sebelumnya, format ini memungkinkan penggunaan kode awalan yang berbeda untuk blok gambar yang berbeda. Kode awalan meta adalah indeks yang mengidentifikasi kode awalan mana 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 saja dalam gambar. Tidak ada lagi data yang disimpan.
- Jika bit ini adalah satu, gambar menggunakan beberapa kode awalan meta. Kode awalan meta ini 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
diperoleh 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 ditentukan sebelumnya.
Bit berikutnya berisi gambar entropi dengan lebar prefix_image_width dan tinggi
prefix_image_height.
Interpretasi Kode Awalan Meta
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;
Mengingat piksel (x, y) dalam gambar ARGB, kita dapat memperoleh kode awalan yang sesuai untuk 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 keberadaan struktur PrefixCodeGroup, yang
mewakili serangkaian lima kode awalan. Selain itu, prefix_code_groups adalah array
PrefixCodeGroup (berukuran num_prefix_groups).
Kemudian, dekoder menggunakan grup kode awalan prefix_group untuk mendekode piksel
(x, y), seperti yang dijelaskan dalam "Decoding Entropy-Coded Image
Data".
6.2.3 Mendekode Data Gambar yang Dikodekan dengan Entropi
Untuk posisi saat ini (x, y) dalam gambar, dekoder terlebih dahulu mengidentifikasi grup kode awalan yang sesuai (seperti yang dijelaskan di bagian terakhir). Dengan grup kode awalan, piksel dibaca dan didekode sebagai berikut.
Selanjutnya, baca simbol S dari bitstream menggunakan kode awalan #1. Perhatikan bahwa S adalah
bilangan bulat apa pun dalam rentang 0 hingga
(256 + 24 + color_cache_size- 1).
Interpretasi 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 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.
- Menyalin piksel L (dalam urutan garis pemindaian) dari urutan piksel yang dimulai pada posisi saat ini dikurangi 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 Keseluruhan Format
Di bawah ini adalah tampilan format dalam Augmented Backus-Naur Form (ABNF) RFC 5234 RFC 7405. 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 adalah kemungkinan urutan contoh:
RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image