无损数据压缩

无损数据压缩（精选7篇）

无损数据压缩 篇1

0引言

在水声探测与通信中,常需要对换能器阵列接收到的信号进行存储,因而无损压缩技术得到了更多的关注[1]。常见的无损压缩算法分为两大类:基于统计模型的无损压缩和基于字典模型的无损压缩[2,3,4]。基于统计模型的无损压缩算法有:Huffman压缩算法、算术压缩算法[5]、游程压缩算法[6]等,基于字典模型的算法有LZ77压缩算法、LZ78压缩算法、LZW压缩算法[7,8]等。无损压缩利用数据的统计冗余进行压缩,压缩率受到数据统计冗余度的理论限制,广泛应用于文本数据、程序和特殊场合的图像数据(如指纹图像、医学图像等)的压缩[9]。

1Huffman和LZ77压缩算法原理

1.1 Huffman算法原理

Huffman编码[10]是一种基于二叉树结构的编码方式,编码的核心是Huffman树的建立。

二叉树可以利用来设计前缀编码。假设有一棵如图1所示的二叉树,其四个叶子结点分别表示A,B,C,D四个字符,且约定左分支表示字符‘0’,右分支表示字符‘1’,则可以从根节点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。则所得A,B,C,D的二进制前缀编码分别为0,10,110和111。

假设每种字符在信息中出现的次数为wi,其编码长度为li,信息中只有n种字符,则信息总长为:

$L={\displaystyle \sum _{i=1}^{n}w}{}_{i}l{}_i(1)$

对应到二叉树上,若置wi为叶子结点的权,li恰为从根到叶子的路径长度,则L恰好为二叉树上带权路径长度。由此可见,设计信息长度最短的二进制前缀编码即为以n种字符出现的频率作权,设计一棵Huffman树的问题,由此得到的二进制前缀编码称之为Huffman编码。

1.2 LZ77压缩算法原理

LZ77[11,12]是一种基于字典的压缩算法,其主要思想是把已输入的数据流的一部分作为字典,编码器为输入流开一个窗口,并随着字符串的编码而把窗口中的数据从右移动到左,因而这种方法是基于一个滑动窗口。LZ77的基本思想可以借助图2表示。

从图2中可以得出LZ77算法的最简单步骤:

(1) 从当前压缩位置开始,考察未编码的数据,并试图在滑动窗口中找出最长的匹配字符串,如果找到,则进行步骤(2),否则进行步骤(3);

(2) 边界的偏移,len为可匹配的长度,C为下一个字符。然后将窗口向后滑动len+1个字符,继续步骤(1);

(3) 输出三元符号组(0,0,C)。其中C为下一个字符。然后将窗口向后滑动len+1个字符,继续步骤(1);

解压缩的过程十分简单,只要像压缩时一样维护好滑动的窗口,随着三元组的不断输入,在窗口中找到相应的匹配串,缀上后继字符C输出(如果off和len都为0则只输出后继字符C)即可还原出原始数据。

2Huffman和LZ77算法的压缩效果对比

2.1 水声通信数据压缩率对比

Huffman算法编程实现之后,为了试验针对不同文件类型的压缩效果,分别使用TXT文档和WAV音频进行压缩对比。为了得到正确的压缩结果,对每种类型各取10个样本进行压缩。其中TXT文档内容为水声通信解码的数据, WAV音频则为接收到的水声信号。压缩时所使用的机器配置为:酷睿T2050(1.6 GHz),1G内存,120G硬盘,x1450(128M)独显。使用Huffman算法和LZ77算法进行压缩之后的结果对比如表1和表2所示,对TXT文档和WAV音频的压缩率对比如图3～图4所示。

从表1和图3可以看出,Huffman算法对所选文本文档的压缩率稳定在20%～30%之间,LZ77算法对所选文本文档的压缩率稳定在50%～60%之间。同时压缩时间和解压时间随着文件的大小而变化,文件越大,压缩时间越长,解压时间也越长。

通过表2和图4可以看出,Huffman算法对所选WAV音频的压缩率大约为3%左右,压缩效果较差,而LZ77算法对WAV音频的压缩率大约在1.4%左右,压缩效果比Huffman更差。

2.2 水声信号WAV文件压缩速率对比

一般来说,可以用算法的复杂性来衡量一个算法的效率,而算法的复杂性分为算法的时间复杂性和空间复杂性。算法的时间复杂性越高,算法的执行时间越长;反之,执行时间越短。算法的空间复杂性越高,算法所需的存储空间越多;反之越少。在算法的复杂性分析中,对时间复杂性的分析考虑的更多[13]。

针对本文的两个程序,考虑当输入规模为n时,Huffman算法内部的循环体执行了n2次,这个次数再乘以一个常数因子,便决定了Huffman算法的执行时间。因此Huffman算法的时间复杂性是O(n2)。LZ77算法内部的循环体也执行了n2次,所以LZ77算法的时间复杂性同样是O(n2)。

但是根据测试结果,同样压缩1.67 MB的文本文档,Huffman算法仅仅需要0.312 s,而LZ77却需要4.671 s。其实,这是常数因子所起的作用,可以推测LZ77算法的常数因子较大。按照这一思路,在源文件不断增大的过程中,两种算法运行时间的增加速度将会大致相同。为了验证这一点,选用不同大小的水声信号WAV文件进行了测试。测试时所使用的机器配置为:酷睿T2050(1.6 GHz),1G内存,120G硬盘,x1450(128M)独显。测试结果如表3所示。

通过表3可以看出,在压缩源文件不断增大的过程中,LZ77压缩算法的压缩时间T2和Huffman算法的压缩时间T1的增长速度基本持平。由此,以下猜测得以验证:LZ77和Huffman算法的时间复杂性都是O(n2),所不同的是常数因子。可以预测,在压缩更大的水声WAV文件的时候,LZ77算法的执行时间将依然保持在Huffman算法执行时间的4倍左右。

3结语

在本文中,重点介绍了Huffman算法和LZ77算法的基本原理。在编程实现两种算法之后,通过对不同类型文件的压缩对比,可以看出,针对水声领域解码之后的TXT文件数据,LZ77的压缩率优于Huffman,而针对接受到的水声信号WAV文件,Huffman则要优于LZ77。此外,对于要求压缩速率的场合,Huffman算法要远远优于LZ77算法。

摘要：为了选择适合水声通信数据无损压缩的算法,对哈夫曼压缩算法和LZ77压缩算法进行了对比研究。通过C语言编程实现两种算法的压缩,并利用水声通信数据获得压缩结果。对两种算法的压缩率和压缩效率对比分析之后,得出结论:对于水声信号,使用哈夫曼算法将获得更好的压缩率和压缩速率。尤其是哈夫曼算法的压缩速率远远优于LZ77算法。

关键词：无损数据压缩,水声通信,哈夫曼算法,字典模型算法

无损数据压缩 篇2

气象雷达原始回波数据包含了大气层云雨生消演变过程的动态信息, 反映了云雨的变化轨迹, 这些正是自然长年累月不断演变的痕迹。痕迹的生消是瞬间、不可逆不可重复的, 因此保存含有这些信息的雷达原始回波数据对于研究大自然的演变规律尤为重要[1]。雷达原始回波数据的数据量多、文件大, 利用有效的压缩算法对雷达的原始回波数据进行无损数据压缩具有非常重要的意义。

2 压缩算法的设计原理

文本类型雷达原始回波数据文件中含有较丰富的换行符和回车符, 这些都是冗余信息。根据这个特点, 可以首先利用位图压缩算法对这两种字符进行压缩。雷达原始回波数据的文本文件中包含“0-9”、“-”、空格符以及换行符共13个字符, 它们对应的ASCII编码如表1所示。通过观察可知, 字符“0-9”的ASCII编码连续且均以特征位“3”开头, 而其它三个字符 (“-”、空格符和换行符) 的ASCII编码则不具备这个特点。为了对该文本文件进行有效压缩, 首先对这三个字符按照表1中约定的值进行重新编码, 即:将“-”、空格符和换行符分别编为0x3A、0x3B和0x3C。这样, 经过重新编码后的值在0x30-0x3C的范围内, 且13个字符的编码均以特征位“3”开头, 如表1所示。现在, 就可以采用半字节压缩[2]的方法对重新编码后的文本数据进行压缩, 即:首先将每个字符的特征位压缩掉, 然后将两个字符对应的半字节压缩存储到一个字节中。最后, 对经过半字节压缩处理后的文本数据再进行Huffman压缩[3], 从而构成了位图压缩+半字节压缩+Huffman压缩算法, 以下简称为b Map-HalfB-Huf算法。

3 压缩过程

