WebP 无损比特流规范

Jyrki Alakuijala 博士，Google, Inc.、2023-03-09

摘要

WebP 无损是一种图片格式，用于对 ARGB 图片进行无损压缩。无损格式可精确存储和恢复像素值，包括完全透明像素的颜色值。使用用于顺序数据压缩 (LZ77) 的通用算法、前缀编码和颜色缓存来压缩批量数据。WebP 的解码速度比 PNG 快，并且压缩密度比当前 PNG 格式高 25%。

1 简介

本文档介绍了 WebP 无损图片的压缩数据表示形式。它旨在为 WebP 无损编码器和解码器实现提供详细参考。

在本文档中，我们广泛使用 C 编程语言语法来描述位流，并假设存在一个用于读取位的函数 ReadBits(n)。字节按包含它们的流的自然顺序读取，每个字节的位按最低有效位优先的顺序读取。如果同时读取多个位，则会按原始顺序根据原始数据构建整数。返回的整数的最高有效位也是原始数据的最高有效位。因此，以下陈述

b = ReadBits(2);

相当于以下两个语句：

b = ReadBits(1);
b |= ReadBits(1) << 1;

我们假设每个颜色分量（即 Alpha、红色、蓝色和绿色）都使用 8 位字节表示。我们将相应类型定义为 uint8。整个 ARGB 像素由名为 uint32 的类型表示，该类型是一个由 32 位组成的无符号整数。在显示转换行为的代码中，这些值以以下位进行编码：alpha 为 31..24 位，红色为 23..16 位，绿色为 15..8 位，蓝色为 7..0 位；不过，格式的实现可以自由地在内部使用其他表示形式。

从广义上讲，无损 WebP 图片包含标头数据、转换信息和实际图片数据。标头包含图片的宽度和高度。WebP 无损图片在进行熵编码之前，可以经历四种不同类型的转换。比特流中的转换信息包含应用相应逆转换所需的数据。

2 命名惯例

ARGB

包含 Alpha、红色、绿色和蓝色值的像素值。

ARGB 图片

包含 ARGB 像素的二维数组。

颜色缓存

一个小型哈希寻址数组，用于存储最近使用的颜色，以便能够使用较短的代码回忆起这些颜色。

颜色索引图片

一种颜色的一维图像，可以使用小整数（在 WebP 无损压缩中最多为 256）进行索引。

颜色转换图片

一种包含颜色分量相关性数据的二维子分辨率图像。

距离映射

更改 LZ77 距离，使二维邻近度中的像素具有最小值。

熵图像

一种二维子分辨率图像，用于指示应在图像中的相应方块中使用哪种熵编码，也就是说，每个像素都是元前缀代码。

LZ77

一种基于字典的滑动窗口压缩算法，可发出符号或将符号描述为过去的符号序列。

元前缀代码

一个用于为元前缀表中的元素编制索引的小整数（最多 16 位）。

预测器图片

一种二维子分辨率图像，用于指示图像中特定正方形所用的空间预测器。

前缀代码

一种经典的熵编码方法，使用较少的位来表示出现频率较高的代码。

前缀编码

一种对较大整数进行熵编码的方法，该方法使用熵编码对整数的几个位进行编码，并对剩余的位进行原始编码。这样一来，即使符号范围很大，熵编码的说明也能保持相对较小的规模。

扫描线顺序

像素的处理顺序（从左到右、从上到下），从左上角的像素开始。完成一行后，请从下一行的左侧列继续。

3 RIFF 标头

标头的开头是 RIFF 容器。这包括以下 21 个字节：

1. 字符串“RIFF”。
2. 块长度的小端序 32 位值，即由 RIFF 标头控制的块的总大小。通常，此值等于载荷大小（文件大小减去 8 字节：4 字节用于 'RIFF' 标识符，4 字节用于存储值本身）。
3. 字符串“WEBP”（RIFF 容器名称）。
4. 字符串“VP8L”（无损编码的图片数据的 FourCC）。
5. 无损流中的字节数（小端序 32 位值）。
6. 1 字节签名 0x2f。

