迭代函数系统在自然景物模拟中的应用.doc

迭代函数系统在自然景物模拟中的应用 学号：
迭代函数系统在自然景物模拟中的应用

作者： 指导老师：

摘要：本论文首先介绍了分形的由来，包括分形艺术以及它的特征和应用。接着简要论述了自然景物模拟的方法，重点介绍了迭代函数系统对自然景物进行模拟的方法，并通过举例来分析具体的实现步骤！在Windows XP环境下，利用微软公司提供的Visual C++6.0开发工具，编程实现了一个简单的分形艺术图形生成软件。
关键字：分形艺术的由来，分形艺术图形，生成算法，迭代函数系统，IFS码对自然景物的模拟，牛顿迭代法之分形艺术图形软件介绍

1 分形的由来
1.1分形艺术
分形艺术是科学中的艺术，也是艺术中的科学，分形艺术不仅表达着艺术形式和外观，而且表达着生成这种艺术的科学知识，分形艺术广泛的运用在书籍装帧、广告、装饰、服装设计、影视等领域。从狭义的角度讲，分形艺术是指根据分形几何的科学原理，通过计算机软件创造出来的具有审美功能的图形，动画等艺术作品；从广义的角度讲，凡是具有分形思想的艺术作品都可称之为分形艺术，狭义的分性艺术可以划归电脑艺术（数码艺术）门类，而广义的分形艺术也包括通过手工绘制而成的作品。在艺术史中，广义的分性艺术早已存在，如日本艺术家葛饰北斋的作品《神奈川的巨浪》就是一例，此外一些古建筑艺术和少数民族的装饰艺术中也有类似分形的图案。
分形艺术对艺术最直接的贡献就是带来了新的造型语言及表达方式，分形艺术借助计算机技术构造复杂的几何图形并“诗意”的处理这些图形，表现出新的风格，开辟了视觉传达的新领域，分性艺术这种不同于传统绘画艺术的创作方式，也打破了“艺术只属于艺术家”的传统一是，史任何人都有可能创作自己的艺术作品。
分形几何提供了用于描述一些不能用传统的欧几里德几何描述的复杂几何图形的一种方法。是现代数学的一个重要内容，也是研究和处理自然与工程中不规则图形的强有力的工具，他的应用几乎设计自然科学的各个领域。
1.2分形艺术的特征
分性艺术不仅蕴含了传统的美学思想，而且还产生出许多新的美学特征，首先，分性艺术作品中除了对称性中包含的传统的上下，左右及中心对称等观念之外，它的自相似性又揭示了一种新的对称性，即局部与整体的对称，在欣赏分形艺术作品时，如果我们放大某件作品的局部，就会发现这些局部图形与整体的图形史相似的，其次，分形艺术作品中的线条美也具有新的内涵，以往的绘画，雕塑等一书中，线条主要有直线，圆弧线、波状线、蛇形线。在数学上这些线条都是可微分的。然而，在分形艺术作品中，线条是十分复杂和不规则的，常会使用皮亚诺曲线、希尔伯特曲线、柯赫曲线等类曲线。这类曲线通常被称为“妖魔曲线”。它们具有以下三个特征：
1、能够填充整个空间；
2、十分曲折，在数学上连续但不可导；
3、具有自相似性，尽管这些曲线十分曲折和奇异，但他们的成长却十分简单，这便是分形艺术中线条的独特性；无序中蕴含着有序，复杂中蕴含着简单，变化中蕴含着统一，最后分形艺术美的最大特征就是奇异美，分形艺术作品中的图形又很大的随机性和任意性，我们几乎很难在众多的分形艺术图形中找到完全相同的图形。
较之其他艺术形式来说，分形艺术的作品风格奇特，神奇美丽，变化莫测。此外，这类艺术品的典范都有一个共同的特征即没有特定尺度，因为他具有每一种尺度，观察者从任何距离望去都看到某种赏心悦目的细节，当你走近时，它的构造就在变化，展现出新的结构元素。分形艺术的这种具有强烈的时代感，美令人耳目一新。
1.3 分形艺术的应用
分形就在我们身边，我们身体中的血液循环管道系统、肺脏气管分岔过程、大脑皮层、小肠绒毛等等都是分形；参天大树、连绵的山脉、奔涌的河水、曲折的海岸线、漂浮的云朵等等，也都是分形。分形在自然界中太普遍了，用分形语言去描绘大自然丰富多彩的面貌，应当是最方便、最适宜的。由分形而来的分形艺术离我们也并不遥远，普通人也能体验分形之美。
目前，分形艺术主要研究领域有：
1、 分形艺术图形的数学建模，这是生成各种不同图形的基础；
2、 分形艺术图形的着色、融合和特效处理算法，可以决定生成的图形的精美程度；
3、 分形艺术图形的应用，目前，分形艺术图形主要应用在电影，印刷，装饰以及信息的加密等领域中，我们还需要继续拓展它的应用范围；
4、 科学计算的可视化，通过分形图形把某种不可见的物理、化学过程以直观的形式呈现出来，加深人们的理解。
从当前分形艺术图形的发展状况来看，分形艺术图形有着广阔的发展前景，也将能产生巨大的经济效益，并且已经有了许多的成功实例。目前分形艺术已在以下方面得到了成功的应用：
1、书籍装帧、杂志封面设计；
2、广告业，作为素材制作新颖的广告画面；
3、各种装饰艺术，如大型壁画、扑克牌、挂历、马赛克瓷砖画、居室装饰画等；
4、纺织工业，如文化衫图案、装饰布料设计、刺绣花样设计、真丝方巾印花、时装设计等 。