在b Map-HalfB-Huf算法的压缩过程中, 用0标识换行符和回车符, 用1标识其它字符。具体压缩过程可表述如下:打开源文件, 按顺序每次读取一个字符, 判断该字符是否为换行符或回车符, 如果是, 则将位图信息的相应位置0, 并丢掉该字符;若不是, 则将位图信息的相应位置1, 并将该字符存储到缓存中。此外, 每读取8个字符, 就将生成的位图信息及字符信息依次存储到缓存中。对整个文本文件的数据进行位图压缩完毕后, 然后将按顺序每次读取字符信息中的两个字符, 判断读取的两个字符数值是否均在0x30-0x39的范围之内, 若不在, 则首先对照表1进行编码, 然后再进行半字节压缩处理;若在, 则直接进行半字节压缩处理。半字节压缩过程是:分别将两个字符的低4位取出, 丢掉高4位的特征值位“3”, 再将高地址字符低4位作为新生成字符的高4位, 而低地址字符的低4位字符信息作为新字符信息的低4位信息, 这样就将两个具有相同特征值位的字符信息压缩处理成一个字符信息。对进行半字节压缩后的文本数据再进行Huffman压缩, 并将源文件的大小、压缩文件的大小及压缩后的信息依次存储到压缩文件中, 压缩过程完毕。b Map-HalfB-Huf算法的压缩流程如图1所示。

4 解压过程

压缩是解压的逆过程, 可以按照压缩的逆序进行。在压缩文件中存储了源文件大小和压缩文件大小, 目的是为了保证对压缩文件能够进行正确解压。b Map-HalfB-Huf算法的解压过程如下:打开压缩文件, 首先, 读取前两个整型数据, 这两个整型数据分别表示源文件的大小和压缩文件的大小。然后, 读取压缩信息, 对其进行Huffman解压, 得到半字节压缩信息;然后进行半字节解压, 半字节解压缩的具体过程是:首先将解压的字符信息的高4位与低4位信息分离, 然后将低4位信息作为生成的低地址字符的低4位信息, 而分离出的高4位信息则作为另一个生成字符的低4位信息, 并将此字符存储在前一字符的高1的地址中, 两个字符信息的高4位均用特征值3进行填充, 半字节解压完成。

将半字节解压后的数据信息再按照表1进行译码, 若字符值不在0x30-0x39之间, 则须将字符进行译码操作, 完成译码之后的数据进行位图解压, 恢复原始文件。

5 实验结果

实验数据为实测的雷达原始回波低仰角的I、Q通道混合的文本类型数据, 该文件的大小为3187KB, 以下称为混合数据文件。将I、Q通道数据分离后的文件大小分别是1597KB和1591KB, 以下分别称为I路数据文件和Q路数据文件。压缩的实验结果见表2。采用混合压缩文件将设计的混合压缩算法与通用的压缩算法及压缩软件进行了性能比较, 比较结果见表3 (其中Arith-0表示自适应算术压缩算法, Arith-3表示3阶自适应压缩算法) 。

从表3的压缩结果可以看出, Arith-3算法具有最高的压缩因子, 但其压缩时间和解压时间都比其它算法要长得多。除此之外, 压缩因子最高的是本文的b Map-HalfB-Dhuf算法, 其次是LZW算法;压缩时间最短的是Huffman算法, 其次是b Map-HalfB-Dhuf算法, 但两者差别很小, 仅0.094s;解压时间最短的是WinZip压缩软件, 其次是WinRar压缩软件, 再次是LZW算法及Huffman压缩算法, 然后是本文的b Map-HalfB-Dhuf算法。

由于本文对雷达原始回波进行压缩不仅要求高的压缩因子, 还需要算法有较短的压缩时间, 这样才会在有效的时间内存储或者传输更多的雷达原始回波数据。因此从压缩因子和压缩时间上对压缩算法的性能进行评价, 可以得出:b Map-HalfB-Dhuf算法是以上所有算法中压缩性能最高的算法。从而说明采用b Map-HalfB-DHuf算法对文本类型雷达原始回波数据文件进行压缩是非常有效的。

6 总结

本文主要是对实测气象原始回波文本类型数据进行无损压缩算法研究, 根据文本类型回波数据文件空白字符较丰富及文件仅由13个字符构成的特点, 并根据此特点设计了文本类型的混合压缩算法。将设计的通用压缩算法对实测数据进行了压缩解压实验, 并与通用压缩算法及通用压缩软件WinRar、WinZip的压缩性能进行了综合比较, 比较结果表明设计b Map-HalfB-DHuf算法压缩性能优于通用压缩软件及算法, 可见设计的此压缩算法对文本类型气象回波数据压缩效果是非常显著的。

摘要：本文对气象雷达原始回波文本类型数据进行无损压缩算法研究, 根据文本类型数据的特点, 设计了位图压缩+半字节压缩+双Huffman压缩的混合压缩算法。采用设计的混合压缩算法对实测数据在C环境下进行压缩和解压实验, 结果表明:混合压缩算法的压缩性能优于通用压缩软件WinRar、WinZip的压缩性能。

关键词：无损数据压缩,位图压缩,半字节压缩,混合压缩

参考文献

[1]王立华, 蓝天飞.使用压缩算法实现雷达原始资料共享的技术方法[J].湖北气象.2003, 32-34.

[2]袁玫等.数据压缩技术及应用[M].电子工业出版社:1995.

[3]吴乐南.数据压缩[M].电子工业出版社:2000.

无损数据压缩 篇3

自从有计算机以来, 它的数据存储和传播能力一直在不断的发展, 到目前已经达到了非常强大的地步。然而, 这一时期也是人类的知识爆炸式发展的一个时期, 很难衡量他们哪一个的速度更快。但是我们总能听到电脑用户抱怨磁盘空间不足, 花费太长的时间下载需要的文件, 从人们在使用计算机的过程中可以看到我们仍然期望计算机存储数据和传播数据的能力不断提高。当然我们可以升级计算机硬件, 来提高电脑的性能, 同时, 计算机厂家不断涌现的新型号也意味着这一策略的庞大成本。在同样的硬件条件下, 采用数据压缩可以存储更多的数据、获得更高的传输性能。另外, 便捷终端、微型设备的出现更是需要很好的压缩算法来支持。比方说, 遍布于数码录音笔、数码相机、数码随身听、数码摄像机等各种数字设备中的音频、图像、视频信息, 就必须经过有效的压缩才能在硬盘上存储或是通过 USB 电缆传输。主要讨论几种常见的无损压缩算法, 分析其原理, 并通过对比给出其优缺点。最后给出GZIP在Java Web程序中的一种应用。

2 Huffman编码

Huffman编码是一种常用的压缩方法。是1952年为文本文件建立的, 其基本原理是频繁使用的数据用较短的代码代替, 很少使用的数据用较长的代码代替, 每个数据的代码各不相同。这些代码都是二进制码, 且码的长度是可变的。如: 有一个原始数据序列, ABACCDAA则编码为A (0) , B (10) , C (110) , (D111) , 压缩后为010011011011100。

Huffman编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号, 长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示, 而不常见的符号需要很多为来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而, 它并不处理符号的顺序和重复或序号的序列。而且产生霍夫曼编码需要对原始数据扫描两遍, 第一遍扫描要精确地统计出原始数据中的每个值出现的频率, 第二遍是建立霍夫曼树并进行编码, 由于需要建立二叉树并遍历二叉树生成编码, 因此数据压缩和还原速度都较慢。

2.1 Huffman编码的压缩原理

Huffman编码是一种可变长编码方式, 是由美国数学家David Huffman创立的, 是二叉树的一种特殊转化形式。编码的原理是:将使用次数多的代码转换成长度较短的代码, 而使用次数少的可以使用较长的编码, 并且保持编码的唯一可解性。Huffman算法的最根本的原则是:累计的 (字符的统计数字*字符的编码长度) 为最小, 也就是权值 (字符的统计数字*字符的编码长度) 的和最小。

2.2 Huffman树

首先统计各个符号在文件中出现的次数, 然后根据符号的出现次数, 建立Huffman树, 通过Huffman树得到每个符号的新的编码。对于文件中出现次数较多的符号, 它的Huffman编码的位数比较少。对于文件中出现次数较少的符号, 它的Huffman编码的位数比较多。然后把文件中的每个字节替换成他们新的编码。

建立Huffman树:

把所有符号看成是一个结点, 该结点的值为它的出现次数。进一步把这些结点看成是只有一个结点的树。每次从所有树中找出值最小的两个树, 为这两个树建立一个父结点, 把这两个树和它们的父结点组成一个新的树, 新树的值为它的两个子树的值的和。如此往复, 直到最后所有的树变成了一棵树。我们就得到了一棵Huffman树。

通过Huffman树得到Huffman编码:

Huffman树是二叉树, 它的所有叶子结点就是所有的符号, 它的中间结点是在产生Huffman树的过程中不断建立的。我们在Huffman树的所有父结点到它的左子结点的路径上标上0, 右子结点的路径上标上1。现在我们从根节点开始, 到所有叶子结点的路径, 就是一个0和1的序列。我们用根结点到一个叶子结点路径上的0和1的序列, 作为这个叶子结点的Huffman编码。

例如:有一个文件的内容如下:abbbbccccddde

统计各个符号的出现次数:

a (1) , b (4) , c (4) , d (3) , e (1)

建立Huffman树的过程如图1所示。

通过最终的Huffman树, 我们可以得到每个符号的Huffman编码。

a 为 110, b 为 00, c 为 01, d 为 10, e 为 111。

