一種基于Markov 矩陣的分形建模方法

1、一種基于Markov矩陣的分形建模方法基金項(xiàng)目：福建省教育廳A類科技項(xiàng)目（JA07196）作者簡介： 章立亮，副教授，主研領(lǐng)域:分形與計(jì)算機(jī)圖形圖像章立亮（寧德師范學(xué)院 數(shù)學(xué)研究所 福建 寧德 352100 ）摘 要 提出一種基于轉(zhuǎn)移概率矩陣的Markov迭代函數(shù)系統(tǒng)分形吸引子的建模方法。將MIFS的仿射變換實(shí)施多級化的分解，利用轉(zhuǎn)移概率矩陣對吸引子的局部子圖像做Markov變形處理，基于計(jì)算機(jī)數(shù)學(xué)實(shí)驗(yàn)給出了雪花分形和樹木分形的應(yīng)用實(shí)例，表明該方法能夠有效地控制分形吸引子的局部變形。關(guān)鍵詞 迭代函數(shù)系統(tǒng) Markov 變形 分形 A METHOD OF FRACTAL MODELING BAS

2、ED ON MARKOV MATRIXZHANG Li-liang(Institute of Mathematics,Ningde Teachers College,Ningde Fujian 352100)Abstract Proposed based on the Markov transition probability matrix iterated function system fractal attractor modeling. Affine transformation will MIFS implementation of the multi-level of decomp

3、osition, use of transition probability matrix of the attractor for the local sub-image Zuo Markov deformation processing, computer-based mathematics test given snowflake fractal and fractal trees, an application example, show that the method can effectively Fractal Attractor control of the local def

4、ormation.Keywords Iterated function systems Markov Decomposition Fractal1 引 言迭代函數(shù)系統(tǒng)IFS(Iterated function systems)是分形理論研究的一個(gè)重要領(lǐng)域，其理論和方法在分形的計(jì)算機(jī)構(gòu)造方面應(yīng)用廣泛。Barnsely M F、Elton J H、Hart J C等人把Markov理論應(yīng)用于IFS之中，得到更具普遍意義的廣義迭代函數(shù)系統(tǒng)，開展了許多具體的應(yīng)用研究1，2，3。國內(nèi)一些學(xué)者也積極從事這方面的研究，討論有限Markov轉(zhuǎn)移概率矩陣對吸引子的各種作用，分析MIFS吸引子的結(jié)構(gòu)特征4，5，6

5、。由于MIFS系統(tǒng)在函數(shù)的選擇上加入了可控制的參數(shù)，加強(qiáng)了對圖形的人為控制，因此，很大程度上豐富了IFS可以表現(xiàn)的分形范圍。但這一方法是將Markov矩陣“均勻”地作用于圖像的各個(gè)局部，引起圖像整體結(jié)構(gòu)的演變，在進(jìn)行分形建模時(shí)，它缺乏局部獨(dú)立表示能力。本文提出一種對分形圖像中各局部子圖像進(jìn)行獨(dú)立處理的方法，利用不同類型的Markov轉(zhuǎn)移概率矩陣，將MIFS分形吸引子圖像的各個(gè)局部子圖像分別實(shí)以形狀變形，給出了算法的實(shí)際應(yīng)用實(shí)例，結(jié)果表明該方法具有更好的靈活性和適用性。2 MIFS系統(tǒng)的基本理論 完備度量空間以及個(gè)壓縮映射組成的映射族 稱為迭代函數(shù)系統(tǒng)，記作IFS，對于每一個(gè)映射伴隨一個(gè)概率，取

