（应用数学专业论文）分形图形的代数语言系统研究.pdf

f r a c t a lg r a p h i ca l g e b r al a n g u a g es y s t e mr e s e a r c h b y l i us h u o b e ( l a n g f a n gn o r m a lu n i v e r s i t y ) 2 0 0 7 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e a p p l i c a t i o nm a t h e m a t i c s i nt h e g r a d u a t esc h o o l o f l a n z h o uu n i v e r s i t yo ft e c h n o l o g y s u p e r v i s o r a s s o c i a t ep r o f e s s o rl i us h u q u n m a y , 2 0 11 兰州理工大学学位论文原创性声明禾 原创性声明 本人郑重声明：所呈交的论文是本人在导师 取得的研究成果。除了文中特别加以标注引用的 何其他个人或集体已经发表或撰写的成果作品。 献的个人和集体，均已在文中以明确方式标明。 法律后果由本人承担。 作者签名： 季4 丽 日期：砂年 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文 收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名： 导师签名： 日期：例y 年月局日 b 强伊，f 否具5b 1 4 当前存在的问题8 1 5 课题研究意义9 1 6 本课题主要研究内容9 第2 章迭代函数系统和l 系统1 1 2 1 迭代函数系统1 1 2 2l 系统1 2 第3 章代数语言2 1 3 1 基本概念2 1 3 2 语言2 3 3 3 正则表达式2 4 3 4 文法2 5 3 4 1 上下文无关语言的常见结构和正则表达式方程的解2 5 3 4 2 左线性或右线性相关文法2 5 3 4 3 左右线性相关文法2 6 3 4 4 正则表达式文法2 6 第4 章分形图形的代数语言系统2 7 4 1 代数语言系统的定义2 7 4 2 代数语言系统的语法形式2 7 4 2 1 变量2 7 4 2 2 字母表2 7 4 2 3 公理2 9 2 未来研究工作展望3 9 参考文献4 0 致谢4 4 附录a 攻读学位期间所发表的学术论文4 5 硕+ 学位论文 摘要 目前，作为计算机图形学的一个重要内容的分形图形学引起了科学界的广泛 关注。i f s 和l 系统是分形造型的两个经典生成系统，它们的发展对分形学的研 究有着重要的意义。然而它们也存在着一些缺点，比如迭代函数系统的i f s 码难 找、l 系统字符串描述复杂等。本文的代数语言系统正是为解决这些问题而提出 的。 本文首先介绍了分形的发展历史、形式语言相关理论、分形的基本理论及分 形图形生成的典型方法，如l 系统、迭代函数系统i f s 等。根据形式语言的理 论研究了代数语言系统的基本概念、运算性质、文法结构、正则表达式等。为了 更高效地表示分形图形，依据代数语言系统的文法结构及正则表达式的文法规 则，提出了分形图形的代数语言系统。该系统使得代数语言系统和分形建立了联 系，为了能更便捷的实现一些分形图形，设定了一些带参数的常量、变量、数学 函数、几何图形的自定义符、迭代次数、公理和规则。该系统可以将l 系统和 i f s 进行统一代数描述，也可以将d o l 系统、迭代函数系统( i f s ) 、带凝聚集迭 代函数系统( 凝聚i f s ) 、随机迭代函数系统( i f s p ) 和再归迭代函数系统( r i f s ) 等进 行描述。用户可以根据预定义，系统会自动生成想要的分形图形。该系统还给出 正则表达式方程解的形式将分形吸引子进行代数表示，并给出一些实例。实例表 明，分形图形可以用该代数语言系统简单、明了、高效地表示。 代数语言系统的研究为分形造型的理论描述提供了新的方法，其形式化的描 述大大减小了分形图形描述上的困难，增强了表达分形的能力。该系统将l 系 统和i f s 统一表示，这样可以更大限度的利用两个系统的优点。此外，通过代数 语言系统代数运算，可以生成更加复杂的分形图形。 关键词：分形；l 系统；迭代函数系统；代数语言；正则表达式 分形图形的代数语言系统研究 a b s t r a c t d u r i n gt h ep a s td e c a d e s ，f r a c t a lg r a p h i c sh a v er e c e i v e dt r e m e n d o u sa t t e n t i o n d u et ot h e i rp o t e n t i a la p p l i c a t i o ni nc o m p u t e rg r a p h i c s ls y s t e ma n di t e r a t i v e f u n c t i o ns y s t e m ( i fs ) a r ec l a s s i c a li nf r a c t a ls h a p eg e n e r a t i o ns y s t e m ，t h e d e v e l o p m e n to ft h e i rr e s e a r c hi nt h ef i e l do ff r a c t a ls c i e n c e h a v eag r e a ts i g n i f i c a n c e h o w e v e r ，t h e ya r eg e n e r a t e di nt h ep r o c e s so ft h e i ro w ns h o r t c o m i n g s ，s u c ha si f s c o d ei sd i f f i c u l tt of i n d ，t h es t r i n g so fls y s t e mi sd i f f i c u l tt od e s c r i b e i no r d e rt o s o l v et h e s ed i s a d v a n t a g e s ，t h i sp a p e rp r o p o s e sa l g e b r a i cl a n g u a g e ( a l ) s y s t e m t h i sp a p e rf i r s ti n t r o d u c e st h eh i s t o r i c a ld e v e l o p m e n to ft h ef r a c t a l ，t h et h e o r y o ff o r m a ll a n g u a g e s ，t h eb a s i ct h e o r i e so ff r a c t a la n dt y p i c a lm e t h o d so fg e n e r a t i n g f r a c t a l g r a p h i c s ，s u c h a st h els y s t e m ，i t e r a t i v ef u n c t i o ns y s t e ma n ds o o n a c c o r d i n gt ot h et h e o r yo ff o r m a ll a n g u a g e ，w es t u d yt h eb a s i cc o n c e p t s ，o p e r a t i o n a l p r o p e r t i e s ，g r a m m a t i c a ls t r u c t u r e ，r e g u l a re x p r e s s i o n so fa ls y s t e m i n o r d e rt o r e p r e s e n tf r a c t a lg r a p h i c sm o r ee f f i c i e n t l y ，b a s e do ng r a m m a r s t r u c t u r eo fa ls y s t e m a n dg r a m m a rr u l e so fr e g u l a re x p r e s s i o n s ，w ep r o p o s ea ls y s t e mo f f r a c t a lg r a p h i c s t h i ss y s t e me s t a b l i s h e dc o n t a c t sb e t w e e nt h ea ls y s t e ma n df r a c t a l ，s e ts o m e p a r a m e t e r so ft h ec o n s t a n t s ，v a r i a b l e s ，m a t h e m a t i c a lf u n c t i o n s ，g e o m e t r yo ft h e c u s t o mc h a r a c t e r , t h en u m b e ro fi t e r a t i o n s ，a x i o m sa n dr u l e s ls y s t e ma n dt h ei f s a r ed e s c r i b e db yu s i n gau n i f o r mm e t h o do fa l ，t h i sa ls y s t e mm a i n l yd e s c r i b et h e d o ls y s t e m s ，i f s ，i t e r a t i v ef u n c t i o ns y s t e m sw i t hc o n d e n s e ds e t ，s t o c h a s t i c i t e r a t i v ef u n c t i o ns y s t e m ( i f s p ) ，a n d r e c u r r e n ti t e r a t i v ef u n c t i o ns y s t e m ( r i f s ) ， m e a n w h i l et h ef r a c t a la t t r a c t o ri se x p r e s s e db yt h er e g u l a re x p r e s s i o ne q u a t i o n s o l u t i o no ft h i ss y s t e m ，a n df i v e ss o m ee x a m p l e s t h ee x p e r i m e n tr e s u l t si n d i c a t e t h a tt h ef r a c t a lg r a p hc o u l db es i m p l y ，c l e a r l ya n de f f i c i e n t l ye x p r e s s e dv i at h i s l a n g u a g ea l g e b r a i cs y s t e m a l g e b r a i cl a n g u a g es y s t e mp r o v i d e s an e wm e t h o df o rt h et h e o r e t i c a l d e s c r i p t i o no ft h ef r a c t a l i tg r e a t l yr e d u c e st h ed i f f i c u l t i e so f t h ef o r m a ld e s c r i p t i o n a n de n h a n c e st h ea b i l i t yo ft h ef r a c t a le x p r e s s i o n t h es y s t e mc a nb em o r el i m i t s u s i n gls y s t e ma n di f sa d v a n t a g e s ，a l s ob e u s e da l g e b r a i cl a n g u a g ea l g e b r a i c o p e r a t i o n s ，w h i c hc a ng e n e r a t em o r ec o m p l e xf r a c t a l s k e yw o r d s ：f r a c t a l ；ls y s t e m ；i t e r a t i v ef u n c t i o ns y s t e m ；a l g e b r a i cl a n g u a g e ；r e g u l a r e x p r e s s i o n 硕十学位论文 插图索引 图2 1 厥叶1 2 图2 2 迭代五次后的k o c h 曲线1 4 图2 3 一个含中括号的d o l 系统图例1 5 图2 4 左相关d 1 l 系统生成的植物分形1 5 图2 5 右相关d l l 系统生成的植物分形1 6 图2 62 l 系统生成的植物分形1 7 图2 7 随机l 系统产生的植物分形1 7 图2 8 三维海龟前进方向和旋转1 8 图2 9 三维l 系统生成的植物分形1 9 分形图形的代数语言系统研究 附表索引 表2 1 生成厥叶的i f s 码l l 表4 2 常用函数表2 7 表4 3 几何图形的关键字2 9 表4 4 代数语言系统的分类3 2 硕士学位论文 1 1 课题的研究背景 第1 章绪论 自从两千多年前希腊人e u c l i d ( 欧几里得) 创立了几何学以来，人们对某个数 学集合，总是习惯于在e u c l i d 空间( r ”，e u c f i d e a n ) 对其研究和对其度量，然而 e u c l i d 几何学不是万能的，自然界中的许多现象比如连绵的山川、漂浮的云朵、 树冠、岩石等等，它们都不是e u c l i d 几何意义下的光滑、规则形体。因此就产 生一种新的能够更好地描述自然图形的几何学，就是分形几何。 美籍法国数学家b e n o i tb m a n d e l b r o t 提出了“分形”一词( f r a c t a l ) 1 1 。f r a c t a l 这个词是m a n d e l b r o t 创造的，来源于拉丁文f r a c t u s ，其原意是“不规则的、分 形维的、支离破碎的物体 。分形的出现解决了一些所谓的“数学怪物 的东西 及人们无法用e u c l i d 几何语言描述的现象。对于几何学来说，这是一个新突破， 它引起了数学家和自然科学者的极大关注，引领他们不断去创新。分形有很 高程度的应用普遍性，给自然科学、工程技术等学科提供了科学方法和思考 方式。就如大家所知，现实世界中存在着许多具有标度不变性的分形结构。 这里的结构包含的意义非常广泛，不仅包含研究对象的空间几何形态，而且 还包含那些几何维数小于其测量维数的点集。典型的“数学怪物有c a n t o r 集、y o nk o c h 曲线和s i e r p i n s k i 三角形，它们的共同特点是整体与局部具有相似 性。 分形的不断发展，使分形技术越来越多的应用于计算机图形造型技术 中，人们在使用计算机对一些问题进行深入探讨的过程中，越来越发现，自 然界中的大部分事物存在着随机性复杂性等特性，但是在这些随机性和复 杂性背后，还存在着一定地规律性。面对这些复杂难题，分形就可以利用其 新的思维方式来解决这些问题。与欧式几何造型技术不同，不规则物体的造 型技术往往采用的是过程式模拟，即可以用一个简单的模型加上一些简单的 控制参数来表示一类事物，然后通过一步步地递归调用这一模式就可以产生 非常复杂的事物。而对于如此之大的数据量，我们仅仅用分形图形生成算法 来推理，问题会非常复杂。而分形自身具有的整体与局部相似特性，使我们 采用简单模型就能模拟出的景物呈现奇妙的艺术效果。正是因为分形的发 展，计算机图形学也日益壮大，我们才能看到j u l i a 集和c a n t o r 集的精细美 妙结构；看到了自然景物的无限细节；看到具有高度真实感的三维动画。计 算机图形的研究丰富了分形图形的发展，分形的发展带动着造型技术的发 分形图形的代数语青系统研究 展，主要产生的几种方法有l 系统、迭代函数系统( i f s ) 、分形插值、粒子 系统、d l a 系统、随机插值等等【2 】。用户可以根据所选分形造型不同，选 择出适合的模型来描述它。在这些生成方法中，l 系统不需要有很多的理论 背景，就可以比较简单快捷的生成分形图形，那些有简单计算机知识的人就 可以很快的学会这种方法。那么以上方法是否都可以根据l 系统形式化方 法形式进行描述? 我们想到目前在计算机中应用比较广泛的形式语言，采用 形式化逻辑思维，将每个概念与产生式对应，按规则变换，即使推理过程很 复杂，只要按照计算机演绎这些复杂的过程，最后就可以得到想要的结果， 然后把形式语言还原成人们易于理解的正常语言。 1 2 课题的基本理论 1 2 1 分形的基本理论 2 0 世纪7 0 年代，m a n d e l b r o t 为了描述复杂图形和复杂过程引入了分形一词， 它表示的是不规则、支离破碎的物体。他于1 9 7 5 年出版了分形、机遇和维数， 这标志着分形理论的诞生。对于分形的概念一直没有严格的定义。不同学科 领域的学者对分形的理解是不同的，所以很难给出统一的，让所有的科研人 员都能接受的定义。简单地说，分形是描述一类具有一定意义的自相似复杂 图形和结构形态的总称。分形根据事物的形体不同，有两类图形对象：规则 分形和不规则分形： ( 1 ) 规则分形：大多数分形在一定的标度范围内不断放大其任何组成部 分，其规则程度都是一样的，即具有无限的膨胀和收缩对称性，这个性质称 为比例自相似性；按照统计的观点，其任一局部经平移、旋转、缩放变换后 与其它任意部分相似，像这种具有严格自相似的分形称为规则分形。实际观 察到的分形的最小组成部分是有限的，就是说标度的下限应大于实际分形的 最小组成部分。当然，任何有限分形图形的标度的上限应小于等于整个图形 的尺度。 ( 2 ) 不规则分形：自然界许多事物所具有的不规则性和复杂性往往是随机 的，如蜿蜒曲折的海岸线、变换无穷的布朗运动轨迹等，这类曲线的自相似 性是近似的或统计意义上点，这种自相似性只存在于标度不变区域，超出标度不 变区域，自相似性不复存在，这类曲线为不规则分形。 m a n d e l b r o t 先后对分形给出了两个定义，第一个是19 8 2 年提出的，四年后， 他又提出了更为实用、更易于理解的定义。 定义1 1 如果一个集合在欧氏空间中的h a u s d o r f f 维数d 严格大于其拓扑 维数d r ，则称该集合为分形集，简称分形。 2 硕十学位论文 定义1 2 组成部分以某种方式与整体相似的形体叫分形。 以上m a n d e l b r o t 所给出的两个定义还是不够精确和全面。英国数学家 k f a l c o n e r 从分形的特征着手，给出分形所具有的性质特征【3 j ： ( 1 ) f 具有精细的结构，即在任意小的尺度下，总是有复杂的细节。 ( 2 ) f 是不规则的，以至于它的整体和局部都不能用传统的几何语言来描述。 ( 3 ) f 通常具有某种自相似性，可能是近似的或统计的。 ( 4 ) ，在某种意义下的分形维数通常都大于拓扑维数。 ( 5 ) 在多数情况下，f 可以以非常简单的方式定义，或许以递归过程产生。 分形的理论产生、发展与应用经历了三个阶段【4 ，5 】： 第一个阶段，分形理论产生的萌芽阶段( 19 2 5 年以前) 。这期间几种典型 的分形集开始出现。人们力图用传统的几何语言来进行描述、分类或刻画， 但不能实现。当时这些分形集被人们称为病态的，例如k o c h 曲线。19 19 年 h a u s d o r 行引入了分形维数的概念，以此为基础各种分形维数相继引入。这一阶 段是分形理论发展的第一阶段，其实此时人们已经提出了典型的分形对象及其相 关问题并为讨论这些问题提供了最基本的工具。 第二个阶段，分形理论形成与发展阶段( 1 9 2 5 1 9 7 5 年) 。这一阶段分形理论 逐步形成，而且研究范围也扩大到数学的许多分支中。这一时期，维数的乘积理 论、投影理论、位势方法、网测度技巧、随机技巧均先后建立并成熟，这使得分 形几何的研究具有自己的特色与方法。 第三个阶段，分形理论不断完善和广泛应用阶段( 1 9 7 5 年以后) 。1 9 7 5 年， m a n d e l b r o t 开始发表了一系列有关分形的文章，引进了分形概念，产生了“分形 几何学 。从此，结合计算机技术，分形很快成为一门跨学科的、非线性的相当 活跃学科，其理论研究和应用深入到了人类活动的方方面面。 随着计算机飞速、迅猛的发展，人们越来越感觉到，在利用计算机描述 自然界中的大量的具有复杂、不规则、无序、非平衡、精细结构的事物时， 传统的欧式几何已不能有效地解决这些复杂问题。而如今发展起来的分形理 论，给人们以新的思维，它可以通过复杂的不规则形态，找出整体和局部之 间的本质联系，解决了复杂、不规则事物难描述问题。 1 2 2 形式化方法 形式化方法的发展最早可追溯到2 0 世纪5 0 年代后期，其对程序设计语 言编译技术的研究，2 0 世纪6 0 年代后期达到高潮。经过30 多年的研究和 应用，从最简单的形式化方法：一阶谓词演算方法到现在的应用于不同领域、 不同阶段的基于逻辑、状态机、网络、代数等多形式化方法。如今人们在形 式化方法这一领域取得了重要的研究成果。形式化方法的本质是用数学的方 分形图形的代数语言系统研究 法来描述目标软件系统属性的一种技术。不同的形式化方法，它的数学基础 有所不同，有的是以时态逻辑为基础；有的是以一阶谓词演算为基础；有的 是以集合论为基础。这种方法主要应用于在计算机科学、数学、人工智能等 领域。在逻辑科学中，形式语言是指分析、研究思维形式结构的方法。它是 把各种具有不同内容的思维形式( 主要是命题和推理) 加以比较，找出其中各 个部分相互联结的方式，如命题中包含概念间的联结，推理中则是各个命题 之间的联结，提取出它们共同的形式结构，再引入表达形式结构的符号语言 形式，用符号与符号之间的联系表达命题或推理的形式结构。 现行的形式语法系统是c h o m s k y 从产生语言的角度研究语言。通过抽 象，他将语言形式的定义为一个字母表中的字母组成的串的集合。 ( 1 ) 形式文法【6 】 文法g 是一个四元组，即g = ( ，y ，s ，尸) 。其中，叫做字母表，代表一 个有限字符的集合，它的元素称为字母或终结符；y 叫做非终结符集合，是 一个有限字符的集合，它的元素称为变量或非终结符( 一般用大写英文字母 表示) ；s 称为文法的开始符，是一个特殊的非终结符，即s y ；p 称为产 生式，是非空又穷集合。尸中的元素均具有形式口寸，读作1 2 定义为。 其中口( z u f ) + ，且口中至少有y 中一个元素出现；( z u f ) 。口称为产生 式口专的左值，称为产生式口专的右值。对于文法g ，如果sj 木缈，则 称国是g 的一个句型；若国中包含的字符全是终结符，缈称g 产生的一个句 子。 给定文法g = ( ，y ，s ，尸) ，有开始符号s ，把s 可以推导出的所有终结符 串的集合，称为由文法产生的语言，记为三( g ) ，即 三( g ) = 缈isj 国，国) ( 2 ) 形式语言的特点【7 】 高度的抽象化( 采用形式化的手段：专用符号、数学公式来描述语言 的结构关系，这种结构关系是抽象的) 。 是一套演绎系统( 形式语言本身的目的是要用有限的规则来推导出语 言中无限的句子，提出形式语言的哲学基础也是想用演绎的方法来研究自然 语言) 。 具有算法的特点( 例如句法分析中采用不同的算法来构造句子的句法 推导树) 。 1 3 国在内外发展现状 当前生成分形图形的方法很多，最典型最成功的就是迭代函数系统 ( i f s ) 。迭代函数系统是由b a r n s l e y 和h u t c h i n s o n 提出的用来研究分形的数 4 硕十学位论文 学方法。其基本思想是给定几何对象的整体和局部，在仿射变换的作用下， 整体和局部具有自相似结构。用户首先要对几何对象的整体进行定义，然后 选定若干仿射变换，将整体经仿射变换变换到局部，如此进行反复迭代，一 直迭代到得到满意的分形图形。到目前为止，国内外学者在基于迭代函数系 统o f s ) 的分形图形生成领域进行了大量研究工作，产生了带凝聚集i f s 、带 参数i f s 、带概率i f s 、再归i f s 等，并取得了一定的成果【8 1 1 】。 美国伊利诺斯州立大学计算机系的j o h nc h a r t 和p a u ls h e r m a n 通过操 作一个由再归迭代函数系统( r i f s ) 生成的分形图来达到建模的方法，这就是 分形生成的交互式建模方法【l2 1 。这个方法可以直接让用户对吸引子上的特 定点进行指定，然后通过拖拉其它的点到满意的位置，这关系到图形效果的 关键步骤，同时吸引子的形状也会改变。 h a m m e l 与p r u s i n k i e w i c z 等通过加入不同变换顺序的约束条件，提出了 “语言约束式迭代函数系统( 1a n g u a g e r e s t r i c t e di f s ) ”方法【l3 1 ，该方法可以 比较通用地概括各类不同的i f s 方法。 传统的i f s 是基于压缩仿射变换，其建模能力非常有限，若对局部进行 仿射变换，其整体吸引子不一定也仿射变换，也就是说迭代函数系统( i f s ) 不是仿射不变的。对于这些缺点，意大利学者l j u b i s am k o c i c 基于i f s 理 论，提出了仿射不变迭代函数系统a i f s 1 4 】。这种新的技术可以模拟基本分 形的可预知的形状，可以得到与现实自然界物体特别是生物属性及生物形态 非常接近的模拟图形。 陈传臻等给出了一种获取i f s 码的方法l l 副，简单的分析了分形图i f s 码的理论基础，在此基础上提出了更为有效的方法一一矩形框法，该方法大 大减少了繁琐的修正操作，提高了获取i f s 码的效率。 魏小鹏等提出了基于i f s 的3 df r a c t a l 可视化技术研究【l6 1 ，将i f s 进行 扩展，使之可作用于3 d 对象的顶点集，给出了3 df r a c t a l 绘制技术。在此 基础上，为了使视觉深度信息更好的再现，给出了基于b 样条的颜色插值技 术。 张赣源等提对i f s 中随机迭代算法进行改进【1 7 】，通过改变组成i f s 的 各个仿射变换的系数，在构造对应吸引子的随机迭代算法中不必再引入新的 中间量，从而降低了运算量。 熊勇等给出了确定一个随机迭代函数系统的原图像经过仿射变换后得 到的新图像所对应的随机i f s 的具体方法【l 引，它对揭示仿射变换参数的随 机i f s 中的作用提供了某些信息。 刘向东等提出了迭代函数系统i f s 吸引子的参数控制与树木模拟 1 9 1 ， 对i f s 树木的模拟给出了参数变化控制的条件，方便了对树木模拟的实现。 分形图形的代数语肓系统研究 翟俊海等提出了一种迭代函数系统应用于图形模拟的新方法【2 0 1 ，此方 法对那些具有自相似的分形图形模拟非常有效，对一般图形，若选取合理的 仿射变换系数，也可以取得满意的模拟效果。 张正炳等提出了一种实现图象几何变换的迭代函数系统i f s 参数修改 法【2 ，导出了实现图象平移、旋转和缩放的i f s 参数变换公式，这种方法 是通过修改图象的i f s 码而实现i f s 吸引子的几何变换。 王梦等提出了一种新的分形插值算法【22 1 ，通过矩形剖分上的采样数据点 构建分形差值曲面，从而得到连续的分形图形。 王镝等人给出了一种吸引子通用参数控制方法【2 3 1 ，通过对参数的改变 来控制i f s 吸引子的形状，从而生成形状各异的分形图形。此方法通过对两 个原始三角形位置和形状的改变得到i f s 码，然后通过不断引入新的三角形 并对新的三角形的位置和形状进行改变，从而达到i f s 吸引子的外观的改 变。 章立亮研究了迭代函数系统i f s 随机分形的构造问题，提出了基于概率分布 随机和生成元随机的方法【2 4 1 ，通过引入随机因素对带概率的i f s 的伴随概率集 作随机化处理，从而实现了i f s 随机分形的计算机生成。 王吴鹏等建立了具有几何意义的外部参数模型【2 5 1 ，通过引入外部参数间接 地控制函数系统中内部的参数，产生新的i f s ，使得能够按照一定的图形设计规 则控制分形图形的演化。 张文辉等在原有系统的迭代过程中嵌入不同形式的参数对原有的系统进行 改造1 2 引，拓宽了参数的调控范围。 刘树群针对迭代函数系统分形吸引子变形时出现失真、断裂、特征退化等问 题，分析现有变形技术的缺陷，提出基于i f s 的交互式分形造型生成算法【2 7 1 ，解决 了吸引子变形时的连通性问题：并在吸引子连续变化中采用对点交互式插值的方 法获得高效快速的实时动画效果。 胡海龙提出再归迭代函数系统的分形图形生成技术【2 引，这种方法是以某种 关系将多个迭代函数系统进行组合，这样生成的吸引子可以表现出多个i f s 吸引 子的特征。 李红达等人阐述了迭代函数系统i f s 与再归迭代函数系统r i f s 的关系【29 1 ， 说明r i f s 是比i f s 具有更加普遍意义的迭代函数系统，具有更强的表达能力。 迭代函数系统是生成分形图形的最主要方法之一，这种方法生成的大量的分 形图形具有自相似结构。张亦舜等提出了新的方法【3 们，通过寻找新的i f s 建模 技术，根据在已知的i f s 码中加入某些参量进行调整来生成新的分形图形，这种 方法可以得到更自然、逼真的的分形图形。 李庆忠等提出了一种l 系统与i f s 相融合的植物形态模拟新方法【3 1 1 ，将l 6 硕士学位论文 系统和i f s 两种方法的优点结合在一起，可以得到更新颖的富于变幻的分形图 形。 马石安等人给出了两种i f s 吸引子随机迭代算法的改进方法【3 2 1 ，此方法可 以对i f s 吸引子图像实现其局部细节与色彩的控制，具有很强的通用性和实用 性，大大增强了i f s 吸引子的表示范围。对植物的动态模拟及各种形态的植物提 供了一条技术途径。 郝小琴提出了三维迭代函数系统建模技术的研究【3 3 1 ，将i f s 二维模拟推广 到三维，给出了基于树木的分支模式与叶序模式的三维i f s 建模法以及相应的图 形绘制算法。用3 d i f s 来描述森林景物的形体模型，并寻找生成3 d i f s 码的新 途径，这样，由一组i f s 码就可获得多幅森林景物的三维图。 1 9 6 8 年，美国生物学家l i n d e n m a y e r 从植物形态学角度给出用于描述植物 生长的数学模型【3 4 1 ，后来才引进几何解释进行描述，形成了l 系统。 1 9 8 4 年，a l r ls m i t h 把l 系统与计算机图形学综合起来【3 5 】，从而显示了l 系统在植物形态模拟方面的巨大潜力。l 系统本质上是一种形式语言，是一种描 述植物的拓扑结构的方法，它用符号来表示各部分状态，再按照一定文法规则， 通过几何解释形成接近现实的图形。这种模型本质是重写和将形式化语言进行图 形化。 近年来，随着计算机性能的高速发展，计算模型和方法也随之迅猛发展，原 来很难模拟的植物模型，现在也可以非常逼真的描述。l 系统与计算机图形学结 合，更增强了建模的功能，这就吸引着越来越多的人加入到模型架构和植物生长 的研究中来。 秋林等提出了一种用形式化语言l 系统描述植物根部形态的建模方法【3 6 1 ， 借助动态数据结构的应用，同时引入随机生成技术，在一定程度上弥补了l 系 统灵活性较差的不足，使得根系的显示更加自然真实。 陈敏智等提出参数化l 系统生成植物生长结构模型的方法【3 7 】，通过对植物 结构模型所需要的l 系统的迭代公理和若干产生式参数的模拟，实现了植物形 态可视化。 张树兵等给出了一个改进方法1 3 引，采用递归式表示l 系统所生成的表达式， 再由递归式编写递归算法和程序。这种方法简化了建模过程，提高了算法的效率。 丁维龙等提出了用子结构算法来代替重复迭代【3 9 1 ，这样减少了l 系统重复迭 代所占用的系统空间，同时利用植物学家总结的植物架构模型，从而得到l 系 统的模板库，拓宽了系统的适用面，弥补了l 系统在通用性上的缺陷，开发出 了可视化模拟系统v p g 1 。 史丽敏利用l 系统与几何造型结合的方法【4 们，给出了更接近真实的景物。 陆汝钤等提出了广义l 系统【4 1 1 ，对自然界的异步现象进行模拟，证明了广 分形图形的代数语言系统研究 义l 系统不能被传统l 系统所覆盖，同时还将广义l 系统进行划分。 崔劲等提出植物枝干重点生成方法【4 2 1 ，采用特定的l 系统描述植物结构， 并结合灵活的数据结构，是植物特征得以及时调整，较好的弥补了l 系统的不 足。 孔勇等利用计算机对植物的形态进行了模拟【4 3 1 ，通过树枝的旋转角度和步 长加入一个扰动变量，以及将不同的生成规则加入同一l 系统中，使l 系统生 成的图像能更好地表现出植物的生物学和形态学特征。 l s t u d i o 是基于l 系统的植物建模工具【4 4 1 ，是由加拿大的c a l g a r y 大学开发 的，主要研究植物和它外界环境间的交互性。用户只要利用预定义的解释符编出 想要模拟植物的l 系统产生式，再应用产生式软件生成所期望的植物模型。 刘树群等人提出符号重写算法【4 5 1 ，把l 系统的文法规则应用到i f s 中来， 这样使i f s 与l 系统建立了联系，这种方法可以自定义公理和规则，表现出比l 系统和i f s 更强的表达能力和造型能力，实现了l 系统和i f s 难以绘制的分形图 形。 加拿大的c a l g a r y 大学的p r u s i n k i e w i c z 等人为了研究l 系统更强的造型能 力，把l 系统扩展为：开放式l 系统( o p e nl s y s t e m ) 4 6 1 ，此系统能够与周围环 境进行交互；随机l 系统( s t o c h a s t i cl s y s t e m ) 4 7 1 ，此系统能够模拟植物生长的 随机性，为了能够与周围环境进行交互，同时引入了一个与周围环境进行交互的 “交流符号 ；时变( t i m e d ) l 系统【4 引，此系统可以模拟植物的连续生长过程，还 能模拟植物生长过程的计算机动画；微分l 系统( d i f f e r e n t i a ll s y s t e m ) 4 9 1 ，此系 统能更逼真的模拟植物的连续生长过程中植物的叶序、美丽的花朵、弯曲的枝条 等，比较真实的模拟了植物的生长过程。 v i r t u a lp l a n t s 是基于l 系统的一个模拟软件，它是由澳大利亚c p a i 研究中 心研发的，不仅包含已有器官的大小及形状变化规则还包含了新的植物器官产生 规则。主要用来模拟害虫对于作物的影响和大豆、棉花等作物的生长发育过程以 及棉花与害虫之间的交互作用。 1 4 当前存在的问题 迭代函数系统( i f s ) 和l 系统是产生分形图形的两种不同方法，国内外学者 在这两个系统领域进行了大量研究 5 0 - 5 3j ，其理论和应用方面都有较快发展，但 都是分别独立的利用迭代函数系统( i f s ) 或l 系统方法，因为每种方法都有其各 自的局限性，所以很难实现植物形态的自然与逼真模拟效果。 l 系统本质上是字符串重写系统，对描述具有严格分形结构的植物体形态结 构非常精炼，可用于对自然界中相当一部分植物的模拟。为了能够增强l 系统 的造型能力，许多学者从符号、参数、随机性等方面对l 系统进行扩展，产生 8 硕士学位论文 了d o l 系统【5 4 , 5 5 】、带参数l 系统【5 6 1 、随机l 系统，但l 系统在重写过程中其 符号串长度以指数增长会越来越长，字符串比较繁杂，很难对其进行读取，其图 形意义不容易把握。 迭代函数系统i f s 具有严格自相似性，主要利用仿射变换绘制分形图，但缺 乏对事物拓扑结构的控制，带凝聚集i f s 、随机i f s 、再归i f s 等的出现，大大 增强了i f s 的造型控制能力，但生成算法并不统一。刘树群等将i f s 符号化【4 5 1 ， 基于l 系统的文法规则，用形式文法对i f s 进行描述和处理，将i f s 和l 系统 之间建立了联系，但它只对常规i f s 进行了分析，对带凝聚集i f s 、随机i f s 、 再归i f s 等没有进行符号化，而且表达能力也有限。 若要将l 系统和i f s 这两种方法的优点结合起来去生成分形图，找到一个 统一的描述方式去描述i f s 和l 系统是非常必要的。本文根据形式语言及其在l 系统中的应用，定义了一个能将i f s 及l 系统及其扩展系统统一描述的代数语 言系统，即分形图形的语言代数系统。 1 5 课题研究意义 分形被称为是“大自然的几何学 ，研究分形不仅可以解决欧式几何所不能 描述的复杂的、不规则形体的难题，还是探索自然界中复杂事物的客观规律及其 内在联系的必然要求，它为描述这一大类复杂问题提供了新的思维方式和方法。 迭代函数系统( i f s ) 和l 系统是生成分形图形的典型方法，i f s 可以生成大量 的具有自相似结构的分形图形，l 系统利用符号串重写再对其进行解释生成分形 图形，但是i f s 和l 系统都有其局限性，随着对逼真程度和审美要求的不断提 高，为了得到新颖的、富于变化的分形图形，就要寻找新的建模技术。本文结合 了形式语言及i f s 和l 系统的优点，提出了代数语言系统，实现了i f s 和l 系 统的统一描述。这种方法是采用形式化方法，依据形式语言的形式把分形图形进 行抽象的描述，使分形和代数语言建立了联系。正则表达式的引入可以使分形造 型能力比i f s 和l 系统都有所增强；正则表达式方程解的引入使分形造型代数 化，更明了的看到吸引子的代数形式。代数语言系统应用于再归迭代函数系统、 随机迭代函数系统、带凝聚集迭代函数系统、带参数l 系统、随机l 系统等就 可以描述出复杂的迭代函数系统、l 系统不能实现的更加复杂、接近自然的分形 图形。 1 6 本课题主要研究内容 主要研究内容如下： ( 1 ) 基于形式语言和正则表达式基本理论给出了代数语言系统的一些定义、运 9 分形图形的代数语言系统研究 算性质和文法描述： ( 2 ) 研究了代数语言系统的语法形式； ( 3 ) 实现了l 系统及i f s 及其扩展系统用代数语言系统的统一描述； ( 4 ) 通过与分形相结合，给出了代数语言系统生成分形图形的具体实例。 硕士学位论文 第2 章迭代函数系统和l 系统 2 1 迭代函数系统 迭代函数系统( i f s ) 是由m f b a r n s l e y 于19 8 5 年提出的，这个分形造型 国( ；) = ( ；三 ( ； + ( 多) 口，b