基于數(shù)字地形圖與分形理論的地形生成

齊 敏，王 強，韓一紅，張小溪

（西北工業(yè)大學(xué) 電子信息學(xué)院，陜西 西安 710129）

地形是自然界中具有復(fù)雜特征的景物之一。由于具有三維真實感的地形[1-2]能夠逼真地反映真實世界，所以三維真實感地形的繪制方法一直是國內(nèi)外計算機圖形學(xué)領(lǐng)域研究的熱點。

目前，三維地形的生成方法大致可歸納為3種[3-4]：基于真實地形數(shù)據(jù)的地形繪制、分形地景仿真和曲面擬合地形仿真。本文提出一種基于數(shù)字地形圖并結(jié)合分形理論進行三維真實感地形生成的方法，可以得到近似真實地形的三維地形顯示。

1 ASTER GDEM概述

DEM（Digital Elevation Model）數(shù)據(jù)是用一組有序數(shù)值陣列形式表示地面高程的一種實體地面模型，其廣泛應(yīng)用于水文、農(nóng)業(yè)、軍事、氣象以及工程建設(shè)等各個方面。2009年6月30日，全球期待已久的ASTER GDEM[5]（Advanced Space borne Thermal Emission and Reflection Radiometer Global Digital Elevation Model）數(shù)據(jù)由日本經(jīng)濟產(chǎn)業(yè)省MEIT（Ministry of Economy，Trade and Industry）與 NASA （National Aeronautics and Space Administration）共同發(fā)布。該數(shù)據(jù)是NASA根據(jù)Terra近十年的詳盡觀測結(jié)果，

通過ASTER的近紅外波段的垂直向下成像傳感器和后視成像傳感器獲取立體像對，最終生成DEM數(shù)據(jù)。

ASTER GDEM數(shù)據(jù)可以通過國際科學(xué)數(shù)據(jù)服務(wù)平臺（http://datamirror.csdb.cn/）下載。下載的每個 ASTER GDEM 數(shù)據(jù)分片為一個zip格式壓縮文件，其解壓后包括3個文件：兩個img文件（DEM.img與NUM.img）與一個jpeg圖像文件。其中 ，DEM.img 為 DEM 文 件 ，NUM.img 為 QA（Quality Assurance）質(zhì)量評價文件，jpeg文件為DEM暈渲圖縮略圖。

2 三維地形建模

2.1 地形圖灰度值-高程值映射

讀取下載的ASTER GDEM數(shù)據(jù)中的DEM.img文件如圖1所示，對照圖2所示jpeg圖像，可以看出，jpeg圖像中的灰度信息即代表高程信息，灰度值越小，圖像越黑，表示的高程值越低；灰度值越大，圖像越亮，表示的高程值越高。

首先將jpeg地形圖進行縮放處理，為了方便后面的使用，將圖像像素處理成（2n+1）×（2n+1）。使用雙線性內(nèi)插法進行圖像的縮放插值。

雙線性內(nèi)插法[6]是利用周圍4個鄰點的灰度值在兩個方向上作線性內(nèi)插以得到待采樣點的灰度值，即根據(jù)待采樣點與相鄰點的距離確定相應(yīng)的權(quán)值計算出待采樣點的灰度值。放大后的地形圖圖像如圖3所示。

接下來對縮放后的圖像進行灰度值-高程值映射。假設(shè)圖像灰度值范圍為[g1，g2]，高程值范圍為[h1，h2]，采用最簡單的線性映射關(guān)系h=a×g+b，其中h表示高程值，g表示灰度值。映射關(guān)系如圖4所示。

圖1 DEM.img文件Fig.1 DEM.img file

圖2 jpeg文件Fig.2 Jpeg file

圖3 地形圖放大后圖像Fig.3 Amplified image of topographic map

圖4 灰度值-高程值映射關(guān)系Fig.4 Gray value-elevation value mapping relation

很容易得到下面關(guān)系式：

