方　敏，霍　亮，宋　磊，鮑　鵬，王　銳，田　軍

(1. 北京建筑大學測繪與城市空間信息學院，北京 100044； 2. 現(xiàn)代城市測繪國家測繪地理信息局重點實驗室，北京 100044； 3. 北京城建勘測設計研究院有限責任公司，北京 100101)

同名要素匹配是空間數(shù)據(jù)集成、更新和融合的關鍵技術，線要素是矢量空間數(shù)據(jù)的常見類型，其匹配也是當前空間數(shù)據(jù)匹配領域研究的焦點之一[1]。目前，線要素匹配采用的方法有緩沖區(qū)分析法[2-3]、幾何距離法(Hausdorff、Fréchet距離)[4-5]、結構拓撲法[6-7]等，在得到匹配候選指標后，可以進一步采用概率松弛法[8]和模糊信息處理理論[9]尋找最優(yōu)匹配，采用穩(wěn)健估計[10]等方法剔除錯誤匹配，得到最終的匹配結果。

現(xiàn)有的線要素匹配文獻主要是針對GPS軌跡[11]或城市簡單路網(wǎng)[3]，而對一些拓撲結構較為復雜的線要素研究較少，諸如水系網(wǎng)和復雜道路網(wǎng)的匹配，這些線要素在匹配時必須考慮要素的連續(xù)性和拓撲一致性等特征。本文設計了一種基于節(jié)點相似度，顧及拓撲、方向、距離等多方面特征的線要素匹配方法，在保證拓撲一致性的前提下，為線要素匹配提供了切實可行的技術方案。

1　線要素匹配模型設計

要素匹配主要是根據(jù)不同數(shù)據(jù)源中對同名實體的識別和數(shù)據(jù)交換，根據(jù)要素的數(shù)據(jù)特點對同名實體之間的相似性進行判斷，以此來確定是否相互匹配[12]?？紤]空間數(shù)據(jù)在尺度及空間變換上于平移、旋轉、縮放和數(shù)據(jù)綜合方面存在的任意性，根據(jù)線要素的幾何特征和圖論拓撲連通關系，確定要選取的度量指標，以節(jié)點、方向、距離3個因子作為匹配指標，其中節(jié)點處包含的點集為主要匹配對象，其對應的節(jié)點相似度為匹配的主要前提。

本文設計的線要素匹配模型，定義了3種類型的空間關系約束，分別為：拓撲約束(節(jié)點相似度)、方向約束(方向相似度)、距離約束(位置相似度)。首先利用節(jié)點的度來進行粗匹配；然后在滿足方向和距離約束的前提下，對候選匹配集中每個實體的方向和位置兩個匹配約束參數(shù)進行歸一化處理，并加權計算總的空間相似值；最后選取空間相似值最大的點集作為最終的同名節(jié)點。

1.1　節(jié)點相似度

節(jié)點的度是源于復雜網(wǎng)絡的一個概念，在網(wǎng)絡中，節(jié)點的度就是這個節(jié)點與其他節(jié)點相連接邊的數(shù)量[13]。相似度測量的是一對節(jié)點之間的親密程度，從結構上看，如果兩個節(jié)點的連接情況很相似，那么這兩個節(jié)點可能是一對同名點。

在匹配的過程中，以節(jié)點相似度為判斷的先決條件，如果節(jié)點的度一致，則加入候選匹配點集中，若節(jié)點的度不一致，則予以排除。即對于給定的目標數(shù)據(jù)集中一個節(jié)點Pi，首先給定一個緩沖區(qū)半徑R，然后在參考數(shù)據(jù)集中尋找緩沖區(qū)范圍之內的節(jié)點，依次記為Mi1，Mi2，…，Min，它們構成候選匹配點集，記為Qi。本文定義的節(jié)點相似度約束為

TPNode(Pi)=TPNode(Mij)=n

(1)

式中，n表示節(jié)點的連通度。

1.2　方向相似度

空間要素間的方向差異性常用空間要素方向的夾角表示[14]。在復雜的網(wǎng)絡中，線要素是互相連通的，方向用來判斷線要素的走向，可以作為相似性度量的一個重要因子。本文通過計算線要素節(jié)點的順時針夾角來進行方向的度量，即以正北方向為零指向，按順時針方向依次遞增，每個節(jié)點按連接弧段之間的夾角取值范圍為[0，180°]，如圖1所示。

圖1　夾角示意圖

圖1(a)、(b)分別為待匹配數(shù)據(jù)和參考數(shù)據(jù)，以O、O′為中心節(jié)點，落在圓周上的其余點均為與中心節(jié)點相連接的節(jié)點。計算弧段夾角時，需要設定好中心節(jié)點，找到與中心節(jié)點相連的一個端點作為計算的起始點，也是夾角計算方向的起點，以圖(a)為例，設置好中心節(jié)點O，與之相連的節(jié)點分別為A、B、C、D，從起始弧段(OA邊)順時針開始，依次計算與O關聯(lián)的4個弧段夾角。每個夾角采用余弦定理進行計算，相應的節(jié)點連接弧段方向約束定義為

(2)

式中，k表示第k個相應的連接弧段；Δ?表示連接弧段之間的方向差異閾值。

每個節(jié)點與之相連的節(jié)點個數(shù)為n(n>2)，則該節(jié)點與其他節(jié)點構成的夾角個數(shù)為n，依次計算待匹配數(shù)據(jù)和參考數(shù)據(jù)節(jié)點的各個夾角，通過判斷對應夾角差值和角度閾值的大小關系來度量二者的方向相似性。

1.3　位置相似度

位置是空間要素十分重要的特征，同名實體的位置差異在空間表達上表現(xiàn)為在空間位置上不能完全重合，基于這種思想，可以認為同名實體在空間距離上應該是非常接近的。線狀實體的相似可以采用距離特征來度量，主要是用來描述實體之間的位置關系，本文采用歐氏距離來進行距離的度量，節(jié)點之間的距離約束需滿足

(3)

式中，Δd表示兩節(jié)點之間的位置差異閾值。

基于圖1，在進行距離相似性度量時，從中心節(jié)點開始，以起始路段順時針方向計算與中心點相連的路段長度，每個節(jié)點與之相連的節(jié)點個數(shù)為n(n>2)，則該節(jié)點與其他節(jié)點構成的路段數(shù)量為n，依次計算待匹配數(shù)據(jù)和參考數(shù)據(jù)節(jié)點連接的路段長度，通過判斷對應路段距離差值和距離閾值的大小關系來度量二者的位置相似性。

1.4　空間相似值計算

本文根據(jù)線要素節(jié)點和弧段之間的拓撲關系，建立了待匹配數(shù)據(jù)節(jié)點集合S和參考數(shù)據(jù)節(jié)點集合R之間的多個度量指標約束的匹配判定標準。由幾種空間特征加權得到總的空間相似值V，計算公式為

(4)

(5)

式中，λa、λd分別表示方向夾角和距離因子兩個指標所占的權重；Va表示兩個線狀實體集合中所有節(jié)點的角度差值總和；Vd表示兩個線狀實體集合中所有節(jié)點弧段的距離差值總和；i為節(jié)點編號(i=0,1，…，n)。

空間相似值V經(jīng)過歸一化處理之后，返回值區(qū)間為[0，1]。值越大，表明數(shù)據(jù)越相似，則互為同名要素的可能性越高。

2　線要素匹配流程設計

2.1　匹配算法流程

基于節(jié)點相似度的線要素匹配算法，以上述線要素匹配模型為基礎，設計了包括數(shù)據(jù)預處理、候選匹配集獲取、3種空間關系約束、空間相似值計算、相似性判斷等內容的線要素匹配流程，匹配算法流程如圖2所示。

圖2　匹配算法流程

2.2　匹配過程描述

由上述算法，可實現(xiàn)線要素的特征點匹配，具體匹配過程可以描述為：

(1) 對參與匹配的目標數(shù)據(jù)和參考數(shù)據(jù)進行預處理，計算各自的節(jié)點和弧段集合。

(2) 對于給定半徑R，通過對目標數(shù)據(jù)節(jié)點設置緩沖區(qū)，獲取到匹配候選點集Qi1。

(3) 進行拓撲連通性分析，比較候選節(jié)點和目標節(jié)點的節(jié)點相似度：若相等，則加入候選點集合進入下一次判斷；反之進行剔除。由此得到候選匹配點集Qi2。

(4) 進行方向相似性判斷，比較匹配點對之間的弧段方向差值是否在閾值范圍內：若滿足閾值范圍，加入候選點集合進入下一次判斷；反之進行剔除。由此得到候選匹配點集Qi3。

(5) 進行位置相似性判斷，比較匹配點對之間的距離差值是否在閾值范圍內：若滿足閾值范圍，加入候選點集合；反之進行剔除。由此得到候選匹配點集Qi4。

(6) 計算總的空間相似值，在得到的Qi4點集中，通過計算加權之后的空間相似值V，選取相似值最大的點集作為最終的同名節(jié)點。

3　應用與實例

為了驗證本文匹配方法的有效性，以道路網(wǎng)為例，兩種數(shù)據(jù)源分別取自不同時期和不同部門生產(chǎn)的數(shù)據(jù)。選取某市天地圖數(shù)據(jù)和1∶25萬道路網(wǎng)數(shù)據(jù)進行驗證，以1∶25萬道路網(wǎng)數(shù)據(jù)作為待匹配數(shù)據(jù)，天地圖數(shù)據(jù)為參考數(shù)據(jù)，試驗數(shù)據(jù)如圖3所示。

圖3　試驗數(shù)據(jù)

3.1　數(shù)據(jù)預處理

數(shù)據(jù)結構的一致性是匹配的前提和基礎，不同來源的空間數(shù)據(jù)之間除了同名要素本身內容表達存在不一致的情況之外，二者在坐標系統(tǒng)、地圖投影、拓撲結構等方面均存在較大差異。如果要實現(xiàn)多源矢量數(shù)據(jù)的匹配，必須消除二者之間存在的差異，以保證數(shù)據(jù)結構的一致性。首先對匹配數(shù)據(jù)集進行統(tǒng)一的格式轉換、拓撲檢查和屬性檢查等處理，消除道路網(wǎng)數(shù)據(jù)之間的系統(tǒng)誤差，以保證拓撲結構的正確性，從而實現(xiàn)原始數(shù)據(jù)的正確關聯(lián)；然后提取道路網(wǎng)的特征點作為匹配的研究對象，以點線結構存儲的道路網(wǎng)，其特征點主要分為端點、節(jié)點、中點等類型，本文選取的匹配特征點主要是節(jié)點和端點。由于道路網(wǎng)本身的復雜性，其節(jié)點類型也是多種多樣的，主要有表1中幾種情況。

表1　道路網(wǎng)節(jié)點類型

在選取的道路特征點中，需要剔除度為2的偽節(jié)點，保證節(jié)點均出現(xiàn)在度大于2的交叉口處，道路網(wǎng)數(shù)據(jù)預處理前后對比如圖4所示。

圖4　數(shù)據(jù)對比

3.2　匹配應用與分析

兩套道路網(wǎng)數(shù)據(jù)經(jīng)過預處理之后，生成了目標路段6631條，參考路段4779條，兩套路網(wǎng)數(shù)據(jù)疊加效果如圖5所示。從中可以看出，數(shù)據(jù)在整體上差異較大，且多呈現(xiàn)出非線性偏差，但局部地區(qū)能夠較好地吻合。

利用本文算法進行道路網(wǎng)數(shù)據(jù)匹配時，考慮數(shù)據(jù)本身的尺度和精度因素，設置緩沖區(qū)半徑為500 m，方向角度差閾值為5°，距離差閾值為25 m，夾角因子權重0.8，距離因子權重0.2。匹配后部分同名點放大圖如圖6所示，對匹配后的結果進行統(tǒng)計分析，路網(wǎng)匹配正確率為93%，算法能識別出大部分的同名道路實體，主要是路段1∶1的匹配，由于受數(shù)據(jù)采集、區(qū)域等因素的影響，部分路網(wǎng)數(shù)據(jù)不能得到正確的匹配，且匹配結果呈現(xiàn)出多種復雜關系，如n∶1、1∶n和m∶n的匹配關系。針對這些未能正確匹配的路段，通過對參考數(shù)據(jù)集中的路段建立一定的距離閾值的緩沖區(qū)[15]，根據(jù)緩沖區(qū)與待匹配數(shù)據(jù)集中的路段的位置關系確定候選匹配路段，最后結合相似性度量指標確定候選匹配路段是否與參考路段匹配。對于一些局部地區(qū)存在較大差異的路網(wǎng)數(shù)據(jù)，在實際應用過程中，采用了人工輔助選點，保證了同名點的整體均勻分布。本文設計的線要素匹配算法已經(jīng)成功應用于大規(guī)模道路網(wǎng)數(shù)據(jù)匹配中，極大地提高了數(shù)據(jù)生產(chǎn)效率。

圖5　數(shù)據(jù)疊加

圖6　同名點匹配結果放大圖

4　結　語

本文針對多源矢量數(shù)據(jù)匹配問題，通過計算道路節(jié)點相似度，結合方向、距離指標的相似度量來確定線要素的匹配關系。通過試驗驗證，得出以下結論：①顧及拓撲關系和空間位置的多特征度量使得每個相似性特征具有較強的特征差異描述能力，多特征結合可以實現(xiàn)差異互補，整體具有更強的識別能力[16]；②該方法顧及了線要素的連續(xù)性和拓撲結構一致性，計算簡單，具有一定的實用性。

但本文算法還存在不足之處：①相似性特征之間的權值和閾值設定均是依賴于經(jīng)驗值，自適應能力較差；②文中的試驗是針對矢量道路網(wǎng)數(shù)據(jù)進行的，諸如水系網(wǎng)等不同類型的線要素數(shù)據(jù)匹配沒有經(jīng)過算法的驗證。這些問題將是下一步研究的方向。

參考文獻：

[1] 陳競男，錢海忠，王驍,等.提高線要素匹配率的動態(tài)化簡方法[J].測繪學報，2016，45(4):486-493.

[2] 胡云崗，陳軍，趙仁亮,等.地圖數(shù)據(jù)縮編更新中道路數(shù)據(jù)匹配方法[J].武漢大學學報(信息科學版)，2010，35(4):451-456.

[3] ZHANG Meng，MENG Liqiu.Delimited Stroke Oriented Algorithm-Working Principle and Implementation for the Matching of Road Networks[J].Geographic Information Sciences，2008，14(1):44-53.

[4] 陳玉敏，龔健雅，史文中.多尺度道路網(wǎng)的距離匹配算法研究[J].測繪學報，2007，36(1):84-90.

[5] DEVOGELE T.Matching Networks with Different Levels of Detail[J].Geoinformation,2008,12(4)：435-453.

[6] 應申，李霖，劉萬增,等.版本數(shù)據(jù)庫中基于目標匹配的變化信息提取與數(shù)據(jù)更新[J].武漢大學學報(信息科學版)，2009，34(6):752-755.

[7] 鄧敏，徐凱，趙彬彬,等.基于結構化空間關系信息的結點層次匹配方法[J].武漢大學學報(信息科學版)，2010，35(8):913-916.

[8] 趙東保，盛業(yè)華.全局尋優(yōu)的矢量道路網(wǎng)自動匹配方法研究[J].測繪學報，2010，39(4):416-421.

[9] 宗琴，鄧鑫潔，姜樹輝.模糊信息處理的道路網(wǎng)匹配方法[J].測繪科學，2016，41(3):167-170.

[10]欒學晨，楊必勝，李秋萍.基于結構模式的道路網(wǎng)節(jié)點匹配方法[J].測繪學報，2013，42(4):608-614.

[11]訾憲娟.基于浮動車軌跡數(shù)據(jù)的路網(wǎng)重構和地圖匹配[D].濟南：山東大學，2016.

[12]王鵬，鄭貴省，王元.基于多相似度量指標的路網(wǎng)匹配算法研究[J].微型機與應用，2016，35(1):19-22.

[13]王艷紅.基于節(jié)點相似度的復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)算法的研究[D].西安：西安電子科技大學，2014.

[14]翟仁健.基于全局一致性評價的多尺度矢量空間數(shù)據(jù)匹配方法研究[D].鄭州：解放軍信息工程大學，2011.

[15]WALTER V，F(xiàn)RITSCH D.Matching Spatial Data Sets：A Statistical Approach[J].International Journal of Geographical Information Science，1999，13(5):445-473.

[16]付仲良，楊元維，高賢君,等.道路網(wǎng)多特征匹配優(yōu)化算法[J].測繪學報，2016，45(5):608-615.