无损压缩LZW算法

无损压缩LZW算法（精选四篇）

无损压缩LZW算法 篇1

遥测数据 种类繁多 、 数量庞大 , 给遥测系 统带来了 巨大的处 理压力 , 而遥测数 据的冗余 度也很大 , 统计表明 标准遥测 系统中传 输的数据 冗余度达 到90% 以上[1]。 为了降低信号空间 ,缓解数据处理压力,在遥测系统中采 用数据压缩技术成为必 然, 而选择一 个好的数 据压缩算 法 ,会起到事 半功倍的 效果 。 LZW压缩算法 以其编码 简单、适用广 、易于软硬件实现等特点 成为数据压缩算法的 首选。 但遥测数 据数据量 大 ,通用的LZW算法并不 能取得良好的 压缩效果, 其缺点在于传 统字典的 更新方式 和字典的查找 方式影响数据的压缩效 果 。 针对存在 的这些问 题 ,本文提出 了LZW算法的优 化方法 ,并对优化 算法进行验 证分析。实验结果表明,该优化方法提高了 系统的压缩速率和 压缩比 ,达到遥测数据压缩系 统的指标要求。

1LZW算法基础理论

LZW是一种基 于字典编 码的算法 。 字典编码 就是把先输入的 “ 前文 ” 编为字典 , 用来指代 后输入的 重复的 “ 下文 ” , 减少重复性的输出 , 从而达到数据压缩的目的[4]。 LZW压缩算法的基本原理 : 提取原始文本文件数 据中的不同字符 ,基于这些字符创建一个 字典 ,然后用字典中 的字符的 索引来替 代原始文 本文件数 据中的相 应字符 ,减少原始数据大小。 但应该注意到,这里的字典不是事先创建好的 ,而是根据原始文件数 据动态创建的,解码时还 要从已编码的数据中还原出原来的字典[5]。 其压缩过程为编码器逐个输入字符 并累积成一个字符串I,每个输入字符x首先串接在I后面 , 然后在字典中重新查 找字符串I , 找到I则继续取下一个字符串接在I后面继续查找过程 ;否则将其存入字 典,输出指向I的指针 ,预置I为x,取下一个字符……。 算法流程如图1所示。

2传统LZW算法压缩方法的分析

假设母节 点 、 索引 、 字符的长 度都为10位 , 即检索地 址指针数 据长度为10位 , 则字典节 点的个数 为210,称这个字 典的大小 为1 K。 相对于压 缩数据量 而言 , 字典的空 间往往小 得多 , 因为受硬 件条件 、 算法复杂 度和实现 速度等因 素的限制 。 通常由于 压缩数据 任务较大 , 几K大小的字 典也很快 会填满 , 传统LZW算法中当 字典填满 时常采用 以下处理 方式 :(1)停止更新 字典 。 (2)将字典清 空 ,用来重新 更新 。 (3)引用次数 少的删除 。

而这三种 方式会带 来如下影 响 : 停止更新 字典会使 字典对之 后的输入 数据失去 适应性 ,从而导致 压缩效果 差 ; 由于字典 由空至满 是字典慢 慢适应输 入数据的 过程 , 将字典清 空 , 重新填写 会延长字 典对被压 缩数据的 适应时间 , 影响压缩 效果 ; 删除被引 用次数为0或后续出 现频率较 少的词条 ,保留被引 用次数大 于0或后续出 现频率较高的词条。 虽然会提高压缩比,但复杂的字典管理对硬 件资源的 占用和压 缩时间的 消耗是得 不偿失的 。

传统LZW算法中的 查找字典 的方式为 顺序查表 。 当需要处 理的数据 任务量大 时 ,会导致生 成的字典 项较多 ,严重降低 查找字典 的速率 。

若只采用 顺序查表 ,取字典大 小为4 K, 则处理4 KB的数据的 最大查找 长度约为4 096×4 097/2=8 390 656。 假设FPGA查找一个 词条需要4个系统时 钟周期 , 则最坏情 况处理4 KB数据需要 查找8 390 656×4=33 562 624个时钟周 期 ; 字典填满 后若清空 , 以4个时钟周 期的单位 清零为例 , 则还需要 (4 096 -256) ×4个时钟周 期 , 总共用时33 577 984个时钟周 期 。 以100 MHz的时钟为 例 , 则系统处 理4 KB数据的最 大时间为335.78 ms, 处理速率 约为11.91 KB/s。 查找单个 词条的最 大时间为 ( 4 096 - 256 ) × 4个时钟周 期 , 为153 . 6 μs 。 而FPGA对遥测信 号的采样 率为32 k Hz, 量化精度 为8 bit, 采样通道 数为6, 则压缩系 统的输入 数据速率 为192 KB/s。 显然采样 这样的查 字典方式 的压缩算 法速度过 慢 ,不能满足 实时压缩 需求 。

3LZW算法的优化设计

3.1字典大小的设计

