Jyrki Alakuijala, Ph.D., Google Inc., 2023-03-09
Abstract
WebP lossless adalah format gambar untuk kompresi gambar ARGB lossless. Format lossless menyimpan dan memulihkan nilai piksel dengan tepat, termasuk nilai warna untuk piksel yang sepenuhnya transparan. Algoritma universal untuk kompresi data berurutan (LZ77), coding awalan, dan cache warna digunakan untuk kompresi data massal. Kecepatan decoding lebih cepat daripada PNG telah ditunjukkan, serta kompresi 25% lebih padat daripada yang dapat dicapai menggunakan format PNG saat ini.
1 Pengantar
Dokumen ini menjelaskan representasi data terkompresi untuk gambar WebP lossless. Format ini dimaksudkan sebagai referensi mendetail untuk penerapan encoder dan dekoder lossless WebP.
Dalam dokumen ini, kami menggunakan sintaksis bahasa pemrograman C secara ekstensif untuk mendeskripsikan bitstream dan mengasumsikan adanya fungsi untuk membaca bit, ReadBits(n). Byte dibaca dalam urutan natural stream 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. Dengan demikian, 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, direpresentasikan 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 menggunakan representasi lain secara internal.
Umumnya, 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 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 saja 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 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
- Algoritma 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 mengodifikasi bit yang tersisa secara mentah. Hal ini memungkinkan deskripsi kode entropi tetap relatif kecil meskipun rentang simbolnya besar.
- urutan pindai garis
- Urutan pemrosesan piksel (kiri ke kanan dan atas ke bawah), mulai dari piksel kiri atas. Setelah satu baris selesai, lanjutkan dari kolom sebelah kiri di baris berikutnya.
3 Header RIFF
Bagian awal {i>header<i} berisi kontainer RIFF. Format 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 yang dienkode lossless).
- Nilai 32-bit small-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 16384✕16384 piksel.
Bit alpha_is_used hanya sebagai petunjuk, dan tidak memengaruhi decoding. Nilai ini harus disetel 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 diatur ke 0. Nilai lainnya harus diperlakukan sebagai error.
int version_number = ReadBits(3);
4 Transformasi
Transformasi adalah manipulasi data gambar yang dapat dibalik dan dapat mengurangi entropi simbolis yang tersisa dengan membuat model korelasi spasial dan warna. Filter dapat membuat kompresi akhir lebih padat.
Gambar dapat melalui empat jenis transformasi. 1 bit menunjukkan adanya transformasi. Setiap transformasi hanya boleh digunakan satu kali. Transformasi hanya digunakan untuk gambar ARGB level utama; gambar subresolusi (gambar transformasi warna, gambar entropi, dan gambar prediktor) tidak memiliki transformasi, bahkan 0 bit yang menunjukkan akhir transformasi juga tidak ada.
Biasanya, encoder akan menggunakan transformasi ini untuk mengurangi entropi Shannon pada gambar residu. Selain itu, data transformasi dapat ditentukan berdasarkan minimalisasi 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, maka 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 oleh data transformasi. Data transformasi berisi informasi yang diperlukan untuk menerapkan transformasi terbalik dan bergantung pada jenis transformasi. Transformasi terbalik diterapkan dalam urutan terbalik agar dibaca dari bitstream, yaitu, yang terakhir terlebih dahulu.
Selanjutnya, kami menjelaskan data transformasi untuk berbagai jenis.
4.1 Transformasi Predictor
Transformasi prediktor dapat digunakan untuk mengurangi entropi dengan memanfaatkan fakta bahwa piksel di dekatnya sering kali berkorelasi. Dalam transformasi prediktor, nilai piksel saat ini diprediksi dari piksel yang telah didekode (dalam urutan baris pemindaian) dan hanya nilai residu (aktual yang diprediksi) yang dienkode. Komponen hijau dari sebuah 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.
int size_bits = ReadBits(3) + 2;
int block_width = (1 << size_bits);
int block_height = (1 << size_bits);
#define DIV_ROUND_UP(num, den) (((num) + (den) - 1) / (den))
int transform_width = DIV_ROUND_UP(image_width, 1 << size_bits);
Data transformasi berisi mode prediksi untuk setiap blok gambar. Ini adalah gambar subresolusi dengan komponen piksel berwarna hijau menentukan mana dari ke-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), masing-masing dapat menghitung alamat blok filter
dengan:
int block_index = (y >> size_bits) * transform_width +
(x >> size_bits);
Ada 14 mode prediksi yang berbeda. Pada setiap mode prediksi, nilai piksel saat ini diprediksi dari satu atau beberapa piksel di dekatnya yang nilainya sudah diketahui.
Kami memilih piksel tetangga (TL, T, TR, dan L) 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 untuk P, semua piksel O, TL, T, TR, dan L sudah diproses, dan piksel P serta semua piksel X tidak diketahui.
Dengan piksel tetangga sebelumnya, mode prediksi yang berbeda ditentukan sebagai berikut.
| Mode | Nilai yang diprediksi dari setiap saluran piksel saat ini |
|---|---|
| 0 | 0xff000000 (mewakili warna hitam solid dalam ARGB) |
| 1 | L |
| 2 | T |
| 3 | TR |
| 4 | TL |
| 5 | Rata-Rata2(Average2(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(K, T, TL) |
| 12 | ClampAddSubtractFull(L, T, TL) |
| 13 | ClampAddSubtractHalf(Average2(L, T), TL) |
Average2 didefinisikan sebagai berikut untuk setiap komponen ARGB:
uint8 Average2(uint8 a, uint8 b) {
return (a + b) / 2;
}
Prediktor Select didefinisikan sebagai berikut:
uint32 Select(uint32 L, uint32 T, uint32 TL) {
// L = left pixel, T = top pixel, TL = top-left pixel.
// ARGB component estimates for prediction.
int pAlpha = ALPHA(L) + ALPHA(T) - ALPHA(TL);
int pRed = RED(L) + RED(T) - RED(TL);
int pGreen = GREEN(L) + GREEN(T) - GREEN(TL);
int pBlue = BLUE(L) + BLUE(T) - BLUE(TL);
// Manhattan distances to estimates for left and top pixels.
int pL = abs(pAlpha - ALPHA(L)) + abs(pRed - RED(L)) +
abs(pGreen - GREEN(L)) + abs(pBlue - BLUE(L));
int pT = abs(pAlpha - ALPHA(T)) + abs(pRed - RED(T)) +
abs(pGreen - GREEN(T)) + abs(pBlue - BLUE(T));
// Return either left or top, the one closer to the prediction.
if (pL < pT) {
return L;
} else {
return T;
}
}
Fungsi ClampAddSubtractFull dan ClampAddSubtractHalf dijalankan
untuk setiap komponen ARGB sebagai berikut:
// Clamp the input value between 0 and 255.
int Clamp(int a) {
return (a < 0) ? 0 : (a > 255) ? 255 : a;
}
int ClampAddSubtractFull(int a, int b, int c) {
return Clamp(a + b - c);
}
int ClampAddSubtractHalf(int a, int b) {
return Clamp(a + (a - b) / 2);
}
Ada aturan penanganan khusus untuk beberapa piksel batas. Jika ada transformasi prediksi, terlepas dari mode [0..13] untuk piksel tersebut, 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 T-piksel.
Mengatasi piksel TR untuk piksel di kolom paling kanan sangat luar biasa. Piksel di kolom paling kanan diprediksi menggunakan mode [0..13], sama seperti piksel yang tidak berada di batas, tetapi piksel paling kiri di baris yang sama dengan piksel saat ini digunakan sebagai piksel TR.
Nilai piksel akhir diperoleh dengan menambahkan setiap saluran nilai yang diprediksi ke nilai residu yang dienkode.
void PredictorTransformOutput(uint32 residual, uint32 pred,
uint8* alpha, uint8* red,
uint8* green, uint8* blue) {
*alpha = ALPHA(residual) + ALPHA(pred);
*red = RED(residual) + RED(pred);
*green = GREEN(residual) + GREEN(pred);
*blue = BLUE(residual) + BLUE(pred);
}
4.2 Transformasi Warna
Tujuan transformasi warna adalah untuk mendekorasi nilai R, G, dan B dari setiap piksel. Transformasi warna mempertahankan nilai hijau (G) apa adanya, mengubah nilai merah (R) berdasarkan nilai hijau, dan mengubah nilai biru (B) berdasarkan nilai hijau lalu nilai merah.
Seperti halnya transformasi prediktor, pertama-tama gambar dibagi menjadi blok, dan mode transformasi yang sama digunakan untuk semua piksel dalam blok. Untuk setiap blok, ada tiga jenis elemen transformasi warna.
typedef struct {
uint8 green_to_red;
uint8 green_to_blue;
uint8 red_to_blue;
} ColorTransformElement;
Transformasi warna 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. Kemudian, transformasi warna terbalik hanya menambahkan delta tersebut.
Fungsi transformasi warna didefinisikan sebagai berikut:
void ColorTransform(uint8 red, uint8 blue, uint8 green,
ColorTransformElement *trans,
uint8 *new_red, uint8 *new_blue) {
// Transformed values of red and blue components
int tmp_red = red;
int tmp_blue = blue;
// Applying the transform is just subtracting the transform deltas
tmp_red -= ColorTransformDelta(trans->green_to_red, green);
tmp_blue -= ColorTransformDelta(trans->green_to_blue, green);
tmp_blue -= ColorTransformDelta(trans->red_to_blue, red);
*new_red = tmp_red & 0xff;
*new_blue = tmp_blue & 0xff;
}
ColorTransformDelta dihitung menggunakan bilangan bulat 8-bit bertanda tangan yang mewakili
angka 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 8 bit tanpa tanda tangan (uint8) ke representasi 8 bit bertanda (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 dikonversinya).
Perkalian harus dilakukan secara lebih presisi (dengan setidaknya presisi 16-bit). Properti ekstensi tanda dari operasi shift tidak menjadi masalah di sini; hanya 8 bit terendah yang digunakan dari hasil, dan di sana pergeseran ekstensi tanda dan pergeseran yang tidak ditandatangani akan konsisten satu sama lain.
Sekarang, kami menjelaskan konten data transformasi warna sehingga decoding dapat menerapkan transformasi warna terbalik dan memulihkan nilai merah dan biru yang asli. 3 bit pertama dari 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 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
dibiarkan apa adanya.
void InverseTransform(uint8 red, uint8 green, uint8 blue,
ColorTransformElement *trans,
uint8 *new_red, uint8 *new_blue) {
// Transformed values of red and blue components
int tmp_red = red;
int tmp_blue = blue;
// Applying the inverse transform is just adding the
// color transform deltas
tmp_red += ColorTransformDelta(trans->green_to_red, green);
tmp_blue += ColorTransformDelta(trans->green_to_blue, green);
tmp_blue +=
ColorTransformDelta(trans->red_to_blue, tmp_red & 0xff);
*new_red = tmp_red & 0xff;
*new_blue = tmp_blue & 0xff;
}
4.3 Mengurangi Transformasi Hijau
Pengurangan transformasi hijau akan mengurangi nilai hijau dari nilai merah dan biru 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 penuh.
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 ini. (Dalam konteks WebP lossless, kami secara khusus tidak menyebutnya 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 angka tersebut berada di bawah ambang batas (256), array dari nilai ARGB tersebut akan dibuat, yang kemudian digunakan untuk mengganti nilai piksel dengan indeks yang sesuai: saluran hijau dari piksel diganti dengan indeks, semua nilai alfa ditetapkan 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 mengandung entropi yang jauh lebih sedikit daripada warna
itu sendiri, sehingga memungkinkan penghematan yang 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 8 bit
hasil yang paling tidak signifikan.
Transformasi terbalik untuk gambar hanya mengganti nilai piksel (yang merupakan indeks untuk tabel warna) dengan nilai tabel warna yang sebenarnya. Pengindeksan dilakukan berdasarkan komponen hijau dari warna ARGB.
// Inverse transform
argb = color_table[GREEN(argb)];
Jika indeks sama dengan atau lebih besar dari color_table_size, nilai warna aRGB
harus disetel ke 0x00000000 (hitam transparan).
Jika tabel warna kecil (sama dengan atau kurang dari 16 warna), beberapa piksel dibundel menjadi satu piksel. Paket piksel ini menggabungkan beberapa (2, 4, atau 8) piksel menjadi satu piksel, yang masing-masing mengurangi lebar gambar. Pemaketan piksel memungkinkan coding entropi distribusi bersama yang lebih efisien untuk piksel yang berdekatan 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 pada x diposisikan ke dalam 4 bit paling tidak signifikan dari nilai hijau pada x / 2, dan nilai hijau pada x + 1 diposisikan ke dalam 4 bit paling signifikan dari nilai hijau pada x / 2.width_bits= 2: Untuk setiap nilai x, dengan x ≡ 0 (mod 4), nilai hijau pada x diposisikan ke dalam 2 bit yang paling tidak signifikan dari nilai hijau pada x / 4, dan nilai hijau pada x + 1 hingga x + 3 diposisikan sesuai urutan bit yang lebih signifikan dari nilai hijau pada x / 4.width_bits= 3: Untuk setiap nilai x, dengan x ≡ 0 (mod 8), nilai hijau pada x diposisikan ke dalam bit nilai hijau yang paling tidak signifikan pada x / 8, dan nilai hijau pada x + 1 hingga x + 7 diposisikan sesuai untuk bit yang lebih signifikan dari nilai hijau pada x / 8.
Setelah membaca transformasi ini, image_width disubsampelkan 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 Citra
Kita 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").
- Image prediktif: Menyimpan metadata untuk transformasi prediktor (lihat "Predictor Transform").
- Gambar transformasi warna: Dibuat oleh nilai
ColorTransformElement(ditentukan dalam "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.
Pertama-tama, gambar dibagi menjadi sekumpulan blok berukuran tetap (biasanya blok 16x16). Setiap blok ini dimodelkan menggunakan kode entropinya sendiri. Selain itu, beberapa blok dapat memiliki kode entropi yang sama.
Rasiona: Menyimpan kode entropi akan dikenai biaya. Biaya ini dapat diminimalkan jika blok yang serupa secara statistik berbagi kode entropi, sehingga menyimpan kode tersebut hanya sekali. Misalnya, encoder dapat menemukan blok serupa dengan mengelompokkannya menggunakan 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 dilakukan:
- Literal berkode awalan: 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-baru ini dilihat.
Subbagian berikut menjelaskan setiap hal ini secara mendetail.
5.2.1 Literal Berkode Awal
Piksel disimpan sebagai nilai berkode awalan warna 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 tupel dengan panjang dan kode jarak:
- Panjang menunjukkan jumlah piksel dalam urutan garis 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 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).
Rasiona: Pendekatan ini mengurangi persyaratan penyimpanan untuk kode entropi. Selain itu, nilai besar biasanya jarang terjadi, jadi bit tambahan akan digunakan untuk beberapa nilai yang sangat sedikit 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 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 dengan piksel saat ini. Lingkungan ini terdiri dari 120 piksel:
- Piksel yang 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 berada hingga 8
kolom di sebelah kiri piksel saat ini. [
8piksel tersebut].
Pemetaan antara kode jarak distance_code dan pixel
offset yang berdekatan (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 dalam arah Y).
Demikian pula, kode jarak 3 menunjukkan piksel kiri atas.
Decoder dapat mengonversi kode jarak distance_code menjadi jarak urutan garis pemindaian dist sebagai berikut:
(xi, yi) = distance_map[distance_code - 1]
dist = xi + yi * image_width
if (dist < 1) {
dist = 1
}
dengan distance_map adalah pemetaan yang disebutkan di atas, dan image_width adalah lebar
gambar dalam piksel.
5.2.3 Pengkodean Cache Warna
Cache warna menyimpan kumpulan warna yang baru saja digunakan dalam gambar.
Rasional: Dengan cara ini, warna yang baru-baru ini digunakan terkadang dapat dirujuk secara lebih efisien daripada menampilkannya 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 yang ada, dan kode tersebut tidak ditransmisikan dalam kode awalan yang mendekode simbol berwarna 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 sesuai harus menunjukkan
bitstream yang rusak untuk nilai lain.
Cache warna adalah array berukuran color_cache_size. Setiap entri menyimpan
satu warna ARGB. Warna dicari dengan mengindeksnya menurut (0x1e35a7bd * color) >> (32 -
color_cache_code_bits). Hanya satu pencarian yang dilakukan dalam cache warna; tidak ada
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 dekode. Status cache warna dipertahankan dengan memasukkan setiap piksel, baik yang dihasilkan dengan mereferensikan 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 ini menggunakan coding awalan varian secara spasial. Dengan kata lain, blok gambar yang berbeda berpotensi menggunakan kode entropi yang berbeda.
Rasiona: Area gambar yang berbeda mungkin memiliki karakteristik yang berbeda. Jadi, mengizinkan filter untuk menggunakan kode entropi berbeda akan memberikan fleksibilitas yang lebih besar dan kompresi yang berpotensi lebih baik.
6.2 Detail
Data gambar yang dienkode terdiri dari beberapa bagian:
- Mendekode dan membuat kode awalan.
- Kode awalan meta.
- Data gambar berkode entropi.
Untuk setiap piksel tertentu (x, y), ada kumpulan lima kode awalan yang terkait dengannya. Kode ini (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 ini 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, itu adalah kode panjang kode sederhana.
- Jika bit ini adalah 0, itu adalah kode panjang kode normal.
Pada kedua kasus tersebut, mungkin saja 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 daun 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 daun 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 daun tunggal tersebut digunakan.
Kode Panjang Kode Sederhana
Varian ini digunakan dalam kasus khusus ketika hanya 1 atau 2 simbol awalan 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, bergantung 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;
}
Kedua simbol tersebut harus berbeda. Simbol duplikat diizinkan, tetapi tidak efisien.
Catatan: Kasus khusus lainnya adalah ketika 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 sendiri dienkode menggunakan kode awalan; panjang kode pada level yang lebih rendah, code_length_code_lengths, harus dibaca terlebih dahulu. Sisa code_length_code_lengths tersebut (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);
}
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 alfabet:
- Saluran G: 256 + 24 +
color_cache_size - Literal lain (A, R, dan B): 256
- Kode jarak: 40
Jika tidak, ini 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 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 dimunculkan, nilai 8 akan diulangi. - Kode 17 memancarkan rentetan angka nol dengan panjang [3..10], yaitu
3 + ReadBits(3)kali. - Kode 18 memancarkan rentetan angka 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) akan dibentuk menggunakan ukuran alfabetnya 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, yaitu pohon node daun tunggal, tempat nilai node
leaf ditandai dengan nilai 1 dan nilai lainnya adalah 0s.
6.2.2 Decoding Kode Awalan Meta
Seperti disebutkan sebelumnya, format ini memungkinkan penggunaan kode awalan yang berbeda untuk blok gambar yang berbeda. Kode awalan meta adalah indeks yang mengidentifikasi kode awalan yang akan digunakan di berbagai bagian gambar.
Kode awalan meta hanya dapat digunakan ketika 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 image. Tidak ada lagi data yang disimpan.
- Jika bit ini adalah satu, gambar menggunakan beberapa kode awalan meta. Kode awalan meta ini disimpan sebagai image 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 yang digunakan di berbagai bagian gambar.
3 bit pertama berisi nilai prefix_bits. Dimensi gambar entropi berasal dari prefix_bits:
int prefix_bits = ReadBits(3) + 2;
int prefix_image_width =
DIV_ROUND_UP(image_width, 1 << prefix_bits);
int prefix_image_height =
DIV_ROUND_UP(image_height, 1 << prefix_bits);
dengan DIV_ROUND_UP seperti yang didefinisikan sebelumnya.
Bit berikutnya berisi gambar entropi dengan lebar prefix_image_width dan tinggi
prefix_image_height.
Penafsiran Kode Awalan Meta
Jumlah grup kode awalan dalam gambar ARGB dapat diperoleh dengan menemukan kode awalan meta terbesar dari image 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 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];
tempat kita mengasumsikan keberadaan 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 dalam "Mendekode Data Gambar Entropi".
6.2.3 Decoding Data Gambar Entropi Kode
Untuk posisi saat ini (x, y) dalam gambar, decoder terlebih dahulu mengidentifikasi grup kode awalan yang sesuai (seperti yang dijelaskan di bagian terakhir). Dengan grup kode awalan, piksel dibaca dan didekode sebagai berikut.
Berikutnya, 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 tergantung pada nilainya:
- Jika S < 256
- Gunakan S sebagai komponen berwarna 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 panjang kode awalan.
- Membaca bit tambahan untuk panjang dari bitstream.
- Tentukan panjang referensi mundur L dari kode awalan panjang dan bit tambahan yang dibaca.
- Membaca kode awalan jarak dari bitstream menggunakan kode awalan #5.
- Membaca bit tambahan untuk jarak dari bitstream.
- Menentukan jarak referensi mundur D dari kode awalan jarak dan bit tambahan yang dibaca.
- Salin L piksel (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 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 (image_width * image_height).
Perlu diketahui bahwa *element berarti element dapat diulang 0 atau beberapa kali. 5element
berarti element diulang tepat 5 kali. %b mewakili nilai biner.
7.1 Struktur Dasar
format = RIFF-header image-header image-stream
RIFF-header = %s"RIFF" 4OCTET %s"WEBPVP8L" 4OCTET
image-header = %x2F image-size alpha-is-used version
image-size = 14BIT 14BIT ; width - 1, height - 1
alpha-is-used = 1BIT
version = 3BIT ; 0
image-stream = optional-transform spatially-coded-image
7.2 Struktur Transformasi
optional-transform = (%b1 transform optional-transform) / %b0
transform = predictor-tx / color-tx / subtract-green-tx
transform =/ color-indexing-tx
predictor-tx = %b00 predictor-image
predictor-image = 3BIT ; sub-pixel code
entropy-coded-image
color-tx = %b01 color-image
color-image = 3BIT ; sub-pixel code
entropy-coded-image
subtract-green-tx = %b10
color-indexing-tx = %b11 color-indexing-image
color-indexing-image = 8BIT ; color count
entropy-coded-image
7.3 Struktur Data Gambar
spatially-coded-image = color-cache-info meta-prefix data
entropy-coded-image = color-cache-info data
color-cache-info = %b0
color-cache-info =/ (%b1 4BIT) ; 1 followed by color cache size
meta-prefix = %b0 / (%b1 entropy-image)
data = prefix-codes lz77-coded-image
entropy-image = 3BIT ; subsample value
entropy-coded-image
prefix-codes = prefix-code-group *prefix-codes
prefix-code-group =
5prefix-code ; See "Interpretation of Meta Prefix Codes" to
; understand what each of these five prefix
; codes are for.
prefix-code = simple-prefix-code / normal-prefix-code
simple-prefix-code = ; see "Simple Code Length Code" for details
normal-prefix-code = ; see "Normal Code Length Code" for details
lz77-coded-image =
*((argb-pixel / lz77-copy / color-cache-code) lz77-coded-image)
Berikut ini adalah contoh urutan yang mungkin:
RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image