基于静止图像编码的数据压缩算法的研究与实现Word文档下载推荐.doc

基于静止图像编码的数据压缩算法的研究与实现Word文档下载推荐.doc

《基于静止图像编码的数据压缩算法的研究与实现Word文档下载推荐.doc》由会员分享，可在线阅读，更多相关《基于静止图像编码的数据压缩算法的研究与实现Word文档下载推荐.doc（25页珍藏版）》请在冰点文库上搜索。

1.1.4其它编码方法3

1.2小波分析在图像压缩编码研究中的应用4

1.2.1小波的构造5

1.2.2量化和编码6

1.3论文介绍7

第二章静止图像的编码分析9

2.1分级量化的思想9

2.2分层树集合分割算法（SPIHT）10

2.3嵌入式块集合分裂编码器（SPECK）12

2.4现有方法的不足14

第三章图像编码算法及其实现15

3.1小波的构造15

3.1.1提升方法15

3.1.2整数小波16

3.2截断量化的编码方法17

3.3图像的编码算法19

3.3.1算法119

3.3.2算法221

3.4算术编码22

第四章压缩软件的设计及测试24

4.1系统结构24

4.2软件的设计和实现25

4.2.1编码器结构25

4.1.2数据分析部分26

4.2.3文件格式26

4.3软件使用简介27

4.3.1界面设计27

4.3.2小波变换的步骤28

4.3.3小波系数编码的步骤28

4.3.4图像压缩的步骤29

4.4测试分析及结论30

4.4.1压缩效果评价30

4.4.2实验数据31

4.4.3数据分析32

第五章结束语35

5.1研究和开发工作的总结35

5.2将来进一步的工作和计划35

参考文献36

致谢37

附录38

摘要

ABSTRACT

Althoughthetechniquesofdatastoragearedevelopingthedemandforcompressionforimagedataisrapidlygrowingsothattosavethespaceofstorageandimprovetheuseratioofchannel.Comparingwithlossyimagecompression,thelosslessimagecompressionismoredifficultanditsdevelopmentisslower.Now,imagecompressionmethodbasedonwaveletisthebranchwhichdevelopmentisfastinimagecompressingfield.Liftingschemecandesignthewavelettransformsthatmapintegertointeger,whichprovidestheeffectivetoolforstudyingthelosslessimagecompression.Ontheotherhand,themethodforwaveletcoefficientscodingisakeytechniquetoimplementimagecompression,whichnotonlyaffectstheeffectofcompression,butalsothequalitiesofresumingimageandthetimeofcodinganddecoding.

Thisthesispresentsaninvestigationintoliftingscheme,Then,the9/7-Fand9/7-M

waveletswhichusegenerallyinimagecompression,areselectedforfactoringthem

intoliftingstepssoastostudythecoefficientscoding.

Themethodbasedonscalarquantizedsignificanttestingschemesisanimportant

classofcodingforwaveletcoefficients,whichisstudiedinthisthesissoastofindthewaytoimprovetheperformanceoflosslessimagecompression.Theseworksarethekeyofthisthesis.Aninvestigationoftwoclassicalalgorithms,SPIHT（SetPartitioningInHierarchicalTrees）andSPECK（SetPartitionEmbeddedblockcoder）ispresented.Then,thisthesispresentsanalgorithmbasedonthemethodforlosslessimagecompression,whichusesnewstrategyofsetpartitioningandothernewmethods,whichimprovetheperformanceoflosslessimagecompressionandnotaffectthelossycompression.ThenewalgorithmcomparingwithSPIHTandSPECKhasbetterperformancesinlosslesscompression,lossycompressionandtimeofcodinganddecoding.

Inaddition,thisthesispresentsaninvestigationintoarithmeticcoding,especially

itsimplementation.Thisisforfindingtheotherwaytoimprovetheperformancesof

thenewalgorithm.Thisthoughtisprovedbythepractice.

Keywords:

Imagecompressing,Coding,Wavelet,Liftingscheme,Arithmeticcodin

第一章绪论

1.1图像压缩编码研究的现状和发展

图像数据只是众多类型的数据中的一种，因此图像压缩编码也是数据压缩的一个部分，只是图像具有与语音、文字等其他数据不同的特点，所以需要分别加以研究。

图像压缩编码的目的就是为了减少原始数据的数据量，即以尽量少的比特数表示原来的图像，同时又要能保持复原图像的质量，满足规定的要求。

压缩编码节省了数据的存储空间，这样不论是在传输数据还是在处理数据的时候都会给我们带来很大的便利。

我们从信息源得到的数据是含有冗余的，如果可以去掉这些冗余，就可以使数据量减少；

而且数据之间也存在一定的相关性，如果能够去除这些相关性，再对数据进行适当的编码，也能减少原始数据的数据量；

如果可以在一定的程度上容忍损失一些关系不大的数据，同样也能起到减少数据量的目的。

信息论为数据压缩提供了理论基础[1]，信息论认为信源中含有或多或少的自然冗余度，这些冗余度既来自于信源本身的相关性中，又来自于信源概率分布的不均匀性中。

只要找到去除相关性或改变概率分布不均匀性的方法和手段，就可以实现有效的数据压缩。

图像压缩就是指的图像压缩编码，也可以简称图像编码，在本论文的后面部分中，就不再对这几个概念进行区分，它们的含义都是相同的。

图像编码属于信源编码的范畴，真正从科学的意义上对图像编码进行研究的历史相对于很多学科来说并不长，只有不到六十年的时间。

对它的分类根据研究问题的出发点不同，可以有不同的分类方法。

从压缩的角度分类，可以分为无损压缩编码和有损压缩编码，有损压缩也可以称为统计压缩；

从现有的实用编码方法来看，可以划分为三大类经典的编码方法：

统计编码、预测编码和变换编码。

从技术发展的角度，Kunt提出过第一代、第二代图像编码的概念[2]，他把1948年－1988年40年中研究的以去除冗余度为基础的编码方法称为第一代编码，如PCM、DPCM、亚取样编码法，变换域的DFT、DCT、沃尔什－哈达玛变换编码等，以及以此为基础的混合编码法均属于经典的第一代编码法。

第二代编码方法多是80年代以后提出的新的编码方法，如金字塔编码、分形编码、基于神经网络的编码、小波变换编码、模型基编码、分形压缩等。

下面就从基本的三类编码方法出发，全面介绍图像编码的各类方法。

1.1.1统计编码

统计编码是建立在图像的统计特性基础之上的压缩编码方法，根据像素灰度值出现概率的分布特性而进行的压缩编码。

常见的统计编码是变长编码，主要有霍夫曼码、香农-费罗码、算术编码等。

统计编码是一种高效的编码法，其主要的缺点是：

（1）码字不是等长的，不便于数据存储单元收集代码；

（2）前面提到的几种码都缺乏构造性，不能用数学方法建立一一对应关系；

（3）需要在编码过程中知道每种消息出现的概率，但这实际上难以做到。

1.1.2预测编码

预测编码是建立在现代统计学和控制论基础上的，其基本思路是，在图像编码过程中，可以利用图像像素间的相关性，根据某一像素的值来预测相关下一点的取值，然后将像素点的实际值和预测值相减得到一个误差值，对该误差值进行编码。

预测编码主要有两大类，即DM（DetaModulation）和DPCM（DifferentialPulseCodeModulation），DPCM实际上是DM和PCM（PulseCodingModulation）两种技术相结合的编码方法。

1.1.3变换编码

1.1变换编码模型

变换编码的基本模型如图1-1所示，可以看出变换编码主要由：

映射变换、量化及编码器组成。

映射变换据是把图像中的各个像素从一种空间变换到另一种空间，然后针对变换后的信号再进行量化与编码操作。

解码时，先对接收信号进行译码，再进行反变换恢复原始图像。