Huffman树使用变长编码。对于变长编码, 可能会遇到一个问题, 就是重新编码的文件中可能会无法如区分这些编码。比如, a的编码为000, b的编码为0001, c的编码为1, 那么当遇到0001时, 就不知道0001代表ac, 还是代表b。出现这种问题的原因是a的编码是b的编码的前缀。由于Huffman编码为根结点到叶子结点路径上的0和1的序列, 而一个叶子结点的路径不可能是另一个叶子结点路径的前缀, 所以一个Huffman编码不可能为另一个Huffman编码的前缀, 这就保证了Huffman编码是可以区分的。

2.3 使用Huffman编码进行压缩和解压缩

为了在解压缩的时候, 得到压缩时所使用的Huffman树, 我们需要在压缩文件中, 保存树的信息, 也就是保存每个符号的出现次数的信息。

压缩:读文件, 统计每个符号的出现次数。根据每个符号的出现次数, 建立Huffman树, 得到每个符号的Huffman编码。将每个符号的出现次数的信息保存在压缩文件中, 将文件中的每个符号替换成它的Huffman编码, 并输出。

解压缩:得到保存在压缩文件中的, 每个符号的出现次数的信息。根据每个符号的出现次数, 建立Huffman树, 得到每个符号的Huffman编码。将压缩文件中的每个Huffman编码替换成它对应的符号, 并输出。

3 LZ77算法

LZ77算法是字符串匹配的算法。例如:在一段文本中某字符串经常出现, 并且可以通过前面文本中出现的字符串指针来表示。当然这个想法的前提是指针应该比字符串本身要短。

例如, 在上一段短语“字符串”经常出现, 可以将除第一个字符串之外的所有用第一个字符串引用来表示从而节省一些空间。

一个字符串引用通过下面的方式来表示:

* 唯一的标记

* 偏移数量

* 字符串长度

由编码的模式决定引用是一个固定的或变动的长度。后面的情况经常是首选, 因为它允许编码器用引用的大小来交换字符串的大小 (例如, 如果字符串相当长, 增加引用的长度可能是值得的) 。

3.1 LZ77 算法原理

LZ77是 Abraham Lempel 在 1977 年发表的无损数据压缩算法。LZ77算法是基于字典的编码器。LZ77 算法通过使用编码器或者解码器中已经出现过的相应匹配数据信息替换当前数据从而实现压缩功能。这个匹配信息使用称为长度-距离对的一对数据进行编码, 它等同于“每个给定长度个字符都等于后面特定距离字符位置上的未压缩数据流。” (“距离”有时也称作“偏移”) 。

编码器和解码器都必须保存一定数量的最近的数据, 如最近 2 KB、4 KB 或者 32 KB 的数据。保存这些数据的结构叫作滑动窗口, 因为这样所以 LZ77 有时也称作滑动窗口压缩。编码器需要保存这个数据查找匹配数据, 解码器保存这个数据解释编码器所指代的匹配数据。所以编码器可以使用一个比解码器更小的滑动窗口, 但是反过来却不行。

3.2 LZ77 算法的基本流程

1) 从当前压缩位置开始, 考察未编码的数据, 并试图在滑动窗口中找出最长的匹配字符串 (使用哈希表) , 如果找到, 则进行步骤 2, 否则进行步骤 3。

2) 输出三元符号组 (off, len, c) 。其中 off为窗口中匹配字符串相对窗口边界的偏移, len为可匹配的长度, c为下一个字符。然后将窗口向后滑动len+1个字符, 继续步骤1。

3) 输出三元符号组 (0, 0, c) 。其中c为下一个字符。然后将窗口向后滑动len+1个字符, 继续步骤1。

结合实例来说明。假设窗口的大小为10个字符, 刚编码过的10个字符是:abcdbbccaa, 即将编码的字符为:abaeaaabaee。可以直接和要编码字符匹配的最长串为ab (off= 0, len=2) , ab的下一个字符为a, 我们输出三元组: (0, 2, a) 。现在窗口向后滑动3个字符, 窗口中的内容为:dbbccaaaba。下一个字符e在窗口中没有匹配, 我们输出三元组: (0, 0, e) 。窗口向后滑动1个字符, 其中内容变为:bbccaaabae。所以要编码的aaabae在窗口中存在 (off=4, len=6) , 其后的字符为 e, 可以输出: (4, 6, e) 。这样, 我们将可以匹配的字符串都变成了指向窗口内的指针, 并由此完成了对上述数据的压缩。

解压缩的过程十分简单, 只要我们向压缩时那样维护好滑动的窗口, 随着三元组的不断输入, 我们在窗口中找到相应的匹配串, 缀上后继字符c输出 (如果off和len都为0则只输出后继字符c) 即可还原出原始数据。

3.3 LZ77 算法的编码方法

必须精心设计三元组中每个分量的表示方法, 才能达到较好的压缩效果。一般来讲, 编码的设计要根据待编码的数值的分布情况而定。

3.3.1 编码偏移值 (off)

偏移接近窗口尾部的情况要多于接近窗口头部的情况, 这是因为字符串在与其接近的位置较容易找到匹配串, 但对于普通的窗口大小 (例如:4096 字节) 来说, 偏移值基本是均匀分布的, 可以用固定的位数来表示它。

需要的位数bitnum=upper_bound ( log2 ( MAX_WND_SIZE ) )

由此, 如果窗口大小为4096, 用12位就可以对偏移编码。如果窗口大小为2048, 用11位就可以了。

复杂一点的程序考虑到在压缩开始时, 窗口大小并没有达到 MAX_WND_SIZE, 而是随着压缩的进行增长, 因此可以根据窗口的当前大小动态计算所需要的位数, 这样可以略微节省一点空间。

3.3.2 编码字符串长度 (len)

匹配的字符串长度在多数时候时不会太大, 少数情况下才会发生大字符串的匹配。显然可以使用一种变长的编码方式来表示该长度值。要输出变长的编码, 该编码必须满足前缀编码的条件。Huffman编码便可以在此处使用 (但不是最好的选择。适用于此处的好的编码方案很多, 比如Golomb编码) 。

4 LZW算法

LZW算法是基于LZ77思想的一个变种。LZW压缩效率较高。其基本原理是把每一个第一次出现的字符串用一个数值来编码, 在还原程序中再将这个数值还成原来的字符串, 如用数值0x100代替字符串"abccddeee"这样每当出现该字符串时, 都用0x100代替, 起到了压缩的作用。至于0x100与字符串的对应关系则是在压缩过程中动态生成的, 而且这种对应关系是隐含在压缩数据中, 随着解压缩的进行这张编码表会从压缩数据中逐步得到恢复, 后面的压缩数据再根据前面数据产生的对应关系产生更多的对应关系。直到压缩文件结束为止。LZW是可逆的, 所有信息全部保留。LZW属于无损压缩编码, 该编码主要用于图像数据的压缩。对于简单图像和平滑且噪声小的信号源具有较高的压缩比, 并且有较高的压缩和解压缩速度。由于专利权原因, LZW没有得到像LZ77一样的流行。

5 DEFLATE方法

DEFLATE方法是LZ77算法与Huffman编码的组合。GZIP、ZIP即采用这个方法。如前所述, LZ77算法先将文件压缩表示为 (唯一的标记, 偏移量, 字符串长度) 三元组的方式, Huffman编码再进一步对偏移量、字符串长度进行压缩。在LZ77算法中, 需要利用哈希表对字符串进行匹配。

DEFLATE方法集合了LZ77与Huffman编码的优势。并且不受任何专利权制约。它具有通用的开放源码无版权工业标准, 因此得到了广泛的应用。

6 GZIP压缩在Java Web程序中的应用

DEFLATE方法用途十分广泛, 采用它的GZIP压缩目前在HTTP压缩中非常流行。随着互联网和企业信息化的不断发展, 越来越多的系统采用B/S的架构, 使用Java Web程序或J2EE框架无疑是实现B/S架构最好的方法之一。随着系统规模的扩大, 系统性能的优化也是软件工程师和用户关心的主要问题。解决这类问题, 一般会想到的是数据库调优、程序代码优化或缓存处理, 诚然这些方法可以提高系统的性能, 这里要说的是另一种方式:在Web应用中采用GZIP压缩技术, 减少网络数据的传输量。在Java Web程序中有两种方式运用GZIP压缩技术。

6.1 设置Web服务器

目前大部分Java Web服务器都支持GZIP压缩技术, Tomcat服务器从版本5.0之后开始支持对输出内容压缩, 下面是在tomcat 6.0.20环境下中开启GZIP的方法。

在tomcat的安装目录下找到conf目录, 打开server.xml文件可以看到如下内容:

6.2 使用filter方式

这种方式主要是对HttpServletResponse 进行包装, 获取它向客户端浏览器所有的输出, 用filter进行GZIP处理, 等处理完毕, 再输出其内容到HttpServletResponse 对象中。J2EE框架中已经定义了一个HttpServletResponseWrapper类使得包装HttpServletResponse更加容易。

首先定义Wrapper 用来包装HttpServletResponse 对象:

7 结束语

