最近在看图像的压缩，就想着先实现一个jpeg文件的解码。本来以为这种资料在网上会一搜一大堆，但搜了之后才发现很多网上的资料要么不够全面在一些关键的地方模糊不清，要么就是在一些细枝末节的地方有些许错误。导致我在这些地方走了不少弯路，为了使后来之人少走这些许弯路，特写此文记录一下。下面这个项目中包含有C语言实现的jpeg解码，可供大家参考：

• https://github.com/neoql/image

JPEG简介

JPEG（Joint Photographic Experts Group）是联合图像专家小组的英文缩写。它由国际电话与电报咨询委员会CCITT（The International Telegraph and Telephone Consultative Committee）与国际标准化组织ISO于1986年联合成立的一个小组，负责制定静态数字图像的编码标准。

小组一直致力于标准化工作，开发研制出连续色调、多级灰度、静止图像的数字图像压缩编码方法，即JPEG算法。JPEG算法被确定为国际通用标准，其适用范围广泛，除用于静态图像编码外，还推广到电视图像序列的帧内图像压缩。而用JPEG算法压缩出来的静态图片文件称为JPEG文件，扩展名通常为.jpg、.jpe*.jpeg。

JPEG专家组开发了两种基本的压缩算法、两种数据编码方法、四种编码模式。具体如下：

压缩算法：

• 有损的离散余弦变换（Discrete Cosine Transform，DCT）
• 无损的预测技术压缩

数据编码方法：

• 哈夫曼编码
• 算术编码

编码模式：

• 基于DCT顺序模式：编/解码通过一次扫描完成
• 基于DCT递进模式：编/解码需要多次扫描完成，扫描效果从粗糙到精细，逐级递进
• 无损模式：基于DPCM，保证解码后完全精确恢复到原图像采样值
• 层次模式：图像在多个空间多种分辨率进行编码，可以根据需要只对低分辨率数据作解码，放弃高分辨率信息

一般情况下，JPEG图像使用离散余弦变换、哈夫曼编码、顺序模式。

JPEG文件结构分析

JPEG文件使用的数据存储方式有多种。最常用的格式称为JPEG文件交换格式（JPEG File Interchange Format，JFIF）。而JPEG文件大体上可以分成两个部分：标记码(Tag)和压缩数据。

标记码由两个字节构成，其前一个字节是固定值0xFF，后一个字节则根据不同意义有不同数值。在每个标记码之前还可以添加数目不限的无意义的0xFF填充，也就说连续的多个0xFF可以被理解为一个0xFF，并表示一个标记码的开始。而在一个完整的两字节的标记码后，就是该标记码对应的压缩数据流，记录了关于文件的诸种信息。

常用的标记有SOI、APP0、DQT、SOF0、DHT、DRI、SOS、EOI。

注意，SOI等都是标记的名称。在文件中，标记码是以标记代码形式出现。例如SOI的标记代码为0xFFD8，即在JPEG文件中的如果出现数据0xFFD8，则表示此处为一个SOI标记。

以下是常用标记的标记代码和表示的意义：

其他资料里还有一些常用标记如APPn、DRI、RSTn，不过我在实际应用中并没有碰到过这些标记，在此就不过多的介绍了，如果想要了解可以查看此文。

下面将介绍常用标记的具体内容。

SOI ( Start of Image )

图像开始

APP0 ( Application 0 )

应用程序保留标记0

本标记段可以包含图像的一个微缩版本，存为24位的RGB像素。如果没有微缩图像（这种情况更常见），则字段⑦“缩略图水平像素数目”和字段⑧“缩略图垂直像素数目”的值均为0。

DQT ( Define Quantization Table )

定义量化表

其中字段②的内容为：

本标记段中，字段②中包含的内容可以循环出现，表示多个量化表，但最多只能出现4次。

SOF0 ( Start of Frame )

帧图像开始

字段⑥中包含这些字段：

字段⑥中的内容会重复出现，有多少个颜色分量（字段⑤）就出现多少次（一般为3次）。

DHT ( Difine Huffman Table )

定义哈夫曼表

字段②包含下列字段：

此标记段中，字段②中的内容可以循环出现（一般为4次），也可以出现4次。例如，Adobe Photoshop 生成的JPEG图片文件中只有1个DHT标记段，里边包含了4个哈夫曼表；而Macromedia Fireworks生成的JPEG图片文件则有4个DHT标记段，每个DHT标记段只有一个哈夫曼表。

