《智能信息处理概论》结课论文
成绩： 课程名称：智能信息处理概论
分形之Julia集及其算法实现
摘要：本文从自然界的几何现象引出分形的概念，再从其定义、几何特征和分形维的计算这三个方面来加以介绍。以Julia集和Mandelbort集为例来具体描述分形。本文主要从Julia集的特点和算法实现来描述分形以及其实现的方法。
关键词：分形、分数维、Julia集、Mandelbort集、算法实现
引言
大自然是个很伟大的造物者，它留给我们一大笔美丽景观：蜿蜒曲折的海岸线、起伏不定的山脉，变幻无常的浮云，粗糙不堪的断面，袅袅上升的烟柱，九曲回肠的河流，纵横交错的血管，令人眼花缭乱的满天繁星……那么，我们又能从这些美妙的自然现象中得到什么有趣的结论呢？
正文
分形概述
分形的英文单词为fractal，是由美籍法国数学家曼德勃罗（Benoit Mandelbrot）创造出来的。其取自拉丁文词frangere（破碎、产生无规则碎片）之头，撷英文之尾所合成，本意是不规则的、破碎的、分数的。他曾说：分形就是通过将光滑的形状弄成多个小块，反复的碎弄。1975年，曼德勃罗出版了他的法文专著
【1】
《分形对象：形、机遇与维数》，标志着分形理论正式诞生。
两种定义
其一：具有自相似性结构的叫做分形； 其二：数学定义：豪斯道夫维Df>=拓扑维Dt。
若一有界集合，包含N个不相重叠的子集，当其放大或缩小r倍后，仍与原集合叠合，则称为自相似集合。自相似集合是分形集。具有相似性的系统叫做分形。
当放大或缩小的倍数r不是一个常数，而必须是r（r1，r2，….）的各种不同放大倍数去放大或缩小各
【2】 子集，才能与原集合重合时，称为自仿射集合。具有自仿射性的系统叫做分形。
特征
1. 自相似性：局部与整体的相似，是局部到整体在各个方向上的等比例变换的结果； 2. 自仿射性：是自相似性的一种拓展，是局部到整体在不同方向上的不等比例变换的结果； 3. 精细结构：即使对该分形图放大无穷多倍，还是能看到与整体相似的结构，表现出无休止的重复； 4. 分形集无法用传统几何语言来描述，它不是某些简单方程的解集，也不是满足某些条件的点的轨迹；
5. 分形集一般可以用简单的方法定义和产生，如递归、迭代；分形其实是由一些简单的图形，经过递归或者迭代产生的复杂、精细的结构；
【3】6. 无确定的标度且具有分数维数。
1
《智能信息处理概论》结课论文
分数维
拓扑维：又称橡皮几何学。研究几何图形在一对一的双方连续变换下不变的性质，称为拓扑性质。 豪斯道夫维数：1919年提出连续空间的定义：即空间维数不是跃变的，而是可以连续变化的，既可以是整数，也可以是分数，通过具体计算来确定维数。——分数性质
豪斯道夫维数有三种求解方法：
1.放大求解：豪斯道夫维的几何对象，每个棱边长度放大L倍，几何对象对应放大K倍。那么，由，可推导出
。
2.缩小求解：豪斯道夫维的几何对象，等分成N个小的几何图形，则每个小图形每维缩小为原来的
r维。而N个小图形的总和应为。那么，分维为。
3.测量学求解：对一个体积为A，分维为的几何对象，要用半径为r的小球去测度，则所需小球数
目为
哥诺夫容量维。
定义容量维为
。其中，C为结构因子。所以分维为。 这里的分维也称为科尔莫
，且其与相一致。
各棱边放大L倍，相应的几何对象体积放大K倍，则所需小球数目应为 。
若小球半径r缩小L倍，而A保持不变，则所需小球数目仍应为N’。那么所需小球数目的表达式应为
。
由上述两个式子可得
【4】
。即可得到结论容量维与豪斯道夫维相一致。
分形举例——Julia集
Julia 集是由法国数学家 Gaston Julia 和 Pierre Faton 在发展了复变函数迭代的基础理论后获得的。其也是一个典型的分形，只是在表达上相当复杂，难以用古典的数学方法描述。 Julia集与Mandelbort集来自于复数非线性映射
。通过给定的不同初始值，经过无穷次的
迭代产生的分形图集。当C给定初始值，而Z值作为一个变量，通过无数次迭代产生的分形图集称为Julia集; 当Z给定初始值，而C值作为一个变量，通过无数次迭代产生的分形图集称为Mandelbort集。
特点
对于映射
而言，若
,
, 则有二维映射
例如取C=0+0i，则有以下情况发生：
2
《智能信息处理概论》结课论文
如果如果如果然而，当
，则在复Z平面上迭代结果，则在复Z平面上迭代结果，则
；那么，零是；那么，无穷是
的吸引子。复平面上所有与该吸的吸引子。复平面上所有与零
引子相距小于1的点，都产生趋向吸引子的序列。 点的距离超过1的点，都产生趋向无穷的序列。
；那么，产生的序列总出现在上面两个吸引区域之间的边界上。此时，边界，就是Julia集。
，而是一个不规则、非光滑
恰为复平面上的单位圆周
时，其吸引子不再是0，而变为一个区域，被吸进去的点会遍历整个区间，这个区域被
称做混沌区。与此同时，分割混沌区和向逃逸的分界线不再是单位圆则和不光滑的。
Julia集的实际例子是求解三次方程或
。上述式子的三个根是1，
的分界线。当C值越来越大时，复平面上甚至会产生几个离散的吸引区域，而每个孤岛的分界线都是不滚
。 三个根的Newton迭代法是： 和
，即该式有三个吸引子。那么，从
复平面上任何地方的初值开始迭代，最终应该滑到其中的一个吸引子。自然而然，我们所得到的三个吸引区的边界也应该是简单，明显的。然而，绘图时发现，三个扇形区域的边界具有一种特别的性质，即上面的每个点都隔开所有三个区域，形成了一种复杂的边界。当我们把这边界放大时，又会形成自相似的结构。因此，Julia集通常被认为具有分数维结构，并且在这个集上的迭代过程是一种混沌运动。
刚刚，Julia集是在复数平面经过无数次迭代产生的使
上考虑的；那么，让我们从复参数平面
【5】【6】
就是Mandelbort集。
上进行。此时取定，
有界的点集
逃逸时间算法
Julia集是复数映有二维映射
，当C为某一固定值时的一个吸引域，其中。
,
, 则
从逃逸时间算法的角度看，Julia集的内部收敛于某一点或某几个点，而Julia集的外部随着逃逸时间t的增加将发散至，其逃逸边界便是Julia集。
我们可以根据点设计思路：
假设绘图窗口的图形分辨率是1.选定参数的循环。
2.令
,
算出
, t=0。
， 计数t=t+1。
， , 对所有的点
,
点，可显示颜色K+1种，以数字0~K表示，且0表示黑色。
, M=100 ; 令
及
,
，完成如下步骤
逃向的速度决定逃逸区中个点的着色。
3.根据下式的迭代过程从4.计算 如果 如果 如果5.对点程序设计：
：
, 则选择颜色t，转至步骤5； , 则选择颜色0（黑色），转至步骤5； 且
则转至步骤5。
【7】【8】
着颜色t并转至下一点，再从头做步骤5。
3
《智能信息处理概论》结课论文
CJuliaView: :CJuliaView() {
//TODO: : add construction code here
K=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; }
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;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(r>m) { H=k; goto loop2; }
If(k==K) {
H=int(r*10); goto loop2; }
If(r<=m&&k pDC->SetPixel(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; 4 《智能信息处理概论》结课论文 c =0.194-0.6557i c =-1.25 c =0.31+0.04i c =-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，然后取概率 ，由此给出两个反。具体步骤如下： 5