WebP 无损比特流规范

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

摘要

WebP 无损是一种对 ARGB 图像进行无损压缩的图像格式。无损格式准确地存储和恢复像素值,包括全透明像素的颜色值。采用顺序数据压缩的通用算法 (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 距离,使其具有二维邻近度上的最小像素值。
熵图片
二维亚分辨率图片,指示图片中相应方形应使用哪种熵编码,也就是说,每个像素都是一个元前缀代码。
LZ77
一种基于字典的滑动窗口压缩算法,该算法会发出符号或将其描述为一系列过去的符号。
元前缀代码
一个小整数(最多 16 位),用于将元前缀表中的元素编入索引。
预测器图片
二维亚分辨率图像,指示图片中的特定方形使用哪个空间预测器。
前缀代码
一种执行熵编码的经典方法,即使用较小位数来表示更频繁的代码。
前缀编码
一种对较大整数进行熵编码的方法,该方法使用熵码对整数的几个位进行编码,并对其余的位进行原始编码。这样一来,即使符号范围较大,熵代码的描述仍然相对较小。
扫描行顺序
像素的处理顺序(从左到右以及从上到下),从左手上像素开始。一行完成后,从下一行的左侧列继续。

3 RIFF 标题

标头的开头包含 RIFF 容器。包括以下 21 个字节:

  1. 字符串“RIFF”。
  2. 区块长度的采用小端字节序的 32 位值,区块由 RIFF 标头控制的整个大小。通常,这等于载荷大小(文件大小减去 8 个字节:“RIFF”标识符为 4 个字节,对于值本身为 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 位。

通常,编码器会使用这些转换来减少残差图像中的 Shannon 熵。此外,还可以根据熵最小化来确定转换数据。

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 预测器转换

预测器转换可以利用相邻像素通常具有相关性这一事实来降低熵。在 Predictor 转换中,当前像素值根据已解码的像素预测(按扫描行顺序),并且只对残差值(实际 - 预测)进行编码。像素的绿色分量定义了 14 个预测器中的哪一个在 ARGB 图片的特定块中使用。预测模式决定了要使用的预测类型。我们将图片分成多个方形,并且方形中的所有像素都使用相同的预测模式。

预测数据的前 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 像素均未知。

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

模式 当前像素的每个通道的预测值
0 0xff000000(表示 ARGB 纯黑色颜色)
1 L
2 T
3 土耳其
4 TL
5 平均值 2(Average2(L, TR), T)
6 平均值 2(L, TL)
7 平均值 2(L, T)
8 平均值 2(TL, T)
9 平均值 2(T, TR)
10 平均值 2(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;
}

选择预测器的定义如下:

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 组件执行 ClampAddSubtractFullClampAddSubtractHalf 函数,如下所示:

// 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 像素进行寻址是一项特殊情况。最右列的像素通过使用模式 [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) 值,然后再根据红色值进行转换。

与 Predictor 转换一样,首先将图像分成多个块,并对块中的所有像素使用相同的转换模式。对于每个块,有三种类型的颜色转换元素。

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 使用一个带符号的 8 位整数计算,表示一个 3.5 定点数和一个带符号的 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 减绿色转换

减绿色转换会从每个像素的红色和蓝色值中减去绿色值。如果存在此转换,解码器需要将绿色值同时添加到红色值和蓝色值。没有与此转换关联的数据。解码器按如下方式应用逆转换:

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

此转换是多余的,因为它可以使用颜色转换进行建模,但由于这里没有其他数据,因此减去绿色转换的编码位数少于完整颜色转换的位数。

4.4 Color Indexing 转换

如果没有很多唯一像素值,则更高效的做法是创建一个颜色索引数组,并通过该数组的索引替换像素值。颜色索引转换可以实现这一点。(在 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 处绿色值的更高有效位。

读取此转换后,width_bits 会对 image_width 进行下采样。这会影响后续转换的大小。可以使用之前定义的 DIV_ROUND_UP 计算新大小。

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

5 图片数据

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

5.1 图片数据的角色

我们以五种不同的角色来使用图片数据:

  1. ARGB 图片:存储图片的实际像素。
  2. 熵图片:存储元前缀代码(请参阅“元前缀代码解码”)。
  3. Predictor 图片:存储 Predictor 转换的元数据(请参阅“Predictor 转换”)。
  4. 颜色转换图片:由图片的不同块的 ColorTransformElement 值(在“Color Transform”中定义)创建。
  5. 颜色索引编制图片:大小为 color_table_size 的数组(最多 256 个 ARGB 值),用于存储颜色索引转换的元数据(请参阅“Color Indexing 转换”)。

5.2 图像数据的编码

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

首先将图像分成一组固定大小的块(通常为 16x16 的块)。每个块均使用自己的熵代码进行建模。此外,多个块可能共享相同的熵代码。

说明:存储熵代码会产生费用。如果统计上相似的块共享熵代码,从而仅存储一次代码,则可以最大限度地降低此开销。例如,编码器可以通过以下方式找到相似的块:使用其统计属性对其进行聚类;或者在减少对图片进行编码所需的总位数时,重复联接一对随机选择的聚类。

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

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

以下各小节将详细介绍其中每个部分。

5.2.1 前缀编码的字面量

像素会存储为绿色、红色、蓝色和 alpha 值的前缀编码值(按此顺序)。如需了解详情,请参阅第 6.2.3 节

5.2.2 LZ77 向后引用

向后引用是 lengthdistance code 的元组:

  • 长度表示要复制的扫描行顺序的像素数。
  • 距离代码是一个数字,表示之前看到的像素的位置,即要从中复制这些像素的位置。下文介绍了具体的映射。

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

LZ77 前缀编码将大整数值分为两部分:前缀代码和额外位。前缀代码使用熵代码存储,而额外位则按原样存储(没有熵代码)。

说明:此方法可减少熵代码的存储空间要求。此外,较大的值通常很少见,因此图片中的少数值会使用额外的位。因此,这种方法的整体压缩效果更好。

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

值范围 前缀代码 额外位数
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

从前缀代码获取(长度或距离)值的伪代码如下所示:

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.15.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) 将颜色编入索引来查询颜色。颜色缓存中只会执行一次查询,不会发生冲突解决。

在对图片进行解码或编码时,系统会将所有颜色缓存值中的所有条目都设置为 0。颜色缓存代码会在解码时转换为此颜色。通过将每个像素(无论是通过后向引用生成的像素,还是作为字面量生成的像素)按像素在数据流中出现的顺序插入缓存,可以保持颜色缓存的状态。

6 熵代码

6.1 概述

大部分数据都是使用规范前缀代码进行编码的。 因此,代码通过发送前缀代码长度来传输,这与实际的前缀代码不同。

具体而言,该格式使用空间变体前缀编码。换句话说,图像的不同块可能会使用不同的熵代码。

说明:图片的不同区域可能具有不同的特征。因此,允许它们使用不同的熵代码可以提高灵活性,并且有可能更好地进行压缩。

6.2 详细信息

编码图片数据由以下几个部分组成:

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

对于任何指定像素 (x, y),有一组与其关联的五个前缀代码。这些代码为(按比特流顺序):

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

从现在起,我们将该组称为前缀代码组

6.2.1 解码和构建前缀代码

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

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

  • 如果该位为 1,则它是简单的代码长度码
  • 如果该位为 0,则它是常规代码长度代码

在这两种情况下,数据流中仍有未使用的代码长度。这种操作可能效率低下,但格式允许。所述树必须是完整的二元树。单个叶节点被视为完整的二进制树,可以使用简单的代码长度码或普通代码长度码进行编码。使用常规代码长度代码对单个叶节点进行编码时,除一个代码长度外的所有代码长度都为零,并且单个叶节点值将长度标记为 1,即使使用该叶节点树时未消耗任何位也是如此。

简单代码长度代码

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

第一个位表示符号数量:

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 的熵图像。

元前缀代码的解释

通过从熵图片中查找最大的元前缀代码,即可获取 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_image_width + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[position] >> 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 对经过熵编码的图片数据进行解码

对于图片中的当前位置 (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