这个标记段中的哈夫曼表为范氏哈夫曼表在下文中会有介绍。

SOS ( Start of Scan )

扫描开始

表a：

表b：

本标记段中，字段③应该重复出现，有多少个颜色分量，就出现多少次（一般为3次）。本段结束后就是真正的图像信息了。图像信息直至遇到一个标记代码就自动结束，一般就是以EOI标记表示结束。

EOI ( End of Image )

图像结束

由于在JPEG文件中0xFF具有标志性的意思，所以在压缩数据流(真正的图像信息)中出现0xFF，就需要作特别处理。具体方法是，在数据0xFF后添加一个没有意义的0x00。所以在读取图像信息时如果遇到0xFF00其实际意义为0xFF。

JPEG解码过程

解码流程如下

系数解码->差分解码->反量化->反Zig-Zag->隔行正负纠正->IDCT->图像拼接

读入文件

JPEG文件格式一般为

• SOI(0xFFD8)
• APP0(0xFFE0)
• DQT(0xFFDB)
• SOF0(0xFFC0)
• DHT(0xFFC4)
• SOS(0xFFDA)
• 压缩后的图像数据
• EOI(0xFFD9)

备注：JPEG文件在存储16位整型数据时使用的是大端字节序，而不是常用的小端字节序。如果不清楚什么是大小端字节序可以查看这篇大端序与小端序。

范氏哈夫曼编码

哈夫曼编码是一种最优的前缀编码技术，然而其存在的不足却制约了它的直接应用。首先，其解码时间为O(lavg), 其中lavg为码字的平均长度；其次，更为最重要的是，解码器需要知道哈夫曼编码树的结构，因而编码器必须为解码器保存或传输哈夫曼编码树。对于小量数据的压缩而言，这是很大的开销。因而，应用哈夫曼编码的关键是如何降低哈夫曼编码树的存储空间。

范式哈夫曼编码最早由Schwartz[1964]提出，它是哈夫曼编码的一个子集。其中心思想是：使用某些强制的约定，仅通过很少的数据便能重构出哈夫曼编码树的结构。其中一种很重要的约定是数字序列属性(numerical sequence property)，它要求相同长度的码字是连续整数的二进制描述。例如，假设码字长度为4的最小值为0010，那么其它长度为4的码字必为0011, 0100, 0101, ...；另一个约定：为了尽可能的利用编码空间，长度为i第一个码字f(i)能从长度为i-1的最后一个码字得出, 即: f(i) = 2(f(i-1)+1)。假定长度为4的最后一个码字为1001，那么长度为5的第一个码字便为10100。最后一个约定：码字长度最小的第一个编码从0开始。通过上述约定，解码器能根据每个码字的长度恢复出整棵哈夫曼编码树的结构。

JPEG文件的哈夫曼表存储在DHT标记段中。在标记段DHT内，包含了一个或者多个的哈夫曼表。对于单一个哈夫曼表，应该包括了三部分：

• 哈夫曼表ID和表类型

  这个字节的值为一般只有四个0x00、0x01、0x10、0x11。

  0x00表示DC直流0号表

  0x01表示DC直流1号表

  0x10表示AC交流0号表

  0x11表示AC交流1号表

• 不同位数的码字数量

  JPEG文件的哈夫曼编码只能是1_{16位。这个字段的16个字节分别表示1}16位的编码码字在哈夫曼树中的个数。

• 编码内容

  这个字段记录了哈夫曼树中各个叶子结点的权。所以，上一字段（不同位数的码字数量）的16个数值之和就应该是本字段的长度，也就是哈夫曼树中叶子结点个数。

下面用一段哈夫曼表数据举例说明（数据全部以16进制表示）：

红色部分(第1字节): 为哈夫曼表ID和表类型，其值0x11表示此部分数据描述的是AC交流1号表。

蓝色部分(2~17字节): 为不同位数的码字的数量。这16个数值实际意义为：没有1位和4位的哈夫曼码字；2位和3位的码字各有2个；5位码字有5个；6位和8位码字各有1个；7位码字各有6个；没有9位或以上的码字。