映射变换的关键是在于能够产生一系列更加有效的系数，对这些系数编码所需的总比特数比对原始图像进行编码所需的总比特数少，从而达到数据压缩的目的。

映射变换的方法很多，基本可以分为两类：

一类是特殊的映射变换编码法，如一维行程编码、等值线编码等；

另一类是函数变换编码法，传统的正交变换编码有傅里叶变换、DCT变换、沃尔什－哈达玛变换等，近年来利用小波变换的编码方法也得到快速的发展，成为当今图像编码领域的研究前沿和热点之一,后面的论述中对小波变换编码方法作了更多的和更详细的介绍，这是本文主要讨论的编码方法。

严格的说，预测编码也是一种变换编码的方法，但它又具有自身的特殊性，所以在这里就分开来叙述。

我们也可以看出，变换编码也是一种混合编码的方法，因为映射变换本身一般是不会压缩数据的，比如正交函数[3]变换只是把图像从空间（时间）域变换到能量比较集中且不相关的变换域，这样对变换系数编码就可以使存在于相关性中的冗余度得以去除，而且可以选择变换系数中能量集中的部分编码，也就到达了对数据进行压缩的目的。

所以，变换后的系数仍然必须经过量化和编码才能达到数据压缩的目的。

1991年，国际电报咨询委员会（CCITT）和国际标准化组织（ISO）联合组成的专家组，共同制定了静止图像的数码率压缩标准（1994年正式通过），即JPEG（TheJointPhotographicExpertGroup），它就是采用了DCT变换，而最近才提出的新的国际标准JPEG2000则已经采用了小波变换。

1.1.4其它编码方法

（1）分形图像压缩编码

近十年来，分形（Fractal）在图像压缩中的应用也是图像数据压缩领域中的一个热点之一。

基于分形的图像压缩方法与经典的图像数据压缩方法相比，在思维方式上有很大的突破，其压缩比在理论上可超过经典压缩方法的几个数量级，分形图像压缩的发明人之一Barnsley在1988年发表的论文[4]中宣称分形图像压缩可达到1000：

1的压缩比。

分形图像压缩极高的压缩比、快速的解压缩速度颇引人关注。

但其编码速度过于耗费时间，仍是制约其应用的主要难点。

因此，尽管分形图像压缩有巨大的潜力，但要把这种潜力释放出来，还有许多问题有待进一步的研究。

目前的分形图像压缩还处在理论探讨阶段，离实际应用还有不小的距离。

（2）基于模型的图像编码

基于模型或知识的编码方法，是在编码端通过各种分析手段，提取所建模型的特征与状态参数。

在解码端依据这些参数，通过模型及相关知识生成所建模的信源。

这类方法是把计算机视觉和计算机图形学中的方法应用到图像编码中。

（3）利用神经网络的图像编码

神经网络法是模仿人脑处理问题的方法，通过各种人工神经元网络模型对数据进行非线性压缩。

人工神经网络是一个非线性动态网络，工作过程一般分训练和工作两个阶段。

训练阶段就是使用一些训练图像和训练算法，调整网络的权重，使重建图像的误差最小。

目前直接用于图像压缩编码的神经网络主要有反向误差传播（BP）型和自组织映射（Kohonen）型。

这几种编码的方法都试图充分利用计算机图形学、计算机视觉、人工智能与模式识别等相关学科的研究成果，为图像编码开拓出广阔的前景。

但是由于这些编码方法增加了分析的难度，所以大大增加了实现的复杂性。

从当前发展情况来看，分形编码等方法仍处于待深入研究的阶段，目前还存在一些明显的不足：

分形法由于图像分割、迭代函数系统代码的获得非常困难，因而实现起来时间长，算法异常的复杂，因而难以实现和应用；

模型法则仅限于人头肩像等基本的图像上，进一步的发展有赖于新的数学方法和其它相关学科的发展；

