面向道路網(wǎng)VGI數(shù)據(jù)的匹配與融合方法

王志國(guó)，盛業(yè)華，黃 毅，黃寶群

(1.南京師范大學(xué) 虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023;2.江蘇省地理信息資源開(kāi)發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京 210023)

自發(fā)地理信息(Volunteered Geographic Information，VGI)是Goodchild教授在2007年提出的一種有別于傳統(tǒng)測(cè)繪的地理數(shù)據(jù)采集方式[1]。普通非專(zhuān)業(yè)用戶(hù)可以通過(guò)在線協(xié)作的方式自發(fā)進(jìn)行地理信息的生產(chǎn)、收集和發(fā)布，具有數(shù)據(jù)更新快、細(xì)節(jié)豐富、覆蓋范圍廣等優(yōu)勢(shì)?！叭巳硕际莻鞲衅鳌钡淖园l(fā)地理信息在簡(jiǎn)化地理信息數(shù)據(jù)采集方式、豐富數(shù)據(jù)來(lái)源的同時(shí)，大大降低采集成本，提高了數(shù)據(jù)的現(xiàn)勢(shì)性。但是非專(zhuān)業(yè)用戶(hù)采集數(shù)據(jù)時(shí)多使用非專(zhuān)業(yè)設(shè)備，存在采集方式不規(guī)范、對(duì)同一地物描述差異較大、軌跡隨機(jī)性較強(qiáng)等現(xiàn)象，導(dǎo)致VGI數(shù)據(jù)存在精度較低、可靠性不足等問(wèn)題[2]，但大量VGI數(shù)據(jù)對(duì)同一地理要素的重復(fù)采集與融合處理則可改善VGI數(shù)據(jù)的質(zhì)量。道路網(wǎng)作為地理空間數(shù)據(jù)中變化最快的要素之一，是一種重要的資源，其更新受到人們的廣泛關(guān)注。隨著智能移動(dòng)設(shè)備的普及，VGI成為了一種重要的道路網(wǎng)獲取與更新手段，如OpenStreetMap、Google Map Maker等。結(jié)合矢量要素的匹配與融合理論，可以有效提高道路網(wǎng)VGI數(shù)據(jù)的精度，其主要包括匹配與融合兩個(gè)環(huán)節(jié)。VGI數(shù)據(jù)的匹配與融合效果的好壞直接影響到后續(xù)更新的正確性。

矢量要素匹配是對(duì)不同地圖中的同名要素進(jìn)行互相識(shí)別的過(guò)程，是地圖合并或數(shù)據(jù)融合的前提與關(guān)鍵。道路網(wǎng)包括點(diǎn)要素和線要素，常用的點(diǎn)匹配算法可從距離、結(jié)構(gòu)、方位等指標(biāo)進(jìn)行分類(lèi)。歐式距離法、雙向最近距離法[3]、可信度值匹配法[4]等是常用距離指標(biāo)匹配法；8角度分區(qū)、16角度分區(qū)“蜘蛛編碼”[5]是常用的結(jié)構(gòu)指標(biāo)匹配法；星型圖描述要素間方位關(guān)系[6]是常用的方位指標(biāo)匹配法。常用的線要素匹配指標(biāo)有：Hausdorff距離、Fréchet距離等距離指標(biāo)[7]，線要素方向、形狀、拓?fù)涞戎笜?biāo)[8-9]。矢量要素融合源于地圖合并，即將同一地區(qū)兩個(gè)或兩個(gè)以上不同來(lái)源的地圖數(shù)據(jù)合并生產(chǎn)新的地圖過(guò)程。常用的道路網(wǎng)點(diǎn)要素融合算法主要包括基于三角網(wǎng)確定同名點(diǎn)間的轉(zhuǎn)換關(guān)系融合法[5]、基于同名點(diǎn)拓?fù)潢P(guān)聯(lián)的融合算法[10]、利用最小二乘原理融合算法[11]等。常用的線要素融合算法主要包括利用坐標(biāo)轉(zhuǎn)換關(guān)系實(shí)現(xiàn)線融合[12]、基于多評(píng)價(jià)因素實(shí)現(xiàn)線狀要素融合[13]、基于Delaunay三角網(wǎng)的時(shí)空軌跡融合模型[14]等。上述匹配與融合算法多應(yīng)用于地圖合并領(lǐng)域，在道路網(wǎng)VGI數(shù)據(jù)匹配中應(yīng)用較少，如何選取合適的匹配與融合算法需要進(jìn)一步研究。

