基于ＩＦＳ分形樹的ＶＣ＋＋實(shí)現(xiàn)

摘要：迭代函數(shù)系統(tǒng)（IFS）是構(gòu)造分形集的核心技術(shù)，本文采用IFS方法 和隨機(jī)迭代方法構(gòu)造出樹木的模型，并在vc++6.0的環(huán)境下，實(shí)現(xiàn)了分形樹的模擬。

關(guān)鍵詞：迭代函數(shù)系統(tǒng)；分形；樹木模擬;隨機(jī)函數(shù)

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：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 引言

迭代函數(shù)系統(tǒng)（IFS）是繪制分形圖形的重要方法之一，是分形幾何學(xué)的重要分支。其理論和方法為計(jì)算機(jī)模擬自然現(xiàn)象的真實(shí)感圖形提供了一個(gè)有力的工具，特別是對自然景物的計(jì)算機(jī)模擬方面具有明顯的優(yōu)勢。本文首先介紹了IFS，然后提出了帶概率的IFS的分形樹的仿射變換模型，并通過VC++編程，實(shí)現(xiàn)了用IFS迭代方法繪制的分形樹。

2 IFS基本原理

2.1 分形圖的自相似性

眾所周知，自相似性或自仿射性是分形的最重要的特征。即將局部放大后與原圖是相似的，局部是整體的一個(gè)小復(fù)制品，只不過存在一些不等比例變換和扭曲變換等，而迭代函數(shù)系統(tǒng)（IFS）是以仿射變換為框架，根據(jù)幾何對象的整體與局部具有自相似性結(jié)構(gòu)，經(jīng)過迭代而產(chǎn)生的。為說明問題，引入下面的定義：

定義：變換W：R2→R2具有形式 xhr01.tif

式中abcdef為實(shí)數(shù)，則稱W為一個(gè)二維仿射變換，當(dāng)X∈R2時(shí)，常寫成W(X)=AX+t其中xhr02.tif ，且∣ad-bc∣<1其中：e和f是子圖在x，y方向的位移量；θ和φ是子圖相對原圖方向的的旋轉(zhuǎn)角度；r和q是子圖相對于原圖在x，y方向的縮放系數(shù)。

2.2 IFS的吸引子

由于分形圖具有自相似性，因此可以找到N個(gè)壓縮仿射變換Wi(i=1，2……N)使得

W(B)= xhr03.tif，其中W(B)是一幅分形圖形，Wi(B)是由壓縮仿射變換確定的子圖。

定理：一個(gè)IFS由一個(gè)完備度量空間（X，d）和一個(gè)有限壓縮仿射集Wn:X→X，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)且存在惟一的不動點(diǎn)A∈X(X)，滿足A= W(A)= xhr04.tif，并對任意的B∈X(X)，A= xhr05.tif Wn(B)，則A被稱為IFS的吸引子，該吸引子就是一個(gè)分形。

2.3 （Barnasley拼貼定理）

對于一個(gè)給定的雙曲迭代函數(shù)系（IFS），可用計(jì)算機(jī)生成它的吸引子，從而可得到許多漂亮的分形圖，如何尋找適當(dāng)?shù)腎FS碼，使其吸引子就是或近似是該圖形，本文采用拼貼的方法逼近目標(biāo)圖形，以獲取仿射變換Wi及其參數(shù)。拼貼定理如下：

設(shè){X;W1……Wn}是一個(gè)雙曲迭代函數(shù)系，壓縮因子s<1，A是它的吸引子，又E∈X(X)是任意給定的集合，則有h(A，E) ≤(1-S)-1h(E， xhr06.tif)。定理表明，對于任意圖形E，只要選擇適當(dāng)?shù)姆律渥儞Q，就可以使給定集在變換后的并（拼貼）與給定集近似，使拼貼后的重構(gòu)圖形W (E)非常逼近E。所以IFS方法在模擬分形圖像方面具有極其重要的意義。

3 IFS分形樹模擬算法

3.1 帶概率的IFS

基于IFS算法生成樹木的方法是根據(jù)拼貼定理，對已有的樹木圖像用有限個(gè)該圖形的壓縮仿射變換子圖去覆蓋它，并允許重疊，仿射變換族控制著圖形的結(jié)構(gòu)和形狀，在仿射變換Wn中，每一個(gè)仿射變換被調(diào)用的概率P不一定相同，即落入圖像各個(gè)部分中點(diǎn)的數(shù)目不同，因此為每一個(gè)壓縮仿射變換都分配一個(gè)被調(diào)用的概率P，以減少工作量。則IFS成為帶概率的IFS，形式為{X;Wi;Pi，i=1……n}，其中p的選擇需滿足Pi>0， xhr07.tif=1，一般Pi的取值取決于仿射變換子圖的面積，子圖面積越大，落入該子圖的點(diǎn)的數(shù)目越多，所對應(yīng)的仿射變換系數(shù)被選中的概率也就越大，而實(shí)際的圖形可能不規(guī)則，在求取面積時(shí)，用計(jì)算機(jī)實(shí)現(xiàn)時(shí)可以對仿射子圖填充以不同的顏色，然后根據(jù)屏幕上某種顏色的象素點(diǎn)的個(gè)數(shù)來求面積，任意圖形經(jīng)仿射變換后，面積將為變換前的∣ad-bc∣倍，當(dāng)然，考慮到誤差，最終要對概率P進(jìn)行規(guī)一化，xhr07.tif＝1。