2 分形艺术图形
2.1分形艺术图形生成
分形(fractal)最早是在20世纪70年代由美国数学家Madelbrot在其《自然界中的分形几何》一书中提出的。他是想用此词来描述自然界中传统欧氏几何学所不能描述的一大类复杂无规的几何对象,例如,蜿蜒曲折的海岸线、起伏不定的山脉、粗糙不堪的断面、变幻无常的浮云、九曲回肠的河流、纵横交错的血管、令人眼花缭乱的满天繁星等。它们的特点是,极不规则或极不光滑。
分形艺术图形的生成过程
生成分形艺术图形的流程如图1所示，首先在复平面（水平轴为实轴，垂直轴为虚轴）上选取一点，然后选择特效处理方案，再进行牛顿迭代和着色，进而生成分形艺术图形。

图1分形艺术图形生成过程
2.2分形与欧氏几何图形
2.2.1 分形的主要有三个特性
(1)自相似性:即局部与整体的相似,或者说,局部是整体的缩影。
(2)自仿射性:即局部到整体是在不同方向上的不等比例的变换。
(3)精细结构:即在任意小的比例尺度内包含整体。
2.2.2 分形与欧氏几何图形的区别
(1)欧氏图形是规则的,而分形是不规则的,即欧氏图形一般是逐段光滑的,而分形往往在任何区间内都不具有光滑性。
(2)欧氏图形层次是有限的,而分形从数学角度上讲,层次是无限的。
(3)欧氏图形一般不会从局部得到整体的信息,而分形往往可以从局部“看到”整体。
(4)欧氏图形越复杂,其背后的规则越复杂,而分形图形,看上去十分复杂,但背后的规则却相当简单。
2.3 分形图形的生成算法
常采用的分形图生成算法有L-系统、迭代函数系统和逃逸时间算法。通过这些算法可以生成大量美丽、奇异的图案,也可用于景物模拟。
寻求能准确地描述客观世界中各种现象与景观的数学模型,并在计算机中逼真地再现,一直是计算机图形学的一个研究热点。然而实际自然景物如烟雾、植物、水波、火焰等,很难用欧式几何模型完全描述,它们具有极不规则或极不光滑的特点。但不少景观的描述曲线具有自相似性(self2sim ilarity)、长度(面积或体积)不确定、维数不确定等几大特点,这类具有自相似特性的曲线在数学上被定义为分形(fractal)。分形的自相似性在植物模型中表现为几何对象整体(树)与局部(分枝)之间具有自相似结构的特点。迭代函数系统(IFS)将树与分枝通过仿射变换建立自相似性,经过多次迭代产生分形图形,实现描述自然景观的目的。在迭代函数系统中,通过求取仿射变换参数来定义IFS码,它可以描述各级枝条的偏转角度、锥度、螺旋状扭曲以及子干和母干之间的比例尺度,通过多次迭代完成对树木的递推描述,从而构造树木形体。本文分析迭代函数系统IFS码产生原理,一方面加入随机因子,生成风格独特的分形图。另一方面适当控制IFS码,对两个分形图形的IFS码进行插值,达到两个分形图渐变的动画效果。另外通过增加IFS码,对分形图进行变换,得到多个分形图案,可逼真模拟森林、草地等自然景观。
3 迭代函数系统
迭代函数系统与拼贴定理:
Barnsley和Stephen提出的迭代函数系统的基本思想是:认定几何对象的全貌与局部,在仿射变换的意义下,具有自相似结构[1,2]。其物理意义是把原图分解为几部分,每一部分都看作原图在不同仿射变换下的复制品,即任何分形图形都可以看成是通过一系列仿射变换得到的小复制品拼贴而构成。
3.1　迭代函数系统
迭代函数系统(Iterated FunctionSystem,IFS)是分形理论的重要分支,是将待生成的图像看成是由许多与整体相似的(自相似)或经过一定变换与整体相似的(自仿射)小块拼贴而成。
定义1　设函数d为衡量集合X中任两点x和y距离的度量,且所构成度量空间(X,d)是完备的。在该完备度量空间(X,d)上的某变换f:X→X满足d(f(x),f(y))≤sd(x,y),Πx,y∈X,则称该变换为压缩映射,其中常数0≤s<1为压缩因子。
定义2　完备度量空间(X,d)上定义N个有限压缩映射W n:X→X,n=1,2,…,N,对应的压缩因子为sn。这些具有不同压缩因子的压缩映射就构成了一个迭代函数系统,可以简记为IFS{X;W n,n=1,2,…,N},系统的压缩因子定义为最大值,s=m ax{sn:n=1,2,…,N}。
在迭代函数系统中,压缩映射W n的出现概率0<Pn<1称为伴随概率,迭代函数系统的伴随概率满足完备性,即 。这样所有压缩映射和对应的伴随概率确定了整个系统的迭代过程,因此称集合{(W n,P n),n=1,…,N}为迭代函数系统的IFS码。
定理1　设有压缩因子为s的迭代函数系统IFS{X;W n,n=1,…,N},定义X的全体非空紧子集空间H(X)上的变换W：H(X)→H(X)为W(B)=,。则该变换W(B)是分形空间(H(X),h(d))上具有压缩因子s的压缩映射,其中h(A,B)为H(X)上两点的H au sdo rff度量,定义为h(A,B)=d(A,B)∨d(B,A),ΠA,B∈H(X),其中符号∨表示m ax,d(A,B)=m ax{d(x,B),x∈A}为集合间的度量,d(x,B)=m in{d(x,y),y∈B}为点与集合之间的度量。该压缩映射的唯一不动点q∈H(X)满足q=,且q=limW(B),,W指变换W的前向n次迭代。不动点q被称为IFS的吸引子[3]。
定理(压缩映射不动点原理)
设{X;w1,w2,…,wn;c}是(X,d)上的IFS,则:
(1)由下式定义的变换W:F(X)→F(X),即,是完备度量空间(F(X),ρ)上的压缩映射,其压缩因子也是c,即:h(W(A),W(B))≤cρ(A,B);
(2)压缩变换存在唯一的不动点(不变集)p∈F(X),满足p=W(p)=,且不动点可以通过迭代而得到,即,其中,Wn(B)=W(W(n-1)(B))在迭代函数系统IFS{X;w1,w2,…,wn}中通常用线性压缩仿射变换来表示压缩映射,如:对于平面上的仿射变换
wi:R2→R2,有下列形式:Wi=+=AX+b,i=1,2…n,其中ai,bi,ci,di,ei,fi,(x,y)R, ,线性变换矩阵A=,代表旋转、比例、反射变换,矢量代表平移变换,通过调整变换矩阵A与平移矢量b中各参数值可以对分形图实施各种几何变换来构造分形图。
对于一个比较复杂的图形,可能需要多个不同的仿射变换来实现,仿射变换族{wn}控制着图形的结构和形状,由于仿射变换的形式是相同的,所以不同的形状取决于仿射变换的系数。另外,仿射变换族{wn}中,每一个仿射变换被调用的概率不一定是等同的,即落入图形各部分中点的数目不一定相同,这就要引进一个新的量,即仿射变换w被调用的概率p。从而6个仿射变换系数(ai,bi,ci,di,ei,fi)和一个概率pi便组成了IFS算法最关键的部分———IFS码。
3.2　拼贴定理(collage theorem)
定理2　在完备度量空间(X,d)上给定L∈H(X)和Ε>0,选定一个压缩因子为0≤s<1的迭代函数系统IFS{X;W n,n=0,…,N},以至于h〔L,〕≤,则h(L,A)≤,
其中A是这个IFS的吸引子,等价的h(L,A)≤〔L,〕,。
吸引子就是一个分形,是程序生成分形所依据的原理。拼贴定理是迭代函数系统理论的核心,它指出了迭代过程中容许的误差范围,以及应该选取合适的压缩映射W来降低拼贴误差。从上述两个定理可知,如果以IFS码来建模,那么用极少量的代码就可以绘制出非常复杂的图形效果。换言之,一个分形就可以用一个IFS码表示,这样只需反复作压缩映射W,就可以逼近分形。
IF S码的求取
在二维迭代函数系统中,考虑二维欧氏空间的压缩映射集W n:R2→R2,变换前点U用齐次坐标表示为U=[x　y　1]T,变换后的齐次坐标为U′=[x′　y′　1]T,W为二维齐次坐标的变换矩阵[5],