字典的大 小对算法 的执行速 度和压缩 比有影响 。 过小的字典很快会被填满 ,且由于存储的字符串少 ,数据匹配效果差,影响压缩比。 过大的字典可能会增加查字典的时间 ,影响了压缩速度,重要的是大容量字 典耗费的存 储空间也大,要充分考虑FPGA芯片内部块RAM资源。

在计算机 上通过软 件算法试 验找出合 适的字典 大小 ,再考虑算 法的硬件 实现速度 。 软件实验 设计的字 典大小必 须在硬件 的可接受 范围 。 取128 KB的遥测数 据作为压 缩数据源 , 分别设2 K、4 K、6 K、8 K、16 K、32 K的字典空 间大小 ,实验结果 如表1。 随着字典 的增大 ,压缩比都 有一定的 增大 , 对表1进行压缩 比-字典绘图 如图2所示 。 字典大小 为2 K~4 K时压缩比 增长率较 大 , 字典大小 为4 K~16 K区间字典 增长率放 缓 。

从图中可 以看到4 K字典或8 K字典才是 合理的选 择 。 由于FPGA还要完成 其他工作 , 考虑到整 个系统工 作量 ,将其设置 为4 K字典 。

3.2查找字典的方式优化

查找字典 的方式对 压缩和解 压的速度 有很大的 影响 。 为了加快 查找字典 的速度 ,保证压缩 速率 ,对查找字 典的方式 进行优化 ,采用多次 散列法作 为查找字 典的方式 。 根据散列 表思想 ,通过建立 散列函数index=f(K),在字典的 存储位置index和它的关 键字K之间建立 一个确定 的关系 ,使这些关 键字与字 典中相应 的存储位 置一一对 应 。 图3为采用散 列表结构 的字典检 索过程示 意图 。

压缩时采 用的散列 函数为 :

其中 :currentchar为当前输 入数据 ,prechar为前一个编码数据,offset为偏移量 ,tab_size为散列表长 ,即字典地 址为当前输入数据左移 一位再与前一个 编码数据 相异或的 值 。 当散列表 中地址产 生冲突时 ,字典地址 用式(3)计算,如果该式中字典地址小于0,则用式(4)计算字典地址。

利用MATLAB软件对采 用不同次 数散列的 压缩算法 进行测试 ,结果如图4所示 。 为了测试 结果更准 确 ,每种查表 方式都经 过多次测 试取平均 压缩时间 。

从图可看 出 ,在散列次 数达到15次以上时 , 压缩速度 有较大的 提高 ; 散列次数 从15~40时 , 压缩速度 并不总是 提高 ,而是稍有 波动 。 原因如下:

( 1 ) 与信号源 的特性及 散列函数 有关 。

( 2 ) 由于程序 设计为多 次散列后 出现 “ 冲突 ” 则采用顺 序方法查 表 ,散列方法 查过的位 置都有可 能被重复 查找 ,散列次数 越多 ,可能出现 的重复查 找次数就 越多 ,这就增加 了一定的 压缩时间 。

由此可见 , 散列次数 并不是越 多越好 , 由试验结 果来看可 以选择25~40次之间 。 从纵向角 度来看 ,在同等条 件下 ,遥测数据 比随机数 据压缩要 快 。 这是因为 随机信号 源的各个 字符的出 现概率几 乎相等 ,字符间相 互独立 , 冗余度极 小 , 这就会使 程序更频 繁地在查 字典和写 词条 ,平均处理 一个字符 的时间较 长 。 由此可以 把对随机 数据的压 缩时间估 算为实际 压缩的最 大时间 。

3.3字典更新方式的设计

下面通过 软件仿真 比较几种 不同的字 典更新方 式的压缩 效果 ,从表2中可以看 到不能在 提高压缩 比的情况 下同时提 高压缩速 率 , 意味着压 缩比满足 情况下 ,压缩速率 受到制约 。 所以将这 几种字典 更新方式 的优点综 合起来 , 即当字典 没有填满 时就将字 典全部清 除 , 重新建立字典 , 这样可以 同时提高 压缩比和 压缩率 , 并有效地 避免了散 列地址的 冲突 。

4实验结果分析

根据上述 优化设计 方法对FPGA的LZW压缩算法 进行改进 , 设计查字 典散列次 数最大为25次 , 利用Modelsim软件仿真 程序 , 结果如图5所示 。 从图5可以看出 , 改进后的 压缩算法 没有出现 长时间的 查表时间 , 程序压缩 字符的时 间较为均 匀 。 仿真结果 表明 ,当仿真周 期为10 ns(100 MHz时钟 ) 时 , 硬件程序 压缩64 KB遥测数据 用时24.785 ms,平均处理 速率约为2 582.2 KB/s; 压缩64 KB的随机数 据用时83.624 ms, 平均处理 速率约为765.3 KB/s。 这两个速 度都远大 于遥测数 据输入流 速率192 KB/s。

通过对LZW算法的分 析 , 总结了算 法优化 : 字典大小 设计 、 表方式设 计和字典 分别针对 这两个优 化点 ,以MATLAB软件为主 、 Modelsim软件为辅 做仿真实 验 , 为程序优 化 、提高系统 压缩性能 提供依据 。

