運用三維Douglas-Peucker算法提取DEM地形特征

朱雪堅，葉遠智，湯國安

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

一、前 言

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

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

二、算法研究

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

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

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

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

2. 算法改進

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

圖1 算法流程圖

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

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

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

1. 基面的影響

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

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

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

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

2. 掃描方向的影響

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

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

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

四、結(jié)束語

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

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

參考文獻：

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

[2] 楊得志,王杰臣,閭國年.矢量數(shù)據(jù)壓縮的Douglas-Peucker算法的實現(xiàn)與改進[J].測繪通報,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] 費立凡,何津,馬晨燕,等.3維Douglas-Peucker算法及其在DEM自動綜合中的應(yīng)用研究[J].測繪學(xué)報,2006,35(3):278-284.

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

[6] 閭國年,錢亞東,陳鐘明.基于柵格數(shù)字高程模型提取特征地貌技術(shù)研究[J].地理學(xué)報,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的黃土地貌類型提取與制圖—以黃土高原丘陵溝壑實驗樣區(qū)為例[J].地球信息科學(xué),2003(4):110-113.