呂克林

（河南省科學(xué)技術(shù)信息研究院，河南 鄭州 450003）

分形的圖像及應(yīng)用

呂克林

（河南省科學(xué)技術(shù)信息研究院，河南 鄭州 450003）

本文首先闡述了分形的基本概念，并具體介紹了一些典型的分形曲線和分形集，加深讀者對(duì)分形的理解。重點(diǎn)描述如何生成分形的計(jì)算機(jī)圖像，以及分形主要的應(yīng)用領(lǐng)域，強(qiáng)調(diào)計(jì)算機(jī)科學(xué)與其他學(xué)科之間的緊密聯(lián)系。

分形；自相似；迭代；Mandelbrot

隨著計(jì)算機(jī)圖形學(xué)的發(fā)展，最近幾年，分形作為一種藝術(shù)形式已經(jīng)相當(dāng)流行。對(duì)分形有一個(gè)基本的了解，能提高人們的鑒賞力，幫助人們更好地體會(huì)分形藝術(shù)的美。分形作為一門剛剛誕生的學(xué)科，正在許多領(lǐng)域開展應(yīng)用和探索。很多傳統(tǒng)的科學(xué)難題，都由于分形的引入取得了顯著的進(jìn)展。

1 分形的定義

1.1 分形的出現(xiàn)。中國(guó)的海岸線有多長(zhǎng)？很明顯，這取決于測(cè)量所用的標(biāo)度單位。若以公里為標(biāo)尺，會(huì)遺漏大量的細(xì)節(jié)，標(biāo)尺越小，測(cè)出的海岸線就越長(zhǎng)。隨著計(jì)算機(jī)的迅速發(fā)展，人們?cè)谟懻摵吞幚硪幌盗袉栴}的時(shí)候，逐漸感到無法描述一些自然界普遍存在的對(duì)象，如海岸線，樹木，巖石，云團(tuán)，閃電等等。同樣對(duì)于星系分布，凝聚生長(zhǎng)，湍流等復(fù)雜現(xiàn)象，也需要一門新的學(xué)科來描述。1973年，B.B.Mandelbrot在法蘭西學(xué)院講課時(shí)，首次提出了分維和分形幾何的設(shè)想。Fractal一詞由他所創(chuàng)，其原意具有不規(guī)則，支離破碎等意義。分形幾何是一門以非規(guī)則幾何形狀為研究對(duì)象的學(xué)科，也被稱為大自然的幾何學(xué)。

1.2 自相似性。自相似性是指部分與整體具有相似的性質(zhì)。在自然界中，具有自相似性的客觀對(duì)象是非常多的。除了山形的起伏，河流的彎曲，樹木的分枝結(jié)構(gòu)外，生物體內(nèi)也有許多例子，如血管或氣管的分岔，神經(jīng)網(wǎng)絡(luò)等。抽象的自相似例子就更多了，例如數(shù)列0112122312232334…，這是一個(gè)去掉奇數(shù)項(xiàng)后，仍然得到自身的數(shù)列。下文中將提到的Cantor集是一個(gè)更好，更有故事的例子。

1.3 維數(shù)。維數(shù)是重要的幾何特征量，通常定義為表示對(duì)象的一個(gè)點(diǎn)所需的獨(dú)立變量個(gè)數(shù)。人們習(xí)慣認(rèn)為空間是三維的，平面是二維的，直線是一維的，高等代數(shù)中還引入了高維空間概念。然而維數(shù)有許多定義方法，下面介紹兩種基于拓?fù)鋵W(xué)和測(cè)度論的定義。

拓?fù)渚S數(shù)：經(jīng)拓?fù)渥儞Q能轉(zhuǎn)換為孤立點(diǎn)的集合DR=0，變?yōu)橹本€的DR=1，依次類推。