分形图形生成的关键在于IFS码的求取,IFS码的求取依据拼贴定理完成,其算法可为确定性算法和随机性算法两种。按照式(1)决定的6参数仿射变换称为确定性算法,是把一个图形分成若干拼贴子图,如图1(b)所示的W 1、W 2、W 3、W 4等,每一部分都可看作是原图在不同仿射变换下的复制品,这若干部分拼贴起来覆盖原图形。而随机性算法是在原来的IFS中增加一组伴随概率Pn,也称为带概率的迭代函数系统。这样,W n的6个仿射变换系数(a,b,c,d,e,f)和其伴随概率Pn便构成了IFS算法最关键的部分——IFS码。图2演示了一片蕨叶IFS码的生成过程。

（a）原始矩阵 (b) 第一次迭代

(c) 第二次迭代 (d) 第n次迭代

图2蕨叶IFS的生成过程

设蕨叶的IFS为{R2;W 1,W 2,W 3,W 4},原始矩阵经过仿射变换,生成了枝W 1、左叶W 2、右叶W 3、中间片W 4等4个拼贴子图,这决定了蕨叶有4个IFS码。原始矩阵(图2 (a))中3点a、b、c分别对应图2 (b)的左叶(a2,b2,c2)、右叶(a3,b3,c3)、中间片(a4,b4,c4)的3点,将其值分别代入式(1),求取它们的IFS码,具体参数见文献。
4　IFS码对自然景物的模拟
4.1　随机因子对图形的影响
每个IFS码使用一个随机数,可控制其在随机迭代中被选中的概率(控制绘制该部分点的数目[6])。调整左右树枝与树干的随机因子,如Pa=(0.5,1.5,4,4),Pb=(2.5,3.5,2,2)可生成不同风格的树(图3)。

