浅谈PNG无损优化

前段时间在知乎回答了个问题，居然一个赞都没有，还是在博客发一下吧。

PNG无损优化的核心原理很简单，通俗的解释一下，就是由于PNG格式的灵活性，他可以有很多种方式表示同一张图片，不同方式有时就会导致文件大小不一样，而到底哪种方式是最好的，除了拿图片来试并没有太好的选择方法，所以一般的软件为了速度，并不会过多的纠结到底要用什么方式，这样必然不是最优的，优化空间就这么产生了。

还有一点是PNG采用的是deflate算法，也非常的灵活，他的压缩率和encoder的实现有关，不同的encoder使用的时间，压缩出来的大小都不一样，即使使用同一encoder，选择的参数不同，也会导致压缩出来的大小不同。一般来讲压缩率排行如下zopfli > kzip > lzma sdk > zlib 。还有一种程序，DeflOpt和defluff，他们本身并不是encoder，但是他专门负责在不重新压缩的情况下（也就是说他的速度非常快），优化别的encoder压缩的结果，一般都是针对Huffman Tree的一些操作，最终都能抠出几个字节。

当然除了上面这两点是真正的无损压缩以外，还有减小PNG文件大小的方式就是去除一些对图片本身没有任何影响的metadata，比如iTXt、tEXt和zTXt区段可以存任意文本，一般都是生成这个PNG的软件的信息，iCCP区段存的ICC profile，gAMA存的gamma值等等。

下面具体讲一下PNG格式到底有多灵活，有哪些优化空间。

• 首先是bit depth的选择，他表示每个sample需要多少个bit来表示，注意sample不是像素，一个像素等于几个sample与图片的颜色有关，灰度图片就是1个，RGB就是3个，RGBA就是4个。一般来讲肯定是bit depth越小越好，但是由于最终的图片数据是被deflate压缩的，有的时候bit depth故意选大一点反而压缩出来更小。
• 储存颜色可以选择直接以RGB的方式每个像素点储存，或者如果总颜色数量不超过256，可以将所有颜色储存到palette中，给palette中的每个颜色编号，后面的每个像素点只需要储存编号即可，这样就减小了文件体积。但也不是绝对的说采用palette就一定会比不用好，确实是存在反例的。
• 如果使用palette，那么给这些颜色每个编多少号，对最终的大小也会有影响，因为图片数据是用deflate压缩的，那么有的编号方式就会比别的编号方式编码出来的图片数据更利于deflate压缩。
• 如果图片带透明，又可以选择直接以RGBA的方式储存或者以不透明的方式储存然后加入tRNS区段来标记透明的颜色。
• 然后就是最重要的filter的选择了。filter就是在进行压缩之前，先对数据进行一个可逆的预处理，用来提高压缩率。filter有0-4这5种，分别是None、Sub、Up、Average、Paeth。选择不同的filter对压缩大小也会产生很重要的影响。这个filter并不是整个图选一个，而是每行都可以选择不同的，所以假如总共有n行，也就是图片的高度是n，那么总共的可能性就是5的n次方。因为filter是基于周围像素的预测，所以每行的选择并不是独立的，而是相互影响的。
• 如果图片包含全透明的像素点，那么由于颜色是用RGBA来表示的，只要Alpha是0，RGB的值对图片显示不会有任何影响，可以随意操纵的，一般改成比较有规律的值，就可以提高deflate压缩率，但具体怎样改，不同程序的策略都不太一样。

由此可见，给出一个PNG文件，把他压缩成最小，应该是个NP-hard的问题，即使拿一个很小的图片，把以上提到的所有情况都试一遍，也无法证明得到的文件就是最小的，因为deflate的encoder实现也许并不是最优的，比如在2013年Google的zopfli出来之前，没有人知道deflate这个古老的压缩算法还有如此大的优化空间。