【多媒体】PNG简介
（本文改自多媒体导论我课上做的演讲）转眼就暑假了，这一篇我在4月份准备写结果写了一半就坑到了现在，也是很真实。
有个图片格式大家平时网上冲浪特别是如果你自己制作或者去导入表情包的时候常会见到。这个图片格式就是png，平时我写的这些文章很多时候用的图片或类似下面这张图片就是png（PortableNetwork Graphics便携式网络图形）。今天就来简单介绍一下这个图像格式。
png是一种常见的无损压缩图片格式。在说png前，我们来提提png的历史。说历史就不得不提一下它的对手gif，下面这个会动的超可爱的小姐姐就是一张gif图片。
gif诞生于1987年，是一种使用LZW算法的无损压缩格式。它的压缩率还行，且因为能在一个文件中存入多幅图像以达成动画效果而广为使用。但是发明它的公司（Unisys）在它大火的1995年开始就它的压缩专利收费。迫于贫穷，人们开始寻找新的压缩格式来代替它，仅仅过了几个月——1996年——png横空出世。凭借更好的压缩率，对透明效果的支持，更艳丽的颜色，还有最重要的免费等特性，加上天时地利的1999年gif全面收费，png一炮而红。
那么刚才说了png的几个特性，各自都是怎么实现的呢？首先想介绍其他的图像类型一样，先介绍文件的结构。png是由下图这么多的数据块组成的，一眼看去会觉得很多，记不住，那就主要看划着红线的这四个，我们来细化它们。
耐心看看就很好理解，png的文件结构主要是由开头，调色板，主要数据，还有结尾组成的。其中调色板是用于进行索引颜色用的，也就是将图片中出现的颜色进行有限编码用的。由于索引颜色在有些时候会导致有损压缩，而这里讲到的png是无损压缩类型的，故这里就不展开来讲了，同样其他有损压缩算法中常见的量化，变换，二次采样等步骤在这里也见不到。
然后呢Png的每个数据块由下面这四个部分组成。长度，类型，数据本身，还有错误检测CRC码，其中CRC码的算法比较复杂，也不深入讲。
接下来在讲各个数据块之前，先说一下，每个PNG文件的开头都是固定的一串十六进制数字，这串被称为“魔数”的数字是用于表明文件的真正类型，从这里我们也可以明白，只是修改文件的后缀名有时候是没有用的，后缀名并不是一切。
（8950 4e47 0d0a 1a0a便是png的魔数）
然后是每个png的开头数据块——文件头数据块。文件头数据块记录了png的一些基本信息，可以理解为png的大纲或者是身份证。不要看到似乎很多东西就觉得很复杂，其实很多我们都认识。宽度，高度，然后是图片的类型，灰度图和真彩色很好懂，索引彩色也就是刚才说到的调色板。下面的颜色类型也就是细化了一下，然后压缩算法png是固定的，也是接下来要讲的重点——deflate算法。而滤波器是一种优化压缩的方法，扫描方法比较常见的就是逐行扫描，可以理解为字面意思，一行一行扫描，隔行扫描会稍微复杂一点，可以理解为按照一定规律跳着扫描。
说完png的文件头，接下来来说图像数据块。下面这张图就是png图像数据块的处理过程。图像数据块与平时的图像数据差不多，来源也是RGBA值，区别就是这部分利用了刚才说到的压缩算法和滤波器了进行了压缩。
那么说到了压缩部分，先来说说压缩算法，刚才说到的png用的唯一算法是Deflate算法，Deflate算法是1993年菲尔·卡茨发明的，这位大佬还是zip格式的发明者，可惜有个悲惨的人生。他的Deflate算法其实就是是把当时很流行的LZ77编码和之前说过的那个Huffman编码（【CPP】各种各样的树（8）——赫夫曼树）连接在了一起。首先使用LZ77编码对文件进行预编码，然后使用Huffman进行再次编码以压缩文件。之所以要使用它的一个原因就是先前历史中说到的gif对另一流行的LZW算法收费了。
菲尔·卡茨（Phil Katz）
既然知道了Deflate算法的组成，那重点就自然就到了LZ77编码。LZ77编码是Lempel与 Ziv两个大佬在1977年的论文提出的，所以叫LZ77。一年后还出现了效率更好的LZ78编码，但是那个没这个流行，原因也是版权问题。LZ77编码是使用了一个叫做“滑动窗口”的动态字典压缩，主要是用到了字符串的匹配，这样说自然完全不能明白，这里来看看网上找到的例图来进一步理解理解。
首先是LZ77的编码部分：
1.现在有个待编码的字符串。一开始是还没有开始编码的样子。图中黑色框内部是绿色的是滑动窗口，深蓝色的是缓冲区，浅蓝色的是还没读到的字符，右边黑框是编码后的字符串。我们需要右移滑动窗口来进行字符串匹配查找来编码。
2.然后开始，现在窗子里什么都没有，也就是窗子里没有东西能和缓冲区的字符匹配，那么缓冲区第一个字符“A”就编码为A。
3.然后右移一下窗子1位，窗里出现了A，第一个缓冲字符是B，滑动窗口中没有字符可以与缓冲字符匹配，于是直接编码B。
4.再右移窗子1位，现在我们看到匹配了，缓冲区以第一个字符为首的最长匹配串是“AB”，我们把它们编码为一组三元数，分别是偏移值，也就是匹配串的开头与窗子最左边从零开始计数的偏离值，是6；长度即匹配串的长度，是2；还有新字符的编码，也就是匹配失败的那个C。编码为(6,2,C)并写入字符串中。
5.这样我们完成一次匹配，一口气让窗子右移过ABC三个字符，然后再重复上面的匹配步骤，这次是匹配了“BAB”，新字符是A，编码为(4,3,A)。
6.再右移4位(BABA)，现在缓冲区字符（BCAD）在滑动窗口位移2的位置匹配到短语BC，于是将BC编码为(2,2,A)。
7.然后右移，发现缓冲区字符为D，在滑动窗口中没有找到匹配短语，编码为D计入字符串。
8.最后发现缓冲区没有字符了，代表我们编码结束，可以输出最终的字符串了，即右边的AB(6,2,C)(4,3,A)(2,2,A)D。仔细回顾一下过程就会发现其实LZ77也并不复杂。
然后是LZ77的解码部分：
1.理解了LZ77的编码后，和大多数压缩算法一样，解码其实就是编码的逆过程。首先我们有一个LZ77编码后的字符串，同样构造一个读取条，只不过这次的读取条是空的。
2.然后我们取字符串的第一个字，是单独的一个A，把它解码并放到滑动窗口的最末。
3.接下来我们将窗口右移一位，读取B放进最末。
4.然后我们读到一组偏移值，对其进行相同的解码，先取滑动窗口的第6位起的2个字符组成的串，然后右移窗口2+1位，然后把串放进去，再放入新字符C，解码偏移组完成。
5.如此循环往复，解码(4,3,A)和(2,2,A)得到解码字符串。
6.最后解码单独的一个D，解码便完成了。可以看出，解码其实就是编码的逆过程而已，只要理解了编码的原理，也就可以进行解码操作了。
那么LZ77编码的特性是什么呢？
LZ77编码在目标有大量重复字符串，类似文章中有大量排比句的时候，压缩率相对huffman是比较高的。这是因为huffman编码依赖于字符出现频率的不同，但由于重复字符串中的字符出现频率可能会很接近，会导致huffman直接压缩效率很低。但是在LZ77压缩里，我们可以对这样的情形进行压缩，且我们得到的新字符串有希望使字符出现的频率变得很不同，因为会有大量的重复数字和字符夹杂。再然后，由于频率变得不同，我们就想到假如再利用huffman编码进行二次压缩，说不定可以达到更好的压缩率，这其实就是刚才说到的deflate算法的原理了。
但是LZ77算法也有个很大的缺点，那就是由于频繁地要进行字符串匹配查找，如果没有进行其它的优化的话，它的压缩速度会比huffman慢很多很多。且为了增加匹配成功的几率，我们需要加大滑动窗口的大小，这又进一步地增加了压缩的耗时。好在相对的它的解压速度非常快，几乎感觉不到解压的时间。
然后到了过滤器(fliter)部分，过滤器其实是另一种很常见的编码——差分编码(Delta encoding)。关于这个编码说不定之后会详细写篇文章，所以这里就简单写一下，主要的思想就是根据前一个数据的值将后面的值替换成两个数据之间的差值。简单的效果就是下面的图，图中的数值是图片的像素值。关于过滤器png有五种过滤器可供选择，除了比较复杂的Paeth推断外，其他效果都可以简单地在图中看出。
而关于png如何选择合适的过滤器，由于差分编码就是希望数据可以利用差值被集中在较小的值附近，以此来降低编码位数，所以主要的做法就是利用各种过滤器都对图像计算一次，然后求每行每个值的绝对值相差最小，也就是绝对值之和最小的一种方法。如果对结果都不满意的话，直接使用NONE模式即不处理就可以了。
再回顾一下我们对图像数据块压缩的这一部分操作。先有一张图片，各个像素都不同，我们通过过滤器的差分编码我们降低数据的差异，然后通过LZ77合并差分后可能出现的大量重复字符串，然后在利用huffman编码缩写整个文档，这就是png压缩部分的秘密了，回顾下面的图巩固一下w。
最后在压缩完主要数据后就剩一些细枝末节，png会删除掉一些冗余的数据，然后就到了png的结尾数据块了。每个png的结尾数据块其实不难理解，由于数据块结构的定义，IEND数据块的长度总是0（00 00 00 00，除非人为加入信息），数据标识总是IEND（49 45 4E 44），因此，校验用的CRC码也总是AE 42 60 82。
到此为止，png结构的大致内容就简单梳理了一下了，还有很多其他的数据块没有说，那些有兴趣自己去网上找资料就好。
到最后结尾接一下开头说的历史的后续。开始时说到，png是由于gif的专利收费而被逼出来的。由于gif的收费，png迅速崛起，快速抢占了gif的市场，最终我们可以看到如今网络世界中png和gif平分天下。这里我找到了一份相当久远的文章，03年的人们还在思考着gif专利过期后能否重新占领市场，也是很有趣的一件事情。
Gif最终确实抢回了不少市场，但是再没能打败png了。而这次讲的重点的deflate算法如今已经被频繁地使用，但它的发明者菲尔·卡茨，我当时说它有一个悲惨的人生，这个极客也许由于少年时成长环境的不佳导致性格一直不太好，在发明zip一夜暴富后又开始酗酒，频繁因酗酒驾驶而被追捕，一个好好的人在成功后不久就一路堕落，没有人知道他身上发生了什么，他最后的岁月常常不知所踪，最后在2000年4月14日被发现死于一个酒店的房间，终年37岁。死因是酒精导致的严重胰腺出血，身旁是一堆的空酒瓶。他最终没能看到自己的deflate算法统治世界的时候。所以说不要酗酒。