一种基于Markov 矩阵的分形建模方法

1、一种基于Markov矩阵的分形建模方法基金项目：福建省教育厅A类科技项目（JA07196）作者简介： 章立亮，副教授，主研领域:分形与计算机图形图像章立亮（宁德师范学院 数学研究所 福建 宁德 352100 ）摘 要 提出一种基于转移概率矩阵的Markov迭代函数系统分形吸引子的建模方法。将MIFS的仿射变换实施多级化的分解，利用转移概率矩阵对吸引子的局部子图像做Markov变形处理，基于计算机数学实验给出了雪花分形和树木分形的应用实例，表明该方法能够有效地控制分形吸引子的局部变形。关键词 迭代函数系统 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 引 言迭代函数系统IFS(Iterated function systems)是分形理论研究的一个重要领域，其理论和方法在分形的计算机构造方面应用广泛。Barnsely M F、Elton J H、Hart J C等人把Markov理论应用于IFS之中，得到更具普遍意义的广义迭代函数系统，开展了许多具体的应用研究1，2，3。国内一些学者也积极从事这方面的研究，讨论有限Markov转移概率矩阵对吸引子的各种作用，分析MIFS吸引子的结构特征4，5，6

5、。由于MIFS系统在函数的选择上加入了可控制的参数，加强了对图形的人为控制，因此，很大程度上丰富了IFS可以表现的分形范围。但这一方法是将Markov矩阵“均匀”地作用于图像的各个局部，引起图像整体结构的演变，在进行分形建模时，它缺乏局部独立表示能力。本文提出一种对分形图像中各局部子图像进行独立处理的方法，利用不同类型的Markov转移概率矩阵，将MIFS分形吸引子图像的各个局部子图像分别实以形状变形，给出了算法的实际应用实例，结果表明该方法具有更好的灵活性和适用性。2 MIFS系统的基本理论 完备度量空间以及个压缩映射组成的映射族 称为迭代函数系统，记作IFS，对于每一个映射伴随一个概率，取

6、依递归方式独立地取。选取充分大的整数，则序列收敛于IFS的吸引子。压缩映射常取如下形式的仿射变换：若将上述构造IFS吸引子的方法进行推广，考虑应用Markov链控制映射的选取，构成Markov迭代函数系统，在迭代计算过程中下一次被选择的映射的概率与前一次被选择的映射密切相关。若记条件概率，则矩阵 称为Markov转移概率矩阵，其中 。表示上次选择的映射为时，这次选择映射的概率。定义 给定完备空间的压缩映射，令是Markov转移概率矩阵，满足：，则称是一个Markov迭代函数系统，记为MIFS 。定理 设为完备度量空间，是相应的由的非空紧集组成的空间，是上压缩比为的MIFS，其中，变换定义如下：

7、，则是上压缩比为的压缩映射，即，且存在唯一的不动点 ,满足,同时,对任意成立。定理中的不动点A称为这个MIFS的吸引子(吸引子通常为分形)，利用Markov转移概率矩阵可以很大地扩展IFS可以表现的分形的范围，这种由转移概率控制的图像生成方法，只要使用的转移概率矩阵不同，则所得到的MIFS吸引子也各不相同。3 分形图像的局部变形算法3.1 算法思想利用Markov迭代函数系统构造IFS分形吸引子，是通过引入Markov转移概率矩阵人为地控制迭代映射的转移，在迭代过程中图像各局部之间迭代计算的转移方式是依概率相关联的 7，这是一种“整体性”的行为，图像中某一局部分形特性的变化必然会影响到其它局部

8、，因此，图像的分形结构常呈现为局部与整体间或局部与局部间存在某种程度上的自相似性。为了克服这种分形结构的自相似性限制，以便能够构造形状特征更加富有变化的分形图像，本文考虑将图像的不同局部分别进行独立构造，并将图像的各局部子图像依次输出，拼贴形成整幅图像，可以只对某一局部子图像实施变形处理，而不会影响到图像的其它局部子图像，如果对不同的局部子图像选取各异的Markov矩阵，则可能产生包含多种不同形状结构的不具自相似特征的分形图像。应用该方法构造分形图像，首先需要得到图像的各局部子图像的分形迭代码，这可以利用迭代函数系统的仿射变换分解定理来实现。3.2 算法描述仿射变换的分解定理8 如果是分形图像

9、的IFS码，是的逆，定义算子为，则是子图像的IFS码。子图像变换矩阵的转换公式为：应用仿射变换的分解定理对MIFS局部子图像的IFS码进行逐级分解，对仿射变换的最终一级分解码，利用Markov转移概率矩阵实行迭代计算生成对应的局部变形图像。如给定仿射变换，的1级分解码设为，对得到的1级分解变换，还可以继续做下一级的分解，其2级分解码设为，依此逐级分解至设定的级数停止。具体算法如下：（1）从仿射变换族中选择某些仿射变换（如），按照转换公式（*）逐级分解至设定的级数（设为n），得到分解码。（2）对分解得到的前n-1级仿射变换序列：规定只参与迭代但不画点。（3）逐个输出经Markov变形处理后的MI

10、FS：局部子图像。（4）逐个输出未曾进行Markov变形处理的其它各级局部子图像。4 应用实例利用以上算法，分别对雪花分形图像和树木分形图像进行局部变形控制，生成形状结构变化多端的分形图像。实例1（雪花分形）设 其中，(a)原吸引子图像 (b)整体变形 (c)1级分解变形 (d)2级分解变形图1雪花分形图像 图1（a）为未做Markov变形处理前的吸引子图像。利用概率矩阵对雪花分形图像做Markov变形得到如图1（b）所示图像，这是一种整体结构的变形，图像的形状结构表现较为“单一”。将分别对应原吸引子图像底部两个子图像的仿射变换进行1级分解，并利用矩阵和分别对这两个子图像做变形，结果如图1（c

11、）所示，由图可见图像包含有3种不同的形状结构。图1（d）是将对应原吸引子图像顶部子图像的仿射变换进行2级分解后，再对此子图像上部的3个2级子图像做Markov变形的结果。实例2（树木分形）设，图2（a）为未做Markov变形处理前的吸引子图像。先将对应树木上枝子图像的仿射变换进行1级分解，再将分别对应树木的左、右侧枝的两个仿射变换进行2级分解，然后利用矩阵对仿射变换的1级分解子图像和仿射变换的2级分解子图像进行Markov变形，再利用矩阵对仿射变换的2级分解子图像进行Markov变形，得到图2（b）的图像，比较图2（a）与图2（b）可以发现，经多级分解变形处理之后的树木其细节变化多端形态更加逼

12、真、自然。 (a)原吸引子图像 (b)1级和2级分解变形图2树木分形图像5 结 论 以上利用IFS仿射变换的多级化分解方法，可以有效地控制MIFS吸引子图像的局部演变，图像的演变范围能够被任意地限制于指定的局部之中，使得不同局部的分形结构有所差异，可以得到形状富有变化的分形图像，特别是在一类自然景物的分形建模方面，计算机图形实验结果已表明能够取得较好的应用效果，该方法的应用进一步拓宽了MIFS吸引子分形图像的表现范畴。参 考 文 献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双曲迭代函数系统参数与吸引子关系的研究.计算机科学,2000,27(5):68715 李红达,叶正麟,彭国华. 向量递归迭代函数系统及其不变测度.系统科学与数学,2003,23(2):279 2886 王兴元,刘波. 一类NMIFS吸引子的递归计算构造及特性分析.自然科学进展,2004,14(9):103910467 章立亮. Markov迭代函数系统分形的动力学特性分析.工程图学学