神经网络的工作机理至今仍不清楚，硬件研制不成功，所以在图像编码中的应用研究进展缓慢，目前多与其他方法结合使用。

在前面介绍的各种图像编码方法中，统计编码属于有损编码，而预测编码和变换编码可以实现无损编码，也可以实现有损编码。

分形图像压缩和基于模型的图像编码也是有损的。

对于图像的有损压缩，目前以可以取得比较令人满意的效果；

对图像进行无损压缩的研究虽一直没有停顿过，但图像的无损压缩效果却一直还不理想。

而无损图像压缩在医学、军事、遥测等众多领域仍然有广泛的需求。

综上所述，在目前的图像编码研究领域中，虽然存在不少的热点，但基于小波变换的编码方法却具有特别重要的意义。

因此，本文接下来将介绍小波在图像编码中的研究情况。

1.2小波分析在图像压缩编码研究中的应用

小波变换是一种变分辨率的分析方法。

它对高频信号采用小时窗，对低频信号采用大时窗进行分析。

这正好与自然界中高频信号一般持续时间短，而低频信号持续时间较长的时频分布特性相吻合，非常适合于图像处理。

在进一步介绍小波分析之前，我们先简要的回顾一下小波分析方法的历史。

小波分析的思想最早可以追述到上个世纪的最初十年，1910年，Haar提出了小波规范正交基，即最早的小波基，但当时还没有出现”小波”这一术语。

1985年，法国大数学家Meyer首先提出光滑的小波正交基，即后来的Meyer基；

1986年，Meyer及其学生Lemarie提出了多尺度分析的思想，为小波理论做出了重大的贡献。

1988年，女数学家Daubechies提出了具有紧支集光滑正交小波基，即Daubechies基。

之后，信号分析专家Mallat提出了多分辨率分析的概念，给出了构造正交小波基的一般性方法，并以多分辨率分析为基础给出了著名的快速小波算法–Mallat[5]算法（FWT）.90年代，Sweldens等人提出了用提升方案来构造小波的方法，这种以新的方法构造的小波可以称为第二代小波，以便同以前的小波相区别。

第二代小波构造方法的继承了第一代小波变换的多分辨率特性，同时不依赖于傅立叶变换，因此利于构造非线形的小波，在图像处理等领域有广阔的应用前景。

而对于图像压缩编码而言，小波变换得以广泛应用的重要原因在于一方面它拥有传统变换压缩方法的优点，能够很好地去除图像数据中的统计冗余；

另一方面，小波变换的多分辨率特性，使变换后的图像数据能够保持原始图像在各种分辨率下的精细结构，为进一步去除图像中的结构冗余信息提供了便利。

一般来说，对于图像压缩，小波的正则性比频率选择性重要。

实际上，早在1986年，Woods等人就构造了第一个真正意义上小波图像编码器[6]，但那时在图像领域人们却把小波编码称为子带编码。

因为在当时人们还没有完全搞清楚子带编码的工作机理，更不清楚它与数学领域的小波基有着千丝万缕的联系，直到多分辨分析理论提出，信号处理领域的专家们才从理论上统一了众多子带编码器的工作原理。

子带分解其实质上是小波分解，基于子带的图像编码实质上是基于小波的图像非线性逼近，因此后来的”子带编码”和”小波编码”两个词就不再加以区别。

伴随着数学领域的小波理论的发展和非线性逼近论研究的深入，小波图像压缩取得了极大的进展。

一个极具表现力的实证是Daubechies所发现的小波双正交基立即被转化为图像分解所使用的具有线性相位多通道完全重建滤波组。

自从小波理论引入图像处理领域，图像处理工程师们就开始逐渐从非线性逼近论和泛函分析的角度出发，分析、设计和改进图像压缩应用算法。

目前，对于小波变换图像压缩的研究主要集中在两个方面：

一是小波基的选择，一是小波系数的编码。

因为小波变换本身并不能压缩图像，只是提供了减少比特率的一种可能，必须结合其它编码技术对小波系数编码才能实现压缩目的。