本文根據(jù)道路網(wǎng)VGI數(shù)據(jù)特點(diǎn)結(jié)合矢量要素的匹配與融合理論，利用路段結(jié)點(diǎn)和路段距離相似度匹配算法與Delaunay三角剖分融合算法實(shí)現(xiàn)道路網(wǎng)VGI數(shù)據(jù)的匹配與融合，并以某大學(xué)校園道路網(wǎng)為例實(shí)現(xiàn)多人采集道路網(wǎng)VGI數(shù)據(jù)的匹配與融合。

1 道路網(wǎng)VGI數(shù)據(jù)匹配與融合算法

道路網(wǎng)VGI數(shù)據(jù)匹配與融合算法的目標(biāo)是根據(jù)多人沿道路行走的GNSS軌跡數(shù)據(jù)建立道路網(wǎng)絡(luò)。其思路是，首先對(duì)每組GNSS軌跡數(shù)據(jù)分別進(jìn)行必要的預(yù)處理，包括數(shù)據(jù)篩選、數(shù)據(jù)格式轉(zhuǎn)換等；然后再生成每組道路網(wǎng)的路段和結(jié)點(diǎn)，建立道路網(wǎng)拓?fù)潢P(guān)系；接著再利用道路網(wǎng)VGI數(shù)據(jù)匹配與融合算法，首先根據(jù)弧段結(jié)點(diǎn)相似度匹配對(duì)結(jié)點(diǎn)進(jìn)行匹配，其次根據(jù)路段距離相似度對(duì)路段進(jìn)行匹配，再次利用Delaunay三角剖分融合算法進(jìn)行同名路段融合，最后依據(jù)融合后的路段生成新的道路網(wǎng)。

1.1 VGI數(shù)據(jù)預(yù)處理及道路網(wǎng)拓?fù)潢P(guān)系生成

1)VGI數(shù)據(jù)預(yù)處理。針對(duì)多人沿道路行走的GNSS軌跡數(shù)據(jù)，分別對(duì)其進(jìn)行預(yù)處理，主要包括數(shù)據(jù)篩選和數(shù)據(jù)格式轉(zhuǎn)換，剔除低質(zhì)量軌跡數(shù)據(jù)，并將原數(shù)據(jù)轉(zhuǎn)換為shapefile文件，便于后續(xù)處理。

2)單人道路網(wǎng)拓?fù)潢P(guān)系生成。拓?fù)潢P(guān)系是空間數(shù)據(jù)結(jié)構(gòu)化的體現(xiàn)，是對(duì)空間數(shù)據(jù)自動(dòng)處理的基礎(chǔ)，因此必須對(duì)道路網(wǎng)VGI數(shù)據(jù)進(jìn)行拓?fù)涮幚韀15]。道路網(wǎng)主要由弧段與結(jié)點(diǎn)組成，其拓?fù)潢P(guān)系包括：結(jié)點(diǎn)與結(jié)點(diǎn)的關(guān)系、結(jié)點(diǎn)與弧段的關(guān)系、弧段與弧段的關(guān)系等，其中結(jié)點(diǎn)與弧段間的關(guān)系是道路網(wǎng)絡(luò)主要的拓?fù)潢P(guān)系。在進(jìn)行存儲(chǔ)時(shí)，需要記錄每一個(gè)結(jié)點(diǎn)編號(hào)以及相關(guān)聯(lián)弧段等信息。

首先將單人采集并經(jīng)預(yù)處理的GNSS軌跡數(shù)據(jù)組織在單個(gè)圖層中，并對(duì)軌跡線數(shù)據(jù)進(jìn)行結(jié)點(diǎn)、弧段的拓?fù)浠幚?，形成單人道路網(wǎng)絡(luò)數(shù)據(jù)(如圖1所示)，并按鏈狀雙重獨(dú)立編碼結(jié)構(gòu)記錄單人道路網(wǎng)絡(luò)數(shù)據(jù)。

