PNG格式的压缩算法原理

大家好，欢迎来到IT知识分享网。

在过去的几十年里，PNG(便携式网络图形)已经成为应用程序开发的主要部分。从游戏开发到web开发，再到Android开发，它无处不在，这意味着它被广泛采用，但也有被广泛滥用的机会。

正如我之前所讨论的，PNG提供了一种不错的高分辨率图像格式，但这意味着在数据压缩方面还有很大的改进空间。但是在我们开始讨论如何进一步压缩PNG文件之前，我们必须先讨论格式是如何工作的。

了解压缩

PNG的压缩过程是完全无损的;这意味着压缩文件可以准确地重建源图像。分两个阶段完成:预测(又名过滤)和压缩。

1 过滤器(预测)

增量编码是最强大的数字压缩方法之一,基本思想是您可以将任何值表示为与前一个值不同的值，所以：

[2,3,4,5,6,7,8]会变成[2,1,1,1,1,1,1]，其中

[2, 3-2=1,4-3=1, 5-4=1, 6-5=1, 7-6=1, 8-7=1]

这之所以如此强大，是因为如果数据是线性相关的(也就是说，值与前一个值有一些很小的差异)，那么最终会将数据集的值转换为大量重复的小值，这些小值更容易被压缩。
PNG格式使用称为“filtering”的delta编码格式。基本上，对于每一个像素扫描线，当前像素都是按照与左边像素、上面像素和上面左侧像素的某种关系进行编码的。

例如，如果我们用A和B的平均值的差值(X-(((A + B)/2)来编码一个给定的像素，那么我们会得到:

过滤器使用用ABC来预测x的值，使用预测值和实际值之间的差来代替X的值。

现在，值得注意的是，每一行只有很小的差异，PNG允许选择五种模式中的一种，每行:

1. 不使用filtering
2. X和A的差
3. X和B的差值
4. X与(A + B)/2的差值(即平均值)
5. Paeth预测器(A,B,C的线性函数)

这里的意图是，每一行都可以为自己选择最好的filtering方法，这样就可以产生最少的唯一符号（重复符号越多，压缩效果越好）。这是我们每个模式的原始例子:

需要注意的是，这些过滤器是按通道而不是按像素设置的。这意味着该过滤器应用于扫描线的一个像素的所有红色值，然后单独应用于扫描线的所有蓝色值(尽管一行中的所有颜色将使用相同的过滤器)。

PNG格式有一些很好的方式来选择在一个通道上使用哪个过滤器；虽然蛮力是最直接的，但结果并不理想，相反，开发人员在不同的图像类型上进行了试验，并提出了一些接近最优的经验法则：比如对调色板图像以及低于8位的灰度图像不使用过滤器；对于其他的图像，选择最小化绝对差和的滤波器；不是使用256模除(%)，而是使用标准的带符号数学，然后获取abs值，并将它们全部添加到给定行中，然后比较其他筛选器类型的和，选择给出最小和的过滤器。

2 压缩(DEFLATE)

一旦在扫描线上进行了滤波，它将传递给LZ77算法的变种，称为DEFLATE；该算法结合了LZ77编码和一个霍夫曼编码器。它与PKWARE、PKZIP、GZip等压缩器几乎相同。这个实现是开箱即用的标准，但是对于图像数据有一些有趣的注意事项：

1. Deflate限制3到258个符号之间的匹配长度；这使得可以想象的最大压缩比约为1032:1。
2. 如果匹配的符号小于3个，那么您将产生一些开销(overhead)来表示符号

这两个的结果，意味着如果在扫描线中找到匹配项，图像的大小可能会有影响。

考虑下面这张图，270×90版本只有20k，但是270×92版本大了2倍。

从逻辑上看，这似乎是错误的。在一张图片上增加540个像素应该不会导致2倍的压缩膨胀。然而，当我们仔细观察时，我们可以看到为什么会发生这种情况，下面的图像热图表示给定像素的压缩程度。深蓝=高度压缩，黄色/红色=非高度压缩(压缩率不高)

之所以发生这种情况，虽在较小的图像中，扫描线有更多的匹配，因此有更好的压缩率。但是，稍微调整一下大小，就会改变可能出现的匹配类型，一些可能的匹配对象现在在我们的LZ窗口之外，因此没有被匹配，导致文件变大。

至于LZ77和哈夫曼编码，话题太大，本文就不再展开，相关的文章很多，读者可以自行搜索。