1、成績： 課程名稱：智能信息處理概論分形之Julia集及其算法實現摘要：本文從自然界的幾何現象引出分形的概念，再從其定義、幾何特征和分形維的計算這三個方面來加以介紹。以Julia集和Mandelbort集為例來具體描述分形。本文主要從Julia集的特點和算法實現來描述分形以及其實現的方法。關鍵詞：分形、分數維、Julia集、Mandelbort集、算法實現引言大自然是個很偉大的造物者，它留給我們一大筆美麗景觀：蜿蜒曲折的海岸線、起伏不定的山脈，變幻無常的浮云，粗糙不堪的斷面，裊裊上升的煙柱，九曲回腸的河流，縱橫交錯的血管，令人眼花繚亂的滿天繁星那么，我們又能從這些美妙的自然現象中得到什么有趣的結

2、論呢？正文分形概述分形的英文單詞為fractal，是由美籍法國數學家曼德勃羅（Benoit Mandelbrot）創造出來的。其取自拉丁文詞frangere（破碎、產生無規則碎片）之頭，擷英文之尾所合成，本意是不規則的、破碎的、分數的。他曾說：分形就是通過將光滑的形狀弄成多個小塊，反復的碎弄。1975年，曼德勃羅出版了他的法文專著分形對象：形、機遇與維數，標志著分形理論正式誕生。【1】兩種定義其一：具有自相似性結構的叫做分形；其二：數學定義：豪斯道夫維Df=拓撲維Dt。若一有界集合，包含N個不相重疊的子集，當其放大或縮小r倍后，仍與原集合疊合，則稱為自相似集合。自相似集合是分形集。具有相似性的

3、系統叫做分形。當放大或縮小的倍數r不是一個常數，而必須是r（r1，r2，.）的各種不同放大倍數去放大或縮小各子集，才能與原集合重合時，稱為自仿射集合。具有自仿射性的系統叫做分形。【2】特征1. 自相似性：局部與整體的相似，是局部到整體在各個方向上的等比例變換的結果；2. 自仿射性：是自相似性的一種拓展，是局部到整體在不同方向上的不等比例變換的結果；3. 精細結構：即使對該分形圖放大無窮多倍，還是能看到與整體相似的結構，表現出無休止的重復；4. 分形集無法用傳統幾何語言來描述，它不是某些簡單方程的解集，也不是滿足某些條件的點的軌跡；5. 分形集一般可以用簡單的方法定義和產生，如遞歸、迭代；分形其

4、實是由一些簡單的圖形，經過遞歸或者迭代產生的復雜、精細的結構；6. 無確定的標度且具有分數維數。【3】分數維拓撲維Dt：又稱橡皮幾何學。研究幾何圖形在一對一的雙方連續變換下不變的性質，稱為拓撲性質。 豪斯道夫維數Df：1919年提出連續空間的定義：即空間維數不是躍變的，而是可以連續變化的，既可以是整數，也可以是分數，通過具體計算來確定維數。分數性質 豪斯道夫維數有三種求解方法：1.放大求解：豪斯道夫維Df的幾何對象，每個棱邊長度放大L倍，幾何對象對應放大K倍。那么，由LDf=K，可推導出 Df=lnKlnL。2.縮小求解：豪斯道夫維Df的幾何對象，等分成N個小的幾何圖形，則每個小圖形每維縮小為

5、原來的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保持不變，則所需小球數目仍應為N。那么所需小球數目的表達式應為 N=ArLDf。由上述兩個式子可得 Df=ln

6、KlnL。即可得到結論容量維與豪斯道夫維相一致。【4】分形舉例Julia集Julia 集是由法國數學家 Gaston Julia 和 Pierre Faton 在發展了復變函數迭代的基礎理論后獲得的。其也是一個典型的分形，只是在表達上相當復雜，難以用古典的數學方法描述。Julia集與Mandelbort集來自于復數非線性映射fZ=Z2+C。通過給定的不同初始值，經過無窮次的迭代產生的分形圖集。當C給定初始值，而Z值作為一個變量，通過無數次迭代產生的分形圖集稱為Julia集; 當Z給定初始值，而C值作為一個變量，通過無數次迭代產生的分形圖集稱為Mandelbort集。特點對于映射Zn+1=Zn2

7、+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，而變為一個區域，被吸進去的點會遍歷整個區間，這個區域被稱做混沌區。與此同時，分割混沌區和向逃逸的分界線不再是單位圓Z=1，而是一個不規則、非光滑

8、的分界線。當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集的內部收斂于某一點或某幾個點，而Julia集的外部隨著逃逸時間t的增加將發散至

10、，其逃逸邊界便是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,yi算出xi+1,yi+1 ， 計數t=t+1。xt+1=xt2-yt2+pyt

11、+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= -1.5; y1= 1.5; /復平面上C的坐標 p=0.32; q=0.043

12、;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&kSetPixel(nx,ny,H*1000); 在Julia View.h文件夾定義變量如下

13、：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算法：相似變換是指在各個方向上變換的比率必須相同的一種比例變換，仿射變換是指在不同方向上變化的比率可以不同的一種比例變換。相似變換可放大或縮小甚至旋轉，但不變形；而仿射變換可能會變形。仿射變換的數學表達式為:x=a

14、x+by+ey=cx+dy+f 其中，代表仿射變換，x和y是變換前圖形的坐標值，x和y是變換后的圖形的坐標值；a, b, c, d, e, f 是仿射變換系數。對于一個比較復雜的圖形，可能需要多個不同的仿射變換來實現，放射變換族n控制著圖形的結構和形狀，由于仿射變換的形式是相同的，所以不同的形狀取決于仿射變換的系數。另外，仿射變換族n中，每一個仿射變換被調用的概率是不一定等同的，也就是說，落入圖形各部分中點的數目是不一定相同，這就引入了一個新的量，即仿射變換被調用的概率P。從而，6個仿射變換系數（a, b, c, d, e, f）和一個概率（P）便組成了IFS算法最關鍵的部分IFS碼。設計思路

15、：對于復映射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.判斷棧是否為空，若棧空，則停止，否則重復26 。【9】【10】程序設計：/CJULIAView drawingvo

16、id 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(wy/wx); if(wx=0) theta=PI/2; theta=thet

17、a/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.m_cx; cy=dlg.m_cy; x=dlg.m_x;y=dlg.m_y;

18、Invalidate(); 結論分形是一種由簡單的直線或者方程通過無窮次簡單的迭代形式而產生的具有無比精細的結構，這個過程又稱之為混沌。其兩者是密不可分的。分形理論表現出兩個重要原則自相似原則和迭代生成原則。而這兩種原則正是分形算法實現的重要依據。自然界的奧秘是無窮的，它還有許許多多的分形結構等著我們去探索、去發現。我們一定不能放慢腳步，要勇于創新，把大自然留給我們的寶藏發掘出來，為之己用！參考文獻1作者：孫博文； 書名M：分形算法與程序設計Visual C+實現； 版本：第一版；出版地：北京； 出版者：科學出版社； 出版年：2004年11月； 起止頁碼：1-1.2作者：林鴻溢、李映雪； 書名M：分形論奇異性探索； 版本：第一版；出版地：北京； 出版者：北京理工大學出版社； 出版年：1992年9月； 起止頁碼：62-63.3作者：孫博文； 書名M：分形算法與程序設計Visual C+實現