圖1 單人道路網(wǎng)絡(luò)圖

1.2 道路網(wǎng)VGI數(shù)據(jù)匹配

為了將多人采集的道路網(wǎng)VGI數(shù)據(jù)進(jìn)行融合，其關(guān)鍵在于對(duì)經(jīng)處理的單人道路網(wǎng)絡(luò)進(jìn)行匹配。本文首先在路段首尾結(jié)點(diǎn)處建立緩沖區(qū)，對(duì)首尾結(jié)點(diǎn)對(duì)進(jìn)行結(jié)點(diǎn)匹配；然后再根據(jù)路段首尾結(jié)點(diǎn)對(duì)間的歐式距離相似度進(jìn)行路段匹配；進(jìn)而實(shí)現(xiàn)整個(gè)道路網(wǎng)VGI數(shù)據(jù)的匹配。

將第一個(gè)VGI道路網(wǎng)絡(luò)作為參考圖層，其他VGI道路網(wǎng)絡(luò)作為待匹配圖層(調(diào)整圖層)，在結(jié)點(diǎn)匹配的基礎(chǔ)上再以參考圖層中各路段為標(biāo)準(zhǔn)，將各待匹配圖層中的路段與之匹配。

1)路段結(jié)點(diǎn)匹配。路段結(jié)點(diǎn)匹配是路段首尾結(jié)點(diǎn)處建立緩沖區(qū)，緩沖區(qū)是某一指定空間物體的一定范圍內(nèi)鄰域的集合。對(duì)象Oi的緩沖區(qū)定義為

Bi={x:d(x,Oi)≤R}.

(1)

即距對(duì)象Oi的距離d小于R的全部點(diǎn)的集合，d為歐式距離。

在參考圖層的路段首尾兩結(jié)點(diǎn)處分別建立半徑為15 m的緩沖區(qū)，由于校園道路間距離相對(duì)較遠(yuǎn)且較為規(guī)整，本實(shí)驗(yàn)中半徑15 m緩沖區(qū)可以取得較好的匹配效果。若待匹配圖層中存在某一路段的首尾結(jié)點(diǎn)分別落在參考圖層路段首尾結(jié)點(diǎn)的緩沖區(qū)內(nèi)，則待匹配圖層該路段首尾結(jié)點(diǎn)對(duì)與參考圖層路段的首尾結(jié)點(diǎn)對(duì)匹配成功。

2)路段距離相似度匹配。路段距離相似度是參考路段首尾結(jié)點(diǎn)間的歐式距離和待匹配路段首尾結(jié)點(diǎn)的歐式距離的相似程度。

(2)

式中：Sdis為路段距離相似度；Dis(A,B)為參考弧段首尾結(jié)點(diǎn)間的歐式距離；Dis(A′,B′)為待匹配弧段首尾結(jié)點(diǎn)間的歐式距離；A,B,A′,B′分別為參考弧段與待匹配弧段的首尾結(jié)點(diǎn)。

計(jì)算匹配成功的路段結(jié)點(diǎn)對(duì)之間的距離相似度，若待匹配路段與參考路段的距離相似度大于0.8，則認(rèn)為這兩條路段匹配成功；若無(wú)任何待匹配路段與某一參考路段距離相似度大于0.8，則該參考路段匹配失敗。

1.3 道路網(wǎng)VGI數(shù)據(jù)融合

路段融合是在同名路段的基礎(chǔ)上進(jìn)行的，本文依據(jù)基于Delaunay三角網(wǎng)的時(shí)空軌跡融合模型[14]，通過(guò)Delaunay三角剖分融合算法來(lái)實(shí)現(xiàn)道路網(wǎng)VGI數(shù)據(jù)的融合。

道路網(wǎng)VGI數(shù)據(jù)的路段是由GNSS軌跡點(diǎn)連接而成的，如圖2所示中a，b為已匹配的同名弧段，利用路段上GNSS軌跡點(diǎn)根據(jù)Delaunay三角網(wǎng)的構(gòu)網(wǎng)原則，在參考路段和調(diào)整路段間構(gòu)建的Delaunay三角網(wǎng)，并將兩條路段相交處打斷生成新結(jié)點(diǎn)A。

