Thông số kỹ thuật cho luồng Bit không hao tổn WebP

Tiến sĩ Jyrki Alakuijala, Google, Inc., 2023-03-09

Bản tóm tắt

WebP không tổn hao là một định dạng hình ảnh dùng để nén hình ảnh ARGB mà không tổn hao. Đị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ả các giá trị màu cho các pixel hoàn toàn trong suốt. Một thuật toán chung để 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 minh hoạ, cũng như khả năng nén mật độ cao hơn 25% so với định dạng PNG hiện nay.

1 Giới thiệu

Tài liệu này mô tả cách trình bày dữ liệu nén của hình ảnh không tổn hao bằng WebP. Tệp này dùng làm tài liệu tham khảo chi tiết cho việc triển khai bộ mã hoá không tổn hao và bộ giải mã 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 rằng có 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 các byte đó và các bit của mỗi byte được đọc theo thứ tự bit đầu tiên có tầm quan trọng ít nhất. Khi 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. 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 gốc. Do đó, câu lệnh

b = ReadBits(2);

sẽ tương đương với 2 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 (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 kiểu tương ứng là uint8. Một pixel ARGB toàn bộ được biểu thị bằng một loại có tên là uint32, là một số nguyên chưa ký gồm 32 bit. Trong mã hiển thị hành vi của các phép biến đổi, các giá trị này được mã hoá ở các bit sau: alpha trong bit 31..24, màu đỏ trong bit 23..16, màu xanh lục ở bit 15..8 và màu xanh dương ở bit 7..0; tuy nhiên, việc triển khai định dạng này có thể tự do sử dụng một cách biểu diễn khác trong nội bộ.

Nói rộng ra, hình ảnh không tổn hao WebP chứa dữ liệu tiêu đề, thông tin chuyể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 tổn 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 hiệu

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 sử dụng gần đây, nhờ đó có thể gọi lại bằng mã ngắn hơn.

hình ảnh lập chỉ mục màu

Hình ảnh một chiều có các màu có thể được lập chỉ mục bằng cách sử dụng một số nguyên nhỏ (tối đa 256 trong WebP không tổn hao).

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 sắc.

ánh xạ khoảng cách

Thay đổi khoảng cách LZ77 để có các giá trị nhỏ nhất cho các pixel trong độ gần hai chiều.

hình ảnh entropy

Hình ảnh có độ phân giải phụ hai chiều cho biết phương thức lập trình entropy nào sẽ được dùng 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 biểu tượng 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) lập chỉ mục một phần tử trong bảng tiền tố meta.

hình ảnh dự đoán

Một hình ảnh có độ phân giải phụ hai chiều cho biết thông số dự đoán không gian nào được dùng cho một hình vuông cụ thể trong hình ảnh.

mã tiền tố

Là cách cổ điển để mã hoá entropy, trong đó, số lượng bit nhỏ hơn đượ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 các số nguyên lớn hơn, mã 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. Điều này cho phép nội dung mô tả các mã entropy vẫn tương đối nhỏ ngay cả khi phạm vi ký hiệu lớn.

thứ tự dòng quét

Thứ tự xử lý pixel (từ trái sang phải và 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 Tiêu đề RIFF

Phần đầu của tiêu đề có vùng chứa RIFF. Tệp này bao gồm 21 byte sau:

1. Chuỗi 'RIFF'.
2. Giá trị 32 bit của phân đoạn cuối nhỏ, tức là toàn bộ kích thước của phân đ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ừ 8 byte: 4 byte cho giá trị nhận dạng "RIFF" và 4 byte để lưu trữ chính giá trị đó).
3. Chuỗi 'WEBP' (tên vùng chứa RIFF).
4. Chuỗi "VP8L" (FourCC đối với dữ liệu hình ảnh được mã hoá không tổn hao).
5. Một giá trị 32 bit cuối nhỏ của số byte trong luồng không tổn hao.
6. 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 một hình ảnh không tổn hao ở định dạng WebP ở 16384x16384 pixel.

Bit alpha_is_used chỉ là một gợi ý và không ảnh hưởng đến quá trình giải mã. Giá trị này phải được đặt là 0 khi tất cả các giá trị alpha là 255 trong hình và 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 nên được coi là lỗi.

int version_number = ReadBits(3);

4 phép biến đổi

Phép biến đổi là các 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 lập mô hình mối tương quan không gian và màu sắc. Các tệp này có thể giúp quá trình nén cuối cùng dày đặc hơn.

