图像无损压缩算法综述

1、图像无损压缩算法综述【摘要】本文介绍了常见的图像无损压缩方法：静态及动态霍夫曼(Huffman)编码算法、算术编码算法、LZW(lanpel-ziv-velch)编码及其改进算法、行程编码(又称游程编码，RLE)及改进自适应游程编码算法、费苦香农编码算法和一种改进的编码方法。简要分析了各种算法的优缺点。【关键词】霍夫曼算术编码LZW行程编码费诺-香农编码1前言随着技术的不断发展，多媒体技术和通讯技术等对信息数据的存储和传输也提出了更高的要求，给现有的有限带宽带来更严峻的考验，尤其是具有庞大数据量的数字图像通信。存储和传输的高难度极大地制约了图像通信的发展，因此对图像信息压缩技术的研究受到了越来

2、越多的关注。压缩数据量是图像压缩的首要目的，但保证压缩后图像的质量也是非常重要的，无损压缩是指能精确恢复原始图像数据的压缩方法，其在编码压缩过程中没有图像信号的损失。本文介绍了常见的无损压缩方法：静态及动态霍夫曼(Huffman)编码算法、算术编码算法、LZW(lanpel-ziv-velch)编码及其改进算法、行程编码(又称游程编码，RLE)及改进自适应游程编码算法、费诺-香农编码算法和一种改进的编码方法。2常见图像无损压缩算法2.1霍夫曼算法Huffman算法是一种用于数据压缩的算法，由D.A.Huffman最先提出。它完全依据字符出现概率来构造平均长度最短的编码，有时称之为最佳编码，一般

3、叫做Huffman编码。频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。2.1.1静态霍夫曼编码步骤：（1）将信号源的符号出现的概率（在此称为权值）wl,w2,.,wn构造成n棵二叉树集合F=T1,T2,.,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均为空。（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和（3）在F中删除这两棵树，同时将新得到的二叉树加入F中。（4）重复（2）和（3），直到F只含一棵树为止，这

4、棵树便是霍夫曼（Huffman）树。（5）在合并中约定权值小的根结点在左子树上，权值大的在右子树上，然后在每个左分支上标记为0”右分支上标记为1”最后记录从霍夫曼（Huffman）树的根结点到每个叶子结点所经过的分支上的“0”或“1”的序列，从而得到每个符号的Huffman编码。自适应霍夫曼编码这种方案在不需要事先构造Huffman树，而是随着编码的进行，逐步构造Huffman树。同时，这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变（变得更长或更短）。在构造动态霍夫曼编码树的过程中，需要遵循两条重要原则：（1）权重值大的节点，节点编号也较大。（2）父节点的节点

5、编号总是大于子节点的节点编号。以上两点称为兄弟属性（siblingproperty）。在每一次调整节点权重值时，都需要相应的调整节点编号，以避免兄弟属性被破坏。在对某一个节点权重值进行加一操作”时，应该首先检查该节点是否具有所在的块中的最大节点编号，如果不是，则应该将该节点与所在块中具有最大节点编号的节点交换位置。然后再对节点的权重值加。这样，由于该节点的节点编号已经处于原来所属块中的最大值，因此权重值加一之后兄弟属性仍然得到满足。最后，由于节点的权重发生了变化，必须递归地对节点的父节点进行加一操作。在需要插入一个新符号时，总是先构造一个新的子树，子树包含NYT符号与新符号两个叶节点，然后将旧

6、的NYT节点由这个子树替代。由于包含NYT符号的节点权重值为0，而包含新符号的叶节点的权重值为1，因此最终效果相当于原NYT节点位置的权重值由0变为1。因此，下一步将试图对其父节点执行权重值“加一操作”。对符号编码的方法与静态霍夫曼编码一致，每次符号编码完成以后，也将对包含符号的节点权值进行加一操作。将一个新的符号插入编码树或者输出某一个已编码符号后，相应的符号的出现次数增加了1,继而编码树中各种符号的出现频率发生了改变，不一定符合兄弟属性，按照上述方法进行调整，使其符合要求。2.2算术编码算法算术编码完全抛弃了用特殊字符代替输入字符的思想。在算术编码中，输入的字符信息用0到1之间的数字进行编

7、码，它用到两个基本的参数:符号的频率及其编码间隔。对于输入的字符信息，算术编码后形成一个唯一的浮点数。算术编码的效率一般要优于哈夫曼编码，但实现要比哈夫曼编码复杂。2.2.1算术编码原理图1算术编码流程图固定模式编码需要预先对符号序列中的符号进行预扫描，根据统计符号的概率来列出编码概率表。引入几个变量：low为编码间隔的低端，rang为编码间隔的长度,ranglow为编码字符的间隔的低端，ranghigh为编码字符的间隔的高端。在固定模式编码中，ranglow和ranghigh的编码概率不变。计算流程如图1。图2算术编码示意图用例子说明算术编码编解码原理，采用固定模式符号概率分配表见表1。若要

