（应用数学专业论文）迭代函数系统的符号化方法.pdf

硕：卜学位论文 摘要 分形图形学作为计算机图形学领域的一项重要内容被越来越多的人所关注， 迭代函数系统和l 系统是构造分形图形的两个经典数学系统，它们的不断发展对 整个分形学领域有重大的意义。为了能够研究不同i f s 之间的关系，本文首先根 据其吸引子生成的原理，提出了具有明显几何和代数含义的i f s 加法、直积、复 合积和相似运算的定义并分析了其运算性质。这对认识一些i f s 吸引子之间的关 系有很大的帮助，能够在己知i f s 的基础之上构造出更多的分形图来模拟自然界 中的物体。然后通过分析i f s 确定性算法生成分形图形的过程，在i f s 符号化的 基础上给出了符号化系统的具体定义；为了能够快速便捷地实现一些经典分形保 留了少数的预定义符号，用户可以根据需要设定若干带有参数的表示常量、变量、 数学函数、几何图形的自定义符号，设置公理，规则和迭代次数，系统会自动生 成用户所定义的分形；给出了符号系统的生成算法并对其解释程序进行了分析， 通过建立n 进制数和变换之间的一一对应关系，在一定程度上改进了算法，降低 了时间复杂度和空间复杂度。符号系统将各类i f s ，各类l 系统及中点移位曲线 用统一的方法进行描述和处理，并且增强了表达分形的能力。利用不同方法实现 的特殊效果的分形图均可以在符号系统中实现，效率高的生成算法也可以应用在 其中，即保留了原有系统和方法的优点。符号系统以文档格式表示，可读性强， 容易理解，算法快，生成效率高。初始集不再局限于点或图像，并且恰当地选择 初始集可以提高生成速度。 关键词：分形；迭代函数系统；l 系统；符号化；吸引子 迭代函数系统的符号化方法 a b s t r a c t m o r ea n dm o r ep e o p l ea r ec o n c e r n e da b o u tf r a c t a lg r a p h i c sw h i c hi sa ni m p o r t a n t c o n t e n to fc o m p u t e rg r a p h i c s i t e r a t e df u n c t i o ns y s t e ma n dl - s y s t e ma r et w oc l a s s i c a l m a t h e m a t i c a ls y s t e mo fc o n s t r u c t i n gf r a c t a li m a g ea n dt h e i rc o n t i n u o u sd e v e l o p m e n t h a v eg r e a ts i g n i f i c a n c et ot h ew h o l ef i e l do ff r a c t a l i no r d e rt os t u d yt h er e l a t i o n s h i p b e t w e e nd i f f e r e n ti f s ，t h ed e f i n i t i o na n do p e r a t i n gp r o p e r t i e so fi f sa d d i t i o n ，d i r e c t p r o d u c t ，c o m p o u n dp r o d u c ta n ds i m i l a rt h a th a v eo b v i o u sg e o m e t r i ca n da l g e b r a i c m e a n i n ga r er e s e a r c h e d ，b a s e do nt h et h e o r yo fi f sa t t r a c t o rg e n e r a t i n g i ti sh e l p f u l f o rr e c o g n i z i n gt h er e l a t i o n so fs o m ei f sa t t r a c t o r , a n dc o n s t r u c t i n gm o r ef r a c t a l st o s i m u l a t en a t u r a l o b j e c t s b a s e do nk n o w ni f s b ym e a n so fd e f i n i n g v a r i o u s m a t h e m a t i c a lo p e r a t i o n so fi f sf i r s t l yi nt h i sp a p e r t h e nb yw a yo fa n a l y z i n gp r o c e s s o fg e n e r a t i n gf r a c t a lg r a p h i c sw i t hd e t e r m i n i s t i ca l g o r i t h m ，t h ed e f i n i t i o no fs y m b o l s y s t e mi sg i v e nb a s e do ns y m b o l i ci f s ；t ob ea b l et oq u i c k l ya n de a s i l yi m p l e m e n t s o m ec l a s s i c a lf r a c t a l sas m a l ln u m b e ro fp r e d e f i n e ds y m b o l si sr e t a i n e d u s e r sc a ns e t u ps e v e r a lc u s t o ms y m b o l sw i t hp a r a m e t e r , w h i c hr e p r e s e n tc o n s t a n t ，v a r i a b l e ， m a t h e m a t i c a lf u n c t i o n ，g i v ea x i o m ，r u l e s ，a n dt h en u m b e ro fi t e r a t i o n ，t h e nt h es y s t e m w i l la u t o m a t i c a l l yg e n e r a t eu s e r - d e f i n e d f r a c t a l ；g e n e r a t i n ga l g o r i t h mo fs y m b o l s y s t e mi sp r o p o s e da n di t se x p l a n a t i o np r o g r a mi sa n a l y z e d ；t h r o u g he s t a b l i s h i n gt h e c o r r e s p o n dr e l a t i o n s h i pb e t w e e nnh e x a d e c i m a ln u m b e r sa n dt h ec h a n g e ，t h e a l g o r i t h mi si m p r o v e dt os o m ee x t e n t ，t h et i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t yi s r e d u c e d s y m b o ls y s t e mc a i ld e s c r i b ea n dp r o c e s sv a r i o u st y p e so fi f s ，l s y s t e m ， m i d - p o i n td i s p l a c e m e n tc u r eu s i n gau n i f o r mm e t h o d ，a n de n h a n c et h ea b i l i t yo f e x p r e s s i n gf r a c t a lg r a p h i c s s p e c i a lf r a c t a lg r a p h i cw h i c hi sa c h i e v e dw i t hd i f f e r e n t m e t h o d sc a na c h i e v e di ns y m b o ls y s t e m e f f i c i e n tg e n e r a t i n ga l g o r i t h ma l s oc o u l db e a p p l i e di ns y m b o ls y s t e m s a yi no t h e rw o r d s ，i tr e t a i n sa d v a n t a g eo fo r i g i n a ls y s t e m s y m b o ls y s t e mi se x p r e s s e dw i t hd o c u m e n tf o r m a t ，r e a d a b l e ，e a s yt ou n d e r s t a n da n d a l g o r i t h mi sf a s t ，e f f i c i e n t i n i t i a ls e tn ol o n g e rc o n f i n e dt ot h es e to ri m a g e ，a n di f i n i t i a ls e ti ss e l e c t e da p p r o p r i a t eg e n e r a t i n gs p e e dc a nb ei m p r o v e d k e yw o r d s ：f r a c t a l ；i t e r a t e df u n c t i o ns y s t e m ；l - s y s t e m ；s y m b o l i cs y s t e m ； a t t r a c t o r i l 硕十学位论文 插图索引 图3 1i f s 及其运算的分形集比较1 7 图3 2 带凝聚集i f s 复合积18 图3 3a 的迭代结果1 9 图3 4b 的迭代结果1 9 图4 1公理表示的图形2 5 图4 2 三次不同的迭代结果2 6 图4 3 分形树1 2 7 图4 4 分形树2 2 7 图4 5分形树3 2 8 图4 6 符号化系统迭代流程图2 8 图4 7 栈顶的变化情况3l 图4 8 三次迭代结果3 3 i i i 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 。 作者签名：王春藏 日期：29 d 年6 月1日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文 收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名： 导师签名： 土春颤 乒朋 日期：2 pj 口年占月j日 日期：朋汐年夕月f 日 硕十学位论文 1 1 课题的研究背景 第1 章绪论 欧氏几何以及以此为背景的传统数学所研究的图形都是足够光滑和规则的， 然而自然界的真实形态并非如此：充满空隙的宇宙空间，起伏不平的地形地貌， 九曲回肠的河流，纵横交错的大地褶皱、断层、裂缝，流体的湍流，曲曲弯弯的 海岸线，相变点附近的涨落花斑，地下水和石油的渗流，结晶体的分支，生物体 的形态与结构，静电传输误差，股票市场的波动。它们都不是欧氏几何意义下的 光滑、规则形体。根据研究问题的需要，光滑、规则的形态不仅不能很好地近似 它们，有的甚至连一级近似达不到。 1 9 世纪的数学家凭借想象力创造出了一些不够光滑、不够规则的形体，如 c a n t o r 集合、w e i e r s t r a s s 曲线、k o c h 曲线和p e a n o 曲线等等。但是长期以来，它 们被视为是“病态 的或称为“数学怪物，通常只是作为传统数学教科书中的反 例，起着对规则结构的点缀和陪衬作用，很少对它们进行详细的研究。近年来由 于分形这一概念的诞生，才使这些非规则的“数学怪物”获得了新生。科学家们 发现这些难以想象的数学奇葩，以极其简洁的形式描绘出复杂的物体和过程，因 此引起天文、地学、物理、化学、生物、材料、冶金、石油等领域的科学家们的 广泛兴趣。科学家们称分形几何是大自然本身的几何学。 白创立以来，分形几何日益受到各国学者的重视。在过去的几十年里，分形 科学已经有了很大的发展。计算机的应用也大大推动了分形理论的发展，并且由 于模拟分形图的成功而展现出优美的分形图像，迅速扩大了这门新兴科学的影响。 目前分形算法和程序设计已经成为一个独立的研究方向。分形图形完全冲破欧氏 几何的界限，随着计算机在图像处理方面技术的不断成熟，用计算机生成的分形 图形，给人的感觉是越来越新颖独特，内容越来越丰富多彩，也有越来越多的人 对分形领域表现出了极大的关注，这是一种全新的图形设计的构思来源和方法。 生成分形图形关键是要有一个合适的模型来描述对象，根据选择的模型的不 同产生分形的常用方法有迭代函数系统( i f s ) 、l 系统、d l a 模型、粒子系统、随 机插值、曲线曲面技术等。 1 2国内外发展现状 当前生成分形图形的方法越来越多，然而用一个数学系统去研究构造一类存 在于自然界的具有自相似性、标度不变性的分形，最为成功的就是迭代函数系统 ( i t e r a t e df u n c t i o ns y s t e m ，简称i f s ) 。它是由h u t c h i n s o n ( 19 81 ) 署i b a m s l e y ( 19 8 5 ) 提出并发展起来的一种研究分形的数学方法。i f s 的基本思想并不复杂，它认定 迭代函数系统的符号化方法 几何对象的全貌和局部，在仿射变换的意义下，具有自相似结构。几何对象的整 体被定义以后，选定若干仿射变换，将整体形态变换到局部，并且这一过程可以 迭代地进行下去，直到得到满意的造型。 在i f s 提出之后，许多学者对其进行了扩展。1 9 9 1 年加拿大学者v r s c a y 等人 将多项式变换工卜x 2 + 口1 x + a o 引入了迭代函数系统【l 】，将其命名为非线性迭代 函数系统( n i f s ) ，并研究了所产生的吸引子的动力性状；p r z e m y s l a w p r u s i n k i e w i c z 和m a r kh a m m e l 提出了语言约束迭代函数系统( l r i f s ) ，采用迭代 变换坐标系统限制语言的方法【2 1 ，通过加入不同变换顺序的约束条件，能够比较 通用地概括各类不同的i f s 方法；黄宜平【3 】等人对拼贴定理进行了研究，在一定 程度上突破了对于变换压缩的限制，得到了对于非压缩的i f s 也可以达到拼贴的 目的。放宽了i f s 的范围。 在分形图形生成算法方面，也有不少学者对其进行了研究。s a r a h 研究分形 的快速精确的生成算法【4 】；t a oj u 研究仿射变换i f s 和递归龟图几何生成分形算 法【5 】；h s u a nt c h a n g 等分别提出了l 系统与i f s 相融合的方法和分形图形的合成 方法【6 】等等；王兴元等人实现了一类i f s 吸引子在计算机上的模拟，以及具有特殊 性的吸引子的递归计算构造及特性分析【7 - 引。通过理论解析给出了求i f s 吸引子 界的方法，i f s 吸引子的l y a p u n o v 指数和关联维数的算法。利用计算机构造了 一系列i f s 吸引子，分析了i f s 吸引子的动力学特征，讨论了当参数变化时i f s 吸引子界的变化规律；刘树群给出了i f s 吸引子图像仿射变换的分形码变换通式 【9 1 ，并讨论了几种常见的吸引子变换，其为分形图像变换和分形图形设计提供了 一种简捷、高效和灵活的处理方式，还提出了点变换算法【l ，解决了吸引子变形 的连通性问题获得了高效快速的实时动画效果。 由于i f s 反问题没能得到很好的解决，许多学者提出了i f s 生成分形图形的 交互式控制技术，并在景物的模拟方面取得了一定的进展。美国伊利诺斯州立大学 计算机系p a u ls h e r m a n 和j o h nc h a r t 给出一个分形图形生成算法【1 1 1 ，使用户可 以直接操作一个由周期迭代函数系统( r i f s ) 生成的分形对象，这种方法可以让用 户指定吸引子上的特定点，然后拖拽其他点到用户需要的位置，为符合新的位置， 吸引子的形状会改变。章立亮提出了一种生成分形技术【1 2 1 ，即对不动点多边形的 调控来实现对原迭代函数系统分形图形的操作。这种方法可以直观有效的获得大 量形态各异的分形图；魏小鹏讨论了传统的迭代函数系统拼贴建模方法【l3 1 ，从 整体和局部的组合与相似关系出发，对传统拼贴建模方法进行简化，给出两种简 化方法：局部轮廓法和三点法，分析了三种建模方法的应用条件和具体实现技术； 覃风清等通过v c + + 编程，采用多重缩小机制和随机迭代算法i l 引，分别对 s i e r p i n s k i 直角三角形和蕨类植物进行构造与模拟；韩云萍【l 副等人将i f s 和自由曲 面理论应用于计算机辅助设计中模拟了种植果树的山坡；郭继东【l6 j 等研究了多 2 硕七学位论文 i f s 和嵌套i f s 迭代生成算法，采用概率驱动的随机迭代算法绘制生成自景物， 算法简单快速，生成景物逼真；王吴鹏【1 7 】等讨论了基于i f s 来搜索和解决植物的 计算机模拟生成问题的途径，再从植物体的不同形状出发生成一个图画序列，从 而实现对植物体的动态模拟过程。 l 系统的本质上是字符串改写系统。首先定义字符集合，设置初始字符串和 字符串替换规则，然后根据规则对原始字符串不断进行替代，每一步迭代过程中 字符的替换都是并行的，即所有字符同时进行替代操作。由于计算机图形学技术 让l 系统描述的结构被可视化的展现出来，从而使l 系统从理论概念发展成为程 序设计语言，以用于合成不规则图形和真实的植物影像，这又反过来进一步促进 和提高了l 系统强大的建模功能，因此不断的吸引着越来越多的人投入到模型架 构和植物生长的研究中来。 加拿大的c a l g a r y 大学的p r u s i n k i e w i c z 等人对l 系统进行了扩展，提出了能 够与周围环境交互的开放l 系统( o p e nl s y s t e m ) t ”1 和能够模拟植物生长的随机性 的随机l 系统( s t o c h a s t i cl s y s t e m ) t 1 9 】，为l 系统引入了一个“交流符号，该符 号可以实现l 系统与周围的环境的交互；为了模拟植物的连续生长过程， p r u s i n k i e w i c z 等提出了时变( t i m e d ) l 系统【2 们，能够生成植物生长过程的计算机动 画：为了能够进一步描述植物生长的连续的过程，p r u s i n k i e w i c z 又把微分方程引 入到了l 系统，从而提出了微分l 系统( d i f f e r e n t i a ll - s y s t e m ) t 2 1 1 ，该系统能够较好 的模拟植物的叶序、美丽的花朵、弯曲的枝条等，以及植物在生长过程中相互影 响等情况，比较完美的实现了对植物生长过程的模拟；p r u s i n k i e w i c z 等又引入参 数上下文语义相关l 系统的仿射变换几何解释作为一种替代技术并产生细分曲线 【2 2 1 ，l 系统细分算法以直观、简洁、指数自由的方式，反映了并行和局部性质； 陆汝钤等人对自然界的不同步的现象进行的模拟【2 3 1 ，推广了传统的l 系统并提出 了广义l 系统的概念，证明了广义l 系统不能被传统的l 系统所覆盖，还划分出 了l 系统的子类；严继利等在l 系统的理论基础上进一步研究了参数l 系统和开 放式l 系统的数学模型和计算机上的实现过程【2 4 1 ，参数l 系统通过改变系统中的 输入参数值可以使同一个表达式在计算机上模拟出不同类型和分枝的植物，开放 式l 系统能够模拟植物与周围环境间的信息交互过程，在开放式l 系统中引入了 ( 五，恐，) 这个信息模块作为提问模块，以参量五，x 2 ，毛接受和发送环境传递 的信息，解决了传统l 系统在理论上封闭、不能实现和周围环境进行信息交互的 缺陷，可以模拟植物的最优生长环境。 张树兵等用递归结构来表达l 系统生成的表达式【2 5 1 ，简化了数据结构，使运 行l 系统算法所需的时间和所占的空间减少；秋林等概括了植物根系的拓扑结构， 发现了植物根系与l 系统理论的相关性【2 6 1 ，利用l 系统实现了冬小麦根系生长的 动态模拟，同时利用动态数据结构弥补l 系统灵活性的不足，使小麦根系的显示 3 迭代函数系统的符号化方法 方便灵活、更加真实自然；冯莉等将分形理论应用于v r m l 环境中研究植物的计 算机模拟算法【2 7 1 ，通过描述树的属性从而自动生成符合用户要求的三维树；袁可 【2 8 】等在l 系统基础上实现了冬小麦的根系模拟，并引入“管道模型”，使系统在 模拟的同时，能够计算根长、根重、根体积等重要参数，实现了生长发育模型与 形态发生模型的结合。陈敏智等探讨了利用参数l 系统生成植物结构模型的方法 以及基于这些模型的植物形态可视化模拟【2 9 1 ，给出了若干具体的公理和产生式参 数；钟南等探讨了l 系统理论在植物根系生长模拟中的具体应用【3 0 1 ，把括号l 系 统、参数l 系统、随机l 系统和时变l 系统结合起来建立了描述根系生长的产生 式集实现了根系生长的三维可视化；陈晓等针对树在风中的摇曳变形提出了一种 将分形技术和物理力学变形技术相结合的方法【3 1 】，该方法首先利用分形技术建立 了树木模型，然后根据风力级数的强弱并结合树的层次结构特点，给出了风力模 型，在此基础上根据物理力学原理进一步模拟了树的摇曳变形；史丽敏利用l 系 统结合几何造型技术对树木进行绘制【3 2 】；w o j c i e c hp a t u b i c k i 等人提出了“自我组 织 的建模方法【3 3 1 ，该方法集成了树的形成三要素：树枝结构的局部控制、芽和 树枝的空间和光线的竞争、通过内部信号机制规划这种竞争。 澳大利亚c p a i 研究中心开发了一款基于l 系统的软件v i r t u a lp l a n t s ，该软 件包含新的植物器官产生规则以及已有器官的大小及形状变化规则。主要用于模 拟棉花、大豆等作物的生长发育过程和害虫对于作物的影响，研究了棉花与害虫 之间的交互作用；丁维龙【3 4 】等采用子结构算法减少了l 系统重复迭代所占用的系 统空间。并利用植物学家总结的植物架构模型提炼出l 系统规则模板库，在此基 础上开发出可视化模拟系统v p g 1 。该系统弥补了l 系统在通用性上的缺陷，拓 宽了系统的适用面，并且使用方便；l s t u d i o 是由加拿大的c a l g a r y 大学开发的基 于l 系统的植物建模工具【3 5 1 ，研究植物与它们所在的外界环境之间的交互性。使 用者根据其预先定义的解释符号，编制所要模拟的植物的l 系统产生式，软件根 据产生式生成植物图形。 1 3当前存在问题 l 系统是一种生成分形图形比较快捷的方法，不需要深刻的理论背景，有初 步计算机知识的人就能比较快的学会这种方法。l 系统可用于对自然界中相当一 部分植物的模拟，形象逼真、极为相似，能绘制相当复杂的分形图。为了能够增 强l 系统造型控制能力，众多学者从符号，参数，随机性能力表达等方面对l 系 统进行扩充，但这大部分是从某一个特定的方面进行研究，造型控制能力仍然有 限。l 系统要求所绘制的对象的生成元和迭代规则必须清楚，这实际限制了这种 方法的应用，特别是用这种方法对自然界中的植物进行模拟，要求设计人员要有 4 硕十学位论文 足够的经验才可以实现。另外对己知系统的理解也很困难，一般的l 系统经过几 次重写之后，符号串长度以指数增长，较难阅读理解，不易把握其图形含义。 传统的迭代函数系统主要利用仿射变换绘制分形图，虽然拼帖定理告诉我们， 理论上迭代函数系统可以近似的模拟自然界的任何事物，但是寻找一个指定事物 的i f s 码有一定的难度。此外i f s 具有严格的自相似性，缺乏对事物拓朴结构的 控制，带凝聚集i f s ，带参数i f s ，再归i f s 等的提出和应用从不同的角度增强了 i f s 的造型控制能力，但是它们的生成算法有很大的差别，并不统一。用复杂的 格式可以表示出简单的内容，这样牺牲很大，造成了迭代函数系统算法复杂度增 大，交互能力和生成效率降低。 迭代函数系统和l 系统是生成分形图形的两种不同方法，各有不同的优缺点， 想要结合两者的优点去生成分形，能够用统一的方式描述i f s 和l 系统是非常必 要的。王铁红【3 6 】将i f s 符号化，用形式化的方法对i f s 进行描述和处理，在i f s 和l 系统之间建立了联系，但他只对常归i f s 进行了分析，没有分析再归i f s ，带 凝聚集i f s 等符号化的方式，而且表达分形的能力非常有限。本文定义了一个能 将各种i f s 和l 系统以及随机中点移位法作为实例的符号系统，并且给出了计算 机生成和解释的过程及其算法分析。 i 4实际意义 第一分形几何为研究自然界中形形色色的复杂形状和结构提供了十分简洁 的工具，因而在天文、地学、物理、化学、生物、医学、材料乃至语言学、经济 学等领域得到了十分广泛的应用。时至今日，分形理论所包含的深刻内涵还远未 揭示出来。 第二分形几何能为自然界中存在的各种景物提供逼真的描述，这些景物形 态复杂，不规则，使用传统几何描述遇到了极大的因难，而分形模型确能很好地 描述自然景物，因为自然界的许多景物本身大体上就是分形，在计算机上绘制的 自相似集能够产生令人惊奇的图案。 第三迭代函数系统和l 系统是在计算机上绘制分形图形的两种经典的方 法，目前都得到了广泛的应用。本文结合i f s 和l 系统的优点，在将i f s 符号 化的基础上将其进行扩展，提出了分形图形的符号化系统，实现了对各类i f s ，l 系统，中点移位法的统一描述；符号系统将预定义符号和自定义符号相结合，以 文档形式表示，结构清晰，简单直观；从不同的侧面处理可以得到不同的系统， 保留了各类i f s 和l 系统具有的优点；正则表达式的引入使得其分形造型能力和 分形控制能力较i f s ，l 系统都有所增强；随着计算机技术和形式化语言在分形 领域的不断深入，使本文的研究有一定的理论和应用价值。 迭代函数系统的符号化方法 1 5本课题主要研究内容 主要研究内容如下： ( 1 ) 通过吸引子的形状研究i f s 的运算性质以及多个系统之间的关系； ( 2 ) 在i f s 符号化的基础之上对其进行扩展的各种方法； ( 3 ) 研究符号系统实现随机性表达的方式； ( 4 ) 考察对现有系统，情景描述等的支持所需要的结构从而定义符号系统的文 法结构； ( 5 ) 符号系统的表达造型能力，几何控制能力； ( 6 ) 实现各种l 系统和i f s 以及随机中点移位法的具体定义方法。 6 硕十学位论文 第2 章迭代函数系统和l 系统 2 1 迭代函数系统 迭代函数系统的理论依据及应用效果是基于著名的压缩映射不变集定理和拼 贴原理。吸引子定理保证了i f s 吸引子唯一存在性以及这种吸引子求取的方法， 即确定迭代方法对吸引子的生成，拼贴定理保证了完备空间中任意给定的有界子 集，一定可以找到一个i f s 系统与其吸引子相似，两者近似程度在于拼帖的水平， 近似的度量是h a u s d o r f f 距离。 2 1 1定义 一个迭代函数系统3 7 蕊1 由度量空间( 石，d ) 与定义在其上的一组压缩映射变换 q ：x x ，刀= 1 ，2 ，n 所组成，记为： x ；c o ，l = l ，2 ，i v ；如果q 的压缩比为 ，万= l ，2 ，n ，则称s = m a x 乜：n = 1 ，2 ，n ) 为此i f s 的压缩比。 定理1 ( 压缩映射不动点定理) 设 x ；c o , ，n = l ，2 ，) 是完备度量空间( x ，d ) 上的i f s ，压缩比为s ，变换形由下式定义： 形( 功= u ( 功，v b h ( x ) ， n = l 则矿是( 日( x ) ，) 上，压缩比为s 的压缩映射，即( 矿) ，矽( c ) ) s ( b ，c ) ， v b ，c 日( x ) 且存在唯一的不动点( 不变集) 么h ( x ) 满足彳= 职彳) = u q ，并 n = l 且对任意的b 日( ，a = l i m w ( b ) 。不动点a h ( x ) 称为这个i f s 的吸引子。一 般说来，i f s 的吸引子就是分形。 定理2 ( 拼贴定理) 设( x ，d ) 为完备度量空间，给定h ( x ) 和s o ，选定 一个i f s x ；q ，行= 1 ，2 ，) ，其压缩因子为0 s o ，n = l ，一般a 可以由下列的方式给定： b 2 躺2 豇 a f t , 厕- b i c i 。 注意可能对某个f ，f d e t= o i ，则实际操作时可把只设成一个较小的数。随 机算法不同于确定性算法的第二点是：此时的起始图像不再是一个点集，而是任 一点x o x 。然后根据概率随机地选择变换q ，计算五= q ( x o ) ，这样的过程不断 继续就会得到关于x o 的轨迹 ：。，该轨迹收敛于i f s 的吸引子。具体算法步骤 如下： 硕十学何论文 给定一个起始点( 而，甄) 及总的迭代次数； 以概率b ( i = l ，2 ，n ) 选择仿射变换； 变换作用于( 而，) 得到新点坐标( 五，y 1 ) ； 令x o = 五，y o = y l ； 如果迭代次数大于1 0 ，则在屏幕上打出点( 而，y o ) ； 重返步骤，直到迭代次数大于m 为止。 用随机迭代算法绘制分形图，原理清楚，程序简单，节省机时。虽然上面给 出了计算珐的方法，但只是给出了一个大概范围，阢的合适取值决定了图形的绘 制成功，这很大程度上取决于经验，因此增加了利用这种方法的难度，但随机性 迭代算法仍然是一种很好的绘制分形图的基本方法。 2 1 3 带凝聚集i f s 不管是常规的i f s ，还是随机的i f s ，功能都是从日( x ) 的任一集合b 出发， 经过一系列迭代后便得到一个分形几何体。假设共迭代了m 次，则得到的图像便 是矿肘佃) ，而w 1 p ) w 2 p ) ，w 水1 陋) 都消失了，这在画单个分形集时是可以的， 但要类似于一排树，其工作量就太大了。带凝聚的i f s 有效地解决了这个问题。 设 x ；c o , ，n = 1 ，2 ，n ) 是具有压缩因子o j 日( x ) ，形( b ) = u q ( b ) ， i = i 对任意的b h ( x ) ，则对每个b h ( x ) ，w 是h ( x ) 上的对于p 的连续函数。 定理2 4 设( x ，d ) 是度量空间， x ；( c o o ) ，q ，) 是一个( 带凝聚集) 的i f s ， 压缩因子s = m a x s 。：刀= l ，2 ，) ，如果每个嚷都连续依赖于参数p p ，p 是紧 度量空间，则吸引子4 ( d h ( x ) 就是按h a u s d o r f f 度量h ( a ) 连续地依赖于 p p 。该定理告诉我们，通过调整变换中的一些参数，使吸引子得到连续的控制。 9 迭代函数系统的符号化方法 2 1 5 再归i f s 再归迭代函数系统【4 0 1 ( r e c u r r e n ti t e r a t e df u n c t i o ns y s t e m ，简称r i f s ) 是多 个迭代函数系统按照某种关系组合，其吸引子可以表现出多个i f s 吸引子的特征。 设，d ) 是一个完备的度量空间，映射彬：x 专x 为l i p s c h i l z 的，f = 1 , 2 ，n 定义 变换的合成关系r = ( q ，哆) i q 作用在q 上 ，则称 x ；尺；q ，i = 1 ，2 ，n ) 为再归的 迭代函数系统。当q ，缈，出自同一i f s 的变换时，r i f s 即是此i f s ；当哆，缈，出自 不同的两个i f s 时，r i f s 为这两个i f s 按照某种关系构成的再归迭代函数系统。 再归迭代函数系统有三种基本形式：完全转移r i f s ，部分转移r i f s ，交替式 r i f s t 4 1 1 。虽然r i f s 并从根本上改变i f s 在模拟事物时的严格自相似性，但是利用 r i f s 可以生成更加逼真、复杂的分形图形，且实现过程更加直观、方便、易于实 现。 2 2l 系统 1 9 6 8 年，匈牙利生物学家a r i s t i dl i n d e n m a y e r 提出了l i n d e n m a y e r 系统，简 称l 系统作为植物生长的数学理论。l 系统是一种并发的字符串替代系统，其理 论重点为植物拓扑学，即描述细胞或更大的植物模块之间的领接关系，为了对植 物可视化建模，一些l 系统的图形解释被提出。1 9 7 4 年l i n d e n m a y e r 等人提出了 最初的解决方案，随后s z i l a r d 等人提出了l 系统在分形中的图形解释。 p r u s i n k i e w i c z 使用基于龟形的图形解释实现了很多分形和草木植物模型，使龟形 成为最常用的l 系统图形解释方案。 2 2 1定义 l 系统是一个三元组g = 。其中v 是符号的有限集合，称为字母表； 彩是被称为“公理”的符号串；尸是生成规则( 又称产生式) 。在实际应用中还要 约定一些初始量，如起始点坐标、起始角、步长、迭代上限等。 l 系统的理论不断得到发展众多学者在d o l 系统的基础之上进行了广泛而 深入的研究。为了避免l 系统构建的模型过于呆板，e i c h h o r s t 等人提出了随机l 系统，以增强模型的灵活性。h e m a n 等人将l 系统拓展为上下文相关以使植物模 型各个模块之间产生关联。l i n d e n m a y e r 等学者引入参数使l 系统更加简捷高效。 p i z e m y s l a wp r u s i m k i e w i c z 等人通过引入连续时间流扩展参数l 系统，实现连续时 间内的模拟。有些学者将l 系统从二维扩展到了三维，提出了三维l 系统和实现 方法。 1 0 硕士学位论文 2 2 2d o l 系统 d o l 4 2 4 3 1 系统是最简单的一类l 系统，它是确定的、语义无关的系统。在字 符串的重写过程中，字符的替换与它所处的语义环境无关，并且关于某个字符的 替换产生式是唯一确定的。一个d o l 系统可以用一个有序的三元组l = 来表示，对于每一个字符a v ，有且仅有一个单词j ，使得a 寸s 成立，即该系 统的确定性。d o l 系统使用简单，产生式规则的构造相对简便，但是d o l 系统是 确定的、语义无关的，它的产生式规则不能体现具体的语义环境，且是唯一确定 的。这样就使得d o l 系统生成的图形缺乏灵活性，在生成分形图形方面不够生动。 但是它的生成规则简单，易于构造，可以生成一些经典的分形图。 2 2 3 参数l 系统 参数l 系统【4 4 】以d o l 系统为基础，把字符串平行重写过程从仅由字符组成 的单词扩展到了带有参数的字符模块组成的单词，丰富了l 系统产生式的内涵。 通常利用“模块 的概念来表示带参数的字符，规定：字符属于字符集v ，参数 属于实数集r 。由字符a v 和参数口l ，a 2 ，a n r 组成的模块记作a ( a l ，口2 ，a 。) 。 每一个模块都属于集合m = v x r ，其中r 是所有有限参数序列的集合。所有模 块字符串集合和非空模块字符串集合分别记作m = ( v x r ) + 和m + = ( v xr ) + 。模 块中预定义的几何符号和用户定义的符号都可以附带参数。用户定义的参数的意 义取决于系统设计者。 参数l 系统是一个四元组：l = ，其中：y 是系统的字符集；是 系统的参数集； 彩( v x r + ) + j是一个非空单词，称为公理； p c ( v x e ) c ( ) ( y e ( ) + ) ，是产生式规则的有限集合。 参数l 系统的产生式由前驱、条件和后继三部分组成，其一般形式如下： p r e d ：c o n d 争s u c c ， 其中：p r e d 、c o n d 和s u c c 分别表示产生式的前驱、条件和后继。 在参数l 系统中，一个带参数的模块与某个产生式相匹配，它必须满足以下 三个条件： ( 1 ) 模块的字符和产生式的前驱字符相同； ( 2 ) 模块的实参个数和产生式前驱模块的形参个数相等； ( 3 ) 用实参替换产生式前驱模块的形参以后，条件表达式的运算结果为真。 当某个匹配的产生式能用来对某个模块进行重写时，就用该产生式的后继来 替换这个模块，并且用模块中的实参来替换产生式后继中相应位置上的形参。如 果某个模块没有和它相匹配的显式产生式来对其进行重写，则在字符串重写的过 程中就用它自身来进行恒等置换。 在参数l 系统中，可以根据参数的不同取值来决定字符模块产生式的选择， 迭代函数系统的符号化方法 这样就可以通过给参数赋予不同的值来控制分形图的生成，既可以实现分形图的 灵活多样，又可以避免随机l 系统产生的结构畸变。 2 2 4 随机l 系统 随机l 系统【4 5 】是为了改善d o l 系统不够灵活的缺陷，在字符串的重写替换 过程中引入随机性。随机性可以用在最终字符串中字符的解释上，例如“f 代 表前进的步长是可以随机变化的，还可以对一个字符给出多种产生式规则，将概 率值用在产生式的选择上。显然，前一种随机性能够保持基本拓扑结构不变，后 者则能使基本结构发生变化，从而生成更为灵活的结构。 在d o l 系统实现对字符串重写的基础上，对结果字符串中的相同字符给出不 同的解释来实现。在前进时将前进的步长取不同的随机值，或者是在旋转时将旋 转的方向角取不同的随机值，从而来实现最终生成有一定随机性灵活的图形。 多种产生式的随机l 系统是一个有序的四元组：l = ，其中字符 集v 、公理缈和产生式集合p 的定义与d o l 系统中定义的相同；函数万：p _ 0 ，l 】， 称为概率分布，用来确定每个产生式被选中的概率。具体地说，在定义该l 系统 时，以字符a 为前驱的产生式规则可能不只一条，每一条产生式都有各自被选中 的概率值，且这些概率值之和等于1 。随机l 系统的产生式通常表示为： p r e d 专( p r o b ) s u c c 。 其中p r e d 和s u e t 分别为前驱和后继，p r o b 表示该产生式规则被选中的概率。 将概率值用在产生式选择上，对系统定义中的某些字符提供多个产生式规则， 使生成的图形基本结构发生变化，这样的系统十分适合用来具体描述一类植物。 随机l 系统中对于同样的生成规则，经过相同的迭代次数可以生成不同的形态或 拓扑结构，从而在一定程度上实现灵活多变的植物结构图形。但是，由于它是通 过不可控制的随机过程来实现生成图形的多样性的，因此，随机l 系统产生的图 形的结构畸变就无法避免。 2 2 5 语义相关l 系统 在0 l 系统中，重写规则都是上下文不相关的，上下文相关l 系统【4 6 】可以分 为两类：l l 系统和2 l 系统。l l 系统只考虑单边上下文环境，在非随机的情况下， l l 系统的产生式规则可以用如下的形式来描述： p ：a t a ，_ x 其表达的意义为：当a 的左语义为a t 时，ajx ；或者，当a 的右语义为口，时， a x ：2 l 系统的产生式规则可以用如下的形式来描述： p ：a t a 以专x 其表达的意义为：当a 的左语义为a t 并且k 1 的右语义为a r 时，a 哼x ，其中， 1 2 硕+ 学位论文 口，和a ，分别称为a 的左语义和右语义，也可以称为a 的上文和下文。一般地，在 一个上下文相关l 系统中，若对应同一个字母，同时存在上下文相关和上下文不 相关的重写规则，重写时应优先选择符合条件的上下文相关的重写规则。 当产生式p 与待重写