Một hình ảnh có thể trải qua bốn loại biến đổi. Giá trị 1 bit cho biết sự hiện diện của phép biến đổi. Mỗi phép 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; 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, thậm chí không phải bit 0 cho biết kết thúc quá trình 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 còn lại. Ngoài ra, dữ liệu biến đổi có thể được quyết định dựa trên mứ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ó biến đổi, thì 2 bit tiếp theo sẽ chỉ định loại 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 đứng trước 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. Phép biến đổi nghịch đảo được áp dụng theo thứ tự đảo ngược mà chúng được đọc từ luồng bit, tức là biến đổi cuối cùng trước tiên.

Tiếp theo, chúng tôi mô tả dữ liệu biến đổi cho các loại khác nhau.

4.1 Biến đổi công cụ dự đoán

Bạn có thể dùng phép biến đổi dự đoán để giảm entropy bằng cách khai thác dữ kiện rằng các pixel lân cận thường có tương quan. Trong 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ã (theo thứ tự dòng quét) và chỉ giá trị còn lại (thực tế – dự đoán) được mã hoá. Thành phần màu xanh lục của pixel xác định thành phần nào trong số 14 công cụ 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 tôi chia hình ảnh thành các hình vuông và tất cả các pixel trong hình 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 tính bằng 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. Đây 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 trong số 14 công cụ dự đoán được dùng cho tất 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 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 quá trình lập chỉ mục hai chiều. Đối với pixel (x, y), người dùng có thể tính toán địa chỉ khối bộ lọc tương ứng theo:

int block_index = (y >> size_bits) * transform_width +
                  (x >> size_bits);

Có 14 chế độ dự đoán khác nhau. 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 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 điểm dự đoán giá trị cho P, tất cả các pixel O, TL, T, TR và L đều đã được xử lý, đồng thời pixel P và tất cả các pixel X là không xác định.

Dựa trên 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 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	TL
5	Trung bình2(Trung bình2(L, TR), T)
6	Trung bình 2(L, TĐ)
7	Trung bình2(L, 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;
}

Chọn yếu tố 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 cho một số pixel đường viền. Nếu có sự biến đổi dự đoán, bất kể chế độ [0..13] cho các pixel này là gì, thì 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 đều là L-pixel và tất cả các pixel trên cột ngoài cùng bên trái đều là T-pixel.

Việc xử lý pixel TR cho các pixel trên cột ngoài cùng bên phải là điều đặ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, nhưng 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 sử dụng làm pixel TR.

Giá trị pixel cuối cùng nhận được bằng cách thêm từng kênh của giá trị dự đoán vào 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 Chuyể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 từng pixel. Phép biến đổi màu giữ nguyên giá trị màu xanh lục (G) như hiện tại, chuyển đổi giá trị màu đỏ (R) dựa trên giá trị màu xanh lục và chuyển đổi giá trị màu xanh dương (B) dựa trên giá trị màu xanh lục rồi dựa trên giá trị màu đỏ.

Tương tự như trường hợp biến đổi trình 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 sử dụng cho tất cả pixel trong một khối. Đối với 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;

Phép 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. delta chuyển đổi màu phụ thuộc vào ColorTransformElement, giống nhau đối với tất cả các pixel trong một khối cụ thể. delta bị trừ trong quá trình biến đổi màu. Sau đó, phép biến đổi màu 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 số nguyên 8 bit đã ký biểu thị số điểm cố định 3,5 và kênh màu RGB 8 bit đã ký (c) [-128..127] và được xác định như sau:

int8 ColorTransformDelta(int8 t, int8 c) {
  return (t * c) >> 5;
}

Bạn cần chuyển đổi từ cách biểu diễn 8 bit không có chữ ký (uint8) sang phiên bản 8 bit có dấu (int8) trước khi gọi ColorTransformDelta(). Giá trị đã ký phải được hiểu là số bổ sung 8 bit của 2 (nghĩa là phạm vi uint8 [128..255] được ánh xạ tới phạm vi [-128..-1] của giá trị int8 được chuyển đổi).

Phép nhân phải được thực hiện với độ chính xác cao hơn (với độ chính xác tối thiểu là 16 bit). Thuộc tính mở rộng dấu của thao tác chuyển đổi không quan trọng ở đây; chỉ sử dụng 8 bit thấp nhất từ kết quả. Ở đó, việc dịch chuyển mở rộng dấu và dịch chuyển không có chữ ký nhất quán với nhau.

Bây giờ, chúng ta sẽ 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 đảo ngược 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 chuyể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ụ có 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 dương là cte.green_to_red.

