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

胡海龍， 劉樹群

（1. 浙江林學院理學院，浙江 臨安 311300；2. 蘭州理工大學計算機與通信學院，甘肅 蘭州 730050）

20世紀70年代美籍法國數(shù)學家曼德勃羅特(Benoit Mandelbrot)創(chuàng)立了分形幾何學，分形的最重要特征是不規(guī)則性和無限精細自相似結構，因此分形可以很好的用來定義和表達傳統(tǒng)歐氏幾何所不能表達的幾何形體。

迭代函數(shù)系統(tǒng)(Iterated Function System，簡記為IFS)是生成分形的典型方法，可以生成大量的具有自相似結構的分形圖形。但其瓶頸問題是IFS碼的獲取以及其吸引子的自相似性而給人“千篇一律”的感覺。有些學者提出了根據(jù)已知的 IFS碼通過加入某些參量再進行調整[1-3]或者尋找新的 IFS建模技術[4-5]來生成新的分形圖形的方法，宋廣為等提出了基于迭代函數(shù)系統(tǒng)的地紋激光圖案生成算法[6]；為了得到自然、逼真的分形圖形，文獻[7-8]中分別提出了L-系統(tǒng)與IFS相融合的方法和分形圖形的合成方法。

Sierpinski三角形是典型的分形圖形，本文闡述了其生成原理，并對其進行生成元形狀及調整IFS變換兩方面的推廣，得到了吸引子與生成元形狀無關的結論和由已知的IFS經(jīng)過適當?shù)恼{整得到新的IFS，同時生成大量自然、逼真、多樣的分形圖形。

1 仿射變換及IFS理論

定義1（仿射變換）變換 ω :R2→R2形 式 為 ω (x,y)=(ax+by +e,cx+dy+f )，稱為二維的仿射變換，其中 a , b,c,d,e,f 是實常數(shù)。通常也寫成 ω ( X ) =AX +t形式，其中

矩陣A確定了相對于原點的線性變換：縮放變換，旋轉變換，鏡像變換以及錯切變換。t是列向量，確定了平移變換。

當且僅當矩陣A的譜半徑 rσ(A) ＜ 1 時變換為壓縮映射。關于分形空間的詳細理論可以參看文獻[9]。圖1顯示了仿射變換的效果。

圖1 仿射變換ω

定理 2（吸引子定理）一個迭代函數(shù)系統(tǒng)是由完備距離空間 (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出發(fā)，經(jīng)過仿射變換?的依次作用，產(chǎn)生一個迭代結果。各仿射變換再分別作用在上一次的變換結果上，如此反復迭代，其極限集合即為IFS吸引子。

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

令E0為 [ 0 ,1]× [ 0,1]的矩形，如圖2(a)，迭代函數(shù)系統(tǒng)的 3個變換作用在E0上，得到E1=ω1(E0)∪ω2(E0)∪ω3(E0)，如圖2(b)，然后 ω1, ω2, ω3再分別作用在E1上，

得到 E2=ω1(E1)∪ω2(E1)∪ω3( E1)，如圖2(c)，繼續(xù)迭代下去，得到各次迭代結果如圖2(d)～(g)，最終得到此IFS的吸引子為圖2(h)。

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

3 推 廣

推廣1 生成元形狀的改變

IFS同第3部分所述，而生成元不再為四邊形（正方形），在此，將其推廣為點、線段、三角形及圓，生成的分形圖形分別為圖3(a)～(e)。如果迭代次數(shù)足夠大，其吸引子均為圖2(h)所示。

由圖可以看出，對于一個IFS來說，只要變換是收斂的，其吸引子就與生成元形狀無關。

圖3 生成元形狀的推廣

推廣2 對IFS的變換適當調節(jié)，得到新的IFS及吸引子

以 [-1, 1]向上的有向線段為初始集合，如圖4(a)，用有向線段表示仿射變換，IFS及其吸引如圖4(b)所示，其中IFS由3個仿射變換組成，從上到下從左到右依次記為ω1,ω2, ω3，吸引子為Sierpinski三角形。

圖4 調整IFS變換得到新的IFS及其吸引子

（1）調節(jié)一個變換：保持ω2,ω3不變，調節(jié)ω1，得到IFS1及其吸引子如圖4(c)；

（2）調節(jié)兩個變換：保持ω1不變，調節(jié)ω2,ω3，得到 IFS2、IFS3、IFS4及它們的吸引子如圖4(d)、(e)、(f)；

（3）調節(jié)3個變換：調節(jié) ω1,ω2, ω3，得到IFS5、IFS6及其吸引子如圖4(g)、(h)所示。

從圖4可以看出，適當調節(jié)Sierpinski三角形的IFS變換，就可以得到新的IFS，其吸引子有的還保持Sierpinski三角形的影子（如圖4(c)、(d)）；有的完全不同于Sierpinski三角形，可以得到形態(tài)各異，生動逼真的自然景物及日常用品，如樹葉、掃帚、樹冠和盔甲等。

4 結束語

本文敘述了基于IFS理論的Sierpinski三角形生成原理，并對其進行生成元形狀及其IFS調整兩方面的推廣，并運用此方法進行了大量的計算機分形圖形實驗，得到了兩個結論：① 吸引子與生成元形狀無關，② 由Sierpinski三角形的IFS可以得到新的 IFS，由此能生成豐富多彩的分形圖形。

[1]孫 煒, 陳錦昌. 應用迭代函數(shù)系統(tǒng)獲得分形圖形的簡易方法[J]. 工程圖學學報, 2001, 22(3):109-113.

[2]章立亮. 一類全不連通分形圖的構造[J]. 中國圖象圖形學報(A版), 2003, 8(7): 744-747.

[3]章立亮. 一種帶自動參量的迭代函數(shù)系統(tǒng)[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-系統(tǒng)與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.