分形之Julia集及其算法实现

《智能信息处理概论》结课论文1成绩：课程名称：智能信息处理概论分形之Julia集及其算法实现摘要：本文从自然界的几何现象引出分形的概念，再从其定义、几何特征和分形维的计算这三个方面来加以介绍。以Julia集和Mandelbort集为例来具体描述分形。本文主要从Julia集的特点和算法实现来描述分形以及其实现的方法。关键词：分形、分数维、Julia集、Mandelbort集、算法实现引言大自然是个很伟大的造物者，它留给我们一大笔美丽景观：蜿蜒曲折的海岸线、起伏不定的山脉，变幻无常的浮云，粗糙不堪的断面，袅袅上升的烟柱，九曲回肠的河流，纵横交错的血管，令人眼花缭乱的满天繁星……那么，我们又能从这些美妙的自然现象中得到什么有趣的结论呢？正文分形概述分形的英文单词为fractal，是由美籍法国数学家曼德勃罗（BenoitMandelbrot）创造出来的。其取自拉丁文词frangere（破碎、产生无规则碎片）之头，撷英文之尾所合成，本意是不规则的、破碎的、分数的。他曾说：分形就是通过将光滑的形状弄成多个小块，反复的碎弄。1975年，曼德勃罗出版了他的法文专著《分形对象：形、机遇与维数》，标志着分形理论正式诞生。【1】两种定义其一：具有自相似性结构的叫做分形；其二：数学定义：豪斯道夫维Df=拓扑维Dt。若一有界集合，包含N个不相重叠的子集，当其放大或缩小r倍后，仍与原集合叠合，则称为自相似集合。自相似集合是分形集。具有相似性的系统叫做分形。当放大或缩小的倍数r不是一个常数，而必须是r（r1，r2，….）的各种不同放大倍数去放大或缩小各子集，才能与原集合重合时，称为自仿射集合。具有自仿射性的系统叫做分形。【2】特征1.自相似性：局部与整体的相似，是局部到整体在各个方向上的等比例变换的结果；2.自仿射性：是自相似性的一种拓展，是局部到整体在不同方向上的不等比例变换的结果；3.精细结构：即使对该分形图放大无穷多倍，还是能看到与整体相似的结构，表现出无休止的重复；4.分形集无法用传统几何语言来描述，它不是某些简单方程的解集，也不是满足某些条件的点的轨迹；5.分形集一般可以用简单的方法定义和产生，如递归、迭代；分形其实是由一些简单的图形，经过递归或者迭代产生的复杂、精细的结构；6.无确定的标度且具有分数维数。【3】《智能信息处理概论》结课论文2分数维拓扑维：又称橡皮几何学。研究几何图形在一对一的双方连续变换下不变的性质，称为拓扑性质。豪斯道夫维数：1919年提出连续空间的定义：即空间维数不是跃变的，而是可以连续变化的，既可以是整数，也可以是分数，通过具体计算来确定维数。——分数性质豪斯道夫维数有三种求解方法：1.放大求解：豪斯道夫维的几何对象，每个棱边长度放大L倍，几何对象对应放大K倍。那么，由，可推导出。2.缩小求解：豪斯道夫维的几何对象，等分成N个小的几何图形，则每个小图形每维缩小为原来的r维。而N个小图形的总和应为。那么，分维为。3.测量学求解：对一个体积为A，分维为的几何对象，要用半径为r的小球去测度，则所需小球数目为。其中，C为结构因子。所以分维为。这里的分维也称为科尔莫哥诺夫容量维。定义容量维为，且其与相一致。各棱边放大L倍，相应的几何对象体积放大K倍，则所需小球数目应为。若小球半径r缩小L倍，而A保持不变，则所需小球数目仍应为N’。那么所需小球数目的表达式应为。由上述两个式子可得。即可得到结论容量维与豪斯道夫维相一致。【4】分形举例——Julia集Julia集是由法国数学家GastonJulia和PierreFaton在发展了复变函数迭代的基础理论后获得的。其也是一个典型的分形，只是在表达上相当复杂，难以用古典的数学方法描述。Julia集与Mandelbort集来自于复数非线性映射。通过给定的不同初始值，经过无穷次的迭代产生的分形图集。当C给定初始值，而Z值作为一个变量，通过无数次迭代产生的分形图集称为Julia集;当Z给定初始值，而C值作为一个变量，通过无数次迭代产生的分形图集称为Mandelbort集。特点对于映射而言，若,,则有二维映射例如取C=0+0i，则有以下情况发生：《智能信息处理概论》结课论文3如果，则在复Z平面上迭代结果；那么，零是的吸引子。复平面上所有与该吸引子相距小于1的点，都产生趋向吸引子的序列。如果，则在复Z平面上迭代结果；那么，无穷是的吸引子。复平面上所有与零点的距离超过1的点，都产生趋向无穷的序列。如果，则；那么，产生的序列总出现在上面两个吸引区域之间的边界上。此时，边界恰为复平面上的单位圆周，就是Julia集。然而，当时，其吸引子不再是0，而变为一个区域，被吸进去的点会遍历整个区间，这个区域被称做混沌区。与此同时，分割混沌区和向逃逸的分界线不再是单位圆，而是一个不规则、非光滑的分界线。当C值越来越大时，复平面上甚至会产生几个离散的吸引区域，而每个孤岛的分界线都是不滚则和不光滑的。Julia集的实际例子是求解三次方程。三个根的Newton迭代法是：或。上述式子的三个根是1，和，即该式有三个吸引子。那么，从复平面上任何地方的初值开始迭代，最终应该滑到其中的一个吸引子。自然而然，我们所得到的三个吸引区的边界也应该是简单，明显的。然而，绘图时发现，三个扇形区域的边界具有一种特别的性质，即上面的每个点都隔开所有三个区域，形成了一种复杂的边界。当我们把这边界放大时，又会形成自相似的结构。因此，Julia集通常被认为具有分数维结构，并且在这个集上的迭代过程是一种混沌运动。刚刚，Julia集是在复数平面上考虑的；那么，让我们从复参数平面上进行。此时取定，经过无数次迭代产生的使有界的点集就是Mandelbort集。【5】【6】逃逸时间算法Julia集是复数映，当C为某一固定值时的一个吸引域，其中,,则有二维映射。从逃逸时间算法的角度看，Julia集的内部收敛于某一点或某几个点，而Julia集的外部随着逃逸时间t的增加将发散至，其逃逸边界便是Julia集。我们可以根据点逃向的速度决定逃逸区中个点的着色。设计思路：假设绘图窗口的图形分辨率是点，可显示颜色K+1种，以数字0~K表示，且0表示黑色。1.选定参数，,M=100;令,,对所有的点,及，完成如下步骤的循环。2.令,,t=0。3.根据下式的迭代过程从算出，计数t=t+1。4.计算：如果,则选择颜色t，转至步骤5；如果,则选择颜色0（黑色），转至步骤5；如果且则转至步骤5。5.对点着颜色t并转至下一点，再从头做步骤5。【7】【8】程序设计：《智能信息处理概论》结课论文4CJuliaView::CJuliaView(){//TODO::addconstructioncodehereK=100;//逃逸时间m=500;//逃逸半径Mx=800;My=600;//绘图范围xs=-1.5;x1=1.5;ys=-1.5;y1=1.5;//复平面上C的坐标p=0.32;q=0.043;}voidCJuliaview::OnDraw(CDC*pDC){CJuliaDoc*pDoc=GetDocument();ASSERT_VALID(pDoc);//TODO:adddrawcodefornativedataherexb=(x1-xs)/Mx;yb=(y1-ys)/My;for(nx=0;nx=Mx;nx++){for(ny=0;ny=My;ny++){x0=xs+nx*xb;y0=ys+ny*yb;k=0;loop1:xk=x0*x0-y0*y0+p;yk=2*x0*y0+q;k=k+1;r=xk*xk+yk*yk;x0=xk;y0=yk;if(rm){H=k;gotoloop2;}If(k==K){H=int(r*10);gotoloop2;}If(r=m&&kK)gotoloop1;loop2:pDC-SetPixel(nx,ny,H*1000);}}}在JuliaView.h文件夹定义变量如下：public:doublex1,xs;doubley1,ys;doublex0,y0;doublexb,yb;doublexk,yk;doubler;doublep,q;intH,K,k,m;intMx,My;intnx,ny;《智能信息处理概论》结课论文5c=0.194-0.6557ic=0.31+0.04ic=-1.25c=-0.12+0.74i复平面上的IFS算法：相似变换是指在各个方向上变换的比率必须相同的一种比例变换，仿射变换是指在不同方向上变化的比率可以不同的一种比例变换。相似变换可放大或缩小甚至旋转，但不变形；而仿射变换可能会变形。仿射变换的数学表达式为其中，代表仿射变换，x和y是变换前图形的坐标值，和是变换后的图形的坐标值；a,b,c,d,e,f是仿射变换系数。对于一个比较复杂的图形，可能需要多个不同的仿射变换来实现，放射变换族控制着图形的结构和形状，由于仿射变换的形式是相同的，所以不同的形状取决于仿射变换的系数。另外，仿射变换族中，每一个仿射变换被调用的概率是不一定等同的，也就是说，落入图形各部分中点的数目是不一定相同，这就引入了一个新的量，即仿射变换被调用的概率P。从而，6个仿射变换系数（a,b,c,d,e,f）和一个概率（P）便组成了IFS算法最关键的部分——IFS码。设计思路：对于复映射，设为给定点，我们寻找Z使得，由此给出两个反函数，即和。则可以将看成是一个IFS，然后取概率,分别画。具体步骤如下：《智能信息处理概论》结课论文61.当k=0(k为迭代的次数)时，压栈，画点Z0；2.从栈顶取一点（Z，k）；3.根据概率，分别计算和，画点，将压栈，令；4.重复步骤3直至；5.画点和；6.判断栈是否为空，若栈空，则停止，否则重复2~6。【9】【10】程序设计：///CJULIAViewdrawingvoidCJULIAView::OnDraw(CDC*pDC){CJULIADoc*pDoc=GetDocument();ASSERT_VALID(pDoc);//TODO:adddrawcodefornativedataherefloatk;for(i=0;i32000;i++){m=(int)(2000/15*x+3500/15);n=(int)(2000/15*y+3000/15);if(i10)//CClientDCpDC(this);pDC-SetPixel(m,n,m_pColor);wx=x-cx;wy=y-cy;if(wx0)theta=atan(wy/wx);if(wx0)theta=PI+atan(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);elser=-sqrt(r);x=r*cos(theta);y=r*sin(theta);}///CJULIAViewmessagehandlersvoidCJULIAView::OnParamSet(){//TODO:AddyourcommandhandlercodehereCCsetParadlg;cx=dlg.m_cx;cy=dlg.m_cy;x=dlg.m_x;y=dlg.m_y;}Invalidate();}结论分形是一种由简单的直线或者方程通过无穷次简单的迭代形式而产生的具有无比精细的结构，这个过程又称之为混沌。其两者是密不可分的。《智能信息处理概论》结课论文7分形理论表现出两个重要原则——自相似原则和迭代生成原则。而这两种原则正是分形算法实现的重要依据。自然界的奥秘是无穷的，它还有许许多多的分形结构等着我们去探索、去发现。我们一定不能放慢脚步，要勇于创新，把大自然留给我们的宝藏发掘出来，为之己用！参考文献[1]作者：孙博文；书名[M]：分形算法与程序设计——VisualC++实现；版本：第一版；出版地：北京；出版者：科学出版社；出版年：2004年11月；起止页码：1-1