分形之Julia集及其算法实现

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业成绩： 课程名称：智能信息处理概论分形之Julia集及其算法实现摘要：本文从自然界的几何现象引出分形的概念，再从其定义、几何特征和分形维的计算这三个方面来加以介绍。以Julia集和Mandelbort集为例来具体描述分形。本文主要从Julia集的特点和算法实现来描述分形以及其实现的方法。关键词：分形、分数维、Julia集、Mandelbort集、算法实现引言大自然是个很伟大的造物者，它留给我们一大笔美丽景观：蜿蜒曲折的海岸线、起伏不定的山脉，变幻无常的浮云，粗糙不堪的断

2、面，袅袅上升的烟柱，九曲回肠的河流，纵横交错的血管，令人眼花缭乱的满天繁星那么，我们又能从这些美妙的自然现象中得到什么有趣的结论呢？正文分形概述分形的英文单词为fractal，是由美籍法国数学家曼德勃罗（Benoit Mandelbrot）创造出来的。其取自拉丁文词frangere（破碎、产生无规则碎片）之头，撷英文之尾所合成，本意是不规则的、破碎的、分数的。他曾说：分形就是通过将光滑的形状弄成多个小块，反复的碎弄。1975年，曼德勃罗出版了他的法文专著分形对象：形、机遇与维数，标志着分形理论正式诞生。【1】两种定义其一：具有自相似性结构的叫做分形；其二：数学定义：豪斯道夫维Df=拓扑维Dt。

3、若一有界集合，包含N个不相重叠的子集，当其放大或缩小r倍后，仍与原集合叠合，则称为自相似集合。自相似集合是分形集。具有相似性的系统叫做分形。当放大或缩小的倍数r不是一个常数，而必须是r（r1，r2，.）的各种不同放大倍数去放大或缩小各子集，才能与原集合重合时，称为自仿射集合。具有自仿射性的系统叫做分形。【2】特征自相似性：局部与整体的相似，是局部到整体在各个方向上的等比例变换的结果；自仿射性：是自相似性的一种拓展，是局部到整体在不同方向上的不等比例变换的结果；精细结构：即使对该分形图放大无穷多倍，还是能看到与整体相似的结构，表现出无休止的重复；分形集无法用传统几何语言来描述，它不是某些简单方程

4、的解集，也不是满足某些条件的点的轨迹；分形集一般可以用简单的方法定义和产生，如递归、迭代；分形其实是由一些简单的图形，经过递归或者迭代产生的复杂、精细的结构；无确定的标度且具有分数维数。【3】分数维拓扑维Dt：又称橡皮几何学。研究几何图形在一对一的双方连续变换下不变的性质，称为拓扑性质。 豪斯道夫维数Df：1919年提出连续空间的定义：即空间维数不是跃变的，而是可以连续变化的，既可以是整数，也可以是分数，通过具体计算来确定维数。分数性质 豪斯道夫维数有三种求解方法：1.放大求解：豪斯道夫维Df的几何对象，每个棱边长度放大L倍，几何对象对应放大K倍。那么，由LDf=K，可推导出 Df=lnKln

5、L。2.缩小求解：豪斯道夫维Df的几何对象，等分成N个小的几何图形，则每个小图形每维缩小为原来的r维。而N个小图形的总和应为NrDf=1。那么，分维为Df=lnNln1r。 3.测量学求解：对一个体积为A，分维为Df的几何对象，要用半径为r的小球去测度，则所需小球数目为Nr=ACrDf1rDf 。其中，C为结构因子。所以分维为Df=lnNrln1r。 这里的分维也称为科尔莫哥诺夫容量维。 定义容量维为Dcp=limr0lnNrln1r，且其与Df=lnNln1r相一致。各棱边放大L倍，相应的几何对象体积放大K倍，则所需小球数目应为 N=KArDf。若小球半径r缩小L倍，而A保持不变，则所需小球

6、数目仍应为N。那么所需小球数目的表达式应为 N=ArLDf。由上述两个式子可得 Df=lnKlnL。即可得到结论容量维与豪斯道夫维相一致。【4】分形举例Julia集Julia 集是由数学家 Gaston Julia 和 Pierre Faton 在发展了复变函数迭代的基础理论后获得的。其也是一个典型的分形，只是在表达上相当复杂，难以用古典的描述。Julia集与Mandelbort集来自于复数非线性映射fZ=Z2+C。通过给定的不同初始值，经过无穷次的迭代产生的分形图集。当C给定初始值，而Z值作为一个变量，通过无数次迭代产生的分形图集称为Julia集; 当Z给定初始值，而C值作为一个变量，通过无

