View on GitHub

JPEG 编码过程解析

前言

我们目前互联网上大多图片都使用 RGB 色彩空间表示图片，也就是使用三个通道（红绿蓝）来表示每个像素点，每个通道使用 1 个字节（8 位） 来表示。早期 BMP 图片使用的就是直接存储每个通道的值，但这样会导致图片文件过大，所以后来才出现了 JPEG 这种图片编码压缩方法。

背景知识

色差信号

对于 RGB 色彩空间来说，JPEG 会先把色彩信号转换成色差信号，原因是人眼对亮度的感知要比对色彩的感知要强，所以可以对色彩信号进行更强的压缩。把亮度 信息分离出来后，可以有针对性地使用不同的量化表、采样因子来达到不同的压缩率。 色差信号的转换公式可以参考 YCbCr。

DCT

DCT（Discrete Cosine Transform）是 JPEG 图片编码的核心算法，它可以把图片从空间域转换到频域，这样可以更好地利用人眼对图片的感知特性。简单 来说 DCT 就是把原始的图像信号分成多个小块，然后对每个小块进行变换，得到频域的系数。这样可以把图像的能量集中在少量的频率上。特别地对于第一个系数 即 $ u=0 $ 时，这个系数表示图片的平均亮度，也称之为直流信号（DC），剩下的系数称为交流信号（AC）。人眼对亮度识别是很敏感的，其次才是高频信号， 通过 DCT 变换后可以把图片某个区域内的能量集中在 DC 系数上，剩下的 AC 系数进行尽可能的删减，越高频的信号越可以删减，从而达到压缩的目的。关于 DCT 的白话介绍可以参考 给 5 岁的孩子解释视频压缩中的 DCT。

RLE

RLE（Run-length Encoding） 是一种无损压缩算法，它可以把连续重复的数据序列压缩成一个数据和重复次数的组合。在 JPEG 图片编码中，RLE 会对 DCT 变换后的系数进行压缩，因为 DCT 变换和量化后的系数中有很多连续的 0，这些 0 可以通过 RLE 来压缩。

ZigZag Encoding

ZigZag 是 JPEG 图片编码中用来把 DCT 变换后的系数排列成一维数组的方法。DCT 变换后的系数是一个 8x8 的矩阵，ZigZag 会把这个矩阵按照一定的顺序 读取成一维数组。这样可以把高频信号集中在数组的后面，方便后续的压缩。 ZigZag Coding

哈夫曼编码

哈夫曼编码（Huffman Coding）是一种变长编码，它可以根据信号的出现频率来分配不同长度的编码，从而达到压缩的目的。出现频率越高的信号，分配的编码长度越短。哈夫曼编码 是无损压缩，也就是说可以完全恢复原始信号。哈夫曼编码会输出两个参数，一个是哈夫曼表，另一个是编码后的二进制数据。

编码一个图片

下面我们来把一个位图编码成 JPEG 图片，使用最常见的 RGB 色彩空间，并使用色差信号，采样因子 4:2:2。