图3 随机因子对图形的影响

图4 多个分形图的形成
4.2　多个分形图的生成
在图2分形树的IFS码加入一个IFS码(0.75,0,0,0.75,0.9,0,1),这个码是对第一个分形树作仿射变换,生成一排分形树(图3(a)),这样就可以由一个分形树生成一片森林。增加两个IFS码(0.65,0,0,0.75,0.5,0.1,0.5)和(0.65,0,0,0.75,0.1,-0.4,0.5),也是对第一个枫叶作仿射变换,通过随机调整分形位置,可以生成一片灌木丛(图4 (b))。
4.3　IFS动画设计
定理3　设(X,d)是度量空间,{X;W n,n=0,…,N}是一个(带凝聚的)IFS,压缩因子s=max{sn:n=0,1,…,N},如果每个W n都连续依赖于参数t∈T,T是紧度量空间,则吸引子A(t)∈H(X)就按H au sdo rff度量h(d)连续地依赖于t∈T[3]。
从定理3可知,W n中的变量是连续的,给该变量连续赋值,其生成图形就会连续变形,从而形成动画。
首先将公式(1)化为

其中:r1、r2分别为x、y方向压缩因子;θ、γ为绕x、y轴逆时针旋转角度;e、f为x、y方向上的平移量。

图5 风吹的树
为能得到一棵在风中摇曳的树,根据风力的实际影响情况,在IFS模型中加入风力控制参数pow f。令Η=Η+pow f,Υ=Υ+pow f。这样,不断调整pow f值,就形成树在风中摇曳的动画。本程序中pow f1=(1.0,0.45,0.45,0.10)时为逆时针吹风,对上面分枝W 1影响最大,对树干W 4影响最小,与现实中风力对树木的影响相吻合,如图5所示。当pow f2=(-1.0,-0.45,-0.45,-0.10)时,则为顺时针吹风。
4.4　IFS码之间的变换
若已知两图形的IFS码,通过插值,可使一图形渐变为另一图形。作为变换中的两个源图形,当其IFS数相等时,找出其IFS码渐变的增量,将这一增量加到IFS码中,便可找到中间的IFS码。图6演示了一片枫叶变成一棵大树的过程。
一般情况下,两个源图形的IFS码个数通常是不等的。图7是3个IFS码变换成4个码的演变过程,在实现过程中,通过复制少码图形其中的一组IFS码,从而使自身达到多码图形的IFS码个数,接下来修改少码图形的IFS码中的概率,这种复制方式,只会使被复制的那组IFS码对应的仿射变换部分在生成的时候会显得深色一点,形状不变,最后用插值变换实现演变。

