運(yùn)用三維Douglas-Peucker算法提取DEM地形特征

朱雪堅(jiān)，葉遠(yuǎn)智，湯國安

(1. 浙江省地理信息中心，浙江 杭州 310012; 2. 南京師范大學(xué) 虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210046)

一、前 言

地形特征的提取是近年研究的一個(gè)熱點(diǎn)。利用Douglas-Peucker算法提取地形特征具有效率高、提取效果好等優(yōu)點(diǎn)，因此，該算法廣泛應(yīng)用于矢量數(shù)據(jù)的壓縮和自動(dòng)綜合中。根據(jù)算法針對的數(shù)據(jù)不同，可以將該算法分為兩大類：二維Douglas-Peucker算法和三維Douglas-Peucker算法。文獻(xiàn)[1—3]針對二維Douglas-Peucker算法的特點(diǎn)，對其判斷條件等進(jìn)行優(yōu)化改進(jìn)，加快了算法的效率，提高了篩選精度。在三維算法方面，費(fèi)立凡等在二維Douglas-Peucker算法的基礎(chǔ)上，將原來的基線換成基面，點(diǎn)到線的距離換成點(diǎn)到面的距離，從而實(shí)現(xiàn)了從二維到三維數(shù)據(jù)化簡的擴(kuò)展，以及該算法在DEM地形特征提取和地形自動(dòng)綜合中的應(yīng)用[4-5]。

Douglas-Peucker算法從二維數(shù)據(jù)向三維數(shù)據(jù)化簡擴(kuò)展的兩個(gè)關(guān)鍵是初始基面的選取和掃描方向的確定。對于海量的DEM離散數(shù)據(jù)而言，采用稍有差異的起始基面進(jìn)行三維道格拉斯算法提取地形特征，在進(jìn)行多次迭代后提取的地形特征點(diǎn)將趨于接近，其結(jié)果不會(huì)有很大差異，但在局部部分則存在明顯差異。另外，不同的掃描方向?qū)μ崛〉牡匦翁卣鼽c(diǎn)也有重要影響。本文在原有三維Douglas-Peucker算法的基礎(chǔ)上，對初始基面、掃描方向等進(jìn)行了改進(jìn)與優(yōu)化，并對提取DEM地形特征點(diǎn)的方法進(jìn)行了探討。

二、算法研究

1. 樣區(qū)與數(shù)據(jù)

選擇陜北黃土高原的黃龍山、綏德、神木3個(gè)不同的地貌類型區(qū)作為試驗(yàn)樣區(qū)，分別代表了中山區(qū)、丘陵溝壑區(qū)、微丘區(qū)3種不同的地形復(fù)雜度。

以國家1∶1萬DEM(5 m分辨率)數(shù)據(jù)為基本數(shù)據(jù)源。由于Douglas-Peucker算法針對的是散點(diǎn)數(shù)據(jù)，因此，將所有樣區(qū)的DEM數(shù)據(jù)轉(zhuǎn)換成含(X，Y，Z)三維坐標(biāo)的散點(diǎn)數(shù)據(jù)，作為試驗(yàn)的原始數(shù)據(jù)(見表1)。

表1 試驗(yàn)樣區(qū)數(shù)據(jù)

2. 算法改進(jìn)

三維Douglas-Peucker算法涉及初始原點(diǎn)的選取和掃描方向的確定，不僅影響算法效率，而且影響提取結(jié)果。本文就這一問題探討不同的初始基面及不同的掃描方向?qū)Φ匦翁卣鼽c(diǎn)提取結(jié)果的影響程度。文獻(xiàn)[4—5]中對三維Douglas-Peucker算法已有詳細(xì)闡述，本文將著重闡述改進(jìn)方面(如圖1所示)。

圖1 算法流程圖

1) 初始基面。利用松弛原理人為選定原點(diǎn)、初始錨點(diǎn)和初始漂浮點(diǎn)，可以大大加快算法運(yùn)行的效率。但若原點(diǎn)、初始錨點(diǎn)和初始漂浮點(diǎn)中含有無值點(diǎn)或全為無值點(diǎn)(ArcGIS中高程值為-9999的點(diǎn))，原始算法將-9999認(rèn)為是一個(gè)有效值參與計(jì)算，使得初始基面“遠(yuǎn)離”DEM地表，不具備足夠的特征去“審視”整個(gè)DEM地表，從而不能提取令人滿意的地形特征點(diǎn)。本試驗(yàn)通過改變原點(diǎn)、初始錨點(diǎn)和初始漂浮點(diǎn)的初始高程，模擬不同的初始基面對提取的地形特征點(diǎn)的影響。試驗(yàn)選用的3個(gè)初始基面分別為：高程全為0的平面，下文中稱為0基面；高程全為該區(qū)域的平均高程，下文中稱為均值面；高程分別為區(qū)域內(nèi)的最小高程和平均高程，用以模擬地形走勢的基面，下文中稱為趨勢面。以此實(shí)現(xiàn)初始基面向DEM地表逐步逼近的過程。對于每個(gè)基面，采用3、10、20三個(gè)域值分別進(jìn)行提取。

2) 掃描方向。算法要依據(jù)一定的順序?qū)EM數(shù)據(jù)進(jìn)行有序掃描，而三維離散點(diǎn)是無序的。使用該算法進(jìn)行地形特征提取時(shí)，須對三維離散點(diǎn)進(jìn)行排序。而規(guī)則格網(wǎng)的DEM本身就具有行、列及對角線等方向，因此，文獻(xiàn)[4—5]以規(guī)則格網(wǎng)DEM中原有的行、列兩個(gè)方向?yàn)閮纱尾煌膾呙桧樞颍凑障刃?列)后列(行)的順序連續(xù)進(jìn)行壓縮，省掉了對三維離散點(diǎn)的排序過程，算法效率得到很大的提高。但是，行掃描獲得的是地形縱向特征點(diǎn)，列掃描獲得的是地形橫向特征點(diǎn)，同理，正反對角線的掃描也存在相似的特點(diǎn)。由于地貌自相似性的存在，一定的區(qū)域地貌形態(tài)具有一定的方向性，當(dāng)其與掃描方向之間存在一定的角度時(shí)，會(huì)導(dǎo)致某些重要的地形特征點(diǎn)在連續(xù)兩次(或多次)掃描時(shí)被忽略，從而丟失了一些局部的重要地形特征點(diǎn)。因此，行、列兩次掃描及正反對角線方向的掃描都應(yīng)基于原始數(shù)據(jù)進(jìn)行。

三、試驗(yàn)結(jié)果與分析

1. 基面的影響

本文分別利用0基面、均值面和趨勢面提取地形特征點(diǎn)，提取后的數(shù)據(jù)量見表2。試驗(yàn)結(jié)果顯示：0基面與均值面、趨勢面提取后所得數(shù)據(jù)量差異較大，而均值面與趨勢面之間的差異非常小。從圖2(a)、圖2(b)可以看出，與均值面相比，0基面丟失了大量的地形特征點(diǎn)，且在空間分布上，均值面所得的地形特征點(diǎn)分布更趨均勻和合理；圖2(b)、圖2(c)為均值面與趨勢面之間的比較，可以發(fā)現(xiàn)，兩者無論在所得到的地形特征點(diǎn)還是在空間分布上，基本上都一致。

以上試驗(yàn)結(jié)果顯示，初始基面的選取對不同地貌類型提取的DEM地形特征點(diǎn)都有重要影響，當(dāng)選取的初始基面“遠(yuǎn)離”整體DEM地表時(shí)，基面“審視”DEM全局特征的特點(diǎn)隨之減弱，將會(huì)損失部分非常重要的地形特征點(diǎn)，而這部分地形特征點(diǎn)主要位于左下角區(qū)域。離左下角越遠(yuǎn)的區(qū)域，基面的影響越小，這就使得提取的地形特征點(diǎn)在空間分布上較不均勻，如選取0基面為初始基面對綏德樣區(qū)進(jìn)行提取時(shí)，提取得到的地形特征點(diǎn)呈現(xiàn)沿地形走勢、高密低疏的特點(diǎn)；當(dāng)初始基面的選取越來越逼近DEM所表示的地表時(shí)，將能消除初始基面對局部區(qū)域(尤其是左下角區(qū)域)的影響，使提取的地形特征點(diǎn)在空間分布上更趨均勻與合理。

表2 不同基面、閾值下提取地形特征點(diǎn)后的數(shù)據(jù)量 kB

圖2 不同基面提取地形特征點(diǎn)結(jié)果對比(閾值為20)

2. 掃描方向的影響

分別用行、列、正對角線和反對角線4個(gè)掃描方向?qū)υ糄EM數(shù)據(jù)進(jìn)行掃描。從圖3中可以看出，行掃描得到的地形特征點(diǎn)基本上保留的是垂直方向上的，而損失了大量水平方向上的地形特征點(diǎn)；列掃描得到的地形特征點(diǎn)基本上保留的是水平方向上的，而損失了大量垂直方向上的地形特征點(diǎn)。當(dāng)兩者求并集后，絕大部分的地形特征均被很好地識別和保留。兩對角線方向掃描數(shù)據(jù)與行列方向掃描數(shù)據(jù)提取的地形特征點(diǎn)結(jié)果呈現(xiàn)很大的不同，但與行列方向掃描類似，正對角線方向掃描數(shù)據(jù)得到的是呈現(xiàn)一定反對角線方向分布的特征點(diǎn)，而反對角線方向掃描數(shù)據(jù)得到的是呈現(xiàn)一定正對角線方向分布的特征點(diǎn)。

其原因?yàn)椋谶M(jìn)行行掃描時(shí)，當(dāng)點(diǎn)到面的最大距離小于給定的閾值時(shí)，刪除點(diǎn)的方向是水平方向上的，因此水平方向上的特征點(diǎn)保留得較差；同理，進(jìn)行列掃描時(shí)，垂直向上的特征點(diǎn)也保留得較差；基于與行列掃描同樣原因，正對角方向掃描時(shí)，規(guī)則格網(wǎng)DEM中正對角方向同一列、相鄰行之間的高程相似性可能會(huì)被強(qiáng)加的邏輯遠(yuǎn)離所掩蓋，從而會(huì)丟掉一些行向本可保留的、有價(jià)值的點(diǎn)。在相同閾值下，反對角方向掃描的缺點(diǎn)也可類推。綜上所述，基于DEM提取地形特征點(diǎn)，由于三維道格拉斯算法方向性問題的存在，單一的某個(gè)掃描方向并不能很好地提取地形特征點(diǎn)，需要對原始數(shù)據(jù)作多個(gè)方向掃描，并對各方向掃描結(jié)果進(jìn)行并集處理，才能比較完整地提取地形特征點(diǎn)。

圖3 不同掃描方向結(jié)果對比(閾值為20)

四、結(jié)束語

在黃龍山、綏德和神木3個(gè)樣區(qū)的試驗(yàn)結(jié)果表明，0基面和均值面提取的地形特征點(diǎn)存在較大的差異，而均值面與趨勢面幾乎得到相同的結(jié)果，基本保留了地形特征點(diǎn)。因此，從地形簡化程度及特征點(diǎn)保留等方面考慮，選取均值面或趨勢面作為特征點(diǎn)選取的起始基面，都能比較完整地提取地形特征點(diǎn)。

基于三維Douglas-Peucker算法提取的地形特征點(diǎn)具有方向依賴性，文中以水平、垂直及兩對角線4個(gè)方向?yàn)樘崛〉匦翁卣鼽c(diǎn)的掃描方向。試驗(yàn)結(jié)果表明，僅考慮單一方向的掃描都不能很好地提取地形特征點(diǎn)，需要對多個(gè)掃描方向提取的地形特征點(diǎn)進(jìn)行合并處理，才能比較完全地提取地形特征點(diǎn)。因此，在利用改進(jìn)算法進(jìn)行地形特征提取時(shí)，應(yīng)進(jìn)行多方向掃描，提取不同的地形特征點(diǎn)，之后求各個(gè)掃描結(jié)果的并集，才能更加完整地提取地形特征點(diǎn)，為以后的地貌綜合做好準(zhǔn)備。

參考文獻(xiàn)：

[1] 劉曉紅,李樹軍.矢量數(shù)據(jù)壓縮的角度分段道格拉斯算法研究[J].四川測繪,2005,28(2):51-52.

[2] 楊得志,王杰臣,閭國年.矢量數(shù)據(jù)壓縮的Douglas-Peucker算法的實(shí)現(xiàn)與改進(jìn)[J].測繪通報(bào),2002(7):18-22.

[3] REN Yingchao, YANG Chongjun, YU Zhanfu,et al.A Way to Speed Up Buffer Generalization by Douglas-Peucker Algorithm[C]∥Proceedings of IGARSS. Anchorage, AK:IEEE, 2004.

[4] 費(fèi)立凡,何津,馬晨燕,等.3維Douglas-Peucker算法及其在DEM自動(dòng)綜合中的應(yīng)用研究[J].測繪學(xué)報(bào),2006,35(3):278-284.

[5] 何津,費(fèi)立凡.再論三維Douglas-Peucker算法及其在DEM 綜合中的應(yīng)用[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2008,33(2):160-163.

[6] 閭國年,錢亞東,陳鐘明.基于柵格數(shù)字高程模型提取特征地貌技術(shù)研究[J].地理學(xué)報(bào),1998,53(6):562-569.

[7] DOUGLAS D H， PEUCKER T K.Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature [J].The Canadian Cartographer,1973,10(2):112-122.

[8] 朱紅春,張友順,湯國安,等.基于DEM的黃土地貌類型提取與制圖—以黃土高原丘陵溝壑實(shí)驗(yàn)樣區(qū)為例[J].地球信息科學(xué),2003(4):110-113.