绿色部分(18~34字节): 为编码内容。由蓝色部分数据知道，此哈夫曼树有0+2+2+0+5+1+6+1=17个叶子结点，即本字段应该有17个字节。这段数据表示17个叶子结点按从小到大排列，其每每个节点所代表的值依次为0、1、11、2、21、3、31、41……

在读出读出哈夫曼表的数据后，就要建立哈夫曼树，具体方法为：

1. 第一个码字必定为0。

   如果第一个码字位数为1，则码字为0。

   如果第一个码字位数为2，则码字为00。

   如此类推。

2. 从第二个码字开始

   如果它和它前面的码字位数相同，则当前码字为它前面的码字加1。

   如果它的位数比它前面的码字位数大，则当前码字是前面的码字加1后再在后边添若干个0，直至满足位数长度为止。

举例说明

继续以上边的例子说明问题。

• 由于没有1位的码字，所以第一个码字的位数为2，即码字为00
• 由于2位的码字有两个，所以第二个码字位数仍为2，即码字为00+1=01
• 第三个码字为3位，比第二个码字长1位，所以第三个码字为：01+1=10，然后再添1个“0”，得100
• ......

如此类推，最后得到哈夫曼编码如下：

特别注意的是，如果中间有某个位数的码字缺失，例如没有4位码字，则应该在3位码字加1后，添加“00”补足5位，形成下一个5位码字。

在建立好哈夫曼树之后就可以对图像数据进行解码了。

图像数据流的结构

分析图像数据流的结构, 以一个从宏观到微观的顺序来作详细剖析, 即:

数据流→最小编码单元→数据单元与颜色分量→颜色分量单元

• 在图片像素数据流中, 信息可以被分为一段段最小编码单元( Minimum Coded Unit, MCU) 数据流。所谓 MCU, 是图像中一个正方矩阵像素的数据。这些矩阵的大小是这样确定的:

  查阅标记 SOF0 得到图像不同颜色分量的采样因子。大多图片的采样因子为 4: 1: 1 或 1: 1: 1。记三个分量中水平采样因子最大值为 Hmax, 垂直采样因子最大值为 Vmax, 则单个 MCU 矩阵的宽就是 Hmax×8像素, 高就是 Vmax×8 像素。

  如果整幅图像的宽度和高度不是 MCU 宽度和高度的整数倍, 那么编码时会用某些数值填充进去, 保证解码过程中 MCU 的完整性。

  另外, 在数据流中, MCU 的排列方法是从左到右, 从上到下。

• 每个 MCU 又分为若干个数据单元。数据单元的大小必定为 8×8。

  JPEG 文件与 BMP 文件有所不同, 它把图片分成 Y、Cr、Cb 三张子图, 然后分别压缩。三个颜色分量的采样因子可能一样( 如 1: 1: 1) , 也可能不一样( 如 4: 1: 1) 。

  每个 MCU 内部, 数据的顺序是 Y、Cr、Cb。如果一个颜色分量有多个数据单元, 则顺序是从左到右, 从上到下。

举例说明：

下面通过一幅 32px×35px 的图像, 对上面两个问题作具体说明。

image

图 1 中灰色部分为实际图像大小 ( 32px×35px) ;粗虚线表示各个 MCU 的分界; 细虚线表示 MCU 内部数据单元的分界。

假设此图的采样因子为 4: 1: 1, 即 (2×2): (1×1):(1×1)。此时, Hmax=2, Vmax=2。所以, MCU 的宽为 16像素, 高为 16 像素。图像实际的宽刚好是 2 个 MCU,但高则稍稍大于 2 个 MCU 的高度, 所以要补足 3 行
MCU。

在数据流中,MCU 的 顺 序 是 MCU1→MCU2→MCU3→MCU4→MCU5→MCU6。

每个 MCU 又分为 4 个数据单元。采样因子 4: 1: 1表示 Y 分量的水平和垂直方向都是每 2 个像素采样2 次; Cr 分量和 Cb 分量的水平和垂直方向都是每 2个像素采样 1 次。因此, Y 分量取满 256 个采样点; Cr分量和 Cb 分量各自只有 64 个采样点, 取法如图 2 的灰色点。

如果以 MCU1 说明 MCU 数据的次序, 则依次为Y1、Y2、Y5、Y6、Cb1256、Cr1256。图 2 中全部 256 个点均是 Y的采样点, 灰色部分为 Cr 分量和 Cr 分量的采样点。