8、编码字符串eai，则编码过程如图2。子特it记ioU辭讥叮M叮2表1算术编码字符概率分配表2.2.2算术编码解码原理图3解码流程图从原理上讲，解码的过程是编码的逆过程，只要保证编码和解码使用同样的字符概率分配表，解码后的字符就不会出现误差。根据编码时所使用的字符概率区间分配表和压缩后的数值代码所在的范围，可以很容易确定第一个字符。设法去掉第一个符号对区间的影响，找到下一个符号。重复以上操作，直到完成解码过程。计算流程如图3。2.3LZW编码算法LZW编码的基本思想是建立一个字典，将输入字符串编码成定长的码流输出（通常为12位），并在编码过程中动态生成字典，算法是自适应的。但传统LZW算法存在占

9、用大量的字典容量、生成的字典项较多时查找效率低等缺陷。故讨论一种改进LZW编码压缩算法进，将字典初始化为16位，采用散列法和拉链法进行词条检索，采用阈值判断和LRU淘汰机制改进条目更新的方式，编码时采用自适应变码长方式。经测试，相比于传统LZW编码数据压缩算法，改进的算法对不同码长的数据的适应性更好，并且压缩比提高了约8%。LZW编译码LZW编码是一种基于字典模型的无损数据压缩方法，由Lempel-Ziv-Welch共同提出。通过建立一个字符字典，用较短的码字表示较长的字符串，达到数据压缩的目的。在动态的建立字典的同时，字符串和码字之间逐渐建立关系。后续的字符串与字典进行比较，不断完善和壮大字

10、典。生成的字典不需要随着数据一块存储和传输，在解压缩的过程中仍然能够重建一个完全相同的字典，从而进一步地提高压缩效率。在介绍LZW编码流程之前，首先定义几个在LZW编码、解码过程中出现的概念:P：当前前缀，表示在编码算法中正在被处理的前缀C：当前字符，表示在编码算法中当前确定的字符。cW:当前码字，当前被处理字符串对应的码字。pW:先前码字，先前被处理字符串对应的码字。String.cW:当前码字对应的字符串。String.pW:先前码字对应的字符串。LZW编码过程：建立初始字典，该初始字典中包含待处理字符数据流中所有可能出现的字符。同时，设置前缀P为空；读取字符串数据流中的下一个字符作为当前

11、字符，送至C中；判断P+C是否已经存在字典之中，若存在:P=P+C，用C来扩展P,若不存在：把表示前缀P的码字cW输出到编码数据流中。将字符串P+C按照顺序加入字典中，同时使P=C;判断字符数据流是否编码完毕，若编码完毕:编码完成，输出P所对应的码字cW到编码数据流结尾处，若未完成，则继续编码。幵始前蟲F为空LZW译码过程：建立初始字典，该初始字典中包含待处理字符数据流中所有可能出现的字符。读取编码数据流中的第一个码字cW。输出cW所对应的字符串String.cW到字符数据流中。pW=cW，读入编码数据流中的下一个码字cW。判断cW对应的字符串String.cW是否在字典中？若在字典中:将St

12、ring.cW输出到字符数据流，P=String.pW，C=String.pW字符串中的第一个字符，P+C添加到字典；若不在字典中：P=String.pW,C=String.cW中的第一个字符，输出P+C到字符数据流，然后将P+C添加至字典。判断码字流中是否还有待译码字?是:返回步骤pW=cW；否：译码结束。图5LZW解码流程图232改进的LZW编码LZW压缩算法的执行速度依赖于字典查找的速度。在LZW压缩算法中，若直接检索字典，编码的速度很低，同时时间复杂度较高，为O(n2)。因此，选择一种效率较高的字典存储和遍历索引的方式是提高LZW编码效率的主要途径。为了提高字典的存储和索引效率，引入散

13、列表(HashTable)来存储字典，只需通过关键字就可以确定结点的存储位置，这样能有效提高字符串表的检索效率。为了提高编码的效率，采用可变长度的编码方法。在系统中，使用的可变编码位数从8位开始，当编码长度超过了8位的表示范围，则自动增加到9位编码，依次递增编码位数。但增加编码位数使得算法性能和执行效率都受到影响，因此，设定编码长度的最大范围为12位，当编码超出12位(4096)表示范围，需要重新开始字典的生成和编码。当词条数目过多导致字典容量饱和时，需要重新生成字典，clear操作会严重影响压缩编码的压缩比和执行效率，因此，为了解决传统的LZW编码压缩效率低的问题，现作出以下改进:当字典中串

