JPEG: 编码

量化之后，我们已经得到了一系列由整数构成的 $8\times8$ 系数块。低频系数通常集中在左上角，高频区域通常有大量连续的 0。

JPEG 会依次通过 Zigzag 扫描、差分编码、游程编码和哈夫曼编码，把这些规律转换成更短的码流。这一阶段统称为熵编码（entropy coding）。它不会继续降低图像质量，但会充分利用当前数据的统计分布规律，对数据进行充分的压缩。

DC 系数与 AC 系数

在一个 DCT 系数块中，左上角的第一个系数不包含水平或垂直方向上的变化，表示整个样本块的平均水平，称为 DC 系数。其余 63 个系数都表示不同方向、不同频率的变化，统称为 AC 系数。

DC 系数通常比 AC 系数大，且相邻样本块的 DC 系数往往很接近；AC 系数则通常越靠近右下角越小，并在量化后产生大量的 0。因为这两类系数所具有的特点不同，JPEG 需要使用不同的策略去编码它们。

Zigzag 扫描

在对 DC 系数和 AC 系数进行编码之前，我们先要做一些前置工作。目前的 DCT 系数是以二维矩阵的形式存在的：向右表示水平方向频率升高，向下表示垂直方向频率升高。所以无论是逐行读取还是逐列读取，低频系数和高频系数都会交错出现，不利于把 0 聚集起来。

因此，JPEG 采用了所谓的 Zigzag 扫描方式：从左上角开始，在若干条对角线上来回折返，逐渐走向右下角。

下面的矩阵表示每个位置在 Zigzag 扫描中的顺序，其中 0 是 DC 系数，1~63 是 AC 系数：

$$\begin{bmatrix} 0 & 1 & 5 & 6 & 14 & 15 & 27 & 28 \\ 2 & 4 & 7 & 13 & 16 & 26 & 29 & 42 \\ 3 & 8 & 12 & 17 & 25 & 30 & 41 & 43 \\ 9 & 11 & 18 & 24 & 31 & 40 & 44 & 53 \\ 10 & 19 & 23 & 32 & 39 & 45 & 52 & 54 \\ 20 & 22 & 33 & 38 & 46 & 51 & 55 & 60 \\ 21 & 34 & 37 & 47 & 50 & 56 & 59 & 61 \\ 35 & 36 & 48 & 49 & 57 & 58 & 62 & 63 \end{bmatrix}$$

例如，一个量化后的系数块可能长这样：

$$\begin{bmatrix} 15 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ -2 & -1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$$

经过 Zigzag 扫描后，它变成下面这样的一维序列：

$$15, 3, -2, 0, -1, 0, 0, 1, 0, 0, 0, 0, \cdots, 0$$

按照这种读取顺序，低频信息靠前，高频信息靠后，更容易让高频区域中的 0 聚在一起，从而为后续的编码流程做好铺垫。特别需要说明的是，在这样的一维序列中，开头的总是 DC 系数，而后面跟着的则是 63 个 AC 系数。

DC 差分编码

我们先处理序列开头的 DC 系数。由于相邻样本块的平均亮度通常变化不大，它们的 DC 系数往往也很接近。编码器会保存相同分量里前一个数据块的 DC 值，用它来预测当前块的 DC 值。这个保存下来的值称为 DC 预测器。编码当前块时，只需记录当前 DC 值与预测器的差值，解码器就可以还原出当前块的 DC 值。还原出当前块的 DC 值后，解码器将它作为新的 DC 预测器，继续用于下一个块的解码。

假设连续几个亮度块的 DC 系数是：

$$120, 123, 122, 125, 125$$

我们可以记录当前 DC 系数与前一个同分量 DC 系数之间的差值：

$$120, +3, -1, +3, 0$$

在这个例子中，除了第一个值以外，后面的差值通常较小，因而更容易用较短的编码去表示。

但严格来说，DC 系数的差值并不见得比 DC 系数本身更小。