对于整张图片来说, 数据流的数据依次是:

[Y1、Y2、Y5、Y6、Cb1256、Cr1256]、[Y3、Y4、Y7、Y8、Cb3478、
Cr3478]、[Y9、Y10、Y13、Y14、Cb9101314、Cr9101314]、……

切记每个MCU里面颜色分量的顺序，是Y、Cb、Cr。Cb在前Cr在后，许多资料这里都写反了，导致最后解码出的图像无法还原到原来的色彩。

若采样因子为1：1：1，则Hmax=max（1，1，1）=1，Vmax=max（1，1，1）=1。所以，MCU的宽为Hmax8=8像素，高为Vmax8=8像素。图像实际的宽刚好是4个MCU，但高则稍稍大于4个MCU的高度，所以要补足5行MCU。

在数据流中，MCU的顺序是：

MCU1→MCU2→MCU3→MCU4→ ………… →MCU18→MCU19→MCU20。

因此，对于整张图片来说，数据流的数据依次是：

[Y1 、Cb1、Cr1] 、[Y2 、Cb2 、Cr2] 、[Y3 、Cb3、Cr3] 、………… [Y19 、Cb19、Cr19]、[Y20 、Cb20、Cr20]。

同理，这里也是Cb在前，Cr在后。

颜色分量单元的内部解码

“颜色分量单元”约定为说明问题而建立的概念,指的是 MCU 中某个颜色分量中的一个 8×8 数据块,例如上面提到的 Y1、Cr1256、Cb1256 都是一个颜色分量单元。

图像数据流是以位( bit) 为单位存储信息的, 并且内部的数据都是在编码时通过正向离散余弦变换( FDCT) 得到的结果, 所以颜色分量单元应该由两部分组成: 1 个直流分量和 63 个交流分量。

解码的过程其实就是哈夫曼树的查找过程。首先查阅标记段 SOS 中的颜色分量信息, 可以得出各个颜色分量对应使用的直流分量和交流分量使用的哈夫曼树编号。一般来说,

• Y 分量: 直流分量: 直流 0 号哈夫曼树, 交流分量: 交流 0 号哈夫曼树
• Cb 分量: 直流分量: 直流 1 号哈夫曼树, 交流分量: 交流 1 号哈夫曼树
• Cr 分量: 直流分量: 直流 1 号哈夫曼树, 交流分量: 交流 1 号哈夫曼树

颜色分量单元内部综合运用了 RLE 行程编码和哈夫曼编码来压缩数据。每个像素的数据流由两部分构成: 编码和数值。具体读入单个颜色分量单元的步
骤如下:

1. 从此颜色分量单元的起点为单位读入, 直到读入编码与该分量的直流哈夫曼树的某个码字一致, 然后用查得该码字对应的值。值表示该直流分量数值的二进制位数, 也就是接下来需要读入的位数。假如是n位，则继续读入n位数据。再根据下文给出的表查询出所对应的值，这个值就是直流分量的值。

2. 继续读入位数据, 直到读入的编码与该分量交流哈夫曼树的某个码字一致, 然后查得该码字对应的值。值的高 4 位表示当前数值前面有多少个连续的零, 低 4 位表示该交流分量数值的二进制位数, 也就是接下来需要读入的位数。假如是n位，则继续读入n位数据。再根据下文给出的表查询出所对应的值，这个值就是对应位置交流分量的值。

3. 不断重复步骤②, 直到满足交流分量数据结束的条件。结束条件有两个, 只要满足其中一个即可

   • 当读入码字的值为零, 表示往后的交流变量全部为零
   • 已经读入 63 个交流分量

各个数值的译码是按下表进行的：

其实对二进制比较熟悉的人一眼就可以看出这张表的究竟。对于正数使用原码编码，对于负数使用反码编码。

举例说明：

某个颜色分量单元数据如下:

D3 5E 6E 4D 35 F5 8A

若以二进制表示，则为：

1101 0011 0101 1110 0110 1110 0100 1101 0011 0101 1111 0101 1000 1010

假设该颜色分量单元对应以下直流哈夫曼树和交流哈夫曼树，则可将各个以位为单位的数据流拆分如下：

<u>110 1001101</u> <u>01 1</u> <u>11001 101</u> <u>11001 001</u> <u>101 00</u> <u>11010 1</u> <u>1111010 11</u> <u>00</u> 01010

