基于IFS的Sierpinski三角形的生成及其推广

胡海龙， 刘树群

（1. 浙江林学院理学院，浙江 临安 311300；2. 兰州理工大学计算机与通信学院，甘肃 兰州 730050）

20世纪70年代美籍法国数学家曼德勃罗特(Benoit Mandelbrot)创立了分形几何学，分形的最重要特征是不规则性和无限精细自相似结构，因此分形可以很好的用来定义和表达传统欧氏几何所不能表达的几何形体。

迭代函数系统(Iterated Function System，简记为IFS)是生成分形的典型方法，可以生成大量的具有自相似结构的分形图形。但其瓶颈问题是IFS码的获取以及其吸引子的自相似性而给人“千篇一律”的感觉。有些学者提出了根据已知的 IFS码通过加入某些参量再进行调整[1-3]或者寻找新的 IFS建模技术[4-5]来生成新的分形图形的方法，宋广为等提出了基于迭代函数系统的地纹激光图案生成算法[6]；为了得到自然、逼真的分形图形，文献[7-8]中分别提出了L-系统与IFS相融合的方法和分形图形的合成方法。

Sierpinski三角形是典型的分形图形，本文阐述了其生成原理，并对其进行生成元形状及调整IFS变换两方面的推广，得到了吸引子与生成元形状无关的结论和由已知的IFS经过适当的调整得到新的IFS，同时生成大量自然、逼真、多样的分形图形。

1 仿射变换及IFS理论

定义1（仿射变换）变换 ω :R2→R2形 式 为 ω (x,y)=(ax+by +e,cx+dy+f )，称为二维的仿射变换，其中 a , b,c,d,e,f 是实常数。通常也写成 ω ( X ) =AX +t形式，其中

矩阵A确定了相对于原点的线性变换：缩放变换，旋转变换，镜像变换以及错切变换。t是列向量，确定了平移变换。

当且仅当矩阵A的谱半径 rσ(A) ＜ 1 时变换为压缩映射。关于分形空间的详细理论可以参看文献[9]。图1显示了仿射变换的效果。

图1 仿射变换ω

定理 2（吸引子定理）一个迭代函数系统是由完备距离空间 (X,d)和在其上定义的一组分别具有压缩因子0 ≤ sn＜1的有限个压缩映射ωn:X →X,n=1,2,…,N组成，用IFS { X ; ωn, n =1 ,2, … ,N}表示。 则变换ω定义为

是完备度量空间 ( H (X ) , h(d ))上具有压缩因子s的压缩映射，即 h ( ω ( B ) ,ω ( C ))≤s⋅ h( B , C ) ,∀ B , C ∈ H ( X)， 且A∈H( X )，称A为 IFS的吸引子，一般来说，该吸引子就是分形[10-11]。

2 Sierpinski三角形生成原理

本文采用确定性迭代算法生成 Siperpski三角形，其基本原理为：由 R2空间中一个子集B出发，经过仿射变换ϕ的依次作用，产生一个迭代结果。各仿射变换再分别作用在上一次的变换结果上，如此反复迭代，其极限集合即为IFS吸引子。

生成 Sierpinski三角形的 IFS及其过程为：( H ( R2),h( Euclidean))中的IFS { R2;ω1,ω2, ω3} ，其中

令E0为 [ 0 ,1]× [ 0,1]的矩形，如图2(a)，迭代函数系统的 3个变换作用在E0上，得到E1=ω1(E0)∪ω2(E0)∪ω3(E0)，如图2(b)，然后 ω1, ω2, ω3再分别作用在E1上，

得到 E2=ω1(E1)∪ω2(E1)∪ω3( E1)，如图2(c)，继续迭代下去，得到各次迭代结果如图2(d)～(g)，最终得到此IFS的吸引子为图2(h)。

图2 IFS 吸引子生成示例（Sierpinski三角形）

3 推 广

推广1 生成元形状的改变

IFS同第3部分所述，而生成元不再为四边形（正方形），在此，将其推广为点、线段、三角形及圆，生成的分形图形分别为图3(a)～(e)。如果迭代次数足够大，其吸引子均为图2(h)所示。

由图可以看出，对于一个IFS来说，只要变换是收敛的，其吸引子就与生成元形状无关。

图3 生成元形状的推广

推广2 对IFS的变换适当调节，得到新的IFS及吸引子

以 [-1, 1]向上的有向线段为初始集合，如图4(a)，用有向线段表示仿射变换，IFS及其吸引如图4(b)所示，其中IFS由3个仿射变换组成，从上到下从左到右依次记为ω1,ω2, ω3，吸引子为Sierpinski三角形。

图4 调整IFS变换得到新的IFS及其吸引子

（1）调节一个变换：保持ω2,ω3不变，调节ω1，得到IFS1及其吸引子如图4(c)；

（2）调节两个变换：保持ω1不变，调节ω2,ω3，得到 IFS2、IFS3、IFS4及它们的吸引子如图4(d)、(e)、(f)；

（3）调节3个变换：调节 ω1,ω2, ω3，得到IFS5、IFS6及其吸引子如图4(g)、(h)所示。

从图4可以看出，适当调节Sierpinski三角形的IFS变换，就可以得到新的IFS，其吸引子有的还保持Sierpinski三角形的影子（如图4(c)、(d)）；有的完全不同于Sierpinski三角形，可以得到形态各异，生动逼真的自然景物及日常用品，如树叶、扫帚、树冠和盔甲等。

4 结束语

本文叙述了基于IFS理论的Sierpinski三角形生成原理，并对其进行生成元形状及其IFS调整两方面的推广，并运用此方法进行了大量的计算机分形图形实验，得到了两个结论：① 吸引子与生成元形状无关，② 由Sierpinski三角形的IFS可以得到新的 IFS，由此能生成丰富多彩的分形图形。

[1]孙 炜, 陈锦昌. 应用迭代函数系统获得分形图形的简易方法[J]. 工程图学学报, 2001, 22(3):109-113.

[2]章立亮. 一类全不连通分形图的构造[J]. 中国图象图形学报(A版), 2003, 8(7): 744-747.

[3]章立亮. 一种带自动参量的迭代函数系统[J]. 工程图学学报, 2006, 27(2): 171-175.

[4]张亦舜, 杨 扬. 构造IFS吸引子的新算法[J]. 中国图象图形学报(A版), 2002, 7(11): 1161-1164.

[5]魏小鹏, 周运红, 张建明, 等. 自然景物IFS建模技术研究[J]. 工程图学学报, 2003, 24(4): 103-109.

[6]宋广为, 徐 晨, 狄震宇. 一种基于分形的地纹激光图案生成算法[J]. 微计算机信息, 2006, 22(13):253-254.

[7]李庆忠, 韩金姝. 一种 L-系统与IFS相互融合的植物模拟方法[J]. 工程图学学报, 2005, 26(6):135-139.

[8]Hsuan T Chang. Arbitrary affine transformation and their composition effects for two-dimensional fractal sets [J]. Image and Vision Computing, 2004, (22):1117-1127.

[9]沙 震, 阮火军. 分形与拟合[M]. 杭州: 浙江大学出版社, 2005. 123-131.

[10]李水根. 分形[M]. 北京: 高等教育出版社, 2004.86-95.

[11]Jun Kigami. Analysis on Fractals[M]. Beijing: China Machine Press, 2004. 17-27.