（计算机软件与理论专业论文）基于小波变换的图像压缩算法研究.pdf

基于小波变换的图像压缩算法研究 摘要 数字图像压缩是图像处理领域的一个热门研究课题，其研究成果为图像的 存储、传输带来了极大的便利，因而具有重要的研究价值。在众多的图像压缩 方法中，基于小波变换的图像压缩方法具有明显的优势，因而成为现代图像压 缩领域的主流研究方向之一。 本论文分析了小波图像压缩的几种经典算法，以及j p e g 2 0 0 0 图像压缩标 准中的感兴趣区域( r o i ) 编码方法。这两方面都存在不足之处，可以做进一步改 进。本文主要研究工作如下： 1 、对小波变换的理论基础，包括连续小波变换、离散小波变换、多分辨分 析、m a l l a t 算法、双正交小波变换以及提升和整数小波变换进行了简要介绍。 对小波图像编码的几种代表算法，包括两种树型结构算法e z w 和s p i h t ，以 及两种块型结构算法s p e c k 和e b c o t ，进行了比较，并分析了树型结构算法 的不足之处。 2 、将s p i h t 算法与分形编码算法相结合，提出一种混合编码算法。先根 据一种分类算法将图像分割后的块分为三类，然后根据它们各自的特点在小波 域中分别选择s p i h t 或分形方法编码，同时结合率失真判据，使解码图像质量 高于使用s p i h t 和分形方法解码的质量。 3 、分析了j p e g 2 0 0 0 中采用的两种r o i 编码方法一一最大位移法和一般位 移法的优缺点。在最大位移法的基础上提出了一种增加过渡区域的r o i 编码改 进算法。该算法考虑了人眼视觉特点的要求，使解码后的图像具有更好的整体 视觉效果。此外，该算法的复杂度较低，并且能与j p e g 2 0 0 0 码流兼容。 关键词：图像压缩：小波变换；s p i h t ；分形编码；感兴趣区域编码 r e s e a r c ho ni m a g ec o m p r e s s i o na l g o r i t h m b a s e do nw a v e l e tt r a n s f o r m s a b s t r a c t d i g i t a li m a g ec o m p r e s s i o ni sah o tr e s e a r c hs u b j e c to fi m a g ep r o c e s s i n g ，t h e a c h i e v e m e n t so fw h i c hb r i n gg r e a tc o n v e n i e n c et ot h es t o r a g ea n dt r a n s m i s s i o no f i m a g e s 。t h u si ti so fs i g n i f i c a n tv a l u ef o rr e s e a r e h s a m o n gv a r i o u si m a g e c o m p r e s s i o nm e t h o d s ，t h em e t h o db a s e du p o nw a v e l e tt r a n s f o r l t i si so fo b v i o u s a d v a n t a g e sa n dt h e r e f o r eh a sb e c o m eam a j o rr e s e a r c hs u b j e c to fm o d e mi m a g e c o m p r e s s i o n t h ed i s s e r t a t i o n a n a l y z e ds c v e r a lc l a s s i c a la l g o r i t h m so fw a v e l e ti m a g e c o m p r e s s i o na n dt h ee n c o d i n gm e t h o d so fr e g i o no fi n t e r e s t ( r o di nj p e g 2 0 0 0 i m a g ec o m p r e s s i o ns t a n d a r d s ，b o t ho fw h i c hl e a v es o m ef l a w st ob ef u r t h e r i m p r o v e d t h em a i nw o r ko ft h ed i s s e r t a t i o ni sa sf o l l o w s ： 1 ab r i e fd e s c r i p t i o na b o u tt h et h e o r e t i cf o u n d a t i o no fw a v e l e tt r a n s f o r m sw a s g i v e n ，w h i c hi n c l u d e sc o n t i n u o u sw a v e l e tt r a n s f o r i l l s ，d i s c r e t ew a v e l e tt r a n s f o r m ， m u l t i r e s o l u t i o na n a l y s i s ，m a l l a ta l g o r i t h m ，d o u b l eo r t h o g o n a lw a v e l e tt r a n s f o r i l l ， l i f t i n gw a v e l e tt r a n s f o r ma n di n t e g e rw a v e l e tt r a n s f o r m ac o m p a r i s o nw a sm a d e b e t w e e ns e v e r a lr e p r e s e n t a t i v ea l g o r i t h m so fw a v e l e ti m a g ee n c o d i n g ，i n c l u d i n g t w oa l g o r i t h m so ft r e es t r u c t u r e ：e m b e d d e dz e r o t r e ew a v e l e t ( e z w ) a n ds e t p a r t i t i o n i n gi nh i e r a r c h i c a lt r e e s ( s p i h t ) ，a n dt w oa l g o r i t h m so fb l o c ks t r u c t u r e ： s e tp a r t i t i o n e de m b e d d e db l o c kc o d e r ( s p e c k ) a n de m b e d d e db l o c kc o d i n gw i t h o p t i m i z e dt r u n c a t i o n ( e b c o t ) b e s i d e s ，t h ed e f i c i e n c yo ft h et r e es t r u c t u r e a l g o r i t h mw a sa n a l y z e d 2 w ep r o p o s e dah y b r i de n c o d i n ga l g o r i t h mc o m b i n i n gs p i h ta l g o r i t h mw i t h f r a c t a le n c o d i n ga l g o r i t h m i tc l a s s i f i e st h ep a r t i t i o n e db l o c k so fi m a g ei n t ot h r e e c a t e g o r i e s a n du s e ss p i h t o rf r a c t a lm e t h o di nw a v e l e tf i e l da c c o r d i n gt od i f f e r e n t f e a t u r e so ft h ec a t e g o r i e s ，a n dm a k e su s eo fr a t ed i s t o r t i o nc r i t e r i o nt oa c h i e v e b e t t e ri m a g eq u a l i t yt h a nt h o s eo fs p i h ta n df r a c t a lm e t h o d s 3 b ya n a l y z i n gt h em e r i t sa n dd e m e r i t so ft h et w or o ie n c o d i n gm e t h o d so f j p e g 2 0 0 0 ，i e ，m a x s h i f ta n dg e n e r i cs c a l i n gb a s e dm e t h o d ，w ep r o p o s e d a m a x s h i rb a s e da l g o r i t h mu s i n gt r a n s i t i o nr e g i o n ，w h i c hm e e t st h en e e do fh u m a n v i s i o nf e a t u r e sa n dg e t sb e t t e rd e c o d e di m a g ei nt e r m so fo v e r a l lv i s u a le f f e c t m o r e o v e r , t h ep r o p o s e da l g o r i t h mi so fl o wc o m p u t a t i o n a lc o m p l e x i t ya n di s c o m p a t i b l ew i t hj p e g 2 0 0 0c o d es t r e a m k e y w o r d s ：i m a g ec o m p r e s s i o n ；w a v e l e tt r a n s f o r m ；s e tp a r t i t i o n i n gi nh i e r a r c h i c a l t r e e s ( s p i h t ) ；f r a e t a lc o d i n g ；r e g i o no fi n t e r e s t ( r o i ) c o d i n g 图1 1 图2 1 图2 2 图3 1 图3 2 图3 - 4 表3 1 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 - 9 图4 。1 0 图4 1 1 图4 1 2 图表清单 图像压缩系统结构图4 小波变换的时频平面的分辨率示意图9 空间方向树一1 7 8 种等距变换示意图2 4 图像块分类示意图2 5 l e n a 图像编码实验结果对比一3 2 l e n a 图像采用三种编码方法的p s n r 对比3 3 j p e g 2 0 0 0 编码器结构3 6 j p e g 2 0 0 0 解码器结构3 6 子带结构一3 8 j p e g 2 0 0 0 中的小波变换3 9 编码流程4 0 对分辨率等级m 层的分割4 1 一个子区的信息包结构4 2 j p e g 2 0 0 0 中的位移法4 3 滤波器子带问系数对应关系图4 5 r o i 和过渡区域映射一4 7 四幅图像在不同位率下的峰值信噪比4 8 0 2 b p p 位率时的l e n a 图实验结果对比4 9 表3 - 1l e n a 图像采用三种编码方法的p s n r 对比3 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金罂互些盔堂 或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：互良袭熏签字日期：五刁年月7 日 学位论文版权使用授权书 本学位论文作者完全了解盒胆王些太堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金筵王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 工久兹 签字日期：卯叮年6 月f 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 名：磁舻匕 签字帆哆年月日 电话： 邮编： 致谢 三年的研究生生活转瞬即逝，虽然时间短暂但却非常充实，令我终生受益。 首先感谢我的导师张佑生教授，感谢他对我的悉心栽培，感谢他对我耐心 的指导和无私的关怀，感谢他为我课题和论文的顺利完成付出了大量的心血。 张老师渊博的学术知识和严谨的治学态度使我受益匪浅，无论是思想上还是做 人的态度上张老师都对我产生了重要的影响，为我树立了一个值得我终生学习 的目标。 在课题的进行过程中我得到了习雅思、侯顺风、刘俊娜、江涛、洪沛霖、 黄忠、王臻等同学的热情帮助，在此表示感谢! 没有他们的协助，我无法顺利 的完成课题研究。 感谢图形图像实验室的胡敏老师、薛峰老师、王焕宝博士、江巨浪博士等 实验室的老师们对我的关心和帮助，在此表示衷心的感谢。 最后感谢我的父母，一直以来，他们对我的支持与鼓励，关心与爱护，永 远是我赖以进步的基石，是我不断前进的动力，感谢他们为我所付出的一切。 作者：王良燕 2 0 0 6 年5 月 1 1 引言 第一章绪论 随着现代信息技术的飞速发展，需要存储和传输的信息量越来越多，数据 的种类也是层出不穷，如何高效的存储和传输数据变得非常重要。图像是一种 应用相当普遍的数据，几乎每个领域都需要使用图像。在很多场合，图像可以 比文字更直观的表达意思和说明情况，因此图像是一种非常重要的数据。但图 像的存储容量要比文本文件大很多，尤其是未经压缩的位图文件。而且相当多 的图片数据都要在网络上传输，要想顺利地传输大容量的图片，就需要很宽的 信道。为减少图像存储容量和满足传输带宽的要求，必须对图像进行压缩。近 3 0 年来，图像压缩一直是非常活跃的研究领域。 2 0 世纪4 0 年代末，香农( s h a n n o n ) 提出的信息理论【lj ，这是图像压缩的基 础理论。多年来，人们研究出了多种信源编码方法，这些方法最初是应用于一 般的数据压缩上，后来被应用于数字图像。随着数字图像技术的迅速发展，图 像的编码方法受到极大的重视，逐渐形成了一系列的国际标准。目前应用最广 泛的图像压缩标准j p e g 2 1 就在很大程度上节省了图像的存储空间。为了实现更 多的功能和更高的压缩比，人们又制定了新的图像压缩标准j p e g 2 0 0 0 】。 j p e g 2 0 0 0 的核心技术采用的是离散小波变换，这一技术在图像压缩领域的贡献 是相当大的，基于小波技术的图像压缩方法是现代图像压缩领域的主流方向之 一。本文对小波图像压缩做了较全面的介绍，同时又结合其它压缩技术，提出 了改进方法，使压缩图像质量获得进一步提高。 1 2 图像压缩的信息理论基础 信息理论是图像压缩的重要理论基础，它给出了对符号序列进行无失真表 示所需要的比特率下界，所有的熵编码都不能超过这个下界。以下是对信息理 论的简要介绍【4 ，5 1 。 1 熵 在数字图像等信源中，表示信源的符号集是有限集。这种由有限符号集构 成的信源称为离散信源。离散信源可分为两种类型：如果信源的当前输出与以 前的输出是统计独立的，就称为无记忆信源：否则称为有记忆信源。 假设离散信源输出为符号瓤，它出现的概率为肌，则符号靴包含的信息( 或 称为自信息量) 为： l ( x i ) = l 0 9 2 二= - l 0 9 2 仇 ( 1 - 1 ) p 由n 个符号组成的符号集 z i ，x 2 ，靳) 构成的离散信源的每个符号的 平均自信息量为： h ( x ) = 一e p kl 0 9 2 仇 ( 1 - 2 ) k = l 这个平均自信息量h 称为信源的熵( e n t r o p y ) 。单位为比特字符。图 像熵描述了图像信源的平均信息量，即熵表示图像灰度级集合的比特数均值。 以下是通过观察信源得出的几点总结： ( 1 ) 平均码长，芝h ( m 。 ( 2 ) 如果所有i ( x k ) 为整数，则令， t ) = 1 ( x k ) ，可以使平均码长等于熵。一般 情况下，通过较好的码字分配，可以使平均码长接近熵。 ( 3 ) 对于非等概率分布符号集，一般更好的码字分配是不等长编码。 ( 4 ) 等概率分布有更大的熵，即更大的不确定性，需要更长的平均码字。 2 信源编码定理 信源编码是将每一种可能的输出从一个给定的信息源，映射成二进制数字 序列的技术。二进制数字称为“码位”。在理想情况下，这种映射具有这样的 性质：当码位是统计独立的，以相等的概率取0 或l 时，它可以传递最大可能 的信息量。如果映射是可逆的，可以用原信源输出的信息量确定码位的数目。 假设x 是离散无记忆信源的输出，删是其熵，编码后，平均每个信源要 用r 比特表示，定义p 为编码效率，则有： p2 阿r ( 1 3 ) 如果足与日( 相等，则达到理想情况，编码效果最佳；如果丑远大于脚， 则编码效果比较差。 如果采用定长码字编码，即信源的每个符号都采用相同长码字，则编码码 率不可能比日( 更低。若采用块编码，即将信源的k 个连续输出构成一个符号 块进行编码，可以提高编码效率，不过编码码率仍以朋为下限。由此可得定 长编码定理如下。 定理1 1 ( 定长编码定理) ：设x 是离散无记忆信源的输出，圄是其熵， 对x 能够准确解码的定长编码的码长r 满足矗日。 为了提高编码效率，变长编码对符号采用不同长度的码字分配，出现概率 大的符号分配较短的码字，出现概率小的符号则分配较长的码字。通过分析可 得出如下变长编码定理。 定理1 2 ( 变长编码定理) ：设x 是离散无记忆信源的输出，同是其熵， 信源有有限的输出符号，可以构造一个符合前缀条件的唯一可解的变长编码， 其平均码长r v 满足h c x ) _ r ，s 日+ 1 。 从该定理可以看出，变长编码的平均码长大于等于信源的熵，总可以找到 一个编码，使码长小于信源熵加1 。用块编码方式同样可以增加变长编码效率。 2 设无记忆信源中每k 个符号组成块进行编码，则每个符号的平均码长满足月 s r ，s 删+ 1 k 。 由此可见，不管是定长编码还是变长编码，码率都不可能低于信源的熵， 变长编码比定长编码码率更接近于信源的熵。块编码可以提高二者的编码效率。 3 图像编码的评价指标1 5 ，6 】 ( 1 ) 压缩度量 设原始图像的像素个数为m x n ，每个像素用b 位有符号或无符号整数来表 示，因此，描述原始图像像素值需要m x n x b 位。压缩后的位流用c 表示，位流 长度为i 。由此定义压缩比p ，为： n ：m 可x n j 广一x b ( 1 4 )n 2 r 另一种描述压缩程度的标准是比特率，用b p s ( 位每像素) 表示，为： b p s ：且( 1 5 ) 对有损压缩来说，比特率是对图像压缩系统更有意义的性能度量。 ( 2 ) 质量度量 设原始图像的像素个数为m x ? l ，灰阶为m ，竹) ( i = 1 ，2 ，所；j = 1 ， 2 ，万) ，压缩后重构图像的灰阶为f o ，肋。则图像质量的评价指标有如 下几种： 均方误差： m s e 2 去善荟旷( “) 一，( “) 】2 ( 1 - 6 ) 规范化均方误差： n m s e ：m s _ e ( 1 - 7 ) o 。| 其中 q 2 去否荟2 ( f ，力 o - s ) 对数信噪比： s n r = 1 0 l o g 舭7 一= - 1 0 1 0 9 n m s e ( d b ) ( 1 - 9 ) 峰值信噪比： ：10logi25忑52psnr (db)(1-10) = 1 0 1 。g 而( 这些评价标准中，最常用的是峰值信噪比p s n r t 7 1 。一般情况下，当p s n r 超过3 0 d b 时，人眼就很难分辨出重构图像与原始图像的差别。不过以上都只 是客观评价准则，并不能很全面的反映图像的质量，所以有时还要通过主观准 则来评价图像。这种主观评价方法是选择一组评价者给图像打分，对这些主观 打分进行平均获得一个主观评价分，以这个分数的高低来衡量图像的质量。 10 3 图像压缩的基本思想 图像压缩的根本思想就是去除图像中存在的冗余。冗余也就是数据问的相 关性，包括空间冗余、信息冗余、视觉冗余、结构冗余等。冗余的存在，使我 们能根据给出的一部分数据预测出相邻的数据。 各种冗余都和图像的统计特性有关，无误差表示图像样本值所需要的平均 位数取决于图像的统计性质。如果一幅图像中的相关性很强，只需少数样本值 就能提供足够的信息，以很高的概率预测其余样本，那么就可以实现很高的压 缩率。对于无损压缩来说，由于要求压缩图像没有任何信息损失，而在高压缩 率情况下难以进行十分准确的预测，所以压缩率一般都不太高。 在大多数情况下，有一定的信息损失还是可以接受的。因为，与样本值相 联系的有些信息可能是无关紧要的，甚至是噪声信号，而有用信息的少量损失 对图像视觉质量的影响也很小。因此，有损压缩的应用更为普遍。有损压缩就 是在允许的失真水平上使表示图像所需要的位数最少。有损压缩通常都是通过 变换编码，将数据转换成另一种数学基来表示。这种表示能使数据间的相关性 变得更明显，从而更有利于去除相关性。此外，通过量化还可以使大部分不相 干数据接近零而被忽略，使压缩率得到进一步提高。 图像压缩系统的结构包括两部分：编码系统和解码系统。编码系统包括映 射变换、量化和熵编码三个步骤【8 】，如图卜1 所示。我们把映射变换、量化和熵 编码统称为编码器，与之相对应的熵解码、反量化、反映射变换称为解码器。 i i ： 解码系统 ： - - ：一一一一一- - 一o 图1 1图像压缩系统结构图 不管是编码系统还是解码系统，包含的三个步骤都是相互联系、相互制约 4 的。在编码系统中，映射变换是为了改变原始图像数据的特性，使其更有利于 压缩；量化是用有限的符号集来表示映射后的图像；熵编码是为量化后输出的 每个符号分配二进制比特流。因此，三个步骤是共同实现数据压缩的。解码系 统就是编码的逆过程，它的熵解码、反量化及反映射变换是和编码系统中的三 个步骤相互对应，缺一不可的。所以编码系统和解码系统都应该被看作一个整 体。 1 4 图像压缩的基本方法 按编码原理分，信息编码可以划分为预测编码、变换编码、信息熵编码、 予带编码、分形编码、结构编码和基于知识的编码【9 j 。 预测编码是对统计冗余进行压缩，即消除图像像素之间的相关性。对一个 像素用与其相邻的并且已经编码的像素按照某种模型来预测，最后编码的数据 是量化后的差值。 变换编码的基本思想是通过变换来消除图像中存在的高度相关性。它是将 时域图像变换到频域上进行处理的编码方法。变换后在频域上的信息是按照频 谱的能量与频率分布排列的，其系数具有比较低的熵值。首先对空域图像做线 性变换得到一组变换系数，然后对这组系数进行量化、编码和传输。 信息熵编码是根据信息熵原理，用短的码字表示出现概率大的位串或像素， 常用信息熵编码有h u f f m a n 编码 1 0 l 、算术编码【l 和行程长度编码。 子带编码是将图像数据变换到频率域后，按频率分频带，然后用不同的量 化器进行量化，从而达到最优组合。子带编码利用滤波器组，通过重复卷积的 方法，经过取样将输入的信号分解为高频和低频分量，然后对高频和低频分量 进行量化和编码。 分形编码 1 2 1 是利用图像内部子块之间的自相似性，在编码时将图像分解为 若干分形子图，提取其迭代函数系统( i f s ) 代码，然后编码传输这些迭代函数系 统代码，在恢复时由该代码重构各个子图。 结构编码首先将图像纹理、边缘和轮廓结构特征提取出来，然后分别对它 们进行编码。解码时，根据这些结构信息进行合成，从而恢复出原始图像。 基于知识的编码在编码时通过各种分析手段，建立一定的模型来描述待编 码的图像，例如人脸建模，同时提取模型的特征与状态参数进行编码，解码时， 依据这些参数，利用模型及相关知识恢复原始图像。 根据解码后数据是否可以完全恢复，图像压缩可以划分为无损编码和有损 编码【6 1 。 无损压缩是指被压缩的数据进行解码后恢复的数据与原始的数据完全相 同，无损编码的算法删除的仅仅是冗余的信息。就目前的技术，无损压缩算法 般可以把普通文件的数据压缩到原来的1 2 至1 4 。常用的无损数据压缩有 如下几种： ( 1 ) 行程编码：把连续重复的字符串用两个( 或三个) 字节来代替。 ( 2 ) 字典编码；用以前处理过的数据来表示编码过程中遇到的重复部分， 或者从输入的数据中创建一个短语字典，如果编码过程中再遇到该短 语，则用字典中短语的“索引号”来表示。字典编码的算法有l z 7 7 ， l z s s ，l z 7 8 和l z w 。 ( 3 ) 香农一范诺编码：根据变长最佳编码定理来确定字符编码的长度。按照 概率的大小排序，然后将字符分成两组，每组的概率和大体相当。再 从树根到树叶构造二叉树。 ( 4 ) 哈夫曼编码：和香农一范诺编码一样，是一种变长编码方法。它根据字 符出现的概率，用较短的代码代表频率高的字符，用较长的代码代表 频率低的字符。也是通过构造二叉树来求得编码，但二叉树是从树叶 到树根构造的。 ( 2 - 4 ) 式中，y 表示共轭；口越大，( 丢 越宽，时域分辨率越低；反之，4 越小，( 丢 越窄，时域分辨率越高。 公式( 2 4 ) 是小波变换在时域内的表示，它在频域内的另一个等价定义为： s w t x ( a ，6 ) = 苦竺p ( m ) 矿( a m ) e ，“d o ) ( 2 5 ) 2 石。 当a 增加时，痧脚) 的中心频率低移，频带变窄，小波变换抽取的是x ( f ) 在低频窄带的成分；当口变小时，矿( 口m ) 的中心频率高移，频带变宽，小波变 换抽取的是工( 0 在高频较宽频带内的成分。 ， 图2 - 1小波变换的时频平面的分辨率示意图 所以小波变换具有如下时频特性： 口增加时，国降低，j f ，( 三 变宽，时域窗口变宽，能够观测更长的时间区域， 同时t p ( a o ) 变窄，在频域能观测更窄的频域窗，且中心频率向低频移动。 n 减小时，国增大，玎丢) 变窄，时域窗口变窄，观测更短的时间区域，同 时矿0 m ) 变宽，在频域观测更宽的频域窗，且中心频率向高频移动。 2 1 2 离散小波变换 连续小波变换存在信息冗余，不太适合计算机处理，通常都要对其离散化。 离散包括尺度离散化和位移离散化。尺度离散化即对式( 2 3 ) 中的尺度因子a 只 按下式取值：口= 0 0 j ( o l , j z ) ；位移离散化即对式( 2 - 3 ) 中的位移因子b 只按下式取值：b = k a o b o ( o 嘞 ，分解方程为： 鲰“= h ( - 2 k ) 口。o l d “1 = g ( 。一2 i ) 4 。f 2 16 ) h j 一般合成公式为 ( z 。= = h ( - 2 k ) 口t + 1 + g ( 。- 2 k ) d k + 1 ( 2 ，1 7 ) 分解公式( 2 1 3 ) 相当于先对输入序列同滤波器的冲击响应卷积，再进行一 次亚采样，只保留偶数样点。合成公式( 2 1 4 ) 相当于先对输入序列进行一次插 值，再通过滤波器。这组计算离散小波变换和反变换的分解和合成公式( 2 1 6 ) 与( 2 - 1 7 ) 就称为m a l l a t 算法。 2 1 5 双正交小波变换 正交基虽然是一种理想的小波基，但除了h a r r 基外，所有的正交基都不具 有对称性，这在图像编码时会引入相位失真，因此需要一种具有对称性质的小 波基。双正交小波基就具有这种性质。 设存在两个对偶的母小波( f ) 和矿( f ) ，若满足如下互正交关系 缈。，矿) = 如 ( 2 一1 8 ) 其中聊，珂，_ ，f z ，相应的尺度函数满足 ( 妒。，死，) = 以 ( 2 1 9 ) 则称( f ) 和矿( f ) 构成双正交小波。 构造双正交小波基的滤波器系数要满足如下约束条件： ! ( z - i ) ? 譬) + 弦1 ) 置( 曹22 ( 2 - 2 0 ) j 5 ( 一z 一) i ( z ) + 营( 一z 。) 鸯( z ) = 0j 由下式可构造出尺度函数和小波函数： ( 2 ) 2 老6 ( ) 庐( 功) 歹( 2 国) = i 而( 国) 歹( 国) 矿( 2 国) = 苦宫( 国) 矿( 国) 二 痧( 2 m ) = i 季( 国) 旷( 国) 二 ( 2 2 1 ) 2 1 6 提升和整数小波变换 1 提升( 1 i m n g ) 小波变换方法【1 9 1 一般的小波变换是采用傅立叶变换作为主要分析工具的，通过伸缩、平移 一个母函数构成小波基。s w e l d e n s 等人放弃了这种传统方法，提出了一种应用 范围更广、计算速度更快的新型小波变换方法一一提升小波变换。 提升小波变换方法具有如下的优点： ( 1 ) 速度快，一般通过提升方法可以达到比m a l l a t 算法快2 倍的离散小波 分解。 ( 2 ) 使用提升方法，正向和反向小波变换的结构完全一致，只有正负号的差 别。 ( 3 ) 提升小波变换的描述非常简单，不需要使用傅立叶变换。 ( 4 ) 提升方法可以实现完全的同址运算，这一点与f f t 类似。 提升小波变换的基本过程分为三步：分裂、预测和更新。 第一步分裂：将给定的数据集a o 分解成两个集合a 1 和c l 。分解方法有很多种， 采用不同的方法就相当于采用不同的小波基，最常用的是以惰性小波作为第一 级分解。惰性小波变换就是将奇数点集合母z “z 定义为a 1 ，将偶数点集合s j , 2 t 定义 为o l ，即 s , 2 l 2 e v e n ( a o ) 8 ，2 1 + 1 = o d d ( a o ) 第二步预测：用a l 预测c l ，再用预测误差形成新的c l ，即 c l ：= c 1 - p ( a 1 ) 这里的p 是一个与数据结构无关的预测算子，它是独立于数据集的一个确定的 运算形式。“：= ”表示对变量的更新。对于惰性小波变换，就是先将p 滤波器作 用于偶信号上得到奇信号的预测值p ( 鼽力，再将该预测值与原奇信号鼽爿相减得 到奇信号的预测误差西- 1 0 预测过程的表达式如下： 西1 = s j ，2 l + 1 一p ( s j ，2 t ) 当原始的cj 完全可由a l 预测，且预测算子也是理想的预测器时，新的c l 是全零序列；当理想预测不存在，但原始c l 和a l 相关性较大时，通过预测，使 新的c l 具有很低的能量分布。 a l 可以进一步分解成a 2 和c 2 ，a 2 可以进一步分解成幻和c 3 ，直到指定 的分解级数n ，从而形成系数集 a n ，c 。，a l ，c l 。 预测的目的主要是为了消除第一步分裂后留下的冗余，给出更紧致的数据 表示。 第三步更新：由于第2 步预测生成的信号c l 在某些整体性质上并不和原始 数据一样，需要采用更新的过程。因此，定义一个算子u ，通过对c 1 作预测以 生成更好的子数据集，并保持町的一些特性。更新过程写为 a l ：= a l + u ( c o 为了使正、反变换一致，需要定义一个标量运算器q ( a 1 ) ，由它计算一个序 列的某个全局量，例如均值。在当前级，更新过程要求 q ( a 1 ) = q ( a o ) 在由u ( c 1 ) 对a i 进行更新后，要求保持上式成立。 总结上述过程，可得出每一级分解过程的表示如下： a j + l ，c j + 1 ) s p l i t ( a j ) l e , j + l # c j + 1 。p ( a j + 1 ) ( 2 - 2 2 ) a 譬a j + l + u ( c ) j 相应的反变换过程为： a i + 1 - a j + 】一u ( c j “) j c 州- c j + l + p ( a j + 1 ) ( 2 - 2 3 ) a j j o i n ( a j + l ，c ) l 2 整数小波变换【2 0 ，2 1 1 不管是一般的小波变换还是提升小波变换，变换系数一般都是实数值，即 使待分析的信号本身是整数序列，相应小波变换系数也是实数。这一点对图像 压缩是不太有利的。因为实数值的存储要占用更多的空间，而且由于计算精度 有限，需要舍弃某些位，这样就难以进行无失真编码。由于数字图像一般都是 用位数比较低的整数表示，最常用的是8 位，我们也非常希望图像矩阵的小波变 换是整数矩阵，也就是希望有一种“整数一一整数小波交换”将整数序列映射 为整数小波系数，并且这种映射是可逆的。具有这种性质的小波变换称为整数 小波变换。 得到整数小波变换最简单的方式是建立在提升方法基础上的整数小波变 换。这种整数小波变换具有变换可逆、整数存储及只有加减和移位运算等优点。 用提升的方法，很容易构造一般的整数小波变换。式( 2 2 4 ) 给出了基于提升方 法的整数小波变换的基本公式： 让d j - 。i 鸹= $ j 埘, 2 1 + 一1 - i n t p ( s 。j , 2 t 】) i n t u ( d j1 ( 2 - 2 4 ) s 川= j m 厂一1 ) 】f 7 式中i n t 为四舍五入取整运算。 3 两种常用的小波变换 1 4 ( 1 ) d a u b e c h i e s ( 9 ，7 ) 小波变换 采用d a u b e c h i e s ( 9 ，7 ) 小波基的提升小波变换方法描述如下： y ( 2 n + 1 ) - x d ( 2 n + 1 ) + ( 口i x _ ( 2 n ) + x ( 2 n 十2 ) 】) v ( 2 n ) + - x _ ( 2 n ) 十( p 【y ( 2 n 1 ) 十y ( 2 n + 1 ) 】) y ( 2 n + 1 ) 一y ( 2 n + 1 ) + “【y ( 2 n ) + y ( 2 n + 2 ) 】) y t ，则称它是重要的；否则是不重要的。如果以z ，为根的树上 包括蜀，在内的所有系数都是不重要的，则称该树为零树，弼，称为零树根。如 果墨。，是不重要的，但其至少有一个子孙是重要的，则称点( f ，) 为孤立零点。 e z w 是一种嵌入式编码算法。所谓嵌入式编码就是将待编码的信息按重要 性递减的形式排序，从最重要的信息开始编码，当产生的码流达到目标码率或 满足一定失真度要求时，即可结束编码；同样，对于给定的码流，解码器也能 根据要求的解码码率随时结束解码，并得到这时的恢复图像。e z w 的嵌入式特 性是通过重要性排序和逐次逼近量化s a q ( s u c c e s s i v ea p p r o x i m a t i o n q u a n t i z a t i o n ) 来实现的。具体做法是，用组阈值乃，乃，1 顺序判别系数的 重要性。其中疋= 及t 2 ，m l o g2t o ，初始阂值而按条件m a x 托，f 2 取值。由于这组阈值是递减的，因此判别后的系数在总体上也按重要性 递减的顺序排列。 在e z w 编解码过程中要用到两个列表：主表和副表。主表中存放的是编 码中不重要的集合或系数；而副表中存放的是编码的有效信息，输出为各重要 系数的二进制值。编码分为主、副两个过程：在主过程中设定阙值为取，对主 表进行扫描编码，若是重要系数，则将其幅值加入副表中，然后将该系数在数 组中置为零。在副过程中，对副表中的重要系数进行细化，对阈值疋来说，重 要系数所在区间的为 t k , 2 t k 】，若副表中的重要系数位于区间的前半部分，则用 符号0 表示，否则用符号1 表示。编码在两个过程中交替进行，在每个主过程 前将阈值减半。 1 6 零树结构是一种描述图像经过小波变换后重要系数位置的有效方法，但是 e z w 算法中依然存在一些问题1 2 6 1 ： ( 1 ) 由于编码时形成多棵零树，因而要多次扫描图像，造成效率很低，而且 每一棵树必须在前一棵树形成之后才能形成，所以也很难用并行算法优 化。 ( 2 ) 对所有的频域进行等同重要度的编码，不能充分利用小波变换的特点。 ( 3 ) 在一棵零树中包含的元素越多，则越有利于数据压缩，在e z w 算法中 存在这样的树间冗余。 ( 4 ) 通过对小波系数的分析发现，在同一子带中相邻元素间有一定的相关 性，尤其在高频子带存在大量的低值元素，而e z w 算法并没有充分利 用这种相关性。 2 2 2s p i h t 编码算法 实际研究表明，e z w 算法中存在编码冗余。当某个节点的小波系数是重要 的，而它的所有子孙节点的系数都不重要时，e z w 编码的效果就不是很好。 s p i h t 算法是迄今最好的零树小波改进算法之一。它吸取很多零树的思想，在 零树的基础上引入了空间方向树和集合的概念，其目的也是利用方向树来有效 的表示重要系数，通过对树的划分，将尽可能多的不重要系数集中在一个子集 中，用一个单位符号来表示，从而实现高效压缩。空间方向树如图2 2 所示，坐 标集合定义如下： o ( i ，) ：节点( ，) 的直接子节点的坐标集合； 工( t _ ，) ：节点( ，) 的非直接子节点的坐标集合； d ( f ，) ：节点( ，) 的所有后代节点的坐标集合，即 d ( t _ ，) = o ( ，) + 工( ，) ； 日：所有空间方向树的根节点( 金字塔最顶层的所有节点) 的坐标集合。 文 主r h 一 4 卅 1 刊 圳啪士人 i l l l o + 1 d 划 兰刮 h h i 图2 - 2 空间方向树 相对某个阈值来说，如果集合【，中至少有一个节点( ，) 的系数石，是重要 1 7 的，则这个集合就是重要的；否则是不重要的。定义s ( 作为u 是否重要的 标志位，定义如下 蹦耻器囊陋一净r ( 2 - 2 7 ) ，为当前阂值。当集合中只包含一个系数的坐标时，即盯= ( ( i , j ) ，时，简写为 ( f ，) 。 在实际操作中，信息被组织在三个表中： 工胳：不重要集合表 上伊：不重要系数表 l s p ：重要系数表 三伊和三卯表中存放单个系数的坐标矢量，l i s 表中存放表示集合d ( i ，) 或 工( _ ，) 的坐标矢量，分别标记为类型4 和类型召。算法依然采用逐次逼近的 量化方法进行多次扫描。具体扫描过程如下： ( 1 ) 初始化： 计算挖；o o g ：( m a x i 置i ) j ，r = 2 4 。 将l s p 清空，将金字塔顶层的所有系数坐标放入三z p ，将项层除l l n 区域外的所有系数坐标标志为a 类型放入l i s ，即： l j p = l l n + l h n + h l n + h h n l i s = l h n + h l n + h h n ( 2 ) 分类扫描： 使用阈值丁，按式( 2 2 7 ) 扫描工伊和l i s 两个表，按小波系数的重要 性对其坐标排序，具体步骤为： 首先检查三伊： 依次判断每个坐标( f ，) ，输出( f ，) 。如果& ( f ，) = 1 ，即( f ，) 的小波系数搦，是重要的，就接着输出蜀，的符号位( 正为1 ，负 为0 ) ，同时将( f ，) 移入l s p 。 然后检查l i s ： 依次检查每个a 类树根坐标的d ( f 力，输出品p ( 力) 。若 岛( d ( i , j ) ) = 1 ，即d ( t _ ，) 是重要的，就将d ( t j ) 分裂成d ( i ，j ) 和l ( _ ，) 。然后分别检查o ( - ，) 和( j ) ： a ) 对每个( 屯，) 0 ( f ，_ ，) ，输出( tz ) ，如果晶( k ，) = l ，即凰i 是重要的，将( k ，) 放入工卵，并输出1 的符号位( 正为1 ，负 为0 ) ；如果( t ，) = 0 ，即凰，是不重要的，就将( t ，) 放入三妒； b ) 若工( j ) 不为空，将坐标( f ，) 标志为召类型移到l i s 末尾；否 则，将( f ，) 从三坶中删除。 依次检查每个曰类树根坐标的三( j )