回忆一下前面的步骤，一个 $8\times8$ 样本块的 DCT 系数可以表示为：

$$F(u,v)=\frac{1}{4}C(u)C(v)\sum_{x=0}^{7}\sum_{y=0}^{7}f(x,y)\cos\left(\frac{(2x+1)u\pi}{16}\right)\cos\left(\frac{(2y+1)v\pi}{16}\right)$$

其中 $C(u)$ 和 $C(v)$ 使用同一个归一化系数函数：

$$C(k)= \begin{cases} \dfrac{1}{\sqrt{2}}, & k=0 \\ 1, & k=1,2,\ldots,7 \end{cases}$$

DC 系数不包含任何水平或垂直方向的变化，所以两个频率索引都为 0，也就是 $F(0,0)$。将 $u=v=0$ 代入后，两个余弦项无论 $x$ 和 $y$ 取什么值都变成 $\cos(0)=1$；同时，两个归一化系数 $C(0)$ 都等于 $1/\sqrt{2}$。因此 DC 系数就是 64 个样本值之和的 $1/8$：

$$F(0,0)=\frac{1}{4}\cdot\frac{1}{\sqrt{2}}\cdot\frac{1}{\sqrt{2}}\sum_{x=0}^{7}\sum_{y=0}^{7}f(x,y)=\frac{1}{8}\sum_{x=0}^{7}\sum_{y=0}^{7}f(x,y)$$

在 DCT 变换前，需要先将输入样本块的每个样本值减去 128，使得样本值的范围从 $[0, 255]$ 变为 $[-128, 127]$，也就是 $[-2^7, 2^7-1]$。

当 64 个样本全部取最小值 $-2^7$ 时，DC 系数为 $64\times(-2^7)/8=-2^{10}$；当它们全部取最大值 $2^7-1$ 时，DC 系数为 $64\times(2^7-1)/8=2^{10}-8$。因此 DC 系数的绝对值不会超过 $2^{10}$。

如果前一个 DC 系数取 $-2^{10}$，当前 DC 系数取 $2^{10}-8$，两者之差便达到最大值：

$$(2^{10}-8)-(-2^{10})=2^{11}-8<2^{11}$$

所以 DC 差值的最大绝对值小于 $2^{11}$。也就是说，在极端情况下，DC 系数的差值可以比原本的 DC 系数还要大。但是这种情况很少会在自然图像中出现。大多数情况下，DC 差值的绝对值都比较小。

正因为差值的取值范围仍然很广，但是通常值又比较小，JPEG 并不会直接把差值原样写进码流。我们完全可以用较少的存储位数去表示较小的值，用较大的存储位数去表示较大的值，从而减少整体所需要的存储空间。

更具体的做法是，先根据差值的绝对值判断它需要多少个二进制位，记作 SIZE；再用 SIZE 个二进制位（附加位）写出具体数值。

我们来看一些例子：

如果差值为 $6$，它的二进制形式是110，因此它属于 SIZE 3。

如果差值为 $-6$，它的绝对值是 $6$，因此同样属于 SIZE 3。而它的附加位 001，则是将 $6$ 的三位二进制形式 110 逐位取反得到的。这里我们也能看出 JPEG 解码器是如何区分正负数的。解码器根据 SIZE 读取指定数量的附加位，通过附加位的最高位就可以判断正负：

• 最高位为 1 时直接按正数解码；
• 最高位为 0 时，将附加位的无符号值减去 $2^{\mathrm{SIZE}}-1$，比如 001 就解码为 $1-(2^3-1)=-6$。

从前面的分析，我们也能得出，编码 DC 系数时，因为 DC 差值的绝对值小于 $2^{11}$，因此 SIZE 的取值范围是 $[0,11]$。其中 SIZE=0 表示差值为 0，不需要附加位。

虽然使用SIZE和附加值，让我们可以在附加值中使用更少的位数表示 DC 差值，但是这种方式也引入了一个额外的SIZE字段，如果所有的SIZE值都按4位的存储空间去存储，这会不会反而让整体所占的存储空间变得更大呢？

