基于ＩＦＳ分形樹的ＶＣ＋＋實現

摘要：迭代函數系統（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：R2→R2具有形式 xhr01.tif

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

2.2 IFS的吸引子

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

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

定理：一個IFS由一個完備度量空間（X，d）和一個有限壓縮仿射集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)且存在惟一的不動點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<1，A是它的吸引子，又E∈X(X)是任意給定的集合，則有h(A，E) ≤(1-S)-1h(E， xhr06.tif)。定理表明，對于任意圖形E，只要選擇適當的仿射變換，就可以使給定集在變換后的并（拼貼）與給定集近似，使拼貼后的重構圖形W (E)非常逼近E。所以IFS方法在模擬分形圖像方面具有極其重要的意義。

3 IFS分形樹模擬算法

3.1 帶概率的IFS

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