圖2中三角網(wǎng)中三角形間主要有兩種鄰接模式。第一種是圖2中1、2類(lèi)三角形間互相有兩條鄰邊三角形，融合后點(diǎn)為兩條鄰接邊的權(quán)重比的分割點(diǎn)；第二種是圖2中3、4類(lèi)只有一條鄰接邊的三角形，融合后點(diǎn)為一條鄰接邊的權(quán)重比分割點(diǎn)及交點(diǎn)。路段融合后新的結(jié)點(diǎn)P，根據(jù)式(3)計(jì)算得出

(3)

式中：W表示權(quán)重，參考路段WⅠ=n；調(diào)整路段WⅡ=1；融合后路段WP=n+1，其中n表示已參與融合的路段數(shù)，即經(jīng)多次融合后該路段的權(quán)重。

最后再將兩條路段融合得到的新結(jié)點(diǎn)依次相連，即可完成同名路段的融合，如圖3所示。

圖2 建立Delaunay三角網(wǎng)

圖3 同名路段融合

1.4 道路網(wǎng)VGI數(shù)據(jù)匹配與融合算法過(guò)程

①單人采集GNSS軌跡數(shù)據(jù)篩選、數(shù)據(jù)格式轉(zhuǎn)換,并將單人采集數(shù)據(jù)組織在單個(gè)圖層；

②對(duì)圖層中軌跡數(shù)據(jù)進(jìn)行結(jié)點(diǎn)、弧段拓?fù)浠幚?，按鏈狀雙重獨(dú)立編碼記錄單人道路網(wǎng)絡(luò)數(shù)據(jù)；

③在參考圖層的參考路段的首尾結(jié)點(diǎn)處建立緩沖區(qū)，遍歷出首尾結(jié)點(diǎn)均落在緩沖區(qū)內(nèi)的全部待匹配路段；

④根據(jù)式(1)計(jì)算待匹配路段與參考路段的距離相似度，如果相似度大于0.8則標(biāo)記已匹配并記錄路段編號(hào)，否則匹配失敗并記為“-1”；

⑤重復(fù)③～④步，直至道路網(wǎng)全部路段完成匹配，并輸出道路網(wǎng)匹配結(jié)果；

⑥根據(jù)匹配結(jié)果，若匹配結(jié)果為“-1”，則該路段無(wú)同名路段，保留原路段無(wú)需融合；若匹配結(jié)果不為“-1”，則繼續(xù)進(jìn)行⑦～⑧步；

⑦以參考路段為基準(zhǔn)，稀釋調(diào)整路段點(diǎn)密度，并在同名路段間建立Delaunay三角網(wǎng)；

⑧根據(jù)權(quán)重比依次計(jì)算各分割點(diǎn)，連接各分割點(diǎn)得到融合后路段，并判斷融合后路段與參考路段方向是否一致，若不一致則反向存儲(chǔ)；

⑨重復(fù)⑦～⑧步直至全部路段融合完成并輸出道路網(wǎng)VGI數(shù)據(jù)融合結(jié)果。

2 實(shí)驗(yàn)及結(jié)果分析

基于Visual Studio 2010開(kāi)發(fā)環(huán)境，利用C+調(diào)用ArcGIS Engine 10.2對(duì)本文的算法予以實(shí)現(xiàn)，對(duì)多人沿道路行走記錄的GNSS軌跡數(shù)據(jù)進(jìn)行處理，實(shí)現(xiàn)VGI道路采集數(shù)據(jù)的匹配與融合。

2.1 道路網(wǎng)VGI數(shù)據(jù)獲取

本文以某大學(xué)校園道路網(wǎng)為例，多人次獨(dú)立利用帶GNSS單點(diǎn)定位功能的智能手機(jī)進(jìn)行校園道路網(wǎng)VGI數(shù)據(jù)的采集。所采集的GNSS軌跡數(shù)據(jù)的水平精度為10 m，垂直精度為5 m，經(jīng)過(guò)預(yù)處理，本次實(shí)驗(yàn)選取4組道路網(wǎng)VGI數(shù)據(jù)，每組包含77條路段。

四組原始觀測(cè)數(shù)據(jù)如圖4(a)所示，選取圖中圓圈內(nèi)兩組原始觀測(cè)數(shù)據(jù)進(jìn)行對(duì)比如圖4(b)所示。發(fā)現(xiàn)原始觀測(cè)數(shù)據(jù)軌跡嚴(yán)重抖動(dòng)，并且兩組數(shù)據(jù)間差異明顯，這是VGI數(shù)據(jù)的典型問(wèn)題。

2.2 道路網(wǎng)匹配與融合結(jié)果

根據(jù)本文算法對(duì)以上VGI道路網(wǎng)數(shù)據(jù)進(jìn)行匹配與融合處理，融合后的道路網(wǎng)如圖5(a)所示，融合后的道路網(wǎng)明顯更接近實(shí)際情況。對(duì)比融合前后道路網(wǎng)，選取圖4(a)中圓圈處放大后如圖5(b)所示，紅色(深色)的表示融合后的道路，其他顏色(淺色)表示采集的原始數(shù)據(jù)，從中可見(jiàn)，融合后數(shù)據(jù)精度明顯提高。如果融合后點(diǎn)位中誤差小于原始觀測(cè)數(shù)據(jù)的距離均方根差(DRMS)，則可認(rèn)為融合成功，數(shù)據(jù)精度提高。在道路網(wǎng)中隨機(jī)均勻選取50個(gè)特征點(diǎn)進(jìn)行檢查，發(fā)現(xiàn)僅有4處點(diǎn)位中誤差比距離均方根差大，樣本融合成功率為92%。

圖4 原始道路網(wǎng)VGI數(shù)據(jù)

2.3 分析與討論

1)將融合后的道路網(wǎng)與Google影像圖進(jìn)行疊加對(duì)比分析(如圖6所示)，可見(jiàn)融合后道路網(wǎng)與實(shí)際路網(wǎng)重疊度較高，沒(méi)有明顯偏移，與Google Earth影像地圖精度相近。

2)高樓附近的道路數(shù)據(jù)精度較低。融合前后均存在高樓附近道路VGI數(shù)據(jù)精度比空曠地區(qū)道路VGI數(shù)據(jù)精度低的現(xiàn)象，主要是由于高樓遮擋手機(jī)GNSS信號(hào)造成的。

3)VGI道路網(wǎng)融合后弧段的質(zhì)量與匹配成功參與融合的弧段數(shù)成正相關(guān)。在樣本中共有4處點(diǎn)位中誤差比距離均方根差大，主要是誤匹配或匹配失敗導(dǎo)致參與融合路段數(shù)較少。

圖5 道路網(wǎng)VGI數(shù)據(jù)融合結(jié)果

圖6 融合后道路網(wǎng)與Google Earth地圖疊加結(jié)果

4)選擇高效的匹配算法來(lái)提高匹配率和采集多組的道路網(wǎng)VGI數(shù)據(jù)是提高融合后數(shù)據(jù)質(zhì)量的有效方法。參與的人越多，道路網(wǎng)則越平順，其精度也會(huì)明顯提高。

3 結(jié)束語(yǔ)

本文設(shè)計(jì)了一種適用于道路網(wǎng)VGI數(shù)據(jù)的匹配融合的算法，實(shí)現(xiàn)了對(duì)多人參與的道路網(wǎng)VGI數(shù)據(jù)的有效匹配與融合處理。通過(guò)將處理后的道路網(wǎng)與原始觀測(cè)道路網(wǎng)數(shù)據(jù)的對(duì)比，以及將融合結(jié)果與Google Earth影像地圖的疊加顯示，可見(jiàn)匹配融合處理后道路網(wǎng)更加平滑，數(shù)據(jù)精度明顯提高，證明了該算法的可靠性。本方法在對(duì)結(jié)構(gòu)規(guī)整、道路間距離較遠(yuǎn)的道路網(wǎng)處理時(shí)效果較好，但對(duì)結(jié)構(gòu)復(fù)雜的道路網(wǎng)的復(fù)雜結(jié)點(diǎn)的匹配；對(duì)距離相近道路間如何避免誤匹配現(xiàn)象；對(duì)首尾結(jié)點(diǎn)相同、路徑不同的路段匹配等問(wèn)題的適應(yīng)性尚需進(jìn)一步驗(yàn)證。對(duì)道路網(wǎng)VGI數(shù)據(jù)進(jìn)行匹配與融合，可以改善VGI數(shù)據(jù)自身的缺點(diǎn)，通過(guò)與已有數(shù)據(jù)的對(duì)比可以快速發(fā)現(xiàn)變化數(shù)據(jù)并根據(jù)專(zhuān)業(yè)知識(shí)進(jìn)行相關(guān)分析，同時(shí)也可讓專(zhuān)業(yè)測(cè)繪部門(mén)在進(jìn)行地形圖測(cè)量等相關(guān)工作時(shí)有的放矢，為專(zhuān)業(yè)部門(mén)的地理信息更新提供良好的基礎(chǔ)，極大地縮短專(zhuān)業(yè)數(shù)據(jù)的更新周期，具有較高的應(yīng)用價(jià)值。

參考文獻(xiàn)：

[1] GOODCHILD M F. Citizens as Sensors: The World of Volunteered Geography[J]. GeoJournal, 2007, 69(4):211-221.

[2] 張雪晨.探討志愿者地理信息數(shù)據(jù)精度提升所面臨的問(wèn)題——針對(duì)移動(dòng)設(shè)備數(shù)據(jù)的分析[J].信息與電腦,2013(6):144-145.

[3] 田文文.基于自發(fā)地理信息的空間數(shù)據(jù)變化發(fā)現(xiàn)與更新方法研究[D].武漢：武漢大學(xué)，2013.

[4] BEERI C,KANZA Y,SAFRA E,et al.Object fusion in geographic information systems[C]. Proceedings of the Thirtieth international conference on Very large data bases-Volume 30.VLDB Endowment ,2004:816-827.

[5] SAALFELD A. Automated Map Conflation [D].Washington DC,USA: The University of Maryland,1993.

[6] CUETO K. A feature-based approach to conflation of geospatial sources[J]. International Journal of Geographical Information Science, 2004, 18(5):459-489.

[7] LYU Haiyang, SHENG Yehua, GUO Ningning, et al. Geometric Quality Assessment of Trajectory-generated VGI Road Networks Based on the Symmetric Arc Similarity[J]. Transactions in GIS, 2017. DOI: 10.1111/tgis.12256.

[8] 郭寧寧，盛業(yè)華，黃寶群，等.基于人工神經(jīng)網(wǎng)絡(luò)的多特征因子路網(wǎng)匹配算法[J].地球信息科學(xué)學(xué)報(bào), 2016, 18(9):1153-1159.

[9] 劉光孟,劉萬(wàn)增.線目標(biāo)特征點(diǎn)相似性匹配[J].測(cè)繪工程,2014,23(1):35-38.

[10] 張橋平，李德仁，龔健雅.城市地圖數(shù)據(jù)庫(kù)圖形合并技術(shù)[J].測(cè)繪通報(bào),2003(9):27-29.

[11] 童小華，鄧愫愫，史文中.數(shù)字地圖合并的平差原理與方法[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2007(7):621-625.

[12] FILIN S, DOYTSHER Y. A Linear Mapping Approach to Map Conflation: Matching of Polylines [J]. Surveying and Land Information Systems,1999,59(2), 107-114.

[13] 唐文靜，趙玉新，郝燕玲，等.數(shù)字地圖點(diǎn)狀要素合并變換算法研究[J].系統(tǒng)仿真學(xué)報(bào)，2009(5):1399-1402.

[14] 唐爐亮，劉章，楊雪，等.符合認(rèn)知規(guī)律的時(shí)空軌跡融合與路網(wǎng)生成方法[J].測(cè)繪學(xué)報(bào), 2015(11): 1271-1284.

[15] 王鵬波,武芳,翟仁健.一種用于道路網(wǎng)綜合的拓?fù)涮幚矸椒╗J].測(cè)繪科學(xué)技術(shù)學(xué)報(bào), 2009, 26(1):64-68.