Jyrki Alakuijala, Tiến sĩ, Google, Inc., 09/03/2023
Bản tóm tắt
WebP không tổn hao là một định dạng hình ảnh để nén không tổn hao hình ảnh ARGB. Định dạng không mất dữ liệu lưu trữ và khôi phục chính xác các giá trị pixel, bao gồm cả giá trị màu cho các pixel trong suốt hoàn toàn. Một thuật toán phổ biến để nén dữ liệu tuần tự (LZ77), mã hoá tiền tố và bộ nhớ đệm màu được dùng để nén dữ liệu hàng loạt. Tốc độ giải mã nhanh hơn PNG đã được chứng minh, cũng như khả năng nén dày đặc hơn 25% so với khả năng đạt được bằng định dạng PNG hiện nay.
1 Giới thiệu
Tài liệu này mô tả cách biểu thị dữ liệu nén của một hình ảnh WebP không tổn hao. Đây là tài liệu tham khảo chi tiết về việc triển khai bộ mã hoá và giải mã không mất dữ liệu WebP.
Trong tài liệu này, chúng tôi sử dụng rộng rãi cú pháp ngôn ngữ lập trình C để mô tả luồng bit và giả định sự tồn tại của một hàm để đọc các bit, ReadBits(n). Các byte được đọc theo thứ tự tự nhiên của luồng chứa các byte đó và các bit của mỗi byte được đọc theo thứ tự bit có giá trị nhỏ nhất trước. Khi nhiều bit được đọc cùng một lúc, số nguyên sẽ được tạo từ dữ liệu ban đầu theo thứ tự ban đầu. Các bit quan trọng nhất của số nguyên được trả về cũng là các bit quan trọng nhất của dữ liệu ban đầu. Do đó, câu lệnh
b = ReadBits(2);
tương đương với hai tuyên bố dưới đây:
b = ReadBits(1);
b |= ReadBits(1) << 1;
Chúng tôi giả định rằng mỗi thành phần màu (tức là alpha, đỏ, xanh dương và xanh lục) được biểu thị bằng một byte 8 bit. Chúng ta xác định loại tương ứng là uint8. Một pixel ARGB hoàn chỉnh được biểu thị bằng một loại có tên là uint32, là một số nguyên không dấu gồm 32 bit. Trong mã cho thấy hành vi của các phép biến đổi, các giá trị này được mã hoá trong các bit sau: alpha trong các bit 31..24, màu đỏ trong các bit 23..16, màu xanh lục trong các bit 15..8 và màu xanh dương trong các bit 7..0; tuy nhiên, các cách triển khai định dạng có thể tự do sử dụng một cách biểu diễn khác ở bên trong.
Nhìn chung, hình ảnh WebP không suy hao chứa dữ liệu tiêu đề, thông tin biến đổi và dữ liệu hình ảnh thực tế. Tiêu đề chứa chiều rộng và chiều cao của hình ảnh. Một hình ảnh không suy hao WebP có thể trải qua 4 loại biến đổi trước khi được mã hoá entropy. Thông tin biến đổi trong luồng bit chứa dữ liệu cần thiết để áp dụng các phép biến đổi nghịch đảo tương ứng.
2 Danh pháp
- ARGB
- Giá trị pixel bao gồm các giá trị alpha, đỏ, xanh lục và xanh dương.
- Hình ảnh ARGB
- Một mảng hai chiều chứa các pixel ARGB.
- bộ nhớ đệm màu
- Một mảng nhỏ có địa chỉ băm để lưu trữ các màu được dùng gần đây nhằm có thể gọi lại chúng bằng mã ngắn hơn.
- hình ảnh lập chỉ mục màu
- Hình ảnh một chiều về màu sắc có thể được lập chỉ mục bằng một số nguyên nhỏ (tối đa 256 trong WebP không mất dữ liệu).
- hình ảnh biến đổi màu
- Hình ảnh có độ phân giải phụ hai chiều chứa dữ liệu về mối tương quan của các thành phần màu.
- ánh xạ khoảng cách
- Thay đổi khoảng cách LZ77 để có giá trị nhỏ nhất cho các pixel trong khoảng cách hai chiều.
- hình ảnh entropy
- Hình ảnh có độ phân giải phụ hai chiều cho biết nên sử dụng phương pháp mã hoá entropy nào trong một hình vuông tương ứng trong hình ảnh, tức là mỗi pixel là một mã tiền tố meta.
- LZ77
- Một thuật toán nén cửa sổ trượt dựa trên từ điển, phát ra các ký hiệu hoặc mô tả các ký hiệu đó dưới dạng chuỗi ký hiệu trước đây.
- mã tiền tố meta
- Một số nguyên nhỏ (tối đa 16 bit) lập chỉ mục một phần tử trong bảng tiền tố meta.
- hình ảnh dự đoán
- Hình ảnh có độ phân giải phụ hai chiều cho biết bộ dự đoán không gian nào được dùng cho một ô vuông cụ thể trong hình ảnh.
- mã tiền tố
- Một cách kinh điển để thực hiện mã hoá entropy, trong đó một số lượng nhỏ bit được dùng cho các mã thường xuyên hơn.
- mã hoá tiền tố
- Một cách để mã hoá entropy cho các số nguyên lớn hơn, mã hoá một vài bit của số nguyên bằng cách sử dụng mã entropy và mã hoá các bit còn lại ở dạng thô. Điều này cho phép nội dung mô tả về mã entropy vẫn tương đối nhỏ ngay cả khi phạm vi của các biểu tượng lớn.
- thứ tự quét dòng
- Thứ tự xử lý các pixel (từ trái sang phải và từ trên xuống dưới), bắt đầu từ pixel trên cùng bên trái. Sau khi hoàn tất một hàng, hãy tiếp tục từ cột bên trái của hàng tiếp theo.
3 RIFF Header
Phần đầu của tiêu đề có vùng chứa RIFF. Mã này bao gồm 21 byte sau:
- Chuỗi "RIFF".
- Giá trị 32 bit, little-endian của độ dài đoạn, là toàn bộ kích thước của đoạn do tiêu đề RIFF kiểm soát. Thông thường, kích thước này bằng kích thước tải trọng (kích thước tệp trừ đi 8 byte: 4 byte cho giá trị nhận dạng "RIFF" và 4 byte để lưu trữ chính giá trị đó).
- Chuỗi "WEBP" (tên vùng chứa RIFF).
- Chuỗi "VP8L" (FourCC cho dữ liệu hình ảnh được mã hoá không mất dữ liệu).
- Giá trị 32 bit, little-endian của số byte trong luồng không mất dữ liệu.
- Chữ ký 1 byte 0x2f.
28 bit đầu tiên của luồng bit chỉ định chiều rộng và chiều cao của hình ảnh. Chiều rộng và chiều cao được giải mã dưới dạng số nguyên 14 bit như sau:
int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;
Độ chính xác 14 bit cho chiều rộng và chiều cao của hình ảnh giới hạn kích thước tối đa của hình ảnh WebP không tổn hao ở mức 16384✕16384 pixel.
Bit alpha_is_used chỉ là một gợi ý và không ảnh hưởng đến quá trình giải mã. Bạn nên đặt giá trị này thành 0 khi tất cả giá trị alpha đều là 255 trong hình ảnh và 1 trong trường hợp khác.
int alpha_is_used = ReadBits(1);
version_number là mã 3 bit và bạn phải đặt thành 0. Mọi giá trị khác đều được coi là lỗi.
int version_number = ReadBits(3);
4 phép biến đổi
Các phép biến đổi là những thao tác có thể đảo ngược đối với dữ liệu hình ảnh, có thể giảm entropy tượng trưng còn lại bằng cách mô hình hoá các mối tương quan về không gian và màu sắc. Chúng có thể nén cuối cùng dày đặc hơn.
Một hình ảnh có thể trải qua 4 loại biến đổi. 1 bit cho biết sự hiện diện của một phép biến đổi. Mỗi biến đổi chỉ được phép sử dụng một lần. Các phép biến đổi chỉ được dùng cho hình ảnh ARGB ở cấp chính; các hình ảnh có độ phân giải phụ (hình ảnh biến đổi màu, hình ảnh entropy và hình ảnh dự đoán) không có phép biến đổi, ngay cả 0 bit cho biết kết thúc phép biến đổi.
Thông thường, bộ mã hoá sẽ sử dụng các phép biến đổi này để giảm entropy Shannon trong hình ảnh dư. Ngoài ra, bạn có thể quyết định biến đổi dữ liệu dựa trên việc giảm thiểu entropy.
while (ReadBits(1)) { // Transform present.
// Decode transform type.
enum TransformType transform_type = ReadBits(2);
// Decode transform data.
...
}
// Decode actual image data (Section 5).
Nếu có một phép biến đổi, thì 2 bit tiếp theo sẽ chỉ định loại phép biến đổi. Có 4 loại biến đổi.
enum TransformType {
PREDICTOR_TRANSFORM = 0,
COLOR_TRANSFORM = 1,
SUBTRACT_GREEN_TRANSFORM = 2,
COLOR_INDEXING_TRANSFORM = 3,
};
Loại biến đổi theo sau là dữ liệu biến đổi. Dữ liệu biến đổi chứa thông tin cần thiết để áp dụng phép biến đổi nghịch đảo và phụ thuộc vào loại biến đổi. Các phép biến đổi nghịch đảo được áp dụng theo thứ tự ngược lại với thứ tự mà chúng được đọc từ luồng bit, tức là phép biến đổi cuối cùng sẽ được áp dụng trước.
Tiếp theo, chúng ta sẽ mô tả dữ liệu biến đổi cho các loại khác nhau.
4.1 Biến đổi của đối tượng dự đoán
Biến đổi dự đoán có thể được dùng để giảm entropy bằng cách khai thác thực tế là các pixel lân cận thường có mối tương quan. Trong biến đổi dự đoán, giá trị pixel hiện tại được dự đoán từ các pixel đã được giải mã (theo thứ tự dòng quét) và chỉ giá trị dư (thực tế – dự đoán) được mã hoá. Thành phần màu xanh lục của một pixel xác định trong số 14 giá trị dự đoán được dùng trong một khối cụ thể của hình ảnh ARGB. Chế độ dự đoán xác định loại dự đoán sẽ sử dụng. Chúng ta chia hình ảnh thành các ô vuông và tất cả các pixel trong một ô vuông đều sử dụng cùng một chế độ dự đoán.
3 bit đầu tiên của dữ liệu dự đoán xác định chiều rộng và chiều cao của khối theo số lượng 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);
Dữ liệu biến đổi chứa chế độ dự đoán cho từng khối của hình ảnh. Đây là hình ảnh có độ phân giải phụ, trong đó thành phần màu xanh lục của một pixel xác định trong số 14 giá trị dự đoán được dùng cho tất cả các pixel block_width * block_height trong một khối cụ thể của hình ảnh ARGB. Hình ảnh có độ phân giải phụ này được mã hoá bằng các kỹ thuật tương tự như mô tả trong Chương 5.
Số lượng cột khối, transform_width, được dùng trong lập chỉ mục hai chiều. Đối với một pixel (x, y), người ta có thể tính toán địa chỉ khối bộ lọc tương ứng bằng cách:
int block_index = (y >> size_bits) * transform_width +
(x >> size_bits);
Có 14 chế độ dự đoán. Trong mỗi chế độ dự đoán, giá trị pixel hiện tại được dự đoán từ một hoặc nhiều pixel lân cận có giá trị đã biết.
Chúng tôi chọn các pixel lân cận (TL, T, TR và L) của pixel hiện tại (P) như sau:
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
trong đó TL là trên cùng bên trái, T là trên cùng, TR là trên cùng bên phải và L là bên trái. Tại thời điểm dự đoán giá trị cho P, tất cả các pixel O, TL, T, TR và L đã được xử lý, còn pixel P và tất cả các pixel X đều chưa xác định.
Với các pixel lân cận trước đó, các chế độ dự đoán khác nhau được xác định như sau.
| Chế độ | Giá trị dự đoán của từng kênh trong pixel hiện tại |
|---|---|
| 0 | 0xff000000 (biểu thị màu đen tuyền trong ARGB) |
| 1 | L |
| 2 | T |
| 3 | lira Thổ Nhĩ Kỳ (TR) |
| 4 | trưởng nhóm |
| 5 | Trung bình2(Trung bình2(L, TR), T) |
| 6 | Trung bình2(L, TL) |
| 7 | Average2(L; T) |
| 8 | Average2(TL; T) |
| 9 | Average2(T; TR) |
| 10 | Average2(Average2(L; TL); Average2(T; TR)) |
| 11 | Chọn(L, T, TL) |
| 12 | ClampAddSubtractFull(L, T, TL) |
| 13 | ClampAddSubtractHalf(Average2(L, T), TL) |
Average2 được xác định như sau cho từng thành phần ARGB:
uint8 Average2(uint8 a, uint8 b) {
return (a + b) / 2;
}
Bộ chọn dự đoán được xác định như sau:
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;
}
}
Các hàm ClampAddSubtractFull và ClampAddSubtractHalf được thực hiện cho từng thành phần ARGB như sau:
// 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);
}
Có các quy tắc xử lý đặc biệt đối với một số pixel viền. Nếu có một biến đổi dự đoán, bất kể chế độ [0..13] cho các pixel này, giá trị dự đoán cho pixel trên cùng bên trái của hình ảnh là 0xff000000, tất cả các pixel trên hàng trên cùng là L-pixel và tất cả các pixel trên cột ngoài cùng bên trái là T-pixel.
Việc giải quyết TR-pixel cho các pixel ở cột ngoài cùng bên phải là điều đặc biệt. Các pixel ở cột ngoài cùng bên phải được dự đoán bằng cách sử dụng các chế độ [0..13], giống như các pixel không nằm trên đường viền, nhưng pixel ngoài cùng bên trái trên cùng hàng với pixel hiện tại sẽ được dùng làm pixel TR.
Giá trị pixel cuối cùng được tính bằng cách cộng từng kênh của giá trị dự đoán với giá trị dư đã mã hoá.
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 Biến đổi màu
Mục tiêu của quá trình biến đổi màu là loại bỏ mối tương quan giữa các giá trị R, G và B của từng pixel. Phép biến đổi màu giữ nguyên giá trị màu xanh lục (G), biến đổi giá trị màu đỏ (R) dựa trên giá trị màu xanh lục và biến đổi giá trị màu xanh lam (B) dựa trên giá trị màu xanh lục rồi đến giá trị màu đỏ.
Như trường hợp của biến đổi dự đoán, trước tiên, hình ảnh được chia thành các khối và cùng một chế độ biến đổi được dùng cho tất cả các pixel trong một khối. Đối với mỗi khối, có 3 loại phần tử biến đổi màu.
typedef struct {
uint8 green_to_red;
uint8 green_to_blue;
uint8 red_to_blue;
} ColorTransformElement;
Biến đổi màu thực tế được thực hiện bằng cách xác định một delta biến đổi màu. Mức chênh lệch biến đổi màu phụ thuộc vào ColorTransformElement, mức này giống nhau đối với tất cả các pixel trong một khối cụ thể. Delta được trừ trong quá trình chuyển đổi màu. Sau đó, phép biến đổi màu đảo ngược chỉ cần thêm các delta đó.
Hàm biến đổi màu được xác định như sau:
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 được tính bằng cách sử dụng số nguyên 8 bit có dấu biểu thị số cố định 3,5 và kênh màu RGB 8 bit có dấu (c) [-128..127] và được xác định như sau:
int8 ColorTransformDelta(int8 t, int8 c) {
return (t * c) >> 5;
}
Bạn phải chuyển đổi từ biểu thị không dấu 8 bit (uint8) sang biểu thị có dấu 8 bit (int8) trước khi gọi ColorTransformDelta(). Giá trị đã ký phải được diễn giải là số bù hai 8 bit (tức là: dải uint8 [128..255] được ánh xạ đến dải [-128..-1] của giá trị int8 đã chuyển đổi).
Phép nhân phải được thực hiện với độ chính xác cao hơn (ít nhất là độ chính xác 16 bit). Thuộc tính mở rộng dấu của thao tác dịch chuyển không quan trọng ở đây; chỉ 8 bit thấp nhất được dùng từ kết quả và trong các bit này, thao tác dịch chuyển mở rộng dấu và thao tác dịch chuyển không dấu nhất quán với nhau.
Giờ đây, chúng ta mô tả nội dung của dữ liệu biến đổi màu để quá trình giải mã có thể áp dụng phép biến đổi màu nghịch đảo và khôi phục các giá trị màu đỏ và màu xanh dương ban đầu. 3 bit đầu tiên của dữ liệu biến đổi màu chứa chiều rộng và chiều cao của khối hình ảnh theo số lượng bit, giống như biến đổi dự đoán:
int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;
Phần còn lại của dữ liệu biến đổi màu chứa các thực thể ColorTransformElement, tương ứng với từng khối của hình ảnh. Mỗi ColorTransformElement 'cte' được coi là một pixel trong hình ảnh có độ phân giải phụ mà thành phần alpha là 255, thành phần màu đỏ là cte.red_to_blue, thành phần màu xanh lục là cte.green_to_blue và thành phần màu xanh lam là cte.green_to_red.
Trong quá trình giải mã, các thực thể ColorTransformElement của các khối sẽ được giải mã và phép biến đổi màu nghịch đảo được áp dụng cho các giá trị ARGB của các pixel. Như đã đề cập trước đó, phép biến đổi màu đảo ngược chỉ là thêm các giá trị ColorTransformElement vào các kênh màu đỏ và màu xanh dương. Các kênh alpha và green vẫn giữ nguyên.
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 Trừ phép biến đổi màu xanh lục
Biến đổi trừ màu xanh lục sẽ trừ các giá trị màu xanh lục khỏi các giá trị màu đỏ và màu xanh lam của mỗi pixel. Khi có phép biến đổi này, bộ giải mã cần thêm giá trị màu xanh lục vào cả giá trị màu đỏ và màu xanh dương. Không có dữ liệu nào liên kết với phép biến đổi này. Bộ giải mã áp dụng phép biến đổi nghịch đảo như sau:
void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
*red = (*red + green) & 0xff;
*blue = (*blue + green) & 0xff;
}
Phép biến đổi này là dư thừa vì có thể mô hình hoá bằng phép biến đổi màu. Tuy nhiên, vì không có dữ liệu bổ sung nào ở đây, nên phép biến đổi trừ màu xanh lục có thể được mã hoá bằng ít bit hơn so với phép biến đổi màu đầy đủ.
4.4 Biến đổi lập chỉ mục màu
Nếu không có nhiều giá trị pixel riêng biệt, thì việc tạo một mảng chỉ mục màu và thay thế các giá trị pixel bằng chỉ mục của mảng có thể hiệu quả hơn. Biến đổi lập chỉ mục màu sẽ thực hiện việc này. (Trong bối cảnh WebP không tổn hao, chúng tôi không gọi đây là một biến đổi bảng màu vì có một khái niệm tương tự nhưng linh hoạt hơn trong phương pháp mã hoá không tổn hao WebP: bộ nhớ đệm màu.)
Phép biến đổi lập chỉ mục màu sẽ kiểm tra số lượng giá trị ARGB riêng biệt trong hình ảnh. Nếu số đó thấp hơn một ngưỡng (256), thì nó sẽ tạo một mảng gồm các giá trị ARGB đó, sau đó được dùng để thay thế các giá trị pixel bằng chỉ mục tương ứng: kênh màu xanh lục của các pixel được thay thế bằng chỉ mục, tất cả các giá trị alpha được đặt thành 255 và tất cả các giá trị màu đỏ và màu xanh dương được đặt thành 0.
Dữ liệu biến đổi chứa kích thước bảng màu và các mục trong bảng màu. Bộ giải mã đọc dữ liệu biến đổi lập chỉ mục màu như sau:
// 8-bit value for the color table size
int color_table_size = ReadBits(8) + 1;
Bảng màu được lưu trữ bằng chính định dạng lưu trữ hình ảnh. Bạn có thể lấy bảng màu bằng cách đọc một hình ảnh mà không có tiêu đề RIFF, kích thước hình ảnh và các phép biến đổi, giả sử chiều cao là 1 pixel và chiều rộng là color_table_size.
Bảng màu luôn được mã hoá theo phương pháp trừ để giảm entropy hình ảnh. Các delta của màu trong bảng màu thường chứa ít entropy hơn nhiều so với chính các màu, giúp tiết kiệm đáng kể cho những hình ảnh nhỏ hơn. Trong quá trình giải mã, bạn có thể thu được mọi màu cuối cùng trong bảng màu bằng cách cộng các giá trị thành phần màu trước đó theo từng thành phần ARGB riêng biệt và lưu trữ 8 bit ít quan trọng nhất của kết quả.
Phép biến đổi nghịch đảo cho hình ảnh chỉ đơn giản là thay thế các giá trị pixel (là chỉ mục cho bảng màu) bằng các giá trị thực của bảng màu. Việc lập chỉ mục được thực hiện dựa trên thành phần màu xanh lục của màu ARGB.
// Inverse transform
argb = color_table[GREEN(argb)];
Nếu chỉ mục bằng hoặc lớn hơn color_table_size, thì giá trị màu argb phải được đặt thành 0x00000000 (màu đen trong suốt).
Khi bảng màu nhỏ (bằng hoặc nhỏ hơn 16 màu), một số pixel sẽ được kết hợp thành một pixel duy nhất. Tính năng kết hợp pixel sẽ kết hợp một số (2, 4 hoặc 8) pixel thành một pixel duy nhất, giúp giảm chiều rộng hình ảnh tương ứng. Việc kết hợp pixel cho phép mã hoá entropy phân phối chung hiệu quả hơn cho các pixel lân cận và mang lại một số lợi ích tương tự như mã hoá số học cho mã entropy, nhưng chỉ có thể sử dụng khi có 16 giá trị riêng biệt trở xuống.
color_table_size chỉ định số lượng pixel được kết hợp:
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 có giá trị là 0, 1, 2 hoặc 3. Giá trị 0 cho biết không có hoạt động kết hợp pixel nào được thực hiện cho hình ảnh. Giá trị 1 cho biết 2 pixel được kết hợp và mỗi pixel có phạm vi [0..15]. Giá trị 2 cho biết 4 pixel được kết hợp và mỗi pixel có một dải [0..3]. Giá trị 3 cho biết 8 pixel được kết hợp và mỗi pixel có phạm vi [0..1], tức là một giá trị nhị phân.
Các giá trị được đóng gói vào thành phần màu xanh lục như sau:
width_bits= 1: Đối với mọi giá trị x, trong đó x ≡ 0 (mod 2), giá trị màu xanh lục tại x được đặt vào 4 bit có giá trị nhỏ nhất của giá trị màu xanh lục tại x / 2 và giá trị màu xanh lục tại x + 1 được đặt vào 4 bit có giá trị lớn nhất của giá trị màu xanh lục tại x / 2.width_bits= 2: Đối với mọi giá trị x, trong đó x ≡ 0 (mod 4), giá trị màu xanh lục tại x được đặt vào 2 bit có giá trị nhỏ nhất của giá trị màu xanh lục tại x / 4, và các giá trị màu xanh lục tại x + 1 đến x + 3 được đặt theo thứ tự vào các bit có giá trị lớn hơn của giá trị màu xanh lục tại x / 4.width_bits= 3: Đối với mọi giá trị x, trong đó x ≡ 0 (mod 8), giá trị màu xanh lục tại x được đặt vào bit có giá trị nhỏ nhất của giá trị màu xanh lục tại x / 8, còn các giá trị màu xanh lục tại x + 1 đến x + 7 được đặt theo thứ tự vào các bit có giá trị lớn hơn của giá trị màu xanh lục tại x / 8.
Sau khi đọc phép biến đổi này, image_width sẽ được lấy mẫu phụ theo width_bits. Điều này ảnh hưởng đến kích thước của các phép biến đổi tiếp theo. Bạn có thể tính toán kích thước mới bằng cách sử dụng DIV_ROUND_UP, như đã xác định trước đó.
image_width = DIV_ROUND_UP(image_width, 1 << width_bits);
5 Dữ liệu hình ảnh
Dữ liệu hình ảnh là một mảng các giá trị pixel theo thứ tự dòng quét.
5.1 Vai trò của dữ liệu hình ảnh
Chúng tôi sử dụng dữ liệu hình ảnh cho 5 vai trò khác nhau:
- Hình ảnh ARGB: Lưu trữ các pixel thực tế của hình ảnh.
- Hình ảnh entropy: Lưu trữ mã tiền tố meta (xem phần "Giải mã mã tiền tố meta").
- Hình ảnh dự đoán: Lưu trữ siêu dữ liệu cho phép biến đổi dự đoán (xem "Biến đổi dự đoán").
- Hình ảnh biến đổi màu: Được tạo bằng các giá trị
ColorTransformElement(được xác định trong "Biến đổi màu") cho các khối khác nhau của hình ảnh. - Hình ảnh lập chỉ mục màu: Một mảng có kích thước
color_table_size(tối đa 256 giá trị ARGB) lưu trữ siêu dữ liệu cho phép biến đổi lập chỉ mục màu (xem "Biến đổi lập chỉ mục màu").
5.2 Mã hoá dữ liệu hình ảnh
Việc mã hoá dữ liệu hình ảnh không phụ thuộc vào vai trò của dữ liệu đó.
Đầu tiên, hình ảnh được chia thành một tập hợp các khối có kích thước cố định (thường là các khối 16x16). Mỗi khối này được mô hình hoá bằng cách sử dụng mã entropy riêng. Ngoài ra, một số khối có thể dùng chung cùng một mã entropy.
Lý do: Việc lưu trữ mã entropy sẽ tốn chi phí. Chi phí này có thể được giảm thiểu nếu các khối tương tự về mặt thống kê dùng chung một mã entropy, nhờ đó chỉ lưu trữ mã đó một lần. Ví dụ: bộ mã hoá có thể tìm thấy các khối tương tự bằng cách phân cụm chúng bằng các thuộc tính thống kê hoặc bằng cách liên tục kết hợp một cặp cụm được chọn ngẫu nhiên khi bộ mã hoá giảm tổng số bit cần thiết để mã hoá hình ảnh.
Mỗi pixel được mã hoá bằng một trong ba phương thức có thể có:
- Các chữ cố định được mã hoá bằng tiền tố: Mỗi kênh (xanh lục, đỏ, xanh dương và alpha) đều được mã hoá entropy một cách độc lập.
- Tham chiếu ngược LZ77: Một chuỗi pixel được sao chép từ nơi khác trong hình ảnh.
- Mã bộ nhớ đệm màu: Sử dụng mã băm nhân ngắn (chỉ mục bộ nhớ đệm màu) của một màu vừa xuất hiện.
Các tiểu mục sau đây sẽ mô tả chi tiết từng bước.
5.2.1 Chữ cố định được mã hoá bằng tiền tố
Pixel được lưu trữ dưới dạng các giá trị được mã hoá bằng tiền tố của màu xanh lục, đỏ, xanh dương và alpha (theo thứ tự đó). Hãy xem Mục 6.2.3 để biết thông tin chi tiết.
5.2.2 Tham chiếu ngược LZ77
Tham chiếu ngược là các bộ gồm độ dài và mã khoảng cách:
- Chiều dài cho biết số lượng pixel theo thứ tự dòng quét sẽ được sao chép.
- Mã khoảng cách là một số cho biết vị trí của một pixel đã thấy trước đó, từ đó các pixel sẽ được sao chép. Bạn có thể xem thông tin chi tiết về mối liên kết này bên dưới.
Các giá trị về độ dài và khoảng cách được lưu trữ bằng cách sử dụng mã hoá tiền tố LZ77.
Phương pháp mã hoá tiền tố LZ77 chia các giá trị số nguyên lớn thành hai phần: mã tiền tố và các bit bổ sung. Mã tiền tố được lưu trữ bằng mã entropy, trong khi các bit bổ sung được lưu trữ nguyên trạng (không có mã entropy).
Lý do: Phương pháp này giúp giảm yêu cầu về bộ nhớ đối với mã entropy. Ngoài ra, các giá trị lớn thường hiếm gặp, vì vậy, các bit bổ sung sẽ được dùng cho rất ít giá trị trong hình ảnh. Do đó, cách tiếp cận này giúp nén tốt hơn nói chung.
Bảng sau đây biểu thị mã tiền tố và các bit bổ sung được dùng để lưu trữ các dải giá trị khác nhau.
| Phạm vi giá trị | Mã tiền tố | Bit bổ sung |
|---|---|---|
| 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 |
Mã giả để lấy giá trị (độ dài hoặc khoảng cách) từ mã tiền tố như sau:
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;
Ánh xạ khoảng cách
Như đã lưu ý trước đó, mã khoảng cách là một số cho biết vị trí của một pixel đã thấy trước đó, từ đó các pixel sẽ được sao chép. Tiểu mục này xác định ánh xạ giữa mã khoảng cách và vị trí của một pixel trước đó.
Mã khoảng cách lớn hơn 120 biểu thị khoảng cách pixel theo thứ tự dòng quét, bù 120.
Các mã khoảng cách nhỏ nhất [1..120] là mã đặc biệt và được dành riêng cho vùng lân cận của pixel hiện tại. Khu vực lân cận này bao gồm 120 pixel:
- Các pixel nằm từ 1 đến 7 hàng phía trên pixel hiện tại và có tối đa 8 cột ở bên trái hoặc tối đa 7 cột ở bên phải pixel hiện tại. [Tổng số pixel như vậy =
7 * (8 + 1 + 7) = 112]. - Các pixel nằm trong cùng hàng với pixel hiện tại và có tối đa 8 cột ở bên trái pixel hiện tại. [
8pixel như vậy].
Sau đây là mối quan hệ giữa mã khoảng cách distance_code và độ lệch pixel lân cận (xi, yi):
(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)
Ví dụ: mã khoảng cách 1 cho biết độ lệch là (0, 1) cho pixel lân cận, tức là pixel phía trên pixel hiện tại (chênh lệch 0 pixel theo hướng X và chênh lệch 1 pixel theo hướng Y).
Tương tự, mã khoảng cách 3 cho biết pixel trên cùng bên trái.
Bộ giải mã có thể chuyển đổi mã khoảng cách distance_code thành khoảng cách theo thứ tự dòng quét dist như sau:
(xi, yi) = distance_map[distance_code - 1]
dist = xi + yi * image_width
if (dist < 1) {
dist = 1
}
trong đó distance_map là ánh xạ được lưu ý ở trên và image_width là chiều rộng của hình ảnh tính bằng pixel.
5.2.3 Mã hoá bộ nhớ đệm màu
Bộ nhớ đệm màu lưu trữ một nhóm màu đã được dùng gần đây trong hình ảnh.
Lý do: Bằng cách này, đôi khi bạn có thể tham chiếu các màu đã dùng gần đây một cách hiệu quả hơn so với việc phát ra các màu đó bằng hai phương thức khác (được mô tả trong 5.2.1 và 5.2.2).
Mã bộ nhớ đệm màu được lưu trữ như sau. Trước tiên, có một giá trị 1 bit cho biết có sử dụng bộ nhớ đệm màu hay không. Nếu bit này là 0, thì không có mã bộ nhớ đệm màu và các mã này không được truyền trong mã tiền tố giải mã các biểu tượng màu xanh lục và mã tiền tố độ dài. Tuy nhiên, nếu bit này là 1, thì kích thước bộ nhớ đệm màu sẽ được đọc tiếp theo:
int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;
color_cache_code_bits xác định kích thước của bộ nhớ đệm màu (1 <<
color_cache_code_bits). Phạm vi giá trị được phép cho color_cache_code_bits là [1..11]. Các bộ giải mã tuân thủ phải cho biết một luồng bit bị hỏng cho các giá trị khác.
Bộ nhớ đệm màu là một mảng có kích thước color_cache_size. Mỗi mục nhập lưu trữ một màu ARGB. Màu sắc được tra cứu bằng cách lập chỉ mục theo (0x1e35a7bd * color) >> (32 -
color_cache_code_bits). Chỉ có một hoạt động tra cứu được thực hiện trong bộ nhớ đệm màu; không có giải pháp xung đột.
Khi bắt đầu giải mã hoặc mã hoá hình ảnh, tất cả các mục trong tất cả các giá trị bộ nhớ đệm màu đều được đặt thành 0. Mã bộ nhớ đệm màu được chuyển đổi thành màu này tại thời điểm giải mã. Trạng thái của bộ nhớ đệm màu được duy trì bằng cách chèn mọi pixel (cho dù được tạo bằng cách tham chiếu ngược hay dưới dạng chữ) vào bộ nhớ đệm theo thứ tự xuất hiện trong luồng.
6 Mã Entropy
6.1 Tổng quan
Hầu hết dữ liệu được mã hoá bằng mã tiền tố chuẩn. Do đó, các mã này được truyền bằng cách gửi độ dài mã tiền tố, thay vì mã tiền tố thực tế.
Cụ thể, định dạng này sử dụng phương pháp mã hoá tiền tố biến đổi theo không gian. Nói cách khác, các khối khác nhau của hình ảnh có thể sử dụng các mã entropy khác nhau.
Lý do: Các khu vực khác nhau của hình ảnh có thể có các đặc điểm khác nhau. Vì vậy, việc cho phép chúng sử dụng các mã entropy khác nhau sẽ mang lại tính linh hoạt cao hơn và có khả năng nén tốt hơn.
6.2 Chi tiết
Dữ liệu hình ảnh được mã hoá bao gồm nhiều phần:
- Giải mã và tạo mã tiền tố.
- Mã tiền tố meta.
- Dữ liệu hình ảnh được mã hoá entropy.
Đối với một pixel nhất định (x, y), có một tập hợp gồm 5 mã tiền tố được liên kết với pixel đó. Các mã này (theo thứ tự luồng bit) là:
- Mã tiền tố 1: Dùng cho kênh xanh lục, độ dài tham chiếu ngược và bộ nhớ đệm màu.
- Mã tiền tố 2, 3 và 4: Lần lượt được dùng cho các kênh màu đỏ, xanh dương và alpha.
- Mã tiền tố số 5: Dùng cho khoảng cách tham chiếu ngược.
Từ đây trở đi, chúng ta sẽ gọi nhóm này là nhóm mã tiền tố.
6.2.1 Giải mã và tạo mã tiền tố
Phần này mô tả cách đọc độ dài mã tiền tố từ luồng bit.
Bạn có thể mã hoá độ dài mã tiền tố theo hai cách. Phương thức được dùng sẽ do một giá trị 1 bit chỉ định.
- Nếu bit này là 1, thì đó là mã có độ dài mã đơn giản.
- Nếu bit này là 0, thì đó là mã có độ dài mã thông thường.
Trong cả hai trường hợp, có thể có các độ dài mã không dùng đến vẫn nằm trong luồng. Cách này có thể không hiệu quả nhưng được định dạng cho phép. Cây được mô tả phải là cây nhị phân đầy đủ. Một nút lá duy nhất được coi là cây nhị phân đầy đủ và có thể được mã hoá bằng mã độ dài mã đơn giản hoặc mã độ dài mã thông thường. Khi mã hoá một nút lá duy nhất bằng mã có độ dài mã thông thường, tất cả trừ một độ dài mã đều bằng 0 và giá trị nút lá duy nhất được đánh dấu bằng độ dài 1 – ngay cả khi không có bit nào được sử dụng khi cây nút lá duy nhất đó được dùng.
Mã chiều dài mã đơn giản
Biến thể này được dùng trong trường hợp đặc biệt khi chỉ có 1 hoặc 2 ký hiệu tiền tố trong phạm vi [0..255] với độ dài mã 1. Tất cả các độ dài mã tiền tố khác đều là số 0 ngầm định.
Bit đầu tiên cho biết số lượng ký hiệu:
int num_symbols = ReadBits(1) + 1;
Sau đây là các giá trị biểu tượng.
Ký hiệu đầu tiên này được mã hoá bằng 1 hoặc 8 bit, tuỳ thuộc vào giá trị của is_first_8bits. Phạm vi tương ứng là [0..1] hoặc [0..255]. Ký hiệu thứ hai (nếu có) luôn được giả định nằm trong khoảng [0..255] và được mã hoá bằng 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;
}
Hai biểu tượng này phải khác nhau. Bạn có thể dùng các ký hiệu trùng lặp, nhưng điều này không hiệu quả.
Lưu ý: Một trường hợp đặc biệt khác là khi độ dài mã tiền tố tất cả đều là số không (mã tiền tố trống). Ví dụ: mã tiền tố cho khoảng cách có thể trống nếu không có các tham chiếu ngược. Tương tự, mã tiền tố cho alpha, đỏ và xanh dương có thể trống nếu tất cả các pixel trong cùng một mã tiền tố meta được tạo bằng bộ nhớ đệm màu. Tuy nhiên, trường hợp này không cần xử lý đặc biệt, vì mã tiền tố trống có thể được mã hoá dưới dạng mã chứa một biểu tượng duy nhất 0.
Mã độ dài mã thông thường
Độ dài mã của mã tiền tố nằm trong 8 bit và được đọc như sau.
Trước tiên, num_code_lengths chỉ định số lượng độ dài mã.
int num_code_lengths = 4 + ReadBits(4);
Bản thân độ dài mã được mã hoá bằng mã tiền tố; trước tiên, bạn phải đọc độ dài mã cấp thấp hơn, code_length_code_lengths. Phần còn lại của code_length_code_lengths (theo thứ tự trong kCodeLengthCodeOrder) là số 0.
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);
}
Tiếp theo, nếu ReadBits(1) == 0, số lượng tối đa của các ký hiệu đọc khác nhau (max_symbol) cho mỗi loại ký hiệu (A, R, G, B và khoảng cách) được đặt thành kích thước bảng chữ cái của ký hiệu đó:
- Kênh G: 256 + 24 +
color_cache_size - Các chữ cố định khác (A, R và B): 256
- Mã khoảng cách: 40
Nếu không, nó được xác định là:
int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);
Nếu max_symbol lớn hơn kích thước của bảng chữ cái cho loại biểu tượng, thì luồng bit sẽ không hợp lệ.
Sau đó, một bảng tiền tố được tạo từ code_length_code_lengths và dùng để đọc tối đa max_symbol độ dài mã.
- Mã [0..15] cho biết độ dài mã theo nghĩa đen.
- Giá trị 0 có nghĩa là không có ký hiệu nào được mã hoá.
- Giá trị [1..15] cho biết độ dài bit của mã tương ứng.
- Mã 16 lặp lại giá trị khác 0 trước đó [3..6] lần, tức là
3 + ReadBits(2)lần. Nếu mã 16 được dùng trước khi một giá trị khác 0 được phát ra, thì giá trị 8 sẽ được lặp lại. - Mã 17 phát ra một chuỗi gồm các số 0 có độ dài [3..10], tức là
3 + ReadBits(3)lần. - Mã 18 phát ra một chuỗi số 0 có độ dài [11..138], tức là
11 + ReadBits(7)lần.
Sau khi đọc độ dài mã, mã tiền tố cho mỗi loại ký hiệu (A, R, G, B và khoảng cách) sẽ được tạo bằng cách sử dụng kích thước bảng chữ cái tương ứng.
Mã độ dài mã thông thường phải mã hoá một cây quyết định đầy đủ, tức là tổng của 2 ^ (-length) cho tất cả các mã khác 0 phải chính xác bằng 1. Tuy nhiên, có một trường hợp ngoại lệ đối với quy tắc này, đó là cây có một nút lá duy nhất, trong đó giá trị nút lá được đánh dấu bằng giá trị 1 và các giá trị khác là 0.
6.2.2 Giải mã mã tiền tố Meta
Như đã lưu ý trước đó, định dạng này cho phép sử dụng các mã tiền tố khác nhau cho các khối hình ảnh khác nhau. Mã tiền tố meta là các chỉ mục xác định mã tiền tố cần dùng trong các phần khác nhau của hình ảnh.
Bạn chỉ có thể sử dụng mã tiền tố meta khi hình ảnh đang được dùng trong vai trò của một hình ảnh ARGB.
Có hai khả năng cho mã tiền tố meta, được biểu thị bằng giá trị 1 bit:
- Nếu bit này bằng 0, thì chỉ có một mã tiền tố meta được dùng ở mọi nơi trong hình ảnh. Không có dữ liệu nào được lưu trữ nữa.
- Nếu bit này là 1, thì hình ảnh sẽ sử dụng nhiều mã tiền tố meta. Các mã tiền tố meta này được lưu trữ dưới dạng hình ảnh entropy (được mô tả bên dưới).
Các thành phần màu đỏ và xanh lục của một pixel xác định mã tiền tố meta 16 bit được dùng trong một khối cụ thể của hình ảnh ARGB.
Hình ảnh Entropy
Hình ảnh entropy xác định mã tiền tố nào được dùng trong các phần khác nhau của hình ảnh.
3 bit đầu tiên chứa giá trị prefix_bits. Kích thước của hình ảnh entropy được lấy từ 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);
trong đó DIV_ROUND_UP được xác định trước đó.
Các bit tiếp theo chứa một hình ảnh entropy có chiều rộng prefix_image_width và chiều cao prefix_image_height.
Giải thích mã tiền tố meta
Bạn có thể lấy số lượng nhóm mã tiền tố trong hình ảnh ARGB bằng cách tìm mã tiền tố meta lớn nhất trong hình ảnh entropy:
int num_prefix_groups = max(entropy image) + 1;
trong đó max(entropy image) cho biết mã tiền tố lớn nhất được lưu trữ trong hình ảnh entropy.
Vì mỗi nhóm mã tiền tố chứa 5 mã tiền tố, nên tổng số mã tiền tố là:
int num_prefix_codes = 5 * num_prefix_groups;
Với một pixel (x, y) trong hình ảnh ARGB, chúng ta có thể lấy các mã tiền tố tương ứng để sử dụng như sau:
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];
trong đó chúng ta giả định sự tồn tại của cấu trúc PrefixCodeGroup, đại diện cho một tập hợp gồm 5 mã tiền tố. Ngoài ra, prefix_code_groups là một mảng PrefixCodeGroup (có kích thước num_prefix_groups).
Sau đó, bộ giải mã sẽ sử dụng nhóm mã tiền tố prefix_group để giải mã pixel (x, y), như giải thích trong phần "Giải mã dữ liệu hình ảnh được mã hoá entropy".
6.2.3 Giải mã dữ liệu hình ảnh được mã hoá bằng entropy
Đối với vị trí hiện tại (x, y) trong hình ảnh, trước tiên, bộ giải mã sẽ xác định nhóm mã tiền tố tương ứng (như đã giải thích trong phần cuối). Với nhóm mã tiền tố, pixel được đọc và giải mã như sau.
Tiếp theo, hãy đọc ký hiệu S từ luồng bit bằng mã tiền tố số 1. Lưu ý rằng S là một số nguyên bất kỳ trong phạm vi từ 0 đến (256 + 24 + color_cache_size- 1).
Cách diễn giải S phụ thuộc vào giá trị của S:
- Nếu S < 256
- Sử dụng S làm thành phần màu xanh lục.
- Đọc màu đỏ từ luồng bit bằng mã tiền tố số 2.
- Đọc màu xanh dương từ luồng bit bằng mã tiền tố số 3.
- Đọc alpha từ luồng bit bằng mã tiền tố số 4.
- Nếu S >= 256 & S < 256 + 24
- Sử dụng S – 256 làm mã tiền tố độ dài.
- Đọc các bit bổ sung cho độ dài từ luồng bit.
- Xác định độ dài tham chiếu ngược L từ mã tiền tố độ dài và các bit bổ sung đã đọc.
- Đọc mã tiền tố khoảng cách từ luồng bit bằng mã tiền tố số 5.
- Đọc các bit bổ sung cho khoảng cách từ luồng bit.
- Xác định khoảng cách tham chiếu ngược D từ mã tiền tố khoảng cách và các bit bổ sung đã đọc.
- Sao chép L pixel (theo thứ tự dòng quét) từ chuỗi pixel bắt đầu tại vị trí hiện tại trừ đi D pixel.
- Nếu S >= 256 + 24
- Sử dụng S – (256 + 24) làm chỉ mục trong bộ nhớ đệm màu.
- Lấy màu ARGB từ bộ nhớ đệm màu tại chỉ mục đó.
7 Cấu trúc tổng thể của định dạng
Dưới đây là thông tin về định dạng trong Augmented Backus-Naur Form (ABNF) RFC 5234 RFC 7405. Bản xem trước này không bao gồm đầy đủ thông tin chi tiết. Phần cuối của hình ảnh (EOI) chỉ được mã hoá ngầm thành số lượng pixel (image_width * image_height).
Xin lưu ý rằng *element có nghĩa là element có thể lặp lại 0 hoặc nhiều lần. 5element có nghĩa là element được lặp lại đúng 5 lần. %b biểu thị một giá trị nhị phân.
7.1 Cấu trúc cơ bản
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 Cấu trúc của các phép biến đổi
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 Cấu trúc của dữ liệu hình ảnh
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)
Sau đây là một ví dụ có thể xảy ra:
RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image