所幸的是，因为 DC 差值通常都比较小，所以SIZE是小值的概率也会更大。基于这点，JPEG 会用哈夫曼编码来表示 SIZE，这样出现频率较低的 SIZE 就会被分配较长的码字，出现频率较高的 SIZE 则会被分配较短的码字，这样整体用来存储SIZE的空间也会大大降低。前面提过的附加值则会跟在 SIZE 的哈夫曼码后面。

另外，前面我们说过，一张彩色图像会被划分成 Y、Cb、Cr 三个分量，因此每个分量都会独立维护自己的 DC 预测器，互相不会混用。

DC 预测器会在每个扫描段开始时初始化为 0（扫描段是一段连续编码同一组分量的数据），所以每个分量的第一个 DC 差值在数值上就等于该块的 DC 值。这也是上例中第一个差值为 120 的原因。如果文件使用了重启标记（restart marker），各分量的 DC 预测器还会在每个重启点重新置为 0，使后续数据不再依赖重启点之前的 DC 值。

AC 游程编码

解决了 DC，每个块剩下的 63 个 AC 系数通常由较小的整数和 0 构成。基于这个特点，JPEG 会使用游程编码（run-length encoding，RLE）记录每个非零系数前面有多少个连续的 0。

每个非零 AC 系数会被表示为一对数：

(RUN, SIZE)

其中 RUN 表示这个非零系数前面连续出现的 0 的数量，JPEG 规定它的取值范围为 $[0, 15]$；SIZE 与 DC 编码中的含义相同，表示该非零系数需要多少个附加位。

例如，某一段 AC 系数为：

0, 0, 0, -5, 0, 2

$-5$ 前面有 3 个 0，且 $-5$ 属于 SIZE 3，所以它被表示为 $(3,3)$，后面再跟上 $-5$ 的附加位 010。数值 2 前面有 1 个 0，且 2 属于 SIZE 2，因此表示为 $(1,2)$，后面跟上附加位 10。这一段 AC 系数最终就被编码为：

(3,3) + 010，(1,2) + 10

与前面 DC 系数类似，我们也可以通过数值分析的方法得知，AC 系数的绝对值不会超过 $1020$，也就是小于 $2^{10}$。因此对于非 0 的 AC 系数来说，SIZE 的取值范围就是 $[1,10]$。

不过，在两种特殊情况下，SIZE也可以为0，但这两种情况下它不表示普通的非零系数，而是具有特殊的含义：

• EOB（End of Block）表示从当前位置直到块末尾的系数全部为 0，对应 $(0,0)$；
• ZRL（Zero Run Length）表示连续 16 个 0，对应 $(15,0)$。

前面也提到了，RUN 的取值范围是 $[0, 15]$，也就是说它最多只能表示一个非零系数前面的 15 个 0。如果中间连续出现 16 个或更多的 0，就先写入一个或多个 ZRL，再继续编码后面的非零系数。而当最后一个非零系数后面全是 0 时，只需要一个 EOB 就可以提前结束当前块，不必把剩余位置逐个写出来。

例如：

4, 0, 0, -2, 0, 0, 0, 0, ..., 0

4 前面有 0 个 0，且 4 属于 SIZE 3，所以表示为 $(0,3)$和附加位 100；$-2$ 前面有 2 个 0，属于 SIZE 2，所以表示为 $(2,2)$，附加位为 01；这之后直到块末尾全部都是 0，因此用一个 EOB 就能直接结束。

这段系数最终会被编码为：

(0,3) + 100，(2,2) + 01，EOB

与 DC 类似，为了节省额外引入的RUN和SIZE字段所占的空间，AC 游程编码之后也会使用哈夫曼编码来表示 (RUN, SIZE)，而附加位也是跟在该哈夫曼码后面。

哈夫曼编码