随着网络承载的信息的飞速增长, 数据压缩必然会备受重视。本文比较了几种常见无损压缩算法, 详细分析了使用广泛的DEFLATE方法, 在本文的最后指出了GZIP压缩的一种应用。LZW压缩技术有很多变体, 例如常见的ARC、RKARC、PKZIP高效压缩程序, 但由于LZW 拥有专利, 所以使用的范围受到限制。DEFLATE同时使用了LZ77算法与哈夫曼编码, 不受任何专利所制约。文章只讨论了数据压缩在某一方面的应用, 事实上数据压缩已经在信息技术上广泛应用, 并将在深度和广度上不断延伸。

参考文献

[1][LZ77]Ziv J, Lempel A.A Universal Algorithm for Se-quential Data Compression[J].IEEE Transactions on In-formation Theory, 23 (3) :337-343.

[2]A Method for the Construction of Minimum-RedundancyCodes[J].David A.Huffman, 1952.

[3]吴乐南.数据压缩 (第2版) .电子工业出版社, 2008.

[4]MARK ALLEN WEISS.数据结构与算法分析—C语言描述[M].机械工业出版社, 2004.

[5]吴家安.数据压缩技术及应用[M].科学出版社, 2009.

数字影像无损压缩算法研究 篇4

随着计算机技术、通讯技术和生物医学工程技术等相关技术的高速发展, 通过对医学影像进行数字化处理, 进行计算机智能化处理, 将使依据医学影像进行的诊断放弃传统的肉眼观察和主观判断, 并可依据同一影像进行多种疾病的诊断和多科疾病的诊断。在应用计算机技术后, 医学影像将从形态图像向功能图像转变, 对医学影像数据库和特征库的内容进行提取分析, 将可以帮助医生进行科学的诊断, 提高诊断的科学性、客观性和准确性。

应用DICOM3标准和网络通讯协议标准TCP/IP可以方便地实现对直接具有数字化接口的影像设备的成像数据的提取;小波分析 (Wavelet Analysis) 在时域和频域同时具有良好的局部化性质, 而且由于对图像信号的高频成分采用转件精细的时域或频域取样补偿, 从而可以聚焦到对象的任何细节, 这一特点在医学影像分析中将得到较好的应用。

1总体方案设计

ACR和NEMA联合组成委员会在1993年发布的医学数字成像与通信 (Digital Imaging and Communication in Medicine, DICOM) 标准3.0, 是医学影像设备间联网的专用数字接口, 是进行网络通信时应满足的标准协议, 是一组具有DICOM兼容性的设备所共同遵循的协议。在DICOM标准中, 医学图像包含了许多如图像获取设备对图像的分析、医生的报告及患者情况等信息, 这种信息与图像的结合方便了图像的检索、图像的分析和诊断。医学影像处理的总体结构如图1所示。

1.1符合DICOM标准中间件实现方案

DICOM3消息交换的网络支持对应于ISO/OSI定义的网络传输中的会话层、表示层及联接控制服务单元, 这部分底层 (传输控制层、网络层) 的信息交换定义为通用的网络传输协议。在设计实现中将采用智能Agent中间件技术。当设备采集影像数据后, Agent中间件自动将数据传送到医学影像数据库中, 减少不必要操作的处理, 并能保证数据传输的一致性和同步性。

1.2压缩存储中间件实现方案

影像图片大约需要8～15 MHz的存储空间, 为了缩小存储成本和便于网络传输, 必须对图像进行压缩。现阶段常用的压缩存储方案有4种:① 基于JPEG标准下的无损压缩算法JPEG-LS, 这是DICOM标准支持的一种成熟的无损压缩算法;② 基于整数小波变换的单帧图像无损压缩算法, 它利用了医学图像象素之间存在高度的相关性和整数小波的特性;③ 基于三维整数小波的序列图像无损压缩算法, 对整个序列进行无损压缩, 可以有效地提高图像的压缩率;④ 利用JPEG2000标准支持ROI (Region Of Interest 感兴趣区域) 编码的特性, 对图像的ROI进行无损压缩编码, 对次要信息区域 (如背景) 采用高压缩比的有损压缩方法。

本文在综合分析以上4种方案的基础上, 提出了基于适形离散小波变换 (SA-DWT) [1]与整数小波变换相结合的影像无损压缩算法。并应用该方案构件了智能Agent中间件。

1.3检索诊断中间件实现方案

在应用存储的数字化医学影像和影像特征进行诊断时, 需要完成大量的检索和比对处理, 为了减少网络流量, 提高检索速度, 应用了基于小波模极大值及多尺度不变矩相结合的检索算法, 并建立了算法实现的中间件, 运行效果明显, 能够较好地完成影像的检索和诊断作用。

2无损压缩算法研究

无损图像压缩是指解压缩后的图像与原来图像完全相同, 没有任何信息的损失。医学图像是医学诊断和疾病治疗的重要根据, 在临床上具有重要的应用价值。确保医学影像压缩后的高保真度是医学图像压缩首要考虑的因素。现在医学图像常采用无损压缩, 因为它能够精确地还原图像。但是无损图像压缩的缺点是压缩比低, 仅为2～4;而有损图像压缩的压缩比可高达50, 甚至更高。所以将这2种压缩法方法在保证使用要求的基础上结合起来, 在获取高的压缩质量的前提下提高压缩比。本文提出的基于SA-DWT与整数小波变换相结合的压缩算法, 就是应用SA-DWT算法确定感兴趣区域, 对该区域进行无损压缩, 其他区域进行有损压缩, 大大提高了压缩效率, 并不损失影像的医学作用。

2.1SA-DWT算法

传统的二维小波变换都是针对矩形区域进行的, 得到的变换系数个数一般会大于原始区域像素点个数, 而且由于填充, 变换后区域的边界会出现钝化, 所以限制了任意形状区域的编码效率。

现代的患者同一部位的医学影像可以应用到相关的不同的多个诊断过程中, 因此, 整幅影像中可能存在多个特征区域, 而每个区域的形状都不是规则的图形, 不适合采用传统的二维小波变换。本文采用了Li等提出的适形离散小波变换 (SA-DWT) , 该变换可以用于对任意形状的图像对象进行变换, 因此适合与对医学影像中的感兴趣区域进行编码。测试结果表明:

① 变换域的变换系数同像素域的相同;

② 只要采用的L阶小波滤波器具有完全重构特征, 并且下采样的位置已知, 就存在一个唯一的反变换, 可用于完全重构原始的影像;

③ 长度自适应的小波变换保留了分段采样点的位置, 不会产生超出边界的系数。

由于对奇数长度图像信号的剩余采样点进行了缩放, 因此这种任意长度的小波变换得到的低通系数具有相同的尺度, 这就避免了边界处小波系数的突变。

2.2提升算法原理

由Sweldens等提出来的提升方案 (Lift Scheme) 是构造紧支集双正交小波的一种新方法, 被称为“第二代小波”[2], 也叫做整数小波变换。该方法可以将整数映射到整数, 可以实现由SA-DWT算法分割的不同区域内影像的无损压缩。

对于原始信号sj, 经小波分解成为低频信号sj-1和高频细节信号dj-1两部分。有提升方法构成的小波变换包括:分裂 (Split) 、预测 (Predict) 和更新 (Update) 3个步骤。

2.2.1 分裂

此过程是将原始信号sj分裂成2个互不相交的子集sj-1和dj-1, 通常是将这个信号序列分解成偶数序列和奇数序列, 即

split (sj) = (evenj-1, oddj-1) = (sj-1, dj-1) 。

2.2.2 预测

针对数据间的相关性, 可用sj-1去预测dj-1, 故可以采用一个与数据集结构无关的预测算子P, 使得dj-1=p (sj-1) , 这样就可以用子数据集sj-1代替原始数据集sj。若再用子集dj-1与预测值p (sj-1) 之间的差值去代替dj-1, 则此差值反映了二者的逼近程度。如果预测是合理的, 则差值所包含的信息就比原始子集dj-1包含的信息要少得多。预测表达式为:

$\widehat{d}{}_{j-1}=odd{}_{j-1}-p(even{}_{j-1})=d{}_{j-1}-p(s{}_{j-1})$。

将数据集合分成偶数集合和奇数集合后, 最简单的一个预测算子就是用相邻2个偶数的均值来作为它们之间的奇数的预测值, 即

p (sj-1) =s (j, 2k+sj, 2k+2) /2。

由此可得预测表达式为:

$\widehat{d}{}_{j-1,k}=d{}_{j-1,k}-p(s{}_{j-1})=s{}_{j,2k+1}-(s{}_{j,2k}+s{}_{j,2k+2}/2)$。

2.2.3 更新

经过上述2个步骤后, 所产生的系数系数子集sj-1的某些整体性质 (如均值) 并不和原始数据中的性质一致, 因此需要采用更新过程。其目的是通过算子U产生一个更好的子数据集合$\widehat{s}{}_{j-1}$, 使之保持与原始数据集一致的特征。$\widehat{s}{}_{j-1}$定义如下:

$\widehat{s}{}_{j-1}=even{}_{j-1}+U(\widehat{d}{}_{j-1})=s{}_{j-1}+U(\widehat{d}{}_{j-1})$。