摘要：针对数据采集压缩系统压缩速率慢和压缩效果不足这一问题,分析了字典大小和查找字典的方式对压缩性能的影响,提出了优化LZW算法的方法。该方法引入基于散列函数的字典查找方式和删除当前未被引用词条的字典更新方式提高字典压缩效率,并通过优化算法和传统算法的比较以及仿真,验证了算法的优越性。测试结果表明,该优化方法整体上提高了系统的压缩性能,具有较高的工程实用性。

无损压缩LZW算法 篇2

关键词：无损图像压缩； 整数小波； 多级树集合分裂排序

中图分类号： TP 911 文献标志码： A doi： 10.3969/j.issn.1005-5630.2015.01.012

Abstract：This paper studied a lossless compression algorithm. The algorithm transforms the image data by integer wavelet， achieving lossless compression with coding wavelet sub-band data with set partitioning in hierarchical trees （SPIHT）. The limitation of lossless image compression is probed and image information entropy is estimated. Six pieces of standard grayscale images are used to test the compression algorithm and evaluate time consuming. The results of simulation show that it has fast rate， and can obtain a higher compression ratio. Thus， the algorithm is practical.

Keywords：lossless image compression； integer wavelet； set partitioning in hierarchical trees（SPIHT）

引 言

图像压缩有无损压缩和有损压缩两种压缩方式。有损压缩能够获得较高的压缩比，广泛地应用于各种图像处理中，由于医学图像、遥感图像等获取成本很高，图像信息有着特殊用途，不能丢弃细节信息，需使用无损压缩。随着电子行业软硬件技术和网络的发展，人们对图像质量的要求日益提高，即使人们日常的生活照片（例如，孩子的成长照、风景照等），很多人也希望能够完整地保存下来，但是存储这些图像数据给存储设备和网络传输带来很大压力，而无损压缩能够在减小存储空间的同时不会丢失任何信息，能满足人们对图像品质要求，能够完整保存图像信息，所以无损压缩是必不可少的技术手段[1]。

无损压缩是没有任何信息损失的压缩，即100%重建原图像，无损压缩的极限由其信息熵决定。图像的信息熵不一样，同一种算法对不同的图像压缩比就不一样。常见的无损压缩方法有游程编码、LZW编码、熵编码、预测编码等。本文采用小波变换结合SPIHT编码进行图像的压缩。

1 小波基的选择

正交变换能够有效地消除图像像素间的相关性，其中小波变换拥有很好的时-频特性，能很好地描述图像的频率特性，且不会出现离散余弦变换在低码率下的方块效应，能够获得相同位率下更好的压缩性能。在图像压缩应用中，小波基的正交性、紧支撑性、对称性、正则性和消失矩都是影响图像压缩效果的关键因素[2-3]。选取时要对上述性质综合考虑，但还没有发现一个小波基对各种类型的图像都表现出最佳的能量压缩性能和最好的相关性的消除能力，通过大量实验研究人员还是找到了一些对各种情况总体上相对较好的小波基，例如用于有损压缩的Daubechies（9/7）（9/7中9和7分别表示小波分解和合成时系数的个数）小波基和用于无损压缩的Le Gall 5/3小波基。有损压缩能够获得较高的压缩比，在图像压缩中有着广泛的应用，因而对Daubechies（9/7）小波基的研究也非常多。无损压缩所能取得的压缩比十分有限，使得其应用有了一定的局限性，因而Le Gall 5/3小波基的研究相对就比较少[4-7]。本文研究的是图像的无损压缩，选择综合性能相对较好的Le Gall 5/3整数小波作为小波变换的小波基。

2 Le Gall 5/3提升小波变换

Le Gall 5/3提升小波是2阶消失距的对称双正交小波[2]，5/3变换是整数到整数变换。基本思想是通过由基本小波（lazy wavelet）逐步构建出一个具有更加良好性质的新小波，其实现步骤有3 步：分解（split）、预测（predict）和更新（update）。分解是将数据分为偶数序列和奇数序列2个部分，预测是用分解的偶数序列预测奇数序列，得到的预测误差为变换的高频分量，更新是由预测误差来更新偶数序列，得到变换的低频分量。其正变换公式为[2]

由于Le Gall 5/3整数小波变换在变换中只有加减法，虽然在取整的过程中由于正变换和逆变换都会出现0.5，但是由于在正变换中多（少）了0.5，相应的在逆变换就会少（多）了0.5，这样经过取整，误差为0，那么也就是实现了无损压缩[4]。非整数的小波变换，例如有损压缩中应用广泛的Daubechies（9/7）小波，因其运算中涉及浮点运算而无法精确重建。

3 SPIHT编解码[8]

