（计算机软件与理论专业论文）植物形态的分形模拟.pdf

摘唼 摘要 植物足自然界的一个重要组成部分，与我们的生活息息相关。随着分形学 的研究和发展，植物模拟已成为人们研究的热点问题。植物模拟在人工智能、 计算机游戏、虚拟现实、教学软件、农林业研究等领域中占有重要的地位，有 着广阔的应用前景。 本文主要对确定l 一系统、随机l 系统、参数l 一系统、语义l 一系统、开放 l 一系统等作了深入研究，在l 系统符号解释扩展的基础上，利用丌放l 一系统初 步探索了植物与环境的关系，初步研究了植物内部和外部的信息传递。在此基 础上，作者利用l 系统理论，采用标准图形软件接口o p e n g i 和支持可视化编 程的集成，l ：发环境v c + + 6 0 ，实现了植物模拟的演示系统。另一方面，运剧光 照、纹理映刺等技术，结台植物生长过程中的随机因素和趋光性等自然现象， 实现了植物生长过程的计算机模拟，生成的植物具有三维立体效果，形态逼真， 符合自然生长规律。 本文利用计算机作图技术，模拟了植物生长发育过程，找出了植物生长发 育过程中的自然智能因素，对人工智能、人工生命等领域的研究具自一定的指 导和启发意义。同时，本文的研究有助于揭示自然界的一个道理：看似复杂的 自然现缘背后其实蕴藏着简单的规律。 关键词：分形l 系统植物模拟环境 a b s t r a c t p l a n t ，a sa ni m p o r t a n tp a r to ft h en a t u r e ，i sc l o s e l yr e l a t e dt oo u r l i f e a l o n g w i t h t h er e s e a r c ha n dd e v e l o p m e n to ff r a c t a l ，s i m u l a t i o no t 、p l a n th a sb e c o m eah o tt o p i c s i m u l a t i o no fp l a n tp l a y sa ni m p o r t a n tr o l ei na r t i f i c i a li n t e l l i g e n c e ，c o m p u t e rg a m e ， v i r t u a l r e a l i t y 、c a i 。a g r i c u l t u r e a n d f o r e s t r y r e s e a r c he t c a n dh a sh a daw i d e a p p l i c a t i o ni nt h e s ea r e a s t h i sa r t i c l em a k e sad e e pr e s e a r c ho nt h ed e f i n i t e1 - s y s t e m ，s t o c h a s t i cl - s y s t e m p a r a m e t r i cl - s y s t e m ，c o n t e x tl - s y s t e m o p e n1 - s y s t e m ，a n di n t e g r a t e so t h e re x t e n s i o n o fs y m b o li n t e r p r e t a t i o n i tm a k e se x p l o r a t o r yr e s e a r c ho nt h er e l a t i o n s h i pb e t w e e n p l a n ta n de n v i r o n m e n t o nt h eb a s i so f o p e n1 - s y s t e m i ta l s om a k e s ab a s i cr e s e a r c ho n t h ei n l b r m a l i o nt r a n s f e rb e t w e e np l a n ti n t e r i o ra n dp l a n te x t e r i o r t h e n i t g i v e sa c o m p u t e rp r o g r a mt od e m o n s t r a t et h es i m u l a t i o no fp l a n t t h ep r o g r a mi sd e v e l o p e d b yv c + + 6 0 u s i n gt h es t a n dg r a p h i cp r o g r a m m i n g i n t e r l a c eo p e n g l o nt h eo t h e r h a n d t h ed r a w i n gp a r to ft h ep r o g r a ma p p l i e st h et e c h n o l o g yo fi l l u m i n a t i o n a n d t e x t u r em a p p i n g ，t a k i n gi n t oa c c o u n ts o m en a t u r ep h e n o m e n as u c ha sr m a d o mn a t u r a l f a c t o ra n d p h o t o t r o p i s m t h ep l a n t ，g e n e r a t e d b y t h e p r o g r a m ，t h u s i s t h r e e d i m e n s i o n a l v i v i d a n da c c o r dw i t hn a t u r a l l a w 1 h i sa r t i c l ef i n d so u tt h en a t u r a li n t e l l i g e n c ei n g r e d i e n ti nt h eg r o w i n gp l o e c s so f p l a n tb ym e a n so fc o m p u t e rs i m u l a t i o no fp l a n tg r o w t hb a s e do nc o m p u t e i g r a p h i c t e c h n o l o g y c o n s e q u e n t l yi t h a sg u i d a n c ea n ds u g g e s t i o nm e a n i n gt ot h es t u d yo t a l a n da r t i f i c i a ll i f e a tt h es a m et i m et h er e s e a r c ho ft h i sa r t i c l eh e l p s t od i s c o v e ra n a t u r a lp r i n c i p l e ：as e e m i n g l yc o m p l i c a t e dn a t u r a lp h e n o m e n o nc o n t a i n ss i m p l er u l e s k e yw o r d s ：f i a c t a l ，l - s y s t e m ， s i m u l a t i o no f p l a n t e n v i r o n m e n t 两北r 业人：学f i ! ；ji 。论文 鹅一哥绪论 第一章绪论 1 1 研究背景 几个世纪以来，自然界多姿多彩的自然景物吸引了无数的科学家，数学家 们对其显著的几何特性作了广泛的研究。研究表明，自然界中植物形态虽然千 差万别，却大都蕴含着一个同样的、具有自相似的物质结构规则，亦即植物体 的每一相对独立部分的形态构造模式是整体形态构造模式的缩影。 传统的欧氏几何主要研究规则图形和光滑曲线，对自然景物的描述却显得 无能为力。2 0 世纪7 0 年代b m a n d e l b r o t 创立了分形几何学，用来描述那些不 规则而欧氏几何无法描述的几何现象和物体，被誉为“大自然本身的几何学”， 使自然景物的描绘成为可能，这也是分形几何得到高度重视的原因之一。 自然景物模拟是计算机图形学应用的前沿课题，而植物模拟则是其中最诱 人的研究领域之一。以计算机为手段对植物生长进行建模与仿真，将为探索植 物生命的奥秘和生长过程的规律，以及改善人类生存环境质量带来新的契机。 对于中国这样的一个农业大国、林业弱国，开展植物生长的建模研究有着特别 蘑要的意义。农林业信息化将成为2 1 世纪的重要发展趋势，生念环境保护与建 设是人类社会可持续发展的永恒主题。在植物的生长发育过程中，无论是枝叶 还是根系，都呈现出对环境的良好适应，最大限度地满足了自身生命活动的各 种需要，这种自适应和自寻优能力是一种自然智能，对人工智能研究有重要参 考价值。同时，以模拟植物生长为内容的娱乐、教育软件也是不可忽视的发展 方向。本文就是作为人工智能教育软件来研究的。 1 2 研究现状 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 m a t i c a l m o d e l s f o r c e l l a r i n t e r a c t i o n s i n d e v e l o p m e n t ”的论文， 酋次提出著名的“字符串重写系统( s t r i n gr e w r i t i n gs y s t e m ) ”，习惯称之为l 一 系统( l s y s t e m ) 它是一种关于植物形态与生长的描述方法，开始时只着重于 植物的拓扑结构，即植物组件( 主干、枝条等) 之间的相邻关系，后来把几何 解释加进描述过程，形成后来被人们重视的l 一系统2 l 。以后在加拿大学者 登! ! ! 些叁! ：型! ! 堡兰 笙二! 笪堡 p r u s i n k i e w i c z 等的发展和应用下，成为植物生长建模的主要方法之一。 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 ) 以表现植物的拓扑结构，并对产生的字符串进行几何解释，就能生成非常复杂 的分彤图形。l 一系统适合于描述分形现象；也适合描述植物的形态结构。l 一系 统实质上表明。在复杂的自然现象的背后，存在着简单的规律，换言之，我们 可以寻找到简单的方式来描述自然界的复杂现象。 为建立完整有效的植物模型，l 一系统的功能不断地被扩展，其中加拿大学 者p r u s i n k i e wi c z 为l 一系统的发展作出了杰出的贡献。早期的l 系统简称为 d o l 一系统。前缀d 代表确定性，0 代表与上下文无关( c o n t e x tf r e e ) 。通过加上 儿何形态信息，诸如线段的长度和线段的转角等，d o l 一系统利用“龟行解释” r t u i t l ei n t e r p r e t a t i o n ) 法，可模拟分形几何图形。随机l 系统克服了确定性l 系统只能生成规则分形图形的局限，可构造随机的植物拓扑结构。参数化i 。一系 统使l 一系统能够模拟时延信息”】。l i n d e n m 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 ) 信息。前 者体现了子代单元是继承了父代单元，或植物内因( e n d o g e n o u s ) 的发展现象。 应用上下文无关l 一系统可以实现胞后代信息传输功能。而上f 文相关 ( c o n t e x t s e n s i t i n e ) l 一系统的提出主要是用于表现植物生长过程中的外因 ( e x o g e n o u s ) 发展特征：植物器官单元的发育与发生与其相邻器官状态是相关 的。i l 系统是只包括单边的上下文相关系统。当采用左相关语法叫，该系统可 以模拟植物从根向茎、叶的信息传输，反之则相反。k u r t h 与s l o b o d a 认为上下 文相关的【一系统在表现与环境交互方面是有缺陷，因为上下文相关功能只能提 供局部的敏感性。m e c h 与p r u s i n k i e w i c z 发展了所谓的“开放式( o p e n ) l 一系统” 1 4 1 ，该系统在形式化公理与产生式中引入了交流单元( c o m m u n i c a t i o nm o d u l e s ) ， 用于传送、调整“环境一植物”两方的相互信息，以实现植物与环境并发过程 的模拟研究。他们给出了典型的应用实例之一是植物根系的发展过程模拟，其 两一匕i 业大学 i ! ! t 。论文_ ；f ；一章绪论 巾除了给定根系模型之外，还给出了土壤中水含量的模型。该研究从原理r 表 现了植物生长与局部环境的动态耦合过程，即根系的吸水效应改变了周围韵土 壤水分含量，而水分含量分布的变化又影响了根系的发展方向。为了模拟植物 的连续生长过程，p r u s i n k i e w i c z 等提出了时变l 系统| 5 l 。为了进步表示植物 的连续变化过程，p r u s i n k i e w i s c 等又提出了微分l 一系统( d i f f c r e n t i a ll s y s t e m ) ”“浚系统能较好的模拟植物的叶序、花朵、以及模拟植物生长竞争、裁减等的 条件下的情况。 除了现在不断改进的l 系统，还有很多植物模拟方法。例如r e e v e s 提出 了一个叫做粒子系统( p a r t i c l es y s t e m ) 的随机模型。后来r e e v e s 等将该方法用 于模拟森林、草地等复杂系统。该方法不适合表现个体植物的形态结构，但对 大片的植物可以进行有效的模拟。 v i e n n o t 提出的分枝矩阵模型( r a m i f i c a t i o nm a t r i x ) 模拟了植物的结构。 用矩阵来描述植物分枝节点的个数和彼此之间的关系，加上自定义的几个结构 参数，并通过迭代产生植物的分形结构。 b l o o m e n t h a 定义了一些如枝条的弯曲参数，树皮纹理的生成等可绘制真实 感较强植物图形的参数。在绘制较粗的树木枝干时，为了形象逼真，通常把真 实植物的一段枝干的纹理处理成数字图片，通过纹理映射的方法，绘制成树皮 纹理。 w e b e r 提出了基于几何可观察性的三维植物构造模型。该模型定义了许多 参数，例如枝条的前半段和后半段分别定义以不同的偏转角度向下和向上偏转， 这样基本能模拟一般的或s 型枝条弯曲形状。对每一段加入随机偏转量来模拟 枝条弯曲的随机性。w e b e r 利用这些参数，快速生成了较复杂的树木，而不需 要太多的植物学及数学知识，就构造出了与样本十分类似的几何模型。同时， 该模型还给出了多分辨率尺度下模拟的简化方法，使得大片森林背景基本上可 以实时绘制。 a o n o 和h o n d a 模型的基础上提出了构造植物形态的a 系统，浚模型针对 早期l 系统不能生成复杂三维枝条结构的缺点，根据植物诸如单轴分枝结构、 合轴分枝结构等的一些特征，设定分枝角度按照一定的统计规律随机变化，并 西北1 业犬宰岫t ：论义弟一革斩融 由自创的吸引子( a t t r a c t o r ) 算法，模拟光照、重力以及风等对植物形态的影响， 形象地模拟了多种植物。 o p p e n h e i m e r 通过定义各级枝条地偏转角度、锥度、旋转状扭曲以及干与母 干之间地尺寸比例等，和对植物形态地一些描述，再引入一些随机变量构造树 木模型。 b a r n s l e y 与d e m k o 通过若干仿射变换，应用迭代函数系统( i f s ) 生成了自 相似性极强的蕨类植物叶片。之后b a r n s l e y 等发展了再现迭代函数系统 ( r e c u r r e n ti f s ) ，在自相似性生成方面更为灵活地体现植物体局部之间的不同 自相似性。p r u s i n k i e w i c z 和h a m m e l 通过加入变换顺序的约束条件，综合各类 不同的i f s 方法发展了一种称为语言约束式迭代函数系统( l a n g u a g e r e s t r i c t e d i f s ) 的方法。它是种分形绘制的典型方法，将整体形态变换到局部，较好的 模拟了迭代性较强的各类植物。 g r e e n e 提出了体元素空间方法，即将三维空间区域分割成相同的立方体单 元一体元素( v o x e l ) ，将空间中植物和周围环境都用体元素近似表示。这样仅根 据标记的立方体编号，检测植物和周围环境是否占用了相同的立方体，实现了 植物与障碍物之阳j 的碰撞检测，模拟了蔓生植物的生长。其选择的立方体单元 越小，则精度越高，计算速度越慢：反之亦然。 d er e f r y e 等提出了基于有限自动机( f i n i t ea u t o m a t i o n ) 的植物形态发生建 模方法，也称为“参考轴技术”( r e f e r e n c ea x i st e c h n i q u e ) 。该模型用随机过程 的马尔可大链理论以及“状态转换图( s t a t et r a n s i t i o ng r a p h ) ”方式描述植物发 育、生长、休眠、死亡等过程，是第一个适合模拟植物生长过程的模型。但该 模型存在不易理解和使用的缺点。g o d i n 等在此基础上提出了多尺度意义下的植 物拓扑结构( m t g ) ，能够以不同时问尺度描述植物的拓扑结构。赵星等从植 物学的角度出发，提出了微状态和宏状态的双尺度概念，建立了虚拟植物生长 的双尺度自动机模型。该模型考虑了植物的生长机理，参数物理意义明确，并 且应用了符合植物顶芽和腋芽发育过程的概率模型，更适合模拟真实植物的生 长过程。 随着各种植物建模理论的成熟，计算机硬件的飞速发展和数据采集能力的 ! ! ! ! ! 些查兰型! ! ：堡兰兰二! 笪丝 提高，许多国家涌现出优秀的建模软件。 美困o n x y 公司利用所丌发的t r e ec l a s s i c 软件以及t r e e p r o f e s s i o n a l 软件生成了具有二百多种常见植物的三维植物图形库。 j s d a 研究机构基于棉花生理生态的建模方法开发了棉花生长过程管理专家系统 ( c o t t o n p l u s ) 。 澳大利亚的研究机构c e n t r ef o rp l a n ta r c h i t e c t u r ei n f o r m a t i c s 基于l 一系统建 模方法丌发了v i s u a lp l a n t s 软件，能模拟棉花、大豆、玉米等农作物根系的生 长和病虫害对植物生长的影响。 德国k u r t z f e r n h o u t 公司基于图形学的方法开发的p l a n t s t u d i o 软件。日本 岩手大学开发的v i s u a lg a r d e n i n g ，d i g i t a ll a n d s c a p e s 能对植物生长特性，如自 我修建、光照对植物的影响，植物根系的生长，大面积景观等进行较好的模拟。 加拿大c a l g a r y 大学基于l 一系统建模方法和应用少量植物学知识开发的c p e g ， l s t u d i o ，v i r t u a ll a b o r a t o r y 能再现灭绝的树种，并能应用与计算机辅助景观设 计和植物学教学。 法国c i r a d 开发的a m a p 系列软件在植物生长机理模型与可视化模型结 合方面取得了卓有成效的进展，该软件包括了若干个子系统软件，以完成不同 的应用功能。并对数据库中的数据进行提炼，以图表的方式显示出来，用来与 描述植物发芽功能的概率模型产生的植物生长参数曲线进行比较，验证和调整 模型参数。并用多尺度树图方法根据植物体的不同尺度来定义和描述被测量植 物体的拓扑结构和几何结构，最终建立基于实际测量数据的植物生长模型。 a m a p 合并了离散的单个体和它们之间的结合、更新过程以及离散马尔可 夫过程，依靠一系列标准的形式来对植物实体问的拓扑结构，几何结构以及树 的尺寸结构进行描述和编码。用了多角度树图像的形式对树进行了模拟。通过 选择和视觉化不同类型的数据，如每个生长周期的节间平均数量，进一步描述 了不同类型的环境因素数据对生长和分枝过程的影响。 1 3 植物模拟与仿真的意义 植物生长模拟涉及到众多领域，包括植物生理学、作物栽培学、农业气象 学和微气象学、土壤学、微生物学、计算机科学等众多学科，该领域吸引了许 s 曲北1 - 业 学坝t 。论文第帚绪论 多计算机科学家、植物学家以及数学家等，他们提出了许多模拟植物的方法和 模型，并开发了许多植物模拟软件。现今，对于虚拟植物生跃主要有两个研究 方向。第一是单纯的植物外观形态模拟，注重形态的逼真性。其目的为自然景 观的再现，主要用于教育、娱乐、商业、园林规划等领域。第二是真实植物生 长过程的模拟，注重植物学理论的真实性。其目的在于植物生长过程的研究， 可用于农田试验、作物病虫害研究、资源环境分析、作物栽培指导、及作物生 长机理的研究等。 在人工智能研究中，自适应和白寻优是一个十分重要的问题，植物的生长 过程对它所处的环境，表现出良好的自适应和自寻优能力，这是一种自然智能。 对植物生长发育过程模拟的机理，反过来对人工智能的研究有重要的指导意义。 1 4 论文结构安排 下面将本文完成的各章节内容安排介绍如下： 第一章绪论，主要介绍论文的研究背景、研究现状及研究意义。 第二章主要介绍分形、l 系统的一些基本理论和概念。 第三章结合前人对l 一系统的符号扩展，介绍了l 系统的一些应用研究， 同时列出作者编写的演示系统所生成的一些图例。 第四章主要介绍演示系统的一些关键技术。 第五章结束语，总结全文，说明了本文所作的主要贡献并指出本文的不足 及有待进一步研究的工作，并对以后的工作及前景做了进一步展望。 6 第一章分彤i ol 一系统牲奉理论 第二章分形与l 一系统基本理论 2 1 分形的引入 小规则的几何形状在我们剧团处处可见，诸如花草、山脉、烟云、火焰等 等举日皆是，大自然在向我们展示其美丽多姿的同时，也向我们提出r 严峻的 挑战：怎样描述这种不规则的自然现象呢? 从5 0 年代起，b m a n d e l b r o t 孤身人，整h 思索着一种新的几何学。他试 图通过这种几何学统一一描述自然界、人类社会中普遍存在的各种不规则现象， 如流体湍动、曲折的海岸线、多变的天气、动荡的股市、经济收入分配关系、 棉花的价格波动等等。严格况，那时候他自己也刁i 明确自己在找什么，甚至不 知道要找的是一种新的几何学。 引用分形这一学科当之无愧的领袖人物m a n d e l b r o t 的话来说： “为什么几何学常常被说成是冷酷无情和枯燥乏味的? 原因之一在 于它无力描写云彩、山岭、海岸线或树木的形状。云彩不是球体，山岭不足锥 体，海岸线不是圆周，树皮并不光滑，i i j 电更不是沿着直线传播的。 更为般地，我要指出，自然界的许多图样是如此地不舰则和支离破碎， 以致与欧几墼得( 几何1 本书中用这个术语柬称呼所有标准的几何学相 比，自然界不只具有较高程度的复杂性，而且j | j 有完全不同层次上的复杂度。 自然界型样的长度，在不同标度下的数目，在所有实际情况下都是无限的。 这些图样的存在，激励着我们去探索那些被欧几里得搁置在一边，被认为 足“无形状可言的”形状，去研究无定形的形态学。然而数学家蔑视这种挑 战，他们想出种种与我们看得见或感觉到的任何东西都无关的理论，却回避从 人自然提出的问题。 作为对这个挑战的回答，我构思和发展了大自然的一种新的几何学，并在 许多4 ：同领域中找到了用途。它描述了我们周围的许多不规则和支离破碎的形 状，并通过鉴别出一族我称为分彤的彤状，创立了相当成熟的理论”i “。 分形不但抓住了浑沌与噪声的实质，而且抓住了范围更广的一系列自然形 式的本质，这些形式的几何在过去相当长的时间里是没办法描述的，或者被商 贵的科学认为是不屑于研究的，它们包括：海岸线、树枝、l u 脉、星系分粕、 西朵、聚合物、天气模式、大脑皮层褶皱、肺部支气管分支以及血液微循环管 道等等。 分形在自然界中太普遍了，用分形语言去描绘大自然丰富多彩的面貌，应 当是最方便、最适宜的。正因如此，人们说“分形是大自然的几何学”悼i ，“分 ! ! ! ! ! 、! ! 苎兰塑! ：堕兰 形处处可见” 第一幸分彤i oi 系统堆奉耻论 2 2 什么是分形? 到底什么是分形呢? 丌始时，m a n d e l b r o t 把那些i t a u s d o r l l 维数刁：是整数的 集合称为分彤。按这个定义，某些看来应该是分形成员的，例如著名的p e a n o 曲线，就被排除在外，于是m a n d e l b r o t 又修改了原束的定义，洗分形是那些局 ( f l l l l 整体按某种方式相似的集合，这是目前关于分形定义普遍被接受的蜕法。 研究分形，似乎如同研究生命一样，先弄清楚定义再研究，还足在研究、发展 之中给出科学的定义，看来还是后者更有道理1 。 到曰前为止，分形尚无最后的定义。k f a l c o n e r 认为i l ，划分形的定义，可 以用生物学中对“生命”定义的办法。“生命”是很难定义的，但却町以给出一 系列生命对象的特征，例如繁殖能力，运动能力。除了有些对象例外，大部分 情形都能因此而得到分类，于是就不会因为暂时没有严格的定义而停步不| j 。 对分形似乎也宜于给出一系列特征性质，当集合具备这些性质时就可以认为是 分形：当因此而排除掉一些自己的同类时，再作特殊的研究。按这种观点，称 集合f 是分形，是指它具有下面典型的性质： f 具有精细的结构，也就是蜕，在任意小的尺度f ，它总是有复杂的细 节： ( 2 ) f 是不规整的，它的整体与局部都不能用传统的几何语音来描述； ( 3 ) f 通常有自相似形式，这种自相似可以是近似的或统计意义下的； ( 4 ) 一般地，f 的某种定义之下的分形维数大于它的拓扑维数： ( 5 ) 在大多数令人感兴趣的情形下，f 以非常的方法确定，可能由迭代过程 产生。 综观上述f a l c o n e r 的说明，不难发现其中有较大的灵活性，比如( | ) 中的“精 细”，“细节”作何解释? ( 2 ) 中“不能”的说法怎样操作? 因为“不能”需沧证， 而没有作到的事不可以说是不能做到的；“几何语言”指的是什么? ( 3 ) 白相似怎 样理解? 以及“大多数令人感兴趣的情形”，更是没有确切的标准。 分形是自然形念的几何抽象，如同自然界找不到数学上所说的直线和圆周 样，自然界也不存在“真正的分形”。只要注意到分形包含一个无穷小尺度的 内涵，便可以知道自然形态只是停留在一定层次内可以合理地按分形模型来考 虑。从背景意义上看，说分形是大自然的几何学是恰当的| 2 l 。 2 3 研究分形的一般方法 利用分形方法模拟植物形态结构的方法主要有i 。- 系统法、迭代函数系统 ( i f s ) 法、受限扩散凝聚( d i a ) 法、粒子系统法等。 r 第一章分彤loi ，系统坫奉理论 l ，迭代函数系统法 i f s ( i t e r a t e df u n c t i o n s y s t e m ) 法是分形绘制的典型方法。它是 h u t c h i n s o n ( 1 9 8 1 1 和b a r n s l e y ( 1 9 8 5 ) 提出并发展起来的一种研究分形的数学方 法，i f s 的基本思想并不复杂，它认定几何对象的全貌与局部，在仿射变换的意 义下，具有白相似结构。这样一柬，几何对象的整体被定义以后，选定若一f | 仿 身寸变换，将整体形态变换到局部，并且这一过程可以迭代地进行下去，直到满 意的造型。其理论依据及应用效果是基f 著名的压缩映射不变集定理和拼帖定 理。1 f sl 。，以定义为由一组满足一定条件的映射函数w 。( 例如压缩的仿射变换) 及一组变换发! 忙的概率p 组成：i f s = ( w 。，p i ) l i = l 2 ，n l ，利用i f s 生成植物图 像的方法是对初始植物图像按照已知概率选择函数而实施的。一种迭代变换。迭 代函数系统用很少的数据就能完成图像的模拟。在图像压缩方面显示了很大优 势，也是一个很诱人的研究领域。i f s 主要用于分形绘制和图像压缩。这方面的 研究主要集中在利用i f s 码进行图像绘制和求已知图像的i f s 码，以及图像压 缩方面。 2 、受限扩散凝聚法 受限扩散凝聚( d l a ) 法是美国科学家w i a e n 和s a n d e r 于1 9 8 1 年提出的， 其基本方法是：在一个平面网格上选定一个静止的微粒作为种予，然后在距种 r 较远的格点上产生一个微粒，令微粒沿网格上下左右的方向随机行走。如果 该微粒在行走过程中与种子相碰，就凝聚在种子上；如果微粒走到边界上，就 被边界吸收而消失。如此重复上述步骤，就会以种子为中心形成个不断增长 的凝聚集团，利j j ；| d l a 或其修改的模型可以对部分植物的形态结构进行计算机 模拟，如植物根系的生长过程模拟和海藻类植物的形态结构模拟等。d l a 模型 ：e 要用f 模拟各种分形生长和凝聚现象。 3 、粒子系统法 粒子系统法的基本思想是用大量的、具有一定生命的粒予图元来描述自然 界不j ；! i l 则的模糊景物。每个粒子在任一时刻都具有随机的形状、大小、颜色、 透明度、运动方向和运动速度等属性，并随时删推移发生位置、形态的变化。 每个粒子的属性及动力学性质均由一组预先定义的随机过程来说明。粒子存系 统内都要经过“产生”、“活动”和“死亡”这三个具有随机性的阶段，在某一 时刻所有存活粒子的集合就构成了粒子系统的模型。粒子系统适合用束模拟山、 水、树丛、草地等模糊、随机图像。 4 、i 系统法 1 9 6 8 年，美国植物学家a r e s t i dl i n d e n m a y e r 提出了著名的l 系统法，成为 植物生长建模的主要方法之一。l 系统是一种字符串重写系统，通过对植物对 i 竺! ! ! ! 查兰塑! 堡兰塑二要! ! ! 堕。! ! 二墨竺竺尘竺堕 象尘跃过程的经验式概括和抽蒙，构造公理与产生式集，生成字符发展序列， 表现植物的拓扑结构。它以形式化的语言描述植物的结构利生长，在语毒的终 结符与植物结构对应时，由文法生成的句子代表植物，衙句子生成的。 ，n “过程 足植物生长发育的过程。最简单的l 一系统简称为d o ，一系统，d 表示确定性，0 表示与上f 文无关。随机l 一系统克服了确定性l 一系统只能生成规则分形图形的 局限，町构造随机的植物拓扑结构。参数化l ，系统使l 一系统能够模拟时延信息。 1 9 8 4 年，s m i t h 等人将l 一系统引入到植物模拟的分枝拓扑研究中，并称之为文 担二， ：j 图g m f t a l ) 方法。 l 系统法的特点：它能简洁地描述植物的拓扑结构，例如枝条和l 花序结构。 具宵定义简单、结构化程度高、易于实现等特点。 综上所述，可以看出：虽然浣i f s 法、d l a 法、粒子系统法和l - 系统法都 能j _ ；j 柬模拟植物的形态结构，但是它们各有所长，利用i f s 法能生成各种植物， 又能模拟各种山、水、云等，但合适的i f s 码的选择是一个令人非常头疼的问 题，i f s 在图像压缩方面具有很大的优势和广阔的前景。d l a 法最适合模拟各 种凝聚现象。粒子系统法在模拟森林、草地等方面具有其无可比拟的优点。而 l ，系统法无疑是描述植物拓扑结构的一种简洁、有效的方法。 2 4l 系统的基本概念 二4 ，l 简单l 一系统 最简单的l 系统足d o l 系统，它是干十形式语言系统，我们先看实例。 考虑由两个字母a 和b 组成的字符串，称为单词，a , b 可在同一单词中出现 多次，每个字母与一个改写规则对应。例如规则1 ：“a - - ) a b ”表示用a b 替换a ； 规则2 ：“b - - ) a ”表示用a 替换b 。规定改写过程从一个称作公理的单词开始，一 步步运用规则进行迭代。如从公理“b ”开始的改写过程是：第步运用规则b - ) a 得到单词a ，第二步运用规则a - - ) a b 得到单词a b ，第三步将a b 中的a 和b 分别 进行替换，得到单词a b a ；以此类推，得到如下过程： 遮岱逸数词周埋里结墨 刀：始公理 b 第一步 第二步 第三步 第四步 第五步 第六步 b a a a b ： a 专a b t a - ) a b ： a - a b ： a - - ) a b ； b 专a b 争a b a b - - ) a b 专a l 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 阴北t 。业人学埘咤义 第一章分彤jl ，一系统书本挫论 这就是一个实际的d o l 一系统。 下丽给出o l 一系统和d o l 。系统的形式定义： 令v 表示一个字符集，v + 表示v 上所有单词( 由符号或字符组成的字符 串) 的集合，一个0 l 一系统可以用一个有序的三元组l = 来表示，其中f 0 是( ( j 】v 。) 个非空单词，称作公理，p 是产生式规则的有限集合，产生式记 作c - ) s ，字符c 和单词s 分别叫做产生式的前驱和后继。如果对给定的前驱c v 尤明确解释的产生式，则规定c c ( 其中c - c p ) 。 在o l 。一系统中，对于每个字母c v 当且仅当有一个非空单词s ，使得c - - ) s 则o l 。一系统是确定的，记作d o l 一系统l “。 系统的迭代过程是：首先从公理开始，把中的字符作为第0 次迭代的 结果字符；调用p 中的相应规则，改写第i 次迭代的结果字符，得到第卜1 次迭 代的结果字符( i = 0 ，l ，2 3 ) ；迭代过程可以在有限次内进行。 2 ，4 2 l 一系统的平面几何解释 i 一系统是一个形式语法系统，它可以有各种的语义解释。下面介绍一种平 面几何解释，叫龟行解释法。 设想一只乌龟在乎面上爬行，其状态用三个值描述，记作i x ，y ) ，其中x ，y 为乌龟所在位置的直角坐标，1 3 表示乌龟头的朝向。再给定乌龟爬行的步长d 及扭转方向的角度增量6 ，几种符号的图形解释( 如图2 1 所示) 为： i ? ：向前移动一步，步长为d 。乌龟到达状态( x ，y ) ，其中 x 。x + d c o s y y + s i n 俚， 图形解释是从( x ，y ) n ( x ，y ) 丽一直线段； + ：向赶转6 角，乌龟f 一状态为( x y ，旺+ 6 ) ，规定正向角是逆时针方向； 一：向右转6 角，乌龟下一状态为( x y ，6 ) ，规定负向角是顺时针方向。 其中d 、“和6 是可以改变的参数。 f t + ? 厂一、一、 图2 1 几种符号的幽形解释 利用l 系统，可以生成典型的分形图彤。下面的例子是著名的v o i ik o c h 丛：些! ! ! 生兰! ! ! ! ! ! ：堕兰笙二曼坌堂。! ! 二墨竺苎些堕 l 线，卜成过程。 例2 17 匕成y o nk o c h 曲线的d o i ，。系统： 公理：f f f f ( ! 1 ， 规则集p ：f 专f + f f f f + f + f f 其中规定： 1 ) 丌始点在图形的庄下方，前进方向向上，步长为1 个坼位； 2 ) “f ”表示沿前进方向走一步，“一”表示向右转9 0 。，“十”表示向左转 9 0 。： 3 ) 在迭代过程中每深入一层，步长缩d 、到上层的】4 。 幽2 2 是本d o l ，系统迭代过程的平面几何解释，其中： 图( a ) 是由公理f f f f 描述的初始状态： 图( b ) 是由规则f f + f f f f + f + i ? 一f 描述的生成元； 图( c l 是第一次迭代的结果； 图 d ) 是第二次迭代的结果； 图( e ) 是第三次迭代的结果。 ( a ) 初始状态( b ) 生成元 ( d ) n = 2( e ) n = 3 幽22 生成f o i lk o c h 曲线的d o l - 系统 ! ! i 塑些叁兰型! ：堡苎塑= 至坌丝l ! ! 二墨堑堡查些堡 2 4 ，3 随机o l 一系统 利h j 确定的d o l 系统生成的植物图像显得很死板，为，避免这种情况，又 j ；f 入r 随机o l 一系统。随机性可用在字符解释上( 例如 中步长d - j 以足随机的) ， 也可用在产生式上。前者保持基本拓扑结构1 i 变，后者基本拓扑结构发生变化， 儿何性质也发生变化，因而生成更为“活泼”的结构。 一个随机o i 一系统是一个有序的四元组： g n = v 0 ) p 5 d( 22 ) 其q - , # 符集v 公理和产生式集p 与d o l 一系统相同，函数n ：p 号 0 ，li 用 来确定缚个产生式p 被应用的概率。殴旺为v 中任意字符，以d 为前驰的产生 式可以有多个，但这些产生式的概率之和应该为l 。随机0 f 。一系统的产生式记作： p r e d - ) ( p r o b ) s l i c e ( 2 3 ) 其中p l c d ，和s u c 2 c 分别称为前驱和后继，p r o b 为本产生式被应用的概率。 这样，在随机o l 一系统中，对于同样的产生式模块，经过相同的迭代次数可 以生成不同的植物结构。 例2 2 一个随机0 l 一系统实例： 0 ) ：a b a p l ：a f 0 4 ) a p 2 ：a - ) ( 0 6 ) b p 3 ：b - - ) b a( 2 4 ) 产生式p l , p 2 表示可用a 或b 代替a ，每次迭代的时候将根据被应用的概 率随机决定是应用产生式p - 或是p 2 。在产生式p 3 中没有明确指定应用概率，系 统默认为1 。 例如在 a b a - ) a b a bf 2 5 ) 中，p i 彼应用到第一个字符a 的改写，p 2 被用到第二个字符a 的改写。 2 4 4 轴向树及括号的引入 树木在宏观形态结构上都是出主干、分枝和树叶构成的分层结构，山主干 分生第一层分枝，再由第一层分枝分生第二层分枝，如此一层一层分生下去直 至树叶，树木在生长发展过程中其形态就是这样不断地在前一层基础上复制与 其相似的组织结构，呈现出一定的自相似的分形特征i ”1 。为了便于研究这种植 物结构，表示较复杂的分又，我们引用了轴向树的概念。 设想要描述一棵树，它有根，主干，旁支等。 在l 系统中引入下面的说法： 根：特殊的节点，树的出发点，没有的驱的枝条； 1 1 明北】业_ ：学坝 。论殳 第一币分形。- i 。一系统毕奉理论 节点：树木的各枝条闽躲连接点； 主轴：带有分枝的枝条； 顶端：树的顶端即终止节点，它是不带后继的分枝。 节问：两个节点之f h j 的分枝。 路径：从根出发直到顶端，形成路径。在路径中的节点至少有一个后继分枝 分枝序列：从根至顶端有主轴和分枝，形成分枝序列。 主轴与分枝将分成0 级、l 级、2 级。 f 级主轴为上一级主轴的分枝。 这种表示称为轴向树，图2 3 是个轴向树的实例。 幽2 3 轴向树实例 。终止节点 分支节点 - - - 连顶端 连内节点 一个轴连同它的后代一起形成树枝，一个树枝本身也是一棵轴向树。轴和 分枝是宵序的。树的最底部的轴的序号记为0 。一个从序号为r l 的母亲轴上发出 来的侧枝的序号汜为n + l 。树枝的序号等于它的最下面一层的轴的序号。轴的 终端节点叫做分枝顶部。 为了表示轴向树，l i n d e n m a y e r 引入了括号字符，一棵带有边标号的轴向 树由建立在字符集v e = v um l li 二的单词表示： 【l j = x l 【a 1 x 2 a 2 x 。【a j j x ”i ( 2 6 ) 其中子单词x i , x 2 ，x n _ 1 v ，不包含括号，并且子单词a h a 2 a ，v b 它们是自 嵌套的。x l 。2 x n x ，i 表示主轴，a l a 2 a 。表示u 的第一级分枝。丽每一个分枝 a 又能分解成类似于u 的形式，产生一级分枝或二级分枝。这种分解过程可以 递归进行。 4 雏_ 二章分形。oi 系统犟年删葩 蹦2 4 个树结构的实铡 分枝 图2 4 是一个树结构的实例，代表它的字符串为： c o = a b c d l e f f g h i j k i m ( 2 7 ) 子 社间a b c ：j i m 是u 的主轴，x l = a b ，x 2 = e ：l ；x 3 气是节问，x 4 = l m 是顶点。子单 词a l = c d ，a 2 = g h l i 和a 3