比特流的前 28 位指定了图片的宽度和高度。宽度和高度会解码为 14 位整数，如下所示：

int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;

图片宽度和高度的 14 位精度将 WebP 无损图片的最大尺寸限制为 16384x16384 像素。

alpha_is_used 位仅为提示，不应影响解码。如果图片中的所有 Alpha 值均为 255，则应将其设置为 0；否则，应将其设置为 1。

int alpha_is_used = ReadBits(1);

version_number 是一个 3 位代码，必须设置为 0。任何其他值都应被视为错误。

int version_number = ReadBits(3);

4 种转换

这些转换是对图片数据的可逆操作，可通过对空间和颜色相关性进行建模来减少剩余的符号熵。它们可以使最终压缩更加密集。

图片可以进行四种类型的转换。1 位表示存在转换。每种转换只能使用一次。转换仅用于主级 ARGB 图像；子分辨率图像（颜色转换图像、熵图像和预测器图像）没有转换，甚至没有指示转换结束的 0 位。

通常，编码器会使用这些转换来降低残差图像中的香农熵。此外，还可以根据熵最小化来确定转换数据。

while (ReadBits(1)) {  // Transform present.
  // Decode transform type.
  enum TransformType transform_type = ReadBits(2);
  // Decode transform data.
  ...
}

// Decode actual image data (Section 5).

如果存在转换，则接下来的两位用于指定转换类型。 转换有四种类型。

enum TransformType {
  PREDICTOR_TRANSFORM             = 0,
  COLOR_TRANSFORM                 = 1,
  SUBTRACT_GREEN_TRANSFORM        = 2,
  COLOR_INDEXING_TRANSFORM        = 3,
};

转换类型后紧跟转换数据。转换数据包含应用逆转换所需的信息，具体取决于转换类型。逆转换的应用顺序与从比特流中读取的顺序相反，即先应用最后一个。

接下来，我们将介绍不同类型的数据转换。

4.1 预测变量转换

预测器转换可用于利用相邻像素通常相关这一事实来减少熵。在预测器转换中，当前像素值根据已解码的像素（按扫描线顺序）进行预测，并且仅对残差值（实际值 - 预测值）进行编码。像素的绿色分量用于定义在 ARGB 图像的特定块中使用 14 个预测器中的哪一个。预测模式用于确定要使用的预测类型。我们将图片划分为正方形，并且正方形中的所有像素都使用相同的预测模式。

预测数据的前 3 位用于定义块宽度和高度（以位为单位）。

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);

转换数据包含图像中每个块的预测模式。它是一种子分辨率图像，其中像素的绿色分量用于定义 14 个预测器中的哪一个用于 ARGB 图像特定块中的所有 block_width * block_height 像素。此子分辨率图像采用与第 5 章中所述相同的技术进行编码。

块列数 transform_width 用于二维索引。对于像素 (x, y)，可以通过以下方式计算相应的过滤块地址：

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

共有 14 种不同的预测模式。在每种预测模式下，当前像素值都是根据一个或多个值已知的相邻像素预测的。

我们选择当前像素 (P) 的相邻像素（TL、T、TR 和 L），如下所示：

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

其中，TL 表示左上角，T 表示顶部，TR 表示右上角，L 表示左侧。在预测 P 的值时，所有 O、TL、T、TR 和 L 像素都已处理完毕，而 P 像素和所有 X 像素都是未知的。

根据上述相邻像素，不同的预测模式定义如下。

对于每个 ARGB 分量，Average2 的定义如下：

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

选择预测器的定义如下：

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;
  }
}

系统会针对每个 ARGB 分量执行函数 ClampAddSubtractFull 和 ClampAddSubtractHalf，如下所示：

// 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);
}

