（信号与信息处理专业论文）基于小波变换的图像压缩编码算法及其并行化研究.pdf

摘要 基于小波变换的图像压缩编码算法及其并行化研究 作者简介：张新菊，女，19 8 6 年0 1 月出生，师从成都理工大学罗省贤教 授，20 11 年7 月毕业于成都理工大学信号与信息处理专业，获得工学硕士学位 摘要 数字图像作为信息的载体，具有直观、明确、高效的特点，但其数据的海 量性给存储和传输也提出了难题，因此图像压缩不可避免，图像压缩算法的研 究也就成了现在信息处理的热点。 近年来，基于小波变换进行图像的压缩编码取得了迅速发展，对图像的变 换系数采用不同的量化和编码，就得到了不同的压缩编码算法。在各种基于小 波变换的图像编码算法中，s h a p i r o 提出的嵌入式小波零树编码e z w 算法和基 于e z w 算法改进的多级树集合分裂编码s p i h t 算法是目前公认的两种较成功 的算法，本文对这两种算法的传统算法分别进行研究，基于两种算法存在的不 足提出了改进算法，并且通过实验证明了改进算法的有效性。 传统的嵌入式小波零树编码e z w 算法采用小波零树结构思想、逐次逼近 量化方法、z 字型扫描顺序，可以保证一定的编码效率，但仍然存在最低频能 量损失大、零树根较少、编码量大等不足。本文的改进算法选用z 9 7 双正交小 波进行图像分解和重构，由于z 9 7 双正交小波具有较好的消失矩和光滑性、较 高的正则阶数，可以保证较好的小波性能，利于压缩编码。此外，改进算法对 图像的最低频单独进行d p c m 编码，可以避免最低频子图受到很大的损失，在 低码率时保证恢复图像的质量；对最高频边缘子图编码时不做小波系数重要后 代的判断处理策略，较大程度的消除了编码冗余；改变了z 字型扫描顺序，针 对不同层次图像采用不同扫描顺序，有利于生成更多的零树根。仿真结果表明， 改进算法与传统e z w 算法相比，重构图像的峰值信噪比p s n r 有一定的提高， 均方误差减小，编码、解码效率有所提高。 传统s p i h t 算法在系数子集的分割和重要信息的传输方面采用了独特的 方法，能够在实现幅值大的系数优先传输的同时，隐式地传送系数的排序信息。 但是传统s p i h t 算法存在未充分考虑人眼视觉特征、算法占用内存空间太大等 问题，针对这些问题，本文提出改进算法，改进算法仍然选取z 9 7 双正交小波 作为小波基，在阈值处理上结合人眼视觉特性h v s 进行特殊处理。实验仿真验 证了改进算法较传统s p i h t 算法的重构图像可以得到更高的主观信噪比，视觉 效果较好，尤其是在图像的细节部分效果更为显著。 成都理工大学硕士学位论文 最后，本文对e z w 改进算法的编码部分实行了并行化处理。e z w 改进算 法的编码部分计算量大，使用串行处理编码效率较低。本文研究的并行算法利 用e z w 改进算法扫描过程存在的内在并行性，基于m p i 实行了并行化处理， 实验结果表明，并行编码计算达到了较高的并行效率，验证了并行算法的有效 性。 关键词：数字图像小波变换压缩编码零树并行化 r e s e a r c ho ft h ei m a g ea l g o r i t h mo fc o m p e s s i o na n dc o d i n g b a s e do nw a v e l e tt r a n s f o r ma n di t sp a r a l l e l i z a t i o n i n t r o d u c t i o no ft h ea u t h o r ：z h a n g x i n j u ，f e m a l e ，w a sb o r n i nj a n u a r y , 19 8 6 ， w h o s et u t o rw a sp r o f e s s o rl u os h e n g x i a n s h eg r a d u a t e df r o mc h e n g d u u n i v e r s i t yo ft e c h n o l o g yi ns i g n a la n di n f o r m a t i o np r o c e s s i n gm a j o r a n dw a s g r a n t e dt h em a s t e rd e g r e ei nj u l y , 2 0 11 a bs t r a c t d i g i t a li m a g eh a st h ef e a t u r e so fi n t u i t i v e ，c l e a ra n de f f i c i e n t ，b u ti t sm a s s o f d a t at ot h es t o r a g ea n dt r a n s m i s s i o n a r ea l s op r e s e n t e dp r o b l e m s ，s ol m a g e c o m p r e s s i o ni si n e v i t a b l ea n dt h es t u d yo fi m a g ec o m p r e s s i o na lg o r i t h mh a s b e e n n o wh o ts p o t si ni n f o r m a t i o np r o c e s s i n g i nr e c e n ty e a r s ，i m a g ec o m p r e s s i o nb a s e do nw a v e l e tt r a n s f o r mh a sa c h i e v e d r a p i dd e v e l o p m e n t d i f f e r e n tq u a n t i z a t i o na n dc o d i n go f t r a n s f o r mc o e f f i c i e n t so f i m a g e sc a ng e td i f f e r e n tc o m p r e s s i o na l g o r i t h m s d u r i n ga v a r i e t yo fi m a g ec o d i n g a i g o r i t h m sb a s e do nw a v e l e tt r a n s f o r m ，s h a p i r o se m b e d d e d z e r o t r e ew a v e l e te z w a i g o r i t h ma n dt h ei m p r o v e de z wa l g o r i t h mf o rs e tp a r t i t i o n i n g i nh i e r a r c h i c a lt r e e s s p i h tc o d i n ga l g o r i t h ma r ew i d e l yr e c o g n i z e da st w oo ft h em o r e s u c c e s s f u l m e t h o d s t h i st h e s i ss e p a r a t e l ys t u d i e s t h et w ot r a d i t i o n a la l g o r i t h m s ，a n dp r o p o s e s i m p r o v e m e n t sb a s e do nt h es h o r t c o m i n g so f t h et w oa l g o r i t h m s ，a n dd e m o n s t r a t e s t h a tt h ei m p r o v e da l g o r i t h mi se f f e c t i v e t h et r a d i t i o n a le m b e d d e dz e r o t r e ew a v e l e te z wa l g o r i t h ma d o p t sz e r o - t r e e a l g o r i t h mi d e a s ，s u c c e s s i v ea p p r o x i m a t i o nq u a n t i z a t i o na n dz f o n t ss c a no r d e rt o g u a r a n t e et h ec o d i n ge f f i c i e n c y h o w e v e r ，t h e r e a r es t i l li n s u f f i c i e n t ，s u c ha sa l a r g ee n e r g yl o s so ft h el o w - f r e q u e n c y , f e wz e r or o o t sa n dl a r g ee n c o d i n g ，a n d s o o n t h ei m p r o v e da l g o r i t h mi nt h i st h e s i su s e sz 9 7b i o r t h o g o n a lw a v e l e tf o ri m a g e d e c o m p o s i t i o na n dr e c o n s t r u c t i o n ，b e c a u s e t h a tz 9 7h a sag o o db i o r t h o g o n a l w a v e l e tv a n i s h i n gm o m e n t sa n ds m o o t h n e s s ，h i g h e rr e g u l a ro r d e r ，t o g u a r a n t e e g o o dp e r f 0 咖a n c e ， w h i c hw i l l h e l pc o m p r e s s i o n i na d d i t i o n ，t h ei m p r o v e d a l g o r i t h ms e p a r a t e l yc o d e st h ei m a g eo f t h el o w e s tf r e q u e n c yb yd p c mc o d i n gt o a v o i dt h eg r e a tl o s s ，a n de n s u r et h eq u a l i t yo fi m a g er e s t o r a t i o nw h e ni n l o wb i t r a t e t h es t r a t e g yn o tt oj u d g et h ei m p o r t a n t f u t u r eg e n e r a t i o n so fw a v e l e t i i ! 成都理工大学硕士学位论文 c o e f f i c i e n t sw h e ns u b g r a p h so nt h ee d g eo ft h eh i g h - 疔e q u e n c yc o d i n g ，e l i m i n a t e t h ec o d i n gr e d u n d a n c yg r e a t l y i tc h a n g e st h ezs h a p e ds c a no r d e r , u s i n gd i f f e r e n t s c a n i n go r d e rf o rd i f f e r e n tl e v e l so fi m a g e st oh e l pg e n e r a t em o r ez e r or o o t s s i m u l a t i o nr e s u l t ss h o wt h a t ，t h ep s n rp e a ks i g n a lt on o i s er a t i oo fr e c o n s t r u c t e d i m a g eh a si m p r o v e dt os o m ee x t e n to fi m p r o v e da l g o r i t h mc o m p a r e dw i t ht h e t r a d i t i o n a le z wa l g o r i t h m ，m e a ns q u a r ee r r o ri sd e c r e a s e d ，a n de n c o d i n ga n d d e c o d i n ge f f i c i e n c yi si m p r o v e d t h et r a d i t i o n a ls p i h t a l g o r i t h mu s e sau n i q u ea p p r o a c hi nas u b s e to ft h ep a r t i t i o n c o e f f i c i e n ta n dt h et r a n s m i s s i o no fi m p o r t a n ti n f o r m a t i o n ，t ot r a n s f e rc o e f f i c i e n t i m p l i c i t l yo r d e r i n gi n f o r m a t i o n w h e na c h i e v i n g l a r g ea m p l i t u d et r a n s m i s s i o n c o e f f i c i e n ta tt h es a m et i m ep r i o r i t y b u tt h et r a d i t i o n a ls p i h ta l g o r i t h md o e sn o t c o n s i d e rt h ec h a r a c t e r i s t i c so fh u m a nv i s i o nf u l l ya n dt a k e st o om u c hs p a c ea n d o t h e ri s s u e s t oa d d r e s st h e s ei s s u e s ，t h i st h e s i sp r o p o s e si m p r o v e da l g o r i t h m i m p r o v e da l g o r i t h ms t i l ls e l e c tt h ez 9 7b i o r t h o g o n a lw a v e l e ta sw a v e l e tb a s i s ，a n d a d o p t ss p e c i a lh a n d l i n gi nt h et h r e s h o l dp r o c e s s i n gc o n s i d e r i n gt h eh u m a nv i s u a l s y s t e mh v s s i m u l a t i o nr e s u l t ss h o wt h a tt h en o i s er a t i o o ft h er e c o n s t r u c t e d i m a g es i g n a lo ft h ei m p r o v e da l g o r i t h mi sh i g h e rt h a nt h e t r a d i t i o n a ls p i h t a l g o r i t h m ，a n dt h ev i s u a le f f e c ti sb e t t e re s p e c i a l l ys i g n i f i c a n ti nt h ed e t a i l so f t h e i m a g e f i n a l l y , t h i st h e s i si m p l e m e n t sp a r a l l e lp r o c e s s i n gi n t h ec o d i n gp a r to f i m p r o v e da l g o r i t h mo fe z w t h ec o m p u t a t i o no ft h ec o d i n gp a r to fe z w i sl a r g et o g e t l e s se f f i c i e n ts e r i a l p r o c e s s i n g c o d e t h i sa l g o r i t h mu s e st h ei n h e r e n t p a r a l l e l i s mo ft h es c a n n i n gp r o c e s si ni m p r o v e da l g o r i t h mo fe z w , t oi m p l e m e n t p a r a l l e lp r o c e s s i n gb a s e do nm p i ，a n de x p e r i m e n t a lr e s u l t ss h o wt h a t ，t h ep a r a l l e l c o d i n gc o m p u t a t i o n h a sa c h i e v e dah i g h e r e f f i c i e n c y , w h i c hi m p r o v et h e e f f e c t i v e n e s so ft h ep a r a l l e la l g o r i t h m k e yw o r d s ：d i g i t a li m a g e ，w a v e l e tt r a n s f o r m ，c o m p e s s i o na n dc o d i n g ，z e r o t r e e ， p a r a l l e l i z a t i o n 第1 章引言 第1 章引言 1 1 选题依据 数字图像数据量庞大和信道容量有限的矛盾提出了数据压缩的必要性，推 动了数字图像压缩编码技术的迅猛发展，并且随着信息传输量的不断膨胀，对 数字图像压缩编码技术提出了越来越高的要求。早期制约图像处理发展的因素 主要是一些硬件环境和应用广泛性的问题，科学技术的发展已经逐渐攻克了这 些障碍，使得图像处理专家可将更多的注意力转向对图像处理和压缩算法的研 究【1 1 。 针对数字图像相邻像素之间存在的空间冗余、时间冗余、信息熵冗余、视 觉冗余等，可以采取不同的压缩方法【3 】。传统的压缩编码方法尽管在目前的压 缩方法中仍被采用，但是有很多缺点和不足，例如d c t 变换的压缩图像会出现 不可避免的“方块效应，这种“方块效应在高压缩比时表现尤其明显，成为 限制d c t 变换编码质量的主要因素。 因此，人们一直在研究取代传统方法的新压缩方法。有“数学显微镜 之 称的小波变换同时具有良好的空间分辨率和频率分辨率的特性，使变换系数的 能量能同时在空间和频率上集中；小波分解把图像分层次按照小波基展开，形 成塔形的数据结构，与人眼从粗到精、从全貌到细节的观察习惯一致，可以根 据图像的性质及给定的图像处理标准确定展开到某一级，还可以对细节分量和 近似分量进行分解【4 】。可见，小波变换特别适合于细节丰富、空间相关性差、 冗余度低的图像数据压缩处理【2 】；经小波变换处理过的图像能保持信号与图像 的特征基本不变，且在传递过程中可以抗干扰，在实现高压缩率的情况下能够 保证较高的图像质量，具有较好的视觉效果。 近年来，小波变换已经受到图像压缩编码领域的高度重视，出现了各种基 于小波变换的图像压缩编码方法。作为一种优秀的图像压缩编码方法，基于小 波变换的图像压缩编码算法在图像压缩这一领域有着重大的实用价值和广阔的 发展前景。本文就是基于这样的研究背景，分析研究现有的两种基于小波变换 的压缩编码算法，并且针对其存在的问题，提出改进算法。 1 2 研究现状 基于小波变换的图像压缩方法经历了一段时间的发展历程。l9 8 2 年，b a t t l e 在构造量子场论中使用了类似c a l d e r o n 再生公式的展开。1 9 8 4 年，法国地球物 理学家m o r l e t 分析地震波局部性质时，发现传统的f o u r i e r 变换难以达到要求， 成都理工大学硕士学位论文 创性地引入小波概念对信号进行分解。之后，理论物理学家g r o s s m a n 对m o r l e t 的这种信号进行了展开可行性的研究，按照一个确定数的伸缩平移系 r l ，一 l 、1 i 口1 1 缈i a , m ui ：a , b r ，a 0 对其展开，为小波发展奠定了基础。1 9 8 6 年m e y e r 【一la j 构造出了具有一定衰减性的光滑函数，其二进制伸缩平移系 杪m o ) = 2 - m y ( 2 t 一七) ：j , k 萑z 构成了r 伍) 的规范正交基。1 9 8 7 年m a l l a t 将计 算机视觉领域内的多尺度分析的思想引入到小波分析中，小波函数的构造及信 号按小波变换的分解和重构，并且将此算法应用到图像的分解与重构处理中。 d a u b e c h i e s 构造了具有有限支集的正交小波基，也应用到图像处理中，但是在 数据压缩方面应用效果最好的是a n t o n i n i 构造的双正交小波。总之，小波理论 的逐步完善，已经发展成为图像处理的有力数学工具，有可能取代传统的 f o u r i e r 变换【5 】。 基于小波分析的图像压缩方法很多，目前比较成功的有小波域纹理模型方 法、小波变换零树压缩法、小波包最好基法、小波变换向量量化压缩法等【4 】。 此外，基于小波变换零树压缩法和连续标量量化逼近压缩的编码方法是目前研 究方法中最具有代表性的方法，基于此方法基础上的两种算法：嵌入式小波零 树编码e z w 算法和多级树集合分裂s p i h t 算法以其重构质量好、压缩比高、 硬件易于实现等优点成为当今数字图像压缩编码的主要方向之一，使数字图像 压缩编码技术提升到了一个新水平，也是人们继续研究新方法的基础。 1 3 研究目标和内容 本文着重研究目前两种比较流行的基于小波变换的嵌入式小波零树编码 e z w 算法和多级树集合分裂s p i h t 算法，基于这两种算法提出高效的改进算 法，并进一步应用m a t l a b 开发工具实现改进算法，达到在同等压缩比的情 况下提高重构图像质量的目的。在此基础上，为了提高压缩编码算法的计算效 率，基于m p i 研究和实现改进算法的并行算法。 主要研究内容如下： ( 1 ) 探讨数字图像压缩编码的基本理论，分析图像压缩编码系统的性能评 价和度量标准，以及静态图像压缩编码的国际标准； ( 2 ) 对小波理论进行研究，分析其多分辨率分析特点以及应用于图像分解 后小波变换域系数的特点，研究影响小波变换图像压缩效率和质量的几个主要 因素； ( 3 ) 研究e z w 算法，分析传统e z w 算法的零树结构思想、逐次逼近量 化方法、z 字型扫描顺序。针对算法在零树结构、扫描方式、编码处理方式等 的不足之处提出e z w 改进算法，并且对e z w 改进算法进行实例分析与实验仿 2 第l 章引言 真； ( 4 ) 研究s p i h t 算法，分析传统s p i h t 算法的集合分裂策略的优点，并 且针对其没有充分结合人眼视觉特征( h v s ) 的缺点，提出s p i h t 改进算法， 并且对s p i h t 改进算法进行实例分析与实验仿真： ( 5 ) 最后研究e z w 改进算法编码部分的并行化算法，基于m p i 进行并行 化算法的实验仿真。 3 成都理工大学硕士学位论文 第2 章基于小波变换的图像压缩编码 小波变换编码是近年来随小波变换研究而提出来的一种编码方法，因其具 有很好的时频空频局部特征、以及与人眼视觉特征相结合的特性。小波变换编 码在图像压缩比和质量方面明显优于传统的d c t 编码方法，这种方法已经加入 到m p e g 4 和j p e g 2 0 0 0 等国际图像编码标准，得到越来越广泛的应用f 6 】。 2 1 数字图像压缩编码基本理论 2 1 1 图像的压缩编码方法分类 ( 1 ) 第一代压缩编码方法 2 0 世纪8 0 年代前，主要用传统的信源编码方法对图像压缩，属于第一代 压缩编码方法f 7 】，如图2 1 所示。 第一代压缩 编码方法 图2 - 1 第一代压缩编码方法分类 ( 2 ) 第二代压缩编码方法 2 0 世纪8 0 年代后，出现了第二代压缩编码方法【7 l ，突破了信源编码理论， 结合分形、模型基、神经网络、小波变换等数学工具，充分利用视觉系统生理、 心理特性和图像信源的各种特性实现图像压缩，如图2 2 所示。 第二代压缩 编码方法 子带编码 分层编码 分形编码 模型编码 图2 - 2 第二代压缩编码方法分类 4 一一一一一一一一一一一一一一 码一 一码一 一码二码 编一 一编一 一编二编 素一 一测一 一换二它 像一 一预一 一变二其 第2 章基于小波变换的图像压缩编码 2 1 2 图像的编码质量评价指标 在数字图像压缩处理的过程中，人们希望以较少的比特数存储和传输图像 的同时，还要保证图像的逼真度和可懂度，这也是人们关心的问题之一。对图 像质量的传统评价方法主要有两种 s q 0 1 ：客观保真度准则和主观保真度准则。 另一种常用的评价图像编码质量的指标就是压缩比。 ( 1 ) 客观保真度准则 对图像质量进行客观评价，有几个最常用的评价参数：m s e 、s n r 和p s n r 。 m s e ( m e a ns q u a r ee r r o r , m s e ) 表示输入图像和输出图像之间的均方误 差，是常用的一个准则。设原图像为g ( f ) ，压缩后图像为雪( f ，j ) ，( f 可= 1 ， 2 ，3 , - - - , n ) ，则均方误差m s e 的表示公式为 脚2 去善犁酣一宫( 训2 ( 2 - 1 ) m s e 的值越小，代表图像的质量就越好，反之亦然。 s n r ( s i g n a ln o i s er a t i o ) 是输入图像和输出图像之间的均方信噪比，定义 公式为 ez g ( i ，_ ，) 】2 s n r = 百昔生l _ ( 2 - 2 ) 【g ( f ，力一她叫2 i = i 户i p s n r ( p e a ks i g n a lr a t i o ) 峰值信噪比在文献中比较常用，计算简单， 其定义公式为 p s n r _ l o l g l 而丝二l l 【g ( f ，j ) 一舍( f ，州2 ( 2 3 ) 其中，设定g 。= 2 - 1 ，k 为图像中表示一个像素点所用的二进制位数。一 般情况下，p s n r 的值越高，解码后图像的质量就越好，但是并不绝对代表图 像的主观质量就好，比如当p s n r 很大时，有少量噪声点出现在图像的敏感区 域，人眼可以明显看出有问题。 客观保真度准则主要用于压缩系统设计和调整，但是m s e 和p s n r 常常因 图而异，有时候甚至不能反映视觉质量的实际情况，所以客观评价不能对一幅 图像做最终评价，还需要利用主观保真度评价标准完成最终的综合评价。 ( 2 ) 主观保真度准则 主观评价结果常常受被测图像序列、视觉条件、评分结果统计方法、评价 5 成都理工大学硕士学位论文 人等因素的影响。图像的主观评价以人的主观视觉效果对图像质量来作出评价， 应该充分考虑人眼的视觉特征( h v s ) 。主观评价的常用方法是打分法，即一组 评价者给图像进行主观打分并且求其平均，表2 1 给出了主观评价的两种评分 标准。 表2 - i 图像质量的主观评价标准 评分第一种评价标准第二种评价标准 5优没有失真的感觉 4 良感觉到失真，但是没有不舒服的感觉 3中感觉有点不舒服 2 差感觉较差 l 劣感觉非常不舒服 设每种得分记为& ，每种得分的评价人数为m ，可以得到平均感觉分( m e a n o p t i o ns c o r e ，m o s ) 的主观评价分数： 七 m ，s ， m o s = 上l _( 2 - 4 ) m t l = i m o s 的值越高，表明重构图像的主观质量评价越好。 ( 3 ) 压缩比 压缩比是评价图像压缩效果的另一个重要指标，公式为 6 l c = 一 6 2 ( 2 5 ) 式中6 l 为压缩前图像每像素的平均比特数，b 2 为压缩后每像素所需的平均 比特数。一般情况下压缩比c 总是大于等于1 的，c 越大压缩程度越高，图像压 缩效果越好。 2 1 3 静态图像压缩编码国际标准 因为本文研究的对象是静态图像，所以这里只给出静态图像压缩编码的国 际标准】【1 2 】： ( 1 ) j p e g 标准 2 0 世纪9 0 年代初，国际标准化组织o s o m o 与c c i t t 联合发起的联合图 像专家组，制定了静态图像压缩编码的标准j p e g ( j o i n tp h o t o g r a p h i c e x p e r t g r o u p ) 。j p e g 是用于彩色( 2 4 b i t p i x e l ) 和灰度( 8 b i t p i x e l ) 静态图像的一种完善的 有损无损压缩方法，对相邻像素颜色相近的连续色调图像的效果很好；在较低 6 第2 章基于小波变换的图像压缩编码 的计算复杂度下，能提供较高的压缩比与保真度。 在j p e g 基准编码系统中，输入和输出图像都限制为8 b i t 图像，而量化的 d c t 系数值限制在l l b i t 。图2 3 分别为j p e g 编解、解码流程图。 j p e g 压缩处理首先会将原始图像分为不重叠的8 8 像素子块( k 队y 三 幅图像) ，然后将各子块进行d c t 变换，将得到的系数根据下式进行归一和量 化： 咖) = t o 堋d l 筹l ( 2 6 ) 式中r ( ，l ，) 是图像的一个8 x 8 块的d c t ，z ( z ，v ) 是量化表，r o u n d ( x ) 是四舍 五入函数。 将r o ，y ) 量化后，对量化系数再进行熵编码，熵编码可以采用算术或者 h u f f m a n 编码( v l c ) 。 ( a ) 编码器框图 ( b ) 解码器框图 图2 - 3j p e g 编码解码流程图 ( 2 ) j p e g 2 0 0 0 标准 j p e g 静态图像压缩标准在高比特率的时候有很好的压缩效果，但是在比 特率比较低的时候，重构图像存在严重的“方块效应 ，不能很好地满足网络图 像传输的要求。19 9 9 年，国际化标准j p e g 2 0 0 0 应运而生，该标准以小波变换 作为基本算法，采用了嵌入式编码技术，在保证高比特率及系统性能的前提下， 使低比特率时重构图像的主观保真度比j p e g 标准有明显提高。图2 - 4 给出了 j p e g 2 0 0 0 的基本编码流程。 图2 - 4j p e g 2 0 0 0 基本编码流程方框图 图中，预处理把图像分成大小相同互不重叠的矩形叠块，叠块的尺寸是任 意的，可以小到单个像素、大到整个图像。每个叠块只用自己的参数单独进行 编码。如果图像被分成为小的各个叠块，在j p e g 系统编码时进行的离散小波 变换d w t 就是针对叠块进行的。 7 成都理工大学硕士学位论文 为了达到抗干扰和任意水平的逐渐显示，j p e g 2 0 0 0 的熵编码是x , l 小波变 换系数的量化值按照不同的子带分别进行编码的。它把小的子带分成一个个小 的编码块，每个编码块单独进行行编码，对于每个编码块的各比特面分别进行 3 次扫描：重要性传播( s i g n i f i e a n e e p r o p a - g a t i o n p a s s ) 、细化( r e f i n e m e n t p a s s ) 、清 除( e l e a r u p p a s s ) 。每次扫描的输出用m q 算法继续基于上下文的自适应算术编 码，最后将压缩的各子比特面以数据包的形式输出。 j p e g 2 0 0 0 具有很多优点：良好的低比特率压缩性能；可以按照分辨率或 者像素精度进行累进式传输；可以随机获取和处理码流；优越的抗误码特性； 感兴趣区等。本文所研究的e z w 和s p i h t 算法都是基于j p e g 2 0 0 0 标准进行 的。 ( 3 ) j p e g l s t 3 】 该标准是对连续静态图像进行无损或近于无损压缩编码的国际标准，适用 于遥感、医学等应用领域的图像传输与存储，j p e g l s 标准在无损压缩方面有 着比j p e g 标准更高的编码效率，采用的技术有自适应帧内预测、行程码、 c o l o m b 编码。 2 2 小波基本理论 1 9 8 4 年法国地球物理学家m o r l e t 在分析地震波的局部性质时，发现传统的 分析方法难以满足研究的需要，于是引入了小波变换的概念。小波变换具有多 分辨率分析的特点，且在时域和频域都具有表征信号局部特征的能力，是一种 窗口大小固定不变但形状可变，时间窗和频域窗均可改变的时频局部化分析方 法；在低频部分具有较高的频率分辨率和较低的时间分辨率，在高频部分具有 较高的时间分辨率和较低的频率分辨率【7 】【”j 。小波分析的目的是“既要看到森 林( 信号的概貌) ，又要看到树木( 信号的细节) ，【1 3 】。因此，它被称为数学显微镜， 由于小波变换所具有的这种优势和特点，使得它逐渐发展为主流的数字信号处 理方法。 2 2 1 小波变换基本原理 ( 1 ) 小波基函数 设少( f ) r 似) ，其f o u r i e r 变换痧如) 满足可容性条件1 4 】： g = 上眵纠m d c a o ( 2 - 8 ) 其中口为伸缩因子，f 为平移因子，沙口f ( f ) 称为依赖于参数口，f 的连续小 波基函数。 ( 2 ) 连续小波变换 将任意r ) 空间中的函数厂o ) 在小波基下展开，即进行函数厂( f ) 的连续小 波变换( c o n t i n u ew a v e l e tt r a n s f o r m ，c w t ) ，其表达式为 吁( 口，f ) = ( 九) ，( f ) ) = 去上几妙( 等卜 ( 2 9 ) 由于小波变换对厂o ) 而言是以少( f ) 为核函数的线性变换，因此它具有线性 性、平移特性、频域特性、等内积性和能量守恒等特性4 2 1 。连续小波变换的缩 放因子是大于0 的实数，其重构是不可实现的。常用于分析信号的某些局部特 性，也可用于波形的整形处理。 ( 3 ) 离散小波变换 在计算连续小波变换时，实际上也是用离散的数据进行计算的，只是所用 的缩放因子和平移参数比较小而已，所以，连续小波变换的计算量是惊人的【4 2 1 ， 连续小波变换不能完全重构的缺陷阻碍了它的应用。因此，有必要将其离散化 处理即离散小波变换( d i s c r e t ew a v e l e tt r a n s f o r m d w t ) 。 将连续小波中的伸缩因子a 和平移因子f 离散化，取a = 口：，f = k a z o o 且 _ ，z ，相应的离散小波函数为 础) = 口：( 学卜k s t _ k r o ) ( 2 1 0 ) 离散小波变换为 d g r l s ( j ，k ) - - i s f ( t ) i t s , 册k疵= ( 九x 沙似( f ) ) ( 2 i l ) 离散小波变换重构公式为 凡) = c z d w t ：( j ，k ) 少”( f ) ( 2 - 1 2 ) ( 4 ) 二维小波变换 图像可以看做是二维信号，将小波变换应用到图像处理中，显然一维小波 变换是满足不了要求的，必须将小波变换由一维推广到二维。 令厂g 。，z ：) 2k 2 ) 表示一个二维信号，毛，吒分别表示其横、纵坐标， 5 c ，“，屯) 表示基本二维小波，则二维连续小波变换的公式为 9 成都理工大学硕士学位论文 w t s ( a ；) = ( 瓶而) ，屯“，屯) ) = ! a 缈“沙( 立a ，孕卜呶( 2 1 3 ) 对应的反演小波变换是： 炖，而) = 专f 。軎肌( 口；6 l ，也) ( 学，剥幽如 ( 2 - 1 4 ) 2 2 2 多分辨率分析 多分辨率分析概念是s m a l l a t 和y m e y e r 在1 9 8 6 年提出的，它能将此前 所有的正交小波基的构造统一起来。r 也) 中的多分辨率分析满足以下特点的一 个空间序列眈l e z n 9 2 。1 ： ( 1 ) 单调性( 包含性) ：对任意，z ，有巧c 巧一。； ( 2 ) 伸缩性：厂( f ) 巧营厂( 2 f ) 巧- l ，伸缩性体现了逼近正交小波函数的 变化、尺度的变化、空间的变化三者具有一致性； c3 ，平移不变性：对任意的七z ，有办( 2 孚f 巧办( 2 孚，一七 巧； ( 4 ) 逼近性：q 巧= o ) ，o 匕= r 伍) ； ，e 二，= c5 ，r t e s z 基存在性：存在o ，使 ( 2 了- j t 一七 ) 。z 构成巧的r ；e s z 基a 2 2 3 常用小波基 同傅里叶变换不同，小波基( 小波函数) 并不是唯一的，一切满足小波条 件的函数均可作为小波函数，在不同的应用环境下可选择不同的小波函数，从 而在图像处理中可以充分利用不同小波函数的优点，如消失矩阶数大的小波变 换函数使能量更集中，这点在压缩中用处很大；对称性好的小波函数可以避免 相移；正则性好的小波函数在信号重构中比较平滑。大部分选择支集长度在5 9 之间的小波，支集太长会产生边界问题，但是支集太短对信号能量集中不利。 一般情况下，正则性和消失矩随支集长度的增加而增高【9 】。 下面介绍一下常用的小波基： ( 1 ) h a a r ( 哈尔) 小波1 9 j h a a r 小波( 如图2 5 所示) 是所有小波中用得最早、也是最简单的小波，有 一个有限的紧支撑，它本身是一个阶跃函数，定义为 l o 第2 章基于小波变换的图像压缩编码 f 1 缈胃g ) ： 一1 l0 0 s x 0 5 o 5sx d j 。g ( m - 2 k ) ( 2 1 8 ) 其中，h 、g 分别为重构端的低、高通滤波器，o 。舛为尺度一j 上的尺度系 1 2 第2 章基于小波变换的图像压缩编码 数。 ( 2 ) 一维离散小波的分解与重构 根据上述的算术表达式，很容易得出一维小波分解与重构的快速算法，图 2 - 6 和图2 7 给出了三级分解重构示意图。 q + ， 西慵 图2 - 6 一维小波变换三级图 弓+ j ，i 印， 图2 - 7 一维小波变换三级重构 ( 3 ) 数字图像的小波分解与重构【1 5 】 数字图像是二维小波信号，它的快速算法是在一维离散小波快速算法的基 础上得到的，图像的二维小波变换就相当于在水平和垂直方向上各自独立的进 行一次一维小波变换。 图2 8 给出二维图像小波变换的一级分解图，二维小波的重构是分解的逆 过程，如图2 - 9 所示。 逐行处理逐列处理 图2 - 8 二维小波变换一级分解 1 3 l l l h h l h h 成都理工大学硕士学位论文 逐列处理逐行处理 图2 - 0 二维小波变换一级重构 其中，l l 集中了图像的大部分能量代表图像的概貌；h l 代表水平方向的 细节和垂直方向的概貌，l h 代表垂直方向的细节和水平方向的概貌，h h 代表 对角线方向的细节。 根据以上图像的分解过程可以很容易地得到图像经若干级小波分解后各个 不同方向不同分辨率的多个子图，由于图像呈现塔状，称其为“塔状结构图， 如图2 10 是图像经三级h a a r 小波分解后的塔状图。在这种塔状结构里，可以 看到小波系数和相应的位置信息的组织关系，以h h 3 为例，可看到以h h 3 单 个元素为根形成的子孙树，从它们的方向和空间位置可以看出，这种小波树中， 各级分解子带的系数之间存在很大的相似性。 。，v 撑 l l 3h l 3 h l 2 l h 3h h 3 h l l l h 2 h h 2 ：l h l h h l 图2 - 1 0 三级小波分解塔状图 图2 1 1 ( b ) ( c ) ( d ) 是用h a a r 小波基对大小为2 5 6 x2 5 6 x8 的标准c a m e r a m a n 图像( 如图2 n ( a ) 所示) 进行的一、二、三级分解的实物塔状图，不同级数 的分解产生不同分辨率的子图轮廓。 1 4 第2 章基于小波变换的图像压缩编码 ( a ) c a m e r a m a n 原始图( b ) c a m e r a m a n 一级分解图 ( c ) c a m e r a m a n 二级分解图( d ) c a m e r a m a n 三级分解图 图2 1 1c a m e r a m a n 各级小波分解塔状图 2 4 小波变换域小波系数分析 图像经小波分解后，得到一系列不同分辨率的子图像，如图2 10