从零开始手敲次世代游戏引擎(JPEG特别篇)-2

(首先说一下,这篇会非常难看。但是如果动手去做了,会对各项能力有极大的提高)
我们现在有了核心的算法库,接下来就是实际读取JPEG文件并进行解码了。
首先,JPEG标准(参考引用*2)定义了JPEG交换文件的大的框架结构。
其次,JPEG文件有JFIF和Exif这两种主要的具体实现格式。我们先来看JFIF。JFIF的格式可以参考(参考引用*1)
总的来说,JPEG文件是一个二进制文件,当中包括了一系列以0x FF xx作为开始标记的数据段(Segement)
每个数据段的格式基本如下:
  1. 首先是2个字节的标识符,以FF开头。如 FF C0;
  2. 然后是2个字节的长度,表示该段的长度(有例外,比如包含实际图像数据的SOS段);
  3. (这里需要注意的是,首先,JPEG当中所有的二进制存储都是Big Endian的,或者说是按照网络字节顺序存储的。对于两个字节以上的数据类型,是按照从高位字节(MSB)到低位字节(LSB)的顺序进行存储的,这与X86架构的存储方式是反的;)
  4. (其次,这个长度不包括标识符的2个字节,但是包括其自身的2个字节;)
  5. 接下来的内容则根据段的类型决定。
所以,我们首先需要定义这些段(头)的结构。我们从Framework/Parser/BMP.hpp拷贝新建Framework/Parser/JFIF.hpp,然后根据(参考引用*1)(参考引用*2)当中的(segment header)定义,编写对应的结构体(代码有删节):
然后,我们循环检测段的开头标志,用上面定义的这些结构体将存储在段头结构当中的数据提取出来,大致是如同下面这么一个感觉(有大量删节):
其中,0x FF DA(SOS, Start Of Scan)是实际图像数据存储块开始的标志。当我们检测到这个标志的时候,我们就可以开始Dump图像的数据,直到遇到0x FF D9(EOI, End Of Image)为止。
不过这里面需要注意的问题是,实际上图像数据里面,也会出现0x FF这样的值。为了不让其打乱我们的定位标志,JPEG标准规定,对于图像数据当中出现0x FF这样的情况,在其后立即插入0x 00,也就是以0x FF 00来代表0x FF。(同时,JPEG标准规定,不存在0x FF 00这样的段标志)
上一篇文章当中我们也提到了,JPEG是将图像分割成为8×8的图像块进行编码的。(参考引用*3)当中比较详细地介绍了手工解码一个十分简单的JPEG图像文件的过程。
在我们编程的时候,测试用例的选择同样是十分重要的。一个好的测试用例,可以大大加快我们开发的速度和质量。由于JPEG解码过程涉及到非常多的运算和类型转换,使用一个简单明确的数据样本可以帮助我们快速地找到问题。这里我选用了与参考引用*3相同的图片。这样我们可以将程序解码的每一步结果与文章当中提供的结果进行对比,快速找到问题。这个图片是这样的:
图片来自参考引用*3
太小?放大的话,如下(外框和虚线表示像素边界,不是原图片的一部分):
图片来自参考引用*3
是一个16像素宽,8像素高的图片。左边8×8是全黑,右边8×8是全白。
这么一个图片,在压缩之前是 16(像素(宽)) * 8(像素(高)) * 3 (字节/像素)= 384个字节。经过JPEG压缩之后,是304个字节到653个字节之间。
什么?653个字节?那不是更大了?是的,这是因为JPEG文件的构造当中,除了图像数据之外,还有很多记录图像属性以及压缩算法参数的元数据。因为我们的图片太小了,所以这些开销反而成为了大头。事实上,如果抛去这部分开销,压缩后的图像数据只有7到9个字节。
一般来说,JPEG的压缩率大约在1/5左右。当然这和很多因素有关。
我们接下来就来看这区区9个字节是怎么一步一步展开成为384个字节的。
经过上面的程序的处理,我们可以从文件当中的SOS和EOS这两个标志之间,提取出下面这9个字节的图像数据:
首先,如上面所说的,0x FF 00实际上是代表着FF。所以其实有效的数据一共有8个:
然后,这8个数据其实是一种变种的霍夫曼(Huffman)编码(参考引用*5)。霍夫曼是上个世纪50年代MIT的高材生。这种编码的核心思想就是,用尽量短的2进制bit代表最多出现的数据。
比如说我们有100个人,每个人有一个学号。如果其中有些人经常来上课,我们就给他一个短一点儿的号码。不太来上课的,我们就给他一个长一点的学号。这样的话,每次点名的时候,我们就可以少写一点儿字。
在计算机当中,所有数都是用二进制表示的。比如十进制8,用二进制表示是1000,这个长度就是4个bit;而十进制1,用二进制表示还是1, 这个长度就只有1个bit。如果在一个序列当中,8经常出现,而1出现的比较少,那么我们通过(强行)定义二进制1代表8,而二进制1000代表1,那么就可以缩短整个编码的长度,而不会丢失任何数据。
因此很容易可以想到,如果想要对一个序列进行霍夫曼编码,首先需要统计在这个序列当中基本符号的种类和出现频率。然后将基本符号按照出现频率从高到低进行排序,对于高的给予尽可能短的编码,对于低的给予稍长一些的编码,目的是使最终的整体码长最短。
这是一个算法问题。有兴趣的可以参考(参考引用*5)。我这里就不作更多的展开了。
我们这里需要实现的是霍夫曼编码的解码。绝大部分的解码,最终都是类似一个查字典的过程。首要的是构建这个字典(如果放在安全领域就叫密码本),然后根据索引一个个查出来就好了。
JPEG文件的目的并不是加密,所以这个密码本是放在文件当中的。这也是为什么在我们这个例子当中,压缩之后的文件反而变大的原因。
JPEG的密码本的起始标志是0x FF C4。我们在文件当中定位到它,然后将其提取出来。提取出来的结果大致如下(出于篇幅考虑只列出了部分):
竖线左侧的是编码(索引,密文),右侧的是值(词条,符号,明文)
这里需要注意的有以下几点:
  1. 虽然JPEG当中保存了这个字典(密码本),但是为了缩小文件尺寸(毕竟JPEG的目的是压缩),没有直接保存编码(索引,密文),而只是保存了值(词条,符号,明文)以及其在Huffman Tree当中的层级。我们需要自己根据这些信息重建Huffman Tree来生成索引;
  2. JPEG当中这样的字典(密码本)有4个。其内容是根据被保存的图片内容以及压缩品质设置变化的。在解码的过程当中会根据当前提取的数据状态使用不同的字典(密码本)(后面详述)