7、数次迭代产生的分形图集称为Mandelbort集。特点对于映射Zn+1=Zn2+C而言，若C=Cr+iCi , Z=x+iy , 则有二维映射xn+1=xn2-yn2+Cryn+1=2xnyn+Ci例如取C=0+0i，则有以下情况发生：如果Z01，则在复Z平面上迭代结果Zn；那么，无穷是ZZ2的吸引子。复平面上所有与零点的距离超过1的点，都产生趋向无穷的序列。如果Z0=1，则Zn=1；那么，产生的序列总出现在上面两个吸引区域之间的边界上。此时，边界恰为复平面上的单位圆周Z=1，就是Julia集。然而，当C0时，其吸引子不再是0，而变为一个区域，被吸进去的点会遍历整个区间，这个区域被称做混沌区。

8、与此同时，分割混沌区和向逃逸的分界线不再是单位圆Z=1，而是一个不规则、非光滑的分界线。当C值越来越大时，复平面上甚至会产生几个离散的吸引区域，而每个孤岛的分界线都是不滚则和不光滑的。Julia集的实际例子是求解三次方程fZ=Z3+1=0。 三个根的Newton迭代法是：Zn+1=Zn-fZnfZn或Zn+1=Zn -Zn3-13Zn2。上述式子的三个根是1，-12+32i 和 -12-32i，即该式有三个吸引子。那么，从复平面上任何地方的初值Z0开始迭代，最终应该滑到其中的一个吸引子。自然而然，我们所得到的三个吸引区的边界也应该是简单，明显的。然而，绘图时发现，三个扇形区域的边界具有一种特别

9、的性质，即上面的每个点都隔开所有三个区域，形成了一种复杂的边界。当我们把这边界放大时，又会形成自相似的结构。因此，Julia集通常被认为具有分数维结构，并且在这个集上的迭代过程是一种混沌运动。刚刚，Julia集是在复数平面x，y上考虑的；那么，让我们从复参数平面Cr,Ci上进行。此时取定Z0，经过无数次迭代产生的使Zn有界的点集Cr,Ci就是Mandelbort集。【5】【6】逃逸时间算法Julia集是复数映ZZ2+C ，当C为某一固定值时的一个吸引域，其中C=p+iq , Z=x+iy , 则有二维映射xt+1=xt2-yt2+pyt+1=2xtyt+q。从逃逸时间算法的角度看，Julia集

10、的内部收敛于某一点或某几个点，而Julia集的外部随着逃逸时间t的增加将发散至，其逃逸边界便是Julia集。我们可以根据点x，y逃向的速度决定逃逸区中个点的着色。设计思路：假设绘图窗口的图形分辨率是ab点，可显示颜色K+1种，以数字0K表示，且0表示黑色。1.选定参数C=p+iq ，xmin=ymin=-1.5 , M=100 ; 令x=xmax-xmina-1 , y=ymax-yminb-1 , 对所有的点nx,ny , nx=0,1,a-1及ny=0,1,b-1，完成如下步骤的循环。2.令x0=xmin+nx*x , y0=ymin+ny*y , t=0。3.根据下式的迭代过程从xi,y

11、i算出xi+1,yi+1 ， 计数t=t+1。xt+1=xt2-yt2+pyt+1=2xtyt+q4.计算r=xt2+yt2 ： 如果rM , 则选择颜色t，转至步骤5； 如果t=K , 则选择颜色0（黑色），转至步骤5； 如果rM 且tK 则转至步骤5。5.对点 nx,ny 着颜色t并转至下一点，再从头做步骤5。【7】【8】程序设计：CJuliaView: :CJuliaView() /TODO: : add construction code here K=100;/逃逸时间 m=500;/逃逸半径 Mx=800; My=600;/绘图范围 xs= -1.5; x1= 1.5; ys= -

