成毅

(東北石油大學 石油工程學院， 大慶 163000)

0 引言

數(shù)字高程模型是數(shù)字地形模型的一個分支，當數(shù)字地形模型中的地形屬性為高程時，數(shù)字地形模型就稱為數(shù)字高程模型(DEM)。

隨著科技的發(fā)展，數(shù)字高程模型的相關理論與研究方法廣泛應用于水文、氣象等各個領域[1]。因此，國內(nèi)外學者對DEM的模型進行了深入的研究。葉海建對建立DEM模型的原理和影響DEM生成效率的因素進行了分析，提出改進DEM生成算法效率的關鍵點是改進離散數(shù)據(jù)的存儲結(jié)構(gòu)和其中的查找算法[2];安樂等采用四叉樹結(jié)構(gòu)對采樣數(shù)據(jù)進行存儲，使DEM模型的生成效率得到了顯著的提高，尤其是在數(shù)據(jù)量很大的情況下，效果非常明顯[3]。

在我國學者的努力下，我國關于數(shù)字高程模型的理論和方法取得了豐碩的成果[4]，但是都未提出影響DEM建模效率的具體的模型，本文利用OpenGL，基于仿真實驗結(jié)果，提出了效率模型，結(jié)果表明，該模型可靠度高，適用性強，為未來提高DEM模型的生成效率提供了一定的思路。

1 penGL

近些年來，OpenGl作為一個性能卓越的三維圖形標準發(fā)展迅猛，它在本質(zhì)上是一個開放的三維圖形軟件包，包括了200多個圖像處理函數(shù)[5]。OpenGL獨立于操作系統(tǒng)和窗口系統(tǒng)[6]，與硬件條件無關,用它編寫的軟件可以在UNIX、Windows NT/XP等系統(tǒng)間實現(xiàn)移植[7]，而且使用簡便，效率高。OpenGL不僅提供了基本的點線多邊形的繪制函數(shù)[8]，而且提供了可以繪制復雜三維物體以及曲線和曲面的函數(shù)，這就為實現(xiàn)三維地形可視化奠定了基礎。

使用OpenGL建立DEM的基本思想[9]是：根據(jù)采樣得到離散隨機分布的三維空間高程數(shù)據(jù)，可以根據(jù)精度要求，首先對離散數(shù)據(jù)進行網(wǎng)格劃分，然后再通過反距離權(quán)重插值法得到網(wǎng)格節(jié)點的高程值，進而形成三維地形。

2 反距離權(quán)重插值

在眾多空間插值方法中，反距離權(quán)重插值法插值原理易于理解，算法簡單便于實現(xiàn)，因此，常常作為離散點空間分析的傳統(tǒng)方法之一[10]。反距離權(quán)重插值法的基本思想是：以插值點與采樣點間的距離為權(quán)重進行加權(quán)平均，離插值點越近，樣本點被賦予的權(quán)重就越大，離插值點越遠，樣本點被賦予的權(quán)重就越小，如圖1所示。

反距離權(quán)重插值如式(1)。

(1)

式(1)中，Z是插值點高程估計值；Zi是第i個插值點的高程值，di為第i個樣本點與插值點的歐幾里得距離；n是用于估算插值點值的樣點數(shù)；p是冪。

圖1 反距離權(quán)重插值法示意圖

3 DEM地形模擬仿真

現(xiàn)有某一地區(qū)三維空間離散點數(shù)據(jù)，基于此高程數(shù)據(jù)，采用反距離權(quán)重插值法得到該地區(qū)高度圖，在OpenGL中對高度圖進行網(wǎng)格化得到DEM。

在Windows 7系統(tǒng)和Visual C++6.0平臺上，建立的DEM的模型，如圖2所示。

圖2 分辨率為16時建立的DEM模型

利用VS2016的性能探查器進行性能探查，如圖3所示。

圖3 性能探查

4 影響DEM建模的四方面因素

在圖3中的drawScene函數(shù)為建立DEM模型的主要函數(shù)，總CPU消耗的時間包括執(zhí)行此函數(shù)中的代碼和此函數(shù)調(diào)用的函數(shù)中的代碼所花費的時間，自CPU消耗的時間是執(zhí)行此函數(shù)中的代碼所花費的時間。由此可以看出，建立DEM模型消耗的時間包括計算機建立DEM模型的時間和計算機調(diào)用數(shù)據(jù)的時間。因此，建立DEM的效率不僅與插值函數(shù)有關，而且與數(shù)據(jù)的存儲和調(diào)用有關。總體來說，建立DEM的效率與四方面因素有關：采樣密度，網(wǎng)格劃分精度[11]，數(shù)據(jù)的存儲和讀取效率，插值方法的搜索半徑[12]。

