Jyrki Alakuijala, Tiến sĩ, Google, Inc., 9-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 hình ảnh ARGB không tổn hao. Chiến lược phát hành đĩa đơn định dạng không tổn hao lưu trữ và khôi phục chính xác giá trị pixel, bao gồm cho các pixel hoàn toàn trong suốt. Một thuật toán phổ biến cho tuần tự nén dữ liệu (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ư độ nén với mật độ cao hơn 25% so với khả năng đạt được bằng cách sử dụng định dạng PNG của ngày hôm nay.
1 Giới thiệu
Tài liệu này mô tả bản trình bày dữ liệu nén của một WebP không tổn hao hình ảnh. Đây là tài liệu tham khảo chi tiết cho bộ mã hoá WebP không tổn hao và bộ giải mã.
Trong tài liệu này, chúng tôi sử dụng rộng rãi cú pháp của ngôn ngữ lập trình C để mô tả
luồng bit và giả định tồn tại một hàm để đọc bit,
ReadBits(n)
. Các byte được đọc theo thứ tự tự nhiên của luồng chứa
và các bit của mỗi byte được đọc theo thứ tự bit đầu tiên có ý nghĩa ít nhất. Thời gian
nhiều bit được đọc cùng một lúc, số nguyên được tạo từ
dữ liệu gốc theo thứ tự ban đầu. Những bit quan trọng nhất của dữ liệu được trả về
số nguyên cũng là các bit quan trọng nhất của dữ liệu gốc. Do đó,
tuyên bố
b = ReadBits(2);
tương đương với hai câu lệnh 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 lam và xanh lục, là được biểu thị bằng byte 8 bit. Chúng ta xác định kiểu dữ liệu tương ứng là uint8. Đáp toàn bộ pixel ARGB được biểu thị bằng một loại có tên là uint32, số nguyên 32 bit. Trong đoạn mã cho thấy hành vi của biến đổi, các giá trị này được mã hoá thành các bit sau: alpha theo bit 31..24, màu đỏ trong bit 23..16, màu xanh lục trong bit 15..8 và màu xanh lam trong bit 7..0; tuy nhiên, việc triển khai định dạng này miễn phí để sử dụng một cách trình bày khác trong nội bộ.
Nhìn chung, một hình ảnh WebP không tổn 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. WebP có thể trải qua 4 loại biến đổi khác nhau trước khi được entropy. Thông tin biến đổi trong luồng bit chứa dữ liệu cần thiết để áp dụng phép biến đổi nghịch đảo tương ứng.
2 Danh pháp
- ARGB (thực tế tăng cường)
- Một 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 sử dụng gần đây để có thể hãy nhớ lại chúng bằng các mã ngắn hơn.
- hình ảnh lập chỉ mục màu
- Hình ảnh một chiều của các màu có thể được lập chỉ mục bằng một số nguyên nhỏ (lên đến 256 trong WebP không tổn hao).
- hình ảnh biến đổi màu
- Hình ảnh phân giải phụ hai chiều chứa dữ liệu về mối tương quan của thành phần màu.
- lập bản đồ khoảng cách
- Thay đổi khoảng cách LZ77 để pixel có giá trị nhỏ nhất độ gần hai chiều.
- hình ảnh entropy
- Hình ảnh có độ phân giải phụ hai chiều cho biết nên mã hoá entropy nào được sử dụng trong hình vuông tương ứng trong hình ảnh, nghĩa là mỗi pixel là một siêu dữ liệu mã tiền tố.
- LZ77
- Thuật toán nén cửa sổ trượt dựa trên từ điển hoặc mô tả chúng dưới dạng chuỗi các ký hiệu trong quá khứ.
- mã tiền tố meta
- Một số nguyên nhỏ (tối đa 16 bit) dùng để lập chỉ mục một phần tử trong tiền tố meta bảng.
- hình ảnh gợi ý
- Hình ảnh có độ phân giải phụ hai chiều cho biết công cụ dự đoán không gian nào dùng cho một hình vuông cụ thể trong ảnh.
- mã tiền tố
- Một phương pháp cổ điển để mã hoá entropy khi sử dụng số lượng bit nhỏ hơn để biết các mã thường xuyên hơn.
- mã hoá tiền tố
- Một cách để entropy mã hoá số nguyên lớn hơn, bằng cách này 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 thô. Điều này cho phép mô tả của mã entropy vẫn tương đối nhỏ ngay cả khi phạm vi ký hiệu rất lớn.
- đơn đặt hàng dòng quét
- Thứ tự xử lý 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 thành 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 Tiêu đề RIFF
Phần đầu của tiêu đề có vùng chứa RIFF. Điều này bao gồm 21 byte sau:
- Chuỗi 'RIFF'.
- Một giá trị nhỏ-endian, 32-bit của độ dài đoạn, tức là kích thước toàn bộ của phân đoạn được kiểm soát bởi tiêu đề RIFF. Thông thường, giá trị 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 "RIFF" mã nhận dạng và 4 byte để lưu trữ chính giá trị đó).
- Chuỗi 'WEBP' (tên vùng chứa RIFF).
- Chuỗi "VP8L" (Bốn CC cho dữ liệu hình ảnh được mã hoá không tổn hao).
- Một giá trị nhỏ-endian 32 bit của số byte trong vùng luồng không tổn hao.
- 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 không tổn hao WebP tới 16384 lần thứ tự 16384 pixel.
Bit alpha_is_used chỉ là một gợi ý và sẽ không ảnh hưởng đến việc giải mã. Phải được đặt thành 0 khi tất cả các giá trị alpha là 255 trong hình và nếu không là 1.
int alpha_is_used = ReadBits(1);
version_number là mã 3 bit phải được đặt thành 0. Mọi giá trị khác sẽ sẽ bị coi là lỗi.
int version_number = ReadBits(3);
4 phép biến đổi
Những biến đổi này là những thao tác đảo ngược dữ liệu hình ảnh có thể làm giảm entropy tượng trưng còn lại bằng cách mô hình hoá mối tương quan về không gian và màu sắc. Chúng có thể làm cho quá trình nén cuối cùng trở nên đặc biệt hơn.
Một hình ảnh có thể trải qua bốn loại biến đổi. 1 bit cho biết sự hiện diện của một biến đổi. Mỗi biến đổi chỉ được phép sử dụng một lần. Chiến lược phát hành đĩa đơn biến đổi chỉ được sử dụng cho hình ảnh ARGB cấp chính; 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ó biến đổi, thậm chí không phải bit 0 biểu thị điểm kết thúc của biến đổi.
Thông thường, một bộ mã hoá sẽ sử dụng các biến đổi này để giảm entropy Shannon trong hình ảnh còn lại. Ngoài ra, dữ liệu biến đổi có thể được quyết định dựa trên entropy giảm tối đa.
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ó biến đổi, thì hai bit tiếp theo chỉ định loại biến đổi. Có bốn 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 đứng trước dữ liệu biến đổi. Chuyển đổi dữ liệu 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 biến đổi khác nhau. Phép biến đổi nghịch đảo được áp dụng theo thứ tự ngược lại chúng được đọc từ luồng bit, tức là luồng cuối cùng được đọc trước.
Tiếp theo, chúng ta sẽ mô tả dữ liệu biến đổi cho nhiều loại.
4.1 Biến đổi bộ dự đoán
Phép biến đổi phương pháp dự đoán có thể dùng để giảm entropy bằng cách khai thác dữ kiện thực tế các pixel lân cận thường là tương quan. Trong phép biến đổi công cụ dự đoán, giá trị pixel hiện tại được dự đoán từ các pixel đã được giải mã (trong dòng quét đơn đặt hàng) và chỉ giá trị còn lại (thực tế - dự đoán) mới được mã hoá. Màu xanh lục của một pixel xác định công cụ dự đoán nào trong số 14 công cụ dự đoán được sử dụng trong một khối cụ thể của hình ảnh ARGB. Chế độ dự đoán xác định loại để sử dụng. Chúng tôi chia hình ảnh thành các hình vuông và tất cả pixel trong một hình vuông đều sử dụng cùng 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ố 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 mỗi khối hình ảnh. Nó
là hình ảnh có độ phân giải phụ trong đó thành phần màu xanh lục của pixel xác định giá trị nào
14 công cụ dự đoán được dùng cho tất cả block_width * block_height
pixel 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ự được mô tả trong Chương 5.
Số lượng cột khối, transform_width
, được sử dụng trong hai chiều
lập chỉ mục. Đối với pixel (x, y), người ta có thể tính toán khối bộ lọc tương ứng
theo địa 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ị hiện tại giá trị pixel được dự đoán từ một hoặc nhiều pixel lân cận có giá trị là đã 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) làm 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 có nghĩa là trên cùng bên trái, T có nghĩa là trên cùng, TR có nghĩa là trên cùng bên phải và L có nghĩa là bên trái. Tại thời gian dự đoán giá trị cho P, tất cả các pixel O, TL, T, TR và L đã có đã được xử lý và pixel P và tất cả pixel X đều không xác định.
Với các pixel lân cận trước đó, các chế độ dự đoán khác nhau xác định như sau.
Chế độ | Giá trị dự đoán của mỗi kênh của pixel hiện tại |
---|---|
0 | 0xff000000 (đại diện cho màu đen đồng nhất trong ARGB) |
1 | L |
2 | T |
3 | lira Thổ Nhĩ Kỳ (TR) |
4 | trưởng nhóm |
5 | Trung bình2(Average2(L, TR), T) |
6 | Trung bình2(L; TL) |
7 | Trung bình 2(B; T) |
8 | Trung bình2(TL; T) |
9 | Trung bình 2(T, TR) |
10 | Trung bình2(Trung bình2(L, TL), Trung bình2(T, TR)) |
11 | Select(L, T, TL) |
12 | ClampAddSubtractFull(L, T, TL) |
13 | ClampAddSubtractHalf(Average2(L, T), TL) |
Average2
được định nghĩa như sau cho từng thành phần ARGB:
uint8 Average2(uint8 a, uint8 b) {
return (a + b) / 2;
}
Công cụ dự đoán Select (Chọ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 đường viền. Nếu có biến đổi dự báo, bất kể chế độ [0..13] của 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ả pixel ở hàng trên cùng là pixel L và tất cả các pixel ở cột ngoài cùng bên trái là T-pixel.
Xử lý TR-pixel cho các pixel ở cột ngoài cùng bên phải là đặc biệt. Các pixel trên 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ư pixel không nằm trên đường viền, mà là pixel ngoài cùng bên trái trên cùng một hàng với pixel hiện tại sẽ được dùng làm pixel TR.
Giá trị pixel cuối cùng thu được bằng cách thêm từng kênh của giá trị dự đoán thành giá trị còn lại được 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 việc biến đổi màu là để trang trí các giá trị R, G và B của mỗi điểm ảnh. Sự biến đổi màu giữ nguyên giá trị màu xanh lục (G), biến đổi màu đỏ (R) dựa trên giá trị màu xanh lục và chuyển đổi dựa trên giá trị màu xanh dương (B) trên giá trị màu xanh lục rồi chọn giá trị màu đỏ.
Như trường hợp của phép biến đổi công cụ dự đoán, trước tiên hình ảnh được chia thành khối và chế độ biến đổi tương tự được sử dụng cho tất cả các pixel trong một khối. Cho mỗi khối, có ba 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;
Sự biến đổi màu thực tế được thực hiện bằng cách xác định một delta chuyển đổi màu. Chiến lược phát hành đĩa đơn
delta biến đổi màu sắc phụ thuộc vào ColorTransformElement
, thuộc tính này giống nhau
cho tất cả các pixel trong một khối cụ thể. delta bị trừ trong
biến đổi màu sắc. Sau đó, việc chuyển đổi màu sắc nghịch đảo chỉ là thêm các delta đó.
Hàm biến đổi màu được định nghĩa 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 toán bằng cách sử dụng số nguyên 8 bit đã ký đại diện cho
3,5 số điểm cố định và kênh màu RGB 8 bit có dấu (c) [-128..127]
và được định nghĩa như sau:
int8 ColorTransformDelta(int8 t, int8 c) {
return (t * c) >> 5;
}
Chuyển đổi từ biểu diễn 8 bit không dấu (uint8) sang biểu diễn 8 bit có dấu
cần có một mã (int8) trước khi gọi ColorTransformDelta()
. Giá trị đã ký
nên được hiểu là số bổ sung của hai 8 bit (nghĩa là: phạm vi uint8
[128..255] được ánh xạ với phạm vi [-128..-1] của giá trị int8 được chuyển đổi của nó).
Phép nhân được thực hiện ở độ chính xác cao hơn (ít nhất là 16 bit độ chính xác). Thuộc tính tiện ích ký hiệu của thao tác chuyển không quan trọng tại đây; chỉ 8 bit thấp nhất được sử dụng từ kết quả, và dấu dịch chuyển phần mở rộng và dịch chuyển không dấu nhất quán với nhau.
Bây giờ, chúng tôi sẽ mô tả nội dung của dữ liệu biến đổi màu để có thể áp dụng giải mã nghịch đảo biến đổi màu và khôi phục các giá trị màu đỏ và màu xanh ban đầu. Chiến lược phát hành đĩa đơn 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ố bit, giống như phép biến đổi công cụ 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 có chứa ColorTransformElement
tương ứng với mỗi khối của hình ảnh. Một
ColorTransformElement
'cte'
được coi là một pixel trong hình ảnh có độ phân giải phụ
có thành phần alpha là 255
, thành phần màu đỏ là cte.red_to_blue
, màu xanh lục
thành phần là cte.green_to_blue
và thành phần màu xanh dương là cte.green_to_red
.
Trong khi giải mã, ColorTransformElement
bản sao của khối được giải mã và
thì phép biến đổi màu ngược được áp dụng cho các giá trị ARGB của pixel. Như
nêu trên, phép biến đổi màu nghịch đảo chỉ là thêm
ColorTransformElement
đối với kênh màu đỏ và màu xanh dương. Alpha và xanh lục
các kênh 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ừ biến đổi màu xanh lục
Phép biến đổi trừ màu xanh lục trừ các giá trị màu xanh lục từ giá trị màu đỏ và màu xanh của từng pixel. Khi có sự biến đổi này, bộ giải mã cần thêm màu xanh lục thành cả giá trị màu đỏ và màu xanh lam. Không có dữ liệu nào liên quan đến chỉ số này biến đổi. 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;
}
Sự biến đổi này là dư thừa vì có thể được lập mô hình bằng cách sử dụng biến đổi màu sắc, nhưng vì không có thêm dữ liệu ở đây, phép trừ màu xanh lục có thể là được mã hoá bằng cách sử dụng ít bit hơn so với biến đổi màu toàn bộ.
4.4 Chuyển đổi lập chỉ mục màu
Nếu không có nhiều giá trị pixel duy nhất thì việc tạo mảng chỉ mục màu và thay thế các giá trị pixel bằng chỉ mục của mảng. Màu chuyển đổi lập chỉ mục giúp đạt được điều này. (Đối với WebP không tổn hao, chúng tôi đặc biệt không gọi đây là biến đổi bảng màu bởi vì một biến đổi động tồn tại trong phương thức 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 duy nhất trong hình ảnh. Nếu số đó thấp hơn ngưỡng (256), hệ thống sẽ tạo một mảng gồm 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ả giá trị alpha được đặt thành 255 và tất cả các giá trị màu đỏ và màu xanh lam đượ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 nhập trong màu bảng. 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ảng màu
có thể được lấy bằng cách đọc hình ảnh mà không có tiêu đề RIFF, kích thước hình ảnh và
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á trừ để giảm entropy của hình ảnh. Đồng bằng
màu trong bảng màu thường chứa ít entropy hơn nhiều so với màu
, giúp tiết kiệm đáng kể các hình ảnh nhỏ hơn. Trong quá trình giải mã,
mỗi màu cuối cùng trong bảng màu đều có thể thu được bằng cách thêm màu
các giá trị thành phần màu theo từng thành phần ARGB riêng biệt và lưu trữ ít nhất
đáng kể 8 bit 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 (giá trị này là các chỉ mục vào bảng màu) với giá trị thực tế 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
, 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 ít hơn 16 màu), một vài pixel được nhóm thành một pixel duy nhất. Gói pixel gói một vài (2, 4 hoặc 8) thành một pixel, qua đó giảm chiều rộng của hình ảnh tương ứng. Điểm ảnh tính năng nhóm cho phép mã hoá entropy phân phối chung hiệu quả hơn các pixel lân cận và mang lại một số lợi ích giống như viết mã số học cho entropy, nhưng chỉ có thể sử dụng khi có tối đa 16 giá trị duy nhất.
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ị 0, 1, 2 hoặc 3. Giá trị 0 cho biết không có pixel
cần thực hiện nhóm hình ảnh. Giá trị 1 cho biết rằng 2 pixel
và mỗi pixel có phạm vi [0..15]. Giá trị 2 cho biết rằng
bốn pixel được kết hợp và mỗi pixel có phạm vi [0..3]. Giá trị 3
chỉ ra rằng tám pixel được kết hợp và mỗi pixel có phạm vi [0..1],
tức là 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: Với mọi giá trị x, trong đó x Đồ 0 (mod 2), màu xanh lục giá trị tại x được đặt vào 4 bit có ý nghĩa 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ó nghĩa nhất của giá trị màu xanh lục tại x / 2.width_bits
= 2: Với mọi giá trị x, trong đó x Đồ 0 (mod 4), một màu xanh lục giá trị tại x được đặt vào 2 bit có nghĩa nhỏ nhất của giá trị màu xanh lục tại x / 4 và giá trị màu xanh lục tại x + 1 đến x + 3 được đặt trong số bit có ý nghĩa lớn hơn của giá trị màu xanh lục tại x / 4.width_bits
= 3: Với mọi giá trị x, trong đó x nâng 0 (mod 8), một màu xanh lục giá trị tại x được đặt vào bit nhỏ nhất của màu xanh lục tại x / 8 và giá trị màu xanh lục tại x + 1 đến x + 7 được đặt theo thứ tự đến các bit quan trọng hơn của giá trị màu xanh lục tại x / 8.
Sau khi đọc biến đổi này, image_width
sẽ được width_bits
lấy mẫu con. Chiến dịch này
ảnh hưởng đến kích thước của các biến đổi tiếp theo. Kích thước mới có thể được tính bằng cách sử dụng
DIV_ROUND_UP
, như định nghĩa 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ự đườ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 trong năm 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 "Giải mã mã tiền tố Meta").
- Hình ảnh trình dự đoán: Lưu trữ siêu dữ liệu cho biến đổi công cụ dự đoán (xem "Biến đổi trình dự đoán").
- Hình ảnh biến đổi màu: Do
ColorTransformElement
giá trị tạo ra (được định nghĩa trong "Color Transform") 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 ARGB lưu trữ siêu dữ liệu cho phép biến đổi lập chỉ mục màu (xem "Chuyể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 độc lập với vai trò của nó.
Đầu tiên, hình ảnh được chia thành nhóm các khối có kích thước cố định (thường là 16x16 khối). Mỗi khối trong số này được lập mô hình bằng mã entropy riêng. Ngoài ra, một số khối có thể có cùng mã entropy.
Rationale: Việc lưu trữ mã entropy sẽ làm phát sinh chi phí. Có thể giảm thiểu chi phí này nếu các khối giống nhau về mặt thống kê có chung mã entropy, do đó lưu trữ mã đó một lần. Ví dụ: một bộ mã hoá có thể tìm các khối tương tự bằng cách nhóm các khối đó bằng cách sử dụng các tính chất thống kê hoặc bằng cách liên tục kết hợp các cụm được chọn khi 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 pháp có thể áp dụng:
- Giá trị cố định được mã hoá tiền tố: Mỗi kênh (xanh lục, đỏ, xanh dương và alpha) là entropy được mã hoá 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ột mã băm nhân hàm ngắn (bộ nhớ đệm màu chỉ mục) của màu nhìn thấy gần đây.
Các tiểu mục sau đây sẽ mô tả chi tiết từng trường hợp.
5.2.1 Văn bản được mã hoá tiền tố
Pixel được lưu trữ dưới dạng giá trị được mã hoá bằng tiền tố của màu xanh lục, đỏ, xanh dương và alpha (trong đơn đặt hàng đó). Xem Mục 6.2.3 để biết chi tiết.
5.2.2 Tham chiếu ngược LZ77
Tham chiếu ngược là các bộ dữ liệu về độ dài và mã khoảng cách:
- Độ dài cho biết số lượng pixel trong thứ tự dòng quét được sao chép.
- Mã khoảng cách là một số cho biết vị trí của một mục đã nhìn thấy trước đó. pixel mà từ đó pixel sẽ được sao chép. Việc liên kết chính xác là được mô tả dưới đây.
Các giá trị độ dài và khoảng cách được lưu trữ bằng tính năng mã hoá tiền tố LZ77.
Mã hóa tiền tố LZ77 chia các giá trị số nguyên lớn thành hai phần: 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).
Rationale: Phương pháp này làm giảm yêu cầu lưu trữ đối với entropy . Ngoài ra, các giá trị lớn thường hiếm khi xảy ra, vì vậy các bit bổ sung sẽ được sử dụng cho trong hình ảnh. Do đó, phương pháp này mang lại kết quả nén tốt hơn tổng thể.
Bảng sau biểu thị các mã tiền tố và các bit bổ sung được dùng để lưu trữ các phạm vi giá trị khác nhau.
Phạm vi giá trị | Mã tiền tố | Thông tin 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ị (chiều dài hoặc khoảng cách) từ mã tiền tố là 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;
Bản đồ 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 pixel đã nhìn thấy trước đó mà từ đó pixel đượ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ã trước đó điểm ảnh.
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, được bù trừ bằng 120.
Các mã khoảng cách nhỏ nhất [1..120] là đặc biệt và được dành riêng để đóng vùng lân cận của pixel hiện tại. Vùng lân cận này bao gồm 120 pixel:
- Điểm ảnh cao hơn điểm ảnh hiện tại từ 1 đến 7 hàng và tối đa 8 cột
sang trái hoặc tối đa 7 cột về bên phải của pixel hiện tại. [Tổng số
pixel như vậy =
7 * (8 + 1 + 7) = 112
]. - Pixel ở cùng hàng với pixel hiện tại và có kích thước tối đa là 8
cột ở bên trái pixel hiện tại. [
8
pixel như vậy].
Ánh xạ giữa mã khoảng cách distance_code
và pixel lân cận
độ lệch (xi, yi)
như sau:
(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 (0, 1)
của
pixel lân cận, tức là pixel trên pixel hiện tại (0 pixel
độ chênh lệch về 1 điểm ảnh theo hướng X và 1 điểm ảnh 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 thứ tự đường quét
khoảng cách 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ạ đã nê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 sử dụng gần đây trong hình ảnh.
Rationale: Bằng cách này, các màu được sử dụng gần đây đôi khi được gọi là hiệu quả hơn so với phát chúng sử dụng hai phương pháp 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. Đầu tiên, có giá trị 1 bit cho biết liệu bộ nhớ đệm màu có được sử dụng hay không. Nếu bit này bằng 0 thì không có mã bộ nhớ đệm màu và chúng không được truyền vào mã tiền tố giải mã màu xanh lục và mã tiền tố độ dài. Tuy nhiên, nếu bit này là 1, thì bộ nhớ đệm màu kích thước đượ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 các giá trị được phép cho
color_cache_code_bits
là [1..11]. Bộ giải mã tương thích phải chỉ ra
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 lưu trữ một ARGB
. Các màu được tra cứu bằng cách lập chỉ mục theo (0x1e35a7bd * color) >> (32 -
color_cache_code_bits)
. Chỉ một thao tác tra cứu được thực hiện trong bộ nhớ đệm màu; không có
giải quyết xung đột.
Khi bắt đầu giải mã hoặc mã hoá hình ảnh, tất cả các mục nhập đều có màu được đặt thành 0. Mã bộ nhớ đệm màu được chuyển đổi sang màu này tại thời gian 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, được tạo ra bằng cách tham chiếu ngược hoặc dưới dạng giá trị cố định, vào bộ nhớ đệm trong 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ã được truyền bằng cách gửi độ dài mã tiền tố, dưới dạng khác với mã có tiền tố thực tế.
Cụ thể, định dạng này sử dụng tính năng mã hoá tiền tố biến thể một cách ngẫu nhiên. Trong khu vực khác các từ khác nhau của hình ảnh có thể sử dụng các entropy khác nhau mã.
Rationale: Các vùng 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 các mã này sử dụng các mã entropy khác nhau mang lại sự linh hoạt hơn và 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 một số 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 bất kỳ pixel cho trước nào (x, y), có một bộ năm mã tiền tố được liên kết với nó. Các mã này (theo thứ tự luồng bit):
- Mã tiền tố #1: Dùng cho kênh màu xanh lục, thời lượng tham chiếu ngược và bộ nhớ đệm màu.
- Mã tiền tố #2, #3 và #4: Dùng cho các kênh màu đỏ, xanh dương và alpha, .
- Mã tiền tố #5: Dùng cho khoảng cách tham chiếu ngược.
Từ đây trở đi, chúng tôi gọi nhóm này là nhóm mã có tiền tố.
6.2.1 Giải mã và xây dựng 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 sử dụng đã được chỉ định cho giá trị 1 bit.
- Nếu bit này là 1, thì đó là mã độ dài mã đơn giản.
- Nếu bit này bằng 0 thì đó là mã độ dài mã thông thường.
Trong cả hai trường hợp, có thể vẫn còn độ dài mã chưa dùng đến luồng. Điều này có thể không hiệu quả, nhưng được phép theo định dạng. Cây được mô tả phải là một cây nhị phân hoàn chỉnh. Một nút lá đơn là được coi là một cây nhị phân hoàn chỉnh và có thể được mã hoá bằng cách sử dụng mã độ dài mã hoặc mã độ dài mã thông thường. Khi lập trình một lá đơn nút sử dụng mã độ dài mã thông thường, tất cả trừ một độ dài mã là 0, và giá trị nút một lá được đánh dấu bằng độ dài là 1 -- ngay cả khi không có bit được tiêu thụ khi cây nút một lá đó được sử dụng.
Mã độ 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ã là 1
. Tất cả độ dài mã tiền tố khác là
hoàn toàn là số 0.
Bit đầu tiên cho biết số 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 lần lượt là [0..1] hoặc [0..255]. Thứ hai
ký hiệu, nếu có, luôn được giả định là nằm trong khoảng [0..255] và được mã hoá.
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. Cho phép các ký hiệu trùng lặp, nhưng không hiệu quả.
Lưu ý: Một trường hợp đặc biệt khác là khi tất cả độ dài mã tiền tố là số 0 (
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ó tham chiếu ngược. Tương tự, mã tiền tố cho alpha, đỏ và
màu 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 ra
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ì
có thể lập trình mã tiền tố trống thành mã chứa một ký hiệu 0
duy nhất.
Mã có độ dài mã bình thường
Độ dài mã của mã tiền tố vừa với 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);
Độ dài mã được tự mã hoá bằng mã tiền tố; mã cấp thấp hơn
độ dài, code_length_code_lengths
, trước tiên phải được đọc. Phần còn lại
code_length_code_lengths
(theo đơn đặt hàng trong kCodeLengthCodeOrder
)
là 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 là ReadBits(1) == 0
, số lượng tối đa các ký hiệu đọc khác nhau
(max_symbol
) cho mỗi loại biểu tượng (A, R, G, B và khoảng cách) được đặt thành
kích thước bảng chữ cái:
- Kênh G: 256 + 24 +
color_cache_size
- Các giá trị cố định khác (A, R và B): 256
- Mã khoảng cách: 40
Nếu không, thuộc tính này được định nghĩa 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 đối với loại biểu tượng, giá trị
bitstream 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 toàn bộ
thành max_symbol
độ dài mã.
- Mã [0..15] cho biết độ dài mã bằng chữ.
- Giá trị 0 có nghĩa là chưa có ký hiệu nào được mã hoá.
- Các giá trị [1..15] cho biết độ dài bit của đoạn 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 sử dụng trước một số khác 0 giá trị đã được phát ra, giá trị 8 sẽ được lặp lại. - Mã 17 phát ra một chuỗi các số 0 có độ dài [3..10], tức là
3 + ReadBits(3)
lần. - Mã 18 phát ra một vệt có độ dài bằng 0 [11..138], nghĩa là
11 + ReadBits(7)
lần.
Sau khi đọc độ dài mã, một mã tiền tố cho mỗi loại biểu tượng (A, R, G, B và khoảng cách) được tạo bằng cách sử dụng các kích thước bảng chữ cái tương ứng.
Mã độ dài mã thông thường phải mã hoá 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 là một. Tuy nhiên, có
một ngoại lệ đối với quy tắc này, cây nút lá đơn, trong đó nút lá
giá trị đượ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ã meta tiền tố là chỉ mục xác định các mã tiền tố để sử 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 sử dụng trong vai trò của hình ảnh ARGB.
Có hai khả năng đối với mã tiền tố meta, được biểu thị bằng mã 1 bit giá trị:
- Nếu bit này bằng 0 thì chỉ có một mã tiền tố meta được sử dụng ở mọi nơi trong hình ảnh. Hệ thống sẽ không lưu trữ thêm dữ liệu nào khác.
- Nếu bit này là một bit, hình ảnh sẽ sử dụng nhiều mã tiền tố meta. Các thẻ meta này mã tiền tố được lưu trữ dưới dạng hình ảnh entropy (mô tả dưới đây).
Các thành phần màu đỏ và màu xanh lục của một pixel xác định mã tiền tố meta 16 bit được sử dụng trong một khối cụ thể của hình ảnh ARGB.
Hình ảnh entropy
Ảnh entropy xác định mã tiền tố nào được sử 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 entropy
hình ảnh bắt nguồn 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 ảnh entropy có chiều rộng prefix_image_width
và chiều cao
prefix_image_height
Diễn giải mã tiền tố Meta
Có thể lấy số 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 từ 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
ảnh entropy.
Vì mỗi nhóm mã tiền tố chứa 5 mã tiền tố, nên tổng số tiền tố mã là:
int num_prefix_codes = 5 * num_prefix_groups;
Cho trước một pixel (x, y) trong hình ảnh ARGB, chúng ta có thể nhận được 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 tôi giả định sự tồn tại của cấu trúc PrefixCodeGroup
,
đại diện cho bộ năm 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ử dụng nhóm mã tiền tố prefix_group
để giải mã pixel
(x, y), như được giải thích trong "Giải mã hình ảnh được mã hoá Entropy
"Dữ liệu".
6.2.3 Giải mã dữ liệu ảnh được mã hoá 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ẽ nhận dạng nhóm mã tiền tố tương ứng (như được giải thích trong phần cuối). Do nhóm mã tiền tố, pixel được đọc và giải mã như sau.
Tiếp theo, đọc ký hiệu S từ luồng bit sử dụng mã tiền tố #1. Lưu ý rằng S là
bất kỳ số nguyên nào trong phạm vi từ 0
đến
(256 + 24 +
color_cache_size
- 1)
.
Việc diễn giải S phụ thuộc vào giá trị của nó:
- 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ố #2.
- Đọc màu xanh dương từ luồng bit bằng mã tiền tố #3.
- Đọc giá trị alpha từ luồng bit bằng mã tiền tố #4.
- Nếu S >= 256 & S < 256 + 24
- Sử dụng S – 256 làm mã tiền tố độ dài.
- Đọc thêm bit 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 bit bổ sung.
- Đọc mã tiền tố khoảng cách từ luồng bit bằng mã tiền tố #5.
- Đọc thêm bit về 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 sẽ đọc.
- Sao chép L pixel (theo thứ tự dòng quét) từ chuỗi pixel bắt đầu ở vị trí hiện tại trừ đi pixel D.
- Nếu S >= 256 + 24
- Sử dụng S - (256 + 24) làm chỉ mục vào 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à một chế độ xem sang định dạng A thêm Backus-Naur Form (ABNF) RFC 5234 RFC 7405. Bài viết này không bao gồm mọi chi tiết. Phần cuối của hình ảnh (EOI) chỉ được mã hoá ngầm thành số pixel (image_width * image_height).
Xin lưu ý rằng *element
có nghĩa là element
có thể lặp lại từ 0 lần trở lên. 5element
có nghĩa là element
được lặp lại chính xác 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 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 chuỗi ví dụ có thể có:
RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image