ABSTRACT

In this paper, based on the introduction of the basic theory of Iterative Function System(IFS), the first application of IFS code to a given image can reveal the shrinkage characteristics of internal affine transformation. The influence of the numbers and parameters of affine transformations on the generation of fractal tree is analyzed. Thus it can generate fractal trees with different morphologies by modifying the IFS code. Using pseudo-affine transformation to achieve the interpolation of the attractor image, the triangular maple leaves and the pentagon maple leaves are generated. Meanwhile, controllable fractal leaves can be obtained through adjusting interpolation points. Finally, some examples of fractal images are given with Matlab.

Keywords:Fractal, Plant Simulation, Pseudo-Affine Transformation, Maple Leaves

基于迭代函数系统的分形植物模拟

李彩云，郑红婵，林增耀

西北工业大学理学院，陕西 西安

收稿日期：2017年12月23日；录用日期：2018年1月23日；发布日期：2018年1月30日

摘 要

本文在介绍迭代函数系统(IFS)基本理论的基础上，根据IFS码对给定图像的第一次应用来揭示内部的仿射变换收缩特性，分析了仿射变换个数以及参数对生成分形树的影响，从而修改IFS码，生成了具有不同形态的分形树。利用拟仿射变换实现吸引子图像的插值，并生成三角枫叶、五角枫叶等，通过调整插值点生成形状可控的分形树叶。最后，结合Matlab给出分形图的若干实例。

关键词 :分形，景物模拟，拟仿射变换，枫叶

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

自然景物模拟是计算机图形学中一个重要研究课题，其中植物形态仿真模拟引起了广泛的关注。许多学者对其进行了大量的研究，目前常见的方法有L-系统 [1] [2] 、迭代函数系统 [3] [4] [5] 、粒子系统 [6] [7] 、扩散受限凝聚(DLA)模型 [8] 等。迭代函数系统(Iteration Function System，简称IFS)是绘制植物分形图的主要方法，利用该方法既可以模拟自然界存在的物种也可以创造新物种。1999年郝小琴 [9] 提出了基于树木的分枝模式与叶序模式的三维IFS建模法并生成了槐树和雪松。2004仲兰芬、王琰等 [10] 给出了生成单轴分枝和合轴分枝两类树木的递归算法。2008年潘陆益 [11] 提出了基于IFS的分形图的拟仿射变换模型。2012年韩江萍、周敏等 [12] 利用拟仿射变换实现树木成行、树木成林。2016年仲兰芬、王文忠等 [13] 提出了一种通过包含边缘轮廓和主叶脉的树叶草图生成三维树叶的方法。在利用迭代函数系统生成植物的过程中，大多数文献是直接给出IFS码，鲜有文献分析IFS码中各参数对分形图生成的影响。本文通过IFS码对给定图像的第一次应用来揭示内部的仿射变换收缩特性，分析了各仿射变换参数对分形图的影响效果，根据需求可以人为地设定仿射变换的个数以及参数继而得到相应的IFS码，生成单轴、合轴以及树冠的个数不同的分形树。通过IFS码生成的分形图的拟仿射变换即对分形图的平移、旋转、缩放、错切等变换生成具有相似性的多片叶瓣的树叶如三角枫叶、五角枫叶等。

2. 预备知识

仿射变换是指在不同的方向上变化的比率可以不同的一种比例变换。使一个图形产生它的复制品，于是可以将原图分解为几个部分，每个部分可看作是在不同仿射变换下的复制品，而这种分解与尺度无关，即原图经仿射变换后仍可对其局部图形进行类似的分解，这种整体与局部相似的性质正是分形的特征。

定义1 [8] ：变换 $W:R^2\to R^2$ 具有形式为

$W\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]+\left[\begin{array}{c}e\\ f\end{array}\right],$

其中 $a,b,c,d,e,f$ 为实数，则称 $W$ 为一个(二维)仿射变换。

当 $x\in R^2$ 时，上式常改写为

$W\left(x\right)=Ax+t,$

其中 $A=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right],t=\left[\begin{array}{c}e\\ f\end{array}\right]$ 。