14、表填满之后，不立即输出clear信号，删除字典表，而是继续输入一定长度的数据流，使用现有的字典表表对其进行压缩编码，同时计算出这时被压缩的数据流的压缩比，如果所得到的压缩比较低，满足系统要求即RrR0时，表示现在的字典表无法满足当前数据压缩的要求，则进行删除和重建字典表的操作。这样可以有效抑制那些突发的数据对整体压缩性能的影响，使得系统不会由于一些数据毛刺的影响导致多次删除和重建字典表，提高了LZW压缩算法的压缩比和执行效率。改进图6改进的LZW算法实现流程图可以通过流程图看出，改进的LZW编码方式主要在添加新词条字符串时，需要判断码长是否满足要求，同时当系统码长达到最大，即12位码长之后，是

15、否输出clear信号需要通过判断一段数据流的压缩比后决定。2.4游程编码算法行程编码RLE又称游程编码，这种压缩方法广泛的应用于各种图像格式的数据压缩处理中，是压缩图像最简单的方法之一。传统游程编码游程编码技术是在给定的图像数据中寻找连续重复的数值，然后用两个字符取代这些连续值。传统的游程编码是由两个元素的序对组成，其中表示编码符号，表示游程长度，等于有相同编码符号的相同元素的数目。这种方法在处理包含大量重复信息的数据时可以获得很好的压缩效率。但是如果连续重复的数据很少，则难获得较好的压缩比，甚至可能会导致压缩后的编码字节数大于处理前的图像字节数。改进自适应游程编码算法固定格式的常规游程编码与

16、实际游程长度的适应能力差。因此，需要一种灵活的游程编码方式：遇到短游程用较短的字长描述，遇到长游程时自动用较长的码子描述。从二进制的表达方式可以得到启发：二进制计数方法的实质是对不同位置的比特分配不同的权重，而这些权重的分配能够描述任何一个整数。因此，最为理想的游程编码的lk的字长应当等于游程的实际长度对应的二进制数的比特总数。k但是游程的实际长度是随机的，因此解码器无法确切知道当前lk的字长是多少。为此提出一种改进的游程编码算法。仍然采用两个元素的序对(a,a)组成，其中al等于原始码流长度对应的二进制数的比特，a0表示al对应比特数的长度。设定一个游程指针(简称游针)和两个码表(O码表和1

17、码表)。0码表适合对连0编码，1码表适合对连l编码。由统计特性知，连0远远大于连1,对于0码表来说，al往往比较长，因此a0也相应比较大，考虑最大连0,把a0取为4位。而对于1码表来说，al比较短，因此a0也相应比较小，考虑最大连1,把a0取为3位。首先根据游针探测输入码元极性，判断是采用0码表还是1码表。选中码表后，游针通过计数器方式探测连续码流，得到连续码流长度n然后将码流长度转化为二进制码，得到al，同时计算al的长度，并转化为二进制码得到a0；设原始码长为xl，则xl。转化为二进制可以采用如下运算：xn+1=xn/2,yn=xnmod2(n=l,2,)依次把ynyn_,y2y1就得到a

18、l,同理可得到a0。最后合并a0,aj,得到最终编码。2.5费诺-香农编码算法由于霍夫曼编码法需要多次排序，当元素很多时不方便，为此费诺和香农分别单独提出类似的方法，使编码方法更简单。具体编码方法如下：（1）把x1x按概率由大到小，从上到下排成一列，然后把x1x分成两组x1xk和xk+1xn并使得：工p（xj沁工p（xji=1i=k+1（2）给两组中的x,赋值，将概率大的一组赋为0,概率小的一组赋为1。这是该方法的赋值原则。（3）把两组分别按（1）、（2）分组赋值，不断重复，直到每组只有一种输入元素为止。将每个x,所赋的值依次排列起来就是费诺-香农编码。2.6一种新的无损图像压缩算法本方法是一

19、种新的二进制（位级）无损图像压缩方法一一将错误纠正BCH码引入到图像压缩算法中；将图像的二进制分为大小为7的码字，这些块进入到BCH解码器，消除了校验位后，使得原来的块的大小减少到4位。BCH编码方式是将大小为K位的块，通过增加m位的校验位，形成一个长度为n的码字。在本方法中，我们将n的大小定义为7。这个值被选中后进行多次实验，得到较好的结果。图7示出了BCH算法系统的框架。图7BCH算法系统构造图2.6.1压缩步骤第一步：预处理步骤，将图像转换成二进制数字图像。第二步：使用(7,4)BCH码解码器，将这些二进制数转换成一个由4位数据产生的长度为7的块。请注意，并非所有的长度为7位的块都是码字