1.4 分形集。目前還很難給出一個(gè)分形的嚴(yán)格定義。但可以效仿生物學(xué)中，通過列出生命體的一系列特性來解釋“生命”的概念。下面給出分形集合的一些性質(zhì)：一是Hausdoff維數(shù)大于其拓?fù)渚S數(shù)；二是具有近似的或統(tǒng)計(jì)的自相似性；三是從整體到局部均難以用傳統(tǒng)的幾何描述；具有精細(xì)結(jié)構(gòu)，即任意小比例下的細(xì)節(jié)；四是一般可以用非常簡(jiǎn)單的遞歸性方法定義。可以看到，分形的理論工作還有待加強(qiáng)。現(xiàn)有的研究多集中在計(jì)算機(jī)模擬與維數(shù)計(jì)算，對(duì)分形的認(rèn)識(shí)還有待深入。

2 典型的分形曲線與分形集

2.1 Von Koch曲線。1804年，瑞典數(shù)學(xué)家Von Koch發(fā)現(xiàn)了一種曲線，它處處連續(xù)，卻處處不光滑。在分形理論的建立過程中，Von Koch曲線占有重要的地位。Von Koch曲線的生成方法：首先從一個(gè)簡(jiǎn)單的圖形出發(fā)，反復(fù)進(jìn)行同樣的操作：將當(dāng)前圖形中的所有直線段用一段折線（生成元）代替，讓操作次數(shù)趨于無窮，就得到了Von Koch曲線。不同的原圖形和生成元決定了曲線的不同形態(tài)。最常見的是對(duì)正三角形，用右圖的生成元進(jìn)行操作，所得曲線的形狀像一朵雪花，稱為Koch雪花曲線。雪花曲線的周長(zhǎng)沒有上界，因?yàn)槊看尾僮鲌D形的周長(zhǎng)都增加1/3。

2.2 Sierpinski三角形。分形不難從曲線推廣到平面圖形。1916年，波蘭數(shù)學(xué)家Waclaw Sierpinki提出了三角形。它的構(gòu)造方法如下：從等邊三角形開始，每次把圖中所有等邊三角形四等分，去掉中間的一個(gè)小三角形，不斷重復(fù)分割與舍棄的過程直到無窮。Sierpinki三角形兩種常見的推廣：對(duì)正方形用類似的生成規(guī)則，得到的圖案叫Sierpinki地毯。三維空間中，從一個(gè)正方體開始，將所有的正方體27等分，去掉體心與面心處的7個(gè)小正方體，反復(fù)操作得到Sierpinki海綿體。Sierpinki集具有分形的典型特征：經(jīng)典幾何無法描述，局部放大后和整體完全相同。它們?cè)环Q為是病態(tài)的幾何圖形，因?yàn)樵谥荛L(zhǎng)（表面積）趨向于無窮大的同時(shí)，面積（體積）卻趨向于0。

2.3 Cantor集。G.Cantor在1883年構(gòu)造了如下的一類集合。將區(qū)間[0，1]三等分，保留兩邊的閉區(qū)間，再對(duì)這兩部分重復(fù)相同的操作，直至無窮。最后得到離散的點(diǎn)集稱為Cantor集。Cantor集有明顯的自相似性和精細(xì)結(jié)構(gòu)，還有和Sierpinki集相似的特點(diǎn)：Cantor集包含的元素是不可數(shù)的，但是它的長(zhǎng)度是0。另外，Cantor集是一個(gè)閉集（關(guān)于極限封閉），而且[0，1]內(nèi)的任何一個(gè)實(shí)數(shù)，都可以表示成3個(gè)Cantor集中元素的和。實(shí)數(shù)全體是一個(gè)不容易被傳統(tǒng)思維接受的概念。舉例來說，任兩個(gè)有理數(shù)之間都存在一個(gè)有理數(shù)，這是很難直觀想象的。換句話說，用再精細(xì)的顯微鏡去看數(shù)軸，它的密集程度都沒有變化，假想你是一個(gè)數(shù)軸上的有理數(shù)，你無法知道站在你兩邊的是誰。在G. Cantor所生活的時(shí)代，如果有分形理論，這些看似荒謬的結(jié)論，應(yīng)該比較容易被人們接受。