图像数据经过二维小波变换后，小波系数数据量并没有减小，为进行压缩，需要对小波系数进行编码，编码主要根据小波系数之间的相关性。小波系数的相关性主要存在同一子带内，也存在于不同子带之间。SPIHT编码也主要是根据同一子带内以及不同子带间的相关性进行的。不同分解层间的相关性采用链表（树）形式进行组织。每一级的一个节点在下一级存在与之对应的4个节点，一般认为当前该节点重要，其后代对应的4个节点也重要。

nlc202309021303

4 算法解析

本文采用Le Gall 5/3提升小波对图像进行整数小波变换，用SPIHT算法对小波系数编码。图像压缩的基本流程如图1所示。

4.1 小波变换的阶数[2]

小波变换把图像信号分解成为4个信号：低频子带LL和3个方向的信号。3个方向信号又分为水平方向HL，垂直方向LH和对角线方向HH，再次分解低频子带LL又可得到四个子带（LL、HL、LH、HH）。所以总的子带数为3K+1，其中K为小波分解阶数。图像做小波分解时，分解到什么程度才能达到最佳的压缩效果，要根据图像的复杂度和滤波器的长度来确定的。从子带的信息熵可以进行定量的确定。一个子带分解成4个子带的熵的和如果不比原子带的熵就不值得分解了，例如信号X的熵定义为

4.2 小波变换的图像边缘延拓[9]

小波的分解和重构都是建立在假设数据双向无限的，由于计算机的处理能力有限，处理的数据也一定是有限的，这样会在图像的边界部分产生边界效应，即产生很大的失真。因此有必要对图像数据的边界进行延拓，增加图像数据的长度和宽带，使得边界延拓到图像数据的外围，避免对图像数据产生噪声。常用小波边界延拓包括有：补零、光滑常数延拓、周期延拓和对称延拓。实际处理中对称延拓和周期延拓应用较多。一般来说由小波基的性质来选择延拓方法，如果小波基是对称的，选用对称延拓就比较合适。Le Gall 5/3小波的小波基是对称的双正交小波，因此本文算法采用对称延拓。例如，假设原始序列为x（0），x（1），x（2），…，x（2n-1），通过提升变为两个长度均为n的序列。要计算 c（2n-1）需要补x（2n），而计算d（0）需要补c（-1），计算c（-1）需要补x（-1），x（-2）。因此考虑到边界问题，需要在序列的前补两个，后补一个。采用对称延拓，即为

4.3 图像无损压缩的极限讨论

从信息论来讲，无损压缩所能达到最大压缩效率是由图像的信息熵H（x）决定的。但是无损压缩到底能做什么程度，现在还没有有效的方法来做出准确的预测。由于图像的像素之间存在着强烈的相关性，使得精确计算图像信息熵几乎难以实现[10]。文献[10]利用多尺度条件熵和记忆性度量来估计图像无损压缩的极限，实现起来有一定的难度，不同图像高阶熵模型不尽相同，可信度较高的全位面条件熵不容易计算。文献[11]提出了另一种粗略评估方法，因为正交变换具有去相关的性质，对图像数据做正交变换能够在一定程度上去除数据间相关性，而正交变换并不会改变数据的信息熵，完成正交变换的图像数据的统计特性近似符合高斯分布，高斯分布的各个样本近似于相互独立，可以用计算变换后系数的一阶熵来近似图像数据的信息熵。文献[11]中采用计算离散小波变换（discrete wavelet transform，DWT）系数的N阶熵，在这里计算图像的1阶熵到5阶熵。选用6幅标准测试灰度图像如表1所示。

以上各阶熵只是对图像信息熵的粗略估计，由于小波变换不能完全消除图像像素间的相关性，实际上图像的信息熵要低于我们计算的熵。

5 实验分析

选择6幅常用标准测试灰度图像，对本文算法进行实验分析，6幅图像如图2所示。可以看出图2（a）Barbara、图2（b）Goldhill、图2（d）Baboon的内容细节信息较为丰富，含有大量的纹理信息，较难获得较高压缩比，图2（c）Bridge的细节信息较少，图像内容较为简单，一般来说能获得较好的压缩比，图2（e）Boats和图2（f）Lena是图像处理人员常用的测试图像，纹理信息和结构信息均较为适中，很具有代表性，相应的压缩处理时所能获得的压缩性能也较为中庸。

测试硬件环境为ThinkPad T400，操作系统为Windows XP SP3，软件环境为Visual Studio6.0，编程语言为C语语言。上述六幅图像均为512×512，8 bits的灰度图像。

测试了上述图像在Le Gall 5/3整数提升小波在小波阶数从2到8阶的无损压缩比和程序运行时间，测量值如图3、图4所示。