20、，也有长度为7的块是非编码字。因此，我们使用一个额外的位来区分码字和非码字。第三步：生成二进制数的Huffman编码压缩图像文件。第四步：添加位文件应用两种不同的算法：执行长度编码(RLE)算法嘲和哈夫曼编码算法。然后，将该文件添加到压缩的二进制文件中。图8为该方法的流程图。图8算法流程图2.6.2解压步骤第一步：读压缩文件的标题，并从中提取补充位文件，然后通过应用哈夫曼解码器解码提取的文件，申请的RLE解码器，以增加位的方式使得文件返回其原来的形式。第二步：对使用哈夫曼算法压缩的图像文件进行解码。第三步：使用BCH编码。在这个过程中，将读取文件的所有位的信息。添加位的值决定了当前块K的大小，

21、如果添加位当前的值是1,那么块的大小是4位，否则块的大小是7位。BCH编码器返回的块大小为4位到7位的原始大小，并返回BCH解码删除奇偶位。第四步：图像没有任何数据丢失返回其原始状态。3常见无损压缩算法的总结本文介绍了常见的无损压缩方法：静态及动态霍夫曼(Hufnan)编码算法、算术编码算法、LZW(lanpel-ziv-velch)编码及其改进算法、行程编码(又称游程编码，RLE)及改进自适应游程编码算法、费诺-香农编码算法和一种改进的编码方法。Huffman编码算法分析Huffman的编码方法充分利用了短码，编码效率比较高，且对编码设备的要求也比较简单，是综合性能较高的一种编码方法。但是，

22、它也存在工作量大、编解码时问较长等缺陷，给实际应用带来很大困难。自适应霍夫曼编码方案在不需要对数据扫描两遍，而是随着编码的进行，逐步构造Huffman树。同时，这种编码方案对符号的统计也动态进行，随着编码的进行，同一个符号的编码可能发生改变。算术编码算法分析算术编码完全抛弃了用特殊字符代替输入字符的思想。在算术编码中，输入的字符信息用0到1之间的数字进行编码，它用到两个基本的参数:符号的频率及其编码间隔。对于输入的字符信息，算术编码后形成一个唯一的浮点数。算术编码的效率一般要优于哈夫曼编码，但实现要比哈夫曼编码复杂。算术编码能最大限度地减小信息的冗余度，与Huffman编码方法相比，在同样的计

23、算机系统上，算术编码可以得到更好的压缩效果，但却要消耗也许几十倍的计算时间，因此无法成为日常使用的压缩方法。LZW编码算法分析LZW编码属于字典编码，其原理是利用字典把每个字符串编码为一个标识，利用查字典的方法找出重复出现的字符串，以标识来代替字符串，从而达到压缩的目的。LZW编码实现的基本思想是：读取字符串；如果在字典中找到匹配，那么用字典地址代替该字符串，并继续下一个查找，直到查找不到，则把未查找的字符串加入字典；读入下一个字符，循环上述过程，直到结束。LZW压缩算法也存在着一些不足之处，故讨论一种改进的LZW编码数据压缩算法，对传统LZW编码数据压缩算法进行了改进，将字典初始化为16位，

24、采用散列法和拉链法进行词条检索，采用阈值判断和LRU淘汰机制改进条目更新的方式，编码时采用自适应变码长方式。相比于传统LZW编码数据压缩算法，改进的算法对不同码长的数据的适应性更好，并且压缩比提高了约8%。游程编码算法分析游程编码（run-lengthencoding）是把一串连续的重复值（如图像的像素值）用一个单独的值和一个计数值来取代。对有大面积的连续阴影或者颜色相同子块的图像，使用这种方法实现简单，压缩效果很好。传统的游程编码方法，往往导致较短游程的编码位数大于较短游程长度的自然位数，当二元序列中较短游程较多时，较短游程重新编码所导致的数据膨胀会严重影响二元序列的压缩效能。自适应游程编码

25、是一种对小波域经数学形态学处理得到的小波显著系数的有效编码方式。图像小波分解。经数学形态学膨胀处理后，位平面将出现大量极长的连“0”，利用游程编码将是非常有效的。改进的自适应游程编码算法最突出的新特点是其可以将原始比特流转换成码长的二进制编码。实验结果表明，当连续码流相等的情况下，改进的算法可以有效减少编码长度。费诺-香农编码算法分析费诺-香农编码算法与霍夫曼编码有类似之处，但霍夫曼编码法需要多次排序，当元素很多时不方便，费诺-香农编码算法使编码方法更简单。新的无损压缩算法分析本文中，详细介绍了一种新的无损图像压缩方案。新的二进制（位级）无损图像压缩方法一一将错误纠正BcH码引入到图像压缩算法中；将图像的二进制分为大小为7