2.4 Julia集。Julia集是由法國(guó)數(shù)學(xué)家Gaston Julia在1918年發(fā)展了復(fù)變函數(shù)迭代的基礎(chǔ)理論后獲得的，研究zk+1=zk2+c這一變換在復(fù)平面中所生成的一系列讓人眼花繚亂的變化。每個(gè)復(fù)數(shù)對(duì)應(yīng)平面上的一個(gè)點(diǎn)。給定c和z0之后，通過迭代可以得到一連串復(fù)數(shù)。如果所得復(fù)數(shù)的模長(zhǎng)是發(fā)散的，也就是這個(gè)點(diǎn)最終可以“跳”到無窮遠(yuǎn)的地方去，我們就稱Z0是“自由的”。取定復(fù)數(shù)c，如果復(fù)平面上的一個(gè)點(diǎn)是自由的，就把這個(gè)點(diǎn)涂成白色，否則就涂成黑色，此時(shí)邊界就呈現(xiàn)出了Julia集的圖形。如果能依據(jù)自由點(diǎn)的逃跑速度給它涂上漸變的顏色，就會(huì)得到非常美麗的圖案。不同的復(fù)數(shù)c決定不同的Julia集。

Julia集的自相似性似乎不很明顯，但實(shí)際上，任何Julia集均能由它自身的拷貝覆蓋。然而這些拷貝都是通過非線性變換得到的，這里的相似與前面是有著本質(zhì)區(qū)別的。

2.5 Mandelbrot集。仍然考慮zk+1=zk2+c，取定Z0=0，計(jì)算哪些c是“自由的”。用相同的作圖方法可以得到Mandelbrot集的圖形。Mandelbrot的特殊之處在于，將它的邊界放大，會(huì)顯示出許多微型縮影，但沒有一個(gè)是和母集完全相同的。

最后介紹一個(gè)定理：復(fù)數(shù)c對(duì)應(yīng)的Julia集有連通性的充要條件為，c是從Mandelbrot集內(nèi)部選出的。其實(shí)，通過c在Mandelbrot集中的哪個(gè)區(qū)域，可以推斷Julia集的特征，預(yù)測(cè)的范圍遠(yuǎn)遠(yuǎn)不止連通性。把Mandelbrot集比作Julia集的圖解目錄表是很貼切的。

3 分形的計(jì)算機(jī)圖像

3.1 計(jì)算機(jī)圖形學(xué)。計(jì)算機(jī)圖形學(xué)研究如何用計(jì)算機(jī)生成、處理并顯示圖形。分形理論的創(chuàng)立和發(fā)展都和計(jì)算機(jī)圖形學(xué)密切相關(guān)。Julia曾研究過Julia集并使當(dāng)時(shí)的復(fù)分析達(dá)到了很高的水平，只是由于當(dāng)時(shí)還沒有計(jì)算機(jī)，因而使他們的研究中斷。分形的創(chuàng)始人Mandelbrot詳細(xì)地研究過Julia的手稿，借助計(jì)算機(jī)為工具，才使研究開花結(jié)果?？茖W(xué)可視化可以將抽象的概念和數(shù)據(jù)形象化，幫助人們更好地認(rèn)識(shí)和理解問題。有些問題只有借助計(jì)算機(jī)，依靠實(shí)驗(yàn)數(shù)學(xué)的方法，才能得到豐富的、直觀的啟示。

3.2 仿射變換。仿射變換是計(jì)算機(jī)圖形學(xué)中幾何變換的重要內(nèi)容，是一種R2上的線形變換：

其中e和f對(duì)圖形進(jìn)行平移，r和q是放縮比例，θ是繞原點(diǎn)旋轉(zhuǎn)的角度。分形構(gòu)圖中一般只需相似變換，即r=q的情況。仿射變換通常也會(huì)寫成：x'=ax+by+c y'=dx+ey+f

