JPEG编码原理

引言

我们知道,计算机的最常用的色彩空间是RGB(红绿蓝三原色),屏幕上每一个像素都是由红绿蓝三个颜色通道叠加最终显示出来。如果我们的电脑桌面的壁纸(1920*1080)没有经过压缩,那么理论上壁纸的大小应该是$1920 \times 1080 \times 3 = 6220800(byte) \approx 5.93(m)$。而我现在所使用的壁纸的大小却只有(676KB),差不多是理论大小的十分之一。

上面图片的属性中有一个关键字JPEG,JPEG全称是Joint Photographic Experts Group是联合图像专家小组,我们平时经常看的jpg图片就是经过 JPEG 压缩技术压缩后的图片。

JPEG 的压缩是一种有损压缩,所谓有损压缩是指图像经过压缩后回丢失一部分的信息。这也就是 JPEG 压缩率高的原因,也是我们日常生活中最经常接触的图片的压缩格式。

下面就让我们了解一下JPEG的原理。

JPEG 压缩编码步骤

JPEG的压缩步骤分为以下几点

  • 色彩空间转换
  • 分块
  • DCT(离散余弦变换)
  • 量化
  • 编码

在下面介绍 JPEG 算法的时候我会使用 lena 的图片作为例子

第一步:颜色空间转换

RGB虽然是计算机最常用的色彩空间,能够直接对应显示器的显示。但是对于数据传输而言,RGB色彩空间并不合适。所以 JPEG 第一步现将图片的色彩空间转换成 YCbCr(YUV)色彩空间。

由 RGB 转换成 YCbCr 的数学公式如下:

$\begin{equation} \begin{array}{} Y = 0.229 \cdot R + 0.587 \cdot G + 0.114 \cdot B \\ Cb = -0.1687 \cdot R - 0.3313 \cdot G + 0.5 \cdot B \\ Cr = 0.5 \cdot R - 0.4187 \cdot G - 0.0813 \cdot B \end{array} \end{equation}$

YCbCr 是一种电视信号传输所用的色彩空间,对应一个亮度通道 Y 和两个色差通道 Cb 和 Cr。早期只有黑白电视,所以电视信号只需要 Y 通道即可。后面出现了彩色电视,就加上 CbCr 这两个色差信号,而原本的黑白电视只需要处理 Y 通道即可,能够兼容黑白彩色电视的信号传输。

YCbCr 色彩空间广泛用于图片与视频的压缩与传输中,由于人眼对亮度变化相对于颜色变化更加敏感,从上面的图像中可以看出来。Y 通道上的细节更加丰富。基于人眼对亮度信息敏感这一点,将 RGB 转换成 YCbCr 后可以对 YCbCr 进行采样。采样时完全保留 Y 通道,对 CbCr 通道的色差信息略去部分,例如 YCbCr4:1:1 就是每一个像素点保存一个亮度信息,每 $2 \times 2$ 像素保存一个 Cb 和 Cr。下图比较了经过 YCbCr4:1:1 采样后还原的图像。

直接对色差通道比较可以看出一点差别,但是最后将图像还原回 RGB 后发现即使去掉了 $75\%$ 的 CbCr 通道后将图像还原,我们看上去感觉并没有发生大的变化。作为对比,下图中我去掉了$75\%$ 的Y,保留全部的 CbCr。

经过 YCbCr4:1:1 采样后,图像数据减少了一半,同时人眼还看不出图像发生的变化。除了 YCbCr4:1:1,还有 YCbCr4:2:0,YCbCr4:2:2 等,这里就不讨论了。

第二步:分块

在完成了颜色空间的转换后。我们需要对图像进行切割,在这一步,我们需要将图像分割成多个 $8 \times 8$ 的小块。这里 lena 的图片刚好是 $512 \times 512$,所以正好可以分割成 $64 \times 64$ 个 $8 \times 8$ 的像素块。

如果图像切割到了后面发现不满足 $8 \times 8$ 的小块后,可以使用黑色像素来补充。这里要将图像分割成 $8 \times 8$ 的像素点是有原因的,这里分块主要为下一步 DCT 进行准备。

第三步:DCT(离散余弦变换)

DCT(离散余弦变换)是整个 JPEG 压缩的核心,不仅仅是图像压缩,DCT 还可以应用到音频压缩上面。由于 JEPG 使用的是 DCT 的第二个变体,所以这里所讲的 DCT 都是 DCT-II。

下面是一维离散余弦变换的公式

$g(x,u) = C(u) \sqrt{\frac{2}{N}} \sum_{x=0}^{N-1} f(x) \cos \frac{(2x+1)u\pi}{2N} \ \ \ \ \ (u, x = 0, 1, 2, ..., N-1)$

$ C(u) = \begin{cases} \frac{1}{\sqrt{2}} & u = 0 \\ 1 & 其他 \end{cases}$

