作者：vivo 互联网数据库团队- Li Shihai
本文次要介绍无损压缩图片的概要流程和原理，以及Lepton无损压缩在后期调研中发现的问题和解决方案。
一、从一个游戏开始
1.1 游戏找茬
请拿出你的秒表计时，在15秒工夫内找出上面图片的差别。
工夫到了，你发现两张图片的差别了吗？
二、智者的成长
在下面的游戏中，你可能你并没有发现两张图片间有任何差别，而实际上它们一张是3.7MB的jpg格局的原图，另外一张是大小为485KB的jpg格局压缩图片，只是大小不同。你可能会有些怄气，愤愤不平到这是坑骗，然而聪慧的你很快在大脑中产生了一连串的疑难，这些问号让你层层揭开游戏的面纱，不在为愚弄而懊悔，反而从新知中取得高兴。
2.1 苏格拉底助产术
- 下面图片为何变小了呢？
- 失落了的信息去哪了呢？
- 为什么图片品质降落了，我却看不出来呢？
- 我还能将它变的更小吗？
- 我能将它还原成原来的大小吗？
- 为什么要压缩我的图片？
下面图片为何变小了？图片从3.7MB变成485KB是因为我应用了图片查看工具将原图另存成一张新的图片，在另存的过程中，有一个图片品质抉择的参数，我抉择了品质最低，保留后便生成了一张更小的图片。可是图片品质降落了，为什么看不出来呢？这就须要理解图片压缩的原理。
2.2 探究表象背地的故事
利用人眼的弱点。
人的视网膜上有两种细胞，视锥细胞和视杆细胞。视锥细胞用来感知色彩，视杆细胞用来感知亮度。而绝对于色彩，咱们对明暗的感知更显著。
因而能够采取对色彩信息进行压缩来减小图片的大小。
所以咱们在图片压缩前会进行色彩空间的变换，JPEG图片通常会变换成YCbCr色彩空间，Y代表亮度，Cb蓝色色调度，Cr红色色调度，变换后咱们更容易解决色调局部。而后咱们将一张图片切成一块块8*8的像素块，而后应用离散余弦转换算法(DCT)计算出高频区和低频区。
因为人眼对高频区的简单信息不敏感，因而能够对这一部分进行压缩，这个过程叫量化。最初再将新的文件进行打包。这个流程下来就实现了图片的压缩。
根本流程如下图：
JPEG压缩有损。
在下面的流程中，在预测模块的色彩空间转换后，通过舍弃局部色彩浓度信息，进步压缩率。常见选项为4:2:0，通过这一步后原来须要8个数字示意的信息，当初只须要2个，间接摈弃了75%的Cb Cr信息，然而这一步骤是不可逆的，也就造成了图片压缩的有损。此外在熵编码模块，会进一步应用行程长度编码或Huffman编码进一步对图片信息进行压缩，而这一部分的压缩是无损的，是可逆的。
（YCbCr空间转换）
霍夫曼编码原理如下：
如果待编码的字符总共38个符号数据，对其进行统计，失去的符号和对应频度如下表：
首先，对所有符号依照频数大小排序，排序后如下图：
而后，抉择两个频数最小的作为叶子节点，频数最小的作为左子节点，另外一个作为右子节点，根节点为两个叶子节点的频数之和。
（Huffman 树）
通过下面的步骤，就造成了一颗Huffman树，Huffman编码常常用在无损压缩中，其根本思维是用短的编码表示呈现频率高的字符，用长的编码来示意呈现频率低的字符，这使得编码之后的字符串的均匀长度、长度的期望值升高，从而实现压缩的目标。
三、故事的配角 Lepton
不完满。
下面的JPEG压缩尽管升高了图片的大小且品质良好以至于人眼很难分辨其差别，然而因为是有损的压缩，图片品质不能复原到原来的品质，而且实际上此时的jpg图片仍有压缩空间。
Lepton便能够在JPEG根底上进一步对图片进行无损压缩。
3.1 为什么抉择 Lepton
与lepton相似的压缩工具还有jpegcan，MozJPEG，PackJPG，PAQ8PX。但这些工具都或多或少有一些缺点，使得不如lepton更加适宜工业生产。
比方PackJPG须要依照全局排序的程序重新排列文件中的所有压缩像素值。这意味着解压缩是单线程的，同时须要整个图像放入内存中导致解决图片的时延较高吞吐较低。
下图是lepton论文中对几款工具的比拟：
3.2 Lepton进行了哪些优化。
首先在算法上Lepton将图像分为两局部header和图片数据自身，header应用DEFLATE进行无损压缩，图片自身应用算数编码替换霍尔曼编码进行无损压缩。因为JPEG应用Huffman编码，这使得利用多线程比拟艰难，Lepton应用"Huffman切换词"进行了改良。
其次Lepton应用了一个简单的自适应概率模型，这个模型是通过在大量的野外图像上进行测试而开发的。该模型的指标是对每个系数的值产生最精确的预测，从而产生更小的文件；在工程上容许多线程并发解决，容许分块跨多个服务器分布式解决，流的形式逐行解决无效的管制了内存，同时还保障了数据读取和输入的平安。
正是Lepton在上述关键问题的优化，使得它目前能够很好的在生产环境中应用。
3.3 Lepton在vivo存储中的摸索
预期收益：
目前对象存储其中的一个集群大概有100PB数据，其中图片数据大略占70%, 而图片中有90%的图片都是jpeg类型图片，如果依照均匀23%的压缩率，那么 100PB 70% 90% * 23% = 14.5PB，将实现大概14.5PB的老本节约。
同时因为是无损压缩，很好的保障了用户的应用体验。以后lepton压缩性能的设计如下图：
以后遇到的挑战：
- lepton压缩与解压缩对服务器的计算性能要求较高、耗费较大。
- 冀望充分利用闲暇服务器CPU资源，达到降本增效的目标。
- 面对潮汐景象具备动静扩缩容的能力。
以后面临的次要问题：
以后大部分图片的大小在4M-5M， 通过测试对于4M-5M大小的文件压缩时延在1s左右的状况下，须要服务器至多16外围、承载5QPS。此时每个外围的利用率都在95%以上。可见 Lepton的压缩对计算性能要求很高。以后常见的解决方案是应用FPGA卡进行硬件加速、以及横向扩容大量的计算节点。FPGA的应用会减少硬件老本，升高压缩带来的老本收益。
解决方案：
为了解决上述问题及挑战，咱们尝试采纳物理服务器和Kubernetes混合部署的形式解决计算资源的应用和动静扩所容的问题，架构示意图如下：
对于物理服务器的治理以及扩所容通过服务的注册于发现进行弹性扩所容、通过此cgroup/Taskset等形式对过程的cpu应用进行治理。同时对接应用Kubernetes以容器的形式进行治理、容器的灵活性更加适宜这种计算型的服务。
3.4 性能评测
无论是同步压缩，还是异步压缩，通常更加关注图片读取的延时。大量的图片读取会给服务器带来较大的压力，压力次要来自于图片的解压计算。为了进步解压缩效率，以及充分利用公司的资源，咱们将来将lepton压缩服务以独立的服务模式散布于cpu闲暇的服务器，能够依照资源闲暇水平，闲暇工夫，充分利用资源的峰谷来进步计算性能。
压测数据：
咱们选取了不同大小的图片文件，在单机环境下进行了压缩与解压缩测试，测试后果如下图：
压缩比均匀放弃在22%左右。
上图是不同大小的文件压缩与解压缩工夫比例图，橙色是解压工夫，蓝色是压缩工夫。
上图是不同大小的图片，在32线程并发，每个线程解决100个文件的测试数据。
四、 图片压缩的常见问题
4.1 通过文件格式辨别有损和无损压缩
4.2 常见的无损压缩算法
五、 总结
Lepton的无损压缩可能提供比拟高的压缩比，同时不影响用户的图片品质和应用体验、在大数据量的场景下会取得比拟显著的收益。
不足之处是对计算性能要求较高、只反对jpeg类型的图片。对于性能的要求行业内也都有比拟成熟的解决方案，例如上文提到的FPGA和弹性计算计划。关键在于依据企业需要抉择正当的计划。
援用：
- 《The Design, Implementation, and Deployment of a System to Transparently Compress Hundreds of Petabytes of Image Files For a File-Storage Service》
- 《基于深度学习的JPEG图像云存储钻研》
- 《JPEG-Lepton压缩技术要害模块VLSI结构设计钻研》