4.1 采樣密度

采樣密度即在同一區(qū)域內(nèi)采集的數(shù)據(jù)點個數(shù)，如表1、圖4所示。

表1 不同采樣密度下建立DEM模型耗費的建模時間(ms)

圖4 不同采樣密度下建立DEM模型耗費的建模時間折線圖

從表1、圖4中可以清楚的看出，采樣密度越大，DEM建模所耗費的時間越長，效率越低。

采樣密度越大，則需要存儲的數(shù)據(jù)就越多，這就直接造成了數(shù)據(jù)的存儲和讀取效率的降低，進而降低了DEM的建模效率。

4.2 網(wǎng)格劃分精度

在Windows 7系統(tǒng)和Visual C++6.0平臺上，分辨率分別為32,16,8時建立DEM的模型，如圖5-8所示。

圖5 32×32網(wǎng)格地形圖

圖6 64×64網(wǎng)格地形圖

圖7 128×128網(wǎng)格地形圖

圖8 不同網(wǎng)格精度下建立DEM模型耗費的建模時間折線圖

隨著網(wǎng)格劃分精度越來越高，建立的DEM的分辨率也越高，但與此同時，建模所需要的時間也越多，建模效率越低，因此，在建立DEM模型時應綜合考慮精度和時間的關系，如表2所示。

表2 不同網(wǎng)格劃分精度時建立DEM模型所耗費時間

隨著網(wǎng)格劃分精度的增加，相同區(qū)域內(nèi)需要計算的網(wǎng)格節(jié)點數(shù)增多，那么需要搜索的采樣點數(shù)勢必就要增加，這就造成了周圍高程數(shù)據(jù)的搜索效率的降低。例如，在某一區(qū)域內(nèi)，網(wǎng)格劃分精度為時，在此區(qū)域內(nèi)需要計算高程值的網(wǎng)格節(jié)點數(shù)為54個，反距離權(quán)重插值法計算一個網(wǎng)格節(jié)點時需要搜索12個周圍采樣點，則在此區(qū)域內(nèi)一共需要搜索個采樣點，當網(wǎng)格劃分精度為時，在此區(qū)域內(nèi)需要計算高程值的網(wǎng)格節(jié)點數(shù)變?yōu)?12個，則在此區(qū)域內(nèi)一共需要搜索個周圍采樣點，所以在確定網(wǎng)格精度的過程中必須權(quán)衡周圍高程數(shù)據(jù)的搜索效率這個重要因素。網(wǎng)格的精度劃分同樣會對數(shù)據(jù)的存儲和讀取效率產(chǎn)生影響。隨著網(wǎng)格精度的增加，相同區(qū)域內(nèi)需要存儲的高程數(shù)據(jù)就會不斷增多，計算網(wǎng)格節(jié)點時需要提取的采樣點高程數(shù)據(jù)也會隨之增多，這勢必就會造成內(nèi)存開銷的增大以及讀取效率的降低。網(wǎng)格劃分精度是通過數(shù)據(jù)的存儲和讀取以及周圍高程數(shù)據(jù)的搜索效率對插值方法的計算效率產(chǎn)生影響的[13]。在插值函數(shù)一定的情況下，隨著網(wǎng)格劃分精度越高的提高，數(shù)據(jù)索引速度和周圍高程數(shù)據(jù)的搜索效率都會逐漸降低，這在一定程度上就會降低插值函數(shù)的計算效率。綜上所述，網(wǎng)格劃分精度是四個因素里面最重要的一個，我們在進行DEM建模時應重點考慮其影響。

4.3 數(shù)據(jù)的存儲和讀取效率

數(shù)據(jù)的存儲和讀取效率與網(wǎng)格劃分精度和插值方法的計算效率都有關聯(lián)。前面已經(jīng)介紹了網(wǎng)格劃分精度與數(shù)據(jù)的存儲和讀取效率的關系，這里僅介紹數(shù)據(jù)的存儲和讀取效率與插值方法的計算效率的關系。在計算網(wǎng)格節(jié)點的高程值時，需要先搜索出網(wǎng)格節(jié)點周圍的高程數(shù)據(jù)點，然后再提取出這些采樣點的高程值進行插值計算[14]。從這個過程來看，提高數(shù)據(jù)的存儲和讀取效率有助于提高插值函數(shù)的計算效率。

數(shù)據(jù)的存儲和讀取效率的高低取決于數(shù)據(jù)存儲結(jié)構(gòu)是否合理。合理的數(shù)據(jù)存儲結(jié)構(gòu)可以存儲文件數(shù)量較多和單個文件較大的數(shù)據(jù)，在數(shù)據(jù)的提取時也會非常方便，如表3所示。