Trong quá trình giải mã, bản sao ColorTransformElement của các khối được giải mã và phép biến đổi màu nghịch đảo được áp dụng trên các giá trị ARGB của các pixel. Như đã đề cập trước đó, phép biến đổi màu nghịch đảo chỉ thêm giá trị ColorTransformElement vào các kênh màu đỏ và màu xanh dương. Các kênh alpha và màu xanh lục sẽ được 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ừ đi chuyển đổi màu xanh lục

Phép biến đổi màu xanh lục trừ đi các giá trị màu xanh lục từ các giá trị màu đỏ và màu xanh dương của mỗi pixel. Khi có sự 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 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à không cần thiết vì nó có thể được lập mô hình bằng cách sử dụng phép biến đổi màu, nhưng vì không có thêm dữ liệu ở đây, nên phép biến đổi trừ màu xanh lục có thể được mã hoá bằng cách sử dụng ít bit hơn so với phép 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ột mảng chỉ mục màu và thay thế các giá trị pixel bằng các chỉ mục của mảng có thể sẽ hiệu quả hơn. Sự biến đổi lập chỉ mục màu sắc đạt được điều này. (Trong trường hợp WebP không mất dữ liệu, chúng tôi đặc biệt không gọi đây là biến đổi bảng màu vì một khái niệm tương tự nhưng linh động hơn tồn tại trong phương thức mã hoá WebP không tổn hao: bộ nhớ đệm màu.)

Phép biến đổi lập chỉ mục màu 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), thì hệ thống 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 pixel được thay thế bằng chỉ mục, tất cả các giá trị alpha được đặt thành 255, còn tất cả các giá trị màu đỏ và xanh dương 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 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 cách sử dụ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 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á bằ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 entropy thấp hơn nhiều so với chính các màu đó, giúp tiết kiệm đáng kể đối với các hình ảnh nhỏ hơn. Trong quá trình giải mã, bạn có thể lấy được mọi màu cuối cùng trong bảng màu bằng cách thêm các giá trị thành phần màu trước đó theo từng thành phần ARGB một cách 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 ngược cho hình ảnh chỉ đơn giản là thay thế các giá trị pixel (là các chỉ mục cho bảng màu) bằng các 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, thì bạn phải đặt giá trị màu của argb thành 0x00000000 (màu đen trong suốt).

Khi bảng màu có kích thước nhỏ (bằng hoặc ít hơn 16 màu), một số pixel được nhóm thành một pixel duy nhất. Tính năng gói pixel sẽ gói nhiều pixel (2, 4 hoặc 8) thành một pixel duy nhất, giúp giảm chiều rộng hình ảnh tương ứng. Tính năng nhóm pixel cho phép mã hoá entropy phân phối kết hợp 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ư lập trình 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 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ần thực hiện nhóm pixel cho hình ảnh. Giá trị 1 cho biết hai pixel được kết hợp và mỗi pixel có phạm vi là [0..15]. Giá trị 2 cho biết bốn pixel được kết hợp và mỗi pixel có phạm vi là [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 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 Lyft 0 (mô-đun 2), giá trị màu xanh lục 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 ở 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: Đối với mọi giá trị x, trong đó x = 0 (mô-đun 4), một giá trị màu xanh lục 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à các giá trị màu xanh lục tại x + 1 đến x + 3 được đặt theo thứ tự các bit có ý nghĩa 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 Lyft 0 (mô-đun 8), giá trị màu xanh lục tại x được đặt vào bit có ý nghĩa nhỏ nhất của giá trị 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ự các bit quan trọng 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 con bằng 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 trong 5 vai trò khác nhau:

1. Hình ảnh ARGB: Lưu trữ các pixel thực tế của hình ảnh.
2. Hình ảnh entropy: Lưu trữ mã tiền tố meta (xem phần "Giải mã mã tiền tố meta").
3. Hình ảnh công cụ dự đoán: Lưu trữ siêu dữ liệu cho phép biến đổi công cụ dự đoán (xem "Chuyển đổi công cụ dự đoán").
4. Hình ảnh biến đổi màu: Do các giá trị ColorTransformElement tạo (được xác định trong "Biến đổi màu") cho các khối hình ảnh khác nhau.
5. Hình ảnh lập chỉ mục màu: Một mảng kích thước color_table_size (tối đa 256 giá trị ARGB) lưu trữ siêu dữ liệu cho 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ó.

Trước 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 trong số này được lập mô hình bằng mã entropy riêng. Ngoài ra, một vài 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í. Bạn có thể giảm thiểu chi phí này nếu các khối tương tự nhau về mặt thống kê dùng chung một mã entropy, do đó, chỉ lưu trữ mã đó một lần. Ví dụ: một bộ mã hoá có thể tìm thấy các khối tương tự bằng cách phân cụm bằng các thuộc tính thống kê hoặc bằng cách liên tục tham gia một cặp cụm được chọn ngẫu nhiên khi làm 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ể có:

1. Hằng số được mã hoá bằng tiền tố: Mỗi kênh (xanh lục, đỏ, xanh dương và alpha) được mã hoá entropy một cách độc lập.
2. Tham chiếu ngược LZ77: Một chuỗi pixel được sao chép từ nơi khác trong hình ảnh.
3. Mã bộ nhớ đệm màu: Sử dụng một mã băm ngắn nhân lên (chỉ mục bộ nhớ đệm màu) của một màu đã thấy gần đây.

Các tiểu mục sau đây sẽ mô tả chi tiết từng yếu tố này.

5.2.1 Nguyên văn mã hoá theo tiền tố

Pixel được lưu trữ dưới dạng các giá trị được mã hoá bằng tiền tố xanh lục, đỏ, xanh lam và alpha (theo thứ tự đó). 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ộ dữ liệu độ dài và mã khoảng cách:

• Độ 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 đó, mà từ đó các pixel sẽ được sao chép. Việc ánh xạ chính xác được mô tả dưới đây.

Giá trị độ dài và khoảng cách được lưu trữ bằng mã hoá tiền tố LZ77.

Việc 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).