好了。接下来我们需要了解JPEG文件当中图像数据的组织形式。上一篇文章当中我们所提到的8×8分块,这个其实是最底层的组织形式。事实上,彩色图像会包括R/G/B这3个通道(注意普通的JPEG不支持Alpha通道,也就是透明度)。上一篇文章当中也提到,在JPEG压缩的过程当中,首先会将像素的色彩空间从RGB转成YCbCr。这样做的原因(或者说目的)是为了进一步减少文件尺寸。
不过单纯的RGB转YCbCr,这个是一个3个分量到3个分量的坐标轴转换,并不会直接带来数据的减少。秘密在于YCbCr的DownSampling。RGB三个通道都是彩色通道,其对于人眼的重要度其实是基本均等的(如果硬要说的话,G相对来说更重要一些)。但是到了YCbCr领域,Y(辉度)是最重要的(人眼的辨识度/敏感度最高),而两个色差信号就比较不重要一些。
所以,在变换到YCbCr之后,我们就可以将CbCr这两个通道的图缩小。意思是,比如8×8的图像块,Y通道仍然维持8×8的分辨率,但是CbCr这两个通道可以只保留4×4的分辨率,甚至只保留2×2的分辨率,就可以了。事实上,大部分的彩色电视信号,都是采用了这种方式来减少信号的码率。需要进一步了解的,可以参考(参考引用*6)
图片来源:Wikipedia
说了这么多,好像和前面的霍夫曼编码没有什么关系呢?
如果是原版的霍夫曼编码,那么只需要按照字典将“密文”一一翻译成为明文就可以了。然而JPEG当中的复杂性在于,它有4个密码本。什么时候使用哪个密码本,是和上面所说的YUV格式息息相关的。这是因为各个信号的统计分布很可能是非常不一样的。结合其特点使用不一样的密码本可以进一步减少压缩后的文件大小。
常规的做法是,对于Y信号(通道)使用一套密码本,而对于CbCr信号(通道)使用另外一套密码本。注意我这里使用的是“一套”,而不是“一个”。为什么呢?
因为单单是这样解释不了JPEG使用4个密码本的原因(看起来似乎2个就够了?)。这时候请回想起(或者如果还没有看过,请看)上一篇文章当中关于DCT/IDCT的介绍。经过DCT变换之后,矩阵的左上角(0,0)位置的值绝对值一般远大于矩阵当中的其他值。这个左上角的值被称为直流分量(DC。沿用电学称呼,在这里其实与电流没有任何关系)代表的是8×8像素块的平均值,它的统计特性与其他值(交流分量,AC。)也是非常不同的。
可能聪明的你已经猜到,其实JPEG不仅为不同的信道指定了(可能)不同的密码本,也为DCT当中的直流分量和交流分量指定了不同的密码本。所以实际上是这么一个分配情况:
  1. 用于Y通道DC分量的密码本
  2. 用于Y通道AC分量的密码本
  3. 用于CbCr通道DC分量的密码本
  4. 用于CbCr通道AC分量的密码本