具体的更新计算的过程为:

$\widehat{s}{}_{j-1,k}=s{}_{j,2k}+(\widehat{d}{}_{j-1}+\widehat{d}{}_{j-1,k-1})$。

对于数据子集$\widehat{s}{}_{j-1}$重复进行上述相同的3个步骤, 即将$\widehat{s}{}_{j-1}$分解成$\widehat{s}{}_{j-2}$和dj-2, 经过n次分解后, 原始数据sj的小波表示为:

$\{\widehat{\text{s}}{}_{\text{j}-\text{n}},\widehat{\text{d}}{}_{\text{j}-\text{n}},\widehat{\text{d}}{}_{\text{j}-\text{n}+1},\cdots ,\widehat{\text{d}}{}_{\text{j}-2}‚\widehat{\text{d}}{}_{\text{j}-1}\}$。

式中, $\widehat{\text{s}}{}_{\text{j}-\text{n}}$代表了信号的低频部分;$\{\widehat{\text{d}}{}_{\text{j}-\text{n}},\widehat{\text{d}}{}_{\text{j}-\text{n}+1},\cdots ,\widehat{\text{d}}{}_{\text{j}-2},\widehat{\text{d}}{}_{\text{j}-1}\}$代表了信号的高频部分。

重构数据时的提升为:

$\begin{array}{l}s{}_{j-1}=\widehat{s}{}_{j-1}-U(\widehat{d}{}_{j-1})‚\\ d{}_{j-1,l}=d{}_{j-1,l}^{(1)}+a{}_{-1}(s{}_{j-1,l-2}-s{}_{j-1,l-1})‚\\ s{}_j={\rm M}erge(s{}_{j-1},d{}_{j-1})。\end{array}$

2.3整数小波变换

Sweldens已经证明在提升的基础上可以进行整数集到整数集的小波变换。一个整数集合通过小波变换得到的仍然是整数集合。在进行影像压缩编码处理过程中, 不需要对变换后的系数进行量化, 因此可以实现影像的无损压缩。

在进行影像的无损压缩时, 主要采用了S变换和S+P变换。针对影像的特点并结合Haar变换的整型表示方法, 提出如下形式:

S变换之后, 在低通系数sj-1, l的基础上进行线性预测, 以产生新的高通系数dj-1, l, 这就是S+P变换。

2.4实验与分析

在验证算法中, 主要选取了3组MR图像 (256*256*16 bits, 每组30幅) 和2组CT图像 (512*512*16 bits, 每组30幅) , 分别采用了本文提出的算法进行压缩处理, 同时用预测整数小波变换 (简称:PIWT) 、整数小波变换 (IWT) 和差分脉冲编码调制 (DPCM) 等算法对这5组序列影像进行压缩编码, 得到平均压缩率如表1所示。对其中的数据进行分析可知:本算法的压缩率分别比PIWT算法、IWT算法和DPCM算法平均提高81.15%、100.73%和67.61%。表1中的二维算法的压缩率是序列图像中个图像压缩率的平均值。

应用SA-DWT变换可以方便地找到影像中的多个感兴趣区域, 应用整型小波变换对影像象素本身灰度值进行变换, 且保持了变换前后的整数的一致性, 可以实现对感兴趣区域的无损压缩。

在进行若干次提升变换后, 再利用哈夫曼编码对变换后的系数进行编码, 将较好地去除像素间的相关性, 极大地减低了原始图像的信息量。

3结论语

DICOM标准可以方便地将医学影像处理的数据传到计算机中进行处理, HL7标准可以提高医院不同应用软件间的通信能力。根据多媒体技术和关系数据库理论, 建立医学影像数据库。在构建影像数据库和影响特征库时, 为了减少数据存储量, 提高影像传输速率, 而不影响影像的诊断效果的基础上, 本文提出了基于适形离散小波变换 (SA-DWT) 与整数小波变换相结合的影像无损压缩算法, 并构建了该算法的中间件, 在实际的验证测试中, 该算法可以较好地完成影像的压缩存储, 效果良好。

下一步的研究工作将针对目前影像压缩存储算法和影像检索的算法进行深入研究和比较, 进一步发展各种医学影像内容分析的理论和技术, 深入研究能够充分表示医学图像内容的各种特征, 进一步发展系统架构、性能评价、相似性度量方法、人机交互方式、高维度检索和智能诊断等技术。

参考文献

[1]CINKLER K.Very Low Bit-rate Wavelet Video Coding[J].IEEE Journal on Selected Areas in Communication, 1998, 16 (1) :4-11.

无损数据压缩 篇5

1 无损压缩算法

JPEG-LS无损压缩算法的基本思想为[3,4,5]:由当前像素的几个已经出现过的近邻,用其作为当前像素的上下文,用上下文来预测误差,从几个这样的概率分布中选择一个,并根据该分布用一个特殊的Golomb码字来编码预测误差。JPEG-LS图像压缩标准规定的无损和近无损编码处理的主要组成部分如图1所示。

JPEG-LS图像压缩标准采用差分预测编码技术,同时建立了匹配上下文模型,高效地实现了One-pass编码器[6,7],具体算法实现过程如图2所示。

该编码器基于光栅扫描顺序,每次对一个像素进行编码。具体的编码方式分为两种,即正常模式和游长模式,且这两种模式之间是自适应切换的[8,9,10]。

在正常编码模式下,首先采用简单的边缘检测器初步确定一个预测值[11,12];然后再与上下文自适应的预测校正值相结合得到校正预测值;最后使用当前待编码原始像素值减去校正预测值就能得到预测残差,该预测残差的分布满足双边几何分布,利用上下文模型可求得预测残差的编码参数k,熵编码器采用参数k完成Golomb快速一元编码[13,14,15]。当编码器进入游长编码模式时,完成游长计数后,熵编码器采用效率更高的游长编码,从而对平滑图像可进行大倍率的压缩[16]。

2 JPEG-LS无损压缩算法的FPGA实现

采用标准JPEG-LS算法进行无损压缩硬件实现时存在一些不足:

(1)在计算上下文Q时,需要多步串行计算才能得到Q值,关键路径较长,难以满足实时处理的要求;

(2)在计算误差以及误差量化时,采用标准算法时用到浮点乘法,计算精度不能保证,计算复杂度较高,难以满足快速处理的要求;

(3)参数变量更新时,标准算法涉及较多的加减运算和逻辑判断,且诸多操作是串行运算,计算复杂度较高,影响了整个系统运行速度的提升。

JPEG-LS算法包括较多顺序运算步骤,如果直接按照算法实现为硬件逻辑,将会产生较大的延迟时间,严重阻碍时钟频率的提高。

针对以上问题,本文提出的JPEG-LS实现结构以提高最大吞吐量为主要目标,通过多级流水线降低每一级运算的延迟,从而满足更严格的时序约束。除流水线机制外,通过在较细的粒度上实现运算的并行,提高了每一级运算的速度。

2.1 并行运算降低硬件资源消耗

设计采用FPGA片内的Block Ram或Rom资源以存储计算所得的变量值,在JPEG-LS标准中,计算量化梯度合并时,若矢量(Q1,Q2,Q3)的第一个非零元素是一个负数,则必须将该矢量的符合反转得到(-Q1,-Q2,-Q3),此时变量SIGN被设置为-1,反之为+1;在这种可能的合并之后,矢量(Q1,Q2,Q3)以一对一的方式被映射到一个整数Q,其表示采样X的上下文。然而在JPEG-LS标准中并没有规定此映射过程的具体函数,为了能简单实现查找A[Q]、B[Q]、C[Q]、N[Q]表值,将Qi做了优化修改,根据输入的Ra、Rb、Rc、Rd分别计算Rd-Rb、Rb-Rc和Rc-Ra,根据JPEG-LS标准,以这3个梯度值为索引,查表得到3个梯度的量化梯度值id1、id2、id3,在FPGA中使用量化公式

映射后可通过Q值判断SIGN值,若Q>0,则SIGN为1,若Q<0,则SIGN为-1;变量Q则成为索引A[Q]、B[Q]、C[Q]、N[Q]的地址值,此次优化降低了算法复杂度,提高了效率。在计算得到预测值,根据预测值通过量化后得到误差值以及量化误差值的过程如下

此过程实现较为复杂,且周期较长,使得整个过程实时性降低。针对此处计算,设计查询表的方式替代原浮点乘法运算,由于误差Errval的范围在-255~+256之间,所以将Errval之间的值通过上述方法提前算好建立一张Table表存储在FPGA内部资源ROM中,每次只需以误差值为地址去ROM中查找对应的量化误差值即可。通过以上方法,将复杂的算法以及耗时的计算变为了一次查表就能完成,大幅降低了计算量,提高了实时性。

对某一像素编码的最后一步是更新变量A[Q]、B[Q]、C[Q]、N[Q],但该变量更新处理必须在编码过程的最后。为提高编码实时性,使变量的更新周期减少,设计了一种新的变量更新方式,如图3所示。

