基于層次格網索引的高程點線矛盾快速識別方法

劉康甯，葉 勝，王方民，楊孟翰，陳 林

（1.重慶市地理信息和遙感應用中心，重慶 401147）

數字地形圖的生產過程中，儀器誤差、系統誤差、人工粗差及數據轉換等多種因素均可能導致高程點與等高線的高程值間出現邏輯矛盾[1-3]。高程點線矛盾作為數字地形圖的重要質量因子，解決這一問題是進行質量控制的關鍵環節[4-5]。點線矛盾的解決能夠有效提升高程數據的精度，為高程數據及衍生產品生產與分析、實景三維構建、土石方工程量算、長時間序列地形變化研究等應用提供更高精度的基礎數據，充分發揮數字地形圖中高程信息的應用價值。

本文針對當前高程點線矛盾檢查中存在的關鍵問題，提出了一種利用層次格網索引（hierarchical grid index，HGI）數據管理模式，與多進程并行機制相結合的高程點線矛盾快速識別方法，并通過充分梳理點線矛盾錯誤類型及高程點線空間位置關系進一步完善高程判斷邏輯，優化提升了識別方法的準確性和特殊地形下的適用性。

1 數據及錯誤類型

1.1 高程點線數據

本文選用從重慶市酉陽縣1∶10 000 國家基本比例尺地形圖中提取的高程點及等高線數據作為測試數據，等高距為5 m。等高線具有等值性、局部閉合性、連通性和高程遞變性等特征[6]。等高線連續且具有相同等高距D是高程點線矛盾檢查的必要條件[7]，因此從地形圖中提取了等高線的首曲線和計曲線，并消除了等高線自身的高程沖突問題，同時為測試在參照信息不全等特殊情況下，算法對高程數據點線矛盾的識別效果，未對數據中存在部分缺失的等高線進行補全。

1.2 點線矛盾類型歸納

受現實地形多樣性、復雜性影響，高程點數據呈隨機分布特征，點線矛盾在空間分布上不具有明顯規律性。從錯誤類型上來看，點線矛盾多為人工粗差，可進一步可歸納為：①高程邏輯沖突（圖1a）；②點線重合（值相等/值不相等）（圖1b）。

圖1 點線矛盾類型歸納示意圖

2 研究方法

2.1 層次格網索引

空間索引是指依據空間對象的位置和形狀，通過建立數據邏輯與存儲空間的對應關系來描述空間數據在存儲空間中位置的一種數據結構，良好的空間索引能夠大大加快空間數據的處理速度[8-9]。層次格網索引（HGI）是對整幅空間數據進行k次劃分（即k層），得到k層mk*nk（mk：k層行數，nk：k層列數）的數據結構，每個網格區域為一個索引項，并分配一個動態存儲區，滿足劃分條件的地理數據被存儲到對應的存儲空間中[10-11]。由于數字地形圖在生產和管理中均采用圖幅為基本單位，高程點線要素和在二維空間中表現出受圖幅約束的規律性分布狀態，采用層次格網索引能夠更加靈活高效的進行數據組織和數據管理。

面狀格網要素以圖幅信息為依據，通過ArcGIS中的創建漁網工具生成圖幅對應的面狀格網數據，賦予每個面狀格網要素對應的圖幅編號屬性信息。面狀輔助格網數據在高程點線矛盾識別過程中，作為傳遞圖幅長寬尺寸數據的重要介質。

本文采用三層層次格網來構建索引關系（圖2），結合數字地形圖分幅管理模式及矢量高程要素圖形屬性關聯方式，分別設計了第一層和第三層空間，同時為解決點線矛盾運算的數據遍歷機制在應對大數據量時效率低下的問題，使用數據精細化管理的思路，從內部結構上精簡參與運算的數據量進而降低運算壓力，設計層次格網索引中間層，并設置了開放參數，用于中間層空間的精細化約束：第1 層以圖幅編號作為索引標簽，利用等高線及高程點圖幅編號屬性進行單元劃分；第2 層依據當前圖幅的面狀輔助格網數據最小外包矩形（MBR）按照式（1）可以獲取3個關鍵參數（左下角坐標P0(x0，y0)，長度步長?L，寬度步長?W），以上述參數為基礎將第2 層空間分割為m2×n2個小單元，同時構建要素在HGI第二層空間中的存入方式，點狀要素按照式（2）獲取對應的行列號，等高線環要素根據其MBR 中心點坐標按照式（2）獲取行列號，圖幅內部的等高線總體通過與HGI第2 層的單元進行求交，當存在相交關系時進行存入；第3 層將第2 層索引中單個要素的圖形及屬性分離存儲。

圖2 HGI模型設計

式中， MBRGrid為面狀輔助格網要素的最小外包矩形；Length 和Width 分別為MBR 的長寬屬性值；m2為HGI中間層空間分割行數；n2為HGI中間層空間分割列數。

式中， row 和col 分別為HGI 第2 層空間中的行列號；x和y分別為參與計算的點坐標X和Y的值。

2.2 點線矛盾判斷邏輯

基于高程點與等高線的空間位置關系進行點線矛盾判斷邏輯構建，如圖3 所示，高程點P 及等高線L1、L2、L3 的高程值分別為EP、EL1、EL2、EL3，等高距為D，L1 為高程點P 的最鄰近等高線，L2 為第二鄰近等高線，L3 是第三鄰近等高線，將高程點與等高線間的邏輯關系抽象概括為如圖3所示4 種情況，歸納出不存在點線矛盾時應滿足以下條件：

圖3 高程點線空間位置關系

1） 當EL1=EL2≠EL3時，高程點位于或緊鄰山脊、山谷、河流，其空間位置關系如圖3a，此時，若EL2>EL3，則高程點位于或緊鄰山脊，應滿足：(EP-EL1)

2） 當EL1≠EL2，且P點及L2上最近點構成線段與L1 相交時，高程點位于山頂或洼地（圖3b），若EL1>EL2，則應滿足：0<(EP-EL1)

3） 當EL1≠EL2，且P 點與L2 上最近點連成的線段和L1 不相交時，高程點位于山腰（圖3c），若EL1>EL2，則 應 滿 足： (0<(EL1-EP)

除上述情況外，部分高程點落在等高線上（圖3d），形成點線重合，點線高程應保持一致，此時，若滿足：EP=EL1記錄為位置異常，否則記錄為點線矛盾。

2.3 算法流程及多進程并行機制

運算效率是算法性能的重要指標，高程點線數據均為空間數據，相較于文本數據，空間圖形數據的計算往往會造成更多的運算耗時，通過對本文算法特征及常規并行方法的分析，本方法為CPU 密集型而非IO 密集型，多進程機制能夠更好的進行運算效率優化提升。本文方法在多進程機制下的算法流程如圖4所示。

圖4 算法流程圖

3 試驗與分析

本文方法針對構TIN 內插法對平三角處的局限性，以及放射線法運算效率偏低等問題進行了改進與完善，為進行算法測試和精度、效率比對，基于python 與arcpy 站點包進行方法實現，利用配置為AMD 16 核處理器、64 G 運行內存的計算機開展試驗與結果分析。從重慶市酉陽縣1∶10 000 國家標準比例尺地形圖中選取9 個圖幅（303 圖幅范圍：左上角起始圖幅編號H49G075014，右下角終止圖幅編號H49G077016）的矢量高程數據作為測試數據，測試數據共計22 142 條等高要素，5 010 個高程點要素，每幅圖幅平均等高線要素數為2 460 條，平均高程點要素數為557 個，酉陽縣地處武陵山區腹地，河流水系發達，是典型的喀斯特山區，多斷崖和落水洞發育，地形地貌復雜度高，矢量高程數據錯誤類型多樣，測試數據中共包含高程點錯誤50 個，用于精度測試。同時根據測試數據點線要素分布特征，本方法中HGI 中間層參數m和n均按16 取值，各方法測試結果如表1所示。

表1 不同方法對高程點線矛盾識別效果對比

識別精度方面：由表1 可知，放射線法的識別精度為86%，存在5個未成功識別的錯誤高程點，其中3個高程點為凹山頂，2個高程點處于河流處，另將2個臨近問題等高線（部分缺失）的正確高程點誤判為錯誤高程點；由于構TIN內插法僅能對非平三角區域的高程點數據進行判別，總體精度為66%，未成功識別的高程點有13個；其中2個為點線重合且高程值不相等，2個位于河流處，凹山頂處高程點3個，1個高程點臨近問題等高線（部分缺失），另有5個山腰處的錯誤高程點未被成功識別，同時構TIN 內插法還將4個位于數據邊緣處的正確高程點誤判為錯誤高程點；本文方法對50個錯誤高程點均進行了有效識別，但因缺少可參照高程信息，將1 個處于河流內且位于數據邊緣的正確高程點誤判為錯誤高程點，總體精度為98%。

運算效率方面：由于構TIN 內插法需要人工參與，無法實現全流程的自動化識別，因此不進行對比；放射線法的運算耗時為493.42 s，由于本文方法使用了更加細致的判斷邏輯，在未使用HGI索引的情況下，單個圖幅運算耗時為727.53 s，通過添加HGI索引，耗時優化為35.82 s，并行機制下（8 個進程）運算耗時進一步優化為5.27 s，運算效率較無索引且非并行狀態下提升2 個數量級（1/138）。可見HGI 對效率改善有著十分積極的作用，同時能夠充分結合多進程機制，實現運算效率的大幅提升。

文獻[9]對構TIN 法進行了優化，文獻[10]對常規放射線法進行了優化，利用上述優化方法進行算法實現和數據測試，并與本文方法進行對比分析，文獻[9]方法的錯誤識別精度與本方法相同，50 個錯誤高程點中，處于圖幅邊緣處的1 個錯誤高程點因可參照高程信息缺失導致內插等高線出現錯誤，錯誤高程點未能有效識別，同時該方法在應對較大數據量時，其反復構TIN 過程會引入較多耗時，運算耗時75.86 s。文獻[9]提出的有限方向法在提高運算效率的同時降低了對錯誤高程點的識別精度，共有7 個錯誤高程點未能成功識別，其中4 個位于山腰處，1 個位于河流處，另有2 個為點線重合且高程值不相等，此外由于檢索方向的減少，在圖幅邊緣處有2 個高程點出現誤判現象，總體精度為82 %，運算耗時107.32 s。本方法所采用的HGI 索引數據管理模式和多進程的運算機制能夠在平衡精度和效率方面有著更好的表現。為進一步測試方法的適用性與可靠性，從重慶市1∶10 000 基礎庫中隨機抽取9 個圖幅進行高程點錯誤檢查，通對比統計，本文方法對測試數據中存在的39 個錯誤高程點全部實現成功識別。相較于現有方法，本文方法在精度、效率、適用性方面表現良好。

4 結 語

本文將層次格網索引應用到高程點線矛盾檢查的過程中，進行并行機制設計，同時對點線矛盾錯誤類型及高程邏輯進行充分分析，結合等高線的空間位置關系完善判斷邏輯，在提高判斷精度的同時大幅提高了運算效率。