王 鵬，鄭貴省，王 元

(1.軍事交通學(xué)院 研究生管理大隊，天津 300161；2.軍事交通學(xué)院 基礎(chǔ)部，天津 300161)

基于多相似度量指標(biāo)的路網(wǎng)匹配算法研究

王 鵬1，鄭貴省2，王 元1

(1.軍事交通學(xué)院 研究生管理大隊，天津 300161；2.軍事交通學(xué)院 基礎(chǔ)部，天津 300161)

路網(wǎng)數(shù)據(jù)融合是路網(wǎng)數(shù)據(jù)更新以及提升數(shù)據(jù)質(zhì)量的重要方法之一。而路網(wǎng)數(shù)據(jù)融合的關(guān)鍵技術(shù)在于路網(wǎng)匹配。結(jié)合路網(wǎng)數(shù)據(jù)源的特點，提出了一種顧及路段和結(jié)點拓?fù)潢P(guān)系，基于語義、幾何和拓?fù)涠喾N相似度量指標(biāo)的路網(wǎng)匹配算法。通過實驗表明，該算法能在不同尺度的路網(wǎng)數(shù)據(jù)中準(zhǔn)確識別出互相匹配的路段,具備可操作性和實用性。

路網(wǎng)匹配；拓?fù)潢P(guān)系；相似度量指標(biāo)

0 引言

隨著計算機技術(shù)的不斷發(fā)展，地理信息系統(tǒng)(Geographic Information System, GIS)的運用已經(jīng)涵蓋各行各業(yè)。在道路交通領(lǐng)域，已經(jīng)將GIS用于車輛導(dǎo)航、路政設(shè)施管理、交通規(guī)劃、路面管理等各個方面。目前，我國路網(wǎng)建設(shè)發(fā)展迅猛，道路空間位置和屬性變化周期大大縮短。及時準(zhǔn)確地掌握道路空間數(shù)據(jù)，維護(hù)數(shù)據(jù)的現(xiàn)勢性，關(guān)系到基于路網(wǎng)空間信息各種服務(wù)的準(zhǔn)確性和有效性。由于空間數(shù)據(jù)采集周期長，花費代價大，特別是路網(wǎng)數(shù)據(jù)其變化周期短，因此很難及時有效地進(jìn)行更新。在目前的GIS應(yīng)用中，已經(jīng)采用匹配技術(shù)將不同來源和不同尺度的數(shù)據(jù)源進(jìn)行融合和集成，用以提高數(shù)據(jù)的質(zhì)量，解決數(shù)據(jù)不一致等問題[1]。在路網(wǎng)匹配研究中，研究人員已經(jīng)提出了許多路網(wǎng)匹配算法[2-7]，但主要是針對特定的數(shù)據(jù)源，而且算法主要依靠路段自身的相似性進(jìn)行度量，并沒有顧及路網(wǎng)整體結(jié)構(gòu)的影響和制約。因此，本文根據(jù)數(shù)據(jù)源的特點，提出一種顧及路段和結(jié)點的拓?fù)潢P(guān)聯(lián)關(guān)系并基于語義、幾何和拓?fù)涠喾N相似度量指標(biāo)的路網(wǎng)匹配算法，并利用ArcGIS平臺和Python腳本語言來開發(fā)了相應(yīng)的路網(wǎng)匹配腳本工具。

1 路網(wǎng)匹配相似度量指標(biāo)確立

路網(wǎng)匹配主要是根據(jù)不同數(shù)據(jù)源中對同名道路實體的識別和數(shù)據(jù)交換，主要識別路網(wǎng)中的同名路段和同名結(jié)點。根據(jù)路網(wǎng)空間的數(shù)據(jù)特點對同名實體之間的相似性進(jìn)行判斷，以此來判斷是否相互匹配。本文根據(jù)數(shù)據(jù)源的特點，建立如下幾種相似度量指標(biāo)。

1.1 語義

空間數(shù)據(jù)具備豐富的屬性信息，即語義信息。如描述道路的名稱、寬度、長度等屬性。由于數(shù)據(jù)的多來源和多尺度特點，往往存在屬性缺失?；蛴捎诟髯灶I(lǐng)域和專業(yè)的使用習(xí)慣、命名方式和專業(yè)術(shù)語的不同，導(dǎo)致屬性項的不同。因此語義相似度的計算對數(shù)據(jù)模型和屬性數(shù)據(jù)模型的依賴很大[1]，往往不同的數(shù)據(jù)需要采用不同的計算方式。但是在局部區(qū)域中，不同來源的路網(wǎng)空間數(shù)據(jù)，如果存在對道路實體唯一和非歧義的描述(例如道路名稱)，即可認(rèn)為是同名路段。使用道路名稱進(jìn)行相似度量的前提是數(shù)據(jù)源對道路名稱描述的字段必須非空。

1.2 幾何

在GIS數(shù)據(jù)庫中，路網(wǎng)數(shù)據(jù)一般以ployline和point的形式進(jìn)行存儲。路段由ployline構(gòu)成，point是路段的端點和路段之間的交點。ployline由一系列的點按順序構(gòu)成，因此道路實體的相似可以采用距離和方向等幾何特征來度量。在道路空間數(shù)據(jù)中，距離主要用來描述實體之間的位置關(guān)系。這里使用歐式距離來進(jìn)行表示，其計算公式為：

(1)

其中D表示點(xs,ys)和點(xt,yt)之間的距離。其主要用于點和點之間、點和線之間匹配的距離度量。由于道路實體由ployline的形式進(jìn)行存儲，一條ployline一般由若干個具有坐標(biāo)的隱藏折點組成的多條線段構(gòu)成，如圖1所示。

圖1 ployline的組成形式

兩條路段的空間距離可以通過計算一條路段上的折點P1、P2,…,Pn到另一道路段的最短歐式距離di(i=1,2,…,n)，如圖2所示。然后統(tǒng)計最短距離小于距離閾值d的個數(shù)，記為m。m/n的值越接近1，則兩條路段互為同名路段的可能性越大。

圖2 隱藏折點到路段的距離

方向主要用來判斷道路實體的“走向”，是相似性度量的一個重要參數(shù)。方向主要用路段首尾結(jié)點形成的角度來表示，如圖3所示。

圖3 道路弧段的方向

弧段的首尾結(jié)點坐標(biāo)分別為P0(x0,y0)和Pn(xn,yn)，路段的方向角度可以用計算公式表示為：

(2)

1.3 拓?fù)?/p>

拓?fù)湎嗨剖侵覆煌瑪?shù)據(jù)源路段與結(jié)點構(gòu)成的拓?fù)潢P(guān)系相同的程度。其主要由連接結(jié)點的路段數(shù)量(即結(jié)點的度)以及與結(jié)點關(guān)聯(lián)路段的方向來進(jìn)行比較和判斷[8]。道路結(jié)點的度類型如表1所示。

表1 道路結(jié)點的度類型

當(dāng)數(shù)據(jù)尺度差異較大時，依靠結(jié)點度無法進(jìn)行拓?fù)湎嗨贫鹊呐袛唷Ｈ鐖D4所示，結(jié)點A1和B1在空間距離上非常相近，而且具有相同的度，但其不是相互匹配的結(jié)點。因此，采用與結(jié)點關(guān)聯(lián)路段的方向來對結(jié)點的類型進(jìn)行進(jìn)一步的判別。以結(jié)點作為原點，建立平面直角坐標(biāo)系，計算路段的方向，根據(jù)其與X軸正方向形成的角度，進(jìn)一步確定結(jié)點是否匹配。

圖4 依據(jù)結(jié)點的度進(jìn)行判斷產(chǎn)生的錯誤匹配

1.4 路段匹配判定標(biāo)準(zhǔn)

由于道路網(wǎng)是一個整體的空間結(jié)構(gòu)，如果單獨采用上述特性進(jìn)行相似判斷，必然會產(chǎn)生較大的錯誤。因此，本文根據(jù)道路網(wǎng)路段和結(jié)點的拓?fù)潢P(guān)系，建立參考路網(wǎng)數(shù)據(jù)R和目標(biāo)路網(wǎng)數(shù)據(jù)T路段之間多個度量指標(biāo)約束的匹配判定標(biāo)準(zhǔn)。如下式所示：

(3)

2 匹配算法過程

一般來說，在路網(wǎng)拓?fù)渲?，兩條對應(yīng)的匹配路段，其對應(yīng)的結(jié)點是匹配的。而兩條路段的結(jié)點匹配，不一定能保證路段之間匹配，但是可以作為路段匹配的約束。根據(jù)上述原則建立的匹配標(biāo)準(zhǔn)，本文從語義、拓?fù)浜蛶缀稳齻€層次進(jìn)行路網(wǎng)匹配，通過結(jié)點和路段之間的依賴關(guān)系，來確定匹配路段和結(jié)點。如圖5所示。

圖5 匹配中路段和結(jié)點的依賴關(guān)系

匹配算法的基本思路如下：

(4)不斷重復(fù)步驟(2)和(3)，直至參考數(shù)據(jù)中路段和結(jié)點全部遍歷。

完成上述步驟后，能將大部分的同名道路實體識別出來，主要是進(jìn)行路段1：1的匹配。但由于路網(wǎng)數(shù)據(jù)的采集來自不同的部門，因此對道路實體的空間描述和表達(dá)存在較大的差異，使得同名道路實體具備多種匹配關(guān)系，如圖6所示，實線表示小比例尺的參考數(shù)據(jù)R，虛線表示大比例尺目標(biāo)數(shù)據(jù)T。

圖6 同名道路實體存在的匹配對應(yīng)關(guān)系

在未匹配的路段中，可能存在n:1、1:n和m:n三種匹配關(guān)系。通過對參考數(shù)據(jù)集中路段建立一定距離閾值的緩沖區(qū)[5]，根據(jù)緩沖區(qū)與目標(biāo)數(shù)據(jù)集中路段的位置關(guān)系確定候選匹配路段，最后根據(jù)相似度量指標(biāo)確定候選匹配路段是否與參考路段匹配。其原理如下：

(1)對于1:n匹配類型，以參考數(shù)據(jù)中的路段r1，建立半徑為ΔD的緩沖區(qū)，如圖7(a)所示。對落在緩沖區(qū)中的一系列目標(biāo)弧段{t1,t2,…,tn}，根據(jù)拓?fù)潢P(guān)聯(lián)關(guān)系進(jìn)行連接，將連接后的弧段與參考弧段r1根據(jù)式(3)進(jìn)行相似度量，判斷其是否匹配。

(2)對于n:1和m:n的匹配類型，參考路段建立緩沖區(qū)后，可能沒有完全落在緩沖區(qū)內(nèi)的目標(biāo)路段，若緩沖區(qū)內(nèi)沒有目標(biāo)路段，說明該參考路段無匹配路段。若緩沖區(qū)內(nèi)只存在目標(biāo)路段的一部分，如圖7(b)所示，r2建立緩沖區(qū)后并沒有將t1完全包含進(jìn)去，這時選擇與r2關(guān)聯(lián)的一條路段。這里假設(shè)選取r3，將r2和r3合并成一條路段，再創(chuàng)建緩沖區(qū)，緩沖區(qū)將包含目標(biāo)路段t1和t2。然后根據(jù)式(3)判斷r2、r3和t1、t2構(gòu)成的整體路段是否匹配。若r2、r3構(gòu)成的整體路段形成的緩沖區(qū)還未完全包含參考路段，則繼續(xù)連接其關(guān)聯(lián)路段創(chuàng)建緩沖區(qū)，直到緩沖區(qū)存在完整的目標(biāo)路段。

圖7 緩沖區(qū)增長匹配

在緩沖區(qū)增長法匹配中，可能會出現(xiàn)如圖8所示的情況。t3、t4構(gòu)成的路段與t1、t2、t3構(gòu)成的路段均可作為參考路段r1的候選匹配路段。在這種情況下，選取各指標(biāo)值更加接近的一組作為匹配路段，即選擇t1、t2、t3與r1匹配。

圖8 緩沖區(qū)增長后出現(xiàn)多候選匹配路段

綜上所述，匹配策略主要流程為：先根據(jù)道路名稱進(jìn)行初始路段匹配；由初始匹配路段確定初始匹配結(jié)點；由匹配判斷標(biāo)準(zhǔn)判斷與初始結(jié)點關(guān)聯(lián)路段的是否匹配，完成路段的1∶1匹配；在未匹配的路段中，對非1∶1匹配采用緩沖區(qū)增長匹配進(jìn)行匹配判定。其具體流程如圖9所示。

3 算例分析

根據(jù)上述匹配算法，本文利用ArcGIS平臺，結(jié)合Python腳本語言開發(fā)了路網(wǎng)匹配工具。在Python中通過導(dǎo)入ArcPy站點包來訪問ArcGIS的地理處理功能，通過OGR包來讀取道路空間數(shù)據(jù)，并獲取數(shù)據(jù)的屬性信息和幾何信息。利用Python中的函數(shù)來進(jìn)行匹配指標(biāo)計算。

選取面積約為38平方公里的某地區(qū)內(nèi)的不同尺度的路段數(shù)據(jù)，對本文提出的匹配算法進(jìn)行驗證。以小比例尺的作為參考數(shù)據(jù)，大比例尺的作為目標(biāo)數(shù)據(jù)，如圖10所示。

對提取的路網(wǎng)數(shù)據(jù)進(jìn)行拓?fù)涮幚砗吞崛〗Y(jié)點，生成參考路段507條，目標(biāo)路段1 203條；參考結(jié)點324個，目標(biāo)結(jié)點805個。再對路網(wǎng)數(shù)據(jù)進(jìn)行校準(zhǔn)和疊加，如圖11所示。從圖中可以看出，盡管路網(wǎng)數(shù)據(jù)的吻合度較高，但是在局部地區(qū)仍然存在著一定的差異。

利用路網(wǎng)匹配工具箱對路網(wǎng)進(jìn)行匹配，根據(jù)數(shù)據(jù)的精度和質(zhì)量，設(shè)置比例系數(shù)為80%，距離閾值為30 m，方向角度差閾值為15度，緩沖區(qū)半徑為40 m。匹配結(jié)果如圖12所示。對匹配結(jié)果進(jìn)行統(tǒng)計，路段的匹配率為94%。對不能進(jìn)行匹配的路段進(jìn)行分析發(fā)現(xiàn)，由于數(shù)據(jù)受到采集以及繪制等各類因素影響，其質(zhì)量無法得到完全保證。在局部區(qū)域，存在著數(shù)據(jù)差異過大的情況，因此導(dǎo)致匹配失敗。但是匹配結(jié)果能與人工檢查結(jié)果保持一致，能將匹配和未匹配的數(shù)據(jù)進(jìn)行分離，方便對未匹配的路段進(jìn)行人工檢查，具備可操作性和實用性。

圖9 路網(wǎng)匹配流程圖

圖10 參與匹配的路網(wǎng)數(shù)據(jù)

圖11 路網(wǎng)疊加

圖12 路網(wǎng)匹配結(jié)果

4 結(jié)論

本文針對不同尺度下路網(wǎng)匹配的問題，提出一種顧及路段和結(jié)點的拓?fù)潢P(guān)聯(lián)關(guān)系并基于語義、幾何和拓?fù)涠喾N指標(biāo)的路網(wǎng)匹配算法。其充分利用了路網(wǎng)中結(jié)點和路段的拓?fù)潢P(guān)系，顧及了路網(wǎng)的整體性，而且不需要進(jìn)行復(fù)雜的計算及對路網(wǎng)數(shù)據(jù)進(jìn)行過多的分段處理，使得匹配工作更容易實現(xiàn)。實驗表明，該算法具有實用性和可操作性。

[1] 唐文靜.多源地理空間矢量數(shù)據(jù)融合[M].北京：清華大學(xué)出版社，2014.

[2] 胡天碩,毛政元.線實體候選匹配集的優(yōu)化方法研究[J].測繪科學(xué),2011,36(2):132-135.

[3] 田文文,朱欣焰,咼維. 一種VGI矢量數(shù)據(jù)增量變化發(fā)現(xiàn)的多層次蔓延匹配算法[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版),2014,39(8):963-966.

[4] WEISS R, WEIBEL R. Road network selection for small-scale maps using an improved centrality-based algorithm[J]. Journal of Spatial Information Science, 2014(9): 71-99.

[5] WALTER V, FRITSH D. Matching spatial data sets: a statical approach[J]. International Journal of Geographical Information Systems,1999,13(5):445-473.

[6] WILL J. Development of an automated matching algorithm to assess the quality of the OpenStreetMap road network-A case study in Goteborg, Sweden[D]. Lund(Sweden): Lund University ,2014.

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

[8] ZHANG M. Methods and implementations of road-network matching[D]. Munich(Germany): Technical University of Munich, 2009.

Research on road network matching algorithm based on multi similarity measure criteria

Wang Peng1，Zheng guixing2，Wang Yuan1

(1.Postgraduate Training Brigade，Military Transportation University，Tianjin 300161，China；2.General Courses Department，Military Transportation University，Tianjin 300161，China)

Road network data fusion is one of the important methods, which can be used to improve data quality and update data. And the key technology of road network data fusion is the road network matching. According to the characteristics of network data sources, a road network matching algorithm based on geometry, topology and semantics multi similarity measure criteria is proposed, which takes into the consideration of topological relations between the road arcs and the nodes. Experiments show that the algorithm can accurately identify the matching road arcs in different scales, and it is operable and practical.

road network matching; topological relations; similarity measure criteria

P208

A

1674-7720(2016)01-0019-04

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

2015-09-09)

王鵬(1990—)，通信作者，男，碩士，主要研究方向：交通信息工程及控制。E-mail:1741760653@qq.com