直流哈夫曼树：

交流哈夫曼树：

详细说明：

读入数据流并对照直流哈夫曼树，第一个哈夫曼编码为110，其权值为7，所以往后读入7位数据“1001101”，译码成数值为77。因为每个颜色分量单元只有一个直流分量，所以下一个就是第一个交流分量了。

继续读入数据流并对照交流哈夫曼树，得哈夫曼编码为01，其权值为1，所以它的前面没有零，并往后读如1位数据“1”，译码成数值为1。如此往复，最后读到哈夫曼编码“00”，其权值为0，所以满足交流变量结束条件（最后剩余的“01010”对本颜色分量单元来说是冗余的，它可能属于下一个颜色分量单元）。

实际上，这段数据译码为：

77，（0，1），（0，5），（0，-6），（0，-3），（5，1），（2，3）

因此，把它置于1个8*8的矩阵中应为：

image

如果你的解码已经进行到了这里，那么恭喜你，整个程序最麻烦的部分你已经完成了，剩下的只是一些简单的矩阵变换。

直流系数差分编码

每一种颜色分量内, 相邻的两个颜色分量单元的直流变量是以差分来编码的。也就是说，通过上一个步骤解码出来的直流变量数值只是当前颜色分量单元的实际直流变量减去前一个颜色分量单元的实际直流变量。也就是说，当前直流变量要通过前一个颜色分量单元的实际（非解码）直流分量来校正：

DCn=DCn-1+Diff

其中Diff为差分校正变量，也就是直接解码出来的直流系数。但如果当前颜色分量单元是第一个单元，则解码出来的直流数值就是真正的直流变量。

注意, 3 个颜色分量的直流变量是分开进行差分编码的。也就是说, 1 张图片有 3 个直流校正变量。特别特别注意 ,在采样比为4：1：1中也只有3个直流校正变量，比如有一张采样比为4：1：1的图像，他的每个MCU内部是[Y1,Y2,Y3,Cb,Cr],那么每个mcu的的Y2实际值为Y1+Diff，它的Y1为上一个mcu的Y3+Diff。

反量化

不同的颜色分量使用不同的量化表，这个可以从标记段SOF中的颜色分量信息字段查得。一般是Y分量使用量化表0，而Cr、Cb两个分量共同使用量化表1。反量化的过程比较简单。只需要对8*8的颜色分量单元的64个值逐一乘以对应的量化表内位置相同的值则可。图像内全部的颜色分量单元都要进行反量化。

反Zig-Zag

下图中从左图到右图就是正向Zig-Zag，从右图的顺序恢复到左图的顺序就是反向Zig-Zag。

image

在完成上一个步骤后就需要将每个MCU中的每个颜色分量矩阵进行反向Zig-Zag。

IDCT

之前提到，文件中的数据是在编码时通过正向离散余弦变换（FDCT）进行时空域向频率域变换而得到的结果，所以现在解码就必须将其反向离散余弦变换（IDCT），就是把颜色分量单元矩阵中的频率域数值向时空域转换。

YCrCb向RGB转换

要在屏幕上显示图像, 就必须以 RGB 模式表示图像的颜色, 所以, 解码时需要把 YCrCb 模式向 RGB模式转换。

正如前面提到, 并不是每种颜色分量的采样因子都一样, 所以转换时需要注意。由本文第 3 节对 4: 1: 1的采样因子的分析, 可以知道一个 MCU 里有 4 个 Y分量单元, 而 Cr 分量和 Cb 分量各自只有 1 个分量单元。以图 2 为例, 仅有的一个 Cr 分量单元应该平铺用于 4 个 Y 分量单元, 即左上角 16 个值用于 Y1, 右上角 16 个值用于 Y2, 左下角 16 个值用于 Y5, 右下角
16 个值用于 Y6。对于 Cb 分量, 道理一样。

下面是YCrCb向RGB转换的公式:

R = Y + 1.402 * Cr + 128;
G = Y - 0.3441363 * Cb - 0.71413636 * Cr + 128;
B = Y + 1.772 * Cb + 128);

算出来的RGB值如果小于0则为0,如果大于255则为255.

至此, 每个 MCU 的解码已经完成。只要将每个MCU 组成一幅完整的图像就完成了一张 JPEG 图像的解码了。