表3 采用數(shù)據(jù)以不同結(jié)構(gòu)存儲時生成DEM模型所需要時間

在采樣密度，網(wǎng)格劃分精度，插值方法以及周圍高程數(shù)據(jù)的搜索效率一定的情況下，采樣數(shù)據(jù)以不同的結(jié)構(gòu)存儲生成DEM模型時,四叉樹結(jié)構(gòu)的效率明顯高于線性表。因此本文采用四叉樹結(jié)構(gòu)進行數(shù)據(jù)的存儲和讀取。

四叉樹算法是一種空間均勻網(wǎng)格剖分方法，它的基本思想是：首先確定閾值nq，檢查區(qū)域內(nèi)的采樣點個數(shù)是否超過了閾值nq；如果超過了閾值nq，則將該區(qū)域進行四等分，然后對4個子分區(qū)進行同樣的遞歸操作，直到所有子分區(qū)的采樣數(shù)據(jù)個數(shù)均不超過該閾值為止。閾值的選取對四叉樹的深度和形態(tài)會產(chǎn)生重要的影響，分割閾值不同，算法的執(zhí)行效率不同，如圖9、10所示。

nq=3,m=4;

nq=6,m=3;

閾值nq越大，四叉樹深度m越小，建立DEM模型的耗費的時間T就越少;閾值nq越小，四叉樹深度m越大，建立DEM模型耗費的時間T就越多，如圖11、12所示。

圖11 四叉樹下建立DEM模型耗費的建模時間折線圖

圖12 線性表下建立DEM模型耗費的建模時間折線圖

4.4 插值方法搜索半徑

搜索半徑越大，建立DEM模型所需要的時間越長，效率越低；反之，則時間越短，效率越高。在進行DEM建模的過程中，需要對網(wǎng)格交點處的高程值進行插值計算，而插值計算時則需要對周圍高程數(shù)據(jù)進行搜索以獲得高程數(shù)據(jù)。搜索半徑越大(即計算一個網(wǎng)格節(jié)點時需要搜索的采樣點數(shù)越大)，則計算機需要存儲的數(shù)據(jù)就越多，讀取時消耗的時間也越多，同時，這也會增加插值計算時的時間復雜度。搜索半徑越小，則消耗的時間越少，效率越高，但同時插值計算出的網(wǎng)格節(jié)點高程值可能誤差較大；搜索半徑越大，消耗的時間越多，效率越低，但同時插值計算出的高程值誤差較小。因此，在選取搜索半徑時，應綜合考慮誤差和效率兩個因素，使其達到一個最優(yōu)的平衡。模擬實驗結(jié)果，如表4、圖13所示。

表4 采用不同搜索半徑建立DEM模型所需要的時間

圖13 不同搜索半徑下建立DEM模型耗費的建模時間折線圖

5 建立DEM的效率分析模型

設DEM的建模效率為采樣密度為四叉樹數(shù)據(jù)結(jié)構(gòu)的閾值為，插值函數(shù)的搜索半徑為，則分析模擬實驗結(jié)果可得：

ρ∝1U

δ∝1U

α∝1U

β∝1U

雖然DEM的建模效率受到五方面的因素影響，但是他們對建模效率的影響權(quán)重并不一樣，建立數(shù)學模型如式(2)。

U(ρ,α,β,γ,δ)=aρ+bα+cβ+dδ=ab

cdρβ

αδ

(2)

式(2)中:a為采樣密度影響權(quán)重；b為四叉樹數(shù)據(jù)結(jié)構(gòu)的閾值的影響權(quán)重；c為插值函數(shù)的搜索半徑影響權(quán)重；d為網(wǎng)格劃分精度的影響權(quán)重；

此模型中的采樣密度，網(wǎng)格精度，數(shù)據(jù)的存儲和讀取效率，插值函數(shù)的搜索半徑網(wǎng)格劃分精度等四方面因素都會對DEM的建模效率產(chǎn)生影響，這四方面因素相當于自變量，DEM的建模效率相當于因變量，基于此種關系，使用最小二乘法計算各個因素所占的權(quán)重。

將上述模型進行變形可得式(3)。

∑ni=1Xiβi=U

(3)

其中:Xi為影響DEM建模效率的五個因素，i=1,2,3,4,5;βi為各個因素所占的權(quán)重，i=1,2,3,4,5;

6 總結(jié)

采樣密度，網(wǎng)格劃分精度，數(shù)據(jù)的存儲和讀取效率，插值方法搜索半徑，是DEM建模效率的四個主要影響因素。在這4個因素中，網(wǎng)格劃分精度對DEM的建模效率影響最大，起到牽一發(fā)而動全身的作用，因此，在DEM建模時，應該重點考慮其影響，使精度和效率達到一個最優(yōu)的平衡。