一個(gè)仿射變換由六個(gè)參數(shù)寫出，分形通常需要一組仿射變換。例如對(duì)于Sierpinski三角形，三個(gè)變換分別將原圖向三個(gè)頂點(diǎn)收縮到原來的一半大小。

3.3 迭代函數(shù)系統(tǒng)。分形圖形具有自相似性，其定義往往就是遞歸的，最樸素的生成方法是不斷對(duì)當(dāng)前圖形使用各種仿射變換。由于直線段經(jīng)仿射變換后還是直線段，對(duì)于三角形只要把頂點(diǎn)變換后相連即可。圖形越來越復(fù)雜后，記錄當(dāng)前圖案變得困難。迭代函數(shù)系統(tǒng)（Iteration Function System）更多采用的是隨機(jī)算法：由一系列仿射變換按隨機(jī)順序，對(duì)一個(gè)初始點(diǎn)反復(fù)作映射，并記錄下它變換的軌跡，最終這些點(diǎn)會(huì)“填滿”整個(gè)分形圖形的區(qū)域。IFS通常依據(jù)變換后的面積大小，給每個(gè)仿射變換設(shè)定概率，這樣做是為了讓點(diǎn)盡量“平均分布”，避免點(diǎn)很難“跳入”某個(gè)局部。

3.4 Ultra Fractal。Ultra Fractal是一款強(qiáng)大的分形作圖軟件。它最大的特點(diǎn)在于可以簡(jiǎn)單地改變參數(shù)，定義新的公式。軟件還采用了多種加速算法，能夠快速繪制圖案。

4 分形的應(yīng)用

4.1 藝術(shù)設(shè)計(jì)。早在1999年，中國(guó)科技館就舉辦過“分形藝術(shù)展覽”。網(wǎng)絡(luò)上也可以找到大量的分形藝術(shù)作品。在計(jì)算機(jī)如此普及，計(jì)算機(jī)輔助設(shè)計(jì)技術(shù)成熟的今天，分形在藝術(shù)設(shè)計(jì)領(lǐng)域的前景是十分樂觀的。相信在不久的將來，分形會(huì)以印染品或裝飾品的形式，點(diǎn)綴人們的現(xiàn)代生活。

4.2 凝聚生長(zhǎng)。一些樹木的形態(tài)看起來像是分形，樹干可以在不同的位置分出樹枝，每個(gè)樹枝又繼續(xù)分為枝杈。分形在原始植物（比如苔蘚和海藻）上更加明顯，因?yàn)閷?duì)于高級(jí)植物，生物規(guī)律的作用過于復(fù)雜，掩蓋了數(shù)學(xué)模型。所以我們選用一個(gè)簡(jiǎn)單實(shí)驗(yàn)：在圓形碟子的底部覆蓋一層很薄的硫酸銅溶液，將銅制的陰極立在中央進(jìn)行電解，大約半小時(shí)后，析出的銅將擴(kuò)展成幾英寸的分形圖形。有限制的擴(kuò)散凝聚（Diffusion Limited Aggregation）模型提供了很有說服力的模擬：在白色方格紙上，從中心一個(gè)代表陰極的黑色小方格開始，以它為中心做一個(gè)大圓。圓周附近一個(gè)隨機(jī)點(diǎn)釋放出的粒子在平面上隨機(jī)運(yùn)動(dòng)，直到它離開這個(gè)圓或與到達(dá)與黑色方格相鄰的格子為止，這個(gè)格子也被涂黑。模擬得到16 000個(gè)黑色方格時(shí)的效果，與實(shí)驗(yàn)結(jié)果很相似。DLA模型盡管描述起來很簡(jiǎn)單，然而對(duì)于為什么產(chǎn)生分形的樹枝形態(tài)，現(xiàn)在還沒有嚴(yán)格的理論解釋，但毫無疑問這是一個(gè)非常引人注目的現(xiàn)象。

4.3 模擬自然景物。喜歡3D卡通片的人，一定知道Pixar工作室。在繪制山峰和樹木等自然景物時(shí)，用直線、圓弧，樣條曲線去建模生成，逼真程度就非常差，那么Pixar又是如何用電腦制作這些美麗風(fēng)景的呢？很自然地想到利用分形，也就是我們常說“分?jǐn)?shù)維的山峰”。下面是一種簡(jiǎn)單的生成方法：從一個(gè)三角形開始，取三邊中點(diǎn)，各自在垂直方向上移動(dòng)一個(gè)與邊長(zhǎng)成正比的隨機(jī)量，再將它們相連，形成四個(gè)新的小三角形。用同樣的辦法繼續(xù)分割，直到分辨率極限為止，就得到了充滿褶皺的山峰。

Pixar繪圖計(jì)算機(jī)如今廣泛應(yīng)用于醫(yī)學(xué)成像、工程設(shè)計(jì)、虛擬電影和動(dòng)畫制作等領(lǐng)域。

4.4 圖像壓縮。設(shè)想我們要存儲(chǔ)一幅Julia集的圖像，如果用位圖來存儲(chǔ)，需要記錄每個(gè)像素的顏色，占用大量空間。當(dāng)然可用標(biāo)準(zhǔn)壓縮技術(shù)對(duì)其進(jìn)行壓縮，但事實(shí)上只需要記下復(fù)數(shù)c，就可以在任何時(shí)候重建這張圖片，而且不會(huì)遺漏任何細(xì)節(jié)，甚至比原圖更清楚。上面是一個(gè)極端的例子，卻很好地說明了IFS碼壓縮技術(shù)的關(guān)鍵，在于存儲(chǔ)迭代函數(shù)系統(tǒng)而不是存儲(chǔ)圖像。實(shí)際操作時(shí)，首先把原始圖像分解為一些相連的顏色穩(wěn)定的小塊，從大量的仿射變換公式中選出能產(chǎn)生相似效果的，記錄對(duì)應(yīng)參數(shù)作為編碼。IFS編碼是一種有損壓縮，其失真率與壓縮比有關(guān)。IFS的優(yōu)點(diǎn)在于對(duì)自然景物和細(xì)節(jié)豐富的圖像，壓縮比很高，還原效果較好。同時(shí)IFS編碼在縮短處理時(shí)間，自動(dòng)生成，失真度準(zhǔn)則等方面，還有大量問題有待解決。

4.5 經(jīng)濟(jì)學(xué)與社會(huì)學(xué)。分形理論在對(duì)價(jià)格波動(dòng)，利率變化，證券指數(shù)的研究中有很好的表現(xiàn)，因?yàn)槿后w行為存在相似性。不同的投資者，交易金額不同，而買賣決斷的方法卻是大致相同的。另一個(gè)例子來自城市規(guī)劃。當(dāng)城市發(fā)展到一定規(guī)模時(shí)，會(huì)產(chǎn)生新的開發(fā)區(qū)和衛(wèi)星城，這些新的區(qū)域也有相同的發(fā)展模式。以半徑變化的圓模擬城市，可以研究城市“分裂”的臨界值和哪些因素相關(guān)。

5 分形雜談

5.1 認(rèn)識(shí)的改變?！稊?shù)學(xué)分析教程》全書的最后一節(jié)給出了兩個(gè)函數(shù)，一個(gè)處處連續(xù)處處不可導(dǎo)，我們?cè)谏衔囊呀?jīng)看過一個(gè)例子。另一個(gè)函數(shù)連續(xù)且填滿一個(gè)正方形，也是利用分形思想構(gòu)造的。Mandelbrot在《自然界的分形幾何》中提到：“我贊揚(yáng)這些早年的數(shù)學(xué)家，他們?yōu)槲姨峁┝诉@樣的結(jié)構(gòu)，使我能夠?qū)⑺鼈兇谝黄鹚伎?，從而發(fā)現(xiàn)其寶貴的價(jià)值。同時(shí)，我也責(zé)備他們，因?yàn)樗麄冸m然構(gòu)造出許多精彩的反例，卻沒有發(fā)現(xiàn)他們內(nèi)在的聯(lián)系，反而認(rèn)為那是不正常的事情，從而忽視了真正的內(nèi)涵?！笨茖W(xué)史上的每一次爭(zhēng)論都推動(dòng)科學(xué)本身向前發(fā)展。就像G.Cantor的集合論起初被認(rèn)為是“怪胎”一樣，許多分形的現(xiàn)象在漫長(zhǎng)的時(shí)間里被認(rèn)為是不正常的。而現(xiàn)在人們已經(jīng)認(rèn)識(shí)到，這些有悖于直覺和經(jīng)典理論的現(xiàn)象，是合理且廣泛存在的。

5.2 簡(jiǎn)單的規(guī)則。分形通過重復(fù)簡(jiǎn)單的操作，得到極復(fù)雜的圖形。生命游戲依靠簡(jiǎn)單的規(guī)則，賦予了模型自我復(fù)制和進(jìn)化的能力。我們?cè)賮砜匆粋€(gè)著名的例子，Langton螞蟻從一張白紙的某個(gè)方格開始爬行，按照如下規(guī)則：一是如果它進(jìn)入了一個(gè)白色方格，就將其涂成黑色，并左轉(zhuǎn)90度。二是如果它進(jìn)入了一個(gè)黑色方格，就將其涂成白色，并右轉(zhuǎn)90度。在前500步中，它不斷回到原點(diǎn)，留下一系列相當(dāng)對(duì)稱的圖案。此后的10 000步中，圖形變得混沌。突然，仿佛終于拿定主意要干些什么，它不斷重復(fù)著一個(gè)104步的過程，畫出公路一樣的帶狀圖案。自然界的神奇無處不在，水分子居然知道如何構(gòu)造雪花，使其具有復(fù)雜的對(duì)稱性。這些分子能夠自行“裝配”起來，既沒有建筑師的指導(dǎo)，也沒有結(jié)晶形式的模版，大尺度上的形狀完全是依靠短距離的相互作用產(chǎn)生的。最后引用MIT教授T.Toffoli的一段話，“幾十億年來，自然界都在不停地計(jì)算宇宙的下一個(gè)狀態(tài)，我們要做的，實(shí)際上也是我們唯一能做的，就是跟著這碩大無比的計(jì)算過程前進(jìn)，并企圖發(fā)現(xiàn)它的哪一部分恰好接近我們所希望的地方?！?/p>

6 結(jié)語

分形現(xiàn)象普遍地存在于自然界中，是它受到廣泛關(guān)注的根本原因。分形作為一門年輕的學(xué)科，在廣大科學(xué)工作者的共同努力下，無論是理論還是應(yīng)用方面都取得了巨大的進(jìn)展。分形的創(chuàng)立是數(shù)學(xué)與計(jì)算機(jī)科學(xué)結(jié)合的典范，如今計(jì)算機(jī)科學(xué)正在逐漸滲透到各個(gè)學(xué)科當(dāng)中。作為計(jì)算機(jī)專業(yè)的科技工作者，同樣要關(guān)注其他學(xué)科的發(fā)展，重視它們和計(jì)算機(jī)科學(xué)之間的聯(lián)系。

[1]胡瑞安，胡紀(jì)陽，徐樹公.分形的計(jì)算機(jī)圖像及其應(yīng)用[M].北京：中國(guó)鐵道出版社，1995.

[2]張濟(jì)中.分形[M].北京：清華大學(xué)出版社，1995.

[3]常庚哲，史濟(jì)懷.數(shù)學(xué)分析教程[M].北京：高等教育出版社，2003.

[5]郭凱聲，等.數(shù)學(xué)游戲[M].北京：科學(xué)技術(shù)文獻(xiàn)出版社，1999.

TP391.4

A

1671-0037（2014）12-94-3

呂克林（1960-），男，本科，高級(jí)工程師，研究方向：計(jì)算機(jī)應(yīng)用。