根据以上变量更新的方法,得到一组新的A[Q]、B[Q]、C[Q]、N[Q]值,并且将其分别存储在FPGA内存双口RAM中,在下一次计算来临时可根据当前计算得到的Q值作为地址,从4个双口RAM中读取上一次更新的A[Q]、B[Q]、C[Q]、N[Q]值,再通过变量更新模块获得新的更新值存入RAM中。

2.2 算法流水线结构

为提高硬件平台操作速率以及考虑到系统的实时性,选用流水线结构是实现此算法的必要途径,如图4所示。为了完全实现此流水线结构,使用了10个时钟周期的流水线阶段。为避免结构图过于复杂,此处仅是正常模式下的流水线结构图,并未给出游程模式结构图。运用此流水线模式可使得硬件电路操作频率达到120 MHz。

如图4所示,10个流水线阶段分别完成以下步骤:

阶段1完成预测值计算以及局部梯度值计算;

阶段2局部梯度值量化;

阶段3查询变量Q地址;

阶段4读取环境变量(上下文)值;

阶段5更新环境变量值;

阶段6~8 3个周期除法器;

阶段9以及预测误差值计算;

阶段10误差映射及产生bit流输出。

在FPGA中利用流水线的方式来实现算法,各模块的计算复杂度基本相同,且几个模块可同时进行计算,减少了每一级的运算时间,提高了系统实时性。

3 实验及结果

为完成整个编码系统,包括预测器和熵编码器两部分功能,选用Altera公司Stratix系列FPGA,在Quartus软件环境下使用Verilog HDL语言进行编程实现。将传统硬件实现方法和前流水线的JPEG-LS硬件实现的内存消耗、消耗逻辑门单元和硬件操作频率做对比,对比结果如表1所示。

由表1可知,采用了全流水线结构来实现JPEG-LS算法,大幅降低了FPGA内存空间占用,内存空间占用被降低了26%。该流水线模式也使得硬件电路操作频率由105 MHz提高到120 MHz,满足严格的时序约束,且提高了压缩算法的实时性。

4 结束语

为满足高速图像传感器系统的吞吐量需求,本文在FPGA中采用全流水线结构,降低了每一级运算的延迟,实现了JPEG-LS无损/近无损图像压缩算法。该算法已在FPGA平台通过验证,实现了大吞吐量的无损图像压缩,可应用于高速图像传输系统中。

摘要：针对采用传统硬件方法实现JPEG-LS无损图像压缩算法时延时较多、实时性较差的问题,文中提出了一种基于FPGA的全流水线结构来实现JPEG-LS算法。该结构以提高最大吞吐量为主要目标,通过多级流水线降低每一级运算的延迟,大幅提高了压缩算法的实时性,硬件电路操作频率可达120 MHz。

无损数据压缩 篇6

高光谱遥感技术是20世纪80年代兴起的新型对地观测技术, 它将确定物质或地物性质的光谱与把握其空间和几何关系的图像革命性地结合在一起[1]。光谱连续特点使其获取的数据提供了丰富的地物细节, 在国民经济的各个方面获得了广泛应用。随着谱间和空间分辨率的不断增加, 成像光谱仪获取的高光谱数据越来越大, 限制了它在实际中的应用, 必须采用高效的压缩方法对其进行压缩。高光谱数据的获取非常昂贵, 其后续应用主要集中于特征提取、目标检测与分类等领域, 因而无损压缩则成为首选方案。

高光谱数据可以看作准三维图像, 在二维图像的基础上, 增加一维光谱信息。信息冗余来源于空间和谱间的相关性, 其中空间相关性较低, 而谱间具有较强的相关性。现有去除空间相关性的技术已经比较成熟, 如何有效去除谱间相关性, 已成为提高压缩性能的关键。高光谱图像无损压缩方法可以分为基于预测的方法[2,3,4], 基于整数变换的方法[5,6], 基于矢量量化的方法[7], 或者多种方法结合使用。基于预测的方法应用于有损压缩会产生误码传递[8]。Mielikainen J等人提出了基于聚类DPCM (differential pulse code modulation) 的高光谱图像无损压缩算法, 在使用较多参考波段情况下取得了较好的压缩效果, 但算法的复杂度偏高[7]。Zhang J等人将预测误差反馈机制引入谱间预测中, 提高了预测性能[8]。目前, 较多基于预测的方法都结合了聚类、神经网络等技术, 运算量过大, 并且产生了大量附加信息。本文提出一种基于波段分组的高光谱图像无损压缩算法, 为了减少了波段排序算法的计算量, 它根据相邻波段相关性预先进行分组。通过对波段排序算法性能进行研究, 以及对各组波段进行最佳后向排序, 谱间预测结合了最小二乘准则的最优预测, 仿真结果证明了算法的有效性。

1 波段分组

由于波段的自然顺序无法取得较好的预测性能, 根据高光谱图像的特点对波段重新排序非常必要。直接对全部波段进行整体排序, 计算量较大。实验发现, 若波段之间相距较远, 其相关性一般较差, 若预先进行波段分组GOB (group of bands) , 之后对各组进行排序, 可显著减少波段的搜索范围, 从而降低排序算法的计算量。本文根据相邻波段之间相关性来确定GOB的大小, 相关系数的定义如下:

$R{}_{i,j}=\frac{{\displaystyle \sum _{i,j}(}X{}_i-\overline{X})(Y{}_j-\overline{Y})}{\sqrt{{\displaystyle \sum _i(}X{}_i-\overline{X}){}^2{\displaystyle \sum _j(}Y{}_j-\overline{Y}){}^2}}(1)$

式中:Xi和Yj为两个不同波段数据;$\overline{X}$和$\overline{Y}$分别为相应的波段均值。根据式 (1) 计算OMIS-I型高光谱图像相邻波段的相关系数可知, 该型数据的第64波段、第79波段、第98波段和第113波段附近的相关性较差。这些波段与其相邻波段之间不适合进行谱间预测, 采用谱内压缩反而会得到较好的效果。借鉴文献[10]的分组思路, 给出如下波段分组方法:

(1) 计算相邻波段的相关系数Ri, i+1 (0≤i≤D-2) , 其中D为总的波段数;设置阈值T, 若R≥T, 则将该两个波段归为同一GOB, 否则置于不同的GOB;

(2) 若GOB中的波段数大于P, 则将GOB中每P个波段作为一个波段子集SOB (subset of bands) ;若有剩余波段, 则单独作为一个SOB。

2 波段排序

为了提高预测精度, 需要对各个GOB (SOB) 进行波段排序。波段排序是指定义一个波段排列顺序, 指定先编码的波段, 并作为后续待编码波段的参考波段。目前采用较多的排序算法为:单调前向排序、单调后向排序、最佳前向排序、最佳后向排序以及最小生成树排序 (Prim算法) [11]。单调前向 (后向) 排序是指当前波段仅利用与其相邻之前 (或之后) 的波段进行预测;而最佳前向 (后向) 排序指当前波段在其之前 (或之后) 的所有波段中搜索最佳预测波段。若i表示当前要预测的波段, 则σ (i) (0≤i<D) 为排序函数, 上述几种排序算法及运算复杂度的描述如表1所示。

最小生成树排序是将用最小预测误差原则选择最优参考波段问题归结到搜索一个图结构的最小加权生成树的优化问题, 可以获得理论上最优的预测效果。由于需要计算任意两个波段之间的预测误差均方值, 故计算量较大。文献[11]给出的实验结果表明, 后向排序的预测效果优于前向排序的预测效果, 最佳后向排序可以获得接近最小生成树的预测效果。考虑预测性能和复杂度两方面因素, 本文采用最佳后向排序算法对各个GOB (SOB) 进行波段排序, 利用波段之间的互相关系数代替MSE作为搜索原则, 可显著提高搜索速度。对于GOB中存在多个SOB的情况, 除最后一个SOB外, 其他SOB的最后一个波段均在与其相邻的后一个SOB中搜索最佳参考波段, 使得每个GOB中只有一个波段采用谱内压缩方式。对于用特定光谱成像仪获取的高光谱图像, 波段之间的相关性是由遥感器决定的, 与图像内容无关, 因而上述波段的分组和排序结果, 可以应用于大部分用该光谱成像仪获取的高光谱图像。

3 基于最小二乘准则的谱间最优预测

高光谱图像的内容比较丰富, 纹理较为细密, 利用波段内所有像素计算预测系数不可取。通常的做法是先对波段进行聚类, 对各个分类分别计算最佳的预测系数, 但聚类算法计算量较大, 并且会导致较多的附加信息。在当前像素的局部邻域范围内可以认为是平稳的, 利用邻域像素进行预测可以获得较好的效果。本文采用与当前像素具有相同空间位置的参考波段像素进行谱间线性预测, 同时在参考波段和当前波段中选取具有相同空间位置的邻域结构, 在该邻域内利用最小二乘准则求得最优谱间预测系数。具体算法:若pk (i, j) 表示第k个波段中第i行、第j列的像素值;$\widehat{p}$k (i, j) 表示其预测值;ek (i, j) 表示预测误差, 则当前像素pk (i, j) 的谱间线性预测值为:

$\widehat{p}{}_k(i,j)={\displaystyle \sum _{m=1}^L\alpha }{}_{m}p{}_{k-m}(i,j)+\beta (2)$