6、依遞歸方式獨(dú)立地取。選取充分大的整數(shù)，則序列收斂于IFS的吸引子。壓縮映射常取如下形式的仿射變換：若將上述構(gòu)造IFS吸引子的方法進(jìn)行推廣，考慮應(yīng)用Markov鏈控制映射的選取，構(gòu)成Markov迭代函數(shù)系統(tǒng)，在迭代計(jì)算過程中下一次被選擇的映射的概率與前一次被選擇的映射密切相關(guān)。若記條件概率，則矩陣 稱為Markov轉(zhuǎn)移概率矩陣，其中 。表示上次選擇的映射為時(shí)，這次選擇映射的概率。定義 給定完備空間的壓縮映射，令是Markov轉(zhuǎn)移概率矩陣，滿足：，則稱是一個(gè)Markov迭代函數(shù)系統(tǒng)，記為MIFS 。定理 設(shè)為完備度量空間，是相應(yīng)的由的非空緊集組成的空間，是上壓縮比為的MIFS，其中，變換定義如下：

7、，則是上壓縮比為的壓縮映射，即，且存在唯一的不動點(diǎn) ,滿足,同時(shí),對任意成立。定理中的不動點(diǎn)A稱為這個(gè)MIFS的吸引子(吸引子通常為分形)，利用Markov轉(zhuǎn)移概率矩陣可以很大地?cái)U(kuò)展IFS可以表現(xiàn)的分形的范圍，這種由轉(zhuǎn)移概率控制的圖像生成方法，只要使用的轉(zhuǎn)移概率矩陣不同，則所得到的MIFS吸引子也各不相同。3 分形圖像的局部變形算法3.1 算法思想利用Markov迭代函數(shù)系統(tǒng)構(gòu)造IFS分形吸引子，是通過引入Markov轉(zhuǎn)移概率矩陣人為地控制迭代映射的轉(zhuǎn)移，在迭代過程中圖像各局部之間迭代計(jì)算的轉(zhuǎn)移方式是依概率相關(guān)聯(lián)的 7，這是一種“整體性”的行為，圖像中某一局部分形特性的變化必然會影響到其它局部

8、，因此，圖像的分形結(jié)構(gòu)常呈現(xiàn)為局部與整體間或局部與局部間存在某種程度上的自相似性。為了克服這種分形結(jié)構(gòu)的自相似性限制，以便能夠構(gòu)造形狀特征更加富有變化的分形圖像，本文考慮將圖像的不同局部分別進(jìn)行獨(dú)立構(gòu)造，并將圖像的各局部子圖像依次輸出，拼貼形成整幅圖像，可以只對某一局部子圖像實(shí)施變形處理，而不會影響到圖像的其它局部子圖像，如果對不同的局部子圖像選取各異的Markov矩陣，則可能產(chǎn)生包含多種不同形狀結(jié)構(gòu)的不具自相似特征的分形圖像。應(yīng)用該方法構(gòu)造分形圖像，首先需要得到圖像的各局部子圖像的分形迭代碼，這可以利用迭代函數(shù)系統(tǒng)的仿射變換分解定理來實(shí)現(xiàn)。3.2 算法描述仿射變換的分解定理8 如果是分形圖像

9、的IFS碼，是的逆，定義算子為，則是子圖像的IFS碼。子圖像變換矩陣的轉(zhuǎn)換公式為：應(yīng)用仿射變換的分解定理對MIFS局部子圖像的IFS碼進(jìn)行逐級分解，對仿射變換的最終一級分解碼，利用Markov轉(zhuǎn)移概率矩陣實(shí)行迭代計(jì)算生成對應(yīng)的局部變形圖像。如給定仿射變換，的1級分解碼設(shè)為，對得到的1級分解變換，還可以繼續(xù)做下一級的分解，其2級分解碼設(shè)為，依此逐級分解至設(shè)定的級數(shù)停止。具體算法如下：（1）從仿射變換族中選擇某些仿射變換（如），按照轉(zhuǎn)換公式（*）逐級分解至設(shè)定的級數(shù)（設(shè)為n），得到分解碼。（2）對分解得到的前n-1級仿射變換序列：規(guī)定只參與迭代但不畫點(diǎn)。（3）逐個(gè)輸出經(jīng)Markov變形處理后的MI

