節(jié)點(diǎn)相似度輔助下的線要素匹配方法設(shè)計(jì)

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

(1. 北京建筑大學(xué)測(cè)繪與城市空間信息學(xué)院，北京 100044； 2. 現(xiàn)代城市測(cè)繪國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，北京 100044； 3. 北京城建勘測(cè)設(shè)計(jì)研究院有限責(zé)任公司，北京 100101)

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

現(xiàn)有的線要素匹配文獻(xiàn)主要是針對(duì)GPS軌跡[11]或城市簡(jiǎn)單路網(wǎng)[3]，而對(duì)一些拓?fù)浣Y(jié)構(gòu)較為復(fù)雜的線要素研究較少，諸如水系網(wǎng)和復(fù)雜道路網(wǎng)的匹配，這些線要素在匹配時(shí)必須考慮要素的連續(xù)性和拓?fù)湟恢滦缘忍卣?。本文設(shè)計(jì)了一種基于節(jié)點(diǎn)相似度，顧及拓?fù)?、方向、距離等多方面特征的線要素匹配方法，在保證拓?fù)湟恢滦缘那疤嵯拢瑸榫€要素匹配提供了切實(shí)可行的技術(shù)方案。

1　線要素匹配模型設(shè)計(jì)

要素匹配主要是根據(jù)不同數(shù)據(jù)源中對(duì)同名實(shí)體的識(shí)別和數(shù)據(jù)交換，根據(jù)要素的數(shù)據(jù)特點(diǎn)對(duì)同名實(shí)體之間的相似性進(jìn)行判斷，以此來(lái)確定是否相互匹配[12]。考慮空間數(shù)據(jù)在尺度及空間變換上于平移、旋轉(zhuǎn)、縮放和數(shù)據(jù)綜合方面存在的任意性，根據(jù)線要素的幾何特征和圖論拓?fù)溥B通關(guān)系，確定要選取的度量指標(biāo)，以節(jié)點(diǎn)、方向、距離3個(gè)因子作為匹配指標(biāo)，其中節(jié)點(diǎn)處包含的點(diǎn)集為主要匹配對(duì)象，其對(duì)應(yīng)的節(jié)點(diǎn)相似度為匹配的主要前提。

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

1.1　節(jié)點(diǎn)相似度

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

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

TPNode(Pi)=TPNode(Mij)=n

(1)

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

1.2　方向相似度

空間要素間的方向差異性常用空間要素方向的夾角表示[14]。在復(fù)雜的網(wǎng)絡(luò)中，線要素是互相連通的，方向用來(lái)判斷線要素的走向，可以作為相似性度量的一個(gè)重要因子。本文通過(guò)計(jì)算線要素節(jié)點(diǎn)的順時(shí)針夾角來(lái)進(jìn)行方向的度量，即以正北方向?yàn)榱阒赶?，按順時(shí)針?lè)较蛞来芜f增，每個(gè)節(jié)點(diǎn)按連接弧段之間的夾角取值范圍為[0，180°]，如圖1所示。

圖1　夾角示意圖

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

(2)

式中，k表示第k個(gè)相應(yīng)的連接弧段；Δ?表示連接弧段之間的方向差異閾值。

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

1.3　位置相似度

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

(3)

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

基于圖1，在進(jìn)行距離相似性度量時(shí)，從中心節(jié)點(diǎn)開(kāi)始，以起始路段順時(shí)針?lè)较蛴?jì)算與中心點(diǎn)相連的路段長(zhǎng)度，每個(gè)節(jié)點(diǎn)與之相連的節(jié)點(diǎn)個(gè)數(shù)為n(n>2)，則該節(jié)點(diǎn)與其他節(jié)點(diǎn)構(gòu)成的路段數(shù)量為n，依次計(jì)算待匹配數(shù)據(jù)和參考數(shù)據(jù)節(jié)點(diǎn)連接的路段長(zhǎng)度，通過(guò)判斷對(duì)應(yīng)路段距離差值和距離閾值的大小關(guān)系來(lái)度量二者的位置相似性。

1.4　空間相似值計(jì)算

本文根據(jù)線要素節(jié)點(diǎn)和弧段之間的拓?fù)潢P(guān)系，建立了待匹配數(shù)據(jù)節(jié)點(diǎn)集合S和參考數(shù)據(jù)節(jié)點(diǎn)集合R之間的多個(gè)度量指標(biāo)約束的匹配判定標(biāo)準(zhǔn)。由幾種空間特征加權(quán)得到總的空間相似值V，計(jì)算公式為

(4)

(5)

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

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

2　線要素匹配流程設(shè)計(jì)

2.1　匹配算法流程

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

圖2　匹配算法流程

2.2　匹配過(guò)程描述

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

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

(2) 對(duì)于給定半徑R，通過(guò)對(duì)目標(biāo)數(shù)據(jù)節(jié)點(diǎn)設(shè)置緩沖區(qū)，獲取到匹配候選點(diǎn)集Qi1。

(3) 進(jìn)行拓?fù)溥B通性分析，比較候選節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)相似度：若相等，則加入候選點(diǎn)集合進(jìn)入下一次判斷；反之進(jìn)行剔除。由此得到候選匹配點(diǎn)集Qi2。

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

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

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

3　應(yīng)用與實(shí)例

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

圖3　試驗(yàn)數(shù)據(jù)

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

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

表1　道路網(wǎng)節(jié)點(diǎn)類(lèi)型

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

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

3.2　匹配應(yīng)用與分析

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

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

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

圖6　同名點(diǎn)匹配結(jié)果放大圖

4　結(jié)　語(yǔ)

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

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

參考文獻(xiàn)：

[1] 陳競(jìng)男，錢(qián)海忠，王驍,等.提高線要素匹配率的動(dòng)態(tài)化簡(jiǎn)方法[J].測(cè)繪學(xué)報(bào)，2016，45(4):486-493.

[2] 胡云崗，陳軍，趙仁亮,等.地圖數(shù)據(jù)縮編更新中道路數(shù)據(jù)匹配方法[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，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].測(cè)繪學(xué)報(bào)，2007，36(1):84-90.

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

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

[7] 鄧敏，徐凱，趙彬彬,等.基于結(jié)構(gòu)化空間關(guān)系信息的結(jié)點(diǎn)層次匹配方法[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2010，35(8):913-916.

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

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

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

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

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

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

[14]翟仁健.基于全局一致性評(píng)價(jià)的多尺度矢量空間數(shù)據(jù)匹配方法研究[D].鄭州：解放軍信息工程大學(xué)，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].測(cè)繪學(xué)報(bào)，2016，45(5):608-615.