对于某些边界像素，有特殊的处理规则。如果存在预测器转换，无论这些像素的模式 [0..13] 如何，图像最左上角像素的预测值都是 0xff000000，顶行上的所有像素都是 L 像素，最左列上的所有像素都是 T 像素。

处理最右侧列中像素的 TR-pixel 是例外情况。最右侧列上的像素使用模式 [0..13] 进行预测，就像非边界像素一样，但同一行上最左侧的像素会用作 TR 像素。

通过将预测值的每个通道添加到编码的残差值中，即可获得最终的像素值。

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 色彩转换

颜色转换的目标是去除每个像素的 R、G 和 B 值之间的相关性。颜色转换会保持绿色 (G) 值不变，根据绿色值转换红色 (R) 值，并根据绿色值和红色值转换蓝色 (B) 值。

与预测器转换一样，首先将图片划分为多个块，然后对一个块中的所有像素使用相同的转换模式。对于每个块，有三种类型的颜色转换元素。

typedef struct {
  uint8 green_to_red;
  uint8 green_to_blue;
  uint8 red_to_blue;
} ColorTransformElement;

实际的颜色转换是通过定义颜色转换增量来完成的。颜色转换增量取决于 ColorTransformElement，对于特定块中的所有像素，该值都相同。在颜色转换期间，系统会减去增量。然后，逆颜色转换就是添加这些增量。

颜色转换函数的定义如下：

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 使用表示 3.5 定点数的有符号 8 位整数和有符号 8 位 RGB 颜色通道 (c) [-128..127] 计算得出，定义如下：

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

在调用 ColorTransformDelta() 之前，需要将 8 位无符号表示形式 (uint8) 转换为 8 位有符号表示形式 (int8)。带符号的值应解释为 8 位二进制补码数（即：uint8 范围 [128..255] 映射到转换后的 int8 值的 [-128..-1] 范围）。

乘法运算应使用更高的精度（至少 16 位精度）完成。移位操作的符号扩展属性在这里并不重要；结果中仅使用最低 8 位，并且在这些位中，符号扩展移位和无符号移位彼此一致。

现在，我们来描述颜色转换数据的内容，以便解码器可以应用逆颜色转换并恢复原始的红色和蓝色值。颜色转换数据的前 3 位包含图像块的宽度和高度（以位数表示），与预测器转换相同：

int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;

颜色转换数据的其余部分包含 ColorTransformElement 个实例，对应于图片的每个块。每个 ColorTransformElement 'cte' 都被视为子分辨率图像中的一个像素，其 Alpha 分量为 255，红色分量为 cte.red_to_blue，绿色分量为 cte.green_to_blue，蓝色分量为 cte.green_to_red。

在解码期间，系统会对块的 ColorTransformElement 实例进行解码，并对像素的 ARGB 值应用反向颜色转换。如前所述，该反色转换只是将 ColorTransformElement 值添加到红色和蓝色通道。Alpha 和绿色通道保持不变。

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 Subtract Green 转换

减去绿色转换会从每个像素的红色值和蓝色值中减去绿色值。如果存在此转换，解码器需要将绿色值添加到红色值和蓝色值。此转换未关联任何数据。解码器应用逆转换，如下所示：

void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
  *red  = (*red  + green) & 0xff;
  *blue = (*blue + green) & 0xff;
}

此转换是冗余的，因为可以使用颜色转换对其进行建模，但由于此处没有额外的数据，因此可以使用比完整颜色转换更少的位来编码减去绿色转换。

4.4 颜色索引转换

如果唯一像素值不多，则创建颜色索引数组并用数组的索引替换像素值可能更高效。颜色索引转换可实现此目的。（在 WebP 无损压缩的上下文中，我们特意不将其称为调色板转换，因为 WebP 无损压缩编码中存在一个类似但更动态的概念：颜色缓存。）