JPEG Encoding

  1. 读取位图，把 RGB 信号转换成色差信号。这时候还是 3 个通道的数据，只不过每个通道的含义不一样了。
  2. 根据确定的采样因子划分 MCU（Minimum Coded Unit）。常见的是 4:2:2 和 4:2:0 采样因子，采样如下图： YCbCr Sampling 由于色差信号中的 Cb、Cr 通道比较不重要，因此适当进行降采样可以减小图片的大小。因为我们这里使用的是 4:2:2 采样，所以每个 MCU 输出为 16x16 的像素块，并划分成 4 个 8x8 的编码单元，其中有 4 个 Y 通道的编码单元，2 个 Cb 通道，2 个 Cr 通道。如果是 4:4:4 采样，那么 MCU 的大小 则为 8x8，每个 MCU 有 1 个 Y 通道，1 个 Cb 通道，1 个 Cr 通道。

    1. 对于每个 8x8 的编码单元，进行 DCT 变换。变换结果是 1 个 DC 信号和 63 个 AC 信号。

    2. 对图片进行量化，量化表的作用是把大的数字直接除以一个固定值然后四舍五入，这样可以把大的数字变成小的数字，使得后面哈夫曼编码时数字重复几率 更高哈夫曼编码压缩率更高。量化表里的数字越大代表压缩率越高。一般来说会对 Y 通道使用更小的量化表，压缩率更低，而对 Cb、Cr 通道使用更大的 量化表，压缩率更高，因为人眼对色彩的感知不如对亮度的感知强。另外是对于高频信号（即 DCT 结果的右下角），量化表的值会更大，因为高频信号 的能量（振幅）更少，对图片清晰度的影响也更小。标准的量化表，即压缩质量为 50 时亮度和色彩的量化表分别是这样：

      0 1 2 3 4 5 6 7
      16 11 10 16 24 40 51 61
      12 12 14 19 26 58 60 55
      14 13 16 24 40 57 69 56
      14 17 22 29 51 87 80 62
      18 22 37 56 68 109 103 77
      24 35 55 64 81 104 113 92
      9 64 78 87 103 121 120 101
      72 92 95 98 112 100 103 99
      0 1 2 3 4 5 6 7
      16 18 24 47 99 99 99 99
      18 21 26 66 99 99 99 99
      24 26 56 99 99 99 99 99
      47 66 99 99 99 99 99 99
      99 99 99 99 99 99 99 99
      99 99 99 99 99 99 99 99
      99 99 99 99 99 99 99 99
      99 99 99 99 99 99 99 99

    3. 对于 DC 信号，使用 DPCM（Differential Pulse Code Modulation）编码。DPCM 是一种无损压缩算法，它可以把连续的信号差值编码成一个信号。 因为每个相邻的编码单元之间亮度变化不会太大，因此可以把 DC 信号编码成差值，变成更小的数字，重复几率更大，这样更有利于后续的哈夫曼编码。

    4. 把整个 8x8 的编码单元按照 ZigZag 编码成一维数组。这样可以把高频信号集中在数组的后面，方便后续的压缩。

    5. 使用 RLE 编码。由于使用量化表并且按照 ZigZag 编码后高频信号会有很多 0，因此可以使用 RLE 来压缩 AC 信号。特殊地，使用 0x00 作为结 束标志，这表示这个编码单元后续的信号都是 0。

  3. 编码完的每个 MCU，都按照 JFIF 格式写入文件。JFIF 格式是 JPEG 文件的一种常见格式，它包含了文件头、Component 数量、宽高、 DQT（Define Quantization Table）、 DHT（Define Huffman Table）、SOS （Start of Scan）等信息。除此之外还有一些额外的信息比如我们 常见的图片相机信息。关于图片的 tag 可以参考这里。如果自己想要了解一下图片的 EXIF 信息， 可以使用 exiftool 这个工具。MAC 可以直接使用 brew 安装。

探讨 DCT 和量化对图片质量的影响

  1. 我们构造一个简单的 8x8 的图片，为了方便我们使用灰度图片，这样只需要一个通道即可，像素如下：

    0 1 2 3 4 5 6 7
    255 255 100 100 100 0 0 0
    255 255 100 100 100 0 0 0
    255 255 100 100 100 0 0 0
    255 255 100 100 100 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

  2. DCT 转换之后，我们得到的结果如下：

    0 1 2 3 4 5 6 7
    405 366 77 45 49 -62 -86 -6
    366 331 70 41 45 -56 -78 -5
    0 0 0 0 0 0 0 0
    -128 -116 -24 -14 -15 20 27 1
    0 0 0 0 0 0 0 0
    86 77 16 9 10 -13 -18 -1
    0 0 0 0 0 0 0 0
    -72 -65 -14 -8 -9 11 15 1

  3. 量化之后，我们得到的结果如下：

    0 1 2 3 4 5 6 7
    25 33 8 3 2 -2 -2 0
    30 28 5 2 2 -1 -1 0
    0 0 0 0 0 0 0 0
    -9 -7 -1 0 0 0 0 0
    0 0 0 0 0 0 0 0
    4 2 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    -1 -1 0 0 0 0 0 0

    我们可以看到，量化后右下角会出现很多 0，这样可以使用 RLE 来压缩。

  4. 尝试乘回量化表

    0 1 2 3 4 5 6 7
    400 363 80 48 48 -80 -102 0
    360 336 70 38 52 -58 -60 0
    0 0 0 0 0 0 0 0
    -126 -119 -22 0 0 0 0 0
    0 0 0 0 0 0 0 0
    96 70 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    -72 -92 0 0 0 0 0 0

  5. 进行 IDCT（Inverse Discrete Cosine Transform），看看复原出来的信号是怎样

    0 1 2 3 4 5 6 7
    254 254 100 100 99 0 0 0
    254 254 100 99 99 0 0 0
    254 254 101 99 99 0 0 0
    253 253 100 99 99 0 0 0
    0 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

我们可以看到，进行量化后高频部分信号被舍弃了，最终 DCT/IDCT 前后的结果，我们会发现边缘部分的信号影响较大。这也就是为什么 JPEG 图片压缩时 quantity 选择低质量时图片边缘会出现模糊的原因，这个边缘是指物品的轮廓、颜色（亮度）突变的地方。

香港城市大学有一份非常好的可视化一步步JPEG 编码器实现。

总结

JPEG 是一种有损的压缩算法，主要压缩的地方有：

每个 MCU 是单独压缩的，在压缩率较高的情况下，可能导致 MCU 之间边缘会出现截然不一样的边缘陡变。

根据香农极限我们可知，一定的信道容量，无损的压缩是有一定上限的。 需要在文件大小和质量之间取得平衡，JPEG 选择把对人眼不敏感的信号进行更高的压缩率，从而达到更高的压缩率。

References