离散余弦变换将有限序列的数据点拆分成用不同频率的余弦函数叠加而成。

图中展示了不同频率余弦函数的形式,其中第一个是一个直线数据,因此被称为直流数据,简称 DC,而后面波动的数据称为交流数据,简称 AC。其中波动小的是低频,波动大的为高频。

由于图像是二维的,所以要使用二维DCT变换将图像信息转换成不同频率的信号。二维离散余弦变换公式如下

$F(u, v) = \frac{2}{\sqrt{MN}}C(u)C(v) \cos \frac{(2x + 1) u \pi}{2M} \cos \frac{(2y + 1)v\pi}{2N} \ \ \ \ \ (u, x = 0, 1, 2, ..., M-1; y, v = 0, 1, 2, ... , N-1)$

$ C(u) = \begin{cases} \frac{1}{\sqrt{2}} & u = 0 \\ 1 & 其他 \end{cases}$

这里的二维离散余弦变换可以使用两次一维的离散余弦变换来完成。下面来看看这个二维离散余弦变换到底对图像做了什么事情。

从图像上可以看出,经过二维 DCT 变换后,图像的低频系数都集中到左上角,高频系数集中在右下角。下面让我们对分块后的图像中每一个小块进行二维 DCT 变换。

在实际中,进行 DCT 变换前,首先会对整个图像的每一个像素减去 128 使得每一个像素的单通道值取值从【0,255】变成【-128,127】。取其中一小块来分析,变换前的 Y 通道 $8 \times 8$ 的矩阵和变换后的矩阵如下。

$\begin{bmatrix}39&35&40&87&87&65&86&121\\37&35&38&55&90&65&50&72\\47&40&42&68&112&77&56&66\\72&66&66&90&108&74&53&87\\84&84&91&83&72&57&66&126\\86&90&80&76&55&65&113&173\\54&60&57&64&77&107&160&198\\63&65&75&88&127&158&188&202\end{bmatrix} - 128 = \begin{bmatrix} -89&-93&-88&-41&-41&-63&-42&-7\\-91&-93&-90&-73&-38&-63&-78&-56\\-81&-88&-86&-60&-16&-51&-72&-62\\-56&-62&-62&-38&-20&-54&-75&-41\\-44&-44&-37&-45&-56&-71&-62&-2\\-42&-38&-48&-52&-73&-63&-15&-1\\-74&-68&-71&-64&-51&-21&-1&-1\\-65&-63&-53&-40&-1&-1&-1&-1 \end{bmatrix}$

经过DCT变换后

$\begin{bmatrix} 658.7500&-162.8823&36.7927&-29.9837&57.7500&-27.1699&-1.9807&3.7277\\-143.8417&80.9572&-82.9830&25.5870&32.7482&-11.6083&-3.2701&2.8878\\38.5136&-111.5488&10.4764&14.4923&-13.3334&13.4097&-9.7212&0.9195\\-3.6290&16.3362&60.4547&-58.1242&5.5042&12.5685&-2.9204&-12.6037\\42.5000&5.1659&-17.5073&-4.4065&9.0000&2.9722&3.4634&-2.9687\\3.3679&-23.8335&1.6384&1.7244&7.1116&5.4616&-8.9086&-4.3761\\21.1191&0.1576&0.5288&-0.4708&3.0875&4.9927&-4.7264&-1.0013\\-6.7585&-9.9562&-0.6021&-1.6794&-1.7498&1.5242&0.9572&3.2054\end{bmatrix}$

直接看矩阵的元素,可以看出:最左上角元素系数的绝对值最大,称为直流分量(DC),其他的63个元素成为交流分量(AC)。而且交流分量(AC)中绝对值大的元素集中在左上方,对应着图像的低频分量;绝对值小的元素集中在右下方,对应着图像的高频分量。这里所说的低频分量对应着图像的宏观,而高频分量对应着图像的细节。由于人眼对一些细节不敏感,所以利用这一点,我们可以略去一些高频分量,从而在对图像进行有损压缩的同时让人们看起来没什么区别。

由于 DCT 变换是可逆的(IDCT 变换),所以我们对图像进行 DCT 变换后略去部分高频分量后能够还原成图像。下面让我们来看看这些所谓的直流分量和低频高频的交流分量显示出来是什么样子的。

由此可以看出,图像中存在了大量人眼察觉不出的细节,而这些细节部分往往占据了图像的大部分空间。通过二维 DCT 变换,图像的能量被集中到了直流分量 DC 上,图像的细节被分成不同的高低频交流分量,高频分量是人眼不容易察觉的细节。这样在压缩的时候适量地去除一些高频的交流分量,这样就能做到在人眼看不出什么变化的情况下对图像进行大幅度的压缩了。

第四步:量化

