图像无损压缩算法综述 【摘要】 本文介绍了常见的图像无损压缩方法：静态及动态霍夫曼(Huffman)编码算法、算术编码算法、LZW ( lanpel-ziv-velch)编码及其改进算法、行程编码（又称游程编码，RLE）及改进自适应游程编码算法、费诺-香农编码算法和一种改进的编码方法。简要分析了各种算法的优缺点。 【关键词】 霍夫曼 算术编码 LZW 行程编码 费诺-香农编码
1 前言 随着技术的不断发展，多媒体技术和通讯技术等对信息数据的存储和传输也提出了更高的要求，给现有的有限带宽带来更严峻的考验，尤其是具有庞大数据量的数字图像通信。存储和传输的高难度极大地制约了图像通信的发展，因此对图像信息压缩技术的研究受到了越来越多的关注。压缩数据量是图像压缩的首要目的，但保证压缩后图像的质量也是非常重要的，无损压缩是指能精确恢复原始图像数据的压缩方法，其在编码压缩过程中没有图像信号的损失。本文介绍了常见的无损压缩方法：静态及动态霍夫曼(Huffman)编码算法、算术编码算法、LZW ( lanpel-ziv-velch)编码及其改进算法、行程编码（又称游程编码，RLE）及改进自适应游程编码算法、费诺-香农编码算法和一种改进的编码方法。 2 常见图像无损压缩算法
2.1 霍夫曼算法 Huffman算法是一种用于数据压缩的算法，由D.A.Huffman最先提出。它完全依据字符出现概率来构造平均长度最短的编码，有时称之为最佳编码，一般叫做Huffman编码。频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。 2.1.1 静态霍夫曼编码 步骤： （1）将信号源的符号出现的概率（在此称为权值）{w1，w2，...，wn}构造成n棵二叉树集合F={T1，T2，...，Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空。 （2） 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和 （3）在F中删除这两棵树，同时将新得到的二叉树加入F中。 （4）重复（2）和（3），直到F只含一棵树为止，这棵树便是霍夫曼（Huffman）树。 （5）在合并中约定权值小的根结点在左子树上，权值大的在右子树上，然后在每个左分支上标记为“0”，右分支上标记为“1”，最后记录从霍夫曼（Huffman）树的根结点到每个叶子结点所经过的分支上的“0”或“1”的序列，从而得到每个符号的Huffman编码。 2.1.2 自适应霍夫曼编码 这种方案在不需要事先构造Huffman树，而是随着编码的进行，逐步构造Huffman树。同时，这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。 在构造动态霍夫曼编码树的过程中，需要遵循两条重要原则： （1）权重值大的节点，节点编号也较大。 （2）父节点的节点编号总是大于子节点的节点编号。 以上两点称为兄弟属性（sibling property）。在每一次调整节点权重值时，都需要相应的调整节点编号，以避免兄弟属性被破坏。在对某一个节点权重值进行“加一操作”时，应该首先检查该节点是否具有所在的块中的最大节点编号，如果不是，则应该将该节点与所在块中具有最大节点编号的节点交换位置。然后再对节点的权重值加。这样，由于该节点的节点编号已经处于原来所属块中的最大值，因此权重值加一之后兄弟属性仍然得到满足。最后，由于节点的权重发生了变化，必须递归地对节点的父节点进行加一操作。 在需要插入一个新符号时，总是先构造一个新的子树，子树包含NYT符号与新符号两个叶节点，然后将旧的NYT节点由这个子树替代。由于包含NYT符号的节点权重值为0，而包含新符号的叶节点的权重值为1，因此最终效果相当于原NYT节点位置的权重值由0变为1。因此，下一步将试图对其父节点执行权重值“加一操作”。 对符号编码的方法与静态霍夫曼编码一致，每次符号编码完成以后，也将对包含符号的节点权值进行加一操作。将一个新的符号插入编码树或者输出某一个已编码符号后，相应的符号的出现次数增加了1，继而编码树中各种符号的出现频率发生了改变，不一定符合兄弟属性，按照上述方法进行调整，使其符合要求。 2.2 算术编码算法 算术编码完全抛弃了用特殊字符代替输入字符的思想。在算术编码中，输入的字符信息用0到1之间的数字进行编码，它用到两个基本的参数:符号的频 率及其编码间隔。对于输入的字符信息，算术编码后形成一个唯一的浮点数。算术编码的效率一般要优于哈夫曼编码，但实现要比哈夫曼编码复杂。 2.2.1 算术编码原理
图1 算术编码流程图 固定模式编码需要预先对符号序列中的符号进行预扫描，根据统计符号的概率来列出编码概率表。引入几个变量：low为编码间隔的低端，rang为编码间隔的长度,ranglow为编码字符的间隔的低端, ranghigh为编码字符的间隔的高端。在固定模式编码中，ranglow和 ranghigh的编码概率不变。计算流程如图1。 用例子说明算术编码编解码原理，采用固定模式符号概率分配表见表1。若要编码字符串’eai’，则编码过程如图2 。
表1 算术编码字符概率分配表 图2 算术编码示意图 2.2.2 算术编码解码原理
图3 解码流程图 从原理上讲，解码的过程是编码的逆过程，只要保证编码和解码使用同样的字符概率分配表，解码后的字符就不会出现误差。根据编码时所使用的字符概率区间分配表和压缩后的数值代码所在的范围，可以很容易确定第一个字符。设法去掉第一个符号对区间的影响，找到下一个符号。重复以上操作，直到完成解码过程。计算流程如图3。
2.3 LZW编码算法 LZW编码的基本思想是建立一个字典，将输入字符串编码成定长的码流输出(通常为12位)，并在编码过程中动态生成字典，算法是自适应的。但传统LZW算法存在占用大量的字典容量、生成的字典项较多时查找效率低等缺陷。故讨论一种改进LZW编码压缩算法进，将字典初始化为16位，采用散列法和拉链法进行词条检索，采用阈值判断和LRU淘汰机制改进条目更新的方式，编码时采用自适应变码长方式。经测试，相比于传统LZW编码数据压缩算法，改进的算法对不同码长的数据的适应性更好，并且压缩比提高了约8%。 2.3.1 LZW编译码
LZW编码是一种基于字典模型的无损数据压缩方法，由Lempel-Ziv-Welch
共同提出。通过建立一个字符字典，用较短的码字表示较长的字符串，达到数 据压缩的目的。在动态的建立字典的同时，字符串和码字之间逐渐建立关系。后续的字符串与字典进行比较，不断完善和壮大字典。生成的字典不需要随着数据一块存储和传输，在解压缩的过程中仍然能够重建一个完全相同的字典，从而进一步地提高压缩效率。在介绍LZ W编码流程之前，首先定义几个在LZ W编码、解码过程中出现的概念: P:当前前缀，表示在编码算法中正在被处理的前缀 C:当前字符，表示在编码算法中当前确定的字符。 cW:当前码字，当前被处理字符串对应的码字。 pW:先前码字，先前被处理字符串对应的码字。 String.cW:当前码字对应的字符串。 String.pW:先前码字对应的字符串。 LZW编码过程: 建立初始字典，该初始字典中包含待处理字符数据流中所有可能出现的字符。同时，设置前缀P为空；读取字符串数据流中的下一个字符作为当前字符，送至C中；判断P+C是否已经存在字典之中，若存在:P=P+C，用C来扩展P，若不存在：把表示前缀P的码字cW输出到编码数据流中。将字符串P+C按照顺序加入字典中，同时使P=C；判断字符数据流是否编码完毕，若编码完毕:编码完成，输出P所对应的码字cW到编码数据流结尾处，若未完成，则继续编码。
图4 LZW编码流程图 LZW译码过程: 建立初始字典，该初始字典中包含待处理字符数据流中所有可能出现的字符。读取编码数据流中的第一个码字cW。输出cW所对应的字符串String.cW到字符数据流中。 pW=cW，读入编码数据流中的下一个码字cW。判断cW对应的字符串String.cW是否在字典中?若在字典中:将String.cW输出到字符数据流，P=String.pW， C=String.pW字符串中的第一个字符，P+C添加到字典；若不在字典中:P=String.pW，C=String.cW中的第一个字符，输出P+C到字符数据流，然后将P+C添加至字典。判断码字流中是否还有待译码字?是:返回步骤pW=cW；否:译码结束。 图5 LZW解码流程图 2.3.2 改进的LZW编码 LZW压缩算法的执行速度依赖于字典查找的速度。在LZW压缩算法中，若直接检索字典，编码的速度很低，同时时间复杂度较高，为O(n2)。因此，选择一种效率较高的字典存储和遍历索引的方式是提高LZW编码效率的主要途径。为了提高字典的存储和索引效率，引入散列表(Hash Table)来存储字典，只需通过关键字就可以确定结点的存储位置，这样能有效提高字符串表的检索效率。 为了提高编码的效率，采用可变长度的编码方法。在系统中，使用的可变编码位数从8位开始，当编码长度超过了8位的表示范围，则自动增加到9位编码，依次递增编码位数。但增加编码位数使得算法性能和执行效率都受到影响，因此，设定编码长度的最大范围为12位，当编码超出12位(4096)表示范围，需要重新