基于層次格網索引的圖幅接邊處等高線高程錯誤識別和自動修正研究

劉 康 甯，田 永 中*，沈 敬 偉，胡 曉 輝

(1.西南大學地理科學學院，重慶 400715；2.重慶稻田科技有限公司，重慶 400700；3.武漢大學遙感信息工程學院，湖北 武漢 430079)

0 引言

地表高程數據(如DEM)應用廣泛[1-3]，而等高線是構建DEM等的重要數據源之一[4]，早期地形圖存儲的等高線中蘊含著豐富的歷史高程信息，可有效延長地形研究的時間序列[5]，對地表高程長期規律的挖掘具有重要意義。但在數字化過程中，地形圖接邊處易產生人為粗差[6]，且兩圖間等高線處于分離狀態，參照數據不全，易產生誤判。現有軟件及算法對上述錯誤的識別修正功能仍不完善[7]。

地形圖接邊處等高線質量檢查的常用方法包括手工檢查、地理相關法及程序自動檢查等，其中手工檢查人工成本高且精度無保障，地理相關法的精度過分依賴參考數據的準確性[8]。在程序自動檢查方面：趙江洪[9]將數字地形圖的圖幅管理方式轉化為格網概念，曹健等[10]和黃會平等[11]在此基礎上利用格網及格網緩沖區數據優化接邊算法的效率，從而提高了端點匹配的效率；He等[12]通過改進傳統雙向掃描方法，提出了針對等高線的高程矛盾定向掃描檢查方法，但在數據量較大時算法處理效率較低；劉雄等[13]利用ArcPy進行等高線自動接邊和屬性一致性判斷，用端點代表等高線完成屬性檢查，但該方法僅處理了與邊界線相交的等高線，對變形等高線的適用性較低。

綜上發現，當前等高線質量改善研究多關注空間位置問題[14,15]，盡管涉及等高線一致性檢查，但詳細探討接邊算法效率改進的相對較少，且均未涉及自動修正研究。鑒于此，本文提出一種針對地形圖接邊處等高線高程屬性錯誤識別及自動修正的方法，利用層次格網索引(Hierarchical Grid Index,HGI)和方向性二鄰域算法(Directional Two-Neighborhood Algorithm，DTNA)提高運算效率，通過構建強空間位置關系和邏輯判斷實現自動修正功能。

1 研究數據及等高線高程錯誤類型

重慶市酉陽縣地處武陵山區腹地，是典型的喀斯特山區，地形復雜度高，選取該縣1∶1萬國家基本比例尺地形圖作為研究數據，該數據采用Xian_1980_3_Degree_GK_CM_108E投影，共計22 142條等高線，等高距為5 m。等高線高程錯誤類型多樣，部分數據變形明顯[16,17]，根據錯誤產生的原因，可將圖幅接邊處等高線高程錯誤分為4類：1)缺少相鄰圖幅內有效高程信息的參照，造成接邊處等高線增減走勢的判斷錯誤；2)地形圖生產人員造成的人為粗差；3)數據處理過程中產生的等高線數據變形；4)特殊地形等原因產生的偽高程錯誤。

2 研究方法

本文高程錯誤識別與修正方法的技術流程如圖1所示：1)將各圖幅轉化為格網數據，對格網進行特殊屬性構建、唯一標識化等預處理，獲得輔助格網。2)讀取不同圖幅的等高線，并通過數據處理構建3層格網索引，實現層次格網檢索。3)在方向性二鄰域運算模塊中：進行高程沖突識別，獲取驅動因子；獲取等高線空間位置標簽，執行基于空間位置的快速排序；依據驅動因子，執行高程邏輯錯誤雙向查找，進行錯誤判定和修正，并將修正結果匯總輸出。

圖1 本文方法技術路線

2.1 層次格網檢索

圖幅是數字地形圖管理的基本單位，在二維空間中等高線呈現受圖幅約束的分布狀態，層次格網索引能靈活高效地進行數據組織管理[18,19]。本文采用3層格網索引構建索引關系及數據結構(圖2)：第1層以圖幅編號作為索引標簽，進行單元劃分；第2層對每個圖幅進一步劃分，借助輔助格網對象(圖3)創建圖幅上、下、左、右(U、D、L、R)4個方向上的空間單元，計算等高線要素與各空間單元輔助格網要素的距離，當等高線與輔助格網間關系滿足式(1)時，等高線存入輔助格網對應的空間單元中；第3層將第2層索引中單個等高線的圖形及屬性分離存儲，為滿足高程錯誤自動修正的需求，第3層單元中添加了點單元“EndPoint”(等高線空間位置標簽)。

Dis(Linecontour,Linegrid)

(1)

式中：Dis(Linecontour,Linegrid)為等高線要素Linecontour與格網要素Linegrid間的距離；TLine_input為判斷等高線要素能否存入運算空間的閾值。

圖2 層次格網索引及數據結構

圖3 輔助格網對象構建及預處理

2.2 方向性二鄰域算法

八鄰域算法常被用于邊界檢測或對比[20]，而八鄰域關系中包含單元間“線共用”和“點共用”兩種情況，通過對大量數據的分析可知，等高線要素落在圖幅單元共用點上的可能性幾乎為零，又考慮到數據運算模塊的移動具有方向性，故將八鄰域改進為“先右移至行末、后跳轉下一行”的方向性二鄰域模塊。

在層次格網索引中，第2層索引對應U、D、L、R4個空間單元，本文對方向性二鄰域算法進行優化，相鄰圖幅間接邊處的數據運算實質上僅涉及(i，j)圖幅的D和R單元、(i+1，j)圖幅的U單元及(i，j+1)圖幅的L單元(圖4)。為進一步降低計算冗余，本文利用格網“Orientation”屬性，將參與運算的4個空間歸并為Inside和Outside兩個運算空間；同時，建立兩運算空間的吞吐式運算器，存入規則如圖4a所示，單輪計算中僅對參與運算的兩個空間進行數據填充。

圖4 算法優化

2.3 邏輯錯誤判定

2.3.1 基于空間位置標簽的快速排序算法 快速排序算法產生的內循環極小，在速度上具有明顯優勢[21]，特別是面對隨機數據時，快速排序性能極好[22]。一般定義歸屬于同一條等高線閉合曲線的多條曲線段互為理論同一等高線(Same Contour Line in Theory，SCLT)。等高線空間位置標簽(Contour Spatial Location Label，CSLL)是基于空間位置標簽快速排序算法的基礎，其獲取方法如圖5所示。僅將滿足式(2)的等高線對應存進格網兩側空間中，結合格網的“Orientation”屬性，通過式(3)獲得關鍵排序參數(KSP)，然后對要素及屬性進行快速排序，獲得空間上有序且一一對應的兩等高線空間，此時，相同索引值對應的兩空間中的等高線互為理論同一等高線(圖6)，從而構建等高線要素間的強位置關系。

(2)

式中：LineI、LineO分別為Inside、Outside空間內的等高線；TSCLT為理論同一等高線判斷閾值。

(3)

式中：Point為等高線的空間位置標簽；X和Y分別為橫、縱坐標值。

圖5 等高線空間位置標簽獲取

圖6 基于等高線空間位置標簽的快速排序算法

2.3.2 高程邏輯錯誤雙向查找與修正 高程邏輯錯誤雙向查找與修正的主要步驟為：1)根據判定條件(式(4))，將互為理論同一等高線且高程屬性不一致的要素記為高程沖突位點，將高程沖突處Inside空間內線要素、ID及CSLL作為驅動因子進行存儲匯總。2)基于已構建強空間位置關系的等高線，根據驅動因子在Inside空間中反向檢索得到索引值。3)以索引值為起點在兩側空間中分別向Head和Tail方向搜索高程值邏輯錯誤點，進行單方向查找，直到找到邏輯錯誤點后停止。4)待兩側空間均完成搜索，對比兩側在Head和Tail方向上所接觸到的等高線數量，數值小的判定為錯誤側；若相等，分別計算兩側空間當前索引跨度n下的高程差值，差值的絕對值大于n倍等高距的一側判定為錯誤。5)自動修改并記錄錯誤等高線。

(4)

式中：LineI_E和LineO_E分別為Inside和Outside空間中等高線的高程值。

3 閾值設定對結果的影響

3.1 閾值設定對運算精度的影響

3.1.1TSCLT測試TSCLT首先需排除TLine_input的影響，當TLine_input大于或等于接邊處要素與對應輔助格網間的最大距離時(本文測定結果為2.63 m)，圖幅中所有接邊處等高線均可進入運算空間。因此，在TLine_input=3 m時，對TSCLT的設定如式(5)所示。對不同TSCLT取值下運算精度的分析(圖7a)可知，TSCLT由0增至0.9 m的過程中，識別精度及修正精度均快速上升,在0.9 m處出現峰值，此時97.71%的高程沖突被正確識別，修正精度為88.89%；TSCLT>0.9 m時，識別精度呈持續下降趨勢，修正精度呈波動下降趨勢，在TSCLT為2.6 m和4 m時，錯誤配對的SCLT對自動修正的邏輯錯誤判斷提供了額外的高程信息，修正精度出現小幅上升，但兩曲線總體走勢近乎一致。

(5)

式中：x=-0.1為初始值；n=1,2，…，45為迭代次數。

圖7 運算精度與效率結果分析

3.1.2TLine_input通過統計分析可知,兩側圖幅間SCLT要素間最鄰近點的最大距離值為0.9 m，故設TSCLT=0.9 m，使TLine_input按照式(6)取值，得到精度變化情況(圖7b)。由圖7b可知，TLine_input為0～2.3 m時，隨著存入運算空間中的數據量增加，精度不斷提高,TLine_input=2.3 m時，修正精度達到最大值91.40%；TLine_input為2.4～2.7 m時，識別精度仍在上漲，TLine_input=2.7 m時，識別精度達到最大值97.71%，但修正精度出現小幅下降，最后兩精度均在TLine_input=2.7 m時保持不變。

TLine_input(n)(x)=x+0.1

(6)

式中：x=0為初始值，且0≤x≤4;n=1,2，…，40為迭代次數。

3.2 閾值設定對運算效率的影響

作為線要素進入運算空間的判斷條件，TLine_input對運算效率有直接影響,故本文討論TSCLT=0.9 m時，不同TLine_input取值下運算耗時的變化情況(圖7c)。1)當TLine_input<2.7 m時，運算效率與識別精度的變化趨勢基本相似；2)當TLine_input>2.7 m時，運算精度不再發生變化，但耗時仍在不斷增加，直至每次運算將所有數據存入；3)當TLine_input達到實驗數據圖幅尺寸的最大值6 102.78 m時，運算耗時為33 367.81 s，是TLine_input=2.7 m時(163.72 s)的203倍(向下取整)。由此可知，接邊處等高線存在大量缺失或嚴重變形時，運算效率會降低，故本方法在處理接邊處較為完整且變形較少的數據時，效率更高。

兩個閾值對精度和效率均有重要影響，TSCLT主要影響SCLT的配對，合理的TSCLT能夠準確構建接邊處等高線的對應關系，SCLT的精準配對是實現高質量自動修正的關鍵；TLine_input可控制存入運算空間的要素，結合層次格網索引降低參與運算的數據量，既可保證運算精度，又可大幅提高運算效率。實驗結果表明，根據數據特征獲取閾值具有可行性。

4 結果分析

4.1 修正效果對比

自動修正前后的等高線如圖8(彩圖見封2)所示，其中淺藍色、紅色、深藍色線條分別為不存在高程錯誤的等高線、存在高程錯誤的等高線和修正后的等高線。對比發現，本文方法有效識別并修正了存在高程錯誤的等高線數據。

4.2 不同錯誤類型的識別和修正效果

(1)高程沖突識別方面(表1，TSCLT=0.9 m，TLine_input=2.3 m)，總體上算法能夠對“人為粗差”、“缺少有效信息”、“數據變形”3種錯誤類型進行有效識別，特別是針對由“人為粗差”或“缺少有效信息”造成的高程沖突幾乎可以全部識別，對“數據變形”引起的高程沖突的識別精度為75.00%。除上述3種錯誤類型外，結果中還存在3條“偽高程錯誤”，致使算法產生了錯判，在總體精度計算中將其計入分母。

圖8 修正前后等高線對比

表1 高程沖突識別精度統計

(2)高程錯誤自動修正方面(表2，TSCLT=0.9 m，TLine_input=2.3 m)，自動修正總體精度可達91.53%，表明算法能夠對“人為粗差”、“缺少有效信息”、“數據變形”3種錯誤類型進行有效修正。其中，“人為粗差”的修正精度為100%，“數據變形”的修正精度為73.33%，“缺少有效信息”的修正精度為88.89%，另有3條等高線因識別過程出現錯判，導致錯誤修改了原本正確等高線的高程值，在總體精度計算時計入分母。經進一步統計，共有9條等高線未被成功修正，其中7條位于山丘處，1條位于溝谷處，1條位于河流處。可見，未成功修正的等高線多處于地形地貌較復雜區域，地形平緩區域修正效果良好。

表2 高程錯誤自動修正精度統計

4.3 不同方法識別精度及運算效率對比

利用本文方法及文獻[12，13]方法對實驗數據進行高程沖突識別對比(表3)。文獻[12]方法由于僅進行了相鄰等高線間的一致性判斷，對山區復雜地形的高程沖突識別效果不佳，21條等高線被錯判，另有61條未能成功識別，其中51條屬于區域性錯誤，該方法識別精度為65.55%；由于缺少有效的效率優化，其耗時67 774 s。文獻[13]方法容差值與本文方法閾值設置相同，利用邊界線提取和線轉點的方式優化了效率，運算耗時為817.01 s；由于該方法僅對邊界線上的點進行處理，錯判的概率較低，但也影響了其對變形等高線的兼容性，易發生識別遺漏(該方法識別遺漏的16條等高線中有13條存在較為嚴重的變形)。本文方法識別結果中，3條斷崖處等高線被錯判，無識別遺漏，識別精度為97.73%，且層次格網索引和方向性二鄰域算法的應用提高了運算效率，耗時僅為文獻[13]方法的20%。

表3 不同方法對接邊處高程沖突識別效果對比

5 結論

本文基于層次格網索引，綜合方向性二鄰域算法和基于空間位置標簽的快速排序算法，成功構建了接邊處等高線間的強空間位置關系，快速、準確地實現了高程錯誤的識別和修正，為等高線數據的質量改善提供了有效方法。層次格網索引與方向性二鄰域算法的結合，能夠合理減少參與運算的數據量，在保證運算精度的同時，能極大地縮短運算耗時，有效提高運算效率。本文方法精度受地表復雜度的影響，在處理地貌形態較為簡單的數據時精度更高;與其他方法對比，對區域性高程錯誤和數據變形具有更高的適用性。但本文方法對復雜地形的適用性有待提升，錯誤判斷邏輯需進一步完善，今后可將格網索引與分布式計算相結合，進一步提高運算效率。