開源GRASS軟件等高線生成DEM的算法改進

謝中凱，陳振杰，李飛雪

（1.江蘇省地理信息技術重點實驗室，江蘇 南京 210023）

傳統的由人工解譯地形獲取的等高線數據是建立DEM的重要數據源[1]。矢量等高線生成規則格網DEM的方法主要有3種[2,3]：①等高線構建TIN法，矢量等高線生成不規則三角網TIN，然后由TIN內插生成DEM；②等高線離散化法，矢量等高線離散化為數據點，然后采用一般插值方法（如IDW、Kriging插值法等）內插生成DEM[4]；③等高線內插法，矢量等高線按照預定方向直接內插生成DEM，或首先進行柵格化，然后由柵格化后的等高線內插生成DEM。

不同的GIS軟件在利用等高線生成DEM時采用了不同的方法，ArcGIS采用等高線構建TIN法生成DEM，該方法是利用等高線生成DEM的常用方法，但如果在TIN生成時沒有人工加入地面特征點，生成的TIN會有平三角形，這樣插值生成的DEM會產生“平山頂”現象和階梯狀地形。地理資源分析支持系統GRASS是開源GIS軟件[5]，采用等高線內插法生成DEM，分為矢量柵格化和柵格插值2個步驟，其中柵格插值采用線性內插方法，通過鄰近的等高線進行比例內插。本文分析了GRASS軟件中等高線生成DEM算法中存在的問題，并對算法進行了改進。

1 GRASS中DEM生成算法存在的問題

1）在矢量柵格化過程中，如果多條等高線通過一個柵格單元（圖1中為2條），該柵格單元的取值取決于最后進行柵格化的等高線的高程值（圖中紅色單元為待插值柵格單元，黑色單元為等高線柵格化后的柵格單元（稱為等高線柵格單元））。

圖1 2條等高線過同一柵格單元

2）在柵格插值過程中，沒有采用最近鄰的2條等高線進行內插，而是通過四方向Flood Fill算法尋找近鄰等高線。四方向Flood Fill算法的特點是可以避免在搜索時穿越等高線，具體思路為：對紅色柵格單元的鄰域按照“下、右、上、左”的順序進行搜索判斷（如圖2），對搜索到的非等高線柵格單元重復此操作，直到找到2個不同高程值的等高線柵格單元。當算法終止時（如圖3），搜索結果為具有不同高程值的藍色等高線柵格單元，但顯然紫色等高線柵格單元較上側的藍色柵格單元距離紅色待插值柵格單元更近，因此在插值時應當采用紫色等高線柵格單元。

圖2 四方向Flood Fill算法圖

圖3 四方向Flood Fill搜索結果圖

3）內插生成的DEM存在“平山頂”現象。對于圖4中的普通情況，A處所在的待插值柵格單元可通過Flood Fill算法找到2條不同高程值的等高線，采用式（1）進行線性內插。但是對于圖5中的山頂情況，由于Flood Fill算法搜索時不能穿越等高線，搜索結束時只能找到1條等高線，采用式（2）確定A點的高程值，那么被等高線Z1圍成的山頂將具有相同的高程值，生成的DEM存在“平山頂”現象。

圖4 普通情況

圖5 山頂情況

2 算法改進及實現

針對GRASS算法存在的3個問題，分別提出如下解決方案：

1）在矢量柵格化過程中，統計經過每個柵格單元的等高線的條數，并記錄其高程值，然后取高程平均值作為該柵格單元的取值。

2）在柵格插值過程中，采用鏈表記錄搜索到的等高線，每條等高線的信息作為一個鏈表結點，按距離升序排列，內插時取最近的2條等高線。在搜索過程中，當找到第2條等高線后，開始用前2條等高線的最大值作為搜索范圍的限制，減少柵格單元搜索的個數，加快搜索速度。

3）在柵格插值過程中，對于等高線圍成的山頂，采取二輪搜索策略，第二輪搜索時允許跨越一次等高線，使得山頂采用最近鄰的2條等高線進行趨勢內插[6]。在進行趨勢內插時，待插值柵格單元采用式（3）計算，并且應設定一個較小的正值，采用式（4）計算，避免山頂的高度過高。

3 算法實現及評價

等高線生成DEM的改進算法利用Visual Studio 2010平臺和GDAL庫，以C++語言實現，其中矢量柵格化采用Bresenham算法，柵格插值采用改進后的GRASS線性內插算法。算法測試選取面積約4 km2的山地區，原始DEM分辨率為5 m×5 m。首先由原始DEM獲取10 m等高線，然后用不同的算法由等高線重新插值生成DEM。算法評價通過3組DEM之間的比較，3組DEM分別為：ArcGIS軟件生成的DEM（未加入人工特征點）、GRASS軟件生成的DEM和本文改進算法生成的DEM。

在研究區內隨機生成500個隨機采樣點，進行DEM的精度評估[7]。圖6中，橫軸為原始DEM的采樣值，縱軸為不同算法生成的DEM的采樣值，可以看出3種算法得到的擬合直線斜率均接近1，擬合度R2值達到0.99以上。但是本文提出的算法擬合直線的斜率要高于其他2種，而截距要小于其他2種，說明改進后的算法取得了較好的效果，提高了插值精度。

對插值效果的評價，采用等高線回放法[8]。如圖7所示，紅色線為原始等高線，綠色線為不同算法生成的DEM回放得到的等高線。圖7a、b中回放得到的等高線與實際等高線相比，均在山頂處出現了失真現象，圖7a中還在等高線曲率較大的地方出現了失真現象，而圖7c中回放得到的等高線與實際等高線相比，誤差較小。圖7a中出現失真是因為在山頂等特殊地形處生成了平三角形，導致生成的DEM具有“平山頂”現象和階梯狀地形。圖7b中失真是因為山頂處插值時直接采用最近等高線賦值，導致生成的DEM具有“平山頂”現象。

圖6 不同算法生成的DEM精度評價

圖7 等高線回放比較

在特殊地形處的插值效果方面，選取山頂處DEM進行比較。圖8中上圖為不同算法生成的DEM，下圖為相應的山體陰影模型。圖8a、b中可以看到明顯的“平山頂”現象，而圖8c中這種現象得到了消除，與原始DEM相接近。

圖8 山頂處DEM生成比較

4 結 語

對開源GRASS軟件中等高線生成DEM的算法進行改進后能提高DEM生成的精度，解決了山體陡峭地區等高線生成DEM存在的“平山頂”問題。由于現實中地形是多變的，因此等高線的分布也是各異的，對于多條等高線經過同一柵格單元，下一步的研究可以考慮統計柵格單元內不同高程值的等高線的長度，然后以長度為權重計算單元取值。

[1]宋敦江, 岳天祥, 杜正平.由等高線建立DEM的YUEHASM方法研究[J].地球信息科學學報, 2009,11(3): 325-332

[2]張凱選, 潘夢清, 方輝, 等.利用等高線生成 DEM 方法的研究[J].測繪工程, 2007,16(3): 15-18

[3]楊曉云, 唐咸遠, 梁鑫.基于等高線生成DEM的內插算法及其精度分析[J].測繪工程, 2006,15(2):37-39

[4]徐瀟, 譚衢霖, 王浩宇, 等.復雜地貌地形圖等高線內插DEM算法的精度分析[J].遙感信息, 2013,28(6):111-115

[5]吳超.地理資源分析支持系統GRASS的研究與應用[D].武漢：華中科技大學，2005

[6]呂建峰, 劉定生，焦偉利, 等.DEM生成算法并行化研究[J].中國圖像圖形學報,2002, 7(5):506-512

[7]寇程, 柯長青.地形平坦地區DEM生成算法的比較研究[J].測繪與空間地理信息,2013, 36(7): 33-37

[8]唐新明, 林宗堅, 吳嵐.基于等高線和高程點建立DEM的精度評價方法探討[J].遙感信息,1999,14(3):7-10