通過灰度值-高程值映射最終便得到一個將索引值（x，y）映射成高程值（Z值）的二維高度值數(shù)組。數(shù)組只需要存儲高度值，水平面方向的值可以通過分析數(shù)組時生成。

2.2 Diamond-Square算法

20世紀(jì)70年代，美籍法國科學(xué)家Mandelbrot為研究自然界中復(fù)雜、極不規(guī)則的幾何現(xiàn)象創(chuàng)立了分形幾何學(xué)，分形地形建模方法大致可為泊松階躍法、傅立葉濾波法、隨機中點移位法、以及小波變換等幾類。其中，隨機中點移位法是標(biāo)準(zhǔn)的分形幾何法，算法復(fù)雜度較低而且能快速生成自然景物圖形，應(yīng)用最為廣泛。常用的隨機中點移位法有兩種：一種是三角形中點移位法，這種方法的缺點是在細分過程中各中點的坐標(biāo)值不容易確定，細分的過程也不容易控制；另一種是正方形中點移位法，又稱為Diamond-Square算法，它將隨機中點移位方法用于正方形地平面而生成地面特征，是一種較為常用的中點隨機移位算法。

Diamond-Square算法[7-8]由Fourniew等提出，算法具體步驟如圖5所示。

圖5 中，取一矩形，頂點數(shù)為（2n+1）×（2n+1），設(shè)定正方形中 4個頂點的初始高度值 hA、hB、hC、hD，這些點是遞歸細分過程的起始點。遞歸細分過程分為下面兩步：

第一步：Diamond步。取正方形的4個角點，在正方形中點生成一個隨機值，中點為對角線的頂點。該中點的高度值為

式中，rand（d）為隨機變量擾動值，其取值范圍為[-d，d]；d表示在當(dāng)前迭代中的最大移位。關(guān)于隨機變量取值將在后面進行說明。

第二步：Square步。在已知5個點的情況下，分別計算出原始正方形四邊中點的高度值。這四邊中點的高度值與原始四個頂點相關(guān)聯(lián)，并且同時也要加上一個隨機數(shù)，這個隨機數(shù)與第一步中的隨機數(shù)滿足同一個分布。至此，我們已經(jīng)有9個點的高度值已知了，并且原始正方形被分為了4個小正方形。

由此看見，采用Diamond-Square算法將一個正方形經(jīng)過單獨一次細分過程，可得到4個正方形，第二次細分過程可得到16個正方形，第n次細分得到的正方形數(shù)目為22n。因此，采用Diamond-Square算法對地形生成速度很快，而且實現(xiàn)非常容易。

圖5 Diamond-Square算法原理Fig.5 Diamond-Square algorithm principle

2.3 高度控制

網(wǎng)格最終高度Z由受控制高度影響的隨機中點移位算法來計算。從高斯分布中選取隨機值rand（d），其中平均值u和標(biāo)準(zhǔn)偏差σ是控制高度的函數(shù)，這里的控制高度即是上面灰度值-高程值映射過程得到的高程值。

例如對于圖 5（b）中的 E 點，選取平均值 μE=ZE-（ZB+ZC）/2，標(biāo)準(zhǔn)偏差σE=h|μE|，最終便可得到E點的網(wǎng)格最終高度值。在上面式子中，ZE、ZB、ZC為對應(yīng)點處的地面控制高度，h為比例系數(shù)，取值范圍 0＜h＜1。

3 仿真實驗

在仿真實驗中，硬件環(huán)境為，AMD AthlonII X2 250 CPU 3.0GHz 1G內(nèi)存，ATI Radeon HD 4350；軟件環(huán)境為Windows XP下VC++2005以及三維圖形渲染引擎OSG。

OSG（OpenSceneGraph）是一套基于工業(yè)標(biāo)準(zhǔn)OpenGL構(gòu)建的開源視景仿真開發(fā)工具包，主要為圖形圖像應(yīng)用程序的開發(fā)提供場景管理與圖形渲染優(yōu)化的功能。它封裝了OpenGL大部分的函數(shù)功能.

