基于IFS分形树的VC++实现

摘要：迭代函数系统（IFS）是构造分形集的核心技术，本文采用IFS方法 和随机迭代方法构造出树木的模型，并在vc++6.0的环境下，实现了分形树的模拟。

关键词：迭代函数系统；分形；树木模拟;随机函数

中图分类号：TP311文献标识码：A 文章编号：1009-3044(2008)15-20000-00

Realiztion of fractal Tree Based on IFS Using vc++

XIAO Hai-Rong，REN Min-Hong，GUO Tian-Yin

(Deptment of Computer ,Shaanxi University of Technology ,Hanzhong 723003)

Abstract:Iteration function systems is a key technology of constructing fractal images.in this paper, Tree modeling is configured using ifs and random funtion method ,and realizes fractal tree simlation in vc++6.0

Key words:Iteration function systems（IFS）;fractal; tree simulation；random functiom

1 引言

迭代函数系统（IFS）是绘制分形图形的重要方法之一，是分形几何学的重要分支。其理论和方法为计算机模拟自然现象的真实感图形提供了一个有力的工具，特别是对自然景物的计算机模拟方面具有明显的优势。本文首先介绍了IFS，然后提出了带概率的IFS的分形树的仿射变换模型，并通过VC++编程，实现了用IFS迭代方法绘制的分形树。

2 IFS基本原理

2.1 分形图的自相似性

众所周知，自相似性或自仿射性是分形的最重要的特征。即将局部放大后与原图是相似的，局部是整体的一个小复制品，只不过存在一些不等比例变换和扭曲变换等，而迭代函数系统（IFS）是以仿射变换为框架，根据几何对象的整体与局部具有自相似性结构，经过迭代而产生的。为说明问题，引入下面的定义：

定义：变换W：R2R2具有形式 xhr01.tif

式中abcdef为实数，则称W为一个二维仿射变换，当X∈R2时，常写成W(X)=AX+t其中xhr02.tif ,且Oad-bcO

2.2 IFS的吸引子

由于分形图具有自相似性，因此可以找到N个压缩仿射变换Wi(i=1,2……N)使得

W(B)= xhr03.tif,其中W(B)是一幅分形图形，Wi(B)是由压缩仿射变换确定的子图。

定理：一个IFS由一个完备度量空间（X，d）和一个有限压缩仿射集Wn:XX,n=1…..N组成，用IFS{X;Wn,n=1……N}表示，则变换W定义为：W(B)=xhr03.tif,B∈X(X)，则W是完备度量空间（X(X),h(d)）上具有压缩因子s的压缩映射，即h(W(B),W(C))≤sh(B,C),B,C∈X(X)且存在惟一的不动点A∈X(X),满足A= W(A)= xhr04.tif,并对任意的B∈X(X)，A= xhr05.tif Wn(B),则A被称为IFS的吸引子，该吸引子就是一个分形。

2.3 （Barnasley拼贴定理）

对于一个给定的双曲迭代函数系（IFS），可用计算机生成它的吸引子，从而可得到许多漂亮的分形图，如何寻找适当的IFS码，使其吸引子就是或近似是该图形，本文采用拼贴的方法逼近目标图形，以获取仿射变换Wi及其参数。拼贴定理如下：

设{X;W1……Wn}是一个双曲迭代函数系，压缩因子s

3 IFS分形树模拟算法

3.1 带概率的IFS

基于IFS算法生成树木的方法是根据拼贴定理，对已有的树木图像用有限个该图形的压缩仿射变换子图去覆盖它，并允许重叠，仿射变换族控制着图形的结构和形状，在仿射变换Wn中，每一个仿射变换被调用的概率P不一定相同，即落入图像各个部分中点的数目不同，因此为每一个压缩仿射变换都分配一个被调用的概率P，以减少工作量。则IFS成为带概率的IFS，形式为{X;Wi;Pi,i=1……n}，其中p的选择需满足Pi>0, xhr07.tif=1，一般Pi的取值取决于仿射变换子图的面积，子图面积越大，落入该子图的点的数目越多,所对应的仿射变换系数被选中的概率也就越大，而实际的图形可能不规则，在求取面积时，用计算机实现时可以对仿射子图填充以不同的颜色，然后根据屏幕上某种颜色的象素点的个数来求面积，任意图形经仿射变换后，面积将为变换前的Oad-bcO倍,当然，考虑到误差，最终要对概率P进行规一化，xhr07.tif＝1。

3.2 分形树IFS码的获取

要获得分形树的IFS码，由拼贴定理可知，只要在图形空间中找到一组压缩仿射变换的参数，使给定图形在改组压缩仿射作用下形成的子图拼贴与给定图形相近，IFS所有的参数就是要获得的该图形的IFS码。如何获得所需的IFS码是分形模拟的重点，也是一个难点。本文采用锐角三角形的方法，根据分析图形的相似性，在整体和局部图上取一些相对应的特征点，通过三组对应点求解线性方程组，就可以求出一个仿射变换参数。我们把原树图像分为四部分，分别为主干，上支，左右支，最终求得的分形树的IFS码如表1。

3.3 分形树的吸引子算法

利用IFS生成分形树的过程是对初始树的图像按照已知概率选择函数，而实施的一种迭代变换，本文采用随机迭代算法，在该算法中采用了带概率IFS，IFSP为{X;Wi;Pi,I=1,2……N},通过VC++提供的随机数rand(),将当前系统时间作为随机种子，用随机生成的概率决定选择第k个变换 ，不断迭代得到新的x,y坐标，并通过新坐标绘制点，迭代产生其图片。具体算法步骤如下：

①取初始点(x0,y0)及总的迭代次数n。（初始点一般取为仿射变换的不动点）

②生成随机数R，并使R的值为0―1;

③为每一个wi分配相应pi;

④判断随机数落入哪一个空间，调用相应的wi的ifs码值，赋给相应的参数；

⑤把wi作用到（x0,y0）上得到新点（x1,y1）,并且在（x1,y1）处画一点；

⑥如果画的点数小于指定的点数，将本次计算的值作为下一次的x和y值参加计算，循环执行②到⑤，直到完成迭代次数。

3.4 运行结果

本文使用VC++6.0,通过编程实现分形树的构造与模拟，在执行过程中，随着迭代次数的增加，随机落下的点数将逐渐显现处分形树IFS的吸引子。生成的分形树序列如图1所示。

4 结束语

本文在vc++下采用IFS算法绘制分形树，从理论上来讲，吸引子与概率p的选择无关，但在实际绘图是p 起到很重要的作用，控制概率，就是控制拼贴图形各部分落点的密度，使图形在有限步迭代终止时，显示出泷淡虚实的不同层次。而迭代次数的选取没有一个统一的指导理论，只能靠实验来反复进行，直到生成一个清晰的分形树为止。如果分析图已经形成，迭代次数增加，这样使得生成的分形图形的时间大大延长，降低了算法的效率。因此如何确定迭代次数的下限，提高算法效率，是需进一步研究的问题。

参考文献：

[1] 曾文曲，王向阳等，分形理论与分形的计算机模拟[M].沈阳：东北大学出版社，2001.

[2] 孙博文，分形算法与程序设计――vc++实现[M].北京：科学出版社，2004.

[3] 沙震，分形与拟合[M].杭州：浙江大学出版社，2005.

收稿日期：2008-04-13

陕西理工学院科研基金项目(SLG0620)

作者简介：肖海蓉，女，讲师，研究方向：数据库技术及应用和图形图像处理；任民宏，男，副教授，研究方向：计算机图形图像处理和信息管理；郭天印，男，教授，研究方向：人工智能与算法。

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”