颜色索引转换会检查图片中不重复的 ARGB 值的数量。如果该数字低于阈值 (256)，则会创建一个包含这些 ARGB 值的数组，然后使用该数组将像素值替换为相应的索引：像素的绿色通道会被替换为索引，所有 Alpha 值都会设置为 255，所有红色和蓝色值都会设置为 0。

转换数据包含颜色表大小和颜色表中的条目。解码器读取颜色索引转换数据的方式如下：

// 8-bit value for the color table size
int color_table_size = ReadBits(8) + 1;

颜色表使用图像存储格式本身进行存储。可以通过读取不含 RIFF 标头、图片大小和转换的图片来获取颜色表，假设高度为 1 像素，宽度为 color_table_size。颜色表始终采用减法编码，以减少图像熵。调色板颜色的增量通常比颜色本身的熵少得多，因此对于较小的图片，可以节省大量空间。在解码中，可以通过分别按每个 ARGB 分量添加颜色表中的每个最终颜色与前一个颜色分量的值，并存储结果的最低有效 8 位，来获得每个最终颜色。

图像的逆转换只是将像素值（即颜色表的索引）替换为实际的颜色表值。索引是根据 ARGB 颜色的绿色分量完成的。

// Inverse transform
argb = color_table[GREEN(argb)];

如果索引大于或等于 color_table_size，则应将 argb 颜色值设置为 0x00000000（透明黑色）。

当颜色表较小（颜色数小于或等于 16）时，多个像素会捆绑到单个像素中。像素合并将多个（2、4 或 8 个）像素打包成一个像素，从而相应地减少图像宽度。像素捆绑可以更高效地对相邻像素进行联合分布熵编码，并为熵编码带来一些类似于算术编码的优势，但只能在唯一值不超过 16 个时使用。

color_table_size 指定了合并的像素数：

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 的值为 0、1、2 或 3。值为 0 表示不对图片进行任何像素捆绑。值为 1 表示两个像素已合并，每个像素的范围为 [0..15]。值为 2 表示合并了 4 个像素，每个像素的范围为 [0..3]。值为 3 表示合并了 8 个像素，每个像素的范围为 [0..1]，即二进制值。

这些值会打包到绿色分量中，如下所示：

• width_bits = 1：对于每个 x 值（其中 x ≡ 0 [mod 2]），x 处的绿色值会放置到 x / 2 处的绿色值的 4 个最低有效位中，而 x+1 处的绿色值会放置到 x / 2 处的绿色值的 4 个最高有效位中。
• width_bits = 2：对于每个 x 值（其中 x ≡ 0 [mod 4]），x 处的绿色值会放置到 x / 4 处的绿色值的 2 个最低有效位中，而 x + 1 到 x + 3 处的绿色值会依次放置到 x / 4 处的绿色值的更高有效位中。
• width_bits = 3：对于每个 x 值（其中 x ≡ 0 [mod 8]），x 处的绿色值位于 x / 8 处的绿色值的最低有效位，而 x + 1 到 x + 7 处的绿色值按顺序位于 x / 8 处的绿色值的更高有效位。

读取此转换后，image_width 会按 width_bits 进行二次采样。这会影响后续转换的大小。可以使用 DIV_ROUND_UP（如前文所述）计算新的大小。

image_width = DIV_ROUND_UP(image_width, 1 << width_bits);

5 图片数据

图像数据是按扫描线顺序排列的像素值数组。

5.1 图像数据的角色

我们会将图片数据用于以下五种不同的用途：

1. ARGB 图像：存储图像的实际像素。
2. 熵图像：存储元前缀代码（请参阅“元前缀代码的解码”）。
3. 预测器映像：存储预测器转换的元数据（请参阅“预测器转换”）。
4. 颜色转换图片：由图片不同块的 ColorTransformElement 值（在“颜色转换”中定义）创建。
5. 颜色索引图片：大小为 color_table_size（最多 256 个 ARGB 值）的数组，用于存储颜色索引转换的元数据（请参阅“颜色索引转换”）。

