图像无损压缩算法综述..pdf
《图像无损压缩算法综述..pdf》由会员分享,可在线阅读,更多相关《图像无损压缩算法综述..pdf(15页珍藏版)》请在三一文库上搜索。
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)将信号源的符号出现的概率(在此称为权值)w1,w2,. ,wn构造 成 n 棵二叉树集合 F=T1,T2,. ,Tn,其中每棵二叉树Ti 中只有一个带权 为 wi 的根结点,其左右子树均为空。 (2) 在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二 叉树,且置新的二叉树的根结点的
4、权值为其左、右子树上根结点的权值之和 (3)在 F中删除这两棵树,同时将新得到的二叉树加入F中。 (4) 重复(2) 和 (3) , 直到 F只含一棵树为止, 这棵树便是霍夫曼 (Huffman) 树。 (5)在合并中约定权值小的根结点在左子树上,权值大的在右子树上,然 后在每个左分支上标记为 “0” , 右分支上标记为“1” , 最后记录从霍夫曼(Huffman) 树的根结点到每个叶子结点所经过的分支上的“0”或“1”的序列,从而得到每 个符号的 Huffman 编码。 2.1.2 自适应霍夫曼编码 这种方案在不需要事先构造Huffman 树,而是随着编码的进行,逐步构造 Huffman 树
5、。同时,这种编码方案对符号的统计也动态进行,随着编码的进行, 同一个符号的编码可能发生改变(变得更长或更短)。 在构造动态霍夫曼编码树的过程中,需要遵循两条重要原则: (1)权重值大的节点,节点编号也较大。 (2)父节点的节点编号总是大于子节点的节点编号。 以上两点称为兄弟属性( sibling property )。在每一次调整节点权重值 时,都需要相应的调整节点编号,以避免兄弟属性被破坏。 在对某一个节点权重 值进行“加一操作” 时,应该首先检查该节点是否具有所在的块中的最大节点编 号,如果不是,则应该将该节点与所在块中具有最大节点编号的节点交换位置。 然后再对节点的权重值加。 这样,由于
6、该节点的节点编号已经处于原来所属块中 的最大值, 因此权重值加一之后兄弟属性仍然得到满足。最后,由于节点的权重 发生了变化,必须递归地对节点的父节点进行加一操作。 在需要插入一个新符号时,总是先构造一个新的子树,子树包含NYT符号与 新符号两个叶节点, 然后将旧的 NYT节点由这个子树替代。 由于包含 NYT符号的 节点权重值为 0,而包含新符号的叶节点的权重值为1,因此最终效果相当于原 NYT节点位置的权重值由0 变为 1。因此,下一步将试图对其父节点执行权重值 “加一操作”。 对符号编码的方法与静态霍夫曼编码一致,每次符号编码完成以后,也将对 包含符号的节点权值进行加一操作。 将一个新的符
7、号插入编码树或者输出某一个 已编码符号后,相应的符号的出现次数增加了1,继而编码树中各种符号的出现 频率发生了改变, 不一定符合兄弟属性, 按照上述方法进行调整, 使其符合要求。 2.2 算术编码算法 算术编码完全抛弃了用特殊字符代替输入字符的思想。在算术编码中, 输入 的字符信息用 0 到 1 之间的数字进行编码,它用到两个基本的参数: 符号的频 率及其编码间隔。 对于输入的字符信息, 算术编码后形成一个唯一的浮点数。算 术编码的效率一般要优于哈夫曼编码,但实现要比哈夫曼编码复杂。 2.2.1 算术编码原理 图 1 算术编码流程图 固定模式编码需要预先对符号序列中的符号进行预扫描,根据统计符
8、号的概 率来列出编码概率表。 引入几个变量: low 为编码间隔的低端, rang 为编码间隔 的长度 ,ranglow 为编码字符的间隔的低端 , ranghigh 为编码字符的间隔的高端。 在固定模式编码中, ranglow 和 ranghigh的编码概率不变。计算流程如图1。 用例子说明算术编码编解码原理,采用固定模式符号概率分配表见表1。若 要编码字符串 eai ,则编码过程如图2 。 表 1 算术编码字符概率分配表图 2 算术编码示意图 2.2.2 算术编码解码原理 图 3 解码流程图 从原理上讲,解码的过程是编码的逆过程,只要保证编码和解码使用同样的 字符概率分配表, 解码后的字符
9、就不会出现误差。 根据编码时所使用的字符概率 区间分配表和压缩后的数值代码所在的范围,可以很容易确定第一个字符。 设法 去掉第一个符号对区间的影响,找到下一个符号。 重复以上操作, 直到完成解码 过程。计算流程如图3。 2.3 LZW 编码算法 LZW编码的基本思想是建立一个字典,将输入字符串编码成定长的码流 输出( 通常为 12 位),并在编码过程中动态生成字典,算法是自适应的。但传统 LZW 算法存在占用大量的字典容量、生成的字典项较多时查找效率低等缺陷。故 讨论一种改进 LZW编码压缩算法进,将字典初始化为16 位,采用散列法和拉链 法进行词条检索, 采用阈值判断和 LRU淘汰机制改进条
10、目更新的方式, 编码时采 用自适应变码长方式。 经测试,相比于传统 LZW 编码数据压缩算法, 改进的算法 对不同码长的数据的适应性更好,并且压缩比提高了约8% 。 2.3.1 LZW 编译码 LZW 编码是一种基于字典模型的无损数据压缩方法,由Lempel-Ziv-Welch 共同提出。通过建立一个字符字典,用较短的码字表示较长的字符串,达到数 据压缩的目的。 在动态的建立字典的同时, 字符串和码字之间逐渐建立关系。后 续的字符串与字典进行比较, 不断完善和壮大字典。 生成的字典不需要随着数据 一块存储和传输, 在解压缩的过程中仍然能够重建一个完全相同的字典,从而进 一步地提高压缩效率。在介
11、绍LZ W编码流程之前,首先定义几个在LZ W编码、 解码过程中出现的概念 : P:当前前缀,表示在编码算法中正在被处理的前缀 C:当前字符,表示在编码算法中当前确定的字符。 cW:当前码字,当前被处理字符串对应的码字。 pW:先前码字,先前被处理字符串对应的码字。 String.cW: 当前码字对应的字符串。 String.pW: 先前码字对应的字符串。 LZW 编码过程 : 建立初始字典,该初始字典中包含待处理字符数据流中所有可能出现的字 符。同时,设置前缀P为空;读取字符串数据流中的下一个字符作为当前字符, 送至 C中;判断 P+C是否已经存在字典之中,若存在:P=P+C ,用 C来扩展
12、 P,若 不存在:把表示前缀P的码字 cW输出到编码数据流中。将字符串P+C按照顺序 加入字典中,同时使P=C ;判断字符数据流是否编码完毕,若编码完毕: 编码完 成,输出 P所对应的码字 cW到编码数据流结尾处,若未完成,则继续编码。 图 4 LZW 编码流程图 LZW 译码过程 : 建立初始字典,该初始字典中包含待处理字符数据流中所有可能出现的字 符。读取编码数据流中的第一个码字cW 。输出 cW所对应的字符串 String.cW 到 字符数据流中。 pW=cW,读入编码数据流中的下一个码字cW 。判断 cW对应的字符串 String.cW 是否在字典中 ?若在字典中 : 将 String
13、.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 编码
14、效率的主要途径。 为了 提高字典的存储和索引效率,引入散列表(Hash Table) 来存储字典,只需通过关 键字就可以确定结点的存储位置,这样能有效提高字符串表的检索效率。 为了提高编码的效率,采用可变长度的编码方法。在系统中,使用的可变编 码位数从 8 位开始, 当编码长度超过了8 位的表示范围,则自动增加到 9 位编码, 依次递增编码位数。但增加编码位数使得算法性能和执行效率都受到影响,因此, 设定编码长度的最大范围为12 位,当编码超出 12 位(4096) 表示范围,需要重新 开始字典的生成和编码。 当词条数目过多导致字典容量饱和时,需要重新生成字典,clear 操作会严 重影响压缩
15、编码的压缩比和执行效率,因此,为了解决传统的 LZW编码压缩效率 低的问题,现作出以下改进: 当字典中串表填满之后,不立即输出clear信号, 删除字典表, 而是继续输入一定长度的数据流,使用现有的字典表表对其进行压 缩编码,同时计算出这时被压缩的数据流的压缩比,如果所得到的压缩比较低, 满足系统要求即 0RRR ( 其中RR 为当前计算的压缩比, 0R 为系统给定的一个阀 值),则继续先前的操作 ; 如果所得到的压缩比 0 RRR时,表示现在的字典表无 法满足当前数据压缩的要求, 则进行删除和重建字典表的操作。这样可以有效抑 制那些突发的数据对整体压缩性能的影响,使得系统不会由于一些数据毛刺
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图像 无损 压缩 算法 综述
链接地址:https://www.31doc.com/p-5163030.html