成毅
(東北石油大學(xué) 石油工程學(xué)院, 大慶 163000)
數(shù)字高程模型是數(shù)字地形模型的一個(gè)分支,當(dāng)數(shù)字地形模型中的地形屬性為高程時(shí),數(shù)字地形模型就稱為數(shù)字高程模型(DEM)。
隨著科技的發(fā)展,數(shù)字高程模型的相關(guān)理論與研究方法廣泛應(yīng)用于水文、氣象等各個(gè)領(lǐng)域[1]。因此,國內(nèi)外學(xué)者對(duì)DEM的模型進(jìn)行了深入的研究。葉海建對(duì)建立DEM模型的原理和影響DEM生成效率的因素進(jìn)行了分析,提出改進(jìn)DEM生成算法效率的關(guān)鍵點(diǎn)是改進(jìn)離散數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和其中的查找算法[2];安樂等采用四叉樹結(jié)構(gòu)對(duì)采樣數(shù)據(jù)進(jìn)行存儲(chǔ),使DEM模型的生成效率得到了顯著的提高,尤其是在數(shù)據(jù)量很大的情況下,效果非常明顯[3]。
在我國學(xué)者的努力下,我國關(guān)于數(shù)字高程模型的理論和方法取得了豐碩的成果[4],但是都未提出影響DEM建模效率的具體的模型,本文利用OpenGL,基于仿真實(shí)驗(yàn)結(jié)果,提出了效率模型,結(jié)果表明,該模型可靠度高,適用性強(qiáng),為未來提高DEM模型的生成效率提供了一定的思路。
近些年來,OpenGl作為一個(gè)性能卓越的三維圖形標(biāo)準(zhǔn)發(fā)展迅猛,它在本質(zhì)上是一個(gè)開放的三維圖形軟件包,包括了200多個(gè)圖像處理函數(shù)[5]。OpenGL獨(dú)立于操作系統(tǒng)和窗口系統(tǒng)[6],與硬件條件無關(guān),用它編寫的軟件可以在UNIX、Windows NT/XP等系統(tǒng)間實(shí)現(xiàn)移植[7],而且使用簡便,效率高。OpenGL不僅提供了基本的點(diǎn)線多邊形的繪制函數(shù)[8],而且提供了可以繪制復(fù)雜三維物體以及曲線和曲面的函數(shù),這就為實(shí)現(xiàn)三維地形可視化奠定了基礎(chǔ)。
使用OpenGL建立DEM的基本思想[9]是:根據(jù)采樣得到離散隨機(jī)分布的三維空間高程數(shù)據(jù),可以根據(jù)精度要求,首先對(duì)離散數(shù)據(jù)進(jìn)行網(wǎng)格劃分,然后再通過反距離權(quán)重插值法得到網(wǎng)格節(jié)點(diǎn)的高程值,進(jìn)而形成三維地形。
在眾多空間插值方法中,反距離權(quán)重插值法插值原理易于理解,算法簡單便于實(shí)現(xiàn),因此,常常作為離散點(diǎn)空間分析的傳統(tǒng)方法之一[10]。反距離權(quán)重插值法的基本思想是:以插值點(diǎn)與采樣點(diǎn)間的距離為權(quán)重進(jìn)行加權(quán)平均,離插值點(diǎn)越近,樣本點(diǎn)被賦予的權(quán)重就越大,離插值點(diǎn)越遠(yuǎn),樣本點(diǎn)被賦予的權(quán)重就越小,如圖1所示。
反距離權(quán)重插值如式(1)。
(1)
式(1)中,Z是插值點(diǎn)高程估計(jì)值;Zi是第i個(gè)插值點(diǎn)的高程值,di為第i個(gè)樣本點(diǎn)與插值點(diǎn)的歐幾里得距離;n是用于估算插值點(diǎn)值的樣點(diǎn)數(shù);p是冪。
圖1 反距離權(quán)重插值法示意圖
現(xiàn)有某一地區(qū)三維空間離散點(diǎn)數(shù)據(jù),基于此高程數(shù)據(jù),采用反距離權(quán)重插值法得到該地區(qū)高度圖,在OpenGL中對(duì)高度圖進(jìn)行網(wǎng)格化得到DEM。
在Windows 7系統(tǒng)和Visual C++6.0平臺(tái)上,建立的DEM的模型,如圖2所示。
圖2 分辨率為16時(shí)建立的DEM模型
利用VS2016的性能探查器進(jìn)行性能探查,如圖3所示。
圖3 性能探查
在圖3中的drawScene函數(shù)為建立DEM模型的主要函數(shù),總CPU消耗的時(shí)間包括執(zhí)行此函數(shù)中的代碼和此函數(shù)調(diào)用的函數(shù)中的代碼所花費(fèi)的時(shí)間,自CPU消耗的時(shí)間是執(zhí)行此函數(shù)中的代碼所花費(fèi)的時(shí)間。由此可以看出,建立DEM模型消耗的時(shí)間包括計(jì)算機(jī)建立DEM模型的時(shí)間和計(jì)算機(jī)調(diào)用數(shù)據(jù)的時(shí)間。因此,建立DEM的效率不僅與插值函數(shù)有關(guān),而且與數(shù)據(jù)的存儲(chǔ)和調(diào)用有關(guān)??傮w來說,建立DEM的效率與四方面因素有關(guān):采樣密度,網(wǎng)格劃分精度[11],數(shù)據(jù)的存儲(chǔ)和讀取效率,插值方法的搜索半徑[12]。
采樣密度即在同一區(qū)域內(nèi)采集的數(shù)據(jù)點(diǎn)個(gè)數(shù),如表1、圖4所示。
表1 不同采樣密度下建立DEM模型耗費(fèi)的建模時(shí)間(ms)
圖4 不同采樣密度下建立DEM模型耗費(fèi)的建模時(shí)間折線圖
從表1、圖4中可以清楚的看出,采樣密度越大,DEM建模所耗費(fèi)的時(shí)間越長,效率越低。
采樣密度越大,則需要存儲(chǔ)的數(shù)據(jù)就越多,這就直接造成了數(shù)據(jù)的存儲(chǔ)和讀取效率的降低,進(jìn)而降低了DEM的建模效率。
在Windows 7系統(tǒng)和Visual C++6.0平臺(tái)上,分辨率分別為32,16,8時(shí)建立DEM的模型,如圖5-8所示。
圖5 32×32網(wǎng)格地形圖
圖6 64×64網(wǎng)格地形圖
圖7 128×128網(wǎng)格地形圖
圖8 不同網(wǎng)格精度下建立DEM模型耗費(fèi)的建模時(shí)間折線圖
隨著網(wǎng)格劃分精度越來越高,建立的DEM的分辨率也越高,但與此同時(shí),建模所需要的時(shí)間也越多,建模效率越低,因此,在建立DEM模型時(shí)應(yīng)綜合考慮精度和時(shí)間的關(guān)系,如表2所示。
表2 不同網(wǎng)格劃分精度時(shí)建立DEM模型所耗費(fèi)時(shí)間
隨著網(wǎng)格劃分精度的增加,相同區(qū)域內(nèi)需要計(jì)算的網(wǎng)格節(jié)點(diǎn)數(shù)增多,那么需要搜索的采樣點(diǎn)數(shù)勢必就要增加,這就造成了周圍高程數(shù)據(jù)的搜索效率的降低。例如,在某一區(qū)域內(nèi),網(wǎng)格劃分精度為時(shí),在此區(qū)域內(nèi)需要計(jì)算高程值的網(wǎng)格節(jié)點(diǎn)數(shù)為54個(gè),反距離權(quán)重插值法計(jì)算一個(gè)網(wǎng)格節(jié)點(diǎn)時(shí)需要搜索12個(gè)周圍采樣點(diǎn),則在此區(qū)域內(nèi)一共需要搜索個(gè)采樣點(diǎn),當(dāng)網(wǎng)格劃分精度為時(shí),在此區(qū)域內(nèi)需要計(jì)算高程值的網(wǎng)格節(jié)點(diǎn)數(shù)變?yōu)?12個(gè),則在此區(qū)域內(nèi)一共需要搜索個(gè)周圍采樣點(diǎn),所以在確定網(wǎng)格精度的過程中必須權(quán)衡周圍高程數(shù)據(jù)的搜索效率這個(gè)重要因素。網(wǎng)格的精度劃分同樣會(huì)對(duì)數(shù)據(jù)的存儲(chǔ)和讀取效率產(chǎn)生影響。隨著網(wǎng)格精度的增加,相同區(qū)域內(nèi)需要存儲(chǔ)的高程數(shù)據(jù)就會(huì)不斷增多,計(jì)算網(wǎng)格節(jié)點(diǎn)時(shí)需要提取的采樣點(diǎn)高程數(shù)據(jù)也會(huì)隨之增多,這勢必就會(huì)造成內(nèi)存開銷的增大以及讀取效率的降低。網(wǎng)格劃分精度是通過數(shù)據(jù)的存儲(chǔ)和讀取以及周圍高程數(shù)據(jù)的搜索效率對(duì)插值方法的計(jì)算效率產(chǎn)生影響的[13]。在插值函數(shù)一定的情況下,隨著網(wǎng)格劃分精度越高的提高,數(shù)據(jù)索引速度和周圍高程數(shù)據(jù)的搜索效率都會(huì)逐漸降低,這在一定程度上就會(huì)降低插值函數(shù)的計(jì)算效率。綜上所述,網(wǎng)格劃分精度是四個(gè)因素里面最重要的一個(gè),我們?cè)谶M(jìn)行DEM建模時(shí)應(yīng)重點(diǎn)考慮其影響。
數(shù)據(jù)的存儲(chǔ)和讀取效率與網(wǎng)格劃分精度和插值方法的計(jì)算效率都有關(guān)聯(lián)。前面已經(jīng)介紹了網(wǎng)格劃分精度與數(shù)據(jù)的存儲(chǔ)和讀取效率的關(guān)系,這里僅介紹數(shù)據(jù)的存儲(chǔ)和讀取效率與插值方法的計(jì)算效率的關(guān)系。在計(jì)算網(wǎng)格節(jié)點(diǎn)的高程值時(shí),需要先搜索出網(wǎng)格節(jié)點(diǎn)周圍的高程數(shù)據(jù)點(diǎn),然后再提取出這些采樣點(diǎn)的高程值進(jìn)行插值計(jì)算[14]。從這個(gè)過程來看,提高數(shù)據(jù)的存儲(chǔ)和讀取效率有助于提高插值函數(shù)的計(jì)算效率。
數(shù)據(jù)的存儲(chǔ)和讀取效率的高低取決于數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)是否合理。合理的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)可以存儲(chǔ)文件數(shù)量較多和單個(gè)文件較大的數(shù)據(jù),在數(shù)據(jù)的提取時(shí)也會(huì)非常方便,如表3所示。
表3 采用數(shù)據(jù)以不同結(jié)構(gòu)存儲(chǔ)時(shí)生成DEM模型所需要時(shí)間
在采樣密度,網(wǎng)格劃分精度,插值方法以及周圍高程數(shù)據(jù)的搜索效率一定的情況下,采樣數(shù)據(jù)以不同的結(jié)構(gòu)存儲(chǔ)生成DEM模型時(shí),四叉樹結(jié)構(gòu)的效率明顯高于線性表。因此本文采用四叉樹結(jié)構(gòu)進(jìn)行數(shù)據(jù)的存儲(chǔ)和讀取。
四叉樹算法是一種空間均勻網(wǎng)格剖分方法,它的基本思想是:首先確定閾值nq,檢查區(qū)域內(nèi)的采樣點(diǎn)個(gè)數(shù)是否超過了閾值nq;如果超過了閾值nq,則將該區(qū)域進(jìn)行四等分,然后對(duì)4個(gè)子分區(qū)進(jìn)行同樣的遞歸操作,直到所有子分區(qū)的采樣數(shù)據(jù)個(gè)數(shù)均不超過該閾值為止。閾值的選取對(duì)四叉樹的深度和形態(tài)會(huì)產(chǎn)生重要的影響,分割閾值不同,算法的執(zhí)行效率不同,如圖9、10所示。
nq=3,m=4;
nq=6,m=3;
閾值nq越大,四叉樹深度m越小,建立DEM模型的耗費(fèi)的時(shí)間T就越少;閾值nq越小,四叉樹深度m越大,建立DEM模型耗費(fèi)的時(shí)間T就越多,如圖11、12所示。
圖11 四叉樹下建立DEM模型耗費(fèi)的建模時(shí)間折線圖
圖12 線性表下建立DEM模型耗費(fèi)的建模時(shí)間折線圖
搜索半徑越大,建立DEM模型所需要的時(shí)間越長,效率越低;反之,則時(shí)間越短,效率越高。在進(jìn)行DEM建模的過程中,需要對(duì)網(wǎng)格交點(diǎn)處的高程值進(jìn)行插值計(jì)算,而插值計(jì)算時(shí)則需要對(duì)周圍高程數(shù)據(jù)進(jìn)行搜索以獲得高程數(shù)據(jù)。搜索半徑越大(即計(jì)算一個(gè)網(wǎng)格節(jié)點(diǎn)時(shí)需要搜索的采樣點(diǎn)數(shù)越大),則計(jì)算機(jī)需要存儲(chǔ)的數(shù)據(jù)就越多,讀取時(shí)消耗的時(shí)間也越多,同時(shí),這也會(huì)增加插值計(jì)算時(shí)的時(shí)間復(fù)雜度。搜索半徑越小,則消耗的時(shí)間越少,效率越高,但同時(shí)插值計(jì)算出的網(wǎng)格節(jié)點(diǎn)高程值可能誤差較大;搜索半徑越大,消耗的時(shí)間越多,效率越低,但同時(shí)插值計(jì)算出的高程值誤差較小。因此,在選取搜索半徑時(shí),應(yīng)綜合考慮誤差和效率兩個(gè)因素,使其達(dá)到一個(gè)最優(yōu)的平衡。模擬實(shí)驗(yàn)結(jié)果,如表4、圖13所示。
表4 采用不同搜索半徑建立DEM模型所需要的時(shí)間
圖13 不同搜索半徑下建立DEM模型耗費(fèi)的建模時(shí)間折線圖
設(shè)DEM的建模效率為采樣密度為四叉樹數(shù)據(jù)結(jié)構(gòu)的閾值為,插值函數(shù)的搜索半徑為,則分析模擬實(shí)驗(yàn)結(jié)果可得:
ρ∝1U
δ∝1U
α∝1U
β∝1U
雖然DEM的建模效率受到五方面的因素影響,但是他們對(duì)建模效率的影響權(quán)重并不一樣,建立數(shù)學(xué)模型如式(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ù)的存儲(chǔ)和讀取效率,插值函數(shù)的搜索半徑網(wǎng)格劃分精度等四方面因素都會(huì)對(duì)DEM的建模效率產(chǎn)生影響,這四方面因素相當(dāng)于自變量,DEM的建模效率相當(dāng)于因變量,基于此種關(guān)系,使用最小二乘法計(jì)算各個(gè)因素所占的權(quán)重。
將上述模型進(jìn)行變形可得式(3)。
∑ni=1Xiβi=U
(3)
其中:Xi為影響DEM建模效率的五個(gè)因素,i=1,2,3,4,5;βi為各個(gè)因素所占的權(quán)重,i=1,2,3,4,5;
采樣密度,網(wǎng)格劃分精度,數(shù)據(jù)的存儲(chǔ)和讀取效率,插值方法搜索半徑,是DEM建模效率的四個(gè)主要影響因素。在這4個(gè)因素中,網(wǎng)格劃分精度對(duì)DEM的建模效率影響最大,起到牽一發(fā)而動(dòng)全身的作用,因此,在DEM建模時(shí),應(yīng)該重點(diǎn)考慮其影響,使精度和效率達(dá)到一個(gè)最優(yōu)的平衡。