（计算机科学与技术专业论文）分形图形生成研究.pdf

分形图形生成研究 摘要 分腹f t a l ) 是二十i 趾纪新出现的隶属非线性领域的一个分支学科，它使传统数学中 无法表达的形态如山脉、树术等得以逼真的表达。分形几何学在图象数据压缩、模拟自 然景观、艺术图案设计、分形生长以及混沌动力系统的研究等方面肯着广泛的应用，并 已m 现许多研究成果。 m 分形迭代函数系统( i f s ) 的各种算法，依据i f s 码生成了s i e r p i n s k i 二角形、分 形l i j 、分形树、三维树叶、果斟等各种分形图。而其反问题，即如何从已知图形或已有 概念、轮廓中产生、获取 p 8 码则更为重要，冈此，对i f s 绘制图形的特性进行研究以 及引陇i i 喝迭代规律即分形图形生成规律是 分必要的。为此，论文薛先通过对 f s 码 盼实验分析，将树叶迭代码j 三角形迭代码之问逐渐缩小差距，实现r 幽树叶过渡到三 角形的一些巾间演变图形。其次，针对同一i f s 迭代码两次迭代绘制得到的分形图并非 完全相同这一问题展开研究，提出了i f s 分形覆盖相交交点变化曲线的概念，给出了覆 盖相交交点变化曲线的绘制算法，在此基础上进一步研究了分形覆盖相交交点变化f 1 线 的变化率情况，得到了分形覆盖相交交点变化曲线宏观卜比较光滑，但实际上小范围内 异常波动的实验结果。最后，用j u l j a 集的思想实现r 多幅艺术图案的设计j 绘制，并 将绘制的多种分形图进行_ r 综合运用，实现了虚拟景观的生成。 关键词：分形：迭代函数系统l f s ；i f s 迭代码；j u ii a 集 分形圈形生成研究 a b s t r c t i ：r a c t a l isa1 3 e wb r - a 1 3 c h ( ) rt h er e i e a c ef o r mt h ea r e ao fn e n l i n e a ri nt h e t w 0 1 3yc e n t u r y w h i c hc a ne x p r e s ss u c ha sm o u n t a i n ，t t e ea n ds oo nl i f e li k e lyt h a tc a n tb ee x p r e s s e di nt h et r a d ilfo n a lm a t h e m a t i c s f r a c t a 】isw i d e ly l i m e dinm a n yr jcld sm u c ha st h e im a g ed a t ac o m p r e s sio n ，s i m u la t i o no fn a t u r a l s c e n e r y j ；r a c t a lg e c _ n e t r y sg r o w i n ga n dt h er e s e a r c h e ro f c h a o sm e t j l i t ys y s t e m a n ds o0 1 3 b a s e do ni f sc o d e sa n dt h ea l g o r i t h mo f f s t h ef r a c t a jp i c t u r e so f s i e r p i n s k it r i a n g l e ，f r a c t a lm o u n t a i n ，f r a c t a ll f o o ，t h r e e d i m e n s i o n a lt e a v e s ， o r c h a r da n ds oo na r es i m u l a t e db yv bp r o g r a m m i n g b u tt h er e v e r s eq u e s t i o njs m e r ei m p o r t a n t ，t h a ti s ，t oo b t a i ni f sc o d e rf r o mt h a th a v ea 1r e a d ye x s i t e di m a g e ， c o n c e p ti o n o r o u t l i n e d t h e r e f o r e ，j li s v e r yn e c e s s a r y t or e s e a r c ht h e c h a r a c t e r is t ica n dl o o kf o rt h ei t e r a t e dr e g u l a t i o no fi r s f i r s t l y b yt h e e x p e r l m e l 3 ta n da n a l y s i s ，t h ef r a c t a li m a g e sa r er e a l i z e db e t w e e nt h et r e ea n d t h et r i a l 3 9 i et h r o u g hc o n t r a c tt h ed if f e r c n c eo ft h e i ri p sc o d e s g r a d u a l i y s e c o n dly ftisn o tt h es a m ef r a c t a ld i a g r a mb yt h es a m ec o d e so fi f st op r o d u c e f r a c t a ld i a g r a m t h et w og r a p h sa r e e x t r a o r d i n a r ys i m 1 a r , b u tt h e ya r ed i f f e r e n t i nd e t a f l r h ep r o m e mj sr e s e a r c h e da n dt i l e a l g o r i t h m w h i c hc a l c u l a l e st h e in t e r s e c t i o np o in t so ft w og r a p h sc r e a t e db yt h es a m ec o e f f i c i e n to f t h ei f si s p r o p o s e d t h e c u r v ed e s c r i b e d c h a n g i n g o t t h ei n t e r s e c t i o np o i n t sn u m b e r 沁d f a w n t h ec o a t iu s i o ni st h a tt h ec u r v ef l u c t u a t e si nt h et i n yr a n g ea n di ss m o o t hw h e n jl iss e e aa saw h o l e i nf a c t ，t h ec u r v ei saf r a c t a lc u r v e l a s t l y w it hc o m p u t e r e x p e r i m e n t sa n dj u l i as e ti nb r o a ds e n s e ，t h ed e s i g no ft h ep a t t e r no fv a t i o n s a r t sc a l lb ey e a if z e d f i c t i o n a ln a t u r es i g h t sa p p e a rb yc o m p o u n d i n ge a c hs i n g l e p i c l u r e k e yw o r d s ：f r a c t a i ：i t e r a t e df u n c t i o ns y s t e mi f s ：i f sc o d e s ：j u li as e t i j 分形图形牛成研究 1 绪论 介绍课题的研究背景、国内外的研究状况以及进一步研究的必要性，阐明课题所做 的工作。 1 1 课题的研究背景 证人类的q ! 产实践和科学研究中，人们运用传统的几何学如欧几里德几何，解析几 何，微分儿何等来有效地描述客观三维世界巾的许多对象，如各种t 业产t 锚的形状，建 筑物的外形和结构等。 然而，随着计算机科学的迅速发展，人们在使用计算机深入地探讨一系列问题的过 程中逐渐感主u ，用传统的儿何学已4 i 能有效地描述某些自然界大量存在的对象，如：海 岸线，山形，河j i i ，岩，断裂，树木，森林，云团，闪电等等。它们都是非规则形状 的物体，_ j 欧几罩德几何学是无能为力描述的。在自然景物的模拟以及动画的制作中， 如果用直线，圆弧，样条曲线等去建模生成，其逼真程度会非常差。另外，在科学电j 究 中，对许多非规则对象建模分析，如星系分布，凝聚生长，渗流，金融市场的价格浮动 等复杂对象，都需要一种新的几何学来进行描述。 j 求能反映客观世界故有特征的数学摸型的探索，在1 9 7 3 年由m a n d e l b o r t 取得， 突破。分形由m a n d e l b o t t 定义为“组成部分与整体相似的形体叫分形”，分形存秤 于各种自然现象中。“。随着分形理论的发展，分形几何作为- - f 以非规则几何彤状 为研究对象，用来描述大自然的儿何学而在各个学科上得至0 广泛应用。随着计算机的普 遍应用，分形几何被应用于各个领域。 侄客观世界的几何描述方面，分形j l 何学能为自然界中存在的各种景物提供逼真的 摘述。这些自然景物形态复杂，不规则，用传统的几何工具如动画软件和实体造型1 二具 进行描述遇到了极大的凼难，而用分彤模型却能很好地描述自然景物，凶为自然界中的 许多实际景物本身人体上就是分形，分形图形能很逼真地描述自然景物，获得令人惊奇 的自然景物模拟图像，如云彩、山脉、海岸线、森林、沼泽、流体、星体等等。1 9 8 8 年 b a r n s l e y “1 提出了用迭代函数系统模拟自然景物的模型，用分形方法模拟自然景物，动 画制作，建筑物配景以及影视特殊效果景物生成，目前已经可以达到以假乱真的程度。 在气象学巾，人们运用分彤理论来分析和研究云系的形状，降雨的模式和强度等。分彤 j l 何还可用于研究地表面的起伏，如山川，地形，地貌的形态以及它们产生，发展，分 布的规律。分形儿何还被削在“人工生命”领域的研究中，即在计算机上_ h j 分形生长模 型模拟“人工牛命”。分彤以其独特的手段来解决整体与部分的关系问题，利用空间结构 的对称性和自相似性，采 = | j 各种模拟真实图形的模型，使整个生成的景物呈现出细节的 尢穷凹归的性质，丰富多彩，具有奇妙的艺术魅力。所生成的景物中，可以有结构性较 强的树、l 峰，也可以足结构性较弱的火、厶及烟等。生成图形的关键是要有一个合适 的模型来描述对象，根据所选择的分形造型的模型不同，产生分形图形的方法有l 系统、 迭代函数系统i f s 、复分形图生成，粒子系统模型、随机插值法等等。 在同外，分形几何已被良接运用于岂术作品创作和影视制作巾。在i i l e r t l e t 网上， 你很容易就可以获得一些用分形方法制作的艺术图片，从中你可以真止感受到“分形之 分形阁形生成研究 荚”( t h eb e a u t yo ff r a c t a ) 。然而在幽内，分形存其实际应用方面发展却很缓陧。分 形方法有待于进一步推广和使用，特别是在和艺术结合方面。 可以看到，随着计算机图形学的研究及应用的拓广，对分形几何的形f 究具有很大的 现实意义柑理论价值。这有助于将分彤理论实际应用于科研，生产，生活的各个方面， 有助于让人们从分形和分数维的角度重新考虑现实巾的许多问题，使某些抽象的概念和 复杂的过程视觉形象化，使人们的形象思维和逻辑思维有机结合，以便更有效地探讨其 内在水质和规律性，从而达到启迪思维，促进科学创造的目的。 12 分形几何国内外研究状况 1 2 1 典型的分形曲线与分形集“ 1 9 世纪以来，一些著名的数学家在对曲线的深入倒惋中，创立r 一系列结构，形态 与传统几何曲线不同的所谓“病态”曲线，如y o nk o c h 曲线，p e a n ol f f l 线，还有c a n t o r 集，以及s i e r p i n s k i 填料，地毯和海绵等。分形几何创立后，人们发现，这些曲线正是 大自然中俯拾皆是的儿何对象，例如，海岸线，河川，地形边界曲线，断裂，闪电，山 形轮廓等等，它们都是分形曲线。 ( 1 ) v o nk o c hj f i 线。此曲线处处连续但处处不光滑，不可微。从一个简单图形出发， 按一定生成规律不断进行变形便可获得此曲线。若源图为正二角形，则曲线形状象雪花， 故又称k o c h 雪花曲线。 ( 2 ) p e a n o h i b e r t 曲线。此曲线维数为2 并能“充满整个平面”。具有多种形态。 ( 3 ) c a n t o r 集。它是类处处稀疏的儿何对象，是一个无穷点集。有三等分c a n t o r 集平叫义c a n t o r 集之分。 ( 4 ) s i e r p i n s k i 三角形，地毯与海绵体。它时波兰数学家w a c a ws i c r p i n s k i 于1 9 1 6 年提出。s i e r p i n s k i 三角形由一个二角形被不断挖去中间的小三角彤耐生成。s i e r p i n s l d 地毯f n 一个止方形被不断挖去中问的小正方形而生成。s i 哪a i n s k i 海绵体由一个i f 方体被 小断挖去体中心的小正方体和六个面中f i j ：l 的小正方体而生成。 ( 5 ) 海岸线，河川，山形的曲线。用巾点随机位移和中点细分内插分形曲线的方法来 牛成。 1 2 2l 系统 l 系统是生物学家l i n d c n m a y e r 于1 9 6 8 年从植物形态学角度提出的一套明以描述植 物树木的方法，开始时只着重于植物的拓扑结构，即植物组件之间的相邻关系，后来才 把几何解释加进描述过程，形成后来的l 系统。这个系统的高度简洁性和多级结构，为 描述植物树木生k 和繁殖过程的形态和结构特征，提供了行之有效的理论和方法。l 系 统不但能描述植物，而且其构图方法也可阁来绘制各类有规则分形曲线及其它形状。正 因为如此，广大的中外学者对运用l 系统建模和应用进行了更为深入的研究1 与拓展 啦! 0 1 2 3i f s 迭代函数系统 分形图形生成研究 迭代函数系统( i t e r a t i o nf u n c t i o ns y s t e m ，简称i f s ) 足分形几何学的重要分支，它 也是分彤图像中最富生命力并具有广阔应用前景的领域之一。i f s 是m e b a m s l e y 于1 9 8 5 年发展的一个分形构形系统。针对这个系统，b a m s l e y 提出了一整套理论，发展 广一系 列算法规则，并：将之运用于许多方面，做r 大量开创性的工作。i f s 的理论包括以下几 方缸的内容“：压缩映射，度鼋空间、不变紧缩集的存在以及钡6 度理论等。这代函数 系统在一人类物体的建模问题中具有很大的优势，特别是对自然景物的汁算机模拟生成 优势更为明显。实际卜f ，只需给出几个仿射变换的系数，就可基本确定一个物体的迭代 函数系统。正闪为如此，i f s 在图形学中有着广泛的应用，中外学者做r 大量的研究和 探索。其中，可视化技术的研究由2 d 分形对象拓广到3 d f r a c t a l1 7 - 1 8 j 由i f s 研究的自 相似的分形图扩大了其应用范围，i f s 变换不必仅限于仿射变换“9 。；在用腰s 建摸的研 究中，实现r 对原图形的几何变换f 2 0 ；, 将i f s 中的线形变换推广到非线形变换l 2 1 对 自然景物计算机生成问题的探讨，其建摸方法亦由二一维推广到三终2 f ；很多学者致力于 新i f s 分形图象的获取与分析以及i f s 快速生成算法的研究 2 3 - 3 1 3 。 另外，由fi f s 代码可以描述形态各异的对象，这就意味着可以用极少晨的数据， 就可描述复杂的图像图形玲，因而i t s 具有很强的图形数据压缩能力。将之用于图像 矗缩的潜力臣大，这使它倍受各圉研究者关注。它对于数据压缩以及图像通讯等领域的 研究无疑是一股强大的新鲜m 液，必将有力促进专 关领域的发展。许多研究者投入到分 形编码方法的研究中，使分形编码技术”得到迅速发展。从而产卜更多更有效的编码 锌法：”“。 j 2 4 复动力系统的分形集 目前，复动力系统的分形集合卜要包括m a n d e l b r o t 集和j u l i a 集。m a n d e l b r o t 集是分 形中最著名的分形集合，它是分形创始人m a n d e l b r o t 在非线性领域巾作出的杰出贡献。 j u l i a 集是在本世纪初法国数学家g j u l i a 和r f a t o u 分别研究过的一种多项式和有理函数 的迭代，当时由捌央乏相应的图形工具而使研究中断，直到计算机图形学的出现才使其 重凝生机。m a n d e l b r o t 集和j u l i a 集都是通过在复平面中0 ( z 心2 + c 的反复迭代而得到 的点的序列，其中c 和z 均为复数。研究表明，m a n d e | b r o t 集是j u l i a 集的一个总纲， 而j u l i a 集是m a n d e l b r o t 集的边界。由j u l i a 集与m a n d e l b r o t 集旱现在人们面前的美妙图 象令艺术家们叹为观止，将这种艺术图形用于纺织印染、告印刷、工业设计、邮票制 作、服装设计及计算机教学等方面，其经济效益和衬：会效益均具有广阔的应用前景。因 此，它吸引了广大的中外学者倾心钻研其中的奥妙所在，人们致力于对j u l i a 集及其拓广 的研究”“。其中包括生成算法、相关论证、三维分形图的生成及其进一步的拓广：对 j u l i a 集的映射的研究也有进一步的发展，其中有高阶j u l i a 集生成方法的研究，将二 次复映射拓j 。到高阶复映射；将一：阶j u l i a 集的算法逃逸时间算法、随机反函数算法 及旋转逃逸时间算法拓广到高阶和广义的j u l i a 集以及开关j u l i a 集的分形图中4 5 4 珈。； 而通过计算机实验方法又将j u l i a 集的研究拓广到了超越函数嘞 ；以分形和j u l i a 集图像 为基础进行艺术设计的这一研究领域，为入门架起了又一座通向艺术殿堂的桥粱，这方 而的研究更足方兴未艾i 5 1 - 5 2 。 2 j 随机分形生长模型 分形图彤生成研究 由于1 i 规则自相似图形在真实世界中大量存在，随着人们对分形认识的深入，人们 开始对分彤形态的形成过程进行探讨，并提出r 各种生长模趔，埘解析法和汁算机模拟 十f i 结合进行研究。1 9 8 1 年，美因埃克森公司的t h o m a sa w it t e n 和l e u n 8 r d 地s m i d e r 共阳提出d l 模穗，h 口扩散有隔疑聚模型。它能有效地用计算机模拟自然界和实验室中 许多随机生长图形的分形形态。 l z 6 混沌、生物分形和人工生命 混沌学的研究与分形荚系至为密切，它们都是现代菲线性科学的重要缡成鄢分。j 9 2 7 年，丹麦电气- t 程师v a nd e lp o l 在研究氖灯张9 i 鱼振荡器的过程中，发现了种重要的 现象并拉色解释为“不规则的噪声”，后来的研究表明这是一种混沌现象而不是噪声。这 是第一次观察到混沌现象但未发现混沌。1 9 5 9 年，美国的斯墨尔实现_ r 第一个产叶二混沌 的模型。1 9 f i 3 年，& l o r e n z 对混沌运动有，两个重要发现：对扔艟的极端敏感性；解并 不完全随机，而是局限在状态空间的某一几何体上，称为混沌吸引子。其后，混沌理论 得剑蓬勃发展。1 9 7 6 年，r m a y 首次将混沌学引入生物学，他指出：生态学中的一些简 单模型，其有极其复杂的动力行为，其巾包括分岔，序列和混沌。从此生物学家开始刷 混沌理论展开了一系列的研究。混沌与分形磅究的纵国发展，也为人工生命的研究提供 r 理论和方法。人工生命是9 0 年代初发展的学科领域，也是当今计算机学科【 j 继人工智 能后的一个崭新的发展方向。 1 3 论文的主要工作 n ：运用分形几佃原理及算法编程绘制多种分形图的基础上，着重对由分形迭代幽数 系统的 s 迭代码生成分形图的特性展开_ r 细致的研究。实现了多幅岂术图案的设计及 虚拟景观的生成。论文主要工作包括： 】、概要阐述了分形儿何产生的背景、什么是分形以及分形的主要研究内容及其应 用领域。 2 、运削分彤l 系统及分彤迭代函数系统( w s ) 的多种算法编程绘制出s i e r p i n s k i 二角形、分形山、分形树、三维树叶、果园等多幅分形图。 3 、通过对1 f s 码的实验分析，将树叶迭代码与三角形迭代码之问逐渐缩小差距， 实现九由树叶过渡到三角彤的一些中| 、日j 演变图形。 4 、针对同一i f s 迭代码进行计算机绘制时，两次迭代绘制的分形图并非完全相同， 每次得到的点的轨迹之间不完全重合，但其形状大体一样这一问题展开研究。提 h 了1f s 分肜覆盖相交交点变化曲线的概念并给出r 其绘制算法，在此基础上进步研究丁分彤 覆盖相交交点变化曲线的变化率情况，得到了分形覆盖相交交点变化曲线宏观上比较光 滑，位实际上小范围内异常波动的实验结果。 5 、运用逃逸时间算法编程绘制多种j u l i a 集并对高阶广义j u l m 集分形图进行了其体 的分析与研究。 6 、用j u l i a 集的思想实现r 多幅艺术图案的设计与绘制，得到崩i n 阶迭代函数绘制 的“分形花”呈现出m 个花瓣的结果。将绘制的多种分形图进行r 综合运厢，实现了虚 拟景观的生成。 4 分形罔形生成研究 2 分形理论及其应用 2 1 概念的提出者 现代数学的一个新的分支分形几何学，它足由美籍法幽数学家曼德勃罗 ( f 3 b m a n d e l b r o t ) 1 9 7 3 年在法兰西学院讲课时，首次提出了分形几何的设想。分形 ( i ：r a c l a l ) 一词，是曼德勃罗创造出来的，其原意具有币规则、支离破碎等意义，分形 几伺学是一门以非规l j l j l j 形态为研究对旁的几何学。由于不规则现象在自然界是普遍 存在的，l 型此分形几何又称为描述大自然的几何学。分形几何建立以后，很快就引起了 r i ：多学科的关注，这是由于它不仪在理论上，而且在吏用上都具有重要价值。 2 2 分形的定义 门前分彤还没有最终的科学定义，曼德勃罗曾经为分形下过两个定义： ( 1 ) 分形是h a u s d o r f f b e s i c o v i t c h 维数严格人于拓扑维数的集合。凶为它把许多 h a u s d o r f f 维数是整数的分形集合排除在外，例如，经典分形集合p e a n o 曲线分 形维数 ( 2 ) 局郡与整体以某种方式自相似的形，称为分形。 然而，经过理论和应用的检验，人们发现这两个定义很难包括分形如此丰富的内容。 实际 ：，对于什么是分形，剑目前为止还不能给出一个确切的定义，正如生物学中对“生 命”也没有严格明确的定义一样，人们通常足剜生命体的一系列特征来加以说明。对 分形的定义也可同样的处理。 ( i ) 分形集合在任意小尺度1 - ，它总有复杂的细节，或者说它具有精细的结构。 ( i i ) 分形集台是非常不规则的，用传统的几何语言无法来描述它的局部和整体，它既不 是满足某些条件的点的轨迹，也不是某些简单方程的解集。 ( i i i ) 分形集具有某种自相似形式，可能是近似的自相似或者统计的自相似。 ( i v ) 以某种方式定义的分形集合的“分彤维数”，严格大子它孝日应的拓扑维数。 ( v ) 在大多数令人感兴趣的情形下，分形集合足以非常简单的递归的方法产生的。 总之，要精确地给分形下定义为时尚早。 2 3 分彩研究的对象 jd m 学的研究对象是物体的形状，在自然界巾，许多物体的形状是极不规则的，例 如：弯弯曲曲的海岸线，起伏不平的山脉，变化无偿的浮云，以及令人眼花缭乱的满天 分形| 冬 形生成研究 繁星，等等。，这些物体的形状有着共刷的特点，就是极不规则，极不光滑。但是，所有 的经典几何学都是以规则而光滑的形状为其研究对象的，例如：初等平面几何的主要研 究对象足直线与斓；平面解析儿何的主要形f 究对象是一次曲线与一：次曲线；微分jl i i 的 研究对象是光滑的曲线与曲而；代数几何的研究对象则是复空间中的代数曲线，等等。 把凹i i l l 不平的地球表f ：f i i 看成足绝对光滑的球面或椭球面。虽然在许多情况r ，这样 做_ ， f ：不妨碍我们得到非常符合实际的结论，但是，随着人类对客观t f t ：界的认弘 的逐步深 入以及科学技术的不断进步，这种把不规则的物体形状加以规则化，然后进行处理的做 浊已经不男人满意r 。侄7 0 年代中期，- f 新型的几何学脱颖而出分形，l 何学，就 是用求深刻地描述大自然本身的儿何学，它能深刻地刻划大千世界充满奇异而神秘的各 种极不舰则极不光滑的对象，这是数学发展史上的一个新世界。事实上，可以把分彤看 作是1 4 然形态的儿何抽象。 2 4 分形几# - 9 - - 的创始 客观自然界中许多事物，具有自相似的“层次”结构，存理想情况f ，甚至具有无 穷层次。适当的放大或缩小儿何尺寸，整个结构并卅i 改变。，1 i 少复杂的物理现象，背后 就是反映着这类层次结构的分形几何学。 客观事物骨占自己的特征跃度，要用恰当的尺度去测量。用尺米测量万里跃城，嫌 太短；用尺来测量大肠杆菌，又嫌太i s ：。从而产生了特征长度。还有的事物没有特征尺 度，就必须同时考虑从小到大的许许多多尺度( 或者叫标度) ，这叫做“无标度性”的问 题。如物理学中的湍流，湍流是自然界中普遍现象，小至静室中缭绕的轻烟，巨至木星 大气t t ，的涡流，都是十分紊乱的流体运动。流体宏观运动的能量，经过大、中、小、微 等许i i ：多多尺度上的漩涡，最后转化成分子尺度上的热运动，同时涉及大景不同尺度上 的运动状态，就要借助“无标度性”解决问题，湍流中高漩涡区域，就需要用分形儿何 学。 在：i - 世 己，匕十年代，法国数学家曼德尔勃罗特在他的著作中探讨了英同的海岸线 有多长? 这个问题就依赖于测景时所使用的尺度。如果用公里作测量单位，从几米到儿 米的一些曲折会被忽略；改用米来做单位，测得的总长度会增加，但是一些厘米量级 以f f 内就小能反映出来。由于涨潮落潮使海岸线的水陆分界线具有各种层次的不规则住。 海岸线在大小两个方向都有自然的限制，取不列颠岛外缘上j 、突出的点，用直线把它 们连起来，得到海岸线长度的一种下界。使用比这更长的尺度是没有意义的。还有海沙 石的最小尺度是原子和分子，使用更小的尺度也是没有意义的。在这两个自然限良之间， 存在着可以变 f 七f i ：多个数景级的“无标度”区，长度不是海岸线的定量特征，就要用分 维。 数学家寇赫从一个工f 方形的“岛”出发，始终保持面积不变，把它的“海岸线”变 成无限曲线，其长度也4 c l t l i i t 加，并趋向于无穷大。以后可以者到，分维才是。r 寇赫岛” 海岸线的确切特征量，即海岸线的分维均介f 】到2 之间。 6 分彤图形生成研究 这些白然现象，特别足物理现象和分形有着密切的关系，银河系中的符断糟续的星 体分布，就具有分维的吸引了。多孔介质中的流体运动和它产生的渗流模型，都足分形 i z 勺赴玎究对象。这些促使数学家进一步的研究，从而产生r 分形几何学。 随着计算机的发展，计算机图形显示协助了，人们推开分形几何的大门。这座具有无 穷层次结构的宏伟建筑，每一个角落里都存在无限嵌套的迷宫和吲廊，促使数学家和科 学家 ；f ：入研究。法国数学家曼德尔勃罗特这位计算机和数学兼通的人物，对分形几何产 生了重大的推动作用。他在1 9 7 5 、1 9 7 7 和1 9 8 2 年先后用法文和英文出版了二本书，特 别是分形形、机遇和维数以及自然界中的分形儿何学，开创r 新的数学分支 分形几何学。 2 5 分形几何与传统几何的不同 从整体上看，分形几何陶形是处处不规则的。例如，海岸线和山川形状，从远距离 观察，其形状是极4 i 规则的。 希：小同尺度上，图形的规则性又是相同的。上述的海岸线和山川形状，从近距离观 察，j 局部形状又和整体形态相似，它们从整体到局部，都是自相似的。当然，也有一 些分形几何图形，它们并不完全是自相似的。其巾一些是用来描述一般随机现象的，还 育一些是用来描述混沌和非线性系统的。 2 6 分形几何学的应用 近：1 年米，分彤的研究受到非常广泛的重视，其原因在于分形既有深刻的理论意 义，义有巨大的使用价值，它吸引着人们探寻和探讨其中可能的新规律、新方法和新特 征。 分形几何学在许多领域里都有应用，它币仅引出了许许多多的新问题，还为解决古 老的难题带来，新的希望。为什么分形那么快被人们所接受，并且引起人们的极大关注， 其t 要原因有四条： 1 传统的数学研究方法与计算机图形学相结合，使分形成为看的见、摸的着、道 的帆束的东西，没有计算机图形学，这些美丽而极其复杂的u l i a 集和m a n d e d b r o t 集根 小不可能呈现在屏幕上。 2 物理学家和其他许多领域的科学家起了推波助澜的作用。他们越来越惊奇地发 现，自然界坐到处是分形。例如湍流、相变、银河系中的星团、流体存孔隙介质中的渗 透以及人体脉管系统的分义模式等等。分形给复杂的现象解释。 3 分形成为各种不同领域科学家交流的共同语言，使他们能走到起讨论芡同的 阳题。 4 分形既有深刻的理论、又有上! 大的实用价值，这是最主要的原凶。 简单列举分形在以下几各方面的主要应用： 一、模拟自然景象 用分形几何学原理由计算机描绘出来的自然界景象，例女l l i l l 、云、水、植物等，简 分形图形生成研究 由可以与艺术大师f 、j 的杰作媲美，确实令人赞叹不已，甚全可以达到以假乱真的程度。 晦：多作品都被好莱坞的特技行业成批地采用r 。 一、周象数据胝缩 分形图象压缩技术是由札f b a r n s l e y 在1 9 8 7 年提出的。这种方法完全f i 同于传统 的各利，编码方法，它充分利用r 一幅图象中各区域之间的相似性或仿射性，通过一组仿 射变换系数就可以描述一幅图象，这个方法由于能取得极高的压缩比，受到了美国军方 的重视，并引起世界各国研究人员的兴趣，足一个很有发展前途的领域。， ：= 、分形生长发其应用 分形生长研究的日的在于试i 圣| 蛤山分形生长的物理过程，以便揭示分形结构从形核 到长大过程的物理规律，在物理学、化学、牛物学、材料学及医学中，存在着大量分形 牛 丈的实例，研究它们的生长规律，目的是为了达到控制或应用它的 = j 的。 分形图形生成研究 3 分形l 系统 3 1 l 系统 l 系统足以美同生物学家i , i n d e n m a y e r ， ri s l l i d 的名字命名的。他于1 9 6 8 年提出 r 植物形态与车k 的描述方法，开始时只着重于植物的分义结构，后来存描述过程巾加 进r 几何解释，形成了l , - s y s t e m 阁形学家们将ls y s t e m 引进图形学，使l 系统成为一 类臼然景物模拟的有效方法。他们的男一重要贞献是他们指出了l 系统和m a n d e lb r o t 引入的分形概念之间有着密切的联系，因此，1 系统目前也成为生成分形的一个典型的 重要的方法。 3 2 分形l 系统的原理 l 系统是基于符号重写系统。即用一个重写规则逐次地置换初始对象的各个部分来 确定一个复杂的对象。 发有两个字母组成的字符串，重写规则为： h a a ，a b 则系统演变的过程为： b a ab aba abaab aba ababa 这个字符串中字母个数的增长恰恰是n b o n a c c i 舳励8 n l ，l ，2 ，3 ，5 ，8 ，1 3 ， 这个数硎满足以下递推关系： e = + e ， 选用龟爬行过程来描述l 系统生成分形图的过程，设0 ，力为龟所在位越的坐标 a 为龟头指向的角度，y o ，砜) 是龟的初始状态，d 是前进增量，万是角增量参数， 龟按以下命令动作： f ：阳d 矿移动一步，步长为d ，龟状态为p ，j j ，a ) ，= z 十d c o s d y = y + d s i n a 从仁川刁p ，y ) 画一直线； l ：i ，j j 自u 移动一步，步长为d ，不画 十：向芹旋转6 角，则龟_ f 一个状态为y ，n + 一：向右旋转6 角，则龟卜一个状态为g m “砷 经过这样反复重写，最后可以得出分形图。 9 分形图彤生成研究 3 3l 系统对植物结构的模拟 m 于植物是分叉结构，故l 系统产牛植物结构7 产生分彤图有所区别，需要增加将 分叉处的j j 前信息胍入堆栈以及从堆栈中弹冉信息的过释。 轴向树主费有以下儿部分组成： f a ，根：这是一个特殊节点，由根出发可以连接到达任f n j 一个端点； 阳) 内节点：住路径中，该节点至少连接一个后继分支： f c j 终端节点：最后一个分枝的端点，也称为顶端： f 圳自枝，侧枝：良枝是树的主干，侧枝是分枝，可以分为0 级、l 级、2 级分 叉等： 为，描述分义结构，引入两个新的字符，其含义为： ：将当前龟的状态压入堆栈，状态信息包括龟所在的位置与方向等； ：从堆栈中弹出一个状态作为龟的当前状态。 例如，ff 手f _ 7ff f _ 7f 字符串解释见图l ，具体动作如卜： f ：垂直画一个直线段，如整个树长定义为三，贝经正次重写后f 的长度为 ( s ) 6 l ，其中s 为缩小的比例因子( 0 11 0 s d ( ， w u l l + 4 分形图形生成研究 ( 如正方形边框、填充三角形等，本例为正方形边框) ，设定两个数组，一个用来存放a 。 和上次迭代的结果，另一个用来存放本次迭代的结果，然后，给定最大迭代次数( g ) 和 仿射变换个数( 3 ) 及仿射变换系数进行迭代，其i f s 码及图形如下： 裹4 一l t a b 4 1 abcdef 0 5o o0 0o 5o oo o o 50 00 0o 5o 5o o o 5o 0o o0 5o 5o 5 图4 1 s i e t p i m k i 三角形 f i g 4 - 1 s i e l p i n k r r i a n g l e 确定性i f s 迭代算法中初始集的选择是任意的，如果上图的初始集a o 选择为填充三 角形，用上述算法计算，能够得到同样的分形集。我们只要修改生成集合的那一部分程序 即可。 4 1 2 i f s 随机迭代算法 设带有概率的多i f s 由压缩仿射变换集x = x ；：wn ，吼。，w 。，i = l ，2 ，m ) 和一个概率集p = p m p 。，p 。i = 1 2 ，m 】构成。其中： 乃= 1 ，且m 萄，j = l ，2 ，n ，i = l , 2 ，m j = t ( 匀= ( 22 ( 匀+ z ) ，吐：，n ，i = z 五m c t ， 对于任意i ，w i 中的m a x ( j ) 可以小于n ，即把j 为m a x ( j ) + i 至n 的所有参数视为0 。 选取任一点x ( i 2 1 ，2 ，m ) 为初始点，然后递归地随机选取下述集合中的一 个点作为x 。n - - - i ，2 ，于是有 工。h ，( x i ( n - 1 ) ) ，w f ：( z 。( 。一。) ) ，j l ( ( 。一，) 1 4 ( 2 ) 分形图形生成研究 最终得到序列扛。) cx 。，收敛于i f s 的吸引集。 随机迭代算法比确定性算法增加了一个概率集p ，该概率集通常赋予一个很小的正 值，也可以按人的视觉要求确定。当视窗选择太大，也可以增加迭代次数，以提高图象 质量。同样要给出最大迭代次数和仿射变换个数。以下是用随机迭代算法得到的分形山 和分彤树。其i f s 码及图象见下表： 表4 - 2 分形山的t f s 码 t a b ，4 - 2t h er f sc o d eo ff r a c t a lj d o u n r a i n wabcdef p ( 1 ，1 ) 0 0 8 0 00 0 3 10 0 8 4 0o 0 3 0 65 1 7 0 07 9 7 0o 0 3 ( 1 ，2 ) 0 0 8 0 10 0 2 1 2- 0 0 8 0o 0 2 1 26 6 2 0 09 4 0 00 0 2 5 l ( 1 ，3 ) 0 7 5 0 00 0 0 0 00 0 0 0 00 5 3 0 00 3 7 51 1 0 6o 2 2 ( 1 ，4 ) o 9 4 3 00 0 0 0 00 0 0 0 00 4 7 4 0- t 9 8 0一o 6 5o 2 4 5 | ( 1 ，5 ) 一0 4 0 2o 0 0 0 00 0 0 0 00 4 0 2 01 5 5 1 34 5 8 80 2 1 ( 1 ，6 ) 0 2 1 7 0- 0 0 5 20 0 7 5 0o 1 5 0 03 0 0 0 05 7 4 0o 0 7 l ( 1 ，7 ) 0 2 6 2 00 1 0 5o 1 1 4 00 2 4 1 0- 0 4 7 33 0 4 50 1 0 ( 1 8 )0 2 2 0 00 0 0 0 00 0 0 0 0o 4 3 0 01 4 6 0 04 2 8 6o 1 0 圈4 - 2 分彤山 f i g 4 - 2t h ef r a c t a l g o u n t a i n 表4 3 分形树的i f s 码 t a b 4 - 3t h ei 盼c o d eo ff r a c t a l t r e e 【w a b cd e f p l ( 1 ，1 )0 0 5 0 6 0 0 0 0 0o 0 0 0 0 0 0o o o0 1 l ( 1 2 ) o 0 5o 50 0 0 00 0 0 0o 0 01 0 00 1 【( 1 ，3 ) o 6 0o 5 04 0 0 04 0 0 00 0 0o 6 00 2 ( 1 ，4 ) o 5 0o 4 52 0 0 02 0 o oo o o1 1 0o 2 i ( 1 ，5 ) o 5 0o 5 53 0 0- 3 0 00 0 01 0 00 2 i ( 1 ，6 ) o 5 5 0 4 04 0 0- 4 0 00 0 00 7 0o 2 分形图形生成研究 图4 _ 3 分形树 以上是用随机迭代算法生成的二维图象，而在现代，二维图象并不能满足人们的视 堂要求，那么用随机迭代算法能不能生成三维图象昵? 回答是肯定的。下面我们以三维 树叶为例加以说明。 要生成的三维树叶的【f s r 3 ；w 1 ，w ：w 3 ，w 。 ，其中每一个w 为3 3 矩阵，吸引子包 含在 ( 工i ，2 ，工3 ) r 3 ；- 1 0 j l 1 0 ，一1 0 x 2 蔓1 0 ，一l o 屯1 0 ) 。w i 的形式为： 三维图象通过透视交换计算显示在屏幕上的位置，具体采用下述转换公式 一= j + c o s ( z + y + c o s+ 二+ c o s y ； v 。= x s i n + y 4 s i np + z 4 s i n y ； 其中( 白，) 选取以下各组的值： 表4 _ 4 t a b 4 4 口 8 ， 3 0 1 3 5- 1 5 0 4 0 1 2 51 2 5 1 5 7 01 5 0 2 5 6 0- 3 0 、，l， 啊吼 ，r。i + 、， 工y 1 1 i v o _ q z 所所岛 q 吐毋，。l = 、； 工 y ： ，。l w 分形图形生成研究 表4 - 5 三维树叶的i f s 码( 1 ) t a b 4 - 5t h e i f sc o d eo ft h r e e - d i m e n s i o n a l e a v e s ( 1 ) 1 wabc def ( 1 ，1 )0 0 0 00 0 0 00 0 0 0 0o 1 80 o ( 1 ，2 )0 8 3 00 0 0 00 0o o oo 8 60 1 ( 1 ，3 ) 0 2 2 0- o 2 30 0o 2 4o 2 20 o ( 1 ，4 ) o 2 20 2 3 00 0o 2 4o 2 2o o 续： 袁4 5 三维树叶的i f s 码( 2 ) t a b 4 - 5t h e 【f sc o d eo ft h r e e d i m e n s i o n a ll e a v e s ( 2 ) w g h mn qr p l ( 1