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

王 鵬，鄭貴省，王 元

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

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

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

(1.軍事交通學(xué)院 研究生管理大隊(duì)，天津 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ù)源的特點(diǎn)，提出了一種顧及路段和結(jié)點(diǎn)拓?fù)潢P(guān)系，基于語(yǔ)義、幾何和拓?fù)涠喾N相似度量指標(biāo)的路網(wǎng)匹配算法。通過(guò)實(shí)驗(yàn)表明，該算法能在不同尺度的路網(wǎng)數(shù)據(jù)中準(zhǔn)確識(shí)別出互相匹配的路段,具備可操作性和實(shí)用性。

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

0 引言

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

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

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

1.1 語(yǔ)義

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

1.2 幾何

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

(1)

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

圖1 ployline的組成形式

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

圖2 隱藏折點(diǎn)到路段的距離

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

圖3 道路弧段的方向

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

(2)

1.3 拓?fù)?/p>

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

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

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

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

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

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

(3)

2 匹配算法過(guò)程

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

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

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

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

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

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

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

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

(2)對(duì)于n:1和m:n的匹配類型，參考路段建立緩沖區(qū)后，可能沒(méi)有完全落在緩沖區(qū)內(nèi)的目標(biāo)路段，若緩沖區(qū)內(nèi)沒(méi)有目標(biāo)路段，說(shuō)明該參考路段無(wú)匹配路段。若緩沖區(qū)內(nèi)只存在目標(biāo)路段的一部分，如圖7(b)所示，r2建立緩沖區(qū)后并沒(méi)有將t1完全包含進(jìn)去，這時(shí)選擇與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ū)增長(zhǎng)匹配

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

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

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

3 算例分析

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

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

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

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

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

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

圖11 路網(wǎng)疊加

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

4 結(jié)論

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

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

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

[3] 田文文,朱欣焰,咼維. 一種VGI矢量數(shù)據(jù)增量變化發(fā)現(xiàn)的多層次蔓延匹配算法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(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é)報(bào)(信息科學(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].微型機(jī)與應(yīng)用,2016，35(1)：19-22，26

2015-09-09)

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