基于數字地形圖與分形理論的地形生成

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

（西北工業大學 電子信息學院，陜西 西安 710129）

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

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

1 ASTER GDEM概述

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

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

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

2 三維地形建模

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

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

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

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

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

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

圖2 jpeg文件Fig.2 Jpeg file

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

圖4 灰度值-高程值映射關系Fig.4 Gray value-elevation value mapping relation

很容易得到下面關系式：

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

2.2 Diamond-Square算法

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

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

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

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

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

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

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

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

2.3 高度控制

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

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

3 仿真實驗

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

OSG（OpenSceneGraph）是一套基于工業標準OpenGL構建的開源視景仿真開發工具包，主要為圖形圖像應用程序的開發提供場景管理與圖形渲染優化的功能。它封裝了OpenGL大部分的函數功能.

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

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

圖6 地形網格Fig.6 Terrain grid

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

4 結 論

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

[1]朱梅，陳健偉.基于VR的虛擬場景生成算法研究[J].電子測量技術，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]蔣一，魏駿.虛擬現實技術及其在軍事領域的應用[J].國外電子測量技術，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數據介紹與程序讀取[J].遙感應用，2011（6）:69-72.KANG Xiao-wei，FENG Zhong-kui.An introduction to ASTER GDEM and procedure reading[J].Remote Sensing Application，2011（6）:69-72.

[6]尤玉虎，周孝寬.數字圖像最佳插值算法研究[J].中國空間科學技術，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].四川大學學報：自然科學版，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.