下面是我们这个例子当中用到的Y通道的AC分量密码本,对比上面DC分量的密码本,我们可以看到它们是非常不同的(符号的数量远多于DC分量):
好了,有了这些知识储备之后,我们就可以解码那神秘的8个字节了:
在JPEG当中,是按照下面这么一个顺序存储数据的(这里以YUV444为例):
我们根据这个顺序反复替换对应的密码本,就可以得到Y,Cb,Cr三个分量的DCT矩阵。不过这里实际上还有一个秘密,就是被霍夫曼编码的其实并不是矩阵的值,而是关于矩阵的值的一个描述。具体来说:
将FC展开成二进制:
查阅Y(DC)密码本,可以得到前7位(1111 110)= 0x 0a。(为什么我们知道是前7位?仔细看看上面霍夫曼的编码(索引),你会发现在同一个密码本里面没有任何一个短的码会成为长的码的开头一部分。所以我们只需要一位一位的去匹配,直到找到对应的值为止。这就是霍夫曼编码的NB之处)
这个0x 0a其实并不代表Y(DC)的值是10。它的意思其实是说,接下来的10个bit是DC的值。所以我们从第8位开始往后取出10个bit,这才是DC的值。
这就是JPEG当中的霍夫曼编码与常规的霍夫曼编码不同的地方,被称为huffman / entropy coding。其目的当然是:为了进一步毫无人性地减少文件的尺寸。(提供以bit为单位,而不是byte为单位的存储方式)
这就是全部的秘密了吗?
并不是。JPEG是一个相当复杂的编码体系。接下来的AC部分,规则又有些不一样了。
原因其实也并不复杂。每个8×8矩阵里面,DC只有一个,位于(0,0)位置,但是AC有63个,并且大多数为0⃣️。学过算法的应该知道,这是一种典型的稀疏矩阵。下面是我们这个例子的左边8×8的Y分量DCT矩阵:
所以,如果按照DC的存储方式,即使是0,我们也需要为每个0分配存储空间(哪怕是1bit)。这个显然还不够省。
所以AC分量采用的编码方式是,在用于说明数据格式的那个字节(也就是被霍夫曼编码的那个字节当中)除了说明后面有几个bit用来表示AC分量之外,还说明有几个连续的零。但是因为其实这个说明符只有一个字节,所以其中的高4位用于表示连续的0⃣️的个数,低4位用于表示AC分量的bit数。这样的话,最多能够表示的连续的0⃣️的个数是15个。
这对于上面这种情况,还是不够省。所以JPEG又规定,如果数据说明字节的值为0,则表示从该位置开始之后到第64个矩阵元素的值都是0。
这就是全部的秘密了吗?
很可惜,虽然已经很复杂了,还有。
因为DCT矩阵的特点就是左上角有值,右下角基本都是0⃣️,所以传统的按行列进行存储的话,会把0⃣️分散在非零的值之间,不能达到最大的压缩率。所以,JPEG当中对于矩阵的存储采用的是ZigZag方式,如下:
图片来源:ISO/IEC 10918-1 : 1993(E)(参考引用*2)
这样可以将矩阵当中的0⃣️串一长串,然后用一个0x 00早早的将这个矩阵结束掉。
也就是说:
如果矩阵全为零,那么一个0x 00就可以代表它。(压缩率1/64)
如果矩阵里面只有稀稀拉拉几个值,那么几个字节就可以代表它。

好了,经过这样眼花缭乱的技巧之后,我们上面的8个字节,就可以展开成为下面这6个矩阵:
这里最后的一个步骤:Y分量的DC部分在块间是存储的差值。也就是说,第二个8×8块的Y(DC)其实应该是第一个8×8块的Y(DC)+第二个8×8块的Y(DC)。也就是说上面第二个块的Y分量矩阵需要修正为 -512 + 1020 = 508
然后将这些8×8矩阵分别用上一篇我们所写的IDCT变换变换回来,得到:(CbCr为全零矩阵,IDCT之后仍然是全零矩阵)
然后将其上浮128(使得值域从[-128 ,127]变为[0, 255]),然后使用我们上一篇所写的YCbCr –> RGB色彩空间变换,得到最终结果如下:
每组数据分别包括R、G、B三个分量
这正是我们用于测试的图片的样子(左边8×8黑色,右边8×8白色)
最后附上完整的程序执行输出,供有兴趣的读者参考:(代码在jpeg分支当中)
*上面的说明当中还省略了被称为Quantization的过程。这个过程是将DCT矩阵的不同元素进行缩放,使得AC的部分尽可能变成绝对值小于1的小数,然后在取整的时候变成0。JPEG之所以是有损压缩,除了色空间变换之后的YUV chrome sub sampling,数据的丢失主要就是发生在这一步。而上面介绍的其他步骤,在不考虑计算误差的情况下,都是可逆的)
 
参考引用

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 登出 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 登出 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 登出 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 登出 /  更改 )

Connecting to %s

%d 博主赞过: