（信号与信息处理专业论文）基于整数小波的图像压缩编码方法.pdf

中文摭要 摘要 尽管数据存储技术不断发展、信道传输带宽不断加宽，但人 f 3 对于压缩图像 数据以节省数据存储空间和提高信道利用率的需求仍在增长。图像的无损压缩相 对有损压缩来说更加困难，取得的进展也更小。目前，基于小波的图像压缩方法 是图像压缩领域发展较快的一个分支，提升方法能够方便的构造从整数到整数的 小波，为图像的无损压缩研究提供了有力的工具。而对小波系数编码的方法是实 现图像压缩的关键技术，不仅关系到图像的最终压缩效果、也关系到图像的恢复 质量和编解码的时间消耗。 本文对小波的研究主要集中在提升方法上，该方法属于第二代构造小波的新 方法，具有既继承了第一代小波的特性，又不依赖于傅里叶变换，同时便于构造 非线性小波( 如：整数小波) 的特点。本文对提升方法的原理和其中的关键技术 作了详细的阐述和讨论，特鄹是对用提升方法实现从整数到整数的小波f 乍了全面、 细致的分析。并选择了9 7 一f 、9 7 。m 和5 3 三种传统用于图像压缩的小波来用提 升方法实现从整数到整数的小波，为后面进一步研究系数编码做好准备。 基于分级量化的重要性测试编码是小波系数编码方法中重要的一类方法。这 类方法具有复杂度低、性能好等诸多优点，嵌入式零树编码算法( e z w ，t h e e m b e d d e dz e r o t r e ew a v e l e t a l g o r i t h m ) 、可逆嵌入小波压缩( c r e w ，c o m p r e s s i o n w i t h r e v e r s i b l e e m b e d d e d w a v e l e t s ) 、分层树集合分割算法( s p i h t ，s e t p a r t i t i o n i n g h l 商e r a x c h i a c a lt r e e s ) 、嵌入式块集合分割算法( s p e c k ，t h es e tp a r t i t i o ne m b e d d e d b l o c kc o d e r ) 等经典的基于小波的图像压缩编码算法都属于这一类型的方法。本 文对该类方法进行了全面和深入的研究，探讨了基于该方法的图像无损压缩编码 算法，以改善图像无损压缩的性能，这是本文研究的重点。对s p i h t 和s p e c k 这 两种先进的、有代表性的算法本文作了详细和全面的分析与讨论。在此基础上， 本文提出了自己的基于分级量化的重要性测试编码的算法，该算法除了在集合分 类策略和搜索策略上采用了新的方法外，还采用了截断量化和对特殊b i t 组合进行 编码等方法来改善图像无损压缩的性能，同时又不影响有损压缩的性能。本文算 法在无损压缩性能、执行速度和有损压缩性能上同s p i h f 、s p e c k 算法散了比较， 都优于这两种算法。 另外，本文对算术编码，特别是它的实现作了研究，主要是为了探讨将该方 法与本文的算法相结合，进一步提高图像压缩性能的可能性。从实际情况来看， 重庆大学硕士学位论文 这一想法是可行的。 关键词：图像压缩，编码，小波，提升方法，s p i h t ，s p e c k 。算术编码 英文摘要 _h_，_-_-_-_-_-_-_一一 a b s t r a c t a l t h o u g ht h et e c h n i q u e so f d a t as t o r a g ea r ed e v e l o p i n ga n dt h eb a n do fc h a n n e li s w i d e rt h a np a s t ，t h ed e m a n df o rc o m p r e s s i o nf o ri m a g e d a t ai sr a p i d l yg r o w i n gs ot h a t t os a v et h es p a c eo f s t o r a g ea n di m p r o v et h eu s er a t i oo f c h a n n e l c o m p a r i n g w i t h l o s s y i m a g ec o m p r e s s i o n ，t h e l o s s l e s s i m a g ec o m p r e s s i o n i sm o r ed i f f i c u l t a n di t s d e v e l o p m e n t i ss l o w e r n o w , i m a g ec o m p r e s s i o nm e t h o db a s e do nw a v e l e t i st h eb r a n c h w h i c h d e v e l o p m e n t i sf a s ti ni n l a , g ec o m p r e s s i n gf i e l d l i f t i n gs c h e m ec a l ld e s i g nt h e w a v e l e tt r a n s f o r m st h a tm a pi n t e g e rt oi n t e g e r , w h i c hp r o v i d e st h ee f f e c t i v et o o l f o r s t u d y i n gt h el o s s l e s si m a g ec o m p r e s s i o n o n t h eo t h e rh a n d ，t h em e t h o df o rw a v e l e t c o e f f i c i e n t sc o d i n gi sak e yt e c h n i q u et oi m p l e m e n ti m a g ec o m p r e s s i o n ，w h i c hn o to n l y a f f e c t st h ee f f e c to fc o m p r e s s i o n ，b u ta l s ot h eq u a l i t i e so fr e s u m i n gi m a g ea n d t h et i m e o f c o d i n g a n dd e c o d i n g t h i st h e s i sp r e s e n t sa ni n v e s t i g a t i o ni n t ol i f t i n gs c h e m e ，w h i c hi sn e wm e t h o do f t h es e c o n dg e n e r a t i o nw a v e l e t i tn o to n l yi n h e r i t st h ec h a r a c t e r i s t i c o ft h ef i r s t g e n e r a t i o nw a v e l e t , b u ti si n d e p e n d e n to f f o u r i e rt r a n s f o r ma n dp a r t i c u l a r l ye a s yt o b u i l do nn o nl i n e a rw a v e l e tt r a n s f o r m s s u c ha si n t e g e rw a v e l e tt r a n s f o r m s t h i st h e s i s i n t r o d u c e st h et h e o r yo f l i f t i n ga n di t sk e yt e c h n i q u e s ，e s p e c i a l l y , a n a l y z i n gt h ew h o l e p r o c e s sf o rf a c t o r i n g t h ew a v e l e tt r a n s f o r mi n t ol i f t i n gs t e p st h e n ，t h e9 7 - f ，9 7 - ma n d 5 3w a v e l e t sw h i c hu s eg e n e r a l l yi ni m a g ec o m p r e s s i o n ，a r es e l e c t e df o rf a c t o r i n gt h e m i n t ol i f t i n gs t e p ss oa st os t u d yt h ec o e f f i c i e n t sc o d i n g t h em e t h o db a s e do ns c a l a rq u a n t i z e ds i g n i f i c a n et e s t i n gs c h e m e si sa ni m p o r t a n t c l a s so fc o d i n gf o rw a v e l e tc o e f f i c i e n t s ，w h i c hc h a r a c t e r sa r el o wc o m p l i c a t i o n ，g o o d p e r f o r m a n c e ，a n d s o o n a l g o r i t h m s ，s u c h 鹅t h e e m b e d d e dz e r o t r e ew a v e l e t a l g o r i t h m ( e z w ) ，c o m p r e s s i o n 砸t l l r e v e r s i b l ee m b e d d e dw a v e l e t s ( c r e w ) ，s e t p a r t i t i o n i n g i nh i e r a r c h i c a l t r e e s ( s p r a t ) , t h e s e tp a r t i t i o ne m b e d d e db l o c k c o d e r ( s p e c k ) ，w h i c h a r ec l a s s i c a la l g o r i t h m sb a s e do nw a v e l e tf o ri m a g e c o m p r e s s i o n ， a r eb e l o n gt ot h i st y p em e t h o d w h i c hi ss t u d i e di nt l l i st h e s i ss oa st of i n dt h ew a yt o i m p r o v et h ep e r f o r m a n c eo f l o s s l e s si m a g ec o m p r e s s i o n t h e s ew o r k sa r et h ek e yo f t h i st h e s i s a n i n v e s t i g a t i o n o ft w oc l a s s i c a l a l g o r i t h m s ，s p i h ta n ds p e c k ，i s p r e s e n t e d t h e j a t l u st h e s i sp r e s c m s 吼a l g o r i t h mb a s e do nt h em e t h o df o rl o s s l e s s i m a g ec o m p r e s s i o n ，w h i c h u s e sn e w s t r a t e g yo f s e tp a r t i t i o n i n ga n do t h e rn e w m e t h o d s ， w h i c hi m p r o v et h ep e r f o r m a n c eo fl o s s l e s si m a g ec o m p r e s s i o na n dn o ta f f e c tt h el o s s y m 重庆大学硕士学位论文 c o m p r e s s i o n t h en e wa l g o r i t h mc o m p a r i n gw i 也s p i h ta n d s p e c kh a sb e t t e r p e r f o r m a n c e s i nl o s s l e s s c o m p r e s s i o n ，l o s s yc o m p r e s s i o na n dt i m e o fc o d i n ga n d d e c o d i n g i na d d i t i o n ，t h i st h e s i sp r e s e n t sa ni n v e s t i g a t i o ni n t oa r i t h m e t i cc o d i n g , e s p e c i a l l y i t si m p l e m e n t a t i o n t h i si sf o rf i n d i n gt h eo t h e rw a yt oi m p r o v et h ep e r f o r m a n c e so f t h e n e w a l g o r i t h m t h i st h o u g h t i sp r o v e db yt h e p r a c t i c e k e y w o r d s ：i m a g ec o m p r e s s i n g , c o d i n g ，w a v e l e t , l i f t i n gs e h e r a e ，s p i h t , s p e c k ， a r i t h m e t i cc o d i n g i v 缩略语表 缩略语表 b p p ：b i t sp e rp i x e l ，比特率码率 c c i t t ：国际电报咨询委员会 d c t ：d i s c r e t ec o s m et r a n s f o r m s ，离散余弦变换 c r e w ：c o m p r e s s i o n w i t hr e v e r s i b l ee m b e d d e d w a v e l e t s ，可逆嵌入式小波压缩编码 d p c m ：d i f f e r e n t i a lp u l s ec o d em o d u l a t i o n ，差分脉冲编码调制 e b c o t ：e m b e d d e db l o c kc o d m gw i t ho p t i m 谊e dt r u n c a t i o n ，优化截断的嵌入式块编码 e z w - t h ee m b e d d e dz c r o t r e ew a v e l e t a l g o r i t h m ，嵌入式零树小波变换 f i r ：f m i t v i n p u l s er e s p o n s e ，有限冲击响应 f w t ：f a s tw a v e l e tt r a n s f o r m ，快速小波变换 g c d ：g r e a t e s tc o m m o nd i v i s o r ，最大公约数 i s o ：国际标准化组织 j b i g ：j o i n tb i n a r yi m a g eg r o u p ( 二值图像压缩标准) j p e g ：t h ej o i f l tp h o t o g r a p h i ce x p e r tg r o u p ，联合图像专家组 l i p , l i s t o f i n s i g n i f i c a n tp i x e l s ，不重要点列表 l i s ：l i s t o f i n s i g n i f i c a n ts e t s ，不重要集合列表 l s p ：l i s t o f s i g n i f i c a n tp i x e l s ，重要点列表 l t hl m e a rt i m eh i v a r i a n t ，线性时不变系统 m r w d ：m o r p h o l o g i c a lr e p r e s e n t a t i o no f w a v e l e td a t a ，小波数据的形态学表示 m s e ：m e a n s q u a r e d - e r r o r ，均方误差 p c m ：p u l s e c o d i n gm o d u l a t i o n 脉冲编码调制 p s n r ：p o w e r s i g n a l - t o - n o i s er a t i o ，信号噪声功率比 s l c c a ：s i g n i f i c a n c e - l i n k e dc o n n e c t e dc o m p o n e n t a n a l y s i s ，连接重要性连通分支分析 s p e c k ：t h es e tp a r t i t i o ne m b e d d e db l o c k c o d e r ，嵌入式块集合分割编码器 s p i h t ：s e t p a r t i t i o n i n g i nh i e r a r e h i a c a l t r e e s ，分层树集合分割算法 文中主要符号的含义 卜j ：l 工j = 4 、于或等于工的最大整数，卜+ 1 2 j 即是对x 进行四舍五入的运算。 x l ：j 1 = 大于或等于x 的最小整数，i x l 2 1 即是对x 进行四舍五入的运算。 d e t a ：如果a 为方阵，则d e t a 表示a 的行列式。 x 1 1引言 本章主要介绍本论文的工作背景，相关领域的历史、现状和发展趋势。 1 1 图像压缩编码研究的现状和发展 图像数据只是众多类型的数据中的一种，因此图像压缩编码也是数据压缩的 一个部分，只是图像具有与语音、文字等其他数据不同的特点，所以需要分别加 以研究。 图像压缩编码的目的就是为了减少原始数据的数据量，即以尽量少的比特数 表示原来的图像，同时又要能保持复原图像的质量，满足规定的要求。压缩编码 节省了数据的存储空间，这样不论是在传输数据还是在处理数据的时候都会给我 们带来很大的便利。 我们从信息源得到的数据是含有冗余的，如果可以去掉这些冗余，就可以使 数据量减少：而且数据之间也存在一定的相关性，如果能够去除这些相关性，再 对数据进行适当的编码，也能减少原始数据的数据量：如果可以在一定的程度上 容忍损失一些关系不大的数据，同样也能起到减少数据量的目的。 信息论为数据压缩提供了理论基础，信息论认为信源中含有或多或少的自然 冗余度，这些冗余度既来自于信源本身的相关性中，又来自于信源概率分布的不 均匀性中。只要找到去除相关性或改变概率分布不均匀性的方法和手段，就可以 实现有效的数据压缩f 2 l ”j 。 图像压缩就是指的图像压缩编码，也可以简称图像编码，在本论文的后匝部 分中，就不再对这几个概念进行区分，它们的含义都是相同的。 图像编码属于信源编码的范畴，真正从科学的意义上对图像编码进行研究的 历史相对于很多学科来说并不长，只有不到六十年的时间。对它的分类根据研究 问题的出发点不同，可以有不同的分类方法。从压缩的角度分类，可以分为无损 压缩编码和有损压缩编码，有损压缩也可以稔为统计压缩；从现有的实用编码方 法来看，可以划分为三大类经典的编码方法：统计编码、预测编码和变换编码。 从技术发展的角度，k t m t 提出过第一代、第二代图像编码的概念( 2 2 j ，他把1 9 4 8 年一1 9 8 8 年4 0 年中研究的以去除冗余度为基础的编码方法称为第一代编码，如 p c m 、d p c m 、a m 、亚取样编码法，变换域的d f t 、d c t 、沃尔什一哈达玛变 换编码等，以及以此为基础的混合编码法均属于经典的第一代编码法。第二代编 码方法多是8 0 年代以后提出的新的编码方法，如金字塔编码、分形编码、基于神 经网络的编码、小波交换编码、模型基编码、分形压缩等。 重庆大学硕士学位论文 下面就从基本的三类编码方法出发，全面介绍图像编码的各类方法。 1 1 1 统计编码 统计编码是建立在图像的统计特性基础之上的压缩编码方法，根据像素灰度 值出现概率的分布特性而进行的压缩编码。 常见的统计编码是变长编码，主要有霍夫曼码、香农费罗码、算术编码等。 统计编码是一种高效的编码法，其主要的缺点是： ( 1 ) 码字不是等长的，不便于数据存储单元收集代码： ( 2 ) 前面提到的几种码都缺乏构造性，不能用数学方法建立一一对应关系； ( 3 ) 需要在编码过程中知道每种消息出现的概率，但这实际上难以做到。 1 1 2 预测编码 预测编码是建立在现代统计学和控制论基础上的，其基本思路是，在图像编 码过程中，可以利用图像像素间的相关性，根据某一像素的值来预测相关下一点 的取值，然后将像素点的实际值和预测值相减得到一个误差值，对该误差值进行 编码口3 1 。 预测编码主要有两大类，即a m ( d e t am o d u l a t i o n ) 和d p c m ( d i f f e r e n t i a lp u l s e c o d em o d u l a t i o n ) ，d p c m 实际上是刖m 和p c m ( p u l s e c o d i n gm o d u l a t i o n ) 两种 技术相结合的编码方法。 图像信号的p c m 编码与语音信号的p c m 编码相比并没有什么原则上的区别， 但图像信号，特别是视频图像信号占的频带宽，要求响应速度快，因此在电路设 计上有较大的难度。 1 1 - 3 变换编码 图i1 变换编码模型 f i g u r e1 1t r m a s f o r mc o d i n gm o d e l 变换编码的基本模型如图1 1 所示，可以看出变换编码主要由：映射变换、量 化及编码器组成。映射变换据是把图像中的各个像素从一种空间变换到另一种空 间，然后针对变换后的信号再进行量化与编码操作。解码时，先对接收信号进行 译码，再进行反变换恢复原始图像。 映射变换的关键是在于能够产生一系列更加有效的系数，对这些系数编码所 需的总比特数比对原始图像进行编码所需的总比特数少，从而达到数据压缩的目 2 的。 映射变换的方法很多，基本可以分为两类：一类是特殊的映射变换编码法， 如一维行程编码、等值线编码等：另一类是函数变换编码法，传统的正交变换编 码有傅里叶变换、d c t 变换、沃尔什一哈达玛变换等，近年来利用小波变换的编 码方法也得到快速的发展，成为当今图像编码领域的研究前沿和热点之一，1 2 2 节和后面的论述中对小波变换编码方法作了更多的和更详细的介绍，这是本文主 要讨论的编码方法。 严格的说，预测编码也是一种变换编码的方法，但它又具有自身的特殊性， 所以在这里就分开来叙述。我们也可以看出，变换编码也是一种混合编码的方法， 因为映射变换本身一般是不会压缩数据的，比如正交函数变换只是把图像从空间 ( 时间) 域变换到能量比较集中且不相关的变换域，这样对变换系数编码就可以 使存在于相关性中的冗余度得以去除，而且可以选择变换系数中能量集中的部分 编码，也就到达了对数据进行压缩的目的。所以，交换后的系数仍然必须经过量 化和编码才能达到数据压缩的目的。 1 9 9 1 年，国际电报咨询委员会( c c i t t ) 和国际标准化组织( i s o ) 联合组成的专 家组，共同制定了静止图像的数码率压缩标准( 1 9 9 4 年正式通过) ，即j p e g ( t h e j o i n tp h o t o g r a p h i c e x p e r tg r o u p ) ，它就是采用了d c t 变换，而最近才提出的新的 国际标准j p e g 2 0 0 0 则已经采用了小波变换。 1 1 4 其它编码方法 ( 1 ) 分形图像压缩编码 近十年来，分形( f r a c t a l ) 在图像压缩中的应用也是图像数据压缩领域中的 一个热点之一。基于分形的图像压缩方法与经典的图像数据压缩方法相比，在思 维方式上有很大的突破，其压缩比在理论上可超过经典压缩方法的几个数量级， 分形图像压缩的发明人之一m b a m s l e y 在1 9 8 8 年发表的论文中宣称分形图像压 缩可达到1 0 0 0 ：1 的压缩比。分形图像压缩极高的压缩比、快速的解压缩速度颇 引入关注。但其编码速度过于耗费时间，仍是制约其应用的主要难点。因此，尽 管分形图像压缩有巨大的潜力，但要把这种潜力释放出来，还有许多问题有待迸 一步的研究。目前的分形图像压缩还处在理论探讨阶段，离实际应用还有有不小 的距离。 ( 2 ) 基于模型的图像编码 基于模型或知识的编码方法，是在编码端通过各种分析手段，提取所建模型 的特征与状态参数。在解码端依据这些参数。通过模型及相关知识生成所建模的 信源。这类方法是把计算机视觉和计算机图形学中的方法应用到图像编码中。 ( 3 ) 利用神经网络的图像编码 重庆大学硕士学位论文 神经网络法是模仿人脑处理问题的方法，通过各种人工神经元网络模型对数 据进行非线性压缩。人工神经网络是一个非线性动态网络，工作过程一般分训练 和工作两个阶段。训练阶段就是使用一些训练图像和训练算法，调整网络的权重， 使重建图像的误差最小。目前直接用于图像压缩编码的神经网络主要有反向误差 传播( b p ) 型和自组织映射( k o h o n e n ) 型。 这几种编码的方法都试图充分利用计算机图形学、计算机视觉、人工智能与 模式识别等相关学科的研究成果，为图像编码开拓出广阔的前景。但是由于这些 编码方法增加了分析的难度，所以大大增加了实现的复杂性。 从当前发展情况来看，分形编码等方法仍处于待深入研究的阶段，目前还存 在一些明显的不足：分形法由于图像分割、迭代函数系统代码的获得非常困难， 因而实现起来时间长，算法异常的复杂，因而难以实现和应用；模型法则仅限于 人头肩像等基本的图像上，进一步的发展有赖于新的数学方法和其它相关学科的 发展：神经网络的工作机理至今仍不清楚，硬件研制不成功，所以在图像编码中 的应用研究进展缓慢，目前多与其他方法结合使用。 在前面介绍的各种图像编码方法中，统计编码属于有损编码，而预测编码和 变换编码可以实现无损编码，也可以实现有损编码。分形图像压缩和基于模型的 图像编码也是有损的。对于图像的有损压缩，目前以可以取得比较令人满意的效 果：对图像进行无损压缩的研究虽一直没有停顿过，但图像的无损压缩效果却一 直还不理想。而无损图像压缩在医学、军事、遥测等众多领域仍然有广泛的需求。 综上所述，在目前的图像编码研究领域中，虽然存在不少的热点，但基于小 波变换的编码方法却具有特别重要的意义。因此，本文接下来将介绍小波在图像 编码中的研究情况。 1 2 小波分析在图像压缩编码研究中的应用 小波变换是一种变分辨率的分析方法。它对高频信号采用小时窗，对低频信 号采用大时窗进行分析。这正好与自然界中高频信号一般持续时间短，而低频信 号持续时间较长的时频分布特性相吻合，非常适合于图像处理。在进一步介绍小 波分析之前，我们先简要的回顾一下小波分析方法的历史。 小波分析的思想最早可以追述到上个世纪的晟初十年，1 9 1 0 年。h a a r 提出了 小波规范正交基，即最早的小波基，但当时还没有出现“小波”这一术语。“小波分 析( w a v e l e t a n a l y s i s ) ”这一概念最早是在1 9 8 1 年，由法国的地质物理学家m o r l c t 提出的。1 9 8 5 年，法国大数学家m e y e r 首先提出光滑的小波正交基，即后来的 m e y e r 基；1 9 8 6 年m e y e r 及其学生l e m a r i e 提出了多尺度分析的思想，为小波理 论做出了重大的贡献。1 9 8 8 年，女数学家d a u b e c h i e s 提出了具有紧支集光滑正交 4 小波基，即d a u b e c h i e s 基。之后，信号分析专家m a l l a t 提出了多分辨率分析的概 念，给出了构造正交小波基的一般性方法，并以多分辨率分析为基础给出了著名 的快速小波算法m a l l a t 算法( f w t ) 。u # - i 9 0 年代，s w e l d e n s 等人提出了用提升方案来构造小波的方法5 6 t ”，这种以 新的方法构造的小波可以称为第二代小波，以便同以前的小波相区别。第二代小 波构造方法的继承了第一代小波变换的多分辨率特性，同时不依赖于傅立叶变换， 因此利于构造非线形的小波，在图像处理等领域有广阔的应用前景。 而对于图像压缩编码而言，小波变换得以广泛应用的重要原因在于一方面它 拥有传统变换压缩方法的优点，能够很好地去除图像数据中的统计冗余；另一方 面，小波变换的多分辨率特性，使变换后的图像数据能够保持原始图像在各种分 辨率下的精细结构，为进一步去除图像中的结构冗余信息提供了便利。般来说， 对于图像压缩，小波的正则性比频率选择性重要。 实际上，早在1 9 8 6 年，w o o d s 等人就构造了第一个真正意义上小波图像编码 器，但那时在图像领域人们却把小波编码称为子带编码。因为在当时人们还没有 完全搞清楚子带编码的工作机理，更不清楚它与数学领域的小波基有着千丝万缕 的联系，直到多分辨分析理论提出。信号处理领域的专家们才从理论上统一了众 多子带编码器的工作原理。子带分解其实质上是小波分解，基于子带的图像编码 实质上是基于小波的图像非线性逼近，因此后来的“子带编码”和“小波编码”两个词 就不再加以区别。伴随着数学领域的小波理论的发展和非线性逼近论研究的深入， 小波图像压缩取得了极大的进展。一个极具表现力的实证是d a u b e e h i e s 所发现的 小波双正交基立即被转化为图像分解所使用的具有线性相位多通道完全重建滤波 组a 自从小波理论引入图像处理领域，图像处理工程师们就开始逐渐从非线性逼 近论和泛函分析的角度出发，分析、设计和改进图像压缩应用算法。 目前，对于小波变换图像压缩的研究主要集中在两个方面：一是小波基的选 择。一是小波系数的编码。因为小波变换本身并不能压缩图像，只是提供了减少 比特率的一种可能，必须结合其它编码技术对小波系数编码才能实现压缩目的。 所以，基于小波变换的图像压缩方法通常分为如下3 个步骤小波变换、量化和编 码。 此类方法首先对图像进行多级小波分解，然后对每层的小波系数进行量化， 如零树编码进行量化，矢量量化等，再对量化后的系数进行编码，如算术编码、 哈夫曼编码等无失真编码。对于基于小波变换的图像压缩编码方法，对小波交换 后系数的量化和编码是实现数据压缩的关键，也是本文的研究重点。 1 2 1 小波的构造 前面简述了小波交换分析方法的发展，在图像压缩编码研究中，可以按照构 重庆大学硕士学位论文 造小波的方式不同，把图像压缩中用到的小波分为第一代小波和第二代小波。 第一代小波是在基小波的基础上通过平移和膨胀得到不同分辨率下的小波基 函数，并且第一代小波变换后的系数是浮点数，由于受到计算机数据存储和传输 方式的限制，往往不能精确恢复信号，同时浮点数在压缩编码时，一般需要进行 取整量化，因此无法达到无损压缩的目的，只能适用于有损压缩。 第二代小波有提升小波、内插小波、区间小波、m 带小波和非线性小波等， 这些小波在改善图像压缩品质和提高执行速度方面都产生了积极效果。 第二代小波构造方法的特点是： ( 1 ) 继承了第一代小波变换的多分辨率特性： ( 2 ) 不依赖傅立叶变换； ( 3 ) 利于构造非线性小波，如整数小波； ( 4 ) 图象的恢复质量与变换时边界采用何种延拓方式无关。 在这些方法中，提升方法又是一种更有效的、优秀的构造第二代小波的方法。 “提升”算法的基本思想是将现有的小波滤波器分解成基本的构造模块，分步骤完成 小波变换。因此，可以将小波变换分解成3 个过程：分裂，预测和修正( u p d a t e ) 。 p 5 ，6 ，7 j s w e l d e m 已经证明在提升的基础上可以进行整数集到整数集的小波变换，即一 个整数集合通过小波变换得到的仍然是整数集合【6 】。这就给数字图象的压缩编码带 来了好处，由于不需要对变换后的系数进行量化，因此提供了实现无损压缩的可 能。 1 2 2 量化和编码 前面已经提到，原始图像经过小波变换后，还需要经过量化和编码才能真正 实现图像压缩的目的。目前，主要的量化和编码方式有：统计编码、嵌入式零树 编码算法( e z w ，t h ee m b e d d e dz e r o t r e ew a v e l e ta l g o r i t h m ) 、可逆嵌入小波压缩 ( c r e w ，c o m p r e s s i o n w i t h r e v e t s i b l e e m b e d d e d w a v e l e t s ) 、分层树集合分割算法 ( s p i h t ，s e tp a r t i t i o m n gi nh i e r a r c h i a e a lt r e e s ) 、优化截断的嵌入式块编码 ( e b c o t ，e m b e d d e db l o c kc o d i n gw i t ho p t i m i z e dt n m c a t i o n ) 、嵌入式块集合分 割算法( s p e c k ，t h es e tp a r t i t i o ne m b e d d e db l o c kc o d e r ) 、小波数据的形态学表 示( m r w d ，m o r p h o l o g i c a lr e p r e s e n t a t i o no f w a v e l e td a t a ) 、连接重要性连通分支 分析( s ic c a ，s i g n i f i c a n c 净l i n k e dc n c c b e dc o m p o n e n t a n a l y s i s ) 等。 当小波变换最初用于图像压缩中时，对小波系数的编码是直接使用的统计编 码方法，如霍夫曼编码、算术编码等，其效果并不理想。 直到1 9 9 3 年，s h a p i r o 提出了f z w 算法【s l ，对小波系数编码的研究作出了重 大的突破。s h a p i r o 根据小波系数的统计分布规律，提出了一个假设：如果空间树 6 的粗尺度的小波系数对t 门限是不重要的，则在这裸小波树的细尺度的小波系数 也极可能是不重要的。基于此s h a p i r o 引入一个小波“零树”，通过定义p o s 、n e g 、 i z 和z t r 四种符号进行空间小波树递归编码，有效地剔除了对高频系数的编码， 极大地提高了小波系数的编码效率。这个算法采用的是渐进式量化和嵌入式编码 模式，算法复杂度低。因为e z w 算法的出现打破了信息处理领域长期笃信的准则： 高效的压缩编码器必须通过高复杂度的算法才能获得，因此e z w 编码器在数据压 缩史上具有里程碑意义。 1 9 9 5 年，z a n d i 和a 1 e n 等人提出了c r e w 编码方法。它是一个包含了有损 和无损静态图象压缩的系统，使用了一个最好小波滤波器的可逆近似，即整数到 整数的变换，该方法是利用了变换域中空间及频率信息的基于内容的编码。它强 调了小波变换在渐进图象编码中的重要性 9 1 。但后来研究人员发现，该方法实际 上是一种与s p i e l 非常相似的方法，本文后面详细分析了s p i h t 算法，就不再讨 论c r e w 方法。 1 9 9 6 年，由s a i d 和p e a r l m a n 提出的s p i h t 算法则利用了空间树分层分割的 方法，间接实现空间小波树的比特面排序，有效地减小了比特面上编码符号集的 规模i l “。虽然s p h i t 算法实现与e z w 算法有较大差别，但其核心思想与e z w 如 出一辙。同e z w 相比较，它的主要成功之处还在于构造了两种不同类型的空间零 树，从而可以更好的利用小波系数的幅值衰减规律。同e z w 编码器一样，s p h i t 编码器的算法复杂度低，产生的也是嵌入式比特流，但编码器的性能较e z w 有很 大的提高。 m r w d 是s e r v c t t o 、r a m c h a n d r a n 等人在1 9 9 6 提出的一种基于形态学的小波 系数编码方法1 1 7 1 8 】，其最大的特点是将形态学的内容引入了对小波系数的编码中， 虽然其效果改善还不明显，但毕竟给我们提供了一种新的启示。 1 9 9 8 年，b i n g - b i n gc h a i 和j o z s e f v a s s 等人在m r w d 和s p i h t 的基础上改进 提出了s l c c a 算法【1 3 , 1 4 1 5 , 1 6 】。 e b c o t 是优化截断的嵌入式块编码的缩写，该方法由d a v i dt a u b m a n 在1 9 9 8 年的时候提出t 如s h a p i r o 的e z w 、s a i d 和p e a r l m a n 的s p i h 等算法一样，e b c o t 也是对小波变换后生成的子带进行编码的一种算法1 1 2 】。j p e g 2 0 0 0 已经采纳e b c o t 算法作为j p e g 2 0 0 0 标准的编码算法。在算法实现上，e b c o t 编码是先将每个子 带分成一个个相对独立的码块，然后使用优化的分层截断算法对这些码块进行编 码，产生压缩码流，结果图像的压缩码流不仅具有s n r 可扩展而且具有分辨率可 扩展，还可以支持图像的随机存储。比较而言，e b c o t 算法的复杂度较e z w 和 s p i h t 有很大的提高，但由于是采用优化截断方式，e b c o t 的压缩性能也比s p i h t 略有改善。 7 重庆大学硕士学位论文 1 9 9 9 年，i s l a m 和p e a r l m a n 利用了图像的块状结构，提出了s p e c k 算法】， 它同样是完全嵌入式的编码，能够实现图像的渐近传输，具有计算复杂度低的特 点。由于其采用了基于块的编码方案，因此利于在存储空间小的情况下应用。 近年来，基于小波变换的图像压缩研究仍主要集中在对小波系数编码的方法 上，主要考虑利用小波系数的特点，改善图像压缩的性能。小波分析的方法不仅 为多分辨分析、时一频分析和子带编码建立了统一的分析方法，提供了更合理的 表示框架，而且它体现着小波分析这一新型分析方法的优越性：它有快速算法， 实现起来简单方便、速度快，可暂时弥补分形等编码技术的不足：它有着先进的 分析方法，可有效提高现有图像编码标准的水平。 所以，基于小波变换的图像编码研究是当前图像编码领域的前沿和热点。如 前面已经提到的静止图像的最新压缩标准p e g 2 0 0 0 ，就已经用小波变换代替 了广泛在图像处理中应用的离散余弦变换( d c t ，d i s c r e t ec o s i n et r a n s f o r m s ) 。 1 3 本课题的主要工作 本课题为“基于燕数小波变换的图像压缩编码方法”，首先对提升方法进行了详 细的分析，选用了适合图像压缩的三种小波，并用提升方法将这些小波分解为提 升步骤，进而实现可逆的从整数到整数的小波变换，为后面研究无损图像压缩打 下基础。 工作的重点是研究对小波系数进行编码的方法中先进和重要的一类方法 基于分级量化的重要性测试编码方法，对其中的经典算法( 即s p i h t 和s p e c k ) 进行了分析，在此基础上探寻对图像进行无损压缩的算法，以期提高无损图像压 缩的性能，缩短短算法的执行时间，并同时兼顾图像的有损压缩。 为实现以上目标，本文主要做了以下的工作： ( 1 ) 选择合适的小波，并用提升方法构造从整数到整数的小波。比较了传 统的小波和用提升方法构造的优缺点，并对此作了详细的阐述。用c + + 编程实现 了用提升方法构造的小波。 ( 2 ) 设计对小波系数的无损压缩算法。深入研究目前先进的小波系数编码 算法中具有代表性的s p i h t 、s p e c k 算法，阐述了其工作原理，主要的特点。 ( 3 ) 提出自己编码方式，从编码速度和压缩率上使本文的算法具有更好的 性能。用c 卜+ 编程实现了算法。 ( 4 ) 研究了算术编码的方法，并与前面的编码算法结合，改善压缩性能。 用c + + 编程实现了经典的算术编码方法。 ( 5 ) 设计了基于接数小波的图像压缩系统。该系统可以完成无损图像压缩 和有损图像压缩。 8 ( 6 ) 用c + + 编程实现了所设计的编码系统的软件，即c o d e e 2 0 0 3 。该软件可 以直接对b m p 图像进行编码，也可以为了研究的需要进行分步的编码，并能统计 编码的效果。而且该软件采用面向对象的软件设计技术，可以方便的加入新的编 码算法，既具有一定的实用性，又特别适合于研究编码算法。 ( 7 ) 利用c o d e c 2 0 0 3 压缩测试图像，对比