文档介绍：图像无损压缩算法综述
图像无损压缩算法综述
【摘要】 本文介绍了常见的图像无损压缩方法：静态及动态霍夫曼(Huffman)编码算法、算术编码算法、LZW ( lanpel-ziv-velch)编码及其改进算法、行程编码（又称游程编码，RLE）及改进自适应游程编码算法、费诺-香农编码算法和一种改进的编码方法。简要分析了各种算法的优缺点。
【关键词】 霍夫曼 算术编码 LZW 行程编码 费诺-香农编码
1 前言
随着技术的不断发展，多媒体技术和通讯技术等对信息数据的存储和传输也提出了更高的要求，给现有的有限带宽带来更严峻的考验，尤其是具有庞大数据量的数字图像通信。存储和传输的高难度极大地制约了图像通信的发展，因此对图像信息压缩技术的研究受到了越来越多的关注。压缩数据量是图像压缩的首要目的，但保证压缩后图像的质量也是非常重要的，无损压缩是指能精确恢复原始图像数据的压缩方法，其在编码压缩过程中没有图像信号的损失。本文介绍了常见的无损压缩方法：静态及动态霍夫曼(Huffman)编码算法、算术编码算法、LZW ( lanpel-ziv-velch)编码及其改进算法、行程编码（又称游程编码，RLE）及改进自适应游程编码算法、费诺-香农编码算法和一种改进的编码方法。
2 常见图像无损压缩算法
霍夫曼算法
Huffman算法是一种用于数据压缩的算法，。它完全依据字符出现概率来构造平均长度最短的编码，有时称之为最佳编码，一般叫做Huffman编码。频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。
静态霍夫曼编码
步骤：
（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编码。
自适应霍夫曼编码
这种方案在不需要事先构造Huffman树，而是随着编码的进行，逐步构造Huffman树。同时，这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。
在构造动态霍夫曼编码树的过程中，需要遵循两条重要原则：
（1）权重值大的节点，节点编号也较大。 
（2）父节点的节点编号总是大于子节点的节点编号。
以上两点称为兄弟属性（sibling property）。在每一次调整节点权重值时，都需要相应的调整节点编号，以避免兄弟属性被破坏。在对某一个节点权重值进行“加一操作”时，应该首先检查该节点是否具有所在的块中的最大节点编号，如果不是，则应该将该节点与所在块中具有最大节点编号的节点交换位置。然后再对节点的权重值加。这样，由于该节点的节点编号已经处于原来所属块中的最大值，因此权重值加一之后兄弟属性仍然得到满足。最后，由于节点的权重发生了变化，必须递归地对节点的父节点进行加一操作。
在需要插入一个新符号时，总是先构造一个新的子树，子树包含NYT符号与
图1 算术编码流程图
固定模式编码需要预先对符号序列中的符号进行预扫描，根据统计符号的概率来列出编码概率表。引入几个变量：low为编码间隔的低端，rang为编码间隔的长度,ranglow为编码字符的间隔的低端, ranghigh为编码字符的间隔的高端。在固定模式编码中，ranglow和 ranghigh的编码概率不变。计算流程如图1。
用例子说明算术编码编解码原理，采用固定模式符号概率分配表见表1。若要编码字符串’eai’，则编码过程如图2 。
表1 算术编码字符概率分配表 图2 算术编码示意图
算术编码解码原理
图3 解码流程图
从原理上讲，解码的过程是编码的逆过程，只要保证编码和解码使用同样的字符概率分配表，解码后的字符就不会出现误差。根据编码时所使用的字符概率区间分配表和压缩后的数值代码