12、1.5; y1= 1.5; /复平面上C的坐标 p=0.32; q=0.043;void CJuliaview: :OnDraw(CDC* pDC) CJuliaDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); / TODO: add draw code for native data here xb=(x1-xs)/Mx; yb=(y1-ys)/My; for(nx=0;nx=Mx;nx+) for(ny=0;nym) H=k; goto loop2; If(k=K) H=int(r*10); goto loop2; If(r=m&kSetPixe

13、l(nx,ny,H*1000); 在Julia View.h文件夹定义变量如下：public: double x1,xs; double y1,ys;double x0,y0; double xb,yb; double xk,yk; double r; double p,q; int H,K,k,m; int Mx,My; int nx,ny;c =0.194-0.6557ic =0.31+0.04ic =-1.25c =-0.12+0.74i复平面上的IFS算法：相似变换是指在各个方向上变换的比率必须相同的一种比例变换，仿射变换是指在不同方向上变化的比率可以不同的一种比例变换。相似变换可放大

14、或缩小甚至旋转，但不变形；而仿射变换可能会变形。仿射变换的数学表达式为:x=ax+by+ey=cx+dy+f 其中，代表仿射变换，x和y是变换前图形的坐标值，x和y是变换后的图形的坐标值；a, b, c, d, e, f 是仿射变换系数。对于一个比较复杂的图形，可能需要多个不同的仿射变换来实现，放射变换族n控制着图形的结构和形状，由于仿射变换的形式是相同的，所以不同的形状取决于仿射变换的系数。另外，仿射变换族n中，每一个仿射变换被调用的概率是不一定等同的，也就是说，落入图形各部分中点的数目是不一定相同，这就引入了一个新的量，即仿射变换被调用的概率P。从而，6个仿射变换系数（a, b, c, d

15、, e, f）和一个概率（P）便组成了IFS算法最关键的部分IFS码。设计思路：对于复映射FZ=Z2+C ，设Z0为给定点，我们寻找Z使得FZ=Z2+C=Z0 ，由此给出两个反函数，即1Z=Z-C 和2Z=-Z-C 。则可以将1，2，C看成是一个IFS，然后取概率p1=p2=12 , 分别画1和2。具体步骤如下：1.当k=0(k为迭代的次数)时，压栈，画点Z0；2.从栈顶取一点（Z，k）；3.根据概率p1和p2，分别计算1Z=Z-C 和2Z=-Z-C ，画点1，2 ，将（1，k）压栈，令Z=1；4.重复步骤3直至k=N-1 ；5.画点Z-C 和-Z-C；6.判断栈是否为空，若栈空，则停止，否则

16、重复26 。【9】【10】程序设计：/CJULIAView drawingvoid CJULIAView: :OnDraw(CDC* pDC)CJULIADoc* pDoc = GetDocument();ASSERT_VALID(pDoc);/TODO: add draw code for native data herefloat k;for(i=0;i10) /CClientDC pDC(this); pDC-SetPixel(m,n,m_pColor); wx=x-cx; wy=y-cy; if(wx0) theta=atan(wy/wx);if(wx0) theta=PI+atan(

17、wy/wx); if(wx=0) theta=PI/2; theta=theta/2; r=sqrt(wx*wx+wy*wy); k=(float)rand(); rnd=(float)(k/RAND_MAX); if(rnd0.5) r=sqrt(r); else r=-sqrt(r); x=r*cos(theta); y=r*sin(theta);/CJULIAView message handlersvoid CJULIAView: :OnParamSet() /TODO: Add your command handler code here CCsetPara dlg; cx=dlg.

18、m_cx; cy=dlg.m_cy; x=dlg.m_x;y=dlg.m_y;Invalidate(); 结论分形是一种由简单的直线或者方程通过无穷次简单的迭代形式而产生的具有无比精细的结构，这个过程又称之为混沌。其两者是密不可分的。分形理论表现出两个重要原则自相似原则和迭代生成原则。而这两种原则正是分形算法实现的重要依据。自然界的奥秘是无穷的，它还有许许多多的分形结构等着我们去探索、去发现。我们一定不能放慢脚步，要勇于创新，把大自然留给我们的宝藏发掘出来，为之己用！参考文献1作者：孙博文； 书名M：分形算法与程序设计Visual C+实现； 版本：第一版；出版地：北京； 出版者：科学出版社； 出版年：2004年11月； 起止页码：1-1.2作者：林鸿溢、李映雪； 书名M：分形论奇异性探索； 版本：第一版；出版地：北京； 出版者：北京理工大学出版社； 出版年：1992年9月； 起止页码：62-63.3作者：孙博文； 书名M：分形算法与程序设计Visual