10、FS：局部子圖像。（4）逐個(gè)輸出未曾進(jìn)行Markov變形處理的其它各級局部子圖像。4 應(yīng)用實(shí)例利用以上算法，分別對雪花分形圖像和樹木分形圖像進(jìn)行局部變形控制，生成形狀結(jié)構(gòu)變化多端的分形圖像。實(shí)例1（雪花分形）設(shè) 其中，(a)原吸引子圖像 (b)整體變形 (c)1級分解變形 (d)2級分解變形圖1雪花分形圖像 圖1（a）為未做Markov變形處理前的吸引子圖像。利用概率矩陣對雪花分形圖像做Markov變形得到如圖1（b）所示圖像，這是一種整體結(jié)構(gòu)的變形，圖像的形狀結(jié)構(gòu)表現(xiàn)較為“單一”。將分別對應(yīng)原吸引子圖像底部兩個(gè)子圖像的仿射變換進(jìn)行1級分解，并利用矩陣和分別對這兩個(gè)子圖像做變形，結(jié)果如圖1（c

11、）所示，由圖可見圖像包含有3種不同的形狀結(jié)構(gòu)。圖1（d）是將對應(yīng)原吸引子圖像頂部子圖像的仿射變換進(jìn)行2級分解后，再對此子圖像上部的3個(gè)2級子圖像做Markov變形的結(jié)果。實(shí)例2（樹木分形）設(shè)，圖2（a）為未做Markov變形處理前的吸引子圖像。先將對應(yīng)樹木上枝子圖像的仿射變換進(jìn)行1級分解，再將分別對應(yīng)樹木的左、右側(cè)枝的兩個(gè)仿射變換進(jìn)行2級分解，然后利用矩陣對仿射變換的1級分解子圖像和仿射變換的2級分解子圖像進(jìn)行Markov變形，再利用矩陣對仿射變換的2級分解子圖像進(jìn)行Markov變形，得到圖2（b）的圖像，比較圖2（a）與圖2（b）可以發(fā)現(xiàn)，經(jīng)多級分解變形處理之后的樹木其細(xì)節(jié)變化多端形態(tài)更加逼

12、真、自然。 (a)原吸引子圖像 (b)1級和2級分解變形圖2樹木分形圖像5 結(jié) 論 以上利用IFS仿射變換的多級化分解方法，可以有效地控制MIFS吸引子圖像的局部演變，圖像的演變范圍能夠被任意地限制于指定的局部之中，使得不同局部的分形結(jié)構(gòu)有所差異，可以得到形狀富有變化的分形圖像，特別是在一類自然景物的分形建模方面，計(jì)算機(jī)圖形實(shí)驗(yàn)結(jié)果已表明能夠取得較好的應(yīng)用效果，該方法的應(yīng)用進(jìn)一步拓寬了MIFS吸引子分形圖像的表現(xiàn)范疇。參 考 文 獻(xiàn)1 Barnsely M F, Elton J H and Hard D P. Recurrent iterated function systems. Const

13、ructive Approximation,1989,5:3312 Hart J C. Fractal image compression and recurrentiterated function systems. IEEE Computer Graphics and Application,1996,7:25333 Sherman P, Hart J C. Direct manipulation of recurrent models. Computers&Graphics,2003,27:1431514 劉向東,朱偉勇,趙雅明. Markov雙曲迭代函數(shù)系統(tǒng)參數(shù)與吸引子關(guān)系的研究.計(jì)算機(jī)科學(xué),2000,27(5):68715 李紅達(dá),葉正麟,彭國華. 向量遞歸迭代函數(shù)系統(tǒng)及其不變測度.系統(tǒng)科學(xué)與數(shù)學(xué),2003,23(2):279 2886 王興元,劉波. 一類NMIFS吸引子的遞歸計(jì)算構(gòu)造及特性分析.自然科學(xué)進(jìn)展,2004,14(9):103910467 章立亮. Markov迭代函數(shù)系統(tǒng)分形的動力學(xué)特性分析.工程圖學(xué)學(xué)