5.2 图片数据编码

图片数据的编码与其角色无关。

首先，将图片划分为一组固定大小的块（通常为 16x16 块）。每个块都使用自己的熵编码进行建模。此外，多个块可以共享相同的熵编码。

理由：存储熵编码会产生费用。如果统计上相似的块共享一个熵编码，从而只存储一次该编码，则可以最大限度地降低此成本。例如，编码器可以通过使用统计属性对相似块进行聚类，或者通过在减少对图像进行编码所需的总位数时反复联接一对随机选择的聚类，来找到相似块。

每个像素都使用以下三种可能的方法之一进行编码：

1. 前缀编码的字面值：每个通道（绿色、红色、蓝色和 Alpha）都单独进行熵编码。
2. LZ77 向后引用：从图片中的其他位置复制像素序列。
3. 颜色缓存代码：使用最近看到的颜色的短乘法哈希代码（颜色缓存索引）。

以下各小节将详细介绍这些功能。

5.2.1 前缀编码的字面量

像素以绿色、红色、蓝色和 Alpha（按此顺序）的前缀编码值存储。如需了解详情，请参阅第 6.2.3 节。

5.2.2 LZ77 向后引用

后向引用是长度和距离代码的元组：

• 长度表示要按扫描线顺序复制的像素数。
• 距离代码是一个数字，用于指示之前看到的像素的位置，像素将从该位置复制。确切的映射关系请参见下文。

长度和距离值使用 LZ77 前缀编码进行存储。

LZ77 前缀编码将较大的整数值分为两部分：前缀代码和额外位。前缀代码使用熵编码进行存储，而额外的位则按原样存储（不使用熵编码）。

理由：此方法可减少熵编码的存储空间要求。此外，较大的值通常很少见，因此额外的位将仅用于图像中的极少数值。因此，这种方法可实现更好的整体压缩效果。

下表列出了用于存储不同值范围的前缀代码和额外位。

从前缀代码获取（长度或距离）值的伪代码如下所示：

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;

距离映射

如前所述，距离代码是一个数字，用于指示之前看到的像素的位置，系统将从该位置复制像素。此子部分定义了距离代码与前一个像素位置之间的映射。

大于 120 的距离代码表示扫描线顺序中的像素距离，偏移量为 120。

最小距离码 [1..120] 是特殊的，预留给当前像素的邻近区域。此邻域包含 120 个像素：

• 位于当前像素上方 1 到 7 行，且位于当前像素左侧最多 8 列或右侧最多 7 列的像素。[此类像素的总数 = 7 * (8 + 1 + 7) = 112]。
• 与当前像素位于同一行且位于当前像素左侧最多 8 列的像素。[8 个此类像素]。

距离代码 distance_code 与相邻像素偏移量 (xi, yi) 之间的映射关系如下：