从图3中，可以看出小波分解阶数达到4阶后，再增加小波分解阶数所带来的压缩比提升极为有限，而过高时反而略有下降，这是因为图像所含纹理信息量不同，数据间的依赖关系也不同。从表1的数据可以看出除了纹理信息最为丰富的图2（d）Baboon外，其他图像均5阶小波分解达到最优压缩效果。图2（d）Baboon的内容较为丰富，含有大量纹理信息，为了更好表示图像信息需要的小波分解阶数也较多，在6阶分解时达到最优压缩效果。SPIHT算法利用了子带内部和子带之间的相关性，当小波分解过多时，效果会受到影响。从图4中，可以看出随着小波分解阶数的增加，算法消耗的时间也相应增加，从表2的数据中可以看出时间消耗的增加并不显著。纹理信息最少的图2（e）Bridge需要的运行时间最少，纹理信息最为丰富的图2（d）Baboon需要的运行时间最多。从处理各幅图像所用时间来看，该算法完全可以满足实时处理的需要，在降低存储空间的同时，图像质量丝毫没有受到影响。

6 结 论

介绍Le Gall 5/3整数小波变换和SPIHT算法，并将其用于图像的无损压缩，对压缩过程中小波变换对图像边缘的影响加以讨论，确定了周期延拓的方案，以降低图像边缘部分的失真。对无损压缩的极限进行了讨论，利用正交变换不改变图像信息熵的特性，把图像数据经过正交变换后求其熵，对图像信息熵粗略估计，对无损压缩极限进行了粗略预测。选取六幅标准图像对该算法加以验证分析，从时间消耗和压缩效果两个方面来看，该种算法具有广泛的应用价值。

参考文献：

[1] ALARABEYYAT A，AL-HASHEMI S，KHDOUR T，et al.Lossless image compression technique using combination methods[J].Journal of Software Engineering and Applications，2012，5（10）：752-763.

[2] 周兵，李波，李炜.小波图像编码器研究进展[J].计算机科学，2002，29（1）：57-62.

[3] 武永红.基于小波变换的图像无损压缩算法研究[D].重庆：重庆大学，2012.

[4] 闫红梅，李科，吴东梅.SPIHT的超光谱图像无损压缩算法[J].西安科技大学学报，2009，29（5）：598-602.

[5] 张宁，吴银花，金龙旭，等.适于航天应用的高速SPIHT图像压缩算法[J].液晶与显示，2011，26（6）：847-852.

[6] 陈斌，崔志明.JPEG2000的Le Gall（5，3）有损压缩重构优化[J].计算机应用，2006，26（5）：1048-1050.

[7] 姜会亮，胡学龙，郭振民，等.整数（5，3）小波变换结合SPIHT的无损图像压缩[J].计算机工程与应用，2005，41（14）：69-70.

[8] SAID A，PEARLMAN W A.A new，fast and efficient image codec based on set partitioning in hierarchical trees[J].IEEE Transactions on Circuits and Systems for Video Technology，1996，6（3）：243-250.

[9] 潘志刚.低比特率合成孔径雷达数据压缩算法研究[D].北京：中国科学院研究生院，2006.

[10] 张宁，章毓晋，刘青棣，等.利用多尺度条件熵和记忆性度量估计图像无损压缩极限[J].清华大学学报（自然科学版），2000，40（9）：32-36.

[11] CALDERBANK A R，DAUBECHIES I，SWELDENS W，et al.Wavelet transforms that map integers to integers[J].Applied and Computational Harmonic Analysis，1998，5（3）：332-369.

（编辑：程爱婕）

无损压缩LZW算法 篇3

数据压缩一般分为两大类, 无损数据压缩和有损数据压缩[1]。无损数据压缩指在解码后可以无失真的恢复出原始数据, 不会丢失信息;有损数据压缩允许在解码后的数据与原始数据存在一定的误差。下面将主要研究无损数据压缩。

无损数据压缩技术的发展从最初的单纯的熵编码, 发展到今天, 出现了很多新的压缩方法[2]。现在比较常见的数据压缩方法有:

1.1 Huffman编码

Huffman编码是1952年由D.A Huffman在《论最小冗余度代码的构造》论文中提出, Huffman编码由于完全按照字符出现的概率构造编码, 但存在没有错误保护功能和需要缓存区较大等局限性, 效率不高。

1.2 算数编码

算数编码压缩也是一种基于统计模型的压缩方案, 由Elias提出, 在80年代发展起来的一种熵编码方法。和Huffman编码不同的是, 算数编码不用单个信源符号去映射一个码字, 而是将整条输入序列映射成为[0, 1) 区间内的一个小区间, 该序列的概率就等于区间的长度;实际的编码输出是从上述小区间内选择一个代表性的二进制小数, 这就实现高效编码的目的。不足的是实现较为复杂。

1.3 LZ编码

LZ编码是字典编码的英文简称, 是一种基于字典方法的数据压缩技术。是1970年代末由两位以色列科学家Jacoh Ziv和Abraham Lempel提出, 现在由LZ编码衍生出来的算法很多, 比较著名的有LZ77、LZ78、LZS、LZW等, LZ字典编码与基于统计的数据压缩技术不同, 前者既不使用变长码, , 也不使用统计模型, 使有的是字符串, 利用字典将需要的字符串进行编码形成一个标识, 字典保存这些字符串及其标识。字典保存的字符串既可以是静态的, 也可以是动态的 (自适应的) 。静态字典是固定的, 添加字符串是允许的, 但删除是不允许的;而动态字典中的字符串是先前输入流中出现过的, 当读取新的字符串时, 允许字符串的添加或删除。字典编码以压缩效果好和实现方法简单的优势, 得到人们的一致认可。