式中:L为预测阶数。预测误差ek (i, j) 表示为:

$e{}_k(i,j)=|p{}_k(i,j)-\widehat{p}{}_k(i,j)|(3)$

在当前波段中选取与pk (i, j) 相邻的K点局部邻域, 该局部邻域中的像素表示为[qk, 1, …, qk, K]T, 按照下式给出的准则计算预测系数α=[α1, α2, …, αL, β]T

$\arg (\underset{\mathit{\alpha }}{{\displaystyle \min }}({\displaystyle \sum _{n=1}^{{\rm K}}[}q{}_{k,n}-\widehat{q}{}_{k,n}]{}^2))(4)$

上式可表示为:

$\psi =(\mathit{Q}\mathit{\alpha }-\mathit{C}){}^{\text{Τ}}(\mathit{Q}\mathit{\alpha }-\mathit{C})(5)$

式中:

$\mathit{Q}=\left[\begin{array}{cccc}q{}_{k-1,1}& \cdots & q{}_{k-L,1}& 1\\ ⋮& ⋮& ⋮& ⋮\\ q{}_{k-1,{\rm K}}& \cdots & q{}_{k-L,{\rm K}}& 1\end{array}\right];\mathit{C}=\left[\begin{array}{l}q{}_{k,1}\\ ⋮\\ q{}_{k,{\rm K}}\end{array}\right](6)$

预测目标在于使式 (5) 最小化, 由此可以得到最佳预测系数:

$\mathit{\alpha }=(\mathit{Q}{}^{\text{Τ}}\mathit{Q}){}^{-1}(\mathit{Q}{}^{\text{Τ}}\mathit{C})(7)$

由式 (7) 可知, 求解α的运算量随着K和L的增大而增加。综合考虑压缩性能和运算量两方面因素, 选取K=4, L=1。图1所示为参考波段与当前波段相同位置上的邻域结构。其中, Y为当前波段待预测像素;X与Y具有相同的空间位置;Y1～Y4和X1～X4分别对应qk, 1～qk, 4与qk-1, 1～qk-1, 4。

由于利用当前像素之前的已编码邻点进行预测, 预测系数无需作为附加信息进行传输。采用该邻域结构的另一个优点是可以采用逐行处理方式来降低对变换内存的要求。由于JPEG-LS无损压缩标准具有较高的压缩性能和运算效率, 故采用该标准对参考波段和预测残差进行无损压缩。需要指出的是, 在对预测残差进行JPEG-LS压缩前, 需要将残差图像映射到非负空间。若M表示映射函数, ek表示第k波段的预测残差最小值, 则映射后的数据表示为:

${\rm M}[e{}_k(i,j)]=\{\begin{array}{cc}e{}_k(i,j)‚& e{}_k\ge 0\\ e{}_k(i,j)-e{}_k‚& e{}_k<0\end{array}$

4 实验结果与讨论

为验证所提算法的有效性, 利用VC++软件对128波段OMIS型高光谱图像进行了仿真实验。实用型模块化成像光谱仪 (OMIS) 是我国自行研制的成像光谱仪, 它覆盖了从可见光到热红外的波段范围。图2给出了压缩后各波段的bpp曲线图。

可以看出, 多波段预测算法压缩后个别波段bpp要高于谱内JPEG-LS压缩。本文算法进行了波段分组, 很好地解决了这一问题。

5 结 语

本文提出了一种基于波段分组的无损压缩算法。在波段分组的基础上, 对各组进行最佳后向排序, 谱间预测结合了最小二乘的最优预测, 实验结果表明了算法的有效性。多波段预测较多地应用于无波段排序的压缩算法中, 由于预先进行了波段排序, 采用一个参考波段即可获得较好的压缩效果。此外, 本文对波段排序算法性能的研究对后续相关工作具有参考价值。基于上述实验结果, 算法还可以从以下2个方面进行研究:

(1) 高光谱图像内容比较丰富, 不同地物边界处的像素应该单独进行预测;

(2) 谱间只进行前向预测, 双向谱间预测是一种更具潜力的压缩思路, 这也是下一步的研究内容。

摘要：高光谱图像海量数据给存储和传输带来极大困难, 必须对其进行有效压缩。针对高光谱图像不同频谱波段间相关性不同的特点, 提出一种基于波段分组的高光谱图像无损压缩算法。为了降低波段排序算法的计算量, 根据相邻波段相关性大小预先进行分组, 采用最佳后向排序算法对各组波段进行重新排序。在当前波段和参考波段中选取具有相同空间位置的邻域结构, 在最小二乘准则下, 利用邻域像素对当前预测像素进行最优谱间预测。参考波段和预测残差数据进行JPEG-LS压缩。对OMIS-Ⅰ型高光谱图像进行实验的结果表明, 与基于多波段预测算法相比, 该算法可进一步降低压缩后的平均比特率。

关键词：高光谱图像,无损压缩,波段分组,波段排序

参考文献

[1]浦瑞良, 宫鹏.高光谱遥感及其应用[M].北京:高等教育出版社, 2000.

[2]苏令华, 吕韶昱, 万建伟.基于多预测器的高光谱图像无损压缩[J].国防科技大学学报, 2007, 29 (1) :44-48.

[3]MIELIKAINEN J.Lossless compression of hyperspectralimages using lookup tables[J].IEEE Signal ProcessingLetter, 2006, 13 (3) :157-160.

[4]孙蕾, 谷德峰, 罗建书.最佳递归双向预测的高光谱图像无损压缩[J].光学精密工程, 2009, 17 (11) :2864-2870.

[5]DU Q, FOWLER J E.Hyperspectral image compressionusing JPEG2000 and principle component analysis[J].IEEE Geoscience and Remote Sensing Letters, 2007, 4 (2) :201-205.

[6]粘永健, 辛勤, 孙蕾, 等.基于3D SPIHT的高光谱图像压缩技术[J].光学精密工程, 2008, 16 (6) :1146-1151.

[7]付文秀, 王世刚, 高燕梅, 等.结合矢量量化的SPIHT算法用于多光谱图像压缩[J].通信学报, 2004, 25 (6) :110-114.

[8]孙蕾, 罗建书, 谷德峰.基于谱间预测和码流预分配的高光谱图像压缩算法[J].光学精密工程, 2008, 16 (6) :1146-1151.

[9]MIELIKAINEN J, TOIVANEN P.Clustered DPCM forthe lossless compression of hyperspectral images[J].IEEETransactions on Geoscience and Remote Sensing, 2003, 41 (12) :2943-2946.

[10]ZHANG J, LIU G Z.An efficient reordering prediction-based lossless compression algorithm for hyperspectral im-ages[J].IEEE Geoscience and Remote Sensing Letters, 2007, 4 (2) :283-287.

无损数据压缩 篇7

关键词：LZW,FPGA,并行处理,高速无损压缩

当今社会,信息技术发展飞快,快速、高效的存储与传输信息变得尤为重要,从而使得数据压缩技术在工程上具有了很大的需求背景。数据压缩分为无损压缩和有损压缩,无损压缩指的是压缩还原后的数据与压缩前的数据完全相同,而有损压缩压缩还原后的数据与压缩前的数据相比存在一定的偏差。无损压缩主要应用于对数据要求很高,不允许数据失真的场合,如文本数据、程序和特殊应用场合的图像数据(指纹图像、医学图像等)的压缩。有损压缩广泛应用于语音、图像和视频数据的压缩[1,2,3]。本文主要研究了一种基于LZW算法的无损压缩FPGA实现方法[4,5],利用该方法设计的数据压缩系统压缩速度高达66.67～246.15 Mbit/s。

1 高速无损压缩方法的过程描述

LZW无损压缩算法的实现通常采用计算机软件的方法[6],而软件方法一般存在着压缩速度慢、占用资源多等缺点,而采用硬件实现的LZW无损压缩可以很好地克服这些缺点,并能够实现对数据流的实时、高效及自适应压缩。本文主要研究了一种无损压缩的FPGA实现方法,该方法基于LZW算法的改进算法。改进后的LZW算法使用分级字典体系[7],以充分利用FPGA的并行处理[8]能力来实现高速无损压缩。这种分级字典体系由字宽度不同的多个并行字典组成,不同字典间的字宽度连续递增,每个字典的地址空间为分级字典体系地址空间中的一段。修改后的算法实现过程描述如下:

假设分级字典体系中字典个数为n,字典DICT0字宽度为1个字符,字典DICT(n-1)字宽度为n个字符,其中n=2,3,…;数据缓存区长度为n个字符;字典DICT0的地址空间为0 ～ ADDR0,ADDR0=256;字典DICT1的地址空间为ADDR0～ ADDR1;字典DICT(n-1)的地址空间为ADDR(n-2)～ ADDR(n-1);则分级字典体系的地址空间为0～ADDR(n-1)。

1.1 压缩过程描述

压缩过程步骤:

1) 字典(字符串表)初始化,i=0。

2) 如果有数据流输入,从输入数据流中读取1个字符填写到数据缓存区C(i)中,i加1;如已没有数据流输入,缓存区中字符数为j(j<n),执行步骤4)中的(2)。