(0, 1),  (1, 0),  (1, 1),  (-1, 1), (0, 2),  (2, 0),  (1, 2),
(-1, 2), (2, 1),  (-2, 1), (2, 2),  (-2, 2), (0, 3),  (3, 0),
(1, 3),  (-1, 3), (3, 1),  (-3, 1), (2, 3),  (-2, 3), (3, 2),
(-3, 2), (0, 4),  (4, 0),  (1, 4),  (-1, 4), (4, 1),  (-4, 1),
(3, 3),  (-3, 3), (2, 4),  (-2, 4), (4, 2),  (-4, 2), (0, 5),
(3, 4),  (-3, 4), (4, 3),  (-4, 3), (5, 0),  (1, 5),  (-1, 5),
(5, 1),  (-5, 1), (2, 5),  (-2, 5), (5, 2),  (-5, 2), (4, 4),
(-4, 4), (3, 5),  (-3, 5), (5, 3),  (-5, 3), (0, 6),  (6, 0),
(1, 6),  (-1, 6), (6, 1),  (-6, 1), (2, 6),  (-2, 6), (6, 2),
(-6, 2), (4, 5),  (-4, 5), (5, 4),  (-5, 4), (3, 6),  (-3, 6),
(6, 3),  (-6, 3), (0, 7),  (7, 0),  (1, 7),  (-1, 7), (5, 5),
(-5, 5), (7, 1),  (-7, 1), (4, 6),  (-4, 6), (6, 4),  (-6, 4),
(2, 7),  (-2, 7), (7, 2),  (-7, 2), (3, 7),  (-3, 7), (7, 3),
(-7, 3), (5, 6),  (-5, 6), (6, 5),  (-6, 5), (8, 0),  (4, 7),
(-4, 7), (7, 4),  (-7, 4), (8, 1),  (8, 2),  (6, 6),  (-6, 6),
(8, 3),  (5, 7),  (-5, 7), (7, 5),  (-7, 5), (8, 4),  (6, 7),
(-6, 7), (7, 6),  (-7, 6), (8, 5),  (7, 7),  (-7, 7), (8, 6),
(8, 7)

例如，距离代码 1 表示相邻像素的偏移量为 (0, 1)，即当前像素上方的像素（X 方向的像素差为 0，Y 方向的像素差为 1）。同样，距离代码 3 表示左上角像素。

解码器可将距离代码 distance_code 转换为扫描线顺序距离 dist，如下所示：

(xi, yi) = distance_map[distance_code - 1]
dist = xi + yi * image_width
if (dist < 1) {
  dist = 1
}

其中，distance_map 是上述映射，image_width 是图片的宽度（以像素为单位）。

5.2.3 颜色缓存编码

颜色缓存用于存储图片中最近使用过的一组颜色。

理由：这样一来，与使用其他两种方法（在 5.2.1 和 5.2.2 中介绍）相比，有时可以更高效地引用最近使用的颜色。

颜色缓存代码的存储方式如下。首先，有一个 1 位的值，用于指示是否使用颜色缓存。如果此位为 0，则不存在任何颜色缓存代码，并且不会在解码绿色符号和长度前缀代码的前缀代码中传输这些代码。不过，如果此位为 1，则接下来会读取颜色缓存大小：

int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;

color_cache_code_bits 用于定义颜色缓存 (1 << color_cache_code_bits) 的大小。color_cache_code_bits 的允许值范围为 [1..11]。对于其他值，合规的解码器必须指示损坏的位流。

颜色缓存是一个大小为 color_cache_size 的数组。每个条目存储一个 ARGB 颜色。通过按 (0x1e35a7bd * color) >> (32 - color_cache_code_bits) 为颜色编制索引来查找颜色。在颜色缓存中只进行一次查找；没有冲突解决。

在开始解码或编码图像时，所有颜色缓存值中的所有条目都会设置为零。颜色缓存代码在解码时会转换为此颜色。通过将每个像素（无论是通过向后引用生成还是作为字面值生成）按其在流中出现的顺序插入到颜色缓存中，来维护颜色缓存的状态。

6 熵编码

6.1 概览

大多数数据都使用规范前缀代码进行编码。因此，代码是通过发送前缀代码长度（而非实际的前缀代码）来传输的。

具体来说，该格式使用空间可变前缀编码。换句话说，图片的不同块可能会使用不同的熵编码。

理由：图片的不同区域可能具有不同的特征。因此，允许它们使用不同的熵编码可提供更大的灵活性，并可能实现更好的压缩效果。

6.2 详细信息

编码后的图片数据由多个部分组成：

1. 解码并构建前缀代码。
2. Meta 前缀代码。
3. 经过熵编码的图片数据。

对于任何给定的像素 (x, y)，都有一组与之关联的 5 个前缀代码。这些代码（按位流顺序）如下所示：