但是, LZW压缩算法也存在着一些不足之处:

(1) 在LZW算法中, 字典的初始化需要按照ASCLL码表, 消耗256个左右的字典词条数, 而实现字典的寻址, 至少需要9位的地址位去表示相应的词条位置, 需要消耗大量的码字。这样的初始化过程中浪费了大量的字典容量, 直接导致输出码长的浪费, 严重降低最终的压缩比。

(2) 传统的LZW算法在执行过程中, 字典的生成和查找是基于顺序插入和检索模式, 当需要处理的数据量较大时, 会导致生成的字典项较多, 严重降低查找效率;同时, 通过顺序检索模式浪费了大量的算法执行时间, 无法充分利用数据之间的局部相关性, 降低算法的执行效率。

(3) 传统的LZW压缩算法采用8位数据输入, 固定长度编码输出, 随着字典内容的不断增多, 输出编码的位数不断增加, 固定的输出编码长度造成资源的浪费, 系统的压缩率下降。

本文对LZW算法进行相应改进, 实现了高效数据压缩, 提高了压缩性能。

2. 改进的LZW方法

2.1对于字典初始化的方式, 由于在语音识别中使用的更多的是16进制的数据, 因此, 对于字典的初始化, 只需要将16进制数进行字典的初始化, 不需要将所有的ASCLL字符全部初始化。

2.2LZW压缩算法的执行速度依赖于字典查找的速度。在LZW压缩算法中, 若直接检索字典, 编码的速度很低, 同时时间复杂度较高, 为O (n2) 。因此, 选择一种效率较高的字典存储和遍历索引的方式是提高LZW编码效率的主要途径。为了提高字典的存储和索引效率, 引入散列表 (Hash Table) 来存储字典, 只需通过关键字就可以确定结点的存储位置, 这样能有效提高字符串表的检索效率。

2.3为了提高编码的效率, 采用可变长度的编码方法。在系统中, 使用的可变编码位数从8位开始, 当编码长度超过了8位的表示范围, 则自动增加到9位编码, 依次递增编码位数。但增加编码位数使得算法性能和执行效率都受到影响, 因此, 设定编码长度的最大范围为12位, 当编码超出12位 (4096) 表示范围, 需要重新开始字典的生成和编码。

2.4当词条数目过多导致字典容量饱和时, 需要重新生成字典, clear操作会严重影响压缩编码的压缩比和执行效率, 因此, 为了解决传统的LZW编码压缩效率低的问题, 现作出以下改进:

当字典中串表填满之后, 不立即输出clear信号, 删除字典表, 而是继续输入一定长度的数据流, 使用现有的字典表表对其进行压缩编码, 同时计算出这时被压缩的数据流的压缩比, 如果所得到的压缩比较低, 满足系统要求即Rn≤Ro (其中Rn为当前计算的压缩比, Ro为系统给定的一个阀值) , 则继续先前的操作;如果所得到的压缩比Rn>Ro时, 表示现在的字典表无法满足当前数据压缩的要求, 则进行删除和重建字典表的操作。这样可以有效抑制那些突发的数据对整体压缩性能的影响, 使得系统不会由于一些数据毛刺的影响导致多次删除和重建字典表, 提高了LZW压缩算法的压缩比和执行效率。

改进的LZW编码算法的软件流程图如下图1所示:

可以通过流程图看出, 改进的LZW编码方式主要在添加新词条字符串时, 需要判断码长是否满足要求, 同时当系统码长达到最大, 即12位码长之后, 是否输出clear信号需要通过判断一段数据流的压缩比后决定。

3. 算法的压缩比性能仿真

在对算法性能测试时使用系统中需要存储的数据, 分别使用改进的LZW算法和传统LZW算法在不同输出码长情况下进行数据压缩, 得到部分节点的输出数据, 再将这些点的数据通过MATLAB以线图形式输出, 得到对于改进的LZW压缩算法的性能通过与传统LZW编码方法分别通过8位码长和12位码长输出的压缩比性能比较数据图如图2所示, 其中压缩比的定义为:

4. 结论

在图2中可以看出, 改进型LZW算法的压缩比小于传统的LZW算法, 实测结果表明, 对于传统的LZW压缩算法, 在选择输出码长为12位时, 在文件较大时, 压缩性能优于8位输出的LZW算法, 但是压缩数据较小时, 压缩性能较差;传统的LZW算法在压缩过程中, 压缩比在更新字典起初有明显上升, 而在改进型LZW算法中, 在字典更新过程中压缩比明显改善, 提高了约8%。

