胡海龍， 劉樹群

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

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

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

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

1 仿射變換及IFS理論

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

矩陣A確定了相對(duì)于原點(diǎn)的線性變換：縮放變換，旋轉(zhuǎn)變換，鏡像變換以及錯(cuò)切變換。t是列向量，確定了平移變換。

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

圖1 仿射變換ω

定理 2（吸引子定理）一個(gè)迭代函數(shù)系統(tǒng)是由完備距離空間 (X,d)和在其上定義的一組分別具有壓縮因子0 ≤ sn＜1的有限個(gè)壓縮映射ω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的吸引子，一般來(lái)說(shuō)，該吸引子就是分形[10-11]。

2 Sierpinski三角形生成原理

本文采用確定性迭代算法生成 Siperpski三角形，其基本原理為：由 R2空間中一個(gè)子集B出發(fā)，經(jīng)過(guò)仿射變換?的依次作用，產(chǎn)生一個(gè)迭代結(jié)果。各仿射變換再分別作用在上一次的變換結(jié)果上，如此反復(fù)迭代，其極限集合即為IFS吸引子。

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

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

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

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

3 推 廣

推廣1 生成元形狀的改變

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

由圖可以看出，對(duì)于一個(gè)IFS來(lái)說(shuō)，只要變換是收斂的，其吸引子就與生成元形狀無(wú)關(guān)。

圖3 生成元形狀的推廣

推廣2 對(duì)IFS的變換適當(dāng)調(diào)節(jié)，得到新的IFS及吸引子

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

圖4 調(diào)整IFS變換得到新的IFS及其吸引子

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

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

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

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

4 結(jié)束語(yǔ)

本文敘述了基于IFS理論的Sierpinski三角形生成原理，并對(duì)其進(jìn)行生成元形狀及其IFS調(diào)整兩方面的推廣，并運(yùn)用此方法進(jìn)行了大量的計(jì)算機(jī)分形圖形實(shí)驗(yàn)，得到了兩個(gè)結(jié)論：① 吸引子與生成元形狀無(wú)關(guān)，② 由Sierpinski三角形的IFS可以得到新的 IFS，由此能生成豐富多彩的分形圖形。

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

[2]章立亮. 一類全不連通分形圖的構(gòu)造[J]. 中國(guó)圖象圖形學(xué)報(bào)(A版), 2003, 8(7): 744-747.

[3]章立亮. 一種帶自動(dòng)參量的迭代函數(shù)系統(tǒng)[J]. 工程圖學(xué)學(xué)報(bào), 2006, 27(2): 171-175.

[4]張亦舜, 楊 揚(yáng). 構(gòu)造IFS吸引子的新算法[J]. 中國(guó)圖象圖形學(xué)報(bào)(A版), 2002, 7(11): 1161-1164.

[5]魏小鵬, 周運(yùn)紅, 張建明, 等. 自然景物IFS建模技術(shù)研究[J]. 工程圖學(xué)學(xué)報(bào), 2003, 24(4): 103-109.

[6]宋廣為, 徐 晨, 狄震宇. 一種基于分形的地紋激光圖案生成算法[J]. 微計(jì)算機(jī)信息, 2006, 22(13):253-254.

[7]李慶忠, 韓金姝. 一種 L-系統(tǒng)與IFS相互融合的植物模擬方法[J]. 工程圖學(xué)學(xué)報(bào), 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]. 杭州: 浙江大學(xué)出版社, 2005. 123-131.

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

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