图片上的算法之JPEG压缩

大家好，这里是tiankonguse的公众号(tiankonguse-code)。
tiankonguse曾是一名ACMer，现在是鹅厂视频部门的后台开发。
这里主要记录工作中的技术架构与经验、计算机相关的技术、数学、算法、生活上好玩的东西。

这篇文章从公众号tiankonguse-code自动同步过来。
如果转载请加上署名：公众号tiankonguse-code，并附上公众号二维码，谢谢。

零、背景

听了JPEG图片的压缩算法，发现蛮有意思的，这里分享一下。

一、整体思想

JPEG有损压缩算法是一个可逆的算法，所以这里重点介绍压缩部分，对于逆过程这里就不谈了。

整体压缩流程如下：

1. 色彩空间转换
2. 缩减取样
3. DCT变换
4. 量化
5. 熵编码技术

下面分别讲一下这几部分都是做什么的吧.

这里先强调一个思想：
有损压缩的本质就是抛弃那些不影响大局的信息。
从而做到使用更小的储存来表达对应的信息。

二、色彩空间转换

颜色具体显示的时候需要是RGB的形式，比如每个像素由三个8字节的数字组成。
这样的表示相当于使用三个互相独立的颜色矩阵组合成了一张图片。
每个颜色矩阵是等价的，且任何一个颜色矩阵数据有较大偏差时，我们人眼都能明显感知到。

生物学上，研究发现人眼对亮度差异比较敏感，但是颜色的差异变化并不是那么敏感。
所以就有人想到转化为亮度和颜色的表示形式。

大概有下面几种算法：YIQ，YUV 和 YCrCb， 而这里采用的是YUV转化算法。
Y维度代表一个像素的亮度，U和V维度用来代表颜色。

这个转换的好处是后续的步骤中对Y维度只能稍微抛弃一些的信息，对于UV维度可以大量的抛弃信息。
实际使用中由于小数的精度和性能优化，可能导致实际处理中出现一丢丢数据丢失。
当然这一丢丢数据的丢失我们可以接受，然后就可以进入下一部分了。

三、缩减取样

既然有损压缩代表需要抛弃部分数据，那我们主动抛弃一些数据吧。
比如一整图片像素那么多，常见的方式是在U和V维度隔一行取一个信息.
这样在UV维度上数据直接较少一半了.

这一部分是第一次对数据有损抛弃，两个维度直接减少了一半，整体的话就是减少了三分之一。

四、DCT变换

DCT变换的含义是离散余弦变换。

色彩空间转换小节中我们看到RGB数据三个维度是完全等价的，导致不能尽情的抛弃数据。
于是我们转化为YUV数据，然后就可以对UV维度尽情的抛弃数据还不会影响整体数据质量。

那现在我们遇到同样的问题。
对于YUV每一维度都是一个矩阵，矩阵的每一个点对我们来说还是完全等价的。
我们能不能对矩阵进行转化，然后就可以对矩阵的一部分数据尽情的抛弃数据呢？

这样变换的方法有很多，比如傅里叶变换，Walsh-Hadamard变换，正弦变换，余弦变换，斜变换，哈尔变换，K-L变换等等。
这里采用的是余弦变换。
余弦变换后的效果是矩阵左上角的数据权重较高，对于右下角的数据权重较低。

这些变换和色彩空间转换一样，都是可逆的，无损的。
但是变换后的特性允许我们对不同部分的数据进行不同程度的有损。

五、量化

量化的作用就是对于权重较低的数据进行大量有损抛弃，而对权重较高的数据稍微有损抛弃。
这里实际操作就是对矩阵的每个数据进行若干比例的缩小。
矩阵的数据缩小之后有了另外一个特性：大多连续数据是相同的了，右下角的数据大部分是0了。

这里需要提到的一点是对矩阵等比例缩小实际上就是乘以另外一个矩阵。
而这个矩阵称为量化表，一般这个量化表是固定的。

前段时间google宣传提高了JPEG的压缩率，实际上就是找到了一个整体情况更好的量化表。
由于最终有损压缩出的图片很难使用机器或算法来判断是否优劣，所以这里就没有更好的方法来自动计算最优的量化表了。
google之所以得到了更好的量化表，是使用数据挖掘（机器学习？）模拟了人眼，然后用这个人眼来反馈图片的压缩质量，最终找到更好的量化表。

六、熵编码技术

我们使用量化表抛弃了很多影响不大的信息，但是我们并没有进行任何压缩，只是为这一步的压缩准备了条件。
上面提到了，量化后有个特性：大多连续数据是相同的。
于是我们就许要编排数据，然后使用Huffman算法进行无损压缩。

是的，这一步的优化也是无损可逆的。
而且实际处理中为了性能，我们往往是已经有一个经验码表。
这样就不需要进行Huffman概率计算了。

唯一的缺点就是JPEG中没有储存这个码表，这样导致这个码表用于没办法更新了。
当然，码表也比较大，如果储存起来也极大可能导致压缩后数据更大的可能性了吧。

七、总结

JPEG经过五大步操作，JPEG图片就完成了压缩。
可以看到这个压缩算法分工很明确：

算法上：

色彩空间转换，DCT变换都是无损可逆的转换算法。
缩减取样和量化是有损可逆的算法。
熵编码技术是无损可逆压缩算法。

依赖上:

色彩空间转换算法为缩减取样与量化做好了准备：维度的轻重分离。
DCT变换也为量化做好准备：矩阵的轻重分离。
量化为熵编码技术做好了准备：重复数据连续性特点。

这个算法挺有意思的，后续遇到其他有意思的算法继续分享给大家。

八、参考资料

• 主要是部门的分享，了解了这个算法的思想
• wikipedia JPEG
• 论文 Digital Signal Processing

九、其他文章

• 每秒千万级别的量是重生还是炼狱?
• 每秒千万每天万亿级别服务之诞生
• 排名算法
• 什么是协议

对了，我建了一个小密圈算法的世界，欢迎进来交流算法知识。
这个小密圈目前一年需要收50人民币，算下来大概一天收一毛三分钱吧，可以考虑加入我的圈子。

长按图片关注公众号，接受最新文章消息。