定义2 [8] ：度量空间 $\left(X,\rho \right)$ 上的变换 $f:X\to X$ 称为压缩映射或压缩，如果存在一常量 $0\le s<1$ ，使得

$\rho \left(f\left(x\right),f\left(y\right)\right)\le s\rho \left(x,y\right),\forall x,y\in X,$

数 $s$ 称为 $f$ 的压缩因子。

定义3 [8] ：(迭代函数系统IFS)一个迭代函数系统由一个完备度量空间 $\left(X,\rho \right)$ 和一个有限的压缩映射集 $W_n:X\to X$ 及相应的压缩因子 $s_n,n=1,2,\cdots ,N$ 所组成，每个 $W_n$ 有一个伴随概率 $p_n,0<p_n<1$ 且 ${\displaystyle \sum p_n}=1$ 。迭代函数系统IFS记为： $\left\{X;W_n,n=1,2,\cdots ,N\right\}$ ，随机迭代函数系统IFSP记为： $\left\{X;W_n,p_n,n=1,2,\cdots ,N\right\}$ ，且其压缩因子都是 $s=\max \left\{s_n:n=1,2,\cdots ,N\right\}$ 。IFS若满足条件 $s_1^{p_1}\cdot s_2^{p_2}\cdot s_3^{p_3}\cdots s_N^{p_N}<1$ ，则称之为一个IFS码。

定理1 [8] ：设 $\left\{X;W_n,n=1,2,\cdots ,N\right\}$ 是拥有压缩因子 $s$ 的IFS码，则定义变换 $W:H\left(X\right)\to H\left(X\right)$ 为

$W\left(B\right)={\displaystyle \underset{n=1}{\overset{N}{\cup }}{W}_n\left(B\right)},\forall B\in H\left(X\right),$

且 $W$ 是完备空间 $\left(H\left(X\right),h\left(\rho \right)\right)$ 上具有压缩因子 $s$ 的压缩映射，即

$h\left(W\left(A\right),W\left(B\right)\right)\le sh\left(A,B\right),\forall A,B\in H\left(X\right),$

它的唯一不动点集 $P\in H\left(X\right)$ 满足

$P=W\left(P\right)={\displaystyle \underset{n=1}{\overset{N}{\cup }}{W}_n\left(P\right)},$

且 $P=\underset{n\to \infty }{\lim }{W}^n\left(B\right),\forall B\in H\left(X\right)$ 。不动点集 $P\in H\left(X\right)$ 被称为IFS的吸引子。

定理2 [14] ：(拼贴原理)设 $\left(X,\rho \right)$ 为度量空间，给定 $$ 和 $\epsilon >0$ ，选定一个IFS $\left\{X;W_n,n=1,2,\cdots ,N\right\}$ ，其压缩因子 $0\le s<1$ ，使得 $h\left(L,{\displaystyle \underset{n=1}{\overset{N}{\cup }}{W}_n\left(L\right)}\right)\le \epsilon$ ，则有 $h\left(L,A\right)\le \frac{\epsilon }{1-s}$ 。这里， $A$ 是该IFS的吸引子， $h$ 为Hausdorff距离。

3. 不同形态分形树的生成

利用IFS方法生成分形图的关键是找出其相应的IFS码，即仿射变换的系数。下面就介绍仿射变换的一些概念，从而更好地确定IFS码。

3.1. 简单的变换

图形的基本变换包括平移变换、缩放变换、旋转变换、反射变换、错切变换等。利用仿射变换进行分形模拟往往需要连续进行多次基本变换，将整体图形映射为局部图形，称之为组合变换或连续变换。仿射变换对一个图像的第一次应用，通常会揭示其内部的仿射线性收缩特征 [15] 。但是我们还必须注意到，选择一个具有合适结构的图像是非常重要的，只有这样才能够鉴别出其独特的变换，不然就不能够确切地检测出一些可能发生了的旋转和反射。在本文剩下的这些图像中，我们都代表性地使用一个在左上角

镶嵌了一个“L”的 $\left[0,1\right]\times \left[0,1\right]$ 单位正方形作为初始图像。图1给出了图形的4个基本变换。

