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

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

0 引言

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

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

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

1 研究數(shù)據(jù)及等高線高程錯(cuò)誤類型

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

2 研究方法

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

圖1 本文方法技術(shù)路線

2.1 層次格網(wǎng)檢索

圖幅是數(shù)字地形圖管理的基本單位，在二維空間中等高線呈現(xiàn)受圖幅約束的分布狀態(tài)，層次格網(wǎng)索引能靈活高效地進(jìn)行數(shù)據(jù)組織管理[18,19]。本文采用3層格網(wǎng)索引構(gòu)建索引關(guān)系及數(shù)據(jù)結(jié)構(gòu)(圖2)：第1層以圖幅編號(hào)作為索引標(biāo)簽，進(jìn)行單元?jiǎng)澐?；?層對(duì)每個(gè)圖幅進(jìn)一步劃分，借助輔助格網(wǎng)對(duì)象(圖3)創(chuàng)建圖幅上、下、左、右(U、D、L、R)4個(gè)方向上的空間單元，計(jì)算等高線要素與各空間單元輔助格網(wǎng)要素的距離，當(dāng)?shù)雀呔€與輔助格網(wǎng)間關(guān)系滿足式(1)時(shí)，等高線存入輔助格網(wǎng)對(duì)應(yīng)的空間單元中；第3層將第2層索引中單個(gè)等高線的圖形及屬性分離存儲(chǔ)，為滿足高程錯(cuò)誤自動(dòng)修正的需求，第3層單元中添加了點(diǎn)單元“EndPoint”(等高線空間位置標(biāo)簽)。

Dis(Linecontour,Linegrid)

(1)

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

圖2 層次格網(wǎng)索引及數(shù)據(jù)結(jié)構(gòu)

圖3 輔助格網(wǎng)對(duì)象構(gòu)建及預(yù)處理

2.2 方向性二鄰域算法

八鄰域算法常被用于邊界檢測(cè)或?qū)Ρ萚20]，而八鄰域關(guān)系中包含單元間“線共用”和“點(diǎn)共用”兩種情況，通過對(duì)大量數(shù)據(jù)的分析可知，等高線要素落在圖幅單元共用點(diǎn)上的可能性幾乎為零，又考慮到數(shù)據(jù)運(yùn)算模塊的移動(dòng)具有方向性，故將八鄰域改進(jìn)為“先右移至行末、后跳轉(zhuǎn)下一行”的方向性二鄰域模塊。

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

圖4 算法優(yōu)化

2.3 邏輯錯(cuò)誤判定

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

(2)

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

(3)

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

圖5 等高線空間位置標(biāo)簽獲取

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

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

(4)

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

3 閾值設(shè)定對(duì)結(jié)果的影響

3.1 閾值設(shè)定對(duì)運(yùn)算精度的影響

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

(5)

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

圖7 運(yùn)算精度與效率結(jié)果分析

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

TLine_input(n)(x)=x+0.1

(6)

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

3.2 閾值設(shè)定對(duì)運(yùn)算效率的影響

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

兩個(gè)閾值對(duì)精度和效率均有重要影響，TSCLT主要影響SCLT的配對(duì)，合理的TSCLT能夠準(zhǔn)確構(gòu)建接邊處等高線的對(duì)應(yīng)關(guān)系，SCLT的精準(zhǔn)配對(duì)是實(shí)現(xiàn)高質(zhì)量自動(dòng)修正的關(guān)鍵；TLine_input可控制存入運(yùn)算空間的要素，結(jié)合層次格網(wǎng)索引降低參與運(yùn)算的數(shù)據(jù)量，既可保證運(yùn)算精度，又可大幅提高運(yùn)算效率。實(shí)驗(yàn)結(jié)果表明，根據(jù)數(shù)據(jù)特征獲取閾值具有可行性。

4 結(jié)果分析

4.1 修正效果對(duì)比

自動(dòng)修正前后的等高線如圖8(彩圖見封2)所示，其中淺藍(lán)色、紅色、深藍(lán)色線條分別為不存在高程錯(cuò)誤的等高線、存在高程錯(cuò)誤的等高線和修正后的等高線。對(duì)比發(fā)現(xiàn)，本文方法有效識(shí)別并修正了存在高程錯(cuò)誤的等高線數(shù)據(jù)。

4.2 不同錯(cuò)誤類型的識(shí)別和修正效果

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

圖8 修正前后等高線對(duì)比

表1 高程沖突識(shí)別精度統(tǒng)計(jì)

(2)高程錯(cuò)誤自動(dòng)修正方面(表2，TSCLT=0.9 m，TLine_input=2.3 m)，自動(dòng)修正總體精度可達(dá)91.53%，表明算法能夠?qū)Α叭藶榇植睢?、“缺少有效信息”、“?shù)據(jù)變形”3種錯(cuò)誤類型進(jìn)行有效修正。其中，“人為粗差”的修正精度為100%，“數(shù)據(jù)變形”的修正精度為73.33%，“缺少有效信息”的修正精度為88.89%，另有3條等高線因識(shí)別過程出現(xiàn)錯(cuò)判，導(dǎo)致錯(cuò)誤修改了原本正確等高線的高程值，在總體精度計(jì)算時(shí)計(jì)入分母。經(jīng)進(jìn)一步統(tǒng)計(jì)，共有9條等高線未被成功修正，其中7條位于山丘處，1條位于溝谷處，1條位于河流處?？梢姡闯晒π拚牡雀呔€多處于地形地貌較復(fù)雜區(qū)域，地形平緩區(qū)域修正效果良好。

表2 高程錯(cuò)誤自動(dòng)修正精度統(tǒng)計(jì)

4.3 不同方法識(shí)別精度及運(yùn)算效率對(duì)比

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

表3 不同方法對(duì)接邊處高程沖突識(shí)別效果對(duì)比

5 結(jié)論

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