所以，基于小波变换的图像压缩方法[7]通常分为如下3个步骤:

小波变换、量化和编码。

此类方法首先对图像进行多级小波分解，然后对每层的小波系数进行量化，如零树编码进行量化，矢量量化等，再对量化后的系数进行编码，如算术编码、哈夫曼编码等无失真编码。

对于基于小波变换的图像压缩编码方法，对小波变换后系数的量化和编码是实现数据压缩的关键，也是本文的研究重点。

1.2.1小波的构造

前面简述了小波变换分析方法的发展，在图像压缩编码研究中，可以按照构造小波的方式不同，把图像压缩中用到的小波分为第一代小波和第二代小波。

第一代小波是在基小波的基础上通过平移和膨胀得到不同分辨率下的小波基函数，并且第一代小波变换后的系数是浮点数，由于受到计算机数据存储和传输方式的限制，往往不能精确恢复信号，同时浮点数在压缩编码时，一般需要进行取整量化，因此无法达到无损压缩的目的，只能适用于有损压缩。

第二代小波[8]有提升小波、内插小波、区间小波、Ｍ带小波和非线性小波等，这些小波在改善图像压缩品质和提高执行速度方面都产生了积极效果。

第二代小波构造方法的特点是：

（1）继承了第一代小波变换的多分辨率特性；

（2）不依赖傅立叶变换；

（3）利于构造非线性小波，如整数小波；

（4）图象的恢复质量与变换时边界采用何种延拓方式无关。

在这些方法中，提升方法又是一种更有效的、优秀的构造第二代小波的方法。

”提升”算法的基本思想是将现有的小波滤波器分解成基本的构造模块，分步骤完成小波变换。

因此,可以将小波变换[9]分解成3个过程:

分裂,预测和修正Sweldens已经证明在提升的基础上可以进行整数集到整数集的小波变换,即一个整数集合通过小波变换得到的仍然是整数集合。

这就给数字图象的压缩编码带来了好处，由于不需要对变换后的系数进行量化，因此提供了实现无损压缩的可能。

1.2.2量化和编码

前面已经提到，原始图像经过小波变换后，还需要经过量化和编码才能真正

实现图像压缩的目的。

目前，主要的量化和编码方式[10]有：

统计编码、嵌入式零树

编码算法（EZW，theEmbeddedZerotreeWaveletalgorithm）、可逆嵌入小波压缩（CREW，CompressionwithReversibleEmbeddedWavelets）、分层树集合分割算法（SPIHT，SetPartitioningInHierarchiacalTrees）、优化截断的嵌入式块编码（EBCOT，EmbeddedBlockCodingwithOptimizedTruncation）、嵌入式块集合分割算法（SPECK，theSetPartitionEmbeddedbloCKcoder）、小波数据的形态学表示（MRWD，MorphologicalRepresentationofWaveletData）、连接重要性连通分支分析（SLCCA，Significance-LinkedConnectedComponentAnalysis）等。

当小波变换最初用于图像压缩中时，对小波系数的编码是直接使用的统计编码方法，如霍夫曼编码、算术编码等，其效果并不理想。

直到1993年，Shapiro提出了EZW算法，对小波系数编码的研究作出了重大的突破。

Shapiro根据小波系数的统计分布规律，提出了一个假设：

如果空间树的粗尺度的小波系数对Ｔ门限是不重要的，则在这棵小波树的细尺度的小波系数也极可能是不重要的。

基于此Shapiro引入一个小波”零树”，通过定义POS、NEG、IZ和ZTR四种符号进行空间小波树递归编码，有效地剔除了对高频系数的编码，极大地提高了小波系数的编码效率。

这个算法采用的是渐进式量化和嵌入式编码模式，算法复杂度低。

因为EZW算法的出现打破了信息处理领域长期笃信的准则：

高效的压缩编码器必须通过高复杂度的算法才能获