Jyrki Alakuijala，博士Google, Inc., 2012 年 6 月 19 日
标有 [AMENDED] 的段落已于 2014 年 9 月 16 日修订。
标有 [AMENDED2] 的段落已于 2022 年 5 月 13 日修订。
标有 [AMENDED3] 的段落已于 2022 年 11 月 21 日修订。
摘要
WebP 无损是一种适用于 ARGB 图像无损压缩的图片格式。无损格式会精确地存储和恢复像素值，包括 Alpha 值为 0 的像素的颜色值。该格式使用以递归方式嵌入该格式本身的子分辨率图片，用于存储图片的统计数据，例如所使用的熵代码、空间预测器、颜色空间转换和颜色表。LZ77、前缀编码和颜色缓存用于压缩批量数据。事实证明，解码速度比 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 距离，使 2D 邻近区域中的像素最小值。
- 熵图片
- 二维子分辨率图片，指示应在图片中的相应方形中使用哪种熵编码，即每个像素都是元前缀代码。
- 前缀代码
- 执行熵编码的经典方法，其中使用更少的位数处理更频繁的代码。
- LZ77
- 基于字典的滑动窗口压缩算法，该算法会发出符号或将其描述为以往符号的序列。
- 元前缀代码
- 将元前缀表中的元素编入索引的小整数（最多 16 位）。
- 预测器图片
- 二维子分辨率图片，用于指示图片中的特定方形使用的是哪个空间预测器。
- 前缀编码
- 一种使用大型代码来对较大整数进行编码的熵，即使用熵代码对整数的几个位进行编码，并将其余位编码为原始值。这样一来，即使符号范围较大，熵代码的说明仍可保持相对较小。
- 扫描行顺序
- 从左至上像素的处理顺序（从左到右、从上到下）到右侧。完成一行后，从下一行的左列继续。
3 RIFF 标题
标头开头包含 RIFF 容器。这由以下 21 个字节组成：
- 字符串“RIFF”
- 块长度的一个小端 32 位值，是由 RIFF 标头控制的块的完整大小。通常等于载荷大小（文件大小减去 8 个字节，“RIFF”标识符为 4 个字节，存储值本身为 4 个字节）。
- 字符串“WEBP”（RIFF 容器名称）。
- 字符串“VP8L”（无损编码图片数据的区块代码）。
- 无损数据流中字节数的 32 位小端值。
- 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 位。
通常，编码器会使用这些转换来减少残差图片中的 Shannon 熵。此外，可以根据熵最小化来确定转换数据。
while (ReadBits(1)) { // Transform present.
// Decode transform type.
enum TransformType transform_type = ReadBits(2);
// Decode transform data.
...
}
// Decode actual image data (Section 4).
如果存在转换，则后两个位指定转换类型。 有四种类型的转换。
enum TransformType {
PREDICTOR_TRANSFORM = 0,
COLOR_TRANSFORM = 1,
SUBTRACT_GREEN_TRANSFORM = 2,
COLOR_INDEXING_TRANSFORM = 3,
};
转换类型后跟转换数据。转换数据包含应用反向转换所需的信息，具体取决于转换类型。接下来，我们介绍不同类型的转换数据。
4.1 预测器转换
预测器转换可通过利用相邻像素通常是关联的事实来减少熵。在预测器转换中，当前像素值是根据已解码的像素（按扫描线顺序）预测的，并且只有残差值（实际 - 预测）进行编码。预测模式决定了要使用的预测类型。我们将图片划分为方形，而方形中的所有像素都使用相同的预测模式。
预测数据的前 3 位以块位数为单位定义块宽度和高度。二维索引中使用的块列数 block_xsize。
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 block_xsize = DIV_ROUND_UP(image_width, 1 << size_bits);
转换数据包含图片每个块的预测模式。一个块的所有 block_width * block_height 像素都使用相同的预测模式。预测模式被视为图片的像素，并使用第 5 章中所述的相同方法进行编码。
对于像素 x, y，可以通过以下方式计算各自的过滤器块地址：
int block_index = (y >> size_bits) * block_xsize +
(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 都是未知的。
鉴于上述相邻像素，不同的预测模式定义如下。
| 模式 | 当前像素的每个通道的预测值 |
|---|---|
| 0 | 0xff000000（以 ARGB 表示纯黑色） |
| 1 | （左） |
| 2 | T |
| 3 | 土耳其 |
| 4 | 团队负责人 (TL) |
| 5 | Average2(Average2(L, TR), T) |
| 6 | Average2(L, TL) |
| 7 | 平均值 2（左，后） |
| 8 | 平均值 2（TL、T） |
| 9 | 平均值 2（T、TR） |
| 10 | Average2(Average2(L, TL)、Average2(T, TR)） |
| 11 | 选择（L、T、TL） |
| 12 | ClampAddSubtractFull(L, T, TL) |
| 13 | ClampAddSubtractHalf(Average2(L, T), TL) |
每个 ARGB 组件的 Average2 定义如下：
uint8 Average2(uint8 a, uint8 b) {
return (a + b) / 2;
}
Select 预测器的定义如下：
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) { // \[AMENDED\]
return L;
} else {
return T;
}
}
函数 ClampAddSubtractFull 和 ClampAddSubtractHalf 会针对每个 ARGB 组件执行，如下所示：
// 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 像素。
[AMENDED2] 处理最右侧列像素的 TR 像素是极好的。最右列的像素通过使用模式 [0..13] 来预测，就像没有边框一样，但与当前像素位于同一行中的最左边的像素会用作 TR 像素。
4.2 颜色转换
[修正 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 实例被视为图像的像素，并使用第 5 章中所述的方法进行编码。
在解码期间，系统会对块的 ColorTransformElement 实例进行解码，并将反色转换应用于像素的 ARGB 值。如前所述，这种颜色反转只是将 ColorTransformElement 值添加到红色和蓝色通道。[已修订 3]
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 减去绿色转换
减去绿色转换会从每个像素的红色和蓝色值中减去绿色值。如果存在此转换，解码器需要将绿色值同时添加到红色和蓝色。没有与此转换关联的数据。解码器应用反转转换，如下所示：
void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
*red = (*red + green) & 0xff;
*blue = (*blue + green) & 0xff;
}
此转换是多余的，因为它可以使用颜色转换进行建模，但它通常很有用。由于它可以扩展颜色转换的动态特性，并且此处没有其他数据，因此可使用少于全面使用的颜色转换的位来减少绿色转换代码。
4.4 颜色索引转换
如果唯一像素值不多，那么创建颜色索引数组并将像素值替换为数组索引会更加高效。颜色索引转换可实现这一点。（在 WebP 无损上下文中，我们特不称之为“调色板转换”，因为 WebP 无损编码中存在类似但更动态的概念：颜色缓存。）
颜色索引转换会检查图片中唯一 ARGB 值的数量。如果该数字低于阈值 (256)，它会创建一个由这些 AGB 值组成的数组，然后将该像素值替换为相应的索引：将像素的绿色通道替换为索引；所有 Alpha 值都设置为 255；所有红色和蓝色值都设置为 0。
转换数据包含颜色表大小以及颜色表中的条目。 解码器读取颜色索引编制转换数据，如下所示：
// 8 bit value for 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 处的绿色值会位于 x / 8 处绿色值的最低有效位处，x + 1 到 x + 7 处的绿色值会置于 x / 8 处的绿色值中较为重要的位。
5 图片数据
图片数据是扫描行顺序中的像素值数组。
5.1 图片数据的作用
我们以五个不同的角色使用图片数据：
- ARGB 图片：存储图片的实际像素。
- 熵图片：存储元前缀代码。像素的红色和绿色分量用于定义 ARGB 图片的特定块中使用的元前缀代码。
- Predictor 映像：存储 Predictor 转换的元数据。像素的绿色分量定义了 14 个预测器中的哪一个在 ARGB 图像的特定块内使用。
- 颜色转换图片。它由
ColorTransformElement值（在 Color Transform 中定义）针对图片的不同块创建。每个ColorTransformElement'cte'都被视为 Alpha 分量为255、红色分部为cte.red_to_blue、绿色分部为cte.green_to_blue、蓝色分部为cte.green_to_red的像素。 - 颜色索引图片：一个大小为
color_table_size（最多 256 个 ARGB 值）的数组，用于存储 Color Indexing Transform 的元数据。存储为宽度为color_table_size，高度为1的图片。
5.2 图片数据的编码
图片数据的编码与其作用无关。
图片首先会拆分为一组固定大小的块（通常是 16x16 块）。每个块均使用各自的熵代码进行建模。此外，几个块可以共用相同的熵代码。
理由：存储熵代码会产生费用。如果统计上类似的代码块共享熵代码，因此可以最大限度地减少开销，从而仅存储一次该代码。例如，编码器可以通过以下方式查找类似块：使用其统计属性对它们进行聚类；或者在编码器减少编码图片所需的总位数时重复联接一对随机选择的聚类。
每个像素都通过以下三种可能的方式之一进行编码：
- 前缀编码字面量：每个通道（绿色、红色、蓝色和 Alpha）均采用熵编码；
- LZ77 反向引用：从图片中的其他位置复制一系列像素；或者
- 颜色缓存代码：使用最近发现颜色的短的乘法哈希代码（颜色缓存索引）。
以下各小节将详细介绍每种方法。
5.2.1 前缀字面量
像素以绿色、红色、蓝色和 Alpha 值（按此顺序）作为前缀编码值进行存储。如需了解详情，请参阅此部分。
5.2.2 LZ77 向后参考
向后引用是 length 和 distance code 的元组：
长度和距离值使用 LZ77 前缀编码进行存储。
LZ77 前缀编码将大整数值分为两部分：前缀代码和额外位：前缀代码使用熵代码进行存储，而额外位内容按原样存储（不含熵代码）。
说明：这种方法可降低熵代码的存储空间要求。此外，较大的值通常很少见，因此额外的位数会用于图片中的极少值。因此，这种方法可提升整体的压缩效果。
下表显示了用于存储不同值范围的前缀代码和额外位。
| 值范围 | 前缀代码 | 额外位数 |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 0 |
| 3 | 2 | 0 |
| 4 | 3 | 0 |
| 5.6.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 |
用于从前缀代码获取（长度或距离）值的伪代码如下：
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个此类像素]。
距离代码 i 与相邻像素偏移 (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 表示左上像素。
解码器可以将距离代码 i 转换为扫描行顺序距离 dist，如下所示：
[已修订 3]
(xi, yi) = distance_map[i - 1]
dist = xi + yi * xsize
if (dist < 1) {
dist = 1
}
其中 distance_map 是上述映射，xsize 是图片的宽度（以像素为单位）。
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 定义 color_cache 的大小，方法是：(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 详细信息
编码图片数据由以下几个部分组成：
- 解码和构建前缀代码 [AMENDED2]
- 元前缀代码
- 熵编码的图片数据
6.2.1 解码和构建前缀代码
对前缀代码进行解码有几个步骤。
解码代码长度：
本节介绍如何从比特流读取前缀代码长度。
前缀代码长度可通过两种方式编码。使用的方法由 1 位值指定。
- 如果这个位为 1，则为简单代码长度代码；
- 如果此位为 0，则为普通代码长度代码。
在这两种情况下，可能都有未使用的代码长度仍然是数据流的一部分。这可能效率低下，但格式允许。
(i) 简单代码长度代码：
[修正 2]
当只有 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 的代码。
(ii) 普通代码长度代码：
前缀代码的代码长度以 8 位为单位，具体如下所示。
首先，num_code_lengths 用于指定代码长度的数量。
int num_code_lengths = 4 + ReadBits(4);
如果 num_code_lengths 大于 19，则比特流无效。[已修订 3]
代码长度本身使用前缀代码进行编码：首先必须读取较低级别的代码长度 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，则不同读取符号的数量上限为 num_code_lengths。否则，其定义如下：
int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);
然后，根据 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、距离）的前缀代码：
- G 频道：256 + 24 +
color_cache_size - 其他字面量（A、R、B）：256
- 距离代码：40
6.2.2 元数据前缀代码的解码
如前所述，该格式允许对图片的不同代码块使用不同的前缀代码。元前缀代码是一些索引，用于标识要在图片的不同部分使用的前缀代码。
元前缀代码只能用于 ARGB 映像的角色中。
元前缀代码有两种可能，以 1 位值表示：
- 如果此位为零，则图片中的任何位置都只有一个元数据前缀代码。不再存储任何数据。
- 如果这个位为 1，表示图片使用了多个元前缀代码。这些元前缀代码以熵图片的形式存储（如下所述）。
熵图片：
熵图片定义了图片的不同部分所使用的前缀代码，如下所述。
前 3 位包含 prefix_bits 值。熵图片的尺寸衍生自 prefix_bits。
int prefix_bits = ReadBits(3) + 2;
int prefix_xsize = DIV_ROUND_UP(xsize, 1 << prefix_bits);
int prefix_ysize = DIV_ROUND_UP(ysize, 1 << prefix_bits);
其中 DIV_ROUND_UP 如前面所定义。
后面的位包含宽度为 prefix_xsize，高度为 prefix_ysize 的熵图片。
元前缀代码的解释：
对于任何给定的像素 (x, y)，都有一组与其关联的 5 个前缀代码。这些代码（按比特流顺序）：
- 前缀代码 1：用于绿色通道、反向引用长度和颜色缓存。
- 前缀代码 #2、#3 和 #4：分别用于红色、蓝色和 Alpha 通道。
- 前缀代码 #5：用于反向引用距离。
在此之后，我们将这组代码称为前缀代码组。
通过从熵图片中找到最大的元前缀代码，可以获取 ARGB 图片中的前缀代码组数量：
int num_prefix_groups = max(entropy image) + 1;
其中 max(entropy image) 表示熵图片中存储的最大前缀代码。
由于每个前缀代码组包含五个前缀代码，因此前缀代码的总数为：
int num_prefix_codes = 5 * num_prefix_groups;
根据 ARGB 图片中的像素 (x, y)，我们可以获取要使用的相应前缀代码，如下所示：
int position =
(y >> prefix_bits) * prefix_xsize + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[pos] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];
其中，我们假设存在 PrefixCodeGroup 结构，它表示五个前缀代码集。此外，prefix_code_groups 是一个 PrefixCodeGroup 数组（大小为 num_prefix_groups）。
然后，解码器使用前缀代码组 prefix_group 来解码像素 (x,y)，如下一部分所述。
6.2.3 解码熵编码数据
[修正 2]
对于图片中的当前位置 (x, y)，解码器首先会识别相应的前缀代码组（如上一部分所述）。根据前缀代码组，系统会按以下方式读取和解码像素：
使用前缀代码 1 从比特流中读取下一个符号 S。请注意，S 是 0 到 (256 + 24 + color_cache_size- 1) 范围内的任何整数。
S 的解释取决于其值：
- 如果 S < 256
- 使用 S 作为绿色组件。
- 使用前缀代码 2 从比特流中读取红色标记。
- 使用前缀代码 3 从比特流中读取蓝色。
- 使用前缀代码 4 从比特流中读取 Alpha 值。
- 如果 S >= 256 && S < 256 + 24
- 请使用 S - 256 作为长度前缀代码。
- 从比特流读取额外长度。
- 根据长度前缀代码确定后向引用长度 L 以及读取的额外位。
- 使用前缀代码 #5 从比特流读取距离前缀代码。
- 为与比特流的距离读取额外的位。
- 根据距离前缀代码确定反向引用距离 D 以及读取的额外位。
- 按扫描行之前的 L 像素从 D 像素前面的顺序复制。
- 如果 S >= 256 + 24
- 使用 S - (256 + 24) 作为颜色缓存的索引。
- 从该索引处的颜色缓存中获取 ARGB 颜色。
7 广告格式的总体结构
下图展示了 Augmented Backus-Naur Form (ABNF) 中的格式。并未涵盖所有详细信息。图片结尾 (EOI) 只会隐式编码为像素数 (xsize * ysize)。
7.1 基本结构
format = RIFF-header image-size image-stream
RIFF-header = "RIFF" 4OCTET "WEBP" "VP8L" 4OCTET %x2F
image-size = 14BIT 14BIT ; width - 1, height - 1
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 图片数据的结构
[修正 2]
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 = code-length-code encoded-code-lengths
code-length-code = ; see section "Normal Code Length Code"
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