仿射变换是由6个系数所决定的，为了更方便地探讨压缩变换。将矩阵 $A$ 改写为以下形式：

$\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]=\left[\begin{array}{cc}r\cos \theta & -s\sin \phi \\ r\sin \theta & s\cos \phi \end{array}\right]$

只须令

$\begin{array}{l}r=\sqrt{a^2+c^2}\\ \theta =\arccos \left(\frac{a}{\sqrt{a^2+c^2}}\right)\end{array}$

图1. 图形的基本变换

即可，用类似的式子可以得到 $s$ 和 $\phi$ 。其中 $r,s$ 分别表示沿 $x,y$ 轴方向缩放的倍数， $\theta ,\phi$ 分别表示 $x,y$ 轴逆时针方向的旋转角度。因此对于任意一个仿射变换都可以用 $r,s,\theta ,\phi$ 来表示。

3.2. 分形树的算法实现

上一小节已经介绍了各参数的意义，当给定对应的参数值就可以得到每个仿射变换的系数，而每一个仿射变换被调用的概率不一定相同，随机迭代函数系统 $\left\{X;W_n,p_n,n=1,2,\cdots ,N\right\}$ 绘制IFS吸引子的实质是按照概率来选择不同仿射变换，即落入图形各部分中点的数目不一定相同。其中：

${\displaystyle \sum p_n}=1,0<p_n<1,\left(n=1,2,\cdots ,N\right),$

一般情况下， $p_n$ 由下式给出 [16] ：

$p_n=\frac{\left|A_n\right|}{{\displaystyle \sum _{n=1}^N\left|A_n\right|}}=\frac{\left|a_n{d}_n-b_n{c}_n\right|}{{\displaystyle \sum _{n=1}^N\left|a_n{d}_n-b_n{c}_n\right|}},$

其中 $a_n,b_n,c_n,d_n$ 为第 $n$ 个仿射变换的系数。

本文采用随机迭代算法，通过Matlab提供的随机数rand()，用随机生成的概率选择一个仿射变换 $W_n$ 作为迭代规则迭代一次，不断重复此迭代过程，产生的极限图形就是所要绘制的分形图形。设计的算法步骤如下：

(1) 定义IFSP为 $\left\{X;W_n,p_n,n=1,2,\cdots ,N\right\}$ ，设定初始点 $\left(x_0,y_0\right)$ 和迭代次数 $level$ ；

(2) 利用rand()函数生成在区间 $\left[0,1\right]$ 的随机数 $R$ ，以概率 $p_n$ 选取仿射变换 $W_n$ ；

(3) 以 $W_n$ 作用点 $\left(x_0,y_0\right)$ ，得到新坐标 $\left(x_1,y_1\right)$ ；

(4) 令 $x_0=x_1,y_0=y_1$ 并在屏幕上打出 $\left(x_0,y_0\right)$ ；

(5) 重返第(2)步，进行下一次的迭代，直到迭代次数大于 $level$ 为止。

下面就根据IFS对给定图像的第一次应用来揭示内部的仿射变换收缩特性，从而调整已有的IFS码中仿射变换的参数，生成形态各异的分形树。

在图2中，图b~图e是在a的基础上修改IFS码中参数得到的图像，a图对应的IFS码见附录的附表1。图b，图c是修改IFS码中的参数 $\theta ,\phi$ 生成的，从第一行可以看出，b图的旋转角度相对于a图变小，从而生成的树各枝干较紧凑，相反地，c图是旋转角度变大，从而生成的树枝干较分散。图d，图e是修改IFS码中的参数 $r,s$ 生成的，其中图d是增大 $y$ 轴的缩放系数 $s$ ，生成树的枝干较笔直，图e是增大 $x$ 轴的缩放系数 $r$ ，树枝较弯曲。

在此基础上，我们还可以通过修改仿射变换的个数来改变分形树的形态。在图3中图a通过3个仿射变换生成嫩枝，图b用4个仿射变换生成了枝干繁多的单轴 [10] 分形树，图c用5个仿射变换生成一棵