• 前缀代码 1：用于绿色通道、向后引用长度和颜色缓存。
• 前缀代码 #2、#3 和 #4：分别用于红色、蓝色和 Alpha 通道。
• 前缀代码 #5：用于后向参考距离。

从现在开始，我们将此组称为前缀代码组。

6.2.1 解码和构建前缀代码

本部分介绍了如何从比特流中读取前缀代码长度。

前缀码长度可以通过两种方式进行编码。所用的方法由 1 位值指定。

• 如果此位为 1，则表示是简单代码长度代码。
• 如果此位为 0，则表示是正常代码长度代码。

在这两种情况下，都可能存在仍属于数据流的未使用代码长度。这可能效率不高，但格式允许这样做。 所描述的树必须是完全二叉树。单个叶节点被视为完整的二叉树，可以使用简单代码长度代码或正常代码长度代码进行编码。使用正常码长码对单个叶节点进行编码时，除一个码长外，所有码长均为零，并且单个叶节点值标记为长度 1 - 即使在使用该单个叶节点树时不消耗任何位也是如此。

简单代码长度代码

此变体用于特殊情况，即只有 1 个或 2 个前缀符号位于 [0..255] 范围内，且代码长度为 1。所有其他前缀代码长度都隐式为零。

第一个位表示符号数量：

int num_symbols = ReadBits(1) + 1;

以下是符号值。

第一个符号使用 1 位或 8 位进行编码，具体取决于 is_first_8bits 的值。范围分别为 [0..1] 或 [0..255]。如果存在第二个符号，则始终假定其范围为 [0..255]，并使用 8 位进行编码。

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;
}

这两个符号应有所不同。允许使用重复的符号，但效率不高。

注意：另一种特殊情况是，当所有前缀代码长度均为零（空前缀代码）时。例如，如果没有向后引用，距离的前缀代码可以为空。同样，如果同一元前缀代码中的所有像素都是使用颜色缓存生成的，则 alpha、红色和蓝色的前缀代码可以为空。不过，这种情况不需要特殊处理，因为空前缀代码可以编码为包含单个符号 0 的代码。

正常代码长度代码

前缀码的代码长度适合 8 位，读取方式如下。 首先，num_code_lengths 指定代码长度的数量。

int num_code_lengths = 4 + ReadBits(4);

代码长度本身使用前缀代码进行编码；必须先读取较低级别的代码长度 code_length_code_lengths。其余的 code_length_code_lengths（按 kCodeLengthCodeOrder 中的顺序）均为零。

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);
}

接下来，如果 ReadBits(1) == 0，则将每种符号类型（A、R、G、B 和距离）的不同读取符号 (max_symbol) 的最大数量设置为其字母表大小：

• G 渠道：256 + 24 + color_cache_size
• 其他字面值（A、R 和 B）：256
• 距离代码：40

否则，定义如下：

int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);

如果 max_symbol 大于符号类型的字母表大小，则比特流无效。

然后，系统会根据 code_length_code_lengths 构建前缀表，并使用该表读取最多 max_symbol 个代码长度。

• 代码 [0..15] 表示字面代码长度。
  • 值 0 表示未对任何符号进行编码。
  • 值 [1..15] 表示相应代码的位长度。
• 代码 16 将重复前一个非零值 [3..6] 次，即 3 + ReadBits(2) 次。如果在发出非零值之前使用代码 16，则会重复发出值 8。
• 代码 17 会发出长度为 [3..10] 的一连串零，即 3 + ReadBits(3) 次。
• 代码 18 会发出长度为 [11..138] 的一连串零，即 11 + ReadBits(7) 次。

读取代码长度后，系统会使用每种符号类型（A、R、G、B 和距离）各自的字母表大小来形成前缀代码。

正常代码长度代码必须对完整的决策树进行编码，也就是说，所有非零代码的 2 ^ (-length) 之和必须恰好为 1。不过，此规则有一个例外情况，即单叶节点树，其中叶节点值标记为值 1，其他值均为 0。

