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

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 các byte đó và các bit của mỗi byte được đọc theo thứ tự bit có giá trị ít quan trọng nhất trước. 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. Hình ảnh WebP không suy hao có thể trải qua 4 loại phép 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 phép biến đổi nghịch đảo tương ứng.

2 Danh pháp

ARGB

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 chuyể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:

1. Chuỗi "RIFF".
2. 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ị đó).
3. Chuỗi 'WEBP' (tên vùng chứa RIFF).
4. Chuỗi "VP8L" (Bốn CC cho dữ liệu hình ảnh được mã hoá không tổn hao).
5. Một giá trị nhỏ-endian 32 bit của số byte trong vùng 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 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ã. 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 nếu không.

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

Các phép biến đổi là các thao tác có thể đảo ngược đối với dữ liệu hình ảnh, có thể làm giảm entropi biểu tượ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 giá trị này có thể làm cho quá trình nén cuối cùng trở nên dày đặc 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, kể cả bit 0 biểu thị điểm kết thúc của phép 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 chuyển đổi có thể được quyết định 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ó 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ự như mô tả trong Chương 5.

Số lượng cột khối, transform_width, được dùng trong việc lập chỉ mục hai chiều. Đố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) 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 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	Average2(L, TL)
7	Trung bình 2(B; T)
8	Trung bình2(TL; T)
9	Average2(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 xác định như sau cho từng thành phần ARGB:

uint8 Average2(uint8 a, uint8 b) {
  return (a + b) / 2;
}

Phương pháp dự đoán 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. Để 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;

Bạn có thể thực hiện phép biến đổi màu thực tế bằng cách xác định delta biế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à trong những bit này, dịch chuyển tiện ích dấu 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 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;
}

Biến đổi này là thừa vì có thể được mô hình hoá bằng cách sử dụng biến đổi màu, nhưng vì không có dữ liệu bổ sung nào ở đây, nên biến đổi trừ màu xanh lục có thể được mã hoá bằng ít bit hơn so với biến đổi màu đầy đủ.

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. Biến đổi lập chỉ mục màu sắc sẽ giúp bạn thực hiện việc 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 chuyể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ã, bạn có thể lấy mọi màu cuối cùng trong bảng màu bằng cách thêm riêng các giá trị thành phần màu trước đó theo từng thành phần ARGB 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 (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, 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 í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ố 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 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ị xanh lục tại x được đặt vào 4 bit có giá trị ít quan trọng nhất của giá trị xanh lục tại x / 2 và giá trị xanh lục tại x + 1 được đặt vào 4 bit có giá trị quan trọng nhất của giá trị xanh lục tại x / 2.
• width_bits = 2: Với mọi giá trị x, trong đó x nâng 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 theo 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 "Giải mã mã tiền tố Meta").
3. 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").
4. 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.
5. 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 độ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 mô hình hoá 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í. Bạn có thể giảm thiểu chi phí này nếu các khối tương tự về mặt thống kê chia sẻ một mã entropy, nhờ đó chỉ 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:

1. 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.
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 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 đượ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, còn 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 làm giảm yêu cầu về bộ nhớ cho mã entropy. Ngoài ra, các giá trị lớn thường hiếm khi xuất hiện, 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 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.

Lưu ý: Độ dài tham chiếu ngược tối đa 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 các giá trị chiều 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ô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ố 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ã 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 cho một vùng lân cận gầ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].
• Các pixel nằm trong cùng hàng với pixel hiện tại và 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à 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 độ dời (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 thứ tự quét dòng 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ố, thay vì mã 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. 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.

Rationale: Các vùng khác nhau của hình ảnh có thể có các đặc điểm khác nhau. Do đó, việc cho phép các thuật toán này sử dụng nhiều mã entropy sẽ 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 đã 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 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 là (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 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, chúng ta gọi tập hợp 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 sử dụng được chỉ định bằng 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à 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 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ý tự tiền tố nằm trong phạm vi [0..255] với độ dài mã 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 cách sử dụ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ác mã tiền tố trống có thể được mã hoá dưới dạng các mã chứa một ký hiệu 0.

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, giá trị này đượ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 ký hiệu, 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 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ã Chiều dài mã thông thường phải mã hoá một cây quyết định đầy đủ, tức là tổng 2 ^ (-length) cho tất cả mã không bằng 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 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 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 mã tiền tố siêu dữ liệu 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 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

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 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.

Giải thích 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;

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 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). Với 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ó:

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 mã tiền tố #2.
   3. Đọc màu xanh dương từ luồng bit bằng mã tiền tố #3.
   4. Đọc giá trị alpha từ luồng bit bằ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 từ luồng bit.
   3. Xác định độ dài tham chiếu ngược L từ mã tiền tố độ dài và đọc bit bổ sung.
   4. Đọc mã tiền tố khoảng cách từ luồng bit bằng mã tiền tố #5.
   5. Đọc thêm bit về 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 bổ sung sẽ đọc.
   7. 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.
3. Nếu S >= 256 + 24
   1. Sử dụng S – (256 + 24) làm chỉ mục vào bộ nhớ đệm màu.
   2. 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. Tài liệu này không bao gồm tất cả 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ố 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 trình 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