经过前面的色彩空间转换,图像分块和 DCT 变换,我们可以得到三个浮点数矩阵,这三个浮点数矩阵分别对应着对 YCbCr 三个通道进行分块 DCT 变换后的结果。接下来的量化就是对经过 DCT 变换后的低频高频分量进行处理,略去不重要的部分。这里我将上面经过 DCT 变换后得到的亮度矩阵作为例子。

$G = \begin{bmatrix} 658.7500&-162.8823&36.7927&-29.9837&57.7500&-27.1699&-1.9807&3.7277\\-143.8417&80.9572&-82.9830&25.5870&32.7482&-11.6083&-3.2701&2.8878\\38.5136&-111.5488&10.4764&14.4923&-13.3334&13.4097&-9.7212&0.9195\\-3.6290&16.3362&60.4547&-58.1242&5.5042&12.5685&-2.9204&-12.6037\\42.5000&5.1659&-17.5073&-4.4065&9.0000&2.9722&3.4634&-2.9687\\3.3679&-23.8335&1.6384&1.7244&7.1116&5.4616&-8.9086&-4.3761\\21.1191&0.1576&0.5288&-0.4708&3.0875&4.9927&-4.7264&-1.0013\\-6.7585&-9.9562&-0.6021&-1.6794&-1.7498&1.5242&0.9572&3.2054\end{bmatrix}$

在讲解 DCT 的时候我们已经通过图像对比得知舍去高频分量对图片质量影响不大。而且我们也知道相比于浮点数而言,整数所占用的空间更小。所以在量化过程中,除了要舍去高频分量以外,还需要将所有的浮点数转换成整数。

由于人眼对亮度变化的敏感程度比对颜色变化的敏感程度高,所以在量化的过程中,对亮度通道 Y 和色差通道 Cb 和 Cr 的量化是不一样的。我们要保证量化后亮度通道Y的精度损失小,色差通道 Cb 和 Cr 损失的精度可以大一点。基于这一点,JPEG 给出了如下两个标准量化表。

量化的具体操作就是对每一个浮点数除以对应的量化表上的元素然后四舍五入。公式如下

$B_{j,k} = round(\frac{G_{j, k}}{Q_{j, k}}) \ \ \ \ \ (j = 0, 1, 2, ..., 7; k = 0, 1, 2, ..., 7)$

我们对上面的 G 进行量化后得到如下的B

$B = \begin{bmatrix}41&-15&4&-2&2&-1&0&0\\-12&7&-6&1&1&0&0&0\\3&-9&1&1&0&0&0&0\\0&1&3&-2&0&0&0&0\\2&0&0&0&0&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\end{bmatrix}$

可以看到,经过量化后,矩阵中右下角的大部分元素都变成了0,也就是所谓的将高频分量略去,保留了低频分量,同时将低频分量转化成整数能够更好地保存。因为量化表直接决定了舍去多少细节,所以在 JPEG 中决定压缩后图像的质量也是主要取决于量化表,因此我们可以通过修改量化表来对图片的压缩质量进行调整。

完成量化后,我们还需要将量化后的矩阵转化为一维数组,数组的取值顺序如下,这样能够保证0集中在数组的后方。这个对数据编排的方式叫做“Z”字形编排。

最终我们获得如下数组

$41,-15,-12,3,7,4,-2,-6,-9,0,2,1,1,1,2,-1,1,1,3,0,0,0,-1,0,-2,0,0,...,0$

第五步:编码

前面的 DCT 变换和量化已经完成对图像的压缩,已经决定好图像显示出来的最终效果了。接下来我们需要对经过压缩后的图像数据进行编码,从而使用更小的空间来保存图像,在编码这一步 JPEG 使用了如下几种编码方式:

  • 差值编码(DPCM)
  • 游程编码(RLE)
  • 范式哈夫曼编码

JPEG 的作者提出,相邻的 $8 \times 8$ 图像块中的直流分量 DC 差别不大。所以根据这个特点,JPEG 首先对相邻图像块的直流分量 DC 进行了差值编码。这样只要保留第一个图像块的 DC 和以后每一个 DC 之间的差值,就能还原出每一个图像块的 DC。DC 之间的差值计算如下。

Diff = DC(i) - DC(i-1)

由于不方便展示差值编码的效果,所以在后面的例子中我跳过了差值编码这一步,只是大致讲了一下差值编码对 DC 的编码方式。

完成了对 DC 的差值编码后,我们分析数组中的 AC 分量,可以发现数组里面有非常多的0,我们可以使用游程编码来对这些数据进行压缩。这里游程编码的处理如下:

对每一个非零的数字可以用两个数字来表示,第一个数字表示该数字前面连续0的个数,第二个数字就是该数字本身。这两个数字形成一个组,每一组最多表示 16 个数字,也就是第一个数字的取值范围是 0 ~ 15。例如如果有超过 16 个 0,可以这样表示第 16 个 0(15, 0)。