Rationale: Phương pháp này làm 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 rất hiếm, vì vậy, các bit bổ sung sẽ được sử dụng cho rất ít giá trị trong hình ảnh. Do đó, phương pháp này giúp nén tốt hơn về tổng thể.

Bảng sau đây biểu thị các mã tiền tố và các bit bổ sung dùng để lưu trữ các phạm vi giá trị khác nhau.

Lưu ý: Độ dài tham chiếu ngược tối đa được giới hạn ở 4096. Do đó, chỉ 24 mã tiền tố đầu tiên (với các bit bổ sung tương ứng) mới có ý nghĩa đối với giá trị độ dài. Tuy nhiên, đối với giá trị khoảng cách, tất cả 40 mã tiền tố đều hợp lệ.

Phạm vi giá trị	Mã tiền tố	Thêm bit
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ả để nhận 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;

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 một pixel đã thấy trước đó, mà 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 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ù trừ bằng 120.

Mã khoảng cách nhỏ nhất [1..120] là mã đặc biệt và dành riêng cho 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:

• Các pixel có 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 của pixel hiện tại. [Tổng số pixel như vậy = 7 * (8 + 1 + 7) = 112].
• Các pixel ở 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. [8 pixel như vậy].

Ánh xạ giữa mã khoảng cách distance_code và phần bù trừ pixel lân cận (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 phía trên pixel hiện tại (sự khác biệt 0 pixel theo hướng X và 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 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à mục á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 tập hợp các màu được sử dụng gần đây trong hình ảnh.

Rationale: Bằng cách này, đôi khi các màu được sử dụng gần đây đôi khi có thể được đề cập hiệu quả hơn so với việc phát các màu đó bằng 2 phương thức khác (như 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ó một 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ì sẽ không có mã bộ nhớ đệm màu nào tồn tại, đồng thời các mã này không được truyền trong mã tiền tố để giải mã 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 các giá trị được phép cho color_cache_code_bits là [1..11]. Bộ giải mã tuân thủ 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 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 chúng bằng (0x1e35a7bd * color) >> (32 - color_cache_code_bits). Chỉ một lần 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 nhập trong tất cả giá trị bộ nhớ đệm 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 đ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 (có thể được tạo bằng cách tham chiếu ngược hoặc dưới dạng giá trị cố định) 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ố chính tắc. Do đó, mã được truyền bằng cách gửi độ dài mã tiền tố, chứ không phải mã tiền tố thực tế.

Cụ thể, định dạng này sử dụng mã hoá tiền tố biến thể theo không gian. Nói cách khác, các khối hình ảnh khác nhau có thể sử dụng các mã entropy khác nhau.

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 nhiều mã entropy 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 đã mã hoá bao gồm một số phần:

1. Giải mã và tạo mã tiền tố.
2. Mã tiền tố meta.
3. Dữ liệu hình ảnh được mã hoá entropy.

Đối với một pixel bất kỳ (x, y), có một bộ mã tiền tố liên kết với pixel đó. Các mã sau (theo thứ tự luồng bit):

• Mã tiền tố #1: Dùng cho kênh màu xanh lục, độ dài tham chiếu ngược và bộ nhớ đệm màu.
• Mã tiền tố #2, #3 và #4: Dùng tương ứng cho các kênh đỏ, 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 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.

Có thể mã hoá độ dài của mã tiền tố theo hai cách. Phương thức sử dụng được chỉ định bởi một giá trị 1 bit.

• Nếu bit này là 1 thì đó là một 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ó các độ dài mã chưa sử dụng nhưng vẫn nằm trong luồng. Điều 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à một cây nhị phân hoàn chỉnh. Nút lá đơn được coi là một cây nhị phân hoàn chỉnh 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á đơn bằng mã độ dài mã thông thường, tất cả trừ một độ dài mã đều bằng 0 và giá trị của nút lá đơn đượ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á đơn đó đượ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ố nằm trong khoảng [0..255] với độ dài mã là 1. Tất cả các độ dài mã tiền tố khác đều ngầm ẩn bằng 0.

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 đượ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]. Ký hiệu thứ hai (nếu có) luôn được giả định là nằm trong phạm vi [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 ký hiệu này phải khác nhau. Chúng tôi chấp nhận 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ố đều là số 0 (một 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à 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 phải 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 ký hiệu 0 duy nhất.

Mã độ dài mã thông thường

Độ dài mã của mã tiền tố tính bằng 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 mã hoá bằng mã tiền tố; độ dài mã cấp thấp hơn, code_length_code_lengths, trước tiên phải được đọc. 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 là ReadBits(1) == 0, số ký hiệu đọc khác nhau tối đa (max_symbol) đối với mỗi loại biểu tượng (A, R, G, B và khoảng cách) sẽ đượ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, dữ liệu đó sẽ đượ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 đối với 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ã cố định.
  • Giá trị 0 có nghĩa là chưa 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 bạn dùng mã 16 trước khi phát một giá trị khác 0, thì giá trị 8 sẽ được lặp lại.
• Mã 17 phát ra một chuỗi 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 độ dài mã được đọc, mã tiền tố cho từng loại biểu tượng (A, R, G, B và khoảng cách) sẽ được tạo dựa trên kích thước bảng chữ cái tương ứng.

Mã độ dài mã thông thường phải lập trình cho cây quyết định đầy đủ, nghĩa là tổng 2 ^ (-length) của tất cả các mã khác 0 phải bằng 1. Tuy nhiên, có một ngoại lệ đối với quy tắc này là cây nút lá đơn, trong đó giá trị của 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ố nào cần 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 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 giá trị 1 bit:

• 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 không lưu trữ thêm dữ liệu nào.
• Nếu bit này là 1, 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 (như mô tả bên dưới).

Các thành phần màu đỏ và màu xanh lục của 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 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 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 định nghĩa trước đó.

Các bit tiếp theo chứa hình ả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

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) là 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 mã tiền tố tương ứng để 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 một tập hợp 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 phần "Giải mã Dữ liệu hình ảnh được mã hoá bằng entropy".

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ẽ xác định nhóm mã tiền tố tương ứng (như giải thích trong phần trước). 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 bằng cách sử dụng mã tiền tố #1. Lưu ý rằng S là số nguyên bất kỳ trong khoảng 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ó:

1. Nếu S < 256
   1. Sử dụng S làm thành phần màu xanh lục.
   2. Đọc màu đỏ từ luồng bit bằng cách sử dụng mã tiền tố #2.
   3. Đọc dữ liệu màu xanh dương từ luồng bit bằng cách sử dụng mã tiền tố #3.
   4. Đọc giá trị alpha từ luồng bit bằng cách sử dụng mã tiền tố #4.
2. Nếu S >= 256 & S < 256 + 24
   1. Sử dụng S – 256 làm mã tiền tố độ dài.
   2. Đọc các bit bổ sung cho độ dài của luồng bit.
   3. 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.
   4. Đọc mã tiền tố khoảng cách từ luồng bit bằng mã tiền tố #5.
   5. Đọc các bit bổ sung để biết khoảng cách từ luồng bit.
   6. 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 thừa đọc được.
   7. 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 pixel D.
3. Nếu S >= 256 + 24
   1. Sử dụng S – (256 + 24) làm chỉ mục trong bộ nhớ đệm màu.
   2. Nhận 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à hình ảnh về định dạng trong ATăng cường Backus-Naur Biểu mẫu (ABNF) RFC 5234 RFC 7405. Thông tin này không bao gồm mọi chi tiết. Cuối 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à bạn có thể lặp lại element từ 0 lần trở 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 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 trình tự 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