（计算机软件与理论专业论文）基于l系统的植物形态模拟方法的研究与应用.pdf

山东帅范人学硕士学位论文 基于l 一系统的植物形态模拟方法的研究与应用 摘要 分形理论是近二、三十年才发展起来的一门新的学科，它主要描述自然界中的非线 性系统中不光滑和不规则的几何形体。传统的欧氏几何主要研究规则图形和光滑曲线， 对自然植物的描述却显得无能为力，种类丰富的植物虽然形态千差万别，却大都具有自 我相似、自我繁殖的分形特征，分形理论就为自然植物的模拟提供了描述语言和理沦基 础。近年来，分形理论逐渐发展，而分形植物模拟也成为了计算机仿真领域的重要课题。 自从美国生物学家l i n d e n m a y e r 于1 9 6 8 年提出l 一系统后，l 一系统不断完善，为植 物的构型及描绘提供了新的途径。1 9 8 4 年a r s m i t h 等人将l 一系统引入了计算机图形 学中，在计算机上模拟生成了各种形念的植物，显示了计算机在模拟植物方面的强大能 力，为在计算机上实现模拟植物的生长形态提供了理论依据，后来在加拿大学者 p m s i n k i e w i c z 等的发展下，成为植物生长建模的主要方法之一。 传统的基于l 一系统的分形植物虽然也能够表现物种之间的差异和体现物种的多样 性，但分形模拟过程与物种的自然生成过程差别很大，分形过程也无法与自然界的物种 遗传、物种生存环境的选择、进化和变异作用建立必然联系，所以本文在对几种不同类 型的l 一系统和遗传算法基本原理研究分析的基础上，提出了将基于l 一系统的植物模拟 方法与遗传算法结合的思想，以期得到更符合自然规律的植物形态。本文主要工作如下： 1 、在随机l 一系统的参数设计中引入遗传算法。 本文对随机l 一系统中涉及到的参数通过遗传算法进行重新设计，将经过重新设计 的参数表应用于相同的产生式集，可以生成结构有不同变化的植物形态，来继续丰富我 们的植物资料库； 2 、在单规则l 一系统和多规则l 一系统的产生式设计中引入遗传算法。 本文通过遗传算法对l 一系统产生式中的字符或者整个的产生式进行重新设计，并 定义了符合植物生长过程中保持平衡性、稳定性、趋光性等特点的适应度函数，来体现 外界因素对植物生长形态的影响； 3 、把基于l 一系统的植物模拟方法与遗传算法结合的思想应用到虚拟植物生长的过 程中。 植物对它所处的环境，会表现出良好的自适应和自寻优能力，本文在植物生长过程 t 山东帅范人学硕上学位论文 中随时使用遗传算法来调整植物的l 一系统语法，对同一植物在生长过程中根据不同条 件的影响，产生不同的形态变化，可以生成更符合自然规律的植物形态，这在自然景观 再现、虚拟动画、植物学等领域都具有一定的应用价值。 本文利用计算机作图技术，模拟了植物生长过程中分枝结构受外界条件影响后的形 态变化，刘+ 人工智能、人工生命等领域的研究也具有一定的指导和启发意义。 关键词：植物模拟；l 一系统；遗传算法 中图分类号：t p 3 9 1 i i 山东师扎人学硕士学位论文 a b s t r a c t f r a c t a lt h e o r yi sas c i e n c en e w l yd e v e l o p e di nt h ep a s t2 0t o3 0y e a r s ；i tc a nd e s c r i b e r o u g h n e s sa n di r r e g u l a rg e o m e t r i cs h a p e si nt h en a t u r eo ri nn o n - l i n e a rs y s t e m t r a d i t i o n a l e u c l i d i a ng e o m e t r ys t u d i e sr e g u l a rg r 印h i c sa n ds m o o t hc u e s ，t h ed e s c r i p t i o no fm en a t u r a l p l a n ta p p e a r sp o w e r l e s s a l m o u g ht h es h a p e so fp l a n t sa r ed i 虢r e n t ，t h e yh a v et h ec o m m o n c h a r a c t e ro fs e l f 二s i m i l a r i t ya n ds e l f 二r e p r o d u c e f r a c t a lt h e o r yp r o v i d e sad e s c r i p t i o nl a n g u a g e a n dt h e o r e t i c a lf o u n d a t i o no nn a t u r a lp l a n ts i m u l a t i o n w i t ht h ed e v e l o p m e n to ff r a c t a lt h e o r y ， p l a n t sm o d e l i n gu s i n gf r a c t a lb e c a m ea ni m p o r t a n tp r o b l e m o nc o m p u t e rs i m u l a t ef i e l d l - s y s t e m i sc o n t i n u a l l yd e v e l o p i n gs i n c ea r i s t i dl i n d e m n a y e r ， a m e r i c ab i 0 1 0 9 i s t ， i n t r o d u c e di ti n19 6 8 i tp r o v i d e san e wa p p r o a c hf o rc o n f i g u r a t i o no fp l a n t s a r s m i t he t c i n t r o d u c e dl s y s t e mt ot h ec o m p u t e rg r a p h i c si nl9 8 4 a 1 1k i n d so fp l a l l t sc a nb ec r e a t e db yi t i nc o m p u t e r i ts h o w st h ep o w e r f u la b i l i t yo fc o m p u t e ri np l a n t sm o d e l i n g ，a n dp r o v i d e s t h e o r ys u p p o r tf o rr e a l i z i n gv i r t u a lp l a n tg r o w t hi nc o m p u t e r ， s oi tb e c o m e so n eo ft h em a i n p l a n t 伊o 、机hm o d e l i n gm e t h o d sd e v e l o p i n gb yp r u s i i 出i e w i c zi nc a n a d a 1 r a d i t i o n a lf r a c t a lp l a n tb a s e do nl s y s t e mc a nr e f l e c tt h ed i v e r s i t yo ft h ed i 虢r e n t s p e c i e s ，b u tb e t 、v e e nt h ef r a c t a lp r o c e s sa n d t h en a t u r a lp r o c e s si sg r e a td i f i f e r e n t t h ep r o c e s s c a nn o tr e n e c tt h ec h o i c e ，e v o l u t i o na n dm u t a t i o no ft h ep l a n ti nn a t u r e i nt 1 1 i sa n i c l e ，o nt h e b a s i so ft h ea n a l y s i st h eb a s i cp r i n c i p l e so fs e v e r a ld i 丘e r e n tt y p e so fl - s y s t e ma n dg e n e t i c a l g o r i t h n s ，w eb r i n gg e n e t i ca l g o r i t i lt ot h el - s y s t e m t h em a i nw o r ki sa sf o l l o w s ： 1 b r i n gg e n e t i ca l g o r i t h mt ot h ep a r a m e t e r sd e s i g ni ns t o c h a s t i cl s y s t e m t h i sa r r t i c l e d e s i g n st h ep a r a m e t e r so fs t o c h a s t i cl s y s t e mw i t hg e n e t i ca l g o r i t h m ， g e n e r a t e sm o r ek i l l d so fp l a n t 2 b “n gg e n e t i ca l g o r i t t ot h ep r o d u c t i o n sd e s i g ni ns i n g l e - m l e sl s y s t e ma n d m u l t i m l e sl s y s t e m t h i sa n i c l ec h a n g e st h ep l a n tm o 叩h o l o g i e sb yo p e r a t i n gw i t hc h a r a c t e r sa n dp r o d u c t i o n s o fs i n g l e m l e sl - s y s t e ma n dm u l t i r u l e sl s y s t e m ，t h e nd e f i n e sf i t n e s sf u n c t i o nw h i c hc a n k e e pt h eb a l a n c e ，s t a b i l i t ya n dp h o t o t o x i co f t h ep l a n t 3 b r i n gt h el s y s t e ma n d g e n e t i ca l g o r i t l l i l lt ot h ev i n u a lp l a n tg r o 们hp r o c e s s 山东师范大学颂j 二学位论文 t h ep l a n th a v eg o o da d a p t a b i l i t ya n do p t i m i z a t i o ni nd i f j f e r e n te n v i r o n m e n t ，t h i sa n i c l e i n t r o d u c e st h el - s y s t e ma n dg e n e t i ca l g o r i t h mt ot h ev i r t u a lp l a n tg r o w t hp r o c e s s ，i ti n d i c a t e s t h es a m eg e n ei nt h ep l a n tu n d e rt h ei n n u e n c eo fd i f j i e r e n tc o n d i t i o n sc a ng e n e r a t em o r e n a t u r a lp l a n tm o r p h o l o g y t h i sa r t i c l es i m u l a t i n gt h ep l a n tm o r p h o l o g yw i t hc o m p u t e rt e c h n o l o g y ，i th a ss o m e g u i d a n c ea n di n s p i r a t i o ns i g n i f i c a n c ei na n i f i c i a li n t e l l i g e n c e k e yw o r d s ：p l a n tm o d e i i n g ；l s y s t e m ；g e n e t i ca l g o r i t h m c l a s s i f i c a t i o n ：t p 3 9 l 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得( 注：如没有其他需要特别声明的，本栏可 空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已存论文中作了明确的说明并表示谢 = 也 恩。 学位论文作者签名：刹、施 导师签字： 刹雾 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规 定，有权保留向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权堂撞可以将学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：剁、施 导师签字： 越弛 签字日期：腑捐方。日签字日期：腑6 月加日 山东帅范人学坝士学位论文 第一章绪论 1 1 分形问题提出及现实意义 种类繁多的植物是构成自然景物的基础。千百年来，无数的科学家被多姿多彩的自 然植物所吸引，数学家们更是对其显著的几何特性作了广泛的研究【l 】。结果表明，自然 界中的植物虽然形态干差万别，去| j 大都蕴含着一个同样的、具有自相似性质的物质结构 规则：植物体中每一相对独立部分的形念构造模式是整体构造模式的缩影。f 是基于植 物的这一几何特性，使得许多人致力于利用分形理论进行植物模拟的研究【2 1 。 传统的欧氏几何主要研究规则图形和光滑曲线，对自然景物的描述却显得无能为 力。2 0 世纪7 0 年代b m a n d e l b r o t 创立了分形理论，用来描述那些不规则而欧氏几何无 法描述的几何现象和物体，被誉为“大自然本身的几何学”，使自然景物的描绘成为可 能，这也是分形可以得到高度重视的原因之一【3 】。 近二十年来，分形的研究受到非常广泛的重视，其原因在于分形既有深刻的理论意 义，又有巨大的使用价值，它吸引着人们探寻和探讨其中可能的新规律、新方法和新特 征【4 1 。 随着分形理论的发展，分形理论已经运用到许多领域，其研究和应用领域包括了许 多方面，如在图像、数据的压缩方面的研究，在计算机图形学领域的应用，在虚拟植物 模拟中的应用，及在社会科学中的应用【5 】。分形很快的被人们所接受，并且引起人们的 极大关注，用分形理论原理由计算机描绘出来的自然界景象，例如山、云、水、植物等， 简直可以与艺术大师门的杰作媲美，确实令人赞叹不已，甚至可以达到以假乱真的程度。 许多作品都被好莱坞的特技行业成批地采用了1 6 j 。 今天，人们不止满足于景物模型的塑造，市场的需求和人类的好奇心理促使计算机 图形学的工作者们深入研究，把景物模型进一步复杂化以满足影视、游戏、仿真等各个 方向的特定要求。许多计算机可视化的手段诸如几何优化、光照、纹理等越来越多地介 入其中，使自然景物的模拟结果或以假乱真、或出神入化、或科学实用。以计算机为手 段对自然景物进行建模与仿真，将为探索大自然的奥秘和植物生长的规律，以及改善人 类生存环境质量带来新的契机。与此同时，以模拟自然景观为内容的娱乐、教育软件也 是不可忽视的发展方向。近年来，计算机自然景物的模拟因其所具有的广泛应用领域而 山东帅范人学硕士学位论文 成为计算机图形学的一个重要分支。 1 2 国内外研究现状 分形植物模拟就是基于分形理论的植物形态模拟，其原理是利用植物自身结构的分 形性质( 结构自相似性) 生成植物图形或图像的方法【7 j 。当前，分形植物模拟的方法主 要有l 一系统、迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，i f s ) 、受限扩散凝聚( d i f f u s i o n l 。i m j t e da g g r e g a t i o n ，d l a ) 模型和粒子系统。这四种方法的算法原理不同，模拟对象 也各有侧重弘j 。 1 9 6 8 年，美国生物学家l i n d e n m a y e r ( 1 9 2 5 1 9 8 9 ) 在生物理论杂志上发表了名为 “m a t h e i i l a t i c a lm o d e l sf o rc e l l a ri m e r a c t i o n si nd e v e l o p m e n t ”的论文，首次提出著名的 “字符串重写系统( s t r i n gr c w r i t i n gs y s t e m ) ”，习惯称之为l 一系统( l s y s t e m ) 【9 j 。 它是一种关于植物形念与生长的描述方法，_ f 始只着重于植物的拓扑结构，即植物组件 ( 主干、枝条等) 之间的相邻关系，后来把几何解释加进描述过程，形成后来被人们重 视的l 一系统，并在模拟植物、单细胞动物及器官等各方面有了进一步的研究及应用i l 。 l 一系统以自动机理论为基础，用符号空间的一个符号序列来表示细胞的状态，通过 符号序列的变化来描述人工生命的形态生成过程。l 一系统的本质是一个重写系统，通过 对植物对象生长过程的经验式概括和抽象，初始状态与描述规则，进行有限次迭代，生 成字符发展序列( d e v e l o p m e n t a ls e q u e n c e so f w o r d s ) 以表现植物的拓扑结构，并对产生 的字符串进行几何解释，就能生成非常复杂的分形图形，并在加拿大学者p m s i n k i e w i c z 等的发展和应用下，成为植物生长建模的主要方法之一【l 。l 一系统适合于描述分形现象； 也适合描述植物的形态结构。l 一系统实质上表明，在复杂的自然现象的背后，存在着简 单的规律，换言之，我们可以寻找到简单的方式来描述自然界的复杂现象引。 为建立完整有效的植物模型，l 一系统的功能不断地被扩展，其中加拿大学者 p m s i n k i e w i c z 为l 一系统的发展做出了杰出的贡献。早期的l 一系统简称为d o l 一系统，前 缀d 代表确定性，o 代表与上下文无关( c o m e x tf r e e ) 。通过加上几何形态信息，诸如 线段的长度和线段的转角等，d o l 一系统利用“龟行解释 ( t u r t l ei n t e 印r e t a t i o n ) 法，可 以模拟分形几何图形。随机l 一系统克服了确定性l 一系统只能生成规则分形图形的局限， 可构造随机的植物拓扑结构，参数化l 一系统使l 一系统能够模拟时延信息【l 引。 l i n d e i u l l a y e r 曾将植物单元间的信息传输分为两种形式：胞后代( c e l l u l a rd e s c e n t ) 信息 与交互作用( i n t e r a c t i o n ) 信息。前者体现了子代单元是继承了父代单元，或植物内因 2 山东帅范人学硕士学位论文 ( e n d o g e n o u s ) 的发展现象。应用上下文无关l 一系统可以实现胞后代信息传输功能。而 上卜文相关( c o n t e x t s e n s i t i v e ) l 一系统的提出主要是用于表现植物生长过程中的外因 ( e x o g e n o u s ) 发展特征：植物器官单元的发育与其相邻器官状态是相关的。ll 一系统 是只包括单边的上下文相关系统。当采用左相关语法时，该系统可以模拟植物从根向茎、 叶的信息传输，反之则相反。k u r c h 与s l o b o d a 认为上下文相关的l 一系统在表现与环境 交互方面是有缺陷的，因为上下文相关功能只能提供局部的敏感性i l 引。m e c h 与 p m s i n k i e w i c z 发展了所谓的“丌放式( o p e n ) l 一系统”，该系统在形式化公理与产生式 中引入了交流单元( c o m m u n i c a t i o nm o d u l e s ) ，用于传送、调整“环境植物”两方 的相互信息，以实现植物与环境并发过程的模拟研究。他们给出了典型的应用实例之一 是植物根系的发展过程模拟，其中除了给定根系模型之外，还给出了土壤中水含量的模 型。该研究从原理上表现了植物生长与局部环境的动态耦合过程，即根系的吸水效应改 变了周围的土壤水分含量，而水分含量分布的变化又影响了根系的发展方向【1 5 】。为了模 拟植物的连续生长过程，p m s i l l l ( i e w i c z 等提出了时变l 一系统。为了进一步表示植物的连 续变化过程，p r u s i n k i e w i s z 等又提出了微分l 一系统( d i f f e r e m i a ll s v s t e m ) ，该系统能 较好的模拟植物的叶序、花朵、以及模拟植物生长竞争、裁减等的条件下的情况。 国内也有很多学者和分形爱好者致力于l 一系统的研究，主要内容集中在三个方面： 一是利用l 一系统的基本原理，在计算机上绘制例如雪花、c 型、地毯等艺术类图案和少 量的蕃类植物f 1 6 1 7 】；二是在基本l 一系统的基础上进行一些改进和创新，丰富模拟植物 的种类【1 8 】；三是尝试将l 一系统用于三维植物形态的模拟构造【1 9 、2 0 2 1 1 。国内学者在这些 方面都做了很多工作，如利用l 系统的理论，结合计算机图形学，模拟了个别植物的 造型，如树、叶、花等【2 2 】；利用d o l 一系统模拟简单树木的三维造型【2 3 】；将l 一系统与 i f s 有机融合，利用l 一系统生成植物的枝干结构，利用i f s 生成植物的叶片，达到扬长 避短的目的【2 4 】；针对l 一系统的字符串规则灵活性不够的问题，提出建立一种较为通用 的基于l 一系统规则语言分析器的解决方法【2 5 1 。但总的看，l 一系统模拟生成的植物种类 比较单一、死板，更无法体现植物的动态生长过程，而且其产生式规则也没有一致的确 定方法。 进化思想，如遗传算法等，一直以来在解决许多问题方面都被广泛应用。遗传算法 已用于求解带有应用前景的一些问题，例如遗传程序设计、函数优化、排序问题、人工 神经网络、分类系统、计算机图像处理和机器人运动规划等【26 | ，现在又被用来解决植物 模拟中的复杂问题。 山东师 ! c 【大学硕士学位论文 1 9 9 3 年，m c m o m a c k 发表了第一篇用l 一系统进行进化的文章，通过交互的思想， 模型可以控制最终的结果基因型，产生新颖的几何形态，它在生成下一代基凼前先构建 初期的基因型，可以保证最后生成的结果是有意义的【2 7 28 1 。1 9 9 9 年，c u 删发展了 m c m o m a c k 的理论，他的思想的主要不同在于其初期的基因型是封装的，进化过程中 l 一系统的文法保持不变。相对于改变文法规则的方式，c u n y 对七个浮点型参数进行交 叉和变异操作，这些参数来自h o n d a 标准，但最终只可以满足部分标准的要求。令人惊 奇的是，这种思想可以产生大量各异的分枝结构，即使对l 一系统不是很熟悉的人员， 也可以用它来生成植物模型【2 9 1 。j a c o b 将k o z a 的遗传工程技术【3 0 3 1 1 应用到了自动构造 i 厂系统的问题上，提出了g e n e t i cl s y s t e mp r o g r a m m i n g ( g l p ) 的思想，他将模式思 想用到了l 一系统的产生和修改当中，这种层次化的模式有许多优点，相对于直接用符 号来构造产生式，它使每一代的文法结构更简单有效。另外，它可以用来强化对l 一系 统基本规则的要求，来预防其产生式中出现不能匹配的括号，对这种进化过程中可能会 出现的潜在问题提供了解决方案，他证明了遗传算子可以应用于l 一系统1 3 2 、3 引。j a c o b 继 续他之前的研究，将其应用于繁殖和进化人工花卉，利用模板和适应度函数来产生形态 各异的花卉【3 4 3 5 1 。1 9 9 8 年，o c h o a 总结了各种进化方法，提出了一种新的思想，使模 拟者可以在遵守预先定义的规则的前提下，人为的干预进化的过程，这样可以保证只有 相关的基因型模板可以进行进化操作，生成更符合规律的结构形念【36 | 。 1 3 本文主要章节及结构安排 本文在对几种不同类型的l 一系统和遗传算法基本原理研究分析的基础上，提出了 将基于l 一系统的植物模拟方法与遗传算法结合的思想，以得到更符合自然规律的植物 形态，主要工作包括以下几个方面： l 、在随机l 一系统的参数的设计中引入遗传算法。 本文对随机l 一系统中涉及到的参数通过遗传算法进行重新设计，对于相同的产生 式集可以生成结构有不同变化的植物形态，来继续丰富我们的植物资料库； 2 、在单规则l 一系统和多规则l 一系统的产生式设计中引入遗传算法。 本文通过遗传算法对l 一系统产生式中的字符或者整个的产生式的进行重新设计， 并定义了符合植物生长过程中保持平衡性、稳定性、趋光性等特点的适应度函数，来体 现外界因素对植物生长形态的影响； 3 、把基于l 一系统的植物模拟方法与遗传算法结合的思想，应用到虚拟植物生长的 山东帅范人学倾j j 学位论文 过程巾。 植物对它所处的环境，会表现出良好的自适应和自寻优能力，本文在植物生长过程 中随时使用遗传算法来调整植物的l 一系统的语法，对同一植物在生长过程中根据不同 条件的影响，产生不同的形态变化，可以生成更符合自然规律的植物形态，这在自然景 观再现、虚拟动画、植物学等领域都具有一定的应用价值。 本文的结构如下： 第一章绪论，简要介绍了课题的研究背景、意义及当前国内外在分形领域的研究现 状和论文的主要内容及组织结构。 第二章分形理论基础，内容包括：分形的提出，分形植物模拟的提出及意义，并简 单介绍了目前常用的几种分形植物模拟方法的基本原理，并比较了各种方法在模拟对象 方面的侧重点。 第三章l 一系统的基本原理及实现，主要介绍了l 一系统及遗传算法的基本原理，详 细介绍了d o l 一系统、随机l 一系统、参数l 一系统、微分l 一系统、上下文相关l 一系统， 并在v c 6 0 环境下进行了程序实现。 第四章在随机l 一系统的参数设计中、单规则l 一系统和多规则l 一系统的产生式的设 计中引入遗传算法。对随机l 一系统中涉及到的参数通过遗传算法进行重新设计，可以 继续丰富植物资料库；对l 一系统产生式中的字符或者整个的产生式的进行重新设计， 并定义了符合植物生长过程中保持平衡性、稳定性、趋光性等特点的适应度函数，来体 现外界因素对植物生长形态的影响；把基于l 一系统的植物模拟方法与遗传算法结合的 思想，应用到虚拟植物生长的过程中，使用遗传算法来调整植物的l 一系统的语法，对 同一植物在生长过程中根据不同条件的影响，产生不同的形态变化，可以生成更符合自 然规律的植物形态。 第五章总结与展望，对本文的研究成果进行概括并指明今后的研究方向。 山东师范大学倾士学位论文 2 1 分形的提出 第二章分形基本理论 不规则的几何形状在我们周围处处可见，诸如花草、山脉、烟云、火焰等等举目皆 是，大自然在向我们展示其美丽多姿的同时，也向我们提出了严峻的挑战：怎样描述这 种不规则的自然现象呢? 从5 0 年代起，b m a n d e l b r o t 孤身一人，整同思索着一种新的几何学。他试图通过 这种几何学统一描述自然界、人类社会中普遍存在的各种不规则现象，如流体流动、曲 折的海岸线、多变的天气、动荡的股市、经济收入分配关系、棉花的价格波动等等。严 格说，那时候他自己也不明确自己在找什么，甚至不知道要找的是一种新的几何学。 引用分形这一学科当之无愧的领袖人物m a n d e l b r o t 的话来说： “为什么几何学常常被说成是冷酷无情和枯燥乏味的? 原因之一在于它无 力描写云彩、山岭、海岸线或树木的形状。云彩不是球体，山岭不是锥体，海岸线不是 圆周，树皮并不光滑，闪电更不是沿着直线传播的。更为一般地，自然界的许多图样是 如此地不规则和支离破碎，以致与欧几里得( 几何) 相比，自然界不只具有较高程度的 复杂性，而且拥有完全不同层次上的复杂度。自然界图样的长度，在不同标度下的数目， 在所有实际情况下都是无限的。这些图样的存在，激励着我们去探索那些被欧几里得搁 置在一边，被认为是无形状可言的形状，去研究无定形的形态学。然而数学家 蔑视这种挑战，他们想出种种与我们看得见或感觉到的任何东西都无关的理论，却回避 大自然提出的问题。作为对这个挑战的回答，构思和发展了大自然的一种新的几何学， 并在许多不同领域中找到了用途。它描述了我们周围的许多不规则和支离破碎的形状， 并通过鉴别出一族称为分形的形状，创立了相当成熟的理论”【3 。 分形不但抓住了浑沌与噪声的实质，而且抓住了范围更广的一系列自然形式的本 质，这些形式的几何在过去相当长的时间里是没办法描述的，或者被高贵的科学认为是 不屑于研究的，它们包括：海岸线、树枝、山脉、星系分布、云朵、聚合物、天气模式、 大脑皮层褶皱、肺部支气管分支以及血液微循环管道等等。分形在自然界中太普遍了， 用分形语击去描绘大自然丰富多彩的面貌，应当是最方便、最适宜的。j 下因如此，人们 6 山东师范大学倾士学位论文 说“分形是大自然的几何学【3 引、“分形处处可见”盼4 0 1 。 到底什么是分形呢? 开始时，m a n d e l b r o t 把那些h a u s d o r f f 维数不是整数的集合称 为分形。按这个定义，某些看来应该是分形成员的，例如著名的p e a n o 曲线，就被排除 在外，于是m a n d e l b r o t 又修改了原来的定义，说分形是那些局部和整体按某种方式相似 的集合，这是目前关于分形定义普遍被接受的说法。研究分形，似乎如同研究生命一样， 先弄清楚定义再研究，还是在研究、发展之中给出科学的定义，看来还是后者更有道理。 到目自，为止，分形尚无最后的定义。k f a l c o n e r 认为，对分形的定义，可以用生物 学中对“生命”定义的办法。“生命”是很难定义的，但却可以给出一系列生命对象的 特征，例如繁殖能力，运动能力。除了有些对象例外，大部分情形都能因此而得到分类， 于是就不会因为暂时没有严格的定义而停步不前。对分形似乎也宜于给出一系列特征性 质，当集合具备这些性质时就可以认为是分形；当因此而排除掉一些自己的同类时，再 作特殊的研究。按这种观点，称集合f 是分形，是指它具有下面典型的性质： ( 1 ) f 具有精细的结构，也就是说，在任意小的尺度下，它总是有复杂的细节； ( 2 ) f 是不规整的，它的整体与局部都不能用传统的几何语言来描述； ( 3 ) f 通常有自相似形式，这种自相似可以是近似的或统计意义下的； ( 4 ) 一般地，f 的某种定义之下的分形维数大于它的拓扑维数； ( 5 ) 在大多数令人感兴趣的情形下，f 以非常的方法确定，可能由迭代过程产生。 综观上述f a l c o n e r 的说明，不难发现其中有较大的灵活性，比如：( 1 ) 中的“精 细”，“细节”作何解释? ( 2 ) 中“不能”的说法怎样操作? 因为“不能”需论证，而 没有做到的事不可以说是不能做到的；“几何语言”指的是什么? ( 3 ) 自相似怎样理解? 以及“大多数令人感兴趣的情形”，更是没有确切的标准。 分形是自然形态的几何抽象，如同自然界找不到数学上所说的直线和圆周一样，自 然界也不存在“真j 下的分形”。只要注意到分形包含一个无穷小尺度的内涵，便可以知 道自然形态只是停留在一定层次内可以合理地按分形模型来考虑。从背景意义上看，说 分形是大自然的几何学是恰当的。 2 2 分形植物模拟的提出及意义 种类繁多的植物是构成自然景物的基础。千百年来，无数的科学家被多姿多彩的自 然植物所吸引，数学家们更是对其显著的几何特性作了广泛的研究。结果表明，自然界 中的植物虽然形态千差万别，却大都蕴含着一个同样的、具有自相似性质的物质结构规 7 山东帅范人学硕上学位论文 则：植物体巾每一相对独立部分的形态构造模式是整体构造模式的缩影。正是基于植物 的这一几何特性，使得许多人致力于利用分形理论进行植物模拟的研究( 4 2 1 。 2 0 世纪7 0 年代，美国科学家m a n d e l b r o t 创立了分形几何学【4 3 4 引，用来描述那些不 规则、欧氏几何无法描述的几何现象和物体，被誉为“大自然本身的几何学”，开创了 2 0 世纪分形理论的发展。分形理论作为研究非线性问题的一门新兴学科，引起了许多科 学家的关注，因为传统的欧氏几何主要研究规则图形和光滑曲线，对自然植物的描述却 显得无能为力。分形理论研究的对象正是在非线性系统中产生的不光滑和不可微的几何 形体，对应的定量参数是维数，是刻画混沌运动的直观几何语言，更是接近现实世界的 数学。因此，分形几何为自然植物的模拟提供了描述语言和理论基础。 自然景物模拟是计算机图形学应用的前沿课题，而植物模拟则是其中最诱人的研究 领域之一。以计算机为手段对植物生长进行建模与仿真，将为探索植物生命的奥秘和生 长过程的规律，以及改善人类生存环境质量带来新的契机。对于中国这样的一个农业大 国、林业弱国，开展植物生长的建模研究有着特别重要的意义。在植物的生长发育过程 中，无论是枝叶还是根系，都呈现出对环境的良好适应，最大限度地满足了自身生命活 动的各种需要，这种自适应和自寻优能力是一种自然智能，对人工智能研究有重要参考 价值。同时，以模拟植物生长为内容的娱乐、教育软件也是不可忽视的发展方向。植物 生长模拟涉及到众多领域，包括植物生理学、作物栽培学、农业气象学和微气象学、土 壤学、微生物学、计算机科学等众多学科，该领域吸引了许多计算机科学家、植物学家 以及数学家等，他们提出了许多模拟植物的方法和模型，并开发了许多植物模拟软件。 现今，对于植物模拟主要有两个研究方向：第一是单纯的植物外观形态模拟，注重形念 的逼真性，其目的为自然景观的再现，主要用于教育、娱乐、商业、园林规划等领域； 第二是真实植物生长过程的模拟，注重植物学理论的真实性，其目的在于植物生长过程 的研究，可用于农田试验、作物病虫害研究、资源环境分析、作物栽培指导、及作物生 长机理的研究等【4 5 j 。 因此，正是分形理论的发展，使自然植物的描绘成为可能，这也是分形几何得到高 度重视的原因之一。近年来，基于分形的自然景物模拟己成为计算机图形学应用研究的 自订沿课题，而对自然植物的模拟则是其中的难点和重点。 2 3 分形植物模拟的方法 分形植物模拟就是基于分形理论的植物形态模拟，其原理是利用植物自身结构的分 山东师范大学硕i ：学位论文 形性质( 结构自相似性) 生成植物图形或图像的方法。当自订，分形植物模拟的方法毛要 有l 一系统、迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ，i f s ) 、受限扩散凝聚( d i f m s i o n l i m i t e da g g r e g a t i o n ，d l a ) 模型和粒子系统。这四种方法的算法原理不同，模拟对象 也各有侧重。 2 3 1 迭代函数系统法 i f s ( i t e r a t e df u n c t i o ns y s t e m ) 法是分形绘制的典型方法。它是i i u t e h i n s o n ( 1 9 8 1 ) 和b a m s l e v ( 1 9 8 5 ) 提出并发展起来的一种研究分形的数学方法，i f s 的基本思想并不 复杂，它认定几何对象的全貌与局部，在仿射变换的意义下，具有白相似结构。这样一 来，几何对象的整体被定义以后，选定若干仿射变换，将整体形态变换到局部，并且这 一过程可以迭代地进行下去，直到满意的造型。其理论依据及应用效果是基于著名的压 缩映射不变集定理和拼帖定理。i f s 可以定义为由一组满足一定条件的映射函数纰( 例 如压缩的仿射变换) 及一组变换发生的概率p ：，组成：i f s = ( q ，p ) li = 1 ，2 ，3 n ， 利用i f s 生成植物图像的方法是对初始植物图像按照己知概率选择函数而实施的一种迭 代变换。迭代函数系统用很少的数据就能完成图像的模拟，在图像压缩方而显示了很大 优势，也是一个很诱人的研究领域。i f s 主要用于分形绘制和图像压缩。这方面的研究 主要集中在利用i f s 码进行图像绘制和求已知图像的i f s 码，以及图像压缩方面。 2 3 2 受限扩散凝聚法 受限扩散凝聚( d l a ) 法是美国科学家w i t t e n 和s a n d e r 于1 9 8 1 年提出的，其基本 方法是：在一个平面网格上选定一个静止的微粒作为种子，然后在距种子较远的格点上 产生一个微粒，令微粒沿网格上下左右的方向随机行走。如果该微粒在行走过程中与种 子相碰，就凝聚在种子上；如果微粒走到边界上，就被边界吸收而消失。如此重复上述 步骤，就会以种子为中心形成一个不断增长的凝聚集团，利用d l a 或其修改的模型可 以对部分植物的形态结构进行计算机模拟，如植物根系的生长过程模拟和海藻类植物的 形态结构模拟等。d l a 模型主要用于模拟各种分形生长和凝聚现象。 9 山东师范大学硕士学位论文 2 3 3 粒子系统法 粒子系统法的基木思想是用大量的、具有一定生命的粒子图元来描述自然界不规则 的模糊景物。每个粒子在任一时刻都具有随机的形状、大小、颜色、透明度、运动方向 和运动速度等属性，并随时间推移发尘位置、形态的变化。每个粒子的属性及动力学性 质均由一组预先定义的随机过程来说明。粒子在系统内都要经过“产生”、“活动和 “死亡”这三个具有随机性的阶段，在某一时刻所有存活粒子的集合就构成了粒子系统 的模型。粒子系统适合用来模拟山、水、树丛、草地等模糊、随机图像。 综上所述，虽然i f s ，d l a 模型、粒子系统和l 系统都能用来模拟一些自然植物， 但是它们的模拟对象各有侧重。d l a 模型适合模拟一些凝聚现象，因而模拟对象受限。 粒子系统在模拟森林、草地等方面具有其无可比拟的优点，而在对单株自然植物的模拟 中却无能为力。本文的研究对象以l 系统为主，重点以其来模拟植物生长的分枝结构 形态。 l o 山东! j i i j 范人学硕，l 学位论文 第三章l 一系统的基本原理及实现 3 1l 一系统的基本原理 l 一系统实质上就是一个基于符号重写系统。其核心概念是重写( r e w i t i n g ) ，重写 的基本思想是根据预先定义的重写规则( 生成规则) 集，1 断地生成复合形状，片j 它来 取代初始简单物体的某些部分以定义复杂物体。 下面举一个例子直观地理解重写概念，说明并行重写系统的基本特征。 考虑由两个字母a 和b 组成的字符串，称为单词。a ，b 可在同一单词中出现多次， 每个字母与一个改写规则有关。例如，如果写b a ，那么代表字母b 用a 替换；a a b 表示字母a 用a b 替换，这便是改写规则。改写过程从一个称作公理的单词丌始，例如 这个单词仅包括一个字母b ，那么第一步由规则b a 可知公理b 被a 替换；第二步，由 生成规则a a b ，a 被a b 替换。单词a b 由两个字母组成，在下一步两个均被同时替换， 得到新的单词a b a ；接着，由a b a 生成a b a a b ，由a b a a b 又生成a b a a b a b a ，然后是 a b a a b a b a a b a a b ，上述过程可一直进行下去，最后得到一个山a 和b 两个字母组成的字符 串序列。如下图所示： b a a b a b a a b a a b a b a a b a b a a b a a b a b a a b a a b 图3 1l 一系统并行重写实例 这个例子描述了如何从一个单词出发，依据两条规则，递归地产生新的字符串的过 程。这种作法用来表示植物的生长过程十分有效。 l 一系统的数学模型可用“乌龟行走算法”解释，其思想是：将龟形状态定义成一个 三元素集合( x ，y ，口) ，其中笛卡尔坐标( x ，y ) 表示龟形的位置，方向角口表示龟头的 方向，给出步长d 和角增量万，龟形对应于下列命令： l l 山东帅范人学硕士学位论文 f ( d ) ：向前移动一步，步长为d ，龟形状态变为( x ，y ? 口) ，其中x = x + d c o s 口， y = y + d s i n 口，在点( x ，y ) 和( x ，y ) 间画一直线段； + ( 艿) ：向左转万，龟形的下一状态为( x ，y ，口+ 占) ，角的正向为逆时针方向； 一( j ) ：向左转万，龟形的下一状态为( x ，y ，口一万) ，角的正向为顺时针方向。 f jl + ff 图3 2 字符“f 、+ 、一”的含义 如果用于模拟树木的分叉，需加入以下两个新的符号，用龟形解释如下： “ ”：将龟形的当前状态压入堆栈。存入堆栈的信息包括龟形的位置和方向以及 其它一些属性，如所画线段的颜色及宽度等； “】：从堆栈中弹出一个状态作为当前状态，不画线。 例如，字符串“f + f f 一f