（计算机应用技术专业论文）基于聚类的分形图像压缩方法研究.pdf

摘要 摘要 2 l 世纪是一个信息时代，人们在工作生活中大量接触图像，并在彼此之间互相传 播，为了使图像传送更快捷便利，图像压缩技术研究变得非常迫切。1 9 8 7 年由美国数 学家b a r n s l e y 和s l o a n 提出分形图像压缩编码技术，此后j a c q u i n 比1 首先实现了完全 自动的分形压缩编码，给分形图象压缩领域带来突破性的进展。分形图象压缩技术是在 此算法基础上逐渐发展，成为当今图象压缩的一个新领域。 基于分形的图像压缩编码方法是一种全新的编码方法，它利用的是图像的自相似性 及比例特性，通过消除图像的几何冗余度来实现图像数据的压缩。在分形编码中，一幅 图像由一个使它近似不变的压缩仿射变换表示，重构图像是压缩变换的不动点，压缩仿 射变换的参数组成原始图像的分形码。分形解码是一个相对简单的快速迭代过程，解码 图像由分形码表示的压缩变换迭代作用于任意初始图像来逼近。 分形图像编码近年来在图像压缩领域引起了人们的极大兴趣。众所周知，编码时间 长是这项技术的主要缺点，它己成为该方法走向高效能实用化的最主要障碍，因此分形 编码加速方法已成为了近些年来分形压缩的一个研究热点。本文尝试着将基于量子行为 粒子群优化算法( p s o ) 口儿钔、模糊聚类优化算法，遗传算法啼1 与四叉树分割方法相结合 应用于分形图像压缩。实验结果表明几类算法的应用对分形图像的压缩速度有较大提 高。 全文共分为六章，首先介绍了图象压缩技术及近十年来图象压缩的研究成果，分 形几何学的创立和发展、分形的几何特征以及分形的测量和性质。分形图像压缩的相关 理论，包括压缩映射、拼贴定理、迭代函数系统及分形图像压缩编解码过程。文中对提 高分形图像压缩速度进行了分析，简要介绍了粒子群算法、基于量子行为粒子群优化算 法及模糊聚类算法，自适应分块的分形图像压缩方法，阐述了四叉树分割方法，将遗传 算法与四叉树分割方法相结合用于分形图像压缩中，并对算法优缺点进行了对比，并将 算法运用于分形图像压缩中，实验结果表明，算法的应用对分形图像压缩速度有一定的 提高，结果表明该算法具有一定的现实意义。最后对全文进行了总结和展望，指出了今 后研究方向及工作展望。 关键词：分形，图像压缩，基于量子行为粒子群优化算法，模糊聚类，遗传算法 a b s t m c ：t a b s t r a c t t h e21s tc e n t u r yi sa na g eo fi n f o r m a t i o n ，p e o p l ew o r k i n gi nt h el i f eo fal a r g en u m b e ro f c o n t a c t sw i t hi m a g e s ，a n ds p r e a da m o n ge a c ho t h e r , i no r d e rt of a c i l i t a t ef a s t e rt r a n s m i s s i o no f i m a g e s ，i m a g ec o m p r e s s i o nt e c h n o l o g yr e s e a r c hh a sb e c o m ev e r yu r g e n t i n 19 8 7b yt h e a m e r i c a nm a t h e m a t i c i a nb a r n s l e ya n ds l o a n l 1 j p r o p o s e df r a c t a li m a g ec o m p r e s s i o nc o d i n g t e c h n o l o g y , s i n c et h e nj a c q u i n 2 1f i r s tr e a l i z et h ef u l la u t o m a t i cf r a c t a lc o d i n ga n db r i n ga b o u t ab r e a k t h r o u g hi nt h ef i e l do ff r a c t a l i m a g ec o m p r e s s i o n f r a e t a li m a g ec o m p r e s s i o n t e c h n o l o g yb a s e do nt h i sa l g o r i t h ma n db e c o m e an e wf i e l d t h ei m a g ec o m p r e s s i o nc o d i n gw h i c hb a s e do nf r a c t a li san e wc o d i n gm e t h o d i tu s e s t h es e l f - s i m i l a r i t ya n dt h ep r o p o r t i o np r o p e r t i e so fi m a g e ；t h r o u g hr e d u c et h eg e o m e t r yo ft h e i m a g et oa c h i e v ec o m p r e s s i o no fi m a g ed a t a i nt h ef r a c t a lc o d i n g ，a l li m a g ei sd e n o t e db ya s i m i l a rc o m p r e s s e da f f i n et r a n s f o r m a t i o na n dt h er e c o n s t r u c t i o no fi m a g ec o m p r e s s i o ni st h e f i x e dp o i n to fc o n v e r s i o n ，t h ep a r a m e t e ro fc o m p r e s s i o na f f i n et r a n s f o r m a t i o nb u i l d u pt h e f r a c t a lc o d eo fo r i g i n a li m a g e f r a c t a ld e c o d i n gi sas i m p l ep r o c e s so ff a s ti t e r a t i v e t h e d e c o d i n gi m a g ei sd e n o t e db yt h es u b c o m p a c tc o d et h a tt r a n s f o r mi n t h er o l eo fa n y a p p r o x i m a t i o nt ot h ei n i t i a li m a g e i nr e c e n ty e a r s ，f r a c t a li m a g ec o d i n gh a sa r o u s e dg r e a ti n t e r e s ti nt h ef i e l do fi m a g e c o m p r e s s i o n a sw ea j ik n o w , al o n g - t i m ec o s ti st h em a i ns h o r t c o m i n go ft h i sc o d i n g t e c h n o l o g y , i th a sb e c o m et h e m o s ti m p o r t a n to b s t a c l ef o ri t sh i g h - p e r f o r m a n c ea n d p r a c t i c a l i t y s ot h ef r a c t a ls p e e du pc o d i n gm e t h o d sh a sb e c o m ea h o tr e s e a r c hp o i n ti nr e c e n t y e a r s t h i sa r t i c l ew i l lt r yt ou s et h ep a r t i c l es w a r mo p t i m i z a t i o n ( q p s o ) t 3 jw h i c hb a s e d o n t h eq u a n t u ma c t ，t h ef u z z yc l u s t e r i n ga l g o r i t h mo p t i m i z a t i o n ，t h eg e n e t i ca l g o r i t h m sa n dt h e q u a dt r e ep a r t i t i o nm e t h o di nac o m b i n a t i o ni nf r a c t a li m a g ec o m p r e s s i o n t h er e s u l t ss h o w t h a tt h ea p p l i c a t i o no ft h e s et y p e sa l g o r i t h m si m p r o v e df r a c t a li m a g ec o m p r e s s i o nr a t eg r e a t l y t h ef u l la r t i c l ei sd i v i d e di n t os i xc h a p t e r s a tt h ef i r s tt h ep a p e rm a i n l yi n t r o d u c e st h e i m a g ec o m p r e s s i o nt e c h n o l o g y , a n dt h ei m a g ec o m p r e s s i o nr e s e a r c hr e s u l tw i t h i nt h ep a s t10 y e a r s ；t h ef o u n d a t i o na n dd e v e l o p m e n to ft h ef r a c t a lg e o m e t r y , t h eg e o m e t r i cf e a t u r e s ，t h e n a t u r ea n dm e a s u r e m e n to ff r a c t a l ，t h et h e o r yo ff r a c t a li m a g ec o m p r e s s i o n ，i n c l u d i n g m a p p i n g ，c o l l a g et h e o r e m ，i t e r a t i v ef u n c t i o ns y s t e ma n df r a c t a li m a g ec o m p r e s s i o nc o d e c p r o c e s s ；i nt h et e x t ，i ta n a l y s i st h ef e a t u r eo ft h ef r a c t a li m a g ec o m p r e s s i o n ，i n t r o d u c e st h e p a r t i c l eg r o u pa r i t h m e t i c ，o p t i m i z e dp a r t i c l eg r o u pa r i t h m e t i cw h i c hb a s e do nq u a n t u m b e h a v i o ra n df u z z yc l u s t e r i n ga l g o r i t h m ，t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ea l g o r i t h m s w e r ec o m p a r e d ，i n t r o d u c e st h ef r a c t a li m a g ec o m p r e s s i o nm e t h o dt h a ts e l f - a d a p t i v eb l o c ka n d t h ef o u r - f o r k - s p l i tc o m m i n u t em e t h o d ，c o m b i n e dt h eg e n e t i ca l g o r i t h m sa n dq u a dt r e e l i a b s t r a c t p a r t i t i o nm e t h o di nf r a c t a li m a g ec o m p r e s s i o n a l lt h ea l g o r i t h mw i l lb ea p p l i e di nf r a c t a l i m a g ec o m p r e s s i o n ，t h er e s u l t ss h o wt h a tt h ea l g o r i t h ma p p l i e dt ot h ef r a c t a li m a g e c o m p r e s s i o ni n c r e a s et h ec o m p r e s s i o nr a t e ，i ts h o w st h a tt h ea l g o r i t h mh a sap r a c t i c a l s i g n i f i c a n c e a tl a s tt h ea u t h o u rg i v e st h es u m m a r ya n do u t l o o k , p o i n t i n go u tt h ed i r e c t i o nf o r f u t u r er e s e a r c hw o r ka n dv i s i o n k e yw o r d s ：f r a c t a l ，i m a g ec o m p r e s s i o n ，q p s o ，f u z z yc l u s t e r i n g ，g e n e t i ca l g o r i t h m i i i 独创性声明 本人声明所呈交的学位论文是拳人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名：e t期o 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名： 导师签名：l 至墨! 逢 日 期： 第一章绪论 1 1 课题研究背景 第一章绪论 我们生活在一个信息时代，信息对我们来说非常重要。尤其是人类进入2 1 世纪以 来，信息就是一个国家能否立足的生命，是一个企业能否成功的关键。人们都在积极地 获取信息，因而信息社会在有了电子计算机后就具有了数字化的特点，数字化信息带来 了信息爆炸。因此如何有效地存储和传输信息就变得非常重要。 信息是以一定的编码形式表现出来的。编码是用一些简单的符号来表达一定的信 息，它要有一定量的基本元索组成。每一种编码形式可以代表一种信息，最简单的如汉 语言文字就是一种编码，信息被相应地编码以后才能便于存储、处理及传输。但是，如 果仅仪用一些最原始的方法进行编码，信息量将会大到让人吃惊的程度。数据量过大的 问题已成为多媒体技术发展及移动通信发展中一个非常棘手的瓶劲问题。它是制约实现 人类在任伺时间、任何地方、能以任何方式与任何其他人进行任何形式的通信的通信理 想的瓶颈。解决这一问题的方法，单纯用扩大存储器容量，增加通信干线的传输率是不 现实的。数据压缩技术是个行之有效的方法。 通过数据压缩手段把信息的数据量压缩下来，以压缩形式存储和传输，既节约了存 储空间，又提高了通信干线的传输效率，同时也使计算机实时处理音频、视频信息，以 保证播放出高质量的视频、音频节目及使视频会议的大规模实现成为可能。数据压缩不 仅是必要的，也是可能的。压缩编码的理论基础是信息论。从信息论角度来看，压缩的 基本目的是去除数据之间的相关性，保留相互独立的信息分量( 也就是保留不确定的东 西，去掉确定的即可推知的信息) ，使用一种更接近信息本质的描述来代替原有的冗余 描述。这些冗余主要包括： ( 1 ) 空间( 相关) 冗余：某些图像的部分区域可能是均匀着色或显示出规则的模式， 如墙壁。静止图像的压缩主要是去除这种空间冗余。 ( 2 ) 时间( 相关) 冗余：运动序列图像各帧之间的差别极小，存在着高度相关性。 运动序列图像的压缩是在去除空间冗余的同时去除这种时间冗余，从而得到较高的压缩 比。 ( 3 ) 信息嫡( 编码) 冗余：由信息论相关原理可知，量化图像数据像素点时按其信息 嫡的大小分配相应比特数即可；但实际中很难得到每个像素的信息嫡，一般是对每个像素 用相同的比特数表示，这样必然存在冗余。信息嫡冗余和空间、时间冗余均取决于图像 数据的统计特性，属统计冗余。 ( 4 ) 结构冗余：有些图像部分区域存在着非常强的纹理结构或各个部分之间存在 着某种关系如自相似性等，这是结构冗余的表现。 ( 5 ) 知识冗余：有些图像中包含的信息与某些先验的基础知识有关，如人脸图像 中，头、眼、鼻和嘴的相互位置等常识信息称为知识冗余。 江南大学硕士学位论文 ( 6 ) 视觉冗余：在多数情况下重建图像的最终接收者是人的眼睛。而它并不是对 于图像中的任何变化均能感知，如图像系数的量化误差引起的图像变化在一定范围内是 不能为人眼所察觉的，编码方案可以充分利用人类视觉系统的这种视觉冗余获得更高的 压缩比。 1 2 国内外相关研究现状 由于分形图像压缩的研究仍处于发展阶段，其原理和实现过程中还存在许多值得探 索的内容，目前许多研究者主要围绕以下几个方面对分形图像的编码进行研究： ( 1 ) 如何建立更有效的匹配块搜索空间： ( 2 ) 寻找对匹配块的更有效搜索方法： ( 3 ) 寻找图像值域块的更合理分割方法： ( 4 ) 寻找应用于匹配块的更简便更精确的仿射变换： ( 5 ) 对分形参数的更有效表示和量化方法： ( 6 ) 充分挖掘利用人眼的视觉特性。 在改进编码方案方面，当前的研究工作主要集中在块分类方案、搜索算法、图像分 割、与其他编码方法结合，以及快速解码算法等方面。具体的研究情况主要有： ( 1 ) 块分类方案 在进行匹配搜索前，先使用特定的分类规则，将定义域块和值域块分成若干类，然 后仅在同类的块之间比较，可以大大缩短编码时间。j a c q u i n 根据视觉几何特性，把相 似块分成s h a d e 块、e d g e 块、m i d r a n g e 块1 6 1 。f is h e r 等人提出一种更精细的根据亮度及 亮度变化来分类的方法【j 刀，把图象块分成四子块，分别计算每子块的象素亮度平均值和 相应的方差值，根据亮度平均值的分布情况将块分为3 大类。在此基础上，再按方差值 的2 4 种排列分成2 4 类。这样就把所有的图像块分成了7 2 类。 ( 2 ) 搜索算法 分形编码由于在寻找最佳匹配块时需要大量计算而使编码时间过长，为了减少计算 量，目前一般采用不搜索或局部搜索方案。m o n r o 8 】等把包含图像块的某一特定相似块 预先作为该图像块的匹配块。n g u y e nt h a 0 1 9 】采用不带对称变换的局部搜索，把匹配限于 图像块附近区域。多分辨率方法【l o j 【9 1 ，它把图像象素灰度值按金字塔形排列，第k 层分 辨率的定义域块由第k + l 层分辨率的4 个定义域块合并后亚抽样得到。搜索首先从较低分 辨率的定义域块开始，然后再在较高分辨率的定义域块中进行。此外，快速卷积法【l2 1 、 不变特征法【1 3 】、群聚法【14 1 、r t r e e 法【1 5 】、树结构法【1 6 1 等也是提高搜索速度的行之有效 的策略。 ( 3 ) 图像分割方案 图像的分割对整个压缩结果有较大影响。当前有许多分割方法，包括：四叉树分割 f 1 7 1 、h v 分割法( h o r i z o n t a l v e r t i c a lp a r t i t i o n ) 1 1 8 l 、多边形分割【1 9 】、三角分割法【2 0 】等。 四叉树分割是指对于一给定的图像块，如果没有找到满足误差要求的相似块与之匹配， 则该图像块分成4 个子块，反复如此匹配、划分，直到图像块尺寸达到了预先设定的图 2 第一章绪论 像块最小尺寸为止。h v 分割法则是将图像分割成矩形块，如果找不到满足误差要求的 相似块与之匹配，则图像块按垂直水平方向分成两个矩形块。多边形分割是将图像不同 的多边形，使之符合不同的要求。三角分割法是指使用三角测度作为分割准则，把块分 成三角形。 ( 4 ) 与其他编码方法结合 考虑到分形图像编码存在编码时间过长、图像细节易受损失等缺陷，为了改善编码 质量，加快编码速度，可以把分形与其它编码方法相结合。b a r t h e l 提出了f t c 方案( f r a c t a l b a s e dt r a n s f o r mc o d i n g ) 【2 1 1 ，将分形与变换编码结合在一起。y z h a o 和b y u a n 在文献1 2 2 1 中用d c t 把图像块、相似块变换到频域，用分形方法对每个图像块进行初次编码，然后 再用d c t 对图像块与分形近似块的误差值进行第二次编码。这样“用d c t 保留住了图像 细节，使得在较高压缩比下仍有很高的保真度 。在文献【2 3 】中将分形与矢量量化v q 结合 也能产生一定的效果。分形与小波相结合是当前研究的一个方向【2 4 】，应用小波变换将图 像解析成多分辨率的子图像，在相应尺度和方向的子图像上构造不同维数、不重叠的图 像块，在下一级更低分辨率子图像上构造定义域块。最低分辨率的子图像用p c m 单独编 码，其它和传统分形编码一样。分形与小波相结合的方法能带来较高的压缩比和较好的 图像质量，但编码时间仍然较长。 ( 5 ) 快速解码算法 标准的解码方法是对任意初始图像用压缩过程产生得分形码进行迭代，直至重构图 像收敛到理想的水平。b a h a r a v 等提出了一种基于p i f s ( p a r t i t i o n a li f s ) 分层解释的分 解码算法【25 。，该算法的迭代先在图像的粗糙分辨率上进行，一旦达到p i f s 在粗糙分辨 率上的定点，就使用一决定性算法找到它在任意高分辨率上的定点，由于是对低维矢量 进行迭代，从而使计算得到节省。此外还有去均值解码算法、非迭代算法等。 1 3 本文研究内容 本文介绍了分形几何的产生、发展，以及分形图像压缩的最新进展，阐述了分形图 像压缩的相关理论，包括不动点定理、迭代函数系统及拼贴定理。结合分形图像压缩的 特点，介绍了两个聚类算法，并对其优缺点进行了比较分析。本文从提高分形图像压缩 的速度出发，为了进一步将匹配块进行匹配优化，将两种聚类算法应用于分形图像压缩， 实验结果表明，两种算法对提高分形图像压缩速度有较大提高。 1 4 本文主要工作和组织 全文共分六章。 第一章简要介绍了图象压缩技术，并介绍了近十年来图象压缩的研究成果。 第二章介绍了分形几何学的创立和发展、分形的几何特征以及分形的测量和性质。 第三章介绍了分形图像压缩的相关理论，包括压缩映射、拼贴定理、迭代函数系统 及分形图像压缩编解码过程。 江南大学硕士学位论文 第四章介绍了粒子群算法、基于量子行为粒子群优化算法及模糊聚类算法，对算法 优缺点进行了对比，并将算法运用于分形图像压缩中，实验结果表明，算法的应用对分 形图像压缩速度有一定的提高。 第五章介绍了自适应分块的分形图像压缩方法，阐述了四叉树分割方法，将遗传算 法与四叉树分割方法相结合用于分形图像压缩中，对实验结果进行了比较分析，结果表 明该算法具有一定的现实意义。 第六章是全文的总结和展望，对全文工作做一总结并指出了今后研究方向及工作展 望。 4 第二章分形几何学 第二章分形几何学 2 1 分形几何的诞生与发展 大自然中的所有形状和人们考虑的一切图形可以分为两大类，一类是具有特征尺度 的，例如人的身高，建筑物的长、宽、高等等。另一类是没有特征尺度的，即必须同时 考虑从大到小的许许多多尺度，例如天空中的云彩、地面上的海岸线和北方冬季玻璃窗 上的冰霜，这些所谓“无标度”的几何体，其实就是分形。1 9 7 5 年，美国科学家m a n d e l b r o t 发表的专著：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 啪1 标志着分形理论的诞生。从 二十世纪七十年代中期到现在的3 0 多年里，分形理论取得了巨大的成功。首先，分形 理论在现代非线性科学研究中影响巨大，涉及的领域不只是自然科学领域，如地理、地 质、工程技术、生物科学、材料科学等，而且在社会科学与人文科学领域，如经济学、 电影制作等领域也受到广泛青睐。特别是随着计算机技术的迅速发展，分形思想在模式 识别、图像处理、信号处理以及艺术制作等领域获得了巨大的成功。 分形理论的发展过程大致可以分为以下三个阶段： 第一阶段：分形集合存在性的验证阶段( 1 8 7 2 - 1 9 2 5 年) 。 分形几何的雏形可以追朔到1 8 7 5 年，德国数学家维尔斯特拉( w e i e r e s t r a s s ) 构造 了处处连续但处处不可微的函数，集合论创始人康托( c a n t o r ，德国数学家) 构造了有许 多奇异性质的三分康托集( 见图2 - i ) 。1 8 9 0 年，意大利数学家p e a n o 构造出了能够通 过某个正方形内所有点的曲线。这与传统的维数观念矛盾，从而人们提出应正确考虑以 往的长度与面积的概念。1 9 0 4 年，瑞典数学家科赫( y o nk o c h ) 设计出类似雪花和岛屿 边缘的一类曲线。1 9 1 5 年，波兰数学家谢尔宾斯基( s i e r p i n s k i ) 设计了象地毯和海绵 一样的几何图形。这些都是为解决分析与拓朴学中的问题而提出的反例，但它们正是分 形几何思想的源泉。1 9 1 0 年，德国数学家豪斯道夫( h a u s d o r f f ) 开始了奇异集合性质与 量的研究，提出分数维概念。1 9 2 8 年布利干( b o u l i g a n d ) 将闵可夫斯基容度应用于非整 数维，由此能将螺线作很好的分类。1 9 3 2 年庞特里亚金( p o n t r y a g i n ) 等引入盒维数。 1 9 3 4 年，贝塞考维奇( b e s i c o v i t c h ) 更深刻地提示了豪斯道夫测度的性质和奇异集的分 数维，他在豪斯道夫测度及其几何的研究领域中作出了主要贡献，从而产生了豪斯道夫 一贝塞考维奇维数概念。以后，这一领域的研究工作没有引起更多人的注意，先驱们的 工作只是作为分析与拓扑学教科书中的反例而流传开来。 江南大学硕士学位论文 。 专吾 睾吾 詈 t o 丐百了 丐虿 丐 2 一o 1 舭2 舡3 ， j p s 图2 - 1 三分康托集 f i g 2 1c a n t o rt h r e es e t 1 9 6 0 年，曼德布罗特在研究棉价变化的长期性态时，发现了价格在大小尺度间的对 称性。同年在研究信号的传输误差时，发现误差传输与无误差传输在时间上按康托集排 列。在对尼罗河水位和英国海岸线的数学分析中，发现类似规律。1 9 6 7 年，他在美国 的科学杂志上发表了一篇题为英国的海岸线究竟有多长? 的论文。这篇论文对 海岸线的本质作了独特的分析，震惊了当时的整个学术界。这篇论文也成为了作者曼德 布罗特思想的转折点，分形的理论就从此萌芽并迅速发展起来。总之，在第一阶段，人 们已经认识到分形集合的存在性，并为讨论这些问题提供了最基本的工具。 第二阶段：分形理论的创立( 1 9 2 6 1 9 7 5 年) 。 在这一阶段，人们在总结第一阶段的研究成果的基础上，进行深入分析总结，将研 究范围也扩展到了数学的许多分支里，取得了丰硕的成果。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 嘶3 ，它集中了1 9 7 5 年以前曼德布罗 特关于分形几何的主要思想，它将分形定义为豪斯道夫维数严格大于其拓朴维数的集 合，总结了根据自相似性计算实验维数的方法，这标志着分形几何作为一门学科正式诞 生。 我们把具有下面典型性质的集f 称为分形： ( 1 ) f 具有精细的结构，即它包含有任意小比例的细节： ( 2 ) f 具有某种自相似的结构，它可能是精确的，或是近似的，也可能是统计意义 下的自相似： ( 3 ) f 的分维( 以某种方式定义) 严格大于它的拓扑维： ( 4 ) 存在对f 的简单算法( 低信息量) 描述。例如可以由迭代产生。 上述四条性质中，最重要的是第3 条。 下面图形都是分形图形，图2 - 2 为k o c h 雪花，表现出完全的自相似的特性。图2 3 为s i e r p e n s k i 三角形，在s i e r p e n s k i 三角形中每个小三角形都是大三角形的更小版本。 但是，这里的自相似体现在：每一个边都是由它的更小版本组成，而整个图形并没有重 复。 6 玉一五一五一 一 一 一 一 第二章分形几何学 图2 2k o c h 雪花 f i g 2 - 2k o c hs n o w f l a k e 图2 - 3s i e r p e n s k i 三角形 f i g 2 3s i e r p e n s k it r i a n g l e 第三阶段：分形几何迅猛发展时期( 1 9 7 5 年一现在) 。 在这个阶段，分形几何不仅在理论上得到了进一步的完善，而且它的研究内容也得 到了扩展。1 9 8 2 年曼德布罗特的历史性著作大自然的分形几何学与读者见面，在 曼德布罗特看来该书是分形理论的“宣言书”，给分形理论研究者提供了一部“圣经”。 该书图文并茂，从分形的角度考察了自然界中的诸多现象，引起了学术界的广泛关注。 此后，一直持续的分形热吸引了全世界众多科学家和学者，他们在各自领域中的研究工 作，使分形理论遍地开花。如随机分形、多重分形、迭代函数系统理论、复动力系统的 吸引子理论、分形的数值方法、随即布朗运动和布朗曲面等。如今，分形理论的应用己 经扩展到了几乎所有的学科领域，如信号处理、分子化学、材料科学乃至经济、艺术等 领域，并且成果显著。 到目前为止，分形几何学已经成为探索复杂和无序现象的强有力的数学工具，它同 孤立子理论、混沌理论一起被誉为2 0 世纪后期非线性科学的三大理论突破。在理论方 面，维数的估计与计算的算法、分形集的生成与结构、分形的随机理论、动力系统的吸 引子理论与分形的局部结构已获得较深入的研究成果，其势方兴未艾。由于分形几何极 7 江南大学硕士学位论文 强的应用性，它在物理的相变理论、材料的结构与控制、力学中的断裂与破坏、高分子 链的聚合、酶的生长、模式识别、自然图形的模拟、图像压缩处理、自动控制及系统建 模等领域都得到了成功的应用。有关专著纷纷问世，研究成果的数量以几何级数增长， 国际专题会议此起彼伏。当计算机科学特别是计算机图形学应用到分形领域后，它为分 形的研究提供了必要的、有效的工具，并且促使分形理论和应用有更多的新发现。 值得注意的是，近年分形理论的应用发展远远超过了理论的发展，并且给分形的数 学理论提出了更新更高的要求。各种分形维数计算方法和实验方法的建立、改进和完善， 使之理论简便，可操作性强，是分形的科学家们普遍关注的问题。而在理论研究上，建 立既严格又简单的维数理论及计算方法、分形重构( 即求一动力系统，使其吸引集为给 定分形集) 、j u l i a 集和m a n d e l b r o t 集及其推广形式的性质、动力学特征及维数研究 将会成为数学工作者们十分活跃的研究领域。多重分形理论的完善、严格以及如何用这 些理论来解决实际问题可能会引起科学家们广泛的兴趣，而动力学特征、相变和子波变 换可能会成为其中的几个热点。 分形几何的诞生3 0 多年来，它对各学科的影响是极其巨大的。卷入分形狂潮的除 数学家和物理学家外，还有化学家、生物学家、地貌学与地震学家、材料科学家、哲学 家、经济学家乃至作曲家、画家和电影制作家都蜂拥而入。著名的电影“星球大战就 是用分形技术创作的。由于分形的重要特征是自相似性，所以信息科学家对其情有独钟， 分形图像压缩被认为是最具前景的图像压缩技术之一，分形图形被认为是描述大自然景 色最诱人的方法。美国物理学家w h e e l e r 说：“可以相信，明天谁不熟悉分形，谁就不 能被认为是科学上的文化人。 2 2 分形的几何特征 分形作为几何对象，首先是破碎的、不规则的，但不是所有破碎的、不规则的形状 都是分形，一般来说，分形具有自相似性。但分形理论发展到今天，已经不仅限于研究 对象的自相似性质了，如果一个对象的部分与整体具有自仿射变换关系，我们也可以称 它为分形。今后，条件可能进一步拓宽，只要是部分与整体以某种规则联系起来，通过 某种变换使之对应，我们都可以将其看成是分形，因为分形的本质就是标度变换下的不 变性，而这层意思是可以拓宽的。 ( 1 ) 自相似性 白相似( s e l f - s i m il a r ) 便是局部与整体的相似。从严格意义上讲，局部是整体的缩 影。即将一图形任意地划分为许多小的图形，而各个小图形都是原来图形的复制品。下 面举几个典型的例子来理解对象的自相似性。 i ) c a n t o r 三分集 集合论创始人，德国数学家康托( g c a n t o r ，1 8 4 5 1 9 1 8 ) 在1 8 8 3 年曾构造了一种 三分集，其几何表示如下：取一条欧氏长度为l 0 的直线段，将这条直线段三等分之后， 保留两端的线段，将中间的一段扔掉，如图2 1 所示n = l 的操作；再将剩下的两条 直线段分别三等分，然后将其中间部分扔掉，如图2 1 所示n = 2 的操作，以此类推， 8 第二苹分形几何学 直至无穷，便形成了无数个尘埃似的点，这便是c a n t o r 三分集。它们的数目无穷多， 但长度为零。这种构造的自相矛盾性质曾使1 9 世纪的数学家感到困惑。但我们从几何 关系来看，最终生成点的分布是局整相似的，甚至，这个过程中每一步图形之间也是局 整相似的，这便是自相似。 i i ) k o c h 曲线 1 9 0 4 年，瑞典数学家科赫( h y o nk o c h ，1 8 7 0 一1 9 2 4 ) 构造了一种“妖魔曲线”，被 称为k o c h 曲线。其构造过程如下：取一条欧氏长度为l o 的直线段，将其三等分，保 留两端的线段，将中间的一段改成夹角为6 0 0 的两个等长的直线，如图2 - 2 所示n = l 的操作。将长度为l 0 3 的的直线段分别进行三等分，并将它们中间的一段均改换成夹 角为6 0 0 的两段长为l o 9 的直线段，得到如图2 2 中n = 2 的操作。重复上述操作直 至无穷，便得到一条具有自相似结构的折线，这便是我们所说的k o c h 曲线。 i i i ) s i e r p i n s k i 垫片 以上两个自相似图形都是基于一条欧氏直线段生成的，c a n t o r 三分集是将线段删 去一部分，最终得到的是一个离散的点集，而k o c h 曲线是将线段增加一部分，最终得 到的是一个折线集。波兰数学家谢尔宾斯基( w s i e r p i n s k i ，1 8 8 2 1 9 6 9 ) 于1 9 1 5 年给 出了一个从平面二维图形出发做直线的有趣例子。所构造的s i e r p i n s k i 垫片相当于将 上述构造方法推广到平面上，其初始图形是一个等边三角形面，构造过程如下： 首先，我们将这个等边三角形面四等分得到4 个小等边三角形面，去掉中间的一 个( 图2 3 中大网格三角形面) 。将剩下的3 个小等边三角形面分别四等分，再分别去 掉中间的一个( 图2 3 中较大的3 个网格三角形面) 。重复上述操作直至无穷，便可以 得到s i e r p i n s k i 垫片( 图2 3 为n = 3 的图形) ，可以看出它的每一小部分在结构上 都与整体相同，这也是一个典型的自相似图形。 ( 2 ) 自仿射性 自仿射性是自相似性的一种拓展。如果将自相似性看成是局部到整体在各个方向上 的等比例变换的结果的话，那么，自仿射性就是局部到整体在各个方向上的不等比例变 换( 移位、旋转、缩放等) 的结果。前者称为自相似变换，后者称为自仿射变换。 ( 3 ) 精细结构 分形还有一个更重要的特征，即精细结构。在理论上，k o c h 曲线是按一定规则无 限变化的结果，所以，假如用一个数学放大镜看k o c h 曲线的话，无论放大多少倍，都 能看到里面还有与整体相似的结构。这一点非常接近于自然界中的对象，也符合中国古 代的哲学思想：“一尺之捶，日取其半，万世不竭”( 庄子天下篇) 。 在这里，我们不打算讨论物质是否无限可分，我们只注意到分形和自然对象都具有 极多层次的结构，这是分形体最基本的特征。但是，自然界中的对象与数学中的分形还 是有所不同。从严格意义上说，分形都是变化到无穷小尺度时才产生的，而自然形态只 是停留在一定层次范围才可以用合理的分形模式来考虑。也就是说，自然界中的分形特 征只存在于某段层次区间内，而且这段区间内的形态结构也不是完全自相似的，它只具 有统计意义上的自相似性，所以在对自然界的分形研究中，一般我们只关心有限层次的 9 江南大学硕上学位论文 自相似性或自仿射性结构。 2 3 分形的测量 2 3 1 分维概述 维数是几何体的重要特征，是一种最基本的几何不变量。研究表明，分维也是分形 很好的不变量，用它可以把握住分形体的基本特征。那么，什么是分维呢? 在欧氏几何 中，维数定义为描述空间中一个点的位置所需要的独立坐标数目或连续参数的最小数 目。于是，点是0 维的，线是l 维的，面是2 维的，立体是3 维的。好像维数一定 是整数，其实不然。让我们来看这样一个例子：对单位长度的线段、正方形、立方体， 当边长变成原来的1 2 时，原线段、正方形、立方体分别包含2 1 、2 2 、2 3 个小线段、 正方形、立方体。这里我们发现一个小秘密，2 上面的幂，恰好是相应的线段、正方形、 立方体的维数。写成通式为： n = k o ( 2 1 ) 其中，k 为边长缩小的倍数，n 为边长缩小的k 倍后新形体的个数，则d 便是形体所 具有的维数。将式( 2 1 ) 的两边同时取对数有 1 9n = dl gk = d = l gn l g k ( 2 2 ) 从式( 2 2 ) 可以看出，维数d 未必一定是整数。所以说，分数维是有权利存在的。可是 分数维有必要存在吗? 我们来看看下面的例子： 一条线段，如果我们用0 维的点来量它，其结果为无穷大，因为线段中包含无穷 多个点；如果我们用一块平面来量它，其结果是0 ，因为线段中不包含平面。那么，用 怎样的尺度来量它才会得到有限值哪? 看来只有用1 维的单位线段来量它才会得到有 限值。于是，可以得出一个结论： 若测量尺子的维数小于被测对象的维数时，其测量结果是无穷大：若测量尺子的维 数大于被测对象的维数时，其测量结果是o ；只有测量尺子的维数与被测对象的维数相 等时，其结果才是有限值，并且这个维数一定在上述两个维数之间。 比如，对k o c h 曲线，用1 维的线来测量它，其结果是无穷大，因为k o c h 曲线迭代 到无穷多次时，k o c h 曲线将是无限长；若用2 维的小平面来测量它，其结果将是0 ， 因为k o c h 曲线中没有平面。看来只好选一个大于1 维且小于2 维的尺子来测量它， 才会得到有限值。如此说来，k o c h 曲线自身的维数是一个分数，所以存在分维，实际 上，它的分维是1 2 6 1 9 。 分形理论认为维数也可以是分数，是为了定量地描述客观事物的“非规则 程度， 1 9 1 9 年，数学家从测度的角度引入了维数概念，将维数从整数扩大到分数，从而突破 了一般拓扑集维数为整数的界限。 目前，分形维数是一种比较分形的客观工具，是目前刻画分形不规则性的一个重要 指标，许多应用实例都表明这种整维数概念延拓的合理性。分形维数目前已有多种定义， 大量能够用于估计分形维数的方法都已在m o n d e l b r o t 的专著【27 j 中讨论，h a u s d o r f f 维 l o 第二章分形几何学 数、自相似维数以及盒维数是其中三种重要的维数。h a u s d o r f f 维数是基于h a u s d o r f f 测度建立起来的一种分形维数，是分形几何维数理论的基础，也是理论较为完善的一种 维数。但是，计算一个分形的h a u s d o r f f 维数往往是复杂而又困难的，这种计算上的困 难极大地限制了h a u s d o r f f 维数的实际应用。像c a n t o r 集、k o c h 曲线和s i e r p i n s k i 三 角这些具有严格自相似的分形