经过前面的处理，需要编码的内容已经从 64 个有符号整数变成了 DC 的 SIZE、AC 的 (RUN, SIZE)，以及紧跟在这些符号后面的附加位。

接下来，JPEG 使用哈夫曼编码（Huffman coding）进一步压缩 DC 的 SIZE 以及 AC 的 (RUN, SIZE)。它的基本思路是：出现频率高的符号使用较短的码字，出现频率低的符号使用较长的码字，这样整体就能用更少的比特表示同样的信息。

假设现在有四种符号，它们出现的频率分别为：

符号	出现频率	常规编码
A	50%	00
B	25%	01
C	15%	10
D	10%	11

如果为每种符号都分配固定的两位编码，那么无论常见还是少见，每个符号都要占两位，每个符号的平均长度显然就是 2 位。

我们先挑出出现频率最低的两个符号 C 和 D，把它们合并成一个新的符号 CD，而这新符号的出现频率就是 C 和 D 的出现频率之和，也就是 15% + 10% = 25%。这个新产生的符号将作为 C 和 D 的父节点。现在我们有三个符号 A、B 和 CD，它们的出现频率分别为：

符号	出现频率
A	50%
B	25%
CD	25%

我们接着挑出出现频率最低的两个符号 B 和 CD，把它们合并成一个新的符号 BCD，它的出现频率就是 25% + 25% = 50%。这个新产生的符号将作为 B 和 CD 的父节点。现在我们有两个符号 A 和 BCD，它们的出现频率分别为：

符号	出现频率
A	50%
BCD	50%

我们再把剩下的两个符号 A 和 BCD 合并成一个新的符号 ABCD，它的出现频率就是 50% + 50% = 100%，这个新符号将作为 A 和 BCD 的父节点。到此为止，我们已经把原来的四个符号合并成了一个符号 ABCD，并且得到了一棵所谓的哈夫曼树。

我们可以看到，原先的 4 个符号都处于这棵树的叶子节点上。我们可以从根节点出发，沿着树的路径走到每个叶子节点，并在每次向左走时写入 0，向右走时写入 1：

从根节点到每个叶子节点所途经的路径，就构成了每个符号的哈夫曼码：

符号	出现频率	常规编码	一种可能的哈夫曼编码
A	50%	00	0
B	25%	01	10
C	15%	10	110
D	10%	11	111

显然，用这种方法构造的编码，就可以让出现频率高的符号使用较短的码字，出现频率低的符号使用较长的码字。使用上面的哈夫曼码后，每个符号的平均长度就变成了：

$$0.5 \times 1 + 0.25 \times 2 + 0.15 \times 3 + 0.1 \times 3 = 1.75$$

相比原来的 2 位有了明显的减少。

另外，Huffman 编码的一个重要特点就是，没有任何一个码字是另一个码字的前缀，这样解码器就可以从码流中逐位读取，只要匹配到一个完整的码字，就可以立即解码出对应的符号，而不必等到读取完所有位。

上面的例子只用于说明哈夫曼编码的基本原理。实际使用中，JPEG 标准还要求不能将全由 1 组成的码字分配给任何符号。这一点倒也很容易解决，只要在构建过程中引入一个频率最低的虚拟符号，给它分配全 1 的码字即可。

DC 与 AC 会使用不同的哈夫曼表进行编码，一张 DC 表和一张 AC 表合称为一组哈夫曼表。在 JPEG Baseline Sequential 中，解码器可以存储 2 组不同的哈夫曼表。通常来说，亮度平面（Y）会使用一组，而色度平面（Cb 和 Cr）会共用另外一组。实际采用的哈夫曼表会写入文件的头部，因此解码器可以直接从文件中读取并使用。

从系数到比特流

经过这些步骤，大量的 0 不再需要逐个保存，常见的小差值和短游程也只占很少的比特。至此，图像从 RGB 像素一路经过色彩空间转换、色度降采样、DCT、量化与熵编码，终于变成了紧凑的压缩数据。