摘要：分析了传统LZW编码算法的不足, 根据语音数据的特点, 对传统LZW编码数据压缩算法进行了改进, 将字典初始化为16位, 采用散列法和拉链法进行词条检索, 采用阈值判断和LRU淘汰机制改进条目更新的方式, 编码时采用自适应变码长方式。经测试, 相比于传统LZW编码数据压缩算法, 改进的算法对不同码长的数据的适应性更好, 并且压缩比提高了约8%。

关键词：数据压缩,LZW,字典

参考文献

[1]卢开澄, 卢华明.编码理论与通信安全[M].北京:清华大学出版社.2006.

[2]赵楠.航电数据压缩及传输算法研究.2011.1西安电子科技大学硕士学位论文.

[3]David Salomom.Data Compression and The Complete Reference[M].北京:电子工业出版社.2005.

干涉多光谱图像无损压缩算法 篇4

随着航天遥感技术和卫星成像技术的迅速发展,出现了一种新型遥感技术——光谱成像技术,它引发了卫星遥感技术领域的革命性的飞跃。光谱成像技术将光学、光谱学、精密机械、电子技术以及计算机技术融于一体,能获得被测目标的空间维和光谱维的丰富信息,因而在经济建设和军事上均有极高的应用价值。它利用成像光谱仪在连续光谱段上对同一目标同时成像,从而直接反映出被观测对象的光谱特征。

1 干涉多光谱图像成像原理及特点

1.1 成像原理

成像光谱仪(Imaging Spectrometer)是一种新型的航空遥感设备,兼有成像仪和光谱仪的功能,可以同时获得两维空间信息与一维光谱信息,其成像原理如图1所示。

成像光谱仪将一束入射光线送入干涉仪,将其分解成具有一定光程差的光线并进行干涉叠加。成像光谱仪采用行推扫方式一系列干涉图像,由于在一行上各点的光程差不同,从而在成像平面形成具有数条状干涉条纹的多光谱图像。在成像时,地面的一个点形成一列光谱,当载有成像光谱仪的飞行器扫过地面上的一列光点时,就得到一幅完整的干涉多光谱图像,飞行器不断的推扫,形成一系列干涉多光谱图像。根据傅里叶变换光谱学的原理,干涉图与光源的光谱分布之间存在傅里叶变换关系[1,2]。

1.2 干涉多光谱图像的特点

干涉多光谱图像具有高的空间分辨率和光谱分辨率,数据量很庞大,在实际应用中,压缩过程要求在星上进行,所以压缩算法的复杂度不能过高,否则不利于实现实时压缩[3]。

干涉多光谱图像具有较弱的空间相关性和较强的谱间相关性[4],另外它在水平及垂直方向的相关程度不同,垂直方向相关程度高于水平方向相关程度。

超光谱图像的压缩码流通过卫星信道下传时,由于信道的不稳定,有可能出现误比特的情况,这样,错误的比特信息就会对恢复图像的重建产生错误传播,降低了恢复图像的质量。因此,在对超光谱图像进行压缩时,应保证压缩算法具有很好的抗误码性能。由于超光谱图像的一列包含一个像素点的信息,因此在图像重建时,比特错误应对列的影响尽量小,即应将错误传播控制在有限的一列或几列中,所以在压缩算法中可以分别按列进行独立编码,将误码扩散限定在一列范围内[5,6]。

2 干涉多光谱图像无损压缩算法

2.1 算法原理

超光谱图像的压缩,要求在满足一定压缩比的情况下,具有很强的抗误码能力。根据这一特定要求以及超光谱图像自身的特点,在压缩编码时,应充分利用图像的列相关性,而不去考虑其行相关性,也就是对图像数据按列依次编码,并且每一列的编码完全独立。其编码扫描顺序如图2所示。

考虑到超光谱图像数据在列方向上具有很强的相关性,在对其进行列编码时,可对每一列数据去相关,这里采用简单的差分思想,即将序列中的后一个象素值与前一个像素值作差值,并记录符号位,将列数据的编码转换为其差分序列的编码。假设第i列的原始图像数据序列为s[i],其相应的差分序列和符号序列分别为ss[i]和sign[i],则ss[i]和sign [i]由下式确定:

$\{\begin{array}{l}\text{s}\text{s}[0]=s[0]\\ \text{s}\text{s}[i]=s[i]-s[i-1]\text{s}\text{i}\text{g}\text{n}[i]=0‚\\ [i]-s[i-1]>0\\ \text{s}\text{s}[i]=0-(s[i]-s[i-1])\text{s}\text{i}\text{g}\text{n}[i]=1‚\\ [i]-s[i-1]<0\end{array}(1)$

式中i=1,2,…,n。然后对差分序列进行比特平面编码加游程编码。具体的编码算法如下:

(1) 判断第k个差分序列是否全0。如果全0,退出该列编码,进入第(6)步;如果不全为0,继续下一步;

(2) 计算该列的比特平面数,并将数据划分为长为dlen的n/dlen段,按照比特平面由重要到不重要的次序,对每段数据依次进行游程编码;dlen的取值可取2的整次幂,如8,16,32等;

(3) 输出第i段数据的符号位;

(4) 判断第i段数据在第j个比特平面上是否全0,如果全0,输出1个0;否则输出1个1,以及该比特平面上的所有比特;然后进行第j+1个比特平面的编码;

(5) 如果第i段数据的所有比特平面编码完毕,进入第i+1段数据的编码;

(6) 如果第k列数据编码完毕,进入第k+1列编码。

除了上述编码算法外,为了保证有效的压缩性能以及抗误码性能,还需要设计有效、可靠的码流组织结构,如图3所示,以防止接收码流的比特错误在解码过程中产生错误累计致。

使误码扩散,从而保证后续解码都能够完全正确地识别当前列所对应的码流的起始位置,因而后续解码能够不受影响地顺利进行。整个码流结构包括头信息和压缩数据两部分,其中头信息由比特平面信息和列码流地址组成,在比特平面信息和列码流地址中,分别按照列的顺序依次包含各列对应的比特平面数和列码流的地址,而压缩数据则分别包括各列对应的压缩码流。

2.2 本算法的突出优点

本算法采用基于列的比特平面编码和游程编码,对超光谱图像进行无损压缩,特别适于低分辨率的超光谱图像压缩。目前无损压缩算法的压缩比基本在1.6～2.4之间,本算法的压缩倍数一般可达到2倍以上,并且具有良好的抗误码性能。

由于在编码过程中,采用对列独立进行编码的方法,使各列的编码互不影响,并且在头信息中存储了各列码流的起始地址,因此解码时,当前列对应码流的起始地址无需根据前一列码流的解码结束位置计算得到,而可以直接从码流头信息中得到,这样保证了各列码流的独立性。根据这种码流结构,一旦码流中出现比特错误,影响对应列码流的起始地址与前一列码流解码结束位置不一致,当比特错误出现在头信息中的比特平面信息或者列码流中时,解码错误发生在前一列的压缩码流中,但该列所对应码流的起始地址、比特平面数以及压缩数据并没有比特错误,因而可以正确解码;如果比特错误出现在头信息中的列码流起始地址中,将导致该列码流的解码出错,但下一列所对应码流的起始地址、比特平面数以及压缩数据并没有比特错误,因而能够正确解码。可见,在本算法下,误码将被限定在一列之内,不会扩散到其他列,因而本算法适宜于超光谱图像的压缩传输。并且,在本算法中没有包含复杂的变换或数学运算,因而复杂度很低,能满足实时压缩的要求,并易于硬件实现。另一方面,由于本算法仅考虑图像在垂直方向的相关性,而没有利用水平方向的相关性,因而不能利用水平方向的冗余进行压缩编码,故其压缩性能相对JPEG-LS会有一定程度的下降,这正是为提高抗误码能力所付出的代价。

3 试验结果

为了验证本算法的有效性,本文对一组(32幅)128×128×12比特的超光谱图像分别采用JPEG-LS以及本算法进行了无损压缩性能、抗误码性能以及复杂度的对比测试。两种无损压缩算法的压缩比如图4所示。由图4可见,本算法的平均压缩比为2.3倍,略低于JPEG-LS。

在抗误码性能测试中,我们在误码率为10-5时,分别对上述测试图像进行了无损压缩测试。图5(a)为其中一幅干涉多光谱图像的原始图像,图5(b)为误码率为10-5时,采用本算法得到的重建图像,而图5(c)为误码率为10-5时,采用JPEG-LS方法得到的重建图像。显而易见,本算法可以大大降低误码扩散,提高恢复图像质量,具有很强的抗误码能力。

此外,我们对本算法和JPEG-LS的运行时间进行测试,以比较两种算法的计算复杂度。试验结果如图6所示。JPEG-LS算法的平均运行时间为0.42 s,本算法则为0.25 s,可以看出本算法大大降低了计算复杂度,可以满足实时处理需求。

4 结 论

本文针对干涉多光谱图像的压缩要求,提出了一种新的无损压缩方法,具有压缩性能较高、计算复杂度低、硬件实现简单、编码速度和效率都比较高,并且具有很强的抗误码能力,可以满足星上干涉多光谱图像实时压缩处理要求。

参考文献

[1]MAGLI E,OLMO G,QUACCHIO E.Optimized onboardlossless and near-lossless compression of hyperspectral datausing CALIC[J].IEEE Geoscience Remote Sensing Lett.,2004,1(1):21-25.

[2]TAUBMAN D.High performance scalable image compres-sion with EBCOT[J].IEEE Trans.on Image Processing,2000,9(7):1158-1170.

[3]SAID A,PEARLMAN W A.A new,fast,and efficientimage codec based on set partitioning in hierarchical trees[J].IEEE Trans.on Circuits and System for Video Tech-nology,1996,6(3):243-250.

[4]相里斌,赵葆常,薛鸣球.空间调制干涉成像光谱技术[J].光学学报,1998(3):10-13.

[5]相里斌,计忠瑛,黄旻,等.空间调制干涉光谱成像仪定标技术研究[J].光子学报,2004(7):65-67.