图2. 仿射变换不同参数的分形树。第一行第一个是给定的原始图像，后面五个是对初始图像经过一次仿射变换的图形，第二行对应IFS码的吸引子

图3. 仿射变换个数不同的分形树。第一行第一个是初始图像，后面四个是对初始图像经过一次仿射变换的图形，第二行是对应IFS码的吸引子

合轴 [10] 的枯树，图d用6个仿射变换生成具有4个树冠枝叶 [3] 的分形树，图a~图d的IFS码分别对应于附录的附表2~附表5。

我们分析了仿射变换的个数以及相应参数对分形树形状的影响，因此可以根据 $\theta ,\phi$ 来调整树枝之间的紧凑程度， $r,s$ 调整树枝的笔直和弯曲程度，还可以通过仿射变换个数及拼贴方法来决定树的形状，单轴、合轴以及树冠的个数。该方法的优势是利用第1级的映射可以直观地预测分形树的形状，根据我们的需要可以人为地设定仿射变换的个数以及相应的参数，从而得到IFS码并生成对应的分形树。

在自然界中，我们经常会看到具有多片叶瓣的树叶，例如枫叶、三叶草。若还使用上述方法模拟，一片叶瓣需要3~4个仿射变换，当叶片个数较多时，需要拼贴的仿射变换较多，不方便计算。由于这些叶片一般都具有相似的结构，我们采用拟仿射变换的方法可以有效快速地生成树叶。

4. 采用拟仿射变换生成三角枫叶、五角枫叶

4.1. 拟仿射变换

IFS是以仿射变换为框架，经过迭代生成的，但迭代生成的整体分形图却不能简单地使用几何学上的仿射变换的方法实现。我们将分形图整体平移、缩放、旋转、错切等几何变换称为拟仿射变换。其原因在于分形图是一组仿射变换所确定的不动点集，对这些不动点集的拟仿射变换过程就是使这些不动点集从一个状态换到另一个状态的过程，变换后分形图的结构、状态和点的分布密度仍然受IFS码的控制，即在具体算法中，对迭代生成的点进行平移、旋转、缩放、错切等变换操作之后，必须将变换之前的点作为下一次迭代的初值，从而就可以实现分形图整体的仿射变换。在下节中介绍从分形图的拟仿射变换迭代产生的拟仿射变换模型，进而实现分形图的拟仿射变换。

4.2. 分形图的拟仿射变换

为了描述迭代系统的迭代过程，给出如下记号：

变换矩阵： $A_i=\left[\begin{array}{cc}{a}_i& b_i\\ c_i& d_i\end{array}\right]$ ，位移矩阵： $E_i=\left[\begin{array}{c}{e}_i\\ f_i\end{array}\right]$ ，变换后的矩阵： $X=\left[\begin{array}{c}x\\ y\end{array}\right]$ ，初始值： $X_0=\left[\begin{array}{c}{x}_0\\ y_0\end{array}\right]$ ，则IFS的迭代模型用数学表达式表示为：

$X_k=A_i\times X_{k-1}+E_i,$

用矩阵形式表示为：

$\left[\begin{array}{c}{x}_k\\ y_k\end{array}\right]=\left[\begin{array}{cc}{a}_i& b_i\\ c_i& d_i\end{array}\right]\times \left[\begin{array}{c}{x}_{k-1}\\ y_{k-1}\end{array}\right]+\left[\begin{array}{c}{e}_i\\ f_i\end{array}\right].$

(1) 分形图的平移变换

分形图的平移就是将原分形图沿坐标轴移动一个分量，记平移矩阵为 $D=\left[\begin{array}{c}{d}_x\\ d_y\end{array}\right]$ ，

平移变换模型为： $X_k=A_i\left(X_{k-1}-D\right)+E_i+D,$

用矩阵形式表示为：

