分形图形的模拟实现.doc

分形图形的模拟实现摘要通过对分形理论的认识和相关定理的理解，做出了一些比较典型的分形图形并实现了自己想象中的一批奇特的图形。简要介绍迭代函数系统的基本理论，讨论了IFS码的提取方法，并且分别实现了典型的Koch曲线、koch雪花和拓展的Koch曲线；同时利用随机迭代函数系统实现了蕨类植物图形模拟，并讨论了概率的选取对产生分形图的影响；在复平面上的Mandelbrot集和Julia集是分形图形很有趣的一个领域，利用逃逸时间算法，实现了上述两种图形，并利用Matlab强大的图像处理能力，对其进行着色处理，得出了丰富多彩的分形图形；另外，也实现了广义的Mandelbrot集和Julia集。同时对二者之间的关系也有了新的认识。关键词：分形图形；仿射变换；迭代函数系统；Matlab；Koch曲线；逃逸时间算法；Mandelbrot集；Julia集A simulative realization of a fractal graphicsAbstractBased on the cognition of fractal theory and the understanding of theorem concerned, some typical fractal graphics and a set of imaginary graphics have been realized in this article. The theory of Iterated Function Systems(IFS) was concisely described and the parameter design of IFS was discussed. Koch curve, Snow graphics and Generalized-Koch curve were realized afterwards. Meanwhile, by means of IFSP, fern graphics was simulated and the probability of the attractor of IFS were discussed. In plural plane, Mandelbrot set and Julia set are a very interesting field, the above two graphics have been realized through the escape time algorithm, Color up the image by powerful image processing ability of Matlab, and some rich and colorful fractal graphics were realized. Besides, the paper realized generalized Mandelbrot set and Julia set, got some wonderful graphics. at the same time we have new understanding about the relationship of the both sets.Keywords: fractal graphics; affine transformation; IFS; escape time algorithmMatlab; Koch curve; Mandelbrot set; Julia set第一章 引 言自然界是复杂和美丽的。过去由于理论计算和实验技术的局限，科学家们无法对自然界做完美的描述；传统的科学只能把复杂的问题简化成为一个线性问题来研究。对自然界中出现的非线性现象也只能按线性理论作一定的微扰处理。而如今由于分形理论研究的逐步深入以及计算机学科的突飞猛进，使得这二者得以完美的结合，我们获得了许多过去难以想象的分形图形的模拟实现2。本文旨在利用分形理论的研究成果帮助我们实现一系列复杂的自然景物图像的模拟实现，这些景物有的具有良好的自相似性，有的则看似无章可循，但它们都是我们分形理论的研究对象，因此如果将分形理论与计算机相结合，实现这些图像还是很得心应手的。本文并没有对分形理论有过多的阐述，而是利用分形理论的一些成熟的研究成果，实现了对分形图形的模拟，特别是利用L系统，迭代函数系统(IFS系统)可以对这些图形作出很好的模拟，甚至可以实现一些现实中不存在，但又奇妙异常的图形。分数维图形可以模拟天际的积云、空中的闪电、地上的森林、海上的浪花、燃烧的火焰、树木的生长以及如分子、粒子的运动等物理现象。可以用分形图设计壁纸。地板革、地板砖、纺织品等日用品的图案。众所周知，迭代函数系统是构造分形图的重要方法之一，IFS为计算机模拟一些自然现象的真实感图形提供了一个有力的工具。特别是利用带有概率的IFS即IFSP算法绘制分形图，与单纯迭代法绘图相比，不仅实现的代码简单，而且降低了对计算机硬件的要求5。这篇论文分为四章，第二章主要介绍了分形理论的的相关背景和其应用，第三章则主要介绍了迭代函数系统（IFS），因为这是实现分形图形的重要理论基础，接着提供了一些常用的提取IFS码的方法；第四章则围绕这篇论文的主题分形图形的模拟实现，给出了分形图形实现算法，同时由于IFS码的重要性，又添加了一个提取IFS码的实例，增加文章的可读性；第五章，则对分形图形中十分重要的Mandelbrot集和Julia集进行了实现并对广义的M集和J集。最后我们通过MATLAB编程实现算法，并将一批典型的比较经典的分形图成功的实现了。第二章 分形理论相关背景及应用21分形理论的介绍分形(fractal)这个名词是Mandelbrot在20世纪70年代为了表征复杂图形和复杂过程首先引入自然科学领域的，它的原意是不规则的，支离破碎的物体。分形可以分为规则分形和不规则分形。在分形名词使用之前，一些数学家就提出过不少复杂和不光滑的集合，如Cantor集,Koch曲线,Sierpinski垫片，地毯和海绵等。这些都属于规则的分形图形，它们具有严格的自相似性。而自然界的许多事物所具有的不光滑性和复杂性往往是随机的，如蜿蜒曲折的海岸线；变换无穷的布朗运动轨迹等。这类曲线的自相似性是近似的或统计意义上的，这种自相似性只存在于标度不变区域，超出标度不便区域，自相似性不复存在。这类曲线为不规则分形。迄今为止，分形还没有一个严格的定义。1982年Mandelbrot将分形定义为Hausdorff维数大于拓扑维数的集合。1986年，Mandelbrot给出了一个更广泛，更通俗的定义：分形是局部和整体有某种方式相似的形，该定义强调图形中的局部和整体之间的自相似性。一般认为分形是一个具有以下性质的集合F1） F具有精细结构，即在任意小的比例尺度内包含整体。2） F是不规则的，以至于不能用传统的几何语言来描述。3） F通常具有某种自相似性，或许是近似的或许是统计意义下的。4） F是某种方式下定义的“分维数”通常大于F的拓扑维数。5） F的定义常常是非常简单的，或许是递归的。自相似分形是具有几何相似的分形，它的特点是局部与整体具有一定比例的几何相似性，利用这种自相似性，可用迭代函数来描述它的位置，图形。说道分形，就要提到几何图形的维数，一般将维数理解为图形中确定一个点的位置需要的坐标数，如直线维数是1；方形，圆，椭圆等平面图形维数是2；立方体，球等立体图形的维数是3。我们也可以将Hausdoff测定分形维数的方法加以推广，利用以下的公式从测度的角度把规则图形的维数D确定为 公式1这里的是测量单元的尺寸，N()是测度得到的规则图形的测量单元数，的缩小使N()增大。如由1减小为1/2n时，测量正方形得到的N()由1增大为4n，由上式得到维数2；如由1减小为1/2n时，测量立方体得到的N()由1增大为8n得到维数为3。不规则分形只具有统计意义下的自相似性。不规则分形种类繁多，它可以是离散的点集、粗糙曲线、多枝杈的二维图形、粗糙曲面、以至三维的点集和多枝杈的三维图形。目前测定不规则分形的方法很多，主要有：粗糙曲线的圆规维数、从周长面积关系或表面积体积关系求分维、盒维数法、Sandbox法、面积回转半径法、变换(Variation)法、密度密度相关函数法等22.2分形理论的应用分形理论是一门新兴的非线性科学，它给自然科学、社会科学、工程技术、文学艺术等极广泛的学科领域，提供了一般的科学方法和思考方式。就目前所知，它有很高程度的应用普遍性。这是因为，具有标度不变性的分形结构是现实世界普遍存在的一大类结构。此处结构的含义十分丰富，它不仅指研究对象的空间几何形态，而是一般地指其拓扑维数(几何维数)小于其测量维数的点集，如事件点的分布，能量点的分布，时间点的分布，过程点的分布，甚至可能是意识点、思维点的分布。 分形几何学已在自然界与物理学中得到了应用。如在显微镜下观察落入溶液中的一粒花粉，会看见它不间断地作无规则运动（布朗运动），这是花粉在大量液体分子的无规则碰撞下表现的平均行为。布朗粒子的轨迹，由各种尺寸的折线连成。只要有足够的分辨率，就可以发现原以为是直线段的部分，其实由大量更小尺度的折线连成。这是一种处处连续，但又处处无导数的曲线。这种布朗粒子轨迹的分维是 2，大大高于它的拓扑维数 1。在某些电化学反应中，电极附近成绩的固态物质，以不规则的树枝形状向外增长。受到污染的一些流水中，粘在藻类植物上的颗粒和胶状物，不断因新的沉积而生长，成为带有许多须毛的枝条状，就可以用分维。自然界中更大的尺度上也存在分形对象。一枝粗干可以分出不规则的枝杈，每个枝杈继续分为细杈，至少有十几次分支的层次，可以用分形几何学去测量。有人研究了某些云彩边界的几何性质，发现存在从 1公里到1000公里的无标度区。小于 1公里的云朵，更受地形概貌影响，大于1000公里时，地球曲率开始起作用。大小两端都受到一定特征尺度的限制，中间有三个数量级的无标度区，这已经足够了。分形存在于这中间区域。近几年在流体力学不稳定性、光学双稳定器件、化学震荡反映等试验中，都实际测得了混沌吸引子，并从实验数据中计算出它们的分维。学会从实验数据测算分维是最近的一大进展。分形几何学在物理学、生物学上的应用也正在成为有充实内容的研究领域第三章 如何提取IFS码3.1 IFS基本理论对于分形空间上的压缩映射，其压缩因子.定义映射，即：公式2则W是压缩映射，且压缩因子，即：。公式3由这n个压缩映射，及其压缩因子组成一个迭代函数系统IFS。压缩映射不动点定理：设是上的一个IFS，压缩变换W存在唯一的不动点，满足，而且不动点可以通过迭代得到，即。拼贴定理：给定集合和0,若能找到一个IFS使，则：公式4其中：是IFS不动点，亦即吸引子。该理论说明，对于L，如能找到一个IFS，使L恰为IFS的吸引子，则L完全由IFS确定。根据不动点是复制它本身的变换构造出来的，因此，对L进行压缩变换，然后把它们粘贴到一起，用“拼贴”近似表示L。53.2 主要提取方法已有的提取IFS码的方法对于规则的图形如我们熟知的Sierpinski垫片，因为我们已经知道压缩仿射变换中的六个参数所起的作用，再根据图形本身的几何关系，其IFS码可以比较容易的得出。对于不规则但具有分形特性的图形提取IFS码的方法主要有以下几种：最初的方法对那些经典的已知的某景物的IFS参数，改变它的某些参数值或加入随机因素来得到此景物新的IFS参数，然而对那些无已知参数的景物就无能为力了。2三点法我们知道，一般具有分形特征的自然景物图形，它必然存在一些有特征性的点。由于整体和局部的相似性， 整体存在一些有特征性的点， 局部也必然相应地存在一些有特征性的点。由于局部是由整体仿射变换而来，则局部上的一些有特征性的点必然也是由整体上的一些有特征性的点经过同样的仿射函数变换而来。同时我们还知道， 通过三对点(整体上的三个点和局部上对应的三个点)， 我们就可求出一个仿射变换。基于这个道理， 我们只要在整体轮廓上选取三个有特征性的点，然后再在各个局部轮廓上按相同的顺序选取对应的三个有特征性的点。这样根据这些点，就可以获得整体到各个局部的仿射变换。具体步骤如下:1.在原图上取三点：，然后在每一个拼贴子图上相应的取三点: 。选取点时注意：选取的三点最好不使之形成钝角三角形,并尽量能体现图形的整体信息,如选最上、最左、最右或最下的三点小拷贝上点的位置要尽量与整体上点的位置相对应,即小拷贝上取的三点尽量为整体上的三点在压缩映射作用下在小拷贝上的象。2.将这六个点分别代入公式公式5 其中，为原图坐标，为拼贴子图坐标。3.采用三点对应解线性方程组的方法来求取仿射变换系数。4.各个仿射变换的概率可以通过计算得到，最后应对概率集归一化，使其和。至此可得到所求的IFS码。6第四章 分形图形算法的得出根据以上理论事实并参考相关文献，我们得出了对于一般分形图形实现的算法。对于分形图形，一种我们可以利用线段拟和，只需确定两点坐标位置，连线画出即可，另一种则需要根据图形特征，逐步分析提取IFS码，并利用概率分布，得到IFSP码，用点模拟，因此我们提供了两种算法，分别针对上述两种图形的模拟实现。对于规则的自相似图形，典型的有分形树，Koch曲线等，由于它们都具有良好的自相似性，并且显然的直线性，因此只要找出它们的递归特性就可以利用递归函数，采用线段拟和，递归出口为线段长度的一个限值。对于不规则的分形图形，比如蕨类植物，Levy曲线等，我们则可以利用上一章提到的提取IFS码，找出图形的统计自相似性，再利用迭代函数逐步的用点拟合。4.1 具有严格自相似性分形图形的算法我们选择具有代表性的分形树为例，我们观察到二维分形树的树干和树枝具有良好的自相似性，即图形局部放大后可以与整体等同。构造一个递归函数，给出两个象素点的位置便可将两点连线画出，递归出口为线段长度的一个限值，可以根据需要和硬件条件设定，具体思路如下：n 首先，我们向函数传递的是树根或树枝末端点坐标以及线段长度、与横坐标所夹角度，通过函数调用得到的是树顶或树枝顶端点坐标：假定A(x1,y1)为枝末节点，B(x2,y2)为枝顶节点,AB与主枝所夹角度为，亦即相对角度，l为树枝长度，则进而我们得出,利用这一方程组，我们就可以根据A点坐标、线段长度、所夹角度将B点坐标求出，两点连线AB即为所求。n 然后，我们注意到AB既可看为主枝，又可视为侧枝，这是又自相似性决定的，满足了递归的性质：在AB上取一点A1作为树根或枝末节点，偏转角度选定，线段长度确定，同理亦可得到树顶或枝顶节点B1，连线画出，接着再在上取点画线，依此类推，直至线段长度小于某一限值，这时便将分形树描绘出。在我的程序里，我将每一最小相似形中的主枝上设定了最多为七棵侧枝。得出图形：图1：分形树4.2 利用IFS码/IFSP码模拟图形的算法迭代函数系统IFS的理论和方法是分形自然景观模拟的理论基础。迭代函数系统采用确定性与随机性相结合的方法生成植物秆茎或叶片。“确定性”指用以迭代的规则是确定性的，它们由一组仿射变换构成；“随机性”指迭代过程是不确定的，每一次迭代用哪一个规则，不是预先定好的，而是随机的。设最终要生成的图形为M，它要满足下述几何方程：公式6上式含义是，随机地从中挑选一个迭代规则迭代一次，然后在随机地在中选一个规则迭代下一次，不断重复此过程，最后生成地极限图形M就是欲求地形态。具体的提取IFS码，可以参照上一章，这里我们再简单的描述一下。IFS的压缩映射的参数设计由分形图的相似结构，每个压缩映射是由平移、旋转和比例3种变换以及它们的复合变换构成的仿射变换，二维形式为：公式7其中参数由旋转、比例变换所决定的实数；由平移变换所决定的实数。IFS吸引子自然景观的模拟总是在一个矩形区域内进行，取度量空间，由于。因此，参数的取值范围在；的取值影响植物x方向的偏离程度，一般取值为正。在平面欧氏空间R2中，仿射变换有下面两种形式：1公式8公式9其中称为转角，r是相似比。相似变换可以分解成以下四种基本的相似变换：1(1) 旋转变换：公式10它是绕坐标原点逆时针旋转角度的变换。(2) 反射变换R：公式11它是以x轴为反射壁的变换。(3) 伸缩变换：公式12它是沿极线方向伸缩r倍的变换。(4) 平移变换T：公式13这样上述相似变换可以分别写成这些基本变换的复合：公式14下面举Koch曲线为例： 它可以看成是一单位长线段经过下列4个仿射变换迭代生成。1. 缩小至原长1/3；伸缩变换,2. 缩小至1/3:;旋转60o:;右平移1/3:； 得出IFS码 3. 缩小至1/3: ；旋转-60o：；右平移1/2，上移：；得出IFS码：4. 缩小至1/3: ;右平移2/3: ;。生成的IFS码如下：利用以上分析，我们得出Koch曲线的IFS码表1：Koch曲线IFS码abcdefW11/3001/300W21/6-0.2880.2881/61/30W31/60.288-0.2881/61/20.288W41/3001/32/30得出的曲线 图2：Koch曲线接下来，我们利用这里的方法作出一个新的分形图形，同样是先提取IFS码，然后利用迭代函数迭代画出图形，程序与Koch曲线的得出基本相同，只是提取出的IFS码不同，结果如下：表2：Snow图形IFS码abcdefW11/3001/300W21/60.288-0.2881/61/60.288W3-1/60.288-0.288-1/61/20.288W4-1/300-1/32/30W5-1/6-0.2880.288-1/61/2-0.288W61/6-0.2880.2881/61/6-0.288 图3：Snow图形 作图中要注意的是可能分枝方向会弄错，例如可能会把雪花一半向内生长，一半向外生长，这时可以考虑旋转角度加大180o。 图4：Sierpinski地毯表3：Sierpinski地毯IFS码abcdefW11/2001/200W2-1/40.433-0.433-1/41/40.433W3-1/4-0.4330.433-1/41/20扩展的Koch曲线 图5：扩展的Koch曲线而在自然景物的模拟中，我们则需要用到IFSP码，这是一种随机算法，具体步骤如下：1o 取初始点，及总的迭代步数；2o 以概率选取变换；3o 把作用到上，得新点，记;4o 令5o 重返2o，进行下一次迭代。当迭代次数大于某预先给定的数，开始在屏幕上打出点。直到迭代大于总步数为止。流程图如下：2开始仿射变换系数设定设定起始点(x0,y0)，总迭代步数N，总点数M产生一随机数决定用第几个Ri机器解释，绘图(x1,y1)=Ri(x0,y0)x0=x,y0=y1,n=n+1nN?No打印(x0,y0),m=m+1YesmM?结束YesNo图6：IFSP流程图关于IFSP码的构造，这里就不再深入探究了。这里就利用现成的比较成功的IFSP码，如蕨类植物：2表4：蕨类植物IFSP码abcdefpW10000.170000.01W20.155-0.2350.1960.18600.90.07W3-0.1550.2350.1960.18600.40.07W40.8500.025-0.0250.85000.90.85下面我们就利用这IFSP码编程对蕨类植物图形进行模拟，在MATLAB下已实现。具体程序见附录B，迭代次数为100000次。这里要注意：理论上讲仿射变换的概率不会影响最终的迭代结果，只要满足：的大小分配并不影响最终吸引子，也就是绘制的图形完全由确定，与无关，只是为编程绘图提供了极大的方便，的大小分配只影响绘图的速度，即迭代次数。例如我们可以选择每个迭代函数概率相同，这样我们得到如下图形，迭代次数为1000000次查阅相关资料，我们得出各个仿射变换的概率可以通过计算得到，最后对概率集归一化，使其和。至此可得到所求的IFSP码。利用这一原则，我们对的概率加以计算得出 图7：蕨类植物第五章 Mandelbrot集和Julia集生成上面介绍的一些二维迭代是在实平面上进行的。在复平面上，我们则可以得出更加丰富多彩的图形，典型的有Mandelbrot集和Julia集图形。5.1 Julia集的定义与生成Julia集是由法国数学家Julia和Faton在发展了复变函数迭代理论的基础上获得的。在复平面C上，利用复变函数迭代可生成一个非常复杂的集。6 令由可得公式15迭代过程中，如固定参数c，而考虑z得变化，则称Z平面为动态平面，按上式反复迭代得到得数集，称为Julia集。在进行迭代时，每次以新得坐标替代旧坐标进行下一次迭代。为了观察逃离速度，可以规定一个距离函数8计算例如D20所需迭代次数，如果某点经过300次迭代仍未逃离，就可以认为它属于J集，对于趋于内部得点也可以类似处理。在计算机上画映射的Julia集可用逃逸时间算法，算法如下：11. 选定参数,取，取R充分大。定义发散区域，当某轨道进入区域V时，就认为该轨道是发散的。设。10对所有象素点完成下面过程。2. 设3. 作迭代：利用迭代方程 作迭代，由计算，k=k+1;4. 作判别：计算，(i) 若rR,取颜色k，转到第4步；(ii) 若kK，取颜色0，转到第4步；(iii) 若rR，且kK,回到第2步。5. 在象素点(i,j)上着第k种颜色，转到下一个点并从第1步开始。下面我们就可以利用这一算法得出美妙的Julia集了! 下图是C-0.20.75i时作出的Julia集图形，右图是根据迭代次数的不同所着颜色的彩色Julia集图形。具体程序参考附录。 图8：C-0.20.75i, 图9：C=0.364+0.111i,5.2 Mandelbrot集的定义与生成Mandelbrot集被认为是把自相似的外形与无限变化的性质结合起来的一个分形。J集是给定C后对复变量Z进行分类；而M集则是在复参数C填充的平面上对参数C进行分类得到的图形。生成Mandelbrot集的具体算法与Julia集基本相同，得出的图形如下： 图10：Mandelbrot集具体算法见附录。5.3 广义Julia集与Mandelbrot集 通过上述Julia集和Mandelbrot集的研究，我不禁想到了对二次Julia函数和Mandelbrot函数进行拓展，如三次，四次乃至n次函数，只要利用一定的复变函数知识对多次复变函数进行展开，实部与虚部分开，参照二次情形便可得出。限于篇幅，这里只对三次Julia集和Mandelbrot集进行一下模拟实现，得出了另一组神奇的分形图形。 图11：C-0.20.75i,图12：三次的Mandelbrot集可以看出三次的Julia集和Mandelbrot集依然具有自相似性，不过图形已经与二次完全不同了，只要愿意我们可以作四次，五次，乃至n次的Julia集或Mandelbrot集。得出的图形也是奇妙异常。第六章 结论1. 在利用IFS码实现分形图形中，我发现，利用仿射变换仅仅能对长度单位为1的线段进行迭代并实现图形，这就有很大的制约，在实现Julia集时得到启示，我们可以利用坐标，如对Koch曲线：设得出 PACQB这样得出各点坐标，然后连线画出，这比单纯利用IFS码方便并且可以适应其它情形，如任意给定两点坐标和迭代次数便可得出Koch曲线。2. Mandelbrot集与Julia集有着千丝万缕的联系，首先它们都具有自相似性，Mandelbrot集的另一个特性是在M集中任选一点C，通过把它附近越来越小的片断放大，就会找到对应于这个C值的J集。换句话说，M集概括了所有的J集，它是无穷数量的J集的直观的图像目录表。因此常常把M集称为是J集的缩微字典。2附录附录A：分形树模拟实现程序：function Ftree(x,y,length,fai)clcg=0.618;thita=60.0;x1=x-length*cos(fai*pi/180.0);y1=y+length*sin(fai*pi/180.0);plot(x,x1,y,y1);axis equalhold all;if(length4 returnendx11=0.333*x;y11=0.333*y;x12=0.167*x-0.288*y+0.333;y12=0.288*x+0.167*y;x13=0.167*x+0.288*y+0.5;y13=-0.288*x+0.167*y+0.288;x14=0.333*x+0.667;y14=0.333*y;if i=4 hold all; axis equal; plot(x11,y11); plot(x12,y12); plot(x13,y13); plot(x14,y14);endKoch(x11,y11,i);Koch(x12,y12,i);Koch(x13,y13,i);Koch(x14,y14,i);蕨类植物模拟实现程序：clc,clear;a=0,0.85,0.2,-0.15;b=0,0.04,-0.26,0.28;c=0,-0.04,0.23,0.26;d=0.16,0.85,0.22,0.24;e=0,0,0,0;f=0,1.6,1.6,0.44;p=0.01,0.85,0.07,0.07;% p=0.25,0.25,0.25,0.25;x=0;y=0;M=420;N=480;I=ones(M,N);for i=1:100000 k=1; rn=rand(1); total=p(1); while total200) dx=floor(x*40+100); dy=floor(450-y*40); I(dx,dy)=0; endendimview(I);Julia集实现程序：clc,clearM=600;N=600;cx=0.364; 实部