图6 同码数之间的变换

图7 不同码数之间的变换

4.5 IFS码应用举例
下面三个图均用IFS方法生成,其IFS码如表1、表2、表3。

菊花图 树 树叶

i
Ai
Bi
Ci
Di
Ei
Fi
Pi
1
0.745456
-0.4590901
0.400061
0.887121
1.400279
0.091072
0.912676
2
-0.424242
-0.065152
-0.175758
-0.218182
3.809567
6.741476
0.087325
表1 菊花图的IFS码

i
Ai
Bi
Ci
Di
Ei
Fi
Pi
1
-0.04
0
-0.19
-0.47
-0.12
0.3
0.25
2
0.65
0
0
0.56
0.06
1.56
0.25
3
0.41
0.46
-0.39
0.61
0.46
0.4
0.25
4
0.52
-0.35
0.25
0.74
-0.48
0.36
0.25
表2 树的IFS码

i
Ai
Bi
Ci
Di
Ei
Fi
Pi
1
0
0
0
0.16
0
0
0.01
2
0.85
0.04
-0.04
0.85
0
1.6
0.85
3
0.2
-0.26
0.22
0.22
0
1.6
0.07
4
-0.15
0.28
0.26
0.24
0
0.44
0.07
表3 树叶的IFS码

5 牛顿迭代法之分形艺术图形软件介绍
本论文利用微软公司提供的Visual C++6.0集成开发环境，在Windows XP环境下编程实现了一个简单的分形艺术图形生成系统FractalNewton。它的操作简单、快捷，能够快速生成多种分形艺术图形，其工作界面如图8所示：