在地形繪制過程中，通過紋理映射技術(shù)將高度數(shù)據(jù)轉(zhuǎn)化為地形圖形。從本質(zhì)上說紋理是物體表面的細小結(jié)構(gòu)，它可以是光滑表面的花紋、圖案，也可以是物體表面的三維結(jié)構(gòu)，還可以是粗糙的表面。紋理映射是把指定紋理映射到三維物體表面上的技術(shù)，形成最終的圖像。

三維地形的真實感顯示仿真結(jié)果如圖6、7所示。

圖6 地形網(wǎng)格Fig.6 Terrain grid

圖7 地形紋理映射效果Fig.7 Terrain texture mapping

4 結(jié) 論

文中采用ASTER GDEM數(shù)字地形圖與分形理論Diamond-Square算法相結(jié)合對三維地形進行仿真。首先通過數(shù)字地形圖灰度值-高程值映射來得到圖像像素對應(yīng)的高程值，然后利用Diamond-Square算法來產(chǎn)生逼真程度很高的地形，最終通過可視化技術(shù)生成高度真實感的三維地形圖形。仿真實驗表明，本文提出的方法能有效地生成具有真實感的三維地形，進一步工作將研究如何使三維地形圖顯示出更多的地貌細節(jié)信息與自然景物，就能更加逼真地模擬地形自然環(huán)境了，將更加有研究意義和研究價值。

[1]朱梅，陳健偉.基于VR的虛擬場景生成算法研究[J].電子測量技術(shù)，2011，10（6）:45-47.ZHU Mei，CHEN Jian-wei.Research ofvirtualscene generation algorithm based on VR[J].Electronic Measurement Technology，2011，10（6）:45-47.

[2]蔣一，魏駿.虛擬現(xiàn)實技術(shù)及其在軍事領(lǐng)域的應(yīng)用[J].國外電子測量技術(shù)，2007（1）:43-45.JIANG Yi，WEI Jun.Virtual reality technology and its application in the field of military[J].Foreign Electronic Measurement Technology，2007（1）:43-45.

[3]梁俊，王琪，劉坤良，等.基于隨機中點位移法的三維地形模擬[J].計算機仿真，2005，22（1）:213-215.LIANG Jun，WANG Qi，LIU Kun-liang，et al.3D terrain simulation based on the method of random mid-point displacement[J].Computer Simulation，2005，22（1）:213-215.

[4]周煒，董福安，吉楠.基于分形和高度圖控制的三維地形生成[J].電光與控制， 2007，14（4）:66-69.ZHOU Wei，DONG Fu-an，JI Nan.3D terrain generation based on fractal theory and elevation map control[J].Electronics Optics and Control， 2007，14（4）:66-69.

[5]康曉偉，馮鐘葵.ASTER GDEM數(shù)據(jù)介紹與程序讀取[J].遙感應(yīng)用，2011（6）:69-72.KANG Xiao-wei，F(xiàn)ENG Zhong-kui.An introduction to ASTER GDEM and procedure reading[J].Remote Sensing Application，2011（6）:69-72.

[6]尤玉虎，周孝寬.數(shù)字圖像最佳插值算法研究[J].中國空間科學(xué)技術(shù)，2005（3）:14-18.YOU Yu-hu，ZHOU Xiao-kuan.Research of optimal interpolation algorithm for digital image[J].Chinese Space Science and Technology，2005（3）:14-18.

[7]田雨.對分形算法中遞歸法的研究[J].四川大學(xué)學(xué)報：自然科學(xué)版，2007，44（5）:990-994.TIAN Yu.Research on recursion in fractal algorithm[J].Journal of Sichuan University：Natural Science Edition，2007，44（5）:990-994.

[8]馮曉峰，王樹宗.基于分形的真實感地形的生成研究[J].微計算機信息，2007，23（3）:288-290.FENG Xiao-feng，WANG Shu-zong.Study of real sense terrain generation based on fractal[J]. Microcomputer Information，2007，23（3）:288-290.