（应用数学专业论文）基于分形理论的图像编码算法研究.pdf

重庆大学硕士学位论文中文摘要 摘要 在各种多媒体技术和数字通信等应用领域中，图像压缩编码是至关重要的技 术。从2 0 世纪4 0 年代末香农的信息理论提出到现在，涌现出了大量的图像编码 方法。其中，基于分形理论的图像编码方法以其编码思想新颖、高压缩比、多分 辨率、快速解码等优点受到了广泛关注。目前它已经渗透到特征提取、数字水印、 图像签名、纹理分割等图像处理领域中。 基于分形理论的图像编码方法是由b a m s l e y 于1 9 8 8 年首次提出的，源于迭代 函数系统理论。在编码过程中，一幅图像由一个使它近似不变的压缩仿射变换表 示，重构图像是压缩变换的不动点，压缩仿射变换的参数和图像分割信息组成原 始图像的分形码。而解码则是一个相对简单的快速迭代过程，解码图像由分形码 迭代作用于任意的初始图像来逼近。 尽管基于分形理论的图像编码方法有诸多的优点，但是它的编码过程是相当耗 时的，在某种程度上限制了它的广泛应用。因此，本文主要针对它的这个缺点， 深入研究了在保证解码图像质量的同时如何减少编码的时间的问题。 本学位论文收录了作者提出的两个快速编码算法： 1 ) 基于行列式的快速分形图像编码算法( 见第四章) 。该算法是基于图像块 的规范化行列式，能够在相对小的搜索邻域内找到输入子块的最佳匹配块。实验 结果显示：与全搜索基本分形算法比较，依赖于搜索邻域的大小，该算法能在峰 值信噪比( p s n r ) 相同的情况下实现编码速度加快3 0 倍左右。 2 ) 基于规范子块五点和的快速分形图像编码( 见第五章) 。它主要基于本文 新定义的图像块的一种特征五点和，把搜索范围限制在初始匹配块( 五点和 意义下与输入r 块最接近的d 块) 的邻域内。实验表明：该算法能够大大减少子 块匹配比较的数量，与基于叉迹的快速分形算法比较，在相同的搜索邻域内，在 编码时间、图像质量和压缩比方面都更优。 关键词：分形理论，图像编码，快速编码，行列式，五点和 重庆人学硕十学位论文英文摘要 a b s t r a c t i m a g ec o m p r e s s i o na n dc o d i n ga r ee s s e n t i a l l yi m p o r t a n tf o rt h ed e v e l o p m e n to f v a r i o u sm u l t i m e d i as e r v i c e sa n dt e l e c o m m u n i c a t i o na p p l i c a t i o n s s i n c et h ee n do f 1 9 4 0 s ，a f t e rt h ed i s c o v e r yo fi n f o r m a t i o nt h e o r yo fs h a n n o n ，m a n yi m a g ec o d i n g m e t h o d sh a v eb e e np r o p o s e d ，w h e r e i nt h ec o d i n gm e t h o db a s e do nf r a c t a lt h e o r yh a s r e c e i v e dm u c ha t t e n t i o nd u et oi t sh i g hc o m p r e s s i o nr a t i o ，m u l t i r e s o l u t i o na n dv e r yf a s t d e c o m p r e s s i o na n dh a sb e e ne m p l o y e di nm a n yi m a g ep r o c e s s i n ga p p l i c a t i o n ss u c ha s f e a t u r ee x t r a c t i o n s ，d i g i t a lw a t e r m a r k i n g i m a g es i g n a t u r e s ，i m a g er e t r i e v a l sa n dt e x t u r e s e g m e n t a t i o n t h ei m a g ec o d i n gm e t h o db a s e do nf r a c t a lt h e o r yi sf i r s t l yp r o p o s e db yb a r n s l e yi n 1 9 8 8 ，w h i c hi sd e v e l o p e df r o mm a t h e m a t i c a lt h e o r yc a l l e di t e r a t e df u n c t i o ns y s t e m s ( i f s ) d u r i n gt h ee n c o d i n ga ni m a g ei su s u a l l yr e p r e s e n t e db yac o n t r a c t i v ea f f i n e t r a n s f o r m a t i o n , f o rw h i c ht h er e c o n s t r u c t e di m a g ei si t sf i x e dp o i n ta n di sa p p r o x i m a t e t ot h eo r i g i n a li m a g e t h ef r a c t a lc o d eo ft h ei m a g ei n c l u d e st h ep a r a m e t e r so ft h e c o n t r a c t i v et r a n s f o r m a t i o na n dt h ei n f o r m a t i o no fi m a g es e g m e n t a t i o n t h ef r a c t a l d e c o d i n gi sar e l a t i v e l ys i m p l ei t e r a t i o np r o c e d u r e , i nw h i c ht h ed e c o d e di m a g ei s a p p r o x i m a t e db yi t e r a t i n gt h ec o n t r a c t i v et r a n s f o r m a t i o nd e n o t e di nt h ef r a c t a lc o d eo n a na r b i t r a r yi n i t i a li m a g e t h em a i nd r a w b a c ko ft h ei m a g ec o d i n gb a s e do nf r a c t a lt h e o r yi st h ee x p e n s i v e c o m p u t a t i o n a lc o s ti nt h ee n c o d i n gp r o c e s s ，a l t h o u g hi th a sm a n ya d v a n t a g e s t h e r e f o r e , t h i sa u t h o rs t u d i e s m a i n l yh o wt or e d u c er u n t i m ei n t h ee n c o d i n gp r o c e s sw h i l e m a i n t a i n i n gt h er e c o n s t r u c t e di m a g eq u a l i t y t w of a s tf r a c t a le n c o d i n ga l g o r i t h m sp r o p o s e db yt h i sa u t h o ri nt h i sd i s s e r t a t i o na r e s u m m a r i z e da sf o l l o w s ： 1 ) t h ef a s tf r a c t a li m a g ee n c o d i n ga l g o r i t h mb a s e do nl o c a ld e t e r m i n a n t s ( s e e c h a p t e r4 1 t h j sa l g o r i t h mp r o p o s e da na c c e l e r a t i n gs c h e m eb yt h ed e t e r m i n a n t so f n o r m a l i z e dr a n g ea n dd o m a i nb l o c k s ，w h i c hc a nf i n do u tt h eb e s t m a t c h e db l o c kt oa n i n p u tr a n g eb l o c ki nar e l a t i v e l y - s m a l ls e a r c hn e i g h b o r h o o d e x p e r i m e n t a lr e s u l t ss h o w t h a tt h i sa l g o r i t h mc a na c h i e v et h es p e e d - u po fa b o u t3 0t i m e sw i t ht h es a m ep e a k s i g n a l t o - n o i s er a t i o ( p s n r ) a st h eb a s e l i n ef r a c t a la l g o r i t h m ，d e p e n d i n go nt h es e a r c h n e i g h b o r h o o ds i z e 2 1t h ef a s tf r a c t a li m a g ec o d i n gb a s e do nq u i n c u n xs u m so fn o r m a l i z e db l o c k s 重庆大学硕士学位论文 英文摘要 ( s e ec h a p t e r5 ) t h i sm e t h o di sm a i n l yb a s e do nan e w l y - d e f i n e df e a t u r eo fa l li m a g e b l o c k , i e ，q u i n c u n xs u m ，w h i c hi su t i l i z e dt oc o n f i n ee f f i c i e n t l yt h es e a r c hs p a c et ot h e v i c i n i t yo ft h ei n i t i a l - m a t c h e db l o c k e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sm e t h o dc a l l r e d u c ed r a s t i c a l l yt h ea m o u n to fr a n g e d o m a i nc o m p a r i s o n sn e e d e dt oe n c o d ee a c h r a n g eb l o c k t h ep r o p o s e da l g o r i t h mh a sa l s ob e e nc o m p a r e dw i t ht h ef a s tf f a c t a l e n c o d i n ga l g o r i t h mb a s e do nc r o s s - t l a c e , s h o w i n gu n d e rt h es a m es e a r c hn e i g h b o r h o o d i tp e r f o r m sb e t t e ri nt e r m so f e n c o d i n gt i m e ，i m a g eq u a l i t ya n dc o m p r e s s i o nr a t e k e y w o r d s ：f r a c t a lt h e o r y , i m a g ec o d i n g ，f a s te n c o d i n g , d e t e r m i n a n t s ，q u i n c u n xs u m s 1 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 靴论文作者虢习巍签字眺纠蛳咖 学位论文版权使用授权书 本学位论文作者完全了解重废太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重废太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在 年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“”) 躲刻猃j 弛 签字日期2 初年岁月移日 导师签名：什町i 麦 签字日期：诎7 年f 月万咱 重庆大学硕士学位论文1 绪论 1 绪论 1 1 图像编码的研究意义 长期以来，人们在自然界感受到的最重要的信息是视觉信息，但是在早期的 计算机和通信领域，能够处理和传输的主要是文字和语音，因此，早期的计算机 和通信设备的处理能力跟人类的需求有很大的差距。随着通信信道及计算机容量 和速度的提高，图像信息【l 】已经成为通信和计算机系统的一种重要的处理对象。 对于日常的多媒体应用来说，这些未经压缩的数字化图像的信息量过于庞 大，是人们在现有技术条件下有效利用图像信息的一个瓶颈，举例来说： 一幅分辨率为5 1 2 x 5 1 2 ，8 b i t s p i x e l 的灰度图像大小为2 5 6 k b ：同样分辨率 的一幅彩色图像大小为3 x 2 5 6 = 7 6 8 k b ；而一幅2 2 3 0 x 2 2 3 0 x 8 b i t s 的气象卫星红外云 图的大小要达到4 7 4 m b 。这样，一颗卫星每天( 半小时发回一次5 个波段的数据) 的数据量为1 1 g b ；一条航天测量船每年记录的数据要达到1 5 0 0 0 盘0 5 英寸的计 算机磁带。 一路电视信号按c c i r 6 0 标准，数字化后的分辨率为7 2 0 x 5 7 6 ，每秒2 5 帧 所需的数码率为1 6 5 9 m b p s ，若用一个容量为1 g 的硬盘或光盘来存储这样的数据， 则只能存储不到一分钟的图像。对于h d t v 来说，数码率可以达到接近1 g b p s ， 需要的存储量更加惊人。 一个指纹库，若以5 1 2 x 5 1 2 x 8b i t s 的灰度图像来存储一个手指的指纹，一个 4 0 万人的指纹库，每人十指，则共需1 0 0 0 g b 的存储量。 因此，对图像数据的压缩就成了技术进步的迫切需求，而正是由于这种需求， 图像编码【2 】算法和技术成为近3 0 年来一个非常活跃的研究领域，并在商业上取得 极大的成功。 1 2 图像编码发展现状与不足 1 2 1 发展现状 图像编码【j 1 从它产生到现在，主要经历了三个发展阶段： 6 0 - - 7 0 年代：根据媒体特性量身定制的压缩方法中，行程编码是最简单、最容 易被人们想到的一种。大多数计算机中产生的图像都有着大面积重复的颜色块， 为什么非要用无数个完全相同的颜色值来表示某块图像呢? 我们完全可以用一个 颜色值加重复的次数来表示这一块图像，冗余度由此减小了，这就是行程编码方 法的基本思路。 8 0 年代：在这段时间，人们逐渐意识到，对大多数灰度或彩色图像乃至声音文 重庆大学硕士学伊论文l 绪论 件，没有必要完全保留所有的信息，在允许一定精度损失的情况下，可以实现更 为有效的压缩方法。到8 0 年代末，许多人已经在这一领域取得了不小的收获，设 计出一批在压缩效果上让人惊讶不已的声音和图像编码算法。在此基础上，国际 标准化组织( i s o ) 和国际电报电话咨询委员会( c c i t t ) 联合组成了两个委员会：静态 图像联合专家小组( j p e g ) 和动态图像联合专家小组( m p e g ) 。j p e g 的压缩目标是静 止图像( 灰度的和彩色的) ，m p e g 的目标则是声音和视频。但他们的基本理论是完 全一样的( 用离散余弦变换( d c t ) 将图像从时间域转换到频率域再进行处理) ，都是 保留媒体信息中最有规律、最能体现信息主要特征的数据，而略去其他不重要的 数据。 9 0 年代至今：近年来，图像编码的研究仍然是比较热的，最新的压缩方法大 多是与分形【4 】和小波有关。最近十余年来，分形( f r a c t a l ) 在图像编码技术中的应用 已经成为图像数据压缩领域中最为热点的问题之一。原因是基于分形理论的图像 编码方法与经典的图像编码方法相比，在思维方式上有更大的突破( 分形图像编 码有编码思想新颖、压缩比高、解码速度快、分辨率无关性等优点) 。分形图像编 码的发明人之一m b a r n s l e y 5 在1 9 8 8 年发表的论文中宣称分形图像压缩可达到 1 0 0 0 0 ：l 的压缩比。1 9 9 2 年圣诞节，美国微软公司推出了一张名为“m i c r o s o f t e n c a r t a ”的光盘，它是一部奇特的集文字、动画、音响、图像、地图册和字典于 一体的百科全书，内有8 0 0 张可缩放的彩色地图、一本字典、7 个小时的音响和 1 0 0 个动画，包含的7 0 0 多张高质量的图像中有鲜花、植物、人物、动物、云彩 与名胜等等。而所有这些压缩后的数据没有超过6 0 0 m ，完成这一成果所依赖的就 是分形技术，就象b a m s l e y 所评价的：“1 1 1 c ya r ea l lf r a c t a l sf ，与此同时，由于m a l l a t 塔式分解算法 6 的提出，离散小波变换( d w t ) 就成为图像处理的一种重要手段， 因为它不仅可以把图像进行多尺度分解，形成子带图像，还可以有效地去除图像 中系数的相关性，为其他的编码方法提供变换域。目前已有大量基于小波变换的 优秀算法【7 - 8 】，还出现了许多分形与小波相结合的混合编码算法t 3 1 ，取得了很好 的编码效果。 本文中将主要探讨与分形图像编码算法有关的问题。 1 2 2 现有方法的不足 现有的各种图像编码方法都不同程度地存在着以下问题： 编码时问太长 编码算法的复杂度太大，实用性不强，不容易实现 信噪比与压缩比之间的矛盾没有得到很好的解决 新的编码算法在理论方面还不够完善 2 重庆人学硕士学位论文1 绪论 1 3 图像编码的分类 图像编码算法大体可分为无失真编码( 或可逆压缩) 与限失真编码( 或不可逆压 缩) 两大类。 1 3 1 无失真编码 无失真编码是将输入图像中表达像素点灰阶值的每个符号，用规定的码字符 号按一定的方式编排而成。由于规定的码字符比原图像中符号短，从而可用比较 少的比特数来表达原图像的符号，达到图像压缩的目的。在恢复图像时，只要把 得到的码字符与像素点的灰阶符号对应起来，就可无失真的恢复图像。无失真编 码方法包括：h u f f m a n 编码、算术编码、 1 3 t 2 限失真编码 为了迸一步提高图像编码的压缩比， 词典编码、游程编码等。 利用图像中像素之间的相关性，以及人 的视觉对图像狄度灵敏度的差异，用尽可能少的码字来表示所处理的图像，这就 是限失真编码方法。它的出现，满足了大多数图像存储和传输的要求，因此很快 成为了图像压缩的重要手段。现在最常用的方法【1 4 】有： 变换编码把原始图像通过一些变换后，得到在变换域中系数具有比较低的 熵值，然后再用无失真编码把信息压缩下去。如d c t 、d w t 、k l 变换等。 预测编码利用相邻像素之间存在的相关性，采用预测值与原像素的灰阶值 之间进行编码。由于误差信号的熵值比较低，这时再用无失真编码就可进一步压 缩图像信息。 矢量量化将图像分块，每一个块的像素组成一个矢量，然后对矢量直接编 码。注意到图像中的很多块可能比较接近，因而只要用一个矢量就可代表这些块， 通过聚类算法，可用比较少的码字把图像恢复出来。 模型法把图像分割成几个基本模型，模型具有一定的参数，只要将参数进 行编码传输，就可恢复出原来的图像。 基于分形理论的图像编码方法是一种介于和之间的编码方法，因此也是一 种限失真编码。它是把任何一幅图像看作一个分形，只要找到迭代函数系统的参 数，就可以用迭代的方法把原来的图像恢复出来。 1 4 图像编码质量的评价准则 对限失真编码的算法，应该有一个评价标准，可以对恢复后的图像质量好坏 给予评判。其中常用的评价标准有两种：一是客观准则，一是主观准则。 1 4 1 客观准则 客观准则是对编码还原后的图像与原始图像的误差进行定量计算，一般就整幅 图像或图像中一个指定的区域进行某种平均计算，以得到均方误差。 重庆人学硕七学衍论文1 绪论 设一个原始图像为缸( f ，) ，0 s f 肘一l ，0 茎j s n 1 ) ，经编码后的还原图像为 五( j ，) ，o f m 一1 ，0 j n - 1 ， p ( f ，j ) = a ( i ，j ) 一a ( i ，) ，o f m l ，0 j 一1 ) 是误差图像：那么，均方误差 可表示为 ：击艺芝鄱棚 2 两刍缶矿【l j 有时也会用均方根误差表示，即= 【】l 2 。 更常用的评价标准是用信噪l i ：( s n r ) 表示，它用分贝表示编码图像的定量性能 评价。基本的信噪比定义为 s n r = 1 0 1 9 i 而两产鲤一 l ，j ) - z t ( i ，川2 另一种信噪比是先对原始图像去均值，定义如下： 可“) = 嘉m 荟- 1 善n - i ，力 s n r , = 1 0 1 9 i 宗亲i _ 一 i 丑口( f ，) 一她川2 ( 1 2 ) ( 1 3 ) ( 1 4 ) 文献中常用的是峰值信噪l g ( p s n r ) ，a m a x = 2 - 1 ，k 是表示一个像素点用的 2 进制位数，则 p s n r = 1 0 1 9 埘忆乙 面= f 百了一 ，j ) - a ( i ，) 】2 l = 0 j = 0 ( 1 5 ) 在许多采集的视频序列和商用图像的应用中，一般取k = 8 ，因此在一些文献 中，直接将口。= 2 5 5 代入到上式中。 1 4 2 主观准则 对压缩图像质量评价的第二种准则是主观准则，它是选择一组评价者给待评 图像打分，然后把这些分求和再取平均得到一个主观评价分。表1 1 列出的是两种 典型的评分标准。 4 重庆人学硕士学位论文1 绪论 表1 1 对图像质量的主观评分标准 得分第一种评价标准 第一种评价标准 5 非常好感觉不到失寅 4 好 感觉到失真，但没有不舒服感觉 3 一般稍有感觉不舒服 2 较筹不舒服 l 差非常不舒服 设每一种得分记为c ，每一种得分的评分人数为鸭，则一个被称为平均感觉 得分( m o s ) 的主观评价得分为 k c f m o s = 2 i ( 1 6 ) n t厶 i = l 如，一段视频节目的主观评价分为4 5 ，则说明图像质量相当好，感觉不到失真。 评价图像编码效果的另外一个重要指标是压缩t l ( c r ) ，它是指原始图像每像 素的比特数同压缩后平均每像素的比特数的比值，也常用每像素比特值来代表压 缩效果。在视频图像序列传播的应用中，由于信道的限制，目标传输速率是确定 的，例如3 8 4 k b p s 表示每秒3 8 4 k 比特，这时的压缩比就要根据传输的视频帧率和 分辨率来确定。 1 5 分形图像编码的发展趋势 1 1 1 j a c q u i n t l 5 - 1 7 把分形理论成功用于图像编码之后，分形图像编码就引起了世 界各国研究人员的广泛兴趣和关注，发表的论文也逐年增多。从参阅的大量文献 来看，目前分形编码方案大致集中在三个方向：加快分形图像编码的速度、提高 分形图像解码的质量、分形序列图像编码。下面简要介绍这三方面的进展： 加快编码速度分形图像编码时间过长一直是它走向实用化的最大瓶颈。假 定一幅c c 大小的图像，在j a c q u i n 提出的编码方案中，根据子块的复杂程度将 其分成4 类，对于每个值域子块，仅在属于同类的定义域子块中进行搜索。如果4 类 定义域的块数相同，则编码时间减少为原来的1 4 。后来，e w j a c o b s 、y f i s h e r 和r d b o s s t l 8 j 9 根据图像块的灰度平均值将子块分成3 大类，同时又根据图像块灰 度的方差大小将每一类分成2 4 小类，因此，在此方案中，共将定义域子块和值域子 块分成7 2 类，另外还采用了四叉树等的分割方法，从而大大地减少了编码时间。房 育栋、余英林等【2 0 】考虑到区域的相关性，在搜索最佳定义域子块时，优化搜索次序， 先在值域子块附近邻域内寻找，若找不到，再将搜索范围逐渐扩大直至满足预定误 重庆人学硕士学位论文1 绪论 差，此举可减少搜索范围，缩短编码时间。 提高解码质量目前提高解码图像质量的措施有三个：一是采用混合编码方 案，如分形与小波相结合的编码算法【2 1 - 2 4 ) 。二是改进传统的分割方案，在j a c q u i n 最初提出的方案中，采用固定块分割方式，由于受狄度线性逼近的限制，在采用较大 的方块时，虽可以获得较高的压缩比但图像质量较差，而采用较小的方块时，灰度的 逼近较好，解码质量较高，但压缩比较低。另外，正方形方块在形状上也不利于倾斜边 界的编码。因此，一些专家和学者通过改进分割方案来改进图像块质量。y f i s h e r 等人就提出了四叉树的划分方式，使分形解码的质量和编码速度有了较大的提高， 是目前较为实用的压缩方法；他们又提出了一种三角形分割方案、h v 分割方案【2 5 】 等。三是改进灰度的逼近能力，在分形图像基本编码中，采用常用的仿射变换，其灰 度值的逼近式y b ：c o ( z ) = p z + g , 这是一个简单的线性逼近，逼近能力有限，文献 6 8 1 用改 进的仿射变换，其灰度的逼近变为( z ) ：t ( z ) ，t ( z ) 可以为任意形式，从而有效提高了解 码图像质量。 分形序列图像编码在实际应用中，序列图像比静态图像有着更广阔的应 用，而且由于时间维的引入，编码方法也有了新的变化，因此，序列图像编码成 为图像编码研究的热点之一。而分形图像编码在低码率压缩方面有独到之处，所以， 分形编码又被广泛地应用到序列图像之中。 1 6 本文的组织结构 本文将对分形理论及其在图像编码中的应用进行深入地研究，探讨如何减少 编码时间，提高解码图像质量的问题。全文共分为6 章，各章主要内容如下： 第l 章绪论。简单介绍图像编码的研究背景、发展现状与不足、图像编码的 分类、图像质量的评价标准以及当前分形图像编码的发展方向。 第2 章分形理论概述。简要论述了分形理论的产生背景、发展过程和分形的 定义，为后面介绍的内容作铺挚。 第3 章分形图像编码。主要介绍分形图像编码的数学理论基础及基本算法， 还介绍了图像分割的几种方案。 第4 章、第5 章介绍了作者提出的两个加快编码的算法。针对分形图像编码 时间长、计算复杂度高的缺点，采用不同的图像分割方式和不同的搜索方法，提 出了两种加快编码的算法，一个是基于行列式的快速编码算法，另一个是基于规 范子块五点和的快速编码算法。 第6 章全文总结。总结本文的主要研究工作，最后对分形图像编码的实用化 方向提出自己的见解和预测今后研究的方向。 6 重庆大学硕十学位论文2 分形理论概述 2 分形理论概述 为了更好地了解基于分形理论的图像编码方法，首先有必要介绍一些有关分形 理论的基本知识。 2 1 产生背景 分形理论的起源可追溯到十九世纪初。那时，一些科学家们研究了大自然中物 体和现象的几何形状，发现普遍具有复杂的不规则的形状，然而传统的物理学是 以牛顿的确定论为基础的，因此那些现象没有引起足够的重视。而在1 8 2 7 年发现 了布朗运动轨迹的复杂性、岩石在受到碰撞破碎时裂纹的复杂性、化学领域中高 分子的复杂空间结构、化学振荡现象等都难以用确定论来描述，一时间伴随着多 个学科类似问题的出现及研究，一门新的学科一分形就这样应运而生了。 分形理论是在二十世纪七十年代中期由美国科学家m a n d e l b r o t 创立，其诞生 的标志是m a n d e l b r o t 于1 9 7 5 年发表的专著 f r a c t a l ：f o r m ，c h a n c ea n dd i m e n s i o n ) ) 2 6 1 。分形理论是现代非线性科学中一个十分活跃的分支，在地理、地质、材料科 学、工程技术、信息科学、生命科学等多个领域中都有广泛的应用。特别是随着 计算机科学技术的迅猛发展和广泛应用，分形的思想和方法在模式识别、自然图 像模拟、信息讯号处理及艺术制作等领域都取得了巨大的成功。分形理论是研究 自然界中非线性系统中出现的不光滑和不规则的几何形体，核心内容是分形几何。 2 2 发展过程 分形理论经历了一百多年的发展，大致可分为以下三个阶段。 第一阶段( 1 8 7 2 - - 1 9 2 5 ) ：数学家们已认识到几类典型的分形集，并力图对这类 集合与经典集合的差别进行描述、分类和刻画。十九世纪初，虽然人们已认识到 连续曲线与可微曲线的差别，但普遍认为连续曲线上的不可微点应是极少的。但 在1 8 7 2 年，伟大的数学家w e i e r s t r a s s 构造了一个函数： 矽( 功- - e c o s ( 2 7 c b 曲，0 a 1 1 k - - 0 他证明了对某些a 和b 的值，该函数处处不可微。但这个函数图像极难绘画，因 此不够直观。 到1 9 0 4 年，瑞典科学家v o nk o c h 2 7 1 设计了一条被称之为k o c h 曲线的图形， 其设计步骤如下：设岛是单位区问【o ，1 】，第一步( n = 1 ) ，以e o 中间三分之一线段 7 重庆大学硕士学位论文2 分形理论概述 为底，向上作一个等边三角形，然后去掉区间( ，季) ，得一条四折线段的多边形巨。 反是处处可微的，但巨却有三点不可微。第二步( n = 2 ) ，对e l 的四条折线重复上 述过程，得一条十六折线段多边形e ，它有1 5 个点不可微。再重复上述过程，由 e 到e 。当n 趋于无穷时，便得到一条k o c h 曲线，显然该曲线是处处连续但点 点不可微。基本过程见图2 1 。 此后，波兰数学家s i e r p i n s k i l 2 7 】发现了一种三角形，并以自己名字命名，该三 角形具有严格的自相似性。令鼠为边长为1 的等边三角形，第一步( 厅= 1 ) ，联结 三条边的中点，得到四个全等三角形，去掉中间一个，保留其余三个，得s 。第 二步( n = 2 ) ，对s 的三个三角形重复刚才步骤，得s ，它含有9 个小三角形。如 此重复上述步骤，得，当n 趋于无穷时，便得s i e r p i n s k i 三角形( 见图2 2 ) 。 再者，德国数学家c a n t o r t 2 7 1 也构造了一个具有严格自相似性和无限精细性的 著名例子，那就是c a n t o r 三分集。记e o = 0 ，l 】，第一步( n = 1 ) ，去掉中问三分之 一，得巨= 【0 ，- j 1u l _ 2 ，l 】。第二步( 甩= 2 ) ，重复步骤，得 巨= o ，- j 1u l _ 2 ，扣u 暗，引7ul 百8 ，l 】。如此重复刚才一系列步骤，得e ，当n 斗o o 时， 即得c a n t o r 集f ( 见图2 3 ) 。 n 九一 图2 1 k o c h 曲线 f 1 9 2 1k o c h c u r v e 图2 2s t e r p m s k i 二角形 f i 9 2 2s i e r p m s k tt r i a n g l e o 专吾喜 吾吾鲁 t 舻o 一一 舻l i 一i 一 瞅 -_iiiii _ p 3 i i 一i i -l - l舭 封廿i l 捌韩哺u 矩荫hh uh 0h n - 5 图2 3 c a n t o r 三分集 f t 9 2 3c a l l t o rt r i s e c t i o ns e t 8 重庆大学硕十学位论文 2 分形理论概述 总之，在这一阶段，人们已经认识到分形集合的存在，并为讨论这些问题提 供了最基本的工具。 第二阶段( 1 9 2 6 - - - 1 9 7 5 ) ：人们对第一阶段提出的例子和其它分形集合的性质进 行了广泛深入的研究，进一步深化了第一阶段提出的思想，并逐步形成理论，而 且研究范围也扩展到了数学的许多分支里，并取得了丰硕的成果。 在分形维数理论方面，众多维数的定义被引入。如b o u l i g a n d 于1 9 2 8 年引入 b o u l i g a n d 维数，p o u t r i a g i n 和s c h n i r e l m a n 于1 9 3 2 年引入了覆盖维数，k o l m o g r o v 和t i k o m i r o v 于1 9 5 4 年引入了熵维数。众多维数的定义和理论的建立，使人们能 从不同的侧面刻画和分析分形集合的复杂性。对特定的分形集合，估计和计算它 的各种维数及讨论其相互关系便成了分形理论的一个基本研究课题。 在分形集合的结构和性质方面，b o s i c o v i t c h 在此期间先后研究了曲线的维数、 分形集合的局部性质、k a k e y a 集、分形集合的积。m a r s t r a n d 于1 9 5 4 年研究了s 集的性质和结构、分形集合的投影等。 在随机布朗运动方面，l e v y 建立分式布朗运动的理论，研究了稳定过程的性 质。同时，l e v y 对自相似集合的研究在这一阶段也占有重要的地位，现在对自相 似集合的一些研究可以追溯到他的研究结果。自相似集合是目前分形几何研究的 最多最彻底的一类分形集合。 随着人们在这一阶段对分形理论研究的深入和其他学科里分形问题的大量涌 现，客观上要求用一种新的思想和工具去处理相关的问题。正是在这样的时代背 景下，m a n d e l b r o t 经过在众多领域的长期研究后，将自己和已有的研究成果进行总 结和理论上的提升，从而揭示大到宇宙空间的星系分布，小至分子的b r o w n 运动 这些不同尺度上看似无关的和不规则的物质运动的本质。在1 9 7 5 年，他发表了 标志分形几何诞生的划时代的专著( 英文版：f r a c t a l ：f o r m ，c h a n c ea n d d i m e n s i o n ) ) ) 。从此，分形几何的研究和发展进入了一个新的时期。分形几何产生 于对不具有光滑性的复杂对象的研究，而且随着分形理论本身的不断完善，分形 几何逐渐成了描述和研究这种复杂对象的有力工具。而计算机本身的发展，客观 上使得人们刻画和研究这种复杂对象成为了可能。 第三阶段( 1 9 7 6 一现在) ：分形几何得到了迅猛的发展，不仅在理论上有了进一 步的完善，而且研究内容也得到了扩展，如随机分形、多重分形、迭代函数系统 理论、复动力系统的吸引子理论、分形的数值方法、随机布朗运动和布朗曲面等。 现在，人们已看到了分形极强的应用性，它的应用范围已扩展到了几乎所有的应 用学科，如物理学、计算机图形学、图像处理、分子化学、材料科学乃至经济、 艺术等领域，并且已取得了令人注目的成果。这也说明分形理论在一定程度上反 映客观事物某些本质的东西。在这个阶段，国内外很多专家和学者对分形理论及 9 重庆大学硕十学位论文 2 分形理论概述 其在各个领域的应用都进行了大量的研究，已有很多的有关专著出版，发表的研 究论文数量呈几何级数增长。 目前，分形与混澍2 引、分形与小波等也引起了人们的广泛关注。 2 3 分形定义 说到分形，人们会列举一大堆描述它的基本特性，如任意尺度下都能显示细 节，有某种自相似结构，“维数”可以是分数，等等。但究竟什么是“分形”? 恐怕谁 也说不清楚，因为目前还没有公认的严格明确的定义，只能对它的特征进行一些 描述。 粗略地说，分形是对没有特征长度但具有一定意义下的自相似图形和结构的 总称，这里的特征长度可以理解为刻画一个几何体特征的长度( 如直径就是一个 球的特征长度) 。m a n d e l b r o t 命名的“f r a c t a l ”是“破碎的、不规则的”意思，它所描述 的几何体也不同于一般的欧氏几何体。他曾建议将“分形”定义为整体与局部在某种 意义下具有自相似性( s e l f - s i m i l a r i t y ) 的集合，也曾把“分形”定义为h a u s d o r f f 维 数严格大于拓扑维数的集合，但是这些定义都不够精确、不够全面，因为按照这 些定义，有些明显算是“分形”的集合被排除在外了。 英国数学家f a l c o n e r t 2 9 】认为，“分形”的概念可以按生物学中对“生命”概念的类 似方法处理。在生物学中“生命”并没有给出严格和明确的定义，但却可以列出一系 列生物体的特征，如繁殖能力、运动能力以及对周围环境的相对独立的存在能力 等。虽然有一些生物例外，但大部分生物都具有上述特征。同样，我们也可以先 不寻求分形确切简明的定义，而寻求分形的特性。于是，分形就可以看作是具有 或部分具有下列典型性质的复杂集合【2 9 】： 具有精细的结构，即有任意尺度比例的细节，或任意尺度下都显示细节。 非常不规则，它的整体和局部都不能用传统的几何语言来描述。 通常有某种自相似的结构，可能是近似意义的或是统计意义的。 一般地，以某种方式定义的“分形维数”大于它的拓扑维数。 在大多数令人感兴趣的情形，可用非常简单的方法定义，也可以由迭代产 生。 其中，自相似性与分形维数是分形两大最显著的特征。本论文主要是讨论分 形的自相似性，进而利用该特性进行编码算法研究。 2 4 本章小结 本章对分形理论的产生、发展过程及分形的定义作了一个简单的介绍。若要 了解这方面更加详细的内容，请查阅参考文献【3 0 1 。 l o 重庆大学硕士学位论文 3 分形图像编码 3 分形图像编码 3 1 引言 压缩映射、不动点定理、迭代函数系统及拼贴定理【5 】是分形图像编码主要的数 学理论。迭代函数系统( i f s ) 是b a r n s l e y l 5 】及其研究小组在h u t c h i n s o n 3 1 】于1 9 8 1 年 提出的迭代函数理论的基础上发展起来的，它是分形几何的重要组成部分。不动 点理论是泛函分析的重要分支3 2 j 3 1 。拼贴定理【5 1 是b a n a c h 不动点定理的简单推论， 并成功地用于集合、函数( 包括信号、图像) 等的逼近。 本章主要来介绍这些基本的数学知识，并对基于分形理论的图像编码算法作 简单介绍。 3 2 分形图像编码的数学理论 3 2 1 压缩映射 定义3 1 变换w ：r 2 j r 2 具有形式为： 町荆：啦 + 多 - ， 其中a ，6 ，c4e , f 为实数，则称形为一个( - - 维) 仿射变换。 当x r 2 时，式( 3 1 ) 常写成：w ( x ) = 血+ f ，( 3 2 ) 其中a = 旧2 l ，f = 。 四种最常见的平面仿射变换具有明显的几何意义，我们记 4 - - 瞄o 4 6 7 ，4 ，以= l s i c o 。s 目0 搿 ( 3 s ) 则称4 为缩放变换，4 为伸长变换，4 为剪切变换，4 为旋转变换。 定义3 2 度量空间( z ，d ) 上的变换f ：x _ x 称作压缩或压缩映射，如果存在 一个常数0 j 1 ，使得 d ( 厂( 力，厂( y ) ) s d y ) ， v x , y 。r( 3 4 ) 数j 称为厂的压缩因子。 3 2 2b a n a c h 不动点定理 定义3 3 对于度量空间( x ，d ) 的映射f ：x 斗