3) 如果缓存区中字符数为n,执行步骤4)中的(1);如果缓存区中字符数小于n,执行步骤2)。

4) (1)将数据缓存区中n个字符所组成字符串{C0 C1 C2…C(n-1)}、{C0 C1 C2…C(n-2)}…{C0 C1}同时与字典DICT(n-1)、DICT(n-2)…DICT1中已经存储的字符串进行比较即查字典。

①如果在字典DICT(n-1)中查找到对应的字符串,则将该字符串对应的匹配地址(索引号)DICT_MATCHAED_ADDR(n-1)输出到压缩数据流中。数据缓存区清空,i=0,执行步骤2)。

②如果在字典DICT(n-1)…DICT(n-m)(m=1,2,3,…,n-1)中没有查找到对应的字符串,而在字典DICT(n-m-1)中查找到对应的字符串,则将该字符串对应的匹配地址DICT_MATCHAED_ADDR(n-m-1)输出到编码数据流中。同时将字符串{C0…C(n-m)}写入到字典DICT(n-m)的写入地址DICT_ADDR(n-m)处,字典DICT(n-m)写入地址DICT_ADDR(n-m)加1。数据缓存区中C0=C(n-m)、C1=C(n-m+1)…C(m-2)=C(n-2)、C(m-1)=C(n-1),i=m,执行步骤2)。

(2) 如果j=0,压缩结束;如果j≠0(j<n),将数据缓存区中j个字符所组成字符串{C0 C1 C2…C(j-1)}、{C0 C1 C2…C(j-2)}…{C0 C1}同时与字典DICT(j-1)、DICT(j-2)…DICT1中已经存储的字符串进行比较即查字典。

①如果在字典DICT(j-1)中查找到对应的字符串,则将该字符串对应的匹配地址DICT_MATCHAED_ADDR(n-1)输出到编码数据流中,j=0,压缩结束。

②如果在字典DICT(j-1)…DICT(j-m)(m=1,2,3,…,j-1)中没有查找到对应的字符串,而在字典DICT(j-m-1)中查找到字符串,则将该字符串对应的匹配地址DICT_MATCHAED_ADDR(j-m-1)输出到编码数据流中。同时将字符串{C0…C(j-m)}写入到字典DICT(j-m)的写入地址DICT_ADDR(j-m)处,字典DICT(j-m)写入地址DICT_ADDR(j-m)加1。数据缓存区中C0=C(j-m)、C1=C(j-m+1)…C(m-2)=C(j-2)、C(m-1)=C(j-1),j=m。

③如果j>1,执行步骤4)中(2);如果j=1,将字符C0对应于DICT0的匹配地址输出到编码数据流中,压缩结束。

1.2 解压缩过程描述

解压缩过程步骤:

1) 字典初始化。

2) 从编码数据中读取一个编码值到OLD_CODE。

3) 将字典DICT(n-1)或字典DICT(n-2)…DICT0中对应于地址OLD_CODE处所存储的字符或者字符串{OLDC0…OLDC(i-1)}(i=1,2,3,…,n)输出。

4) 如果还有编码数据输入,读入一编码值到NEW_CODE;如果已没有编码数据输入,解压结束。

5) (1)如果NEW_CODE的值小于字典写入地址DICT_ADDR0的值,得DICT0中对应于字典地址NEW_CODE的字符C0。

如果NEW_CODE的值大于字典地址ADDR(j-1)的值,且小于字典写入地址DICT_ADDR(j)的值,其中0<j<n,得DICT(j)中对应于字典地址NEW_CODE的字符串{C0…C(j)}。

将字符串{OLDC0…OLDC(i-1)}和字符C0或字符串{C0…C(j)}中第1个字符C0组成新字符串{OLDC0…OLDC(i-1) C0}。如果i<n,将字符串{OLDC0…OLDC(i-1) C0}添加到字典DICT(i)写入地址DICT_ADDR(i)处,字典DICT(i)写入地址DICT_ADDR(i)加1;如果i=n,不处理。

(2) 如果NEW_CODE不满足步骤5)(1)中的条件,将字符或字符串{OLDC0…OLDC(i-1)}加上该字符串中第1个字符OLDC0组成新字符串{OLDC0…OLDC(i-1) OLDC0}(i<n),将字符串{OLDC0…OLDC(i-1) OLDC0}添加到字典DICT(i)写入地址DICT_ADDR(i)处,字典DICT(i)写入地址DICT_ADDR(i)加1,这样字典地址NEW_CODE对应的字符串为{OLDC0…OLDC(i-1) OLDC0}。

6)将NEW_CODE的值赋给OLD_CODE,执行步骤3)。

1.3 压缩及解压缩实例

以上对算法进行了详细描述,为了更好地表达算法的实现过程,以下给出了一个压缩及解压缩实例。在该实例中,输入为字符数据流“/WED/WE/WEE/WEB/WE”,分级字典体系中字典个数为4,字典DICT0,DICT1,DICT2,DICT3的字宽度分别为1,2,3,4个字符,字典地址分别为0～255,256～511,512～767,768～1023。表1给出了压缩实现的过程,表2给出了压缩过程中所使用的分级字典体系结构。

解压缩过程中使用的分级字典体系与压缩时完全相同。表3给出了解压缩的实现过程,字典重构如表2所示。

2 硬件实现的体系结构

采用上文所描述的算法,笔者设计了基于FPGA的高速无损压缩系统,原理如图1所示。

该系统主要由算法控制模块、分级字典、数据输入FiFo及数据缓存区等组成,系统时钟为50 MHz。其中算法控制器为整个系统的核心部分,协调控制系统其余各个模块共同完成算法的计算流程。分级字典是系统的关键组成部分,用于存储无损压缩过程中产生的中间数据。数据缓存区完成对输入字符数据流8字符缓存,从而实现并行查找字典的功能。FiFo模块用于协调输入数据流与无损压缩之间的速度差。系统中字典更新采用先进先出策略,即一个字典填写满后将从该字典低地址处开始覆盖写人,而不清除字典高地址处已写入内容;分级字典由8个字典组成,其中字典0字宽为1个字符,由256个字符组成,占用地址空间为0～256,不需要在硬件中实际构建,其余7个字典字宽分别为2,3,4,5,6,7,8个字符,占用的地址空间长度分别为256,128,128,64,64,64,64,在硬件系统中需要实际构建。

图2为作者在FPGA上设计的高速无损压缩系统在测试时获取的一张SignalTap波形图,其中clk为系统时钟输入管脚,reset为系统复位输入管脚,wrreq,wrclk,data[7..0]分别为数据流输入请求信号、输入数据同步时钟、输入数据流管脚,dataend为压缩结束信号输入管脚;wrfull为FiFo满信号输出管脚,encodedata[0..9],codeclk分别为编码数据流输出、编码数据流同步时钟管脚。

对系统的实际测试表明,当系统时钟为50 MHz时,压缩速度可达$\frac{50\text{Μ}\text{Η}\text{z}}{5+1}\times 8\text{b}\text{i}\text{t}=$66.67 Mbit/s到$\frac{50\text{Μ}\text{Η}\text{z}}{5+8}\times 8\text{b}\text{i}\text{t}\times 8=$246.15 Mbit/s,平均压缩比约为55%。

3 结语

本文首先阐明了硬件实现基于LZW算法的高速无损压缩基本原理,分别对压缩过程与解压缩过程进行了详细描述,并给出了压缩与解压缩实例。根据这些基本原理在FPGA上设计了高速无损压缩系统并进行了实际测试。测试结果表明,系统压缩速度快,压缩比高,达到了预期设计目标。

利用该高速无损压缩FPGA实现方法所设计的无损压缩系统,可极大地提高数据压缩速度,减少数据的存储空间。同时,在数据传输领域,该系统能够将高速信号转换为缓变信号进行传输,从而降低通信的信道占用费用,提高数据传输的可靠性。

参考文献

[1]李锦明,张文栋,毛海央,等.实时无损数据压缩算法硬件实现的研究[J].哈尔滨工业大学学报,2006,38(2):315-317.

[2]王伟,刘文怡,秦丽,等.遥测数据实时压缩技术的设计与实现[J].仪器仪表学报,2006,27(6):2467-2469.

[3]王文延,赵中华,朱磊.一种JPEG无损压缩专利算法的改进与实现[J].电视技术,2010,34(5):26-29.

[4]AKIL M,PERROTON L,GRANDPIERRE T.FPGA-based architecturefor hardware compression/decompression of wide format images[J].Jour-nal of Real-Time Image Processing,2006,1(2):163-170.

[5]古海云,李丽,许居衍,等.一种Virtex系列FPGA配置数据无损压缩算法[J].计算机研究与发展,2006,43(5):940-945.

[6]AGNEW G B,SIVANANDAN A.A fast method for determining the ori-gins of documents based on LZW compression[J].International Journalon Digital Libraries,2000,3(4):297-301.

[7]LIN M B.A hardware architecture for the lzw compression and decom-pression algorithms based on parallel dictionaries[J].The Journal of VL-SI Signal Processing,2000,26(3):369-381.