3.2 分形樹IFS碼的獲取

要獲得分形樹的IFS碼，由拼貼定理可知，只要在圖形空間中找到一組壓縮仿射變換的參數(shù)，使給定圖形在改組壓縮仿射作用下形成的子圖拼貼與給定圖形相近，IFS所有的參數(shù)就是要獲得的該圖形的IFS碼。如何獲得所需的IFS碼是分形模擬的重點(diǎn)，也是一個(gè)難點(diǎn)。本文采用銳角三角形的方法，根據(jù)分析圖形的相似性，在整體和局部圖上取一些相對應(yīng)的特征點(diǎn)，通過三組對應(yīng)點(diǎn)求解線性方程組，就可以求出一個(gè)仿射變換參數(shù)。我們把原樹圖像分為四部分，分別為主干，上支，左右支，最終求得的分形樹的IFS碼如表1。

3.3 分形樹的吸引子算法

利用IFS生成分形樹的過程是對初始樹的圖像按照已知概率選擇函數(shù)，而實(shí)施的一種迭代變換，本文采用隨機(jī)迭代算法，在該算法中采用了帶概率IFS，IFSP為{X;Wi;Pi，I=1，2……N}，通過VC++提供的隨機(jī)數(shù)rand()，將當(dāng)前系統(tǒng)時(shí)間作為隨機(jī)種子，用隨機(jī)生成的概率決定選擇第k個(gè)變換 ，不斷迭代得到新的x，y坐標(biāo)，并通過新坐標(biāo)繪制點(diǎn)，迭代產(chǎn)生其圖片。具體算法步驟如下：

①取初始點(diǎn)(x0，y0)及總的迭代次數(shù)n。（初始點(diǎn)一般取為仿射變換的不動點(diǎn)）

②生成隨機(jī)數(shù)R，并使R的值為0—1;

③為每一個(gè)wi分配相應(yīng)pi;

④判斷隨機(jī)數(shù)落入哪一個(gè)空間，調(diào)用相應(yīng)的wi的ifs碼值，賦給相應(yīng)的參數(shù)；

⑤把wi作用到（x0，y0）上得到新點(diǎn)（x1，y1），并且在（x1，y1）處畫一點(diǎn)；

⑥如果畫的點(diǎn)數(shù)小于指定的點(diǎn)數(shù)，將本次計(jì)算的值作為下一次的x和y值參加計(jì)算，循環(huán)執(zhí)行②到⑤，直到完成迭代次數(shù)。

3.4 運(yùn)行結(jié)果

本文使用VC++6.0，通過編程實(shí)現(xiàn)分形樹的構(gòu)造與模擬，在執(zhí)行過程中，隨著迭代次數(shù)的增加，隨機(jī)落下的點(diǎn)數(shù)將逐漸顯現(xiàn)處分形樹IFS的吸引子。生成的分形樹序列如圖1所示。

4 結(jié)束語

本文在vc++下采用IFS算法繪制分形樹，從理論上來講，吸引子與概率p的選擇無關(guān)，但在實(shí)際繪圖是p 起到很重要的作用，控制概率，就是控制拼貼圖形各部分落點(diǎn)的密度，使圖形在有限步迭代終止時(shí)，顯示出瀧淡虛實(shí)的不同層次。而迭代次數(shù)的選取沒有一個(gè)統(tǒng)一的指導(dǎo)理論，只能靠實(shí)驗(yàn)來反復(fù)進(jìn)行，直到生成一個(gè)清晰的分形樹為止。如果分析圖已經(jīng)形成，迭代次數(shù)增加，這樣使得生成的分形圖形的時(shí)間大大延長，降低了算法的效率。因此如何確定迭代次數(shù)的下限，提高算法效率，是需進(jìn)一步研究的問題。

參考文獻(xiàn)：

[1] 曾文曲，王向陽等，分形理論與分形的計(jì)算機(jī)模擬[M].沈陽：東北大學(xué)出版社，2001.

[2] 孫博文，分形算法與程序設(shè)計(jì)——vc++實(shí)現(xiàn)[M].北京：科學(xué)出版社，2004.

[3] 沙震，分形與擬合[M].杭州：浙江大學(xué)出版社，2005.

收稿日期：2008-04-13

陜西理工學(xué)院科研基金項(xiàng)目(SLG0620)

作者簡介：肖海蓉，女，講師，研究方向：數(shù)據(jù)庫技術(shù)及應(yīng)用和圖形圖像處理；任民宏，男，副教授，研究方向：計(jì)算機(jī)圖形圖像處理和信息管理；郭天印，男，教授，研究方向：人工智能與算法。

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”