图8 FractalNewton的工作界面
点击鼠标右键弹出下拉菜单，菜单功能如下表所示：

表4 菜单功能列表
子菜单序号
菜单名称
菜单功能
1
关于
对该软件进行简单的说明
2
复制到剪贴板
复制生成的分形艺术图形到剪贴板
3
另存为BMP文件
保存生成的分形艺术图形到BMP文件
4
保存参数文件
保存当前图形的到参数文件中
5
打开参数文件
读取参数文件以生成分形艺术图形
6
参数设置
打开参数设置对话框，以生成不同的分形艺术图形

用户可以通过以上的第6项操作，设置改变不同的参数，生成多种分形艺术图形。参考实例如图9至16所示：

图9：参数设置对话框 图10：图9参数设置对话框对应的图形

图11：参数设置对话框 图12：图11参数设置对话框对应的图形

图13参数设置对话框 图14 图13参数设置对话框对应的艺术图形

图 15 参数设置对话框 图16 图15参数设置对话框对应的艺术图形

结束语
分形几何提供了用于描述一些不能用传统的欧几里得几何描述得复杂几何图形得一种方法。是现在数学得一个重要内容，也是研究和处理自然与工程中不规则图形得强有力工具，它的应用几乎涉及自然科学得各个领域。计算机艺术是随着软件得发展而新兴得艺术形式。计算机图形学中分形研究得深入发展和计算机在艺术设计中得应用，分形几何使我们可以用简单得计算方法得到复杂图案。本文简要分析了迭代函数系统在自然景物模拟中得应用。

致 谢
在本课题的研究过程中和论文撰写中，我学会了分形艺术的基础理论以及迭代函数系统的初步应用，并以此完成了此次论文，在此非常感谢老师的悉心指导和大力帮助！
老师不仅有广博的知识，精通Visual C＋＋6.0的应用，并对我所设计课题具有丰富的经验，在我的设计过程中，老师以诲人不倦的精神，严谨的治学态度，缜密的思维和敏锐的洞察力，指导我如何设计课题，如何撰写论文且帮我的论文构建了一个提纲，并对我论文进行了认真的批阅，这些都使我受益匪浅。老师的人格魅力和敬业精神以及丰富的知识都令我非常钦佩，在此我表示衷心的感谢！在毕业设计的过程中，老师和同组其他同学在相关问题和资料上也给予了大力的帮助，可以说没有老师和同学们的帮助，我的毕业设计是不能够顺利完成的，最后衷心的说一声：谢谢你们!

参考文献
[1]林夏水.分形的哲学漫步[M].北京:首都师范大学出版社,1999.
[2]孙博文.分形算法与程序设计:Visual C++实现.北京:科学出版社,2004.
[3]石其江.实现自然景物模拟方法[J].软件报,2005(43).
[4]分形频道2003版.
[5]潘金贵,艾早阳.分形艺术程序设计[M].南京:南京大学出版社,1998.
[6]M.F.Barnsley,S.Demko.Iterated Function System and the Global Construction of Fractals[J]. R.Soc.Lond.Ser. A Math.Phys.Eng.Sci.1985(399)
[7]刘华杰.分形艺术[M].长沙:湖南电子音像出版社,1997

Abstract: In this paper, the basic knowledge of fractal was firstly introduced. Then the steps of producing fractal artistic pictures were explained and emphasized. Several important algorithms were mainly involved in the process of producing fractal artistic pictures, which include special effective process, Newton iterative algorithm, and coloring algorithm. A simple fractal artistic picture software is developed using Microsoft Visual C++ 6.0, which works under Windows XP.
Keywords: Fractal, Fractal Artistic Pictures, Special Effective Process, Newton Iterative Algorithm, Coloring Algorithm

第 13 页 共 13 页