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

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

數(shù)字地形圖的生產(chǎn)過(guò)程中，儀器誤差、系統(tǒng)誤差、人工粗差及數(shù)據(jù)轉(zhuǎn)換等多種因素均可能導(dǎo)致高程點(diǎn)與等高線的高程值間出現(xiàn)邏輯矛盾[1-3]。高程點(diǎn)線矛盾作為數(shù)字地形圖的重要質(zhì)量因子，解決這一問(wèn)題是進(jìn)行質(zhì)量控制的關(guān)鍵環(huán)節(jié)[4-5]。點(diǎn)線矛盾的解決能夠有效提升高程數(shù)據(jù)的精度，為高程數(shù)據(jù)及衍生產(chǎn)品生產(chǎn)與分析、實(shí)景三維構(gòu)建、土石方工程量算、長(zhǎng)時(shí)間序列地形變化研究等應(yīng)用提供更高精度的基礎(chǔ)數(shù)據(jù)，充分發(fā)揮數(shù)字地形圖中高程信息的應(yīng)用價(jià)值。

本文針對(duì)當(dāng)前高程點(diǎn)線矛盾檢查中存在的關(guān)鍵問(wèn)題，提出了一種利用層次格網(wǎng)索引（hierarchical grid index，HGI）數(shù)據(jù)管理模式，與多進(jìn)程并行機(jī)制相結(jié)合的高程點(diǎn)線矛盾快速識(shí)別方法，并通過(guò)充分梳理點(diǎn)線矛盾錯(cuò)誤類(lèi)型及高程點(diǎn)線空間位置關(guān)系進(jìn)一步完善高程判斷邏輯，優(yōu)化提升了識(shí)別方法的準(zhǔn)確性和特殊地形下的適用性。

1 數(shù)據(jù)及錯(cuò)誤類(lèi)型

1.1 高程點(diǎn)線數(shù)據(jù)

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

1.2 點(diǎn)線矛盾類(lèi)型歸納

受現(xiàn)實(shí)地形多樣性、復(fù)雜性影響，高程點(diǎn)數(shù)據(jù)呈隨機(jī)分布特征，點(diǎn)線矛盾在空間分布上不具有明顯規(guī)律性。從錯(cuò)誤類(lèi)型上來(lái)看，點(diǎn)線矛盾多為人工粗差，可進(jìn)一步可歸納為：①高程邏輯沖突（圖1a）；②點(diǎn)線重合（值相等/值不相等）（圖1b）。

圖1 點(diǎn)線矛盾類(lèi)型歸納示意圖

2 研究方法

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

空間索引是指依據(jù)空間對(duì)象的位置和形狀，通過(guò)建立數(shù)據(jù)邏輯與存儲(chǔ)空間的對(duì)應(yīng)關(guān)系來(lái)描述空間數(shù)據(jù)在存儲(chǔ)空間中位置的一種數(shù)據(jù)結(jié)構(gòu)，良好的空間索引能夠大大加快空間數(shù)據(jù)的處理速度[8-9]。層次格網(wǎng)索引（HGI）是對(duì)整幅空間數(shù)據(jù)進(jìn)行k次劃分（即k層），得到k層mk*nk（mk：k層行數(shù)，nk：k層列數(shù)）的數(shù)據(jù)結(jié)構(gòu)，每個(gè)網(wǎng)格區(qū)域?yàn)橐粋€(gè)索引項(xiàng)，并分配一個(gè)動(dòng)態(tài)存儲(chǔ)區(qū)，滿足劃分條件的地理數(shù)據(jù)被存儲(chǔ)到對(duì)應(yīng)的存儲(chǔ)空間中[10-11]。由于數(shù)字地形圖在生產(chǎn)和管理中均采用圖幅為基本單位，高程點(diǎn)線要素和在二維空間中表現(xiàn)出受圖幅約束的規(guī)律性分布狀態(tài)，采用層次格網(wǎng)索引能夠更加靈活高效的進(jìn)行數(shù)據(jù)組織和數(shù)據(jù)管理。

面狀格網(wǎng)要素以圖幅信息為依據(jù)，通過(guò)ArcGIS中的創(chuàng)建漁網(wǎng)工具生成圖幅對(duì)應(yīng)的面狀格網(wǎng)數(shù)據(jù)，賦予每個(gè)面狀格網(wǎng)要素對(duì)應(yīng)的圖幅編號(hào)屬性信息。面狀輔助格網(wǎng)數(shù)據(jù)在高程點(diǎn)線矛盾識(shí)別過(guò)程中，作為傳遞圖幅長(zhǎng)寬尺寸數(shù)據(jù)的重要介質(zhì)。

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

圖2 HGI模型設(shè)計(jì)

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

式中， row 和col 分別為HGI 第2 層空間中的行列號(hào)；x和y分別為參與計(jì)算的點(diǎn)坐標(biāo)X和Y的值。

2.2 點(diǎn)線矛盾判斷邏輯

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

圖3 高程點(diǎn)線空間位置關(guān)系

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

2） 當(dāng)EL1≠EL2，且P點(diǎn)及L2上最近點(diǎn)構(gòu)成線段與L1 相交時(shí)，高程點(diǎn)位于山頂或洼地（圖3b），若EL1>EL2，則應(yīng)滿足：0<(EP-EL1)

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

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

2.3 算法流程及多進(jìn)程并行機(jī)制

運(yùn)算效率是算法性能的重要指標(biāo)，高程點(diǎn)線數(shù)據(jù)均為空間數(shù)據(jù)，相較于文本數(shù)據(jù)，空間圖形數(shù)據(jù)的計(jì)算往往會(huì)造成更多的運(yùn)算耗時(shí)，通過(guò)對(duì)本文算法特征及常規(guī)并行方法的分析，本方法為CPU 密集型而非IO 密集型，多進(jìn)程機(jī)制能夠更好的進(jìn)行運(yùn)算效率優(yōu)化提升。本文方法在多進(jìn)程機(jī)制下的算法流程如圖4所示。

圖4 算法流程圖

3 試驗(yàn)與分析

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

表1 不同方法對(duì)高程點(diǎn)線矛盾識(shí)別效果對(duì)比

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

運(yùn)算效率方面：由于構(gòu)TIN 內(nèi)插法需要人工參與，無(wú)法實(shí)現(xiàn)全流程的自動(dòng)化識(shí)別，因此不進(jìn)行對(duì)比；放射線法的運(yùn)算耗時(shí)為493.42 s，由于本文方法使用了更加細(xì)致的判斷邏輯，在未使用HGI索引的情況下，單個(gè)圖幅運(yùn)算耗時(shí)為727.53 s，通過(guò)添加HGI索引，耗時(shí)優(yōu)化為35.82 s，并行機(jī)制下（8 個(gè)進(jìn)程）運(yùn)算耗時(shí)進(jìn)一步優(yōu)化為5.27 s，運(yùn)算效率較無(wú)索引且非并行狀態(tài)下提升2 個(gè)數(shù)量級(jí)（1/138）?？梢?jiàn)HGI 對(duì)效率改善有著十分積極的作用，同時(shí)能夠充分結(jié)合多進(jìn)程機(jī)制，實(shí)現(xiàn)運(yùn)算效率的大幅提升。

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

4 結(jié) 語(yǔ)

本文將層次格網(wǎng)索引應(yīng)用到高程點(diǎn)線矛盾檢查的過(guò)程中，進(jìn)行并行機(jī)制設(shè)計(jì)，同時(shí)對(duì)點(diǎn)線矛盾錯(cuò)誤類(lèi)型及高程邏輯進(jìn)行充分分析，結(jié)合等高線的空間位置關(guān)系完善判斷邏輯，在提高判斷精度的同時(shí)大幅提高了運(yùn)算效率。