（应用数学专业论文）ifs不动点连接技术研究.pdf

硕+ 学位论文 摘要 随着对分形图形学领域研究的深入，i f s 已成为自然造型的重要方法，然而 i f s 反问题还是没有得到很好的解决。在这种情况下，i f s 吸引子交互式控制技术 为分形造型提供了捷径。本文的i f s 不动点连接技术正是为实现i f s 吸引子的交 互式控制而提出的。i f s 不动点连接技术的提出，对把握i f s 构成与i f s 吸引子 的关系、预想分形集的i f s 设计和推动i f s 走向实用化都有着重要的意义。 文中首先介绍了分形的基本理论及分形图形生成的典型方法，如逃逸时间法、 l 系统、迭代函数系统i f s 等。在此基础上，给出了一些有关i f s 的新理论与性 质，并提出了i f s 吸引子的全断、全连通还是不完全连通等连通性的判定准则。 i f s 不动点连接技术是建立在不动点变换的基础上，用户编辑变换时附带连 线来表达不动点变换而形成的i f s 交互式设计技术。文中以典型的v o nk o c h 曲线 和s i e r p i n s k i 三角形为例，说明了i f s 不动点连接技术的基本原理。给出了i f s 不动点连接技术的定义及性质，并依据四种不同的分类方法对i f s 不动点连接进 行了分类，其中包括固定不动点连接、自由不动点连接、一笔画不动点连接、分 支型不动点连接、网状型不动点连接和混合型不动点连接等等。 在实现i f s 不动点连接技术时，为了使交互变得直观、灵活以及数据在程序 内部的表示更为方便，实现了几何变换的可视化与升级，根据场景缩放比绘制标 尺与坐标网格并约束变换的输入。最后以图例的形式，说明了基于i f s 不动点连 接技术所实现的功能，主要包括：两点、三点和四点变换的输入与编辑；i f s 吸 引子递归生成的深度与精度控制；常规分形、生长分形和在线分形等三种分形集 生成方式；两点与三点不动点连接分形；轴端、顶点与假设定义域分级不动点连 接分形；一笔画、分支型、网状型与混合型不动点连接分形；为增强分形集的视 觉效果，添加了一些辅助控制，如设置画笔颜色、使用纯色或渐变色设置填充颜 色等。 关键词：分形；迭代函数系统；吸引子；不动点；连通性 i f s 不动点连接技术研究 曼曼量曼曼曼! 曼曼曼曼曼曼曼兰皇曼曼曼曼曼曼曼曼曼曼! 皇曼曼曼! 曼曼曼皇曼曼曼曼皇曼曼i 舅曼曼曼曼曼曼曼曼! ! ! 曼曼曼曼曼曼曼曼曼曼曼 a b s t r a c t w i t hr e s e a r c hi nt h ef i e l do ff r a c t a l g r a p h i c si n - d e p t h ，i f sh a sb e c o m ea n i m p o r t a n tm e t h o do fn a t u r a lm o d e l i n g ，b u tt h ei f si n v e r s ep r o b l e mh a ss t i l ln o tb e e n s a t i s f a c t o r i l yr e s o l v e d i nt h i sc a s e ，t h ei n t e r a c t i v ec o n t r o lt e c h n o l o g yf o ri f sa t t r a c t o r p r o v i d e sas h o r t c u tf o rf r a c t a lm o d e l i n g i f sf i x e dp o i n tc o n n e c t i o nt e c h n o l o g y ( f p c t ) i nt h i sp a p e ri sp u tf o r w a r df o rt h er e a l i z a t i o no fi n t e r a c t i v ec o n t r o lo fi f s a t t r a c t o r t h ep r o p o s i t i o no ft h i st e c h n o l o g yh a sa ni m p o r t a n ts i g n i f i c a n c ef o rg r a s p i n g t h er e l a t i o n s h i pb e t w e e nc o n s t i t u t i o no fi f sa n di f sa t t r a c t o r , d e s i g n i n gi f sf o r a n t i c i p a t e df r a c t a ls e ta n dp r o m o t i n gp r a c t i c a b i l i t yo fi f s t h i sp a p e rf i r s ti n t r o d u c e st 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 f g e n e r a t i n gf r a c t a lg r a p h i c s ，s u c ha st h ee s c a p e t i m em e t h o d ，l - s y s t e ma n di t e r a t e d f u n c t i o ns y s t e m o nt h i sb a s i s ，s o m en e wt h e o r i e sa n dn a t u r e so fi f sa r eg i v e na n d s o m ec r i t e r i af o rj u d g i n gc o n n e c t i v i t yo fi f sa t t r a c t o rs u c ha sb r e a kc o m p l e t e l y , a l l c o n n e c t e do rn o tf u l l yc o n n e c t e da r ep r o p o s e d i f sf p c t w h i c hi sa ni f si n t e r a c t i v ed e s i g nt e c h n o l o g yb a s e do nf i x e d p o i n t c o n v e r s i o n ，f o r m e db a s e do ne x p r e s s i o ni nc o n n e c t i o nw i t hf i x e d p o i n tc o n v e r s i o n w h e nu s e r se d i tt r a n s f o r m a t i o n s w i t ht y p i c a lv o nk o c hc u r v ea n ds i e r p i n s k it r i a n g l e a se x a m p l e s ，s o m ef u n d a m e n t a lp r i n c i p l e so fi f sf p c ti nt h i sp a p e ra r ei l l u s t r a t e d t h ed e f i n i t i o na n dn a t u r eo fi f sf p c ta r eg i v e na n di f sf p c ti sc l a s s i f i e db a s e do n f o u rd i f f e r e n tc l a s s i f i c a t i o n st of i x e df p c ，f r e ef p c ，o n es t r o k ef p c ，b r a n c h t y p ef p c ， m e s h t y p ef p c a n dm i x e d - t y p ef p c ，e t c i no r d e rt om a k ei n t e r a c t i v i t yi n t u i t i v ea n df l e x i b l ea n dd a t aw i t h i np r o g r a mt h a t i sm o r ec o n v e n i e n tt or e a l i z ei nt h er e a l i z a t i o no fi f sf p c t , t h ev i s u a l i z a t i o na n d u p g r a d i n go ft h eg e o m e t r yt r a n s f o r m a t i o n ，d r a w i n go fr u l e ra n dc o o r d i n a t eg r i da n d r e s t r i c t i o no fi n p u tt r a n s f o r m a t i o na c c o r d i n gt ot h es c e n es c a l ea r er e a l i z e d a tt h ee n d ， i nt h ef o r mo fl e g e n d ，t h ef u n c t i o n si f sf p c ta c h i e v e da r es h o w e d ，i n c l u d i n g ：t w o ， t h r e ea n df o u r p o i n t st r a n s f o r m a t i o no fi n p u ta n de d i t i n g ；d e p t ha n dp r e c i s i o nb y w h i c hi f sa t t r a c t o r g e n e r a t e di nr e c u r s i v ec o n t r o l l e d ；t h r e ek i n d so ff r a c t a ls e t g e n e r a t i o nm e t h o d ss u c ha sc o n v e n t i o n a lf r a c t a l ，g r o w t hf r a c t a la n do n 1 i n ef r a c t a l ； t w oa n dt h r e ef p cf r a c t a l ；s h a f t ，v e r t e xa n dh i e r a r c h i c a la s s u m p t i o nd o m a i nf p c f r a c t a l ；o n es t o k e ，b r a n c h t y p e ，m e s h t y p ea n dm i x e d t y p ef p cf r a c t a l ；t oe n h a n c et h e v i s u a le f f e c to ff r a c t a ls e t ，a d d i n gs o m ea n c i l l a r yc o n t r o l s ，s u c ha ss e t t i n gp e nc o l o r s ， s e t t i n gf i l lc o l o rm a k eu s eo fs o l i do rg r a d i e n tc o l o r ，e t c 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 ；a t t r a c t o r ；f i x e dp o i n t ；c o n n e c t i v i t y 硕十学位论文 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 日期：五稗6 月e l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文收 录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名： 导师签名： 日期：翮。年6 月i e l e l 觏：矽f 汐年6 旯l e t n i 硕十学伶论文 插图索引 图2 1 复动力系统生成的m a n d e l b r o t 集和j u l i a 集。1 5 图2 2 各种i ，系统生成的分形图例及其重写规则1 8 图3 1v o nk o c h ： w i ：1 迭代一次2 5 图3 2s i e r p i n s k i ： w | f 曩1 迭代一次2 5 图3 3v o nk o c h ： w i 囊1 不动点连接图2 6 图3 4s i e r p i n s k i ： w i 矗1 不动点连接图2 6 图3 。5 固定不动点连接定义域模式2 8 图3 6 两点式自由不动点连接定义域模式。2 8 图3 7 固定不动点连接与自由不动点连接关系图2 9 图4 1 视口坐标系与用户坐标系一3 1 图4 2 点变换的可视化3 4 图4 3 不动点连接变换计算图3 7 图4 4 点变换升级图3 9 图4 6 三点变换标记图例4 0 图4 7 两点变换的点平移图例4 0 图4 8 三点变换的点平移图例4 1 图4 9 三点变换的对象平移图例4 2 图4 1 0 三点变换的对象旋转图例4 2 图4 1 1 三点变换的对象剪切图例4 2 图4 1 2 三点变换的对象镜像图例4 3 图4 1 3 深度控制吸引子生成图例4 3 图4 1 4 初始元替换图例4 4 图4 1 5 生长分形图例。4 5 图4 1 6 在线分形图例。4 5 图4 1 7 两点不动点连接分形图例4 6 图4 1 8 三点不动点连接分形图例4 6 图4 1 9 轴端不动点连接分形图例。4 7 图4 2 0 顶点不动点连接分形图例4 8 图4 2 1 假设定义域分级分形图例4 8 图4 2 2 一笔画不动点连接分形图例5 0 图4 2 3 分支型不动点连接分形图例5 1 图4 2 4 网状型不动点连接分形图例5 1 i l l i f ( 8 不动点连接技术研究 图4 2 5 混合型不动点连接分形图例5 2 图4 2 6 标尺与设置画笔颜色图例5 2 图4 2 7 设置图形填充颜色图例5 3 i v 硕+ 学位论文 1 1 课题研究背景 第1 章绪论 自e u c l i d 在两千多年前创立几何学以来，在漫长的岁月里，学者们基本上都 在e u c l i d 空间进行研究和探索。然而e u c l i d 几何学不是万能的，大自然的许多现 象都不能用e u c l i d 几何来解释，比如海岸线、山脉、岩石、树木、火焰、烟云、 闪电等等。那么如何来描述大自然几何以及其它许多e u c l i d 几何无法描述的问题 呢? 历史上曾出现由俄罗斯数学家l o b a c h e v s k i 创立的非欧几何，但其影响有限， 还是不能解决上述问题。 2 0 世纪7 0 年代，美籍法国数学家b e n o i tb m a n d e l b r o t 提出了“分形”一词， 其原义是“不规则的、分数维的、支离破碎的物体n o1 9 7 5 年，m a n d e l b r o t 在巴 黎出版了法文著作k so b i e c t sf r a c t a l s ：f o r m e ，b a s a r de td i m e n s i o n ) ) 。1 9 7 7 年，由 m a n d e l b r o t 撰写的f r a c t a l ：f o r m ，c h a n c ea n dd i m e n s i o n ) ) 一书的出版，标志着分 形理论的诞生。1 9 8 2 年，m a n d e l b r o t 的专著n ef r a c t a lg e o m e t r yo fn a t u r e ) ) 二 版的问世，迅速形成了“分形热”，标志着分形理论初步形成。 分形概念的提出，使得在一个世纪前相继出现的一些被称为“数学怪物”的 东西和大自然现象都得到了彻底的解决。典型的“数学怪物有v o nk o c h 曲线、 s i e r p i n s k i 三角形和c a n t o r 集，它们的共同特点是整体和局部具有相似性。然而 作为一门新学科，分形的定义还不是很明确。m a n d e l b r o t 曾指出：h a u s d o r f f 维数 严格大于拓扑维数的集合称为分形。但这仅是实验性的定义，很不严格，且无可 操作性。而后m a n d e l b r o t 修改了这个尝试性定义，提出：把那些整体与局部按某 种方式相似的集合称为分形。分形就跟“生命一词一样，很难给出确切的定义， 但其实质是指被那些传统的物理学和几何学排除在外的不规则形体在标度变换下 的自相似性。在不同的文献中，分形被赋予不同的名称，如“分数维集合一、“豪 斯道夫测度集合 、“s 集合 、“非规则集合 和“具有精细结构集合 等等。通 常可以把分形看作是大小碎片聚集的形态，是没有特征长度的图形、构造或现象 的总称。由于在许多学科中的迅速发展，分形已成为一门描述自然界中许多不规 则事物和现象的规律性学科。 应用分形理论来研究非线性科学中的各种课题，丝毫不贬低线性近似处理方 法的重要性，因为在一定的误差范围内，应用线性近似处理方法可以迅速得到有 效的结果。但是对于远离平衡的非线性复杂系统或过程来说，就只能用分形理论 来进行研究，正如对于低速运动的物体，用牛顿三大定律来处理是完全正确的， 而对微观世界中粒子的高速运动，就只能用量子力学和相对论来描述。 i f s 不动点连接技术研究 分形几何诞生2 0 多年来，对各门科学的影响都是巨大的，涉及的领域有数学、 物理、化学、生物和医学、地貌与地震、材料、天文学、计算机科学、社会与人 文、哲学、经济学、金融学乃至音乐、绘画和影视制作等等。美国物理学家w h e e l e r 说：“可以相信，明天谁不熟悉分形，谁就不能被认为是科学上的文化人 。分形 以其新颖的概念和广阔的应用前景，引起了人们的浓厚兴趣。 分形的计算机生成，有着重大的应用价值。采用分形生成方法，可以用少量 的数据生成复杂的景物图像，从而为分形在模拟自然景物、动画制作、建筑物配 景、图案设计以及影视特殊景物生成等方面显示出传统几何所无法比拟的威力， 有些甚至已经达到了以假乱真的程度。反之，考虑分形生成的反问题，即从给定 的景物图像提取少量的数据形成原图像的分形生成数据，那么在分形图像压缩与 编码、信息的提取与识别、纹理图像分割、数字水印等方面将会有更大的突破。 分形几何学为自然界中存在的各种景物提供了逼真的描述。传统的几何工具 是基于e u c l i d 几何设计的，基本图元是点、线、圆等等，通过几何形状和不同的 比例来定义形体的大小和形态。自然界中有许多景物形态复杂且不规则，使得采 用传统的几何工具进行描述遇到了极大的困难，而利用分形模型却能使困难迎刃 而解，因为自然界中的许多实际景物本身大体上就是分形，或者说，按照分形几 何方法构造的形态与许多自然景物相似。 分形的研究离不开计算机，离不开计算机科学。如果不是计算机图形图像处 理功能的日益强大，无法想象怎样才能直观地看到j u l i a 集和m a n d e l b r o t 集的精 细结构，更无法想象怎样产生具有无限细节的自然景物和高度真实感的三维动画。 反之，对分形理论与方法的研究也极大地丰富了计算机图形学的内容，甚至分形 的思想将会在计算机科学的发展道路上产生一定的影响。 1 2 课题研究内容 本课题的研究内容有： ( 1 ) 研究分形基本原理与分形图形生成的典型方法：分形的定义与特点、分形 空间与分形维数，动力系统，l 系统，迭代函数系统i f s 。 ( 2 ) 基于地址空间的全断i f s 、刚触及i f s 和交叠i f s 与i f s 吸引子之间的关 系，i f s 吸引子连通性，i f s 不动点连接的基本理论、基本原理、定义、性质和分 类。 ( 3 ) 研究i f s 不动点连接技术的实现：坐标系变换及坐标网格的绘制、变换的 可视化及约束输入、几何交换的计算、升级及编辑；分形生成的递归控制、初始 元替换、分形集生成方法控制和辅助控制等功能的实现及图例分析。 2 硕十学位论文 i i i _ i i i i i i 一_ i i 皇曼皇曼皇曼皇蔓皇曼皇皇曼曼皇曼鼍曼 1 , 3 课题国内外研究现状 自m eb a r n s l e y 于1 9 8 5 年提出i f s 以来，国内外学者在i f s 分形图形生成 领域做了大量的研究工作l l _ 8 j ，取得了一定的进展，i f s 也已成为自然形态造型的 重要方法，但i f s 仿射变换的编码困难问题还没有得到很好的解决1 9 1 。在这种情 况下，利用已有的i f s 加以适当的调整来产生更多形态的分形便成了捷径，归纳 近年来这方面的研究内容，主要集中在两个方面：一是增强i f s 分形局部细节变 换的控制，其理论基础是吸引子对参数的连续依赖性原理，该方法能产生局部细 节变化丰富的图形；二是通过改变吸引子分形的结构以产生与原图形存在差异的 新分形，该方法能够得到大量形态各异的图形。纵观这些年对i f s 吸引子控制技 术的研究，可以从三个角度来综述与本课题相关的国内外研究现状： ( 1 ) 从i f s 吸引子的生成技术和可视化技术角度来看： 传统的基于压缩仿射变换的i f s ，其建模能力非常有限，比如不容易预测吸 引子的局部和整体形状；i f s 不是仿射不变的，即对i f s 每部分进行仿射变换的 结果不等于对其吸引子图像的仿射变换。针对上述i f s 的缺点，意大利学者l j u b i s a m k o c i c 在i f s 理论的基础上，提出了一种新的技术一仿射不变迭代函数系统 a i f s 1 0 j 。a i f s 可以用于基本分形的可预知形状的建模。在仿射不变的条件下， i f s 可以对吸引子定位并描述出吸引子整体形状，即吸引子形成的分形图形。用 这个方法可以得到与实际自然界的物体，尤其是生物形态及生物属性非常相似的 物体的模拟图形，比如模拟植物的生长分枝，从而可以从分形维渐变地过渡到充 满空间的自然的不规则图形。 ht c h a n g 提出h f p s ( h i e r a r c h i c a lf i x e d p o i n ts e a r c h i n g ) 算法1 1 1 j ，直接从分 形的i f s 码来确定分形的大致形状、原始大小和位置，利用这些几何信息对一个 已知的分形集进行各种仿射变换来获得新的分形。与传统的随机迭代算法相比， 该算法的计算效率较高，只需要计算i f s 中各变换的不动点就能确定分形集的大 小和位置。文献 1 2 1 3 讨论了几个基本几何变换的复合问题，使用这种复合变换 将一个分形集变换到平面上不同位置，最后合成了一个复杂图形。将单一的分形 集作为种子图按照一定的几何设计规则合成一个预想的复合图形，构图过程原理 简单、几何直观性强，能得到丰富多样的分形图案，但要求事先精确计算各子图 的大小和变换位置，这是直接关系到图形效果的关键步骤，有时保证各子图之间 不交叠是不易实现的。 美国伊利诺斯州立大学计算机系p a u ls h e r m a n 和j o h nc h a r t 给出了一个 交互式建模方法【1 4 j ，用户可以直接操作由递归迭代函数系统( r i f s ) 生成的分形 图。该方法可以让用户指定吸引子上的特定点，然后拖拽其它点到用户期望的位 置，从而改变吸引子的形状。这种方法具有交互性强、直观性好、易于使用等优 3 i f s 不动点连接技术研究 点。对于吸引子上点的位置在小范围内移动时，这种直接处理方式的构图效率较 高，但在大范围内移动吸引子上的点时，不能保证放射变换是压缩的，吸引子的 形状变化不可预料甚至整个吸引子会消失。另外，当吸引子局部之间有重叠时， 重叠部分导致点的地址成倍增加，重复计算地址造成计算时间浪费，会使图形生 成速度降低。 王镝等人在交互式可视化设计i f s 吸引子方面提出了参数控制方法1 1 5 j ，通过 改变参数控制i f s 吸引子的形状，最终生成不同的计算机图像。该方法首先给出 两个原始三角形，通过对两者位置和形状的改变得到i f s 码，然后不断引入新的 三角形并改变其位置和形状来影响i f s 吸引子的外观。该方法实现了连续的参数 控制与i f s 吸引子的动态变化，为计算机交互式设计i f s 提供了支持。 为避开仿射变换参数选取的盲目性和分形造型的不可预知性，章立亮提出了 具有可视化的外部参数模型【1 6 】，即通过对原i f s 各变换的不动点连接而成的闭合 多边形的调控来产生新的i f s ，从而实现按照一定的图形设计规则控制分形图的 演化的目的。利用该算法可以直观有效的获得大量形态各异的分形图。然而，该 算法中对不动点的移动，仅限于保持由它们连接成的多边形的边不相交，如果有 意使这些不动点在移动过程中，产生的多边形的一些边发生相交，则产生的图形 将会发生错切、扭曲、折叠等现象，图形的结构可能更加复杂且不可预知。 维也纳技术大学计算机图形学院的e d u a r dg r o l l e r 和r a i n e rw e g e n k i t t l 提 出了比带压缩仿射变换的i f s 更复杂的i f s 一非线性迭代函数系统【r 7 1 ，将i f s 中 的线性变换推广到非线性变换，并实现了i f s 的交互式可视化设计。他们用扭曲 的网格( 表示非线性函数) 来指定更高复杂度和更高建模能力的i f s 。为建立网格 模型，给出了带有称之为高层次运算的程序。考虑到i f s 的交互式设计及其有限 集的渲染，文中还给出了用z 缓存算法显示随机算法的结果。 魏小鹏等人将二维i f s 分形的可视化推广到了三维。文【1 8 1 基于i f s 理论， 将随机迭代算法进行拓广，使之可作用于3 d 对象的顶点集，并分别给出基于扛 缓存和基于测度理论的3 df r a c t a l 绘制技术。为使视觉深度信息能更好地得以再 现，还给出一种在均匀颜色空间基于b 样条的颜色计算模型，使得顺色选择、处 理、插值皆具有很大的柔性；文【1 9 】利用计算分形吸引子的三维菲线性确定性算 法，给出了一个简单而行之有效的计算光线与分形体表面交点和交点处法矢的技 术，对生成三维真实感分形图形具有重要意义。 ( 2 ) 从i f s 吸引子生成算法角度看： i f s 是图像编码的一种方法，常常要求得到很大的压缩比。雷丁大学的s a r a h b m b e l l 给出了一个解码i f s 码的改进算法【2 0 1 。该算法可以生成分辨率更好的 吸引子图像，甚至提高生成速度。文中讨论了算法的几何性质，并且说明了i f s 码的局部性质与被解码图像的整体拓扑性质之间的直接关系。 4 硕十学何论文 传统的i f s 生成分形图像的方法存在着一些实际问题，如生成效果完全取决 于拼贴过程，这种“交互性 对人的要求太高；压缩比虽然大，但其代价是时间 长，这严重地限制了i f s 的实用。针对i f s 存在的问题，曹汉强等人提出了分形 图像的快速生成新方法【2 ，即采用无逃逸行为算法和最少点绘制算法进行分形图 像的生成。该算法可以并行执行，有利于图形的快速生成( 仅为传统随机迭代算法 中单个仿射变换的生成时间) 和直观地显示图像的生成过程，为分形图像的快速生 成提供了新的途径。 随机迭代算法能够简单快捷地构造i f s 吸引子，但不能保证在有限步内计算 出组成吸引子的所有点。张亦舜等人针对以上不足，提出了一种吸引子构造新算 法1 2 2 】，新算法的主要思想是根据i f s 吸引子具有的自相似性，即根据i f s 吸引子 的局部与整体的相似性得到局部与局部相似的性质。根据上述性质，若得到了吸 引子某个局部的点，则由相应变换就可以得到若干其它局部的点，然后由这些点 组成一个更大的已知局部，由此再求其它局部的点，重复此过程，直到求得整个 吸引子。该算法可以在有限步内生成整个吸引子，并且不必引进概率。 上述算法免去了概率的引进，可是不易控制求逆过程。刘树群等人讨论了一 种基于一般几何变换的分形吸引子的生成【2 3 1 。该算法是直接根据吸引子的最终形 状确定各变换中的参数，再根据变换计算新点位置并绘制。在生成吸引子的过程 中，很容易引进概率来控制变换的使用，并且可以随意控制吸引子的生成层数。 与其它分形吸引子生成算法相比，应用这一算法生成的吸引子效果是一样的。 在i f s 吸引子逼近算法方面，文【2 4 】提出了五种分形集的逼近算法，文 2 5 】 又增加了两种算法，这些算法基本上就是目前i f s 的引子的逼近算法。文【2 4 】的 五种算法的比较结果表明，算法g 是其中最好的算法。文2 5 1 的重点排出算法效 率较高。王万恒在算法g 的基础上，提出了一个逼近算法【2 们，算法得到的误差估 计优于上述所有算法，计算效率与绘图精度也最好。为提高逼近效率，文中还首 次提出了一种优化技术。它的基本思想是，预测某点的下次迭代位置，以决定是 否用它进行下次迭代，从而达到提高计算效率的目的。文f 2 7 1 提出了一种标记算 法，采取边迭代边绘制的方法，对迭代函数系统吸引子逼近集中的每一点，用不同 的符号标记该点的绘制状态以及在各变换下的原像。迭代过程中，根据点的标记符 号减少对该点所做的变换和相应变换下像点的重复绘制。利用该算法与文【3 5 】的 逼近算法进行了数值比较，结果表明，该算法可以快速高效地绘制出i f s 吸引子 的分形图。 ( 3 ) 从i f s 吸引子变形技术和基于i f s 的建模技术角度看： 贾建等人由i f s 的变换构造不动点多边形【2 引，根据不动点多边形的匹配关系 得到从源图像到目标图像的中间插值算法，实现了分形图形的渐变过程。但存在 的问题是渐变过程中图形可能发生严重的扭曲现象。其次，由不动点所构成的多 5 i f s 不动点连接技术研究 曼量舅曼曼曼皇曼鼍皇皇曼曼曼皇曼皇曼i i ! 曼曼曼皇曼曼曼量皇蔓量寡量毫曼曼皇曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼曼量皇寰 边形形状大致反映出该分形图的形状。如果渐变过程中不动点构成的多边形形状 变化有趋于狭长的趋势，则中间生成的分形图形有消失的可能性，也可能看起来 挤成一条窄带，而没有了分形的特征。 b r a n d o nb u t c h 研究了线性分形图形的插值【2 9 1 。文中采用极分解的方法来避 免奇异的中间变换并能够更好地模拟关节运动。还介绍了一种基于图像的技术， 用于确定i f s 吸引子的连通性。对于每个图形插值，都定义了一个带两个参数的 i f s ，并绘制出这些图形的连通性，以保证插值过程中的连通性。 t o m e km a r t y n 研究了2 d 仿射i f s 吸引子变形的新方法【3 0 l 。提出了吸引子变 形的正确性标准：一是通过变形得到的中间形状应该对关键形状的仿射变形不敏 感一称之为变形的仿射稳定性；二是中间形状应该与关键形状有更多的相似性， 就像关键形状之间一样。文中还讨论了由若干不同映射的i f s 表示的混合分形， 并给出了解决方法。还提出了许多新的观点，包括i f s 相似等价类、i f s 标准型、 i f s 变形空间以及特殊s v d 。最后指出了文中所提出的想法在某些方面的应用和 未解决的问题。 在基于i f s 建模方面，魏小鹏讨论了迭代函数系统拼贴建模方法f 3 1 】，从整体 和局部的组合与相似关系出发，对传统拼贴建模方法进行简化，给出两种简化方 法：局部轮廓法和三点法，分析了三种建模方法的应用条件和具体实现技术。简 化方法比传统方法操作简易，而且重构可视化程度高。然而，i f s 建模技术要求 非规则自然景物的自相似程度较高。事实上，真实世界中的许多自然景物的自相 似程度并不高，这将导致重构图形与原景物有一定的差异。因此，在绘制时，需 对每次迭代时所选取的仿射变换作一些随机的调整。 华中科技大学马石安等人给出了一种基于i f s 的森林景物动态模拟方法【3 2 1 。 首先介绍了以迭代函数系统来探索和解决森林树木这一类自然景物在计算机生成 问题的途径，然后从一个已模拟景物的i f s 吸引子出发，改变参数自动生成无重 复的序列图画，以此达到对森林景物动态模拟的目的。用此方法生成的前后两帧 图形之间即有区别，又具有相对的连续性，为计算机对复杂自然景物的动态模拟 提供了一条新的途径。 郝小琴把基于i f s 二维森林景物建模技术推广到三维1 3 3 1 ，提出了基于树木的 分支模式与叶序模式的三维i f s 建模法以及相应的图形绘制算法。与其它建模方 法相比，文中提到的森林景物生成方法具有模型简单、存储量减少、便于并行处 理等优点。 1 4 课题研究意义 迭代函数系统( i t e r a t e df u n c t i o ns y s t e m ) 是生成分形图形的典型方法之一。它 6 硕十学何论文 根据不动点原理采用一组压缩仿射变换来生成i f s 吸引子，即通过对原始图形( 初 始元) 的平移、缩放、旋转、错切、镜像等变换的迭代而形成的具有自相似分形结 构的极限图形。 本课题将借助于分形理论【3 4 枷l 、拓扑学、泛函分析、计算几何、交互控制技 术等研究i f s 的不动点连接技术，可望得到一些有价值的i f s 交互理论以及推动 i f s 走向实用化。i f s 不动点连接技术的研究具有重要的意义： ( 1 ) i f s 不动点连接技术对把握i f s 构成与i f s 吸引子的关系有重要意义 i f s 是一个比较复杂的生成分形图形的方法，它需要依附很多的数学知识。 然而i f s 生成分形图形的基本思想却比较简单，它认定几何对象的整体与局部在 仿射变换意义下具有自相似的结构，因此，定义几何对象的整体并选定仿射变换， 将整体形态变换到局部，反复迭代该过程直到得到满意的分形集。然而要真正的 理解i f s 并不是件容易的事。 通过对i f s 不动点连接技术的研究，可以让人们更加了解什么是分形，更加 容易把握i f s 的基本思想以及与其它的分形图形生成方法的区别，更加深入理解 i f s 的构成与i f s 吸引子之间的关系。 ( 2 ) i f s 不动点连接技术对预想分形集的i f s 设计有重要意义 i f s 生成分形吸引子通常都要经过许多次的迭代才能看清楚吸引子的形状。 对于给定的一个i f s ，显然人工画出其吸引子是不太可能的，而使用计算机模拟 就必然需要设计出简单、快捷、有效的方法，只有这样，我们才能更快更清楚的 看到吸引子的形状。 通过对i f s 不动点连接技术的研究，可以为分形图形的i f s 程序设计提供更 为直接有效的方法，从而减少人工预想分形集所带来的不便。 ( 3 ) i f s 不动点连接技术对推动i f s 交互理论和i f s 走向实用化有重要意义 i f s 的吸引子一般呈现出精细复杂、具有自相似性的结构，能够很好地模拟 传统几何难以描述的各种自然景物。但采用i f s 进行景物模拟时，需要获得构成 该i f s 的各个压缩映射的参数，然而目前i f s 分形生成技术都有其局限性：都是 寻找i f s 码或调整i f s 码来实现分形吸引子的生成和变形，不能很方便地进行交 互并实时看到分形吸引子的形状。 随着对逼真程度和审美要求的不断提高，从简单的m a n d e l b r o t 集和j u l i a 集 到科幻电影上的分形风景，以及近年来印有分形图案的时装，都显示出了分形正 从科学研究领域走进人们的现实生活中。 通过对i f s 不动点连接技术的研究，可以丰富i f s 的交互设计理论，用尽可 能通俗易懂的方式，在一个交互实时界面上，用户只需通过简单的操作，就可以 交互式的实时生成各种美丽的分形图形，为i f s 走向实用化添砖加瓦。 7 i f s 不动点连接技术研究 1 5 论文的组织结构 第一章论述了课题的研究背景、意义、内容及国内外研究现状。 第二章论述了分形的基本理论和分形图形生成的基本方法，包括分形的定 义、特点、分形空间与分形维数、动力系统、i ，系统、迭代函数系统。 第三章论述了i f s 不动点连接技术的基本理论及性质，包括i f s 吸引子连 通性，i f s 不动点连接技术的基本理论、基本原理、定义、性质、分类及固定不 动点连接与自由不动点连接的关系。 第四章论述了i f s 不动点连接的实现，包括坐标系变换、坐标网格的绘制、 变换的可视化及约束输入、几何变换的计算、升级与编辑、实现的功能及图例分 析。 8 硕十学何论文 第2 章分形理论及分形图形生成的基本方法 2 1 分形的定义与特点 2 1 1 分形的定义 分形一词是m a n d e l b r o t 在2 0 世纪7 0 年代为了表征复杂图形和复杂过程首先 引入自然科学领域的，它的原意是不规则、支离破碎的物体。分形几何学是一门 以非规则几何形态为研究对象的几何学。由于不规则现象在自然界是普遍存在的， 因此分形几何又称为描述大自然的几何学。分形几何建立后，很快引起了科学界 的关注，这是由于它不仅在理论上，而且在实际应用方面都具有重要的价值。那 么什么是分形呢? 迄今为止，分形还没有严格的数学定义，只能给出描述性的定义。粗略地说， 分形是对没有特征长度但具有一定意义的自相似图形和结构的总称，此处的特征 长度是指所考虑的集合对象所包含的各种长度的代表者。分形可以分为规则分形 和不规则分形： ( 1 ) 规则分形：大多数分形在一定的标度范围内不断放大其任何组成部分，其 不规则程度都是一样，即具有无限的膨胀和收缩对称性，这个性质称为比例自相 似性；按照统计的观点，其任一局部经平移、旋转、缩放变换后与其它任意部分 相似，像这种具有严格自相似的分形称为规则分形。实际观察到的分形的最小组 成部分是有限的，就是说标度的下限应大于实际分形的最小组成部分。当然，任 何有限分形图形的标度的上限应小于等于整个图形的尺寸。 ( 2 ) 不规则分形：自然界许多事物所具有的不规则性和复杂性往往是随机的， 如蜿蜒曲折的海岸线、变换无穷的布朗运动轨迹等，这类曲线的自相似性是近似 的或统计意义上的，这种自相似性只存在于标度不变区域，超出标度不变区域， 自相似性不复存在，这类曲线为不规则分形。 1 9 8 2 年m a n d e l b r o t 给出分形的一个尝试性的定量刻画： 定义2 1 如果一个集合在欧氏空间中的h a u s d o r f f 维数d h 严格大于其拓扑 维数珥，则称该集合为分形集，简称分形。 此定义强调维数，其中的h a u s d o r f f 维数一般不是整数。该定义不合理，因 为它把一些明显应为分形的集合排除了。1 9 8 6 年，m a n d e l b r o t 又提出了一个实用 的定义： 定义2 2 组成部分以某种方式与整体相似的形体叫分形。 上述定义都不够精确和全面。英国数学家k f a l c o n e r 认为分形的定义应不寻 求分形的确切定义，而是寻求分形的特征。一般地，称集f 是分形，即认为它具 9 i f s 不动点连接技术研究 曼量曼曼皇曼! ! 曼曼皇曼曼曼曼曼曼曼曼i | 1i i _ ii 量曼皇曼皇曼曼曼! 曼曼皇! 曼曼皇曼曼曼曼! 曼皇! 曼曼曼曼曼曼曼曼曼曼曼曼量! 曼曼曼曼曼皇舅 有如下性质： ( 1 ) f 具有精细的结构，即在任意小的尺度下，总是有复杂的细节。 ( 2 ) f 是不规则的，以至于它的整体和局部都不能用传统的几何语言来描述。 ( 3 ) f 通常具有某种自相似性，可能是近似的或统计的。 (