$\left[\begin{array}{c}{x}_k\\ y_k\end{array}\right]=\left[\begin{array}{cc}{a}_i& b_i\\ c_i& d_i\end{array}\right]\left[\begin{array}{c}{x}_{k-1}\\ y_{k-1}\end{array}\right]-\left[\begin{array}{cc}{a}_i& b_i\\ c_i& d_i\end{array}\right]\left[\begin{array}{c}{d}_x\\ d_y\end{array}\right]+\left[\begin{array}{c}{e}_i\\ f_i\end{array}\right]+\left[\begin{array}{c}{d}_x\\ d_y\end{array}\right].$

(2) 分形图的旋转变换

如果分形图绕坐标原点逆时针旋转角度为 $\theta$ ，则旋转矩阵为 $R=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]$ ，

旋转变换模型为： $X_k=R\left(A_i\times R^{-1}\times X_{k-1}+E_i\right),$

用矩阵形式表示为：

$\left[\begin{array}{c}{x}_k\\ y_k\end{array}\right]=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]\left[\begin{array}{cc}{a}_i& b_i\\ c_i& d_i\end{array}\right]\left[\begin{array}{cc}\cos \theta & \sin \theta \\ -\sin \theta & \cos \theta \end{array}\right]\left[\begin{array}{c}{x}_{k-1}\\ y_{k-1}\end{array}\right]+\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]\left[\begin{array}{c}{e}_i\\ f_i\end{array}\right].$

(3) 分形图的缩放变换

设在 $x,y$ 轴方向的放大或缩小的因子为 $K_x,K_y$ ，则缩放矩阵为 $R=\left[\begin{array}{cc}{K}_x& 0\\ 0& K_y\end{array}\right]$ ，

缩放变换模型为： $X_k=R\left(A_i\times R^{-1}\times X_{k-1}+E_i\right),$

用矩阵形式表示为：

$\left[\begin{array}{c}{x}_k\\ y_k\end{array}\right]=\left[\begin{array}{cc}{K}_x& 0\\ 0& K_y\end{array}\right]\left[\begin{array}{cc}{a}_i& b_i\\ c_i& d_i\end{array}\right]\left[\begin{array}{cc}1/K_x& 0\\ 0& 1/K_y\end{array}\right]\left[\begin{array}{c}{x}_{k-1}\\ y_{k-1}\end{array}\right]+\left[\begin{array}{cc}{K}_x& 0\\ 0& K_y\end{array}\right]\left[\begin{array}{c}{e}_i\\ f_i\end{array}\right].$

(4) 分形图的错切变换

沿 $x$ 轴方向的切变系数为 $S_x$ ，则错切变换矩阵为 $R=\left[\begin{array}{cc}1& S_x\\ 0& 1\end{array}\right]$ ，

错切变换模型为： $X_k=R\left(A_i\times R^{-1}\times X_{k-1}+E_i\right),$

用矩阵形式表示为：

$\left[\begin{array}{c}{x}_k\\ y_k\end{array}\right]=\left[\begin{array}{cc}1& S_x\\ 0& 1\end{array}\right]\left[\begin{array}{cc}{a}_i& b_i\\ c_i& d_i\end{array}\right]\left[\begin{array}{cc}1& -S_x\\ 0& 1\end{array}\right]\left[\begin{array}{c}{x}_{k-1}\\ y_{k-1}\end{array}\right]+\left[\begin{array}{cc}1& S_x\\ 0& 1\end{array}\right]\left[\begin{array}{c}{e}_i\\ f_i\end{array}\right].$

同理，可以得到沿 $y$ 轴方向的切变系数为 $S_y$ 对应的矩阵形式：

$\left[\begin{array}{c}{x}_k\\ y_k\end{array}\right]=\left[\begin{array}{cc}1& 0\\ S_y& 1\end{array}\right]\left[\begin{array}{cc}{a}_i& b_i\\ c_i& d_i\end{array}\right]\left[\begin{array}{cc}1& 0\\ -S_y& 1\end{array}\right]\left[\begin{array}{c}{x}_{k-1}\\ y_{k-1}\end{array}\right]+\left[\begin{array}{cc}1& 0\\ S_y& 1\end{array}\right]\left[\begin{array}{c}{e}_i\\ f_i\end{array}\right].$