6.2.2 元前缀代码的解码

如前所述，此格式允许为图像的不同块使用不同的前缀代码。元前缀代码是用于标识在图片的不同部分中使用哪些前缀代码的索引。

仅当图片用作 ARGB 图片时，才能使用元前缀代码。角色

元前缀代码有两种可能，由 1 位值表示：

• 如果此位为零，则表示映像中的所有位置都只使用一个元前缀代码。系统不会再存储任何数据。
• 如果此位为 1，则映像使用多个元前缀代码。这些元前缀代码以熵图像（如下所述）的形式存储。

像素的红色和绿色分量定义了 ARGB 图像特定块中使用的 16 位元前缀代码。

熵图片

熵映像定义了在映像的不同部分中使用的前缀代码。

前 3 位包含 prefix_bits 值。熵图像的维度源自 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);

其中，DIV_ROUND_UP 的定义与之前的定义相同。

接下来的位包含宽度为 prefix_image_width、高度为 prefix_image_height 的熵图像。

Meta 前缀代码的解读

通过从熵图像中找到最大的元前缀代码，可以获得 ARGB 图像中的前缀代码组数量：

int num_prefix_groups = max(entropy image) + 1;

其中，max(entropy image) 表示存储在熵映像中的最大前缀代码。

由于每个前缀代码组包含 5 个前缀代码，因此前缀代码总数为：

int num_prefix_codes = 5 * num_prefix_groups;

给定 ARGB 图像中的像素 (x, y)，我们可以获得要使用的相应前缀代码，如下所示：

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];

其中，我们假设存在 PrefixCodeGroup 结构，该结构表示一组 5 个前缀代码。此外，prefix_code_groups 是一个 PrefixCodeGroup 数组（大小为 num_prefix_groups）。

然后，解码器使用前缀码组 prefix_group 对像素 (x, y) 进行解码，如“解码熵编码的图像数据”中所述。

6.2.3 解码熵编码的图片数据

对于图像中的当前位置 (x, y)，解码器首先会识别相应的字前缀代码组（如上一部分中所述）。给定前缀代码组，像素的读取和解码方式如下。

接下来，使用前缀代码 1 从位流中读取符号 S。请注意，S 是 0 到 (256 + 24 + color_cache_size- 1) 范围内的任意整数。

S 的解读取决于其值：

1. 如果 S < 256
   1. 使用 S 作为绿色分量。
   2. 使用前缀代码 2 从位流中读取红色。
   3. 使用前缀代码 3 从位流中读取蓝色。
   4. 使用前缀代码 #4 从位流中读取 alpha。
2. 如果 S >= 256 且 S < 256 + 24
   1. 使用 S-256 作为长度前缀代码。
   2. 从比特流中读取长度的额外位。
   3. 根据长度前缀代码和读取的额外位确定后向引用长度 L。
   4. 使用前缀代码 #5 从位流中读取距离前缀代码。
   5. 从比特流中读取距离的额外位。
   6. 根据距离前缀代码和读取的额外位确定向后引用距离 D。
   7. 从以当前位置减去 D 像素的位置开始的像素序列中复制 L 个像素（按扫描线顺序）。
3. 如果 S >= 256 + 24
   1. 使用 S - (256 + 24) 作为颜色缓存的索引。
   2. 从该索引处的颜色缓存获取 ARGB 颜色。

7 格式的总体结构

以下是 Augmented Backus-Naur Form (ABNF) RFC 5234 RFC 7405 中的格式视图。其中不包含所有详细信息。图片结束 (EOI) 仅隐式编码到像素数（image_width * image_height）中。

请注意，*element 表示 element 可以重复 0 次或更多次。5element 表示 element 重复 5 次。%b 表示二进制值。

7.1 基本结构

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 转换的结构

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 图片数据的结构

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)

以下是一个可能的示例序列：

RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image