（计算机应用技术专业论文）基于分形和小波理论的图像压缩方法.pdf

大连理工大学硕士学位论文 摘要 近些年来，基于分形理论和小波变换的图像编码技术正逐步显示出它们的优越性， 其中小波变换已经被j p e g 2 0 0 0 国际标准采用。这些理论和技术各有特点，能够在不同 程度上解决图像压缩领域的一些基本问题，同时分形编码方法和小波编码方法之间具有 密切的联系，将它们结合起来可以更好实现图像编码。本文在已有分形理论和小波变换 理论基础上研究并改进了几种图像编码方法，具体研究内容如下： ( 1 ) 传统的分形图像编码是一种不对称编码方法，由于其编码时间太长而影响了它 在图像编码领域的广泛应用。本文在现有无搜索分形图像压缩算法的基础上，通过引进 一种改进的灰度级变换来更好的发挥无搜索分形图像压缩算法的优势，改进的灰度级变 换在相同的条件下可以降低值域块和定义域块的匹配误差，从而减少四叉树分割的等 级，降低了待编码值域块的数量，在减少分形编码的同时提高了图像的压缩质量。 ( 2 ) 由于图像经过小波金字塔分解后，能量系数主要集中在图像分解的低频子图像， 故对低频子图像的有效编码可以极大的提高编码器的总体性能。本文结合分形图像压 缩，利用分形图像压缩技术来编码图像小波分解的低频子图像，使用等级树集合分裂算 法( 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 lt r e e s ，简称s p i h t ) 来编码分形编码的误差子图像和其 余高频子带的系数。由于低频子图像的尺寸比较小，故本文算法极大的减少了分形编码 的时间。同时相比等级树集合分裂算法，由于用较少的压缩预算编码了图像的主要能量， 故可以用更多的预算来编码误差子图像和其余高频子带的系数，从而更好的保存了图像 的细节，提高了图像的解码质量。 ( 3 ) 等级树集合分裂算法作为小波编码领域的一个经典算法，吸引了许多学者对其 进行改进，本文通过分析和研究等级树集合分裂算法的缺点和它编码过程中的特点，提 出了一种基于块的空间方向树算法，并且通过调整编码过程中各信息的输出顺序来提高 图像的解码质量。本算法可以大大的减少等级树集合分裂算法的内存需求，并提高图像 解码质量。 关键词：分形图像压缩；迭代函数系统；小波；等级树集合分裂；图像压缩 大连理工大学硕士学位论文 i m a g ec o m p r e s s i o nb a s e do nf r a c t a la n dw a v e l e t a b s t r a c t t h e s ey e a r s i m a g ec o d i n gm e t h o d sb a s e do nf r a c t a lt h e o r i e sa n dw a v e l e tt r a n s f o r i l la r c s h o w i n gi t sa d v a n t a g e s ，i nw h i c hw a v e l e tb a s e di m a g ec o d i n gm e t h o d sh a v eb e e na d o p t e db y j p e g 2 0 0 0a si t sc o r ea l g o r i t h m t h e s et h e o r i e sa n dt e c h n o l o g i e sh a v et h e i ro w n c h a r a c t e r i s t i c s ，a n dt h e yc a ns o l v ep r o b l e m si ns o m ee x t e n t i nt h em e a n w h i l e ，f r a c t a li m a g e c o d i n gm e t h o d sa n dw a v e l e tb a s e di m a g ec o d i n gm e t h o d sh a v es t r o n gc o r r e l a t i o n i fw ec a n m a k ef u l lu s eo ft h ec o r r e l a t i o n ，w ea r ea b l et os o l v ea b o v ep r o b l e m sb e t t e r i nt h i sp 印e r ，t h e a u t h o rh a sd o n es o m er e s e a r c h e so fi m a g ec o m p r e s s i o nb a s e do nf r a c t a la n dw a v e l e t t r a n s f o r i l l t h ew o r k sm a i n l yc o n t a i nt h r e ep a r t s ： ( 1 ) t h ef r a c t a li m a g ec o d i n ga l g o r i t h mi sa ni r r e v e r s i b l ec o d i n gm e t h o d i t se x h a u s t i v e i n h e r e n te n c o d i n gt i m eh a sl i m i t e di t sa p p l i c a t i o n si nt h ei m a g ec o d i n gf i e l d i nt h i sp a p e r ， b a s e do nt h en os e a r c hf r a c t a 】i m a g ec o d i n ga l g o r i t h m t h ea u t h o ri n t r o d u c e sam o d i f i e d g r e y l e v e lt r a n s f o r mt of u l l ye x p l o i tt h ea d v a n t a g e so ft h en os e a r c hf r a c t a li m a g ec o d i n g a l g o r i t h m t h em o d i f i e dg r e y l e v e lt r a n s f o r mc a ng r e a t l yr e d u c et h em a t c h i n ge r r o rb e t w e e n t h er a n g eb l o c k sa n dt h ed o m a i nb l o c k s t h u s i tc a nr e d u c et h el e v e lo ft h eq u a d t r e e p a r t i t i o n i n ga n dt h en u m b e ro ft h er a n g eb l o c k s 明kp r o p o s e da l g o r i t h mc a nr e d u c et h e e n c o d i n gt i m ew h i l eg e tal i t t l eg a i n sf o rt h er e c o n s t r u c t e di m a g e ( 2 ) t h ei d e ab e h i n dm o s th y b r i df r a c t a lw a v e l e tc o d e r si st oa p p l yad i s c r e t ew a v e l e t t r a n s f o r mt ot h ei m a g ea n dt l l e nu s ef r a c t a lm e t h o d smt h ew a v e l e td o m a i n i ti sw e l l - k n o w n t h a tt h ew a v e l e te n e r g yc o n c e n t r a t i o ni sl o c a t e dp r i m a r i l yi nt h el o w e s tf r e q u e n c ys u b b a n d t h u s ，i ft h el o w e s tf r e q u e n c ys u b b a n di se n c o d e dm o r ee f f e c t i v e l y ，t h ee n c o d e rp e r f o r m a n c e c a nb ee n h a n c e d i nt h i sp a p e r , t h ea u t h o ru s e st h ef a s tf r a c t a li m a g ec o d i n gm e t h o dt oe n c o d e t h el o w e s ts u b b a n da n du s e st h es e tp 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 ) t oe n c o d et h e e r r o ro ft h ef r a c t a lc o d i n ga n do t h e rs u b b a n d s d u et ot h es m a l ls i z eo ft h el o w e s ts u b b a n d a n dt h ef r a c t a ld e c o d i n gs p e e d ，t h ep r o p o s e dm e t h o dc a r lg r e a t l yr e d u c et h ee n c o d i n gt i m eo f t h ef r a c t a lc o d i n g c o m p a r ew i t ht h es p i h t , t h ep r o p o s e dm e t h o d sc a nb e t t e rm a i n t a i nt h e d e t a i l so ft h ei m a g eb e c a u s ei tc a ns e tm o r eb i t b u d g e tt ot h es p m t t h u s ，t h er e c o n s t r u c t e d i m a g eq u a l i t yi se n h a n c e d ( 3 ) t h es p i h ta l g o r i t h mh a sb e e nab e n c h m a r ki nt h ei m a g ec o d i n gf i e l d i nt h i sp a p e r ， t h ea u t h o ra n a l y z e st h ed i s a d v a n t a g e sa n dt h ec h a r a c t e r so ft h es p i h t ，a n dt h e np r o p o s e sa m o d i f l e da l g o r i t h mb a s e do nt h eb l o c ks p a c eo r i e n t a t i o nt r e ea n dt l l ea d j u s t m e n to ft h eo r d e r o ft h eo u t p u ti n f o r m a t i o n t h ep r o p o s e da l g o r i t h mc a nr e d u c et h er e q u i r e m e n to ft h em e m o 巧 - i i i - 基于分形和小波理论的图像压缩方法 a n de n h a n c et h eq u a l i t yo ft h e r e c o n s t r u c t e di m a g ei nt h em e a n w h i l e k e yw o r d s ：f r a c t a li m a g ec o m p r e s s i o n ；i f s ；w a v e l e t ；s p i h t ；i m a g ec o m p r e s s i o n i v 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目一蕉鲨鱼虫垒坐型：超丝丝塑鱼篮屋蕴查巨 作者签名： 导师签名： 日期：醚年日 日期：砌盎年业月芝互日 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 基殳龛谧尘：退塑丝竖1 焦屋盗查窿： 作者签名： 2 柚一一一 日期：j 塑竺红年上月j 厶日 大连理工大学硕士学位论文 引言 随着计算机技术、现代通信技术的飞速发展，人类社会正逐步迈入信息化时代，在 生活和工作中每天都有大量的信息用数字进行存储、处理和传送，如办公自动化、医学 图像及卫星遥感图像处理等。尤其是近几年，随着多媒体技术、互联网技术等新技术的 迅猛发展，许多信息都是以图形、图像形式存储的，它所面临的一个关键问题就是如何 有效地存储、传输图形图像数据，其中数据压缩方法比起数据的存储和数据传输具有更 为突出的实用价值和商业意义。因此，图像数据作为其中数据量最大的一类，在满足一 定图像质量要求的前提下如何高效地对图像进行压缩，并且保持较好的图像质量，这是 图像编码人员努力研究的重点【l - 3 】。 分形的概念是由数学家m a n d e l b r o t 于1 9 7 5 年提出的，他把分形定义为“一种由许 多个与整体有某种相似性的局部所构成的形体 。分形概念的提出以及分形几何学的创 立为描述客观世界提供了更准确的数学模型。2 0 世纪8 0 年代末，b a r n s l e y 及其研究小 组提出了用迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，简称i f s ) 对图像进行压缩编码的思 想1 4 。7 j 。基于分形的图像编码方法实质是对图像中的一个或者多个相对大的部分施行压 缩变换来逼近图像的每一部分。b a m s l e y 提出的算法是一种人工干预的半自动方法，这 种方法并未取得很大的成效。1 9 9 0 年，他的学生j a c q u i n 提出了一种基于局部迭代函数 系统( p a r t i t i o n e di t e r a t e df u n c t i o ns y s t e m ，简称p i f s ) 的可以真正自动实现图像压缩的算 法一分形块编码算法f 8 】，使分形编码从实验室研究走向应用成为可能。分形编码是一种 不同于以往基于信源理论编码的图像压缩方法，由于它引入了局部和全局相关去冗余的 新思想，突破了传统图像压缩方法的局限性，具有较大的潜力。但是传统的分形编码算 法因其编码非常耗时，导致其一直难以实际应用，为此，许多学者在如何加快分形编码 速度方面进行了广泛深入的研究。 由j a c q u i n 提出的传统分形图像压缩是通过发掘图像的自相似性去除冗余，实现压 缩，它是在空间域上进行的基于块的编解码方法，其理论依据，同时也是分形图像压缩 技术的核心是拼贴定理。一幅图像用使图像近似不变的压缩仿射变换( 由一组刻画局部 自相似性的压缩仿射变换组成，即迭代函数系统) 的量化参数来表达，只需存储压缩变 换的量化参数而不是整幅图像，而存储仿射变换量化参数的比特数大大低于储存原始图 像的比特数，因此实现了图像数据的高倍压缩。解码是新颖的快速迭代过程，表达图像 的变换是压缩的，b a n a c h 不动点定理保证变换的不动图像是存在的且是唯一的，可以从 任何初始图像迭代生成。 近十年来，小波图像编码技术得到了迅速的发展和广泛的应用，并日臻成熟。1 9 8 9 基于分形和小波理论的图像压缩方法 年，m a l l a t 首先将小波变换用于多分辨率图像的描述f 9 】，之后小波变换的编码方法迅速 成为图像压缩领域的研究热点之一，其基本思想是把图像进行多分辨率分解，分解成不 同空间、不同频率的子图像，然后再对子图像进行系数编码。系数编码是小波变换用于 图像压缩的核心，压缩的实质是对系数进行量化压缩。由于小波变换的特点，图像经过 小波变换后能量主要集中在低频部分，而高频部分经过量化后系数大部分为零，这一特 性使得对图像进行压缩成为可能。如今，在视频压缩国际标准m p e g - 4 以及静止图像压 缩标准j p e g - 2 0 0 0 中，小波算法已经成为核心算法【1 0 1 。 基于小波的分形图像编码技术是最近出现的一种新兴方法。近年来，一些学者不断 地在研究使用分形编码的一些方法来发掘和利用图像经小波变换后所表现出来的相似 性l l l 明。1 9 9 5 年，r i n a i d 和c a l v a g n o 利用分形图像编码中的分形匹配方法，实现了用 低分辨率子带图像来进行同方向高一级分辨率子带图像的预测【1 3 1 。1 9 9 8 年，d a v i s 把零 树的概念引入到分形图像编码【1 4 】，并把分形图像编码中的相似块和图像块扩大为相似树 和图像树，从而使得相似块与和图像块之间的分形匹配转化为相似树与图像树之间的分 形匹配，取得了很好的压缩效果。 本文在前人工作的基础上，以分形理论和小波理论为基础，在提高分形图像压缩的 编码速度方面，对无搜索分形图像编码方法以及分形小波相结合的混合图像压缩方法进 行了重点研究，主要工作如下： ( 1 ) 探讨了分形理论及其性质，以及它在图像压缩算法中的应用。 ( 2 ) 分析了传统分形编码算法的特点和不足，给出了一种改进的快速分形图像编码 方法，并给出了具体实验结果和分析。 ( 3 ) 研究了分形编码方法和小波变换的特点，将分形编码与小波变换相结合，发挥 两种技术的优势，提出了一种改进的分形小波编码方法并进行了试验仿真和结果分析。 ( 4 ) 研究了现有基于小波的图像压缩方法，在等级树集合分裂算法的基础上提出了 一种改进的小波编码方法，并进行了试验仿真和结果分析。 本文章节安排如下所示： 第一章简要地介绍了数字图像压缩的一些基础知识，包括图像数据冗余，图像压缩 系统的组成，图像压缩的类型以及图像压缩的质量判别标准。 第二章介绍分形图像编码和小波图像编码的基础知识，主要包括分形图像压缩的数 学基础，分形图像压缩的基本原理和实现算法，分形图像压缩的缺点，以及小波分解和 小波变换在图像压缩中的应用等。 第三章介绍了现有的灰度级变换以及基于改进灰度级变换的无搜索分形图像压缩 方法。 大连理工大学硕士学位论文 第四章介绍了y f i s h e r 的分形图像压缩算法和等级树集合分裂算法以及本文提出 的分形和小波图像相结合的改进混合图像压缩算法。 第五章介绍了改进的等级树集合分裂算法及试验结果与分析。 最后是总结与展望。 基于分形和小波理论的图像压缩方法 1 数字图像压缩的基本原理 图像压缩所解决的问题是尽量减少表示数字图像时需要的数据量。减少数据的基本 原理是除去其中多余的数据。以数学的观点来看，这一过程实际就是将二维像素阵列变 换为一个在统计上无关联的数据集合。这种变换在图像存储或传输之前进行。在以后的 某个时候，再对压缩图像进行解压缩来重构原图像或原图像的近似图像。 1 1图像数据冗余 “数据压缩 指减少表示给定信息量所需要的数据量。数据和信息之间必须给予明 确的区分。数据是信息传送的手段。对相同数量的信息可以以不同数量的数据表示。包 含了与所描述的内容无关联的或是重述己经知道了的信息，就叫做包含了数据冗余p j 。 在数字图像中，有几种冗余存在并可以加以利用： ( 1 ) 编码冗余：如果图像的灰度级在编码时用的编码符号数多于表示每个灰度级实 际所需的符号数，则用这种编码得到的图像包含编码冗余。通常，当被赋予事件集的编 码如果没有充分利用各种结果出现的概率，就会存在编码冗余。 ( 2 ) 像素间冗余：任何给定像素的值可以根据与这个像素相邻的像素进行适当的预 测，所以由单个像素携载的信息相对较少。单一像素对于一幅图像的多数视觉贡献是多 余的，它的值可以通过以与其相邻的像素值为基础进行推测。 ( 3 ) 心理视觉冗余：在正常的视觉处理过程中各种信息的相对重要程度不同，那些 不十分重要的信息称作心理视觉冗余。这些冗余在不会削弱图像感知质量的情况下可以 消除。 综上所述图像编码的目的就是去除图像中的冗余，当这几种冗余中的一种或多种得 到减少或消除时，就降低了图像的数据量，从而实现了图像的数据压缩。 1 2 图像压缩系统的组成 一个图像压缩系统包含两个不同的模块：一个编码器模块和一个解码器模块。图像 厂( x ，y ) 输入到编码器中，这个编码器可以根据输入数据生成一组符号。在通过信道进行 传输之后，将经过编码的表达符号送入解码器，经过重构后，就成了输出图像了f ( x ，y ) 。 一般来讲，尹( 五y ) 可能是也可能不是原图像f ( x ，y ) 的准确复制品。如果输出图像是输 入图像的准确复制，系统就是无误差的或具有信息保持的编码系统；如果不是，则在重 建图像中就会呈现某种程度的失真。 编码器的任务是减少或消除输入图像中的编码冗余、像素间冗余或心理视觉冗余。 大连理工大学硕十学位论文 可以通过一系列的操作建立模型。如图1 1 所示，每种操作被设计用来减少上述谈到的 三种冗余种的一种，但并不是每个图像压缩系统都必须包含这三种操作。图1 2 描述了 对应的解码器。 图1 1 f i g 1 1 编码器 e n c o d e r 图1 2 f i g 1 2 解码器 d e c o d e r 1 3 图像压缩编码的分类 利用不同的编码方法删除冗余，就形成了不同类型的压缩编码方法。根据解码后的 数据是否和原始数据一致，图像编码可分为无损编码和有损编码两种【l 5 1 。 ( 1 ) 无损编码 无损编码又称无失真编码或信息保持编码，这是一种在不引入任何失真的条件下使 比特率为最小的压缩方法。该方法要求在解码后得到的恢复图像与原始图像严格相同， 没有任何失真。无损编码方法由于没有利用人眼的视觉特性，一般情况下压缩比很低。 无损编码比特率的最低限可由香农( s h a n n o n ) 定理得到，即无损编码的最大压缩比为 c 慨= , j n ( x ) ，其中t 为原始图像的平均比特率，研矽为原始图像的墒。现有无损编码 方法主要根据信息码字出现概率的分布特征进行压缩编码，寻找出现概率与码字长度间 的最优匹配。常见的有霍夫曼( h u f f i n a n ) 编码、香农一费诺( s h a n n o n f a n o ) 编码以及算术编 码( a r i t h m e t i cc o d i n g ) 。 ( 2 ) 有损编码 有损编码是一类有失真的编码方法，信息论中叫做熵压缩。该方法导致信息的减少， 有信息丢失。丢失了的信息是根本无法恢复的，所以是一个不可逆的过程。常用的方法 有： 变换编码：指将给定的图像变换到另一个数据域( 如频域) 上，使得大量的信息能 有较少的数据来表示。常用的方法有：离散傅立叶变换( d i s c r e t ef o u r i e rt r a n s f o r m ，简 称d f t ) 、离散余弦变换( d i s c r e t ec o s i n et r a n s f o r m ，简称d c t ) 、离散哈达玛变换( d i s c r e t e 基于分形和小波理论的图像压缩方法 h a d a m a r dt r a n s f o r n l ，简称d h t ) 。 预测编码：指只对新的信息进行编码，从而去掉相邻像素之问的相关性和冗余 性。常用的方法有：增量调带1 ( d e l t am o d u l a t i o n ，简称d m ) 、差分脉冲编码调$ i ( d i f f e r e n t i a l p u l s ec o d em o d u l a t i o n ，简称d p c m ) 。 直接映射：常用方法有向量量化、神经网络和方块截尾等。以向量量化为例， 它把图像分块，每一块中的元素组成一个向量，对向量进行新的编码。注意到图像中的 很多块可能比较相近，因而只要用一个向量就可以代表这些块。通过聚类算法，可用比 较少的码把图像恢复出来。 分析综合编码：包括子带、模型基和小波等。 冗余度压缩与不可逆压缩的结合形成了一类称为混合编码技术，它体现了不同类型 技术的交叉和综合，实际上许多国际标准都是采用混合编码技术。 1 4 图像质量的判别标准 消除心理视觉冗余数据导致真实的或一定数量的视觉信息的丢失，因为可能会由此 失去重要的信息，所以迫切需要一种对信息损失的测度来描述解码图像与原始图像的偏 离程度，这些测度一般称为保真度准则。作为这种评估基础的两类准则是：客观保真度 准则和主观保真度准则【10 1 。 ( 1 ) 客观保真度准则 设原始的m n 个像素点的灰度图像a = f ( x ，y ) ，经压缩还原后的图像数据为 匀- - 夕( x ，y ) ，其中x = o ，l ，m ，y = o ，l ，n 。可用下列几种指标评价： 均方误差： m s e = 土( ( x ，y ) 一夕( x ，y ) ) 2 m n 鲁篙。一一“ 规范化均方误差： 一= 等，其中巧= 击萎m 驴n w ) 盯；。删= = 对数信噪比： 盯! s n r = 1 0 l o g 上= - 1 0 l o gn m s e ( d b ) m s e 峰值信噪比： 大连理工大学硕士学位论文 燃= 1 0 1 0 9 麓( d b ) 实际上，p s n r 为常用标准，当p s n r 超过3 0 d b 时，我们的主观视觉很难找出其差 异。 ( 2 ) 主观保真度准则 尽管客观保真度准则提供了一种简单便捷的评估信息损失的机理，但大部分解压缩 图像最终还是由人来进行观察的。所以，使用观察者的主观评估衡量图像品质通常是更 为适当。主观评估是通过一组实验人员对图像进行观察打分，来评价图像的质量。评估 可能采取绝对等级或并排对比f ( x ，y ) 和厂a ( x ，y ) 的形式。表1 1 显示了一个可行的绝对等 级量表。并排对比可以使用诸如 一3 ，- 2 ，一1 ，0 ，l ，2 ，3 这样的标度分别表示主观评估 非常恶劣，恶劣，稍坏，普通，稍好，更好，非常好) 。不管使用何种形式，这些评估 都称为基于主观保真度准则。 表1 1电视图像的等级量表 t a b 1 1 g r a g es c a l eo ft e l e v i s i o ni m a g e 基于分形和小波理论的图像压缩方法 2 分形与小波图像压缩基础 2 1 分形图像压缩基础 19 7 5 年，法国数学家m a n d e l b r o t 发表了t h ef r a c t a lg e o m e t r yo fn a t u r e ，标志 着“分形( f r a c t a l ) 作为- - f 7 科学正式成立，分形理论也成为非线性科学的主要分支之 一，它对自然科学和社会科学都产生了巨大的影响。分形理论既有深刻的理论意义，又 有巨大的实用价值。特别是在图像压缩方面，由于分形结构一般都具有某种形式的自相 似性，尤其对于不规则的几何图形( 曲折的海岸线、多变的云彩图案、参差不齐的金属 表面以及涨落无常的股价曲线) 可由简单的函数簇迭代产生的这一特性，使基于分形理 论的图像压缩方法成为数据压缩的一种行之有效的重要方法【1 6 j 。 2 1 1 分形的定义 经典的欧氏几何所能处理的图形都是相当规则和光滑的，通常是整数维的( 如离散 点集是零维的，光滑曲线是一维的，光滑曲面是二维的等等) 。但随着科学的发展，人 们意识到对过去当作例外的不规则的图形可以而且必须进行详细的分析。分形几何恰好 为研究这些不规则图形提供了经典几何学所没有的理论和思想框架，分数维和自相似性 是其核心之一。一般说来，分形集f 具有以下全部或部分特征 1 5 - 1 刀： ( 1 ) f 具有任意小尺度下的比例细节，或者说它具有精细的结构。 ( 2 ) f 具有不规整性，其局部和整体都不能用传统几何语言来描述。 ( 3 ) f 具有自相似性，这种自相似可以是近似自相似或者是统计自相似。 ( 4 ) f 的分维严格大于它相应的拓扑维数。 ( 5 ) f 一般可用简单的形式描述，并可由简单迭代过程生成。 分形是人们在自然界和社会实践中所遇到的不规则事物、状态和过程的一种数学抽 象，分形的描述式定义能够全面地概括这种抽象。m a n d e l b r o t 曾经指出，分形具有三个 要素：形状( f o r m ) ，机遇( c h a n c e ) ，维数( d i m e n s i o n ) 。首先，分形的形状是支离破碎的， 不规则的。其次，分形可以对一组给定的规则通过随机迭代而得到，而对象本身并不依 赖于随机性，得到同一个分形的概率是百分之百，因此随机性或者机遇仅仅是工具，而 结果却是确定的。第三，维数是分形图形最基本的不变量，是度量分形集“不规则 程 度的数量尺度；分形的维数可以是分数，称为分维。 2 1 2 分形图像压缩的理论基础 分形图像压缩理论的数学基础是集合论、映射、仿射、变换、几何拓扑学、计算机 大连理工大学硕士学位论文 科学以及图像处理有关理论，所以分形学是- - fj 交叉的综合性学科。分形图像压缩的理 论基础是压缩映射定理、迭代函数系统定理和拼贴定理【1 6 ，1 引。 ( 1 ) 压缩映射定理 定义2 1设f ：x _ x 是度量空间上的一个变换，的向前迭代就是变换 f ”：x 专x ，其定义为厂o ( x ) = x ，f 1 ( x ) = 厂( x ) ，f 斛1 ( 工) = f 。y ”( x ) = f ( f ”( x ) ) ，刀= 0 ，1 ，2 定义2 2 变换w ：r 2 专r 2 具有形式 ； = ：三 ； + ； c 2 1 ， 其中a ，b ，g d ，e ，厂为实数，则称形为一个( 二维) 仿射变换。 当x r 2 时，式( 2 1 ) 常写成 r v ( x ) = a x + t = 嘲一阱 有四种平面仿射变换具有明显的几何意义，记 4 = 艄件艄，以= ，4 = 瞄瑚。 其中4 为缩放变换，4 为伸长变换，4 为剪切变换，4 为旋转变换。由此可见，仿射 变换就是把原图进行缩放、扭曲、平移和旋转。 定义2 3 度量空间，d ) 上的变换f ：x x 称作压缩或压缩映射，如果存在一个 常数0 s 。 定理2 2 ( 压缩映射不动点定理) 设 x ；q ，甩= l ，2 ，奶是拥有压缩因子j 的一个迭 代函数系，则变换形：h ( x ) 一h ( x ) 定义如 形( 口) = q ( 曰) u 哆( b ) u u 鲰( 丑) ，日( x ) 是完备空间( 圩( x ) ，乃) 上具有压缩因子s 的压缩映射，即对所有的b ，c h ( x ) ，有 办( 形( 曰) ，( c ) ) s h ( b ，c ) 且它的唯一不动点a 日( x ) ，满足 么= 形似) = u 似) n = l 并且对于任意一个b 日( x ) ，有 a = l i m 矿”( 五) 一 彳同时也被称为该迭代函数的吸引子。上述定理说明：给定一个胃2 上的迭代函数 系统，就能生成唯一的一幅图像。在计算机图像压缩技术中，更有意义的是：对任意一 幅图像，都能找到一个r 2 上的迭代函数系统，使得该迭代函数系统的吸引子就是该图 像或者近似于该图像。 ( 3 ) 拼贴定理 定理2 7 ( 拼贴定理) 嘲设，d ) 为一完备度量空间，给定工h ( x ) 与占艺0 ，选定 一个迭代函数系 x ；c o 。，玎= 1 ，2 ，n ，其压缩因子为s ：0 s 1 ，使得 h ( l ，u 吃( ) ) s n = l 其中h ( d ) 是h a u s d o r f f 度量，则 大连理工大学硕士学位论文 h ( l ，4 ) 者 其中a 是迭代函数系 x ；c o , ，门= 1 ，2 ，n 的吸引子，等价地 1。 h ( l ，4 ) h ( l ，【j ( 工) ) l s 品i 该定理表明，如果迭代函数系统对原图像的变换结果与原图像很接近，而压缩因子 又远小于l ，则其吸引子与原图像也很接近。该定理是分形图像压缩方法的理论基础。 2 1 3 分形图像压缩的基本原理 分形图像压缩是利用图像的自相似性来进行压缩的一种方法。自相似性是指无论几 何尺度怎样变化，景物中任何一小部分的形状都与较大部分的形状相似。从压缩观点来 看，这种自相似性就是一种信息冗余，因而可用于图像压缩。这种方法是在不同的比例 上发现自相似部分，去除重复描述。它对图像进行系统分析，然后提取出一套代码来进 行存储和传输，从而获得压缩。分形图像压缩方法大体可分为两类：一类是分形模型图 像压缩编码，即预先对某一类景物建立分形模型，编码时则根据具体景物提取相应的分 形参数，再编码传送，来实现压缩；另一类是基于迭代函数系统的分形图像压缩编码， 即利用迭代得到原始图像的一个分形近似。后一类方法易于实现，应用较为广泛，其编 码的过程就是依据拼贴定理，通过对给定的图象，寻找一组压缩仿射变换，使其构成的 迭代函数系统逼近给定的吸引子，然后记录下相应参数的过程，并且将这些参数作为图 像的编码进行存储或传输。解码过程首先是由存储或传输的参数确定一组压缩仿射变 换，进而构造一个迭代函数系统，并求出这个迭代函数系统的吸引子，根据吸引子定理， 该迭代函数系统的吸引子就是原始图象的近似。这种方法丢弃原图而只编码传输或存储 其i f s 代码，从而得到很高的压缩比，本文主要论述第二种编码方法。 1 9 9 0 年，j a c q u i n 运用局部迭代函数理论，提出了一种基于块的全自动的分形图像 压缩方法【8 】，这是首次利用计算机进行数字图像的分形压缩的自动算法，对分形图像压 缩方法的实用化起了奠基的作用。分形图像编码p i f s 方法，本质上是假设自然图像中 不同区域间存在着跨尺度冗余( a c r o s s s c a l er e d u n d a n c y ) ，即不同尺度下的冗余来实现图 像压缩的。从结构上看，p i f s 码与i f s 码几乎是相同的。唯一的差别是，前者是利用图 像的不同区域在不同尺度下的相似性( 局部与局部的相似性) ，后者是利用图像的不同区 域在不同尺度下与图像本身的相似性( 局部与整体的相似性) 。 一个p f i s 包括完备度量空间( x ，d ) ，定义域子块口cx ( i = 1 ，2 ，刀) 以及一组压缩 基于分形和小波理论的图像压缩方法 映射集w ：口o x ( i = 1 ，2 ，刀) 。 假设一副大小为m 的灰度图像行灰度级为2 5 6 ) ，在分形编码过程中，图像厂被 分割为大小为b x b 的且互不重叠的值域块和大小为c x c 的且可以相互重叠的定义域 块，通常定义域块的大小是值域块的2 倍。所有的值域块组成了值域块池 r ( 1 i m xn ( s 召) ) ，所有的定义域块组成定义域块池q = bi 口c 力。对于每个值 域块置，我们在定义域块池中搜索一个最优的定义域块d f ，并计算相应的压缩映射w ， 使得w ( 口) 和冠的误差最小，这里的误差度量一般采用均方误差来度量。重复进行直到 所有的值域块都找到相应的最优定义域块，这样我们就得到一组压缩映射集合 w = w 1 1 f m x n ( a 曰) 和相应的定义域块位置。由拼贴定理我们知道，如果一组 映射是压缩的，则这组压缩映射存在唯一不动点，且这个不动点到原始图像的距离任意 小。因此拼贴定理保证了w 的不动点图像和原始图像厂近似。对每一个值域块足，其相 应的定义域块位置和相应的压缩映射构成了r i 的分形编码，所有的值域块的分形编码构 成了原始图像的分形编码。图2 1 表示了值域块和定义域块间的压缩映射。 h l 雾鹗 - 豳 妊 1 17 驾 矿， 。五 刍秀 觏l舞乏鳓缓 、吩 、 | 阌 图2 1 值域块和定义域块间的压缩映射 f i g 2 1 c o n t r a c t i v ea f f i n et r a n s f o r m a t i o nb e t w e e nr a n g eb l o c k sa n dd o m a i nb l o c k s 每一个压缩映射心e h = 部分组成，定义如下所示： w ( 口) = 删( 4 ) ( 2 2 ) 其中表示定义域收缩算子，厂表示等矩变换算子，矽表示灰度级变换，口表示一个图 像定义域块。定义域块收缩算子可以采用四像素平均或欠采样来构造，如图2 2 所示。 通常我们采用四像素平均的方法来构造收缩的定义域子块。假设收缩后的定义域子块的 灰度值为g ，y ) ，则可以用下面公式来得到： 大连理工大学硕士学位论文 g ( x ，y ) = i 1 f ( p ，g ) ，工= 1 2 ，b ；y = 1 2 ，b 叶( p ，q ) g d 。( j 。y ) 、 、 ( a )( b ) 图2 2 定义域块收缩：( a ) 像素值平均；c o ) 欠采样 f i g 2 2 c o n t r a c t i n gd o m a i nb l o c k ：( a ) p i x e lv a l u ea v e r a g e ；( b ) p i x e lv a l u ed e c i m a t i o n 等矩变换算子也称为反射一旋转算子，采用等矩变换的原因是其可以扩大定义域块 池，提高值域块和定义域块之间成功匹配的的概率。同时为了简化图像块之间的匹配， 一般把一个图像子块的旋转化为简单的8 种方式，即旋转0 。，9 0 。，1 8 0 。，2 7 0 。和垂直 中线反射、水平中线反射和主、次对角线反射这8 种固定方式，如图2 3 所示。 一 回圆国 国团囤 图2 3 图像块的8 种旋转和变换 f i g 2 3 t h ee i g h tr o t a t i o n sa n df l i p so fa ni m a g eb l o c k 灰度级变换一般被定义为如下形式： 缈( d ) = s d + o i 其中j 表示亮度调整，o 表示亮度偏移，d 表示经过定义域收缩和等矩变换作用后的定 义域子块，表示大小与d 相同的全1 矩阵。正是参数j 和o 的引进，才使仿射变换后 的d 块的灰度有可能匹配灭块的灰度，如图2 4 所示。 基于分形和小波理论的倒像艇缩方法 盈一 i m a g eb l oc l = 图24 亮度调整与偏移 f i g24t h e g r e y l e v e ls e a l i n ga n dg r e y l e v e l t ) f f s e t 因此，对幅图像的分形编码问题转化为对图像中的每个值域块在定义域块池中 搜索是优的定义域块并计算相应的参数5 和。的过程，而对一个值域块r 和个收缩变 换后的定义域块d ，其相应的堆优参数s 和。由f 面定义的匹配误差e ( 月，d ) 决定： ( 亓，口j = 0 曲+ d ，一拧4 ( 2 通过使用最d - - - 乘法我们可以得到s 和o 如下： ( 24 o ：i 一耐 ( 2 5 ) 这里i 表示值域块月的均值，孑表示收缩变换后的定义域块d 的均值。每个值域块 的分形编码涉及到四个参数，分别为定义域块位置，等矩变换序号，以及亮度调整及亮 度偏移参数s 和o 。前面哪个参数不用量化，后面两个参数需要章化后存储。t o n g 等经 过大量试验表明j 和。分别采用5 比特和7 比特米量化是合适的口“。此外，为了进一步 提高压缩比，可以对量化后的参数s 和。进行熵编码压缩。 总之，在分形编码中，一幅图像是用一个使图像近似不变的压缩变换的参数来表达 的，而这样的参数往往可以紧凑地编码。这大大减少了储存陶像的比特数，困阿实现了 图像数据的高压缩比。 214 分形图像压缩的基本算法 基于e 述描述，个传统分形图像编码算法的具体步骤如下瞄2 ”- ( 1 ) 分割罔像：把原始图像按分辨奎b 占像索分割成若干块( 记为r ，) ，构成值域块 池月。相邻值域块之间没有重叠，它们的并集恰好为原始图像。 ( 2 ) 构成码本：在原始图像中按步长j 从左到右、自上而f 滑动一个2 b x 2 b 窗口得 到定义域块池n 。每个定义域块经过4 邻域像素值平均或欠采样得到bx b 的收缩定义 大连理工大学硕士学位论文 域块，所有收缩后的定义域块构成初始码本，所有初始码本分别经过8 个等矩变换构成 扩大的码本。 ( 3 ) 计算分形码：对于每个值域块碍，可以按下面两个步骤在扩大的码本中寻找其