在具体的算法中，将迭代部分用这四个迭代方程替换就可以得到分形图的平移，旋转，缩放，错切变换。这里我们生成具有相似的多片叶瓣的树叶如三角枫叶、五角枫叶。通过对原始的分形图作不同的拟仿射变换，实现分形图的可控性。不妨假设其中一片叶子的顶点坐标为 $\left(a_1,b_1\right)$ ，用户指定的插值点为 $\left(a_2,b_2\right)$ ，则这两点之间夹角为：

$\alpha =\arccos \left(\frac{\left(a_1^2+b_1^2\right)+\left(a_2^2+b_2^2\right)-\left({\left(a_1-a_2\right)}^2+{\left(b_1-b_2\right)}^2\right)}{2\times \sqrt{a_1^2+b_1^2}\times \sqrt{a_2^2+b_2^2}}\right),$

对原分形图进行旋转角度为 $\alpha$ 的旋转变换，其旋转矩阵为 $R=\left[\begin{array}{cc}\cos \alpha & -\sin \alpha \\ \sin \alpha & \cos \alpha \end{array}\right]$ ，

并计算其长度比为：

$L=\frac{\sqrt{a_2^2+b_2^2}}{\sqrt{a_1^2+b_1^2}},$

在上步的基础上再将原图进行缩放，其缩放矩阵为 $S=\left[\begin{array}{cc}L& 0\\ 0& L\end{array}\right]$ ，从而实现分形图的插值。

4.3. 可控枫叶的算法实现

在这一节中我们展示生成枫叶的具体过程，三角枫叶和五角枫叶的叶瓣之间具有相似的结构，在这里用分步处理的方法来生成枫叶。先生成其中一片叶子作为目标枫叶，然后利用拟仿射变换对原图像进行变换从而生成我们想要的图像。这里可控性分为两个部分，一是叶片的个数m，二是插值的控制点位置。下面给出生成m片枫叶的算法步骤：

(1) 给定初始插值点 $\left(a_2,b_2\right),\left(a_3,b_3\right),\cdots ,\left(a_m,b_m\right)$ ；

(2) 用上节给出的随机迭代算法生成目标树叶；

(3) 对目标树叶运用拟仿射变换模型，调用m次旋转变换以及缩放变换。

现取 $m=3$ ，图4给出在三个不同插值点下生成的三角枫叶，其目标枫叶的IFS码见附录的附表6。

图4. 给定三个插值点生成的三角枫叶

图5. 分形树叶。前两幅图是改变IFS码的三角叶，后两幅是改变叶子数得到的五角叶

为了使图形更加丰富多彩，可以通过修改IFS码或者改变叶子的个数来生成其他形状的分形叶。在图5中，图a，图b是通过修改IFS码得到的。图c，图d是修改叶瓣数即令 $m=5$ ，其中c图中旋转角度分别为 $\frac{\text{π}}{6},-\frac{\text{π}}{6},\frac{5}{12}\text{π},-\frac{5}{12}\text{π}$ ，其中d图中旋转角度分别为 $\frac{\text{π}}{3},-\frac{\text{π}}{3},\frac{5}{4}\text{π},-\frac{5}{4}\text{π}$ 。

5. 结论

在利用IFS方法进行树木模拟过程中，通过IFS码对给定图像的第一次应用可以揭示仿射变换的收缩性质，分析了各仿射变换参数对分形图的影响效果，根据需求可以人为地设定仿射变换的个数以及相应的参数继而得到相应的IFS码，生成形态各异的分形树。但在生成具有相似叶瓣的分形树叶的时候，其中的仿射变换个数较多，不易于实现。根据其叶片的相似性，利用拟仿射变换可以实现分形图的平移、旋转、缩放、错切变换，生成了三角枫叶和五角枫叶。通过不同的变换组合方式，可以生成各式各样的图案。

基金项目

陕西省自然科学基础研究计划项目(2016JM6056)。

文章引用

李彩云,郑红婵,林增耀. 基于迭代函数系统的分形植物模拟
Simulation of Fractal Plant Based on Iteration Function System[J]. 应用数学进展, 2018, 07(01): 128-138. http://dx.doi.org/10.12677/AAM.2018.71016

参考文献 (References)