以前面经过“Z”字形编排后的数组为例

$41,-15,-12,3,7,4,-2,-6,-9,0,2,1,1,1,2,-1,1,1,3,0,0,0,-1,0,-2,0,0,...,0$

使用游程编码后可以表示为:

(0,41);(0,-15);(0,-12);(0,3);(0,7);(0,4);(0,-2);(0,-6);(0,-9);(1,2);(0,1);(0,1);(0,1);(0,2);(0,-1);(0,1);(0,1);(0,3);(3,-1);(1,-2); EOB

完成了游程编码后,我们还需要对每一组的第二个数字进行进一步编码。

JPEG 提供了一张标准的码表如下(该码表是统一的,所有的 JPEG 编码到这一步都是使用一样的码表):

数值 位数 Bits
0 0 -
-1,1 1 0,1
-3,-2,2,3 2 00,01,10,11
-7 ~ -4,4 ~ 7 3 000 ~ 011,100 ~ 111
-15 ~ -8,8 ~ 15 4 0000 ~ 0111,1000 ~ 1111
-31 ~ -16 16 ~ 31 5 00000 ~ 01111,10000 ~ 11111
-63 ~ -32,32 ~ 63 6 000000 ~ 011111,100000 ~ 111111
-127 ~ -64,64 ~ 127 7 0000000 ~ 0111111,1000000 ~ 1111111
-255 ~ -128,128 ~ 255 8 00000000 ~ 01111111,10000000 ~ 11111111
-511 ~ -256,256 ~ 511 9 000000000 ~ 011111111,100000000 ~ 111111111
-1023 ~ -512,512 ~ 1023 10 0000000000 ~ 0111111111,1000000000 ~ 1111111111
-2047 ~ -1024,1024 ~ 2047 11 00000000000 ~ 01111111111,10000000000 ~ 11111111111
-4095 ~ -2048,2048 ~ 4095 12 000000000000 ~ 011111111111,100000000000 ~ 111111111111
-8191 ~ -4096,4096 ~ 8191 13 0000000000000 ~ 0111111111111,1000000000000 ~ 1111111111111
-16383 ~ -8192,8192 ~ 16383 14 00000000000000 ~ 01111111111111,10000000000000 ~ 11111111111111
-32767 ~ -16384,16384 ~ 32767 15 000000000000000 ~ 011111111111111,100000000000000 ~ 111111111111111

使用上面这个码表,我们可以将数值保存为指定位数的二进制数,我们将经过 RLE 编码后的每一组的第二个数字用位数和 Bits 来表示。例如上面的第一组$(0,41)$,$41$ 在上面码表中是位数为 6 的那一组,所以我们可以将 $41$ 用 $(6, 101001)$ 来表示,第一个数字是数值代表的位数,第二个数字是数值对应的二进制数。最后 $(0, 41) \Rightarrow (0, 6, 101001)$,第二组$(0, -15) \Rightarrow (0, 4, 0000)$

至此,我们通过使用多个三元组来表示经过“Z”字形编排的数组。三元组中的第一个数字表示该数字前面连续的 0 的个数,第二和第三个数字分别对应上面码表的位数和 Bits 值。

由于我们规定了每一组最多表示 16 个数,所以三元组中第一个数字的取值范围是 0~15,同时上面的码表也规定了位长的取值范围是 0~15。所以我们可以将第一个数字和第二个数字用一个字节来表示,高四位表示前面连续 0 的个数,低四位表示后面数字的位数。例如:$(0, 6, 101001) \Rightarrow (0x06,101001)$,$(0, 4, 0000) \Rightarrow (0x04, 0000)$。

下一步就是开始范式哈夫曼编码了,在这一步,我们对每一组的第一个数字进行范式哈夫曼编码。范式哈夫曼编码被广泛应用于很多压缩方法中,如 GZIB、ZLIB、PNG、JPEG、MPEG 等。下面给出了 JPEG 标准的范式哈夫曼编码表。

这里四张哈夫曼表分别对应了亮度 DC,色差 DC,亮度 AC,色差 AC 四张哈夫曼表。对应编码表将上面每一组中第一个数据编码完成后,就成功将 JPEG 文件的数据段构造出来了。然后将图像的基本信息(大小,YCbCr 采样方式,哈夫曼表,量化表等)记录下来作为文件头就组成了我们经常用到的.jpg文件了。

总结

最后我们可以以一幅图来总结 JPEG 的编码过程。

参考文献
https://www.impulseadventure.com/photo/optimized-jpeg.html
https://en.wikipedia.org/wiki/JPEG
https://www.ibm.com/developerworks/cn/linux/l-cn-jpeg/

Last modification:May 20th, 2019 at 03:39 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment