基于分形理論的水下地形生成?

潘竹爐

1 引言

地球表面上71%的區(qū)域是海洋，海洋把世界聯(lián)系到一起，然而到目前為止，人類已探測(cè)的海底只有5%，還有95%的海底是未知的［1］。海洋不僅是生命的源泉，提供了人類賴以生存的物質(zhì)和空間，還蘊(yùn)含豐富的生物、化學(xué)、礦產(chǎn)等資源。隨著人類活動(dòng)空間的擴(kuò)展，航海早已不局限于海面上，潛艇、水下機(jī)器人等航海新設(shè)備急切需要水下三維空間地形圖。二維電子海圖只能用水深和等深線來(lái)描述水下的地形地貌，有表述不直觀、信息不全等問(wèn)題，不利于海底地形分析。利用傳統(tǒng)的二維矢量電子海圖提供的水深數(shù)據(jù)、等深線和海岸線等信息構(gòu)建水下DEM，將使水下空間可觀測(cè)維數(shù)大大增加。三維海底地形可視化系統(tǒng)操作更簡(jiǎn)便、表達(dá)更直觀、逼真性更強(qiáng)、信息量更大，更有利于人的接受、感知和理解。

2 數(shù)字高程模型

數(shù)字高程模型（DEM）一般來(lái)說(shuō)是將離散、不規(guī)則的原始采樣高程值使用某些數(shù)學(xué)手段（例如過(guò)采樣、擬合、插值等）重建出相似曲面來(lái)逼近原始的地表。常見(jiàn)的DEM模型根據(jù)數(shù)據(jù)結(jié)構(gòu)的不同主要分為規(guī)則格網(wǎng)DEM（如圖1（a））和不規(guī)則三角網(wǎng)DEM（如圖1（b））。規(guī)則格網(wǎng)數(shù)據(jù)結(jié)構(gòu)冗余較多，但是拓?fù)潢P(guān)系較好，數(shù)據(jù)存儲(chǔ)簡(jiǎn)單；不規(guī)則三角網(wǎng)有較好的數(shù)學(xué)結(jié)構(gòu)，數(shù)據(jù)冗余少，但拓?fù)潢P(guān)系較差，數(shù)據(jù)存儲(chǔ)復(fù)雜［2］。

圖1 常見(jiàn)數(shù)字高程模型

數(shù)字高程模型的平滑內(nèi)插是基于海底地形的過(guò)渡平滑趨勢(shì)構(gòu)建三維海底地形的，通過(guò)二維海圖提供的離散水深點(diǎn)的水深，估計(jì)擬合離散點(diǎn)之間的水深，從而構(gòu)建出完整的水下地形。由海底的過(guò)度平滑趨勢(shì)可知，距離越近的點(diǎn)，相關(guān)度越高。由圖2所示，按內(nèi)插點(diǎn)的區(qū)域可分為分塊內(nèi)插、逐點(diǎn)內(nèi)插和整體內(nèi)插。但是考慮到數(shù)據(jù)量的問(wèn)題，一般采用逐點(diǎn)內(nèi)插，目前，較簡(jiǎn)單的算法有特定區(qū)域的圓、TIN三角網(wǎng)插值、基于VoronoiCells的自然臨近點(diǎn)插值［3］（例如Sibson插值、Laplace插值）、基于數(shù)據(jù)融合的插值算法［4］。

圖2 DEM平滑內(nèi)插分類

3 分形內(nèi)插算法構(gòu)建DEM

分形理論隸屬于非線性科學(xué)，在生物、地球科學(xué)、材料物理等領(lǐng)域都有著很廣泛的應(yīng)用［5］。分形理論萌芽于19世紀(jì)60年代，于20世紀(jì)七、八十年代正式演變?yōu)橐婚T獨(dú)立的學(xué)科，分形插值是分形理論的一個(gè)重要應(yīng)用。分形插值主要應(yīng)用了分形的自相似原理，利用迭代算法由原始特征插值出局部細(xì)小特征。分形能表達(dá)出自然界中許多非線性現(xiàn)象，使用分形插值理論構(gòu)建地表或許最能逼近自然界真實(shí)地形［6］。

3.1 分形理論簡(jiǎn)介

分形理論（Fractal Theory）是一門以不規(guī)則幾何形態(tài)為研究對(duì)象的新理論、新學(xué)科。分形對(duì)象在自然界是普遍存在的，粗糙不平的地表、彎彎曲曲的海岸線、綿延不絕的山脈、裊裊的炊煙、枝繁葉茂的數(shù)木、漫天飛舞的雪花等都是分形。

Mandelbrot因?yàn)樘岢隽恕坝?guó)的海岸線有多長(zhǎng)”的問(wèn)題有了分形思想萌芽的故事幾乎成為佳話被廣為流傳。大量經(jīng)典的分形是自相似的，這種分形的局部和整體具有一定比例的幾何相似性，如Sierpinski墊片（圖3（a）），Koch曲線（圖3（b））。自相似集的生成元中，每一個(gè)壓縮映射都把它變換為一個(gè)小拷貝，它在不同方向上的壓縮比是相同的。多次迭代過(guò)程最終輸出圖形與輸入變得無(wú)關(guān)，真正決定最終輸出的是反饋機(jī)器中的數(shù)學(xué)變換，Barns?ley等把這種數(shù)學(xué)變換稱為迭代函數(shù)系（Iterated Functional System），簡(jiǎn)寫(xiě)為IFS。

圖3 常見(jiàn)的分形圖形

3.2 分形插值算法

分形插值由Barnsley在IFS的基礎(chǔ)上歸納推導(dǎo)出來(lái)［7］。它是分形理論的一個(gè)重要應(yīng)用。自Euclid創(chuàng)立幾何以來(lái)，人們提出了各種插值算法來(lái)描述幾何體。然而對(duì)于現(xiàn)實(shí)世界的大量離散數(shù)據(jù)，除了直到20世紀(jì)60年代提出的樣條函數(shù)插值［8］，幾乎沒(méi)有任何方法能完美克服幾何體的低階全局光滑問(wèn)題。可見(jiàn)數(shù)學(xué)插值更偏愛(ài)“光滑”，“平滑”等字眼。分形插值函數(shù)［9］利用大自然中廣泛存在的精細(xì)自相似結(jié)構(gòu)特征來(lái)擬合滾動(dòng)性強(qiáng)的曲線，為解決幾何體的低階全局光滑問(wèn)題開(kāi)辟了新的領(lǐng)域。

3.2.1 三維IFS分形插值算法推導(dǎo)

兩個(gè)維度的數(shù)據(jù)集合 I=[a，b]，J=[c，d]；設(shè)平面點(diǎn)集 D=I×J={(x，y)∶x∈I，y∈J} ，以 △x，△y 為步長(zhǎng)，將D按M×N格網(wǎng)化：

設(shè)(xm，yn){m=0，1，…，M;n=0，1，…，N}點(diǎn)處的高程數(shù)據(jù)為zm，n，我們的目的是構(gòu)造二元分形插值函數(shù) f∶D→R ，使

設(shè)滿足上式的X方向和Y方向仿射變換為

且滿足邊界條件：

由式（3）和（4）可解得

則可得平面點(diǎn)集x和y方向上得仿射變換為

設(shè)高程z方向的仿射變換為

式中hm，n為高程z方向上的壓縮倍率，它是決定分形插值后曲面的粗糙起伏程度的自由參數(shù)，需滿足 0≤hm，n＜1（否則IFS不收斂），一般稱它為垂直比例因子。

而且可得邊界條件：

聯(lián)立式（7）和（8）可得

令 Wm，n(x，y，z)=(?m(x)，ψn(y)，F(xiàn)m，n(x，y，z));(m=1，2，…，M;n=1，2，…，N)，那么就定義了一個(gè)迭代函數(shù)系統(tǒng)。 Fm，n(x，y，z)為分形插值函數(shù)fm，n(x，y)的隱函數(shù)。

3.2.2 分形插值曲面的計(jì)算步驟

根據(jù)上面推導(dǎo)的公式，分形插值曲面的算法步驟如下：

1）輸入待插值的格網(wǎng)化后的點(diǎn)云(xm，yn，zm，n);m=0，1，2，…，M;n=0，1，2，…，N ；

2）輸入自由參數(shù) hm，n；

3）根據(jù)式（9）計(jì)算參數(shù) gm，n，em，n，fm，n，km，n；

4）根 據(jù) 式（6）和（7）計(jì) 算 ：?m(xi)，ψn(yj)，F(xiàn)m，n(xi，yj，zi，j) ，m=1，2，…，M ；n=1，2，…，N ；i=0，1，…，M ；j=0，1，…N ；

5）經(jīng)過(guò)步驟4）原來(lái)的 (M+1)×(N+1)格網(wǎng)變成((M-1)2+1)×((N-1)2+1)格網(wǎng)。數(shù)據(jù)量大大增加，這就是一次分形插值曲面。若不夠密集，可以繼續(xù)進(jìn)行二次迭代。

4 三維海底地形的仿真實(shí)現(xiàn)

為了驗(yàn)證測(cè)試算法的插值效果，選取一個(gè)上海長(zhǎng)興島附近的二維電子海圖作為數(shù)據(jù)源，如圖4所示，圖中左邊陸地是橫沙島，右邊是長(zhǎng)興島，上面的黑點(diǎn)就是離散點(diǎn)的水深位置分布。

圖4 離散水深點(diǎn)在谷歌地球上的分布

為了方便構(gòu)建DEM，在陸地部分加入SRTM［10］高程數(shù)據(jù)，然后將補(bǔ)充數(shù)據(jù)后的平面離散點(diǎn)集使用平滑內(nèi)插算法—移動(dòng)擬合法生成的DEM如圖5所示。

圖5 平滑內(nèi)插算法輸出的DEM

原始二維海圖離散的水深數(shù)據(jù)共有1790組（以一個(gè)高程點(diǎn)數(shù)據(jù)為一組），以平均點(diǎn)距的1.62倍格網(wǎng)化成29×24格網(wǎng)化，使用Matlab實(shí)現(xiàn)分形插值曲面算法得到785×530的格網(wǎng)數(shù)據(jù)，如圖6所示，選取的自由參數(shù)為0.3，此時(shí)由于自由參數(shù)比較大，所以地形起伏比較大，但是基本上保持了實(shí)際的陸地海洋邊界，如果自由參數(shù)選的足夠小，則分形后的地形變得很光滑，也就退化為傳統(tǒng)插值算法。

由圖5和圖6可以看出，分形插值前后的主要變化是

1）離散數(shù)據(jù)集比較小的情況下，數(shù)據(jù)量大大增加，高程點(diǎn)變得更加密集；

2）分形插值后局部和整體具有一定比例的幾何相似性，這就是分形的自相似性。

選取自由參數(shù)為0.1的分形插值后的三維高程數(shù)據(jù)，采用DEM可視化技術(shù)，導(dǎo)入MultiGen Creator［11］地形建模工具生成的視圖如圖7所示。

5 結(jié)語(yǔ)

三維海底地形圖在在軍事仿真、水下作業(yè)、游戲開(kāi)發(fā)和虛擬現(xiàn)實(shí)等方面都有十分廣闊的應(yīng)用前景。本文綜合利用離散的水深信息構(gòu)建數(shù)字高程模型，推導(dǎo)了數(shù)字高程模型的三維分形內(nèi)插算法，并通過(guò)Matlab建模比較了傳統(tǒng)平滑內(nèi)插算法和分形插值算法，為三維水下地形圖提供了一種行之有效的實(shí)現(xiàn)方法。

［1］http：//www.noaa.gov/ocean.html［EB/OL］.

［2］沈海峰，李慶陽(yáng).電子海圖高程數(shù)據(jù)的離散化研究［C］//廣州：第四屆廣東海事高級(jí)論壇論文集，2012：94-97.

［3］申浩，田峰敏，趙玉新.基于VoronoiCells插值的三維海底地形圖生成方法［J］.系統(tǒng)仿真學(xué)報(bào)，2006，18（2）：444-446，450.

［4］趙凱，胡大斌，肖建波.基于數(shù)據(jù)融合的DEM插值與可視化［J］.計(jì)算機(jī)仿真，2012，29（7）：144-146，213.

［5］朱華，姬翠翠.分形理論及其應(yīng)用［M］.北京：科學(xué)出版社，2011.1，27-47.

［6］邱秋香.三維海底地形仿真技術(shù)的研究與實(shí)現(xiàn)［D］.哈爾濱：哈爾濱工程大學(xué)，2011：9.

［7］盧福丹，陳元枝，蔡續(xù).三維海底地形仿真的研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2014，31（1）：77-80.

［8］陳颙，陳凌.分形幾何學(xué)［M］.北京：地震出版社，2005：5-6，35-44.

［9］孫洪泉.分形幾何與分形插值［M］.北京：科學(xué)出版社，2011：99-219.

［10］http：//en.wikipedia.org/wiki/SRTM［EB/OL］.

［11］王乘，周均清，李利軍.Creator可視化仿真建模技術(shù)［M］.武漢：華中科技大學(xué)出版社，2005：261，356.