基于多相似度量指標的路網匹配算法研究

王 鵬，鄭貴省，王 元

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

基于多相似度量指標的路網匹配算法研究

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

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

路網數據融合是路網數據更新以及提升數據質量的重要方法之一。而路網數據融合的關鍵技術在于路網匹配。結合路網數據源的特點，提出了一種顧及路段和結點拓撲關系，基于語義、幾何和拓撲多種相似度量指標的路網匹配算法。通過實驗表明，該算法能在不同尺度的路網數據中準確識別出互相匹配的路段,具備可操作性和實用性。

路網匹配；拓撲關系；相似度量指標

0 引言

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

1 路網匹配相似度量指標確立

路網匹配主要是根據不同數據源中對同名道路實體的識別和數據交換，主要識別路網中的同名路段和同名結點。根據路網空間的數據特點對同名實體之間的相似性進行判斷，以此來判斷是否相互匹配。本文根據數據源的特點，建立如下幾種相似度量指標。

1.1 語義

空間數據具備豐富的屬性信息，即語義信息。如描述道路的名稱、寬度、長度等屬性。由于數據的多來源和多尺度特點，往往存在屬性缺失。或由于各自領域和專業的使用習慣、命名方式和專業術語的不同，導致屬性項的不同。因此語義相似度的計算對數據模型和屬性數據模型的依賴很大[1]，往往不同的數據需要采用不同的計算方式。但是在局部區域中，不同來源的路網空間數據，如果存在對道路實體唯一和非歧義的描述(例如道路名稱)，即可認為是同名路段。使用道路名稱進行相似度量的前提是數據源對道路名稱描述的字段必須非空。

1.2 幾何

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

(1)

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

圖1 ployline的組成形式

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

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

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

圖3 道路弧段的方向

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

(2)

1.3 拓撲

拓撲相似是指不同數據源路段與結點構成的拓撲關系相同的程度。其主要由連接結點的路段數量(即結點的度)以及與結點關聯路段的方向來進行比較和判斷[8]。道路結點的度類型如表1所示。

表1 道路結點的度類型

當數據尺度差異較大時，依靠結點度無法進行拓撲相似度的判斷。如圖4所示，結點A1和B1在空間距離上非常相近，而且具有相同的度，但其不是相互匹配的結點。因此，采用與結點關聯路段的方向來對結點的類型進行進一步的判別。以結點作為原點，建立平面直角坐標系，計算路段的方向，根據其與X軸正方向形成的角度，進一步確定結點是否匹配。

圖4 依據結點的度進行判斷產生的錯誤匹配

1.4 路段匹配判定標準

由于道路網是一個整體的空間結構，如果單獨采用上述特性進行相似判斷，必然會產生較大的錯誤。因此，本文根據道路網路段和結點的拓撲關系，建立參考路網數據R和目標路網數據T路段之間多個度量指標約束的匹配判定標準。如下式所示：

(3)

2 匹配算法過程

一般來說，在路網拓撲中，兩條對應的匹配路段，其對應的結點是匹配的。而兩條路段的結點匹配，不一定能保證路段之間匹配，但是可以作為路段匹配的約束。根據上述原則建立的匹配標準，本文從語義、拓撲和幾何三個層次進行路網匹配，通過結點和路段之間的依賴關系，來確定匹配路段和結點。如圖5所示。

圖5 匹配中路段和結點的依賴關系

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

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

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

圖6 同名道路實體存在的匹配對應關系

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

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

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

圖7 緩沖區增長匹配

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

圖8 緩沖區增長后出現多候選匹配路段

綜上所述，匹配策略主要流程為：先根據道路名稱進行初始路段匹配；由初始匹配路段確定初始匹配結點；由匹配判斷標準判斷與初始結點關聯路段的是否匹配，完成路段的1∶1匹配；在未匹配的路段中，對非1∶1匹配采用緩沖區增長匹配進行匹配判定。其具體流程如圖9所示。

3 算例分析

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

選取面積約為38平方公里的某地區內的不同尺度的路段數據，對本文提出的匹配算法進行驗證。以小比例尺的作為參考數據，大比例尺的作為目標數據，如圖10所示。

對提取的路網數據進行拓撲處理和提取結點，生成參考路段507條，目標路段1 203條；參考結點324個，目標結點805個。再對路網數據進行校準和疊加，如圖11所示。從圖中可以看出，盡管路網數據的吻合度較高，但是在局部地區仍然存在著一定的差異。

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

圖9 路網匹配流程圖

圖10 參與匹配的路網數據

圖11 路網疊加

圖12 路網匹配結果

4 結論

本文針對不同尺度下路網匹配的問題，提出一種顧及路段和結點的拓撲關聯關系并基于語義、幾何和拓撲多種指標的路網匹配算法。其充分利用了路網中結點和路段的拓撲關系，顧及了路網的整體性，而且不需要進行復雜的計算及對路網數據進行過多的分段處理，使得匹配工作更容易實現。實驗表明，該算法具有實用性和可操作性。

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

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

[3] 田文文,朱欣焰,咼維. 一種VGI矢量數據增量變化發現的多層次蔓延匹配算法[J]. 武漢大學學報(信息科學版),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] 胡云崗,趙仁亮,李志林,等.地圖數據縮編更新中道路數據匹配方法[J].武漢大學學報(信息科學版),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

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

2015-09-09)

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