面向道路網VGI數據的匹配與融合方法

王志國，盛業華，黃 毅，黃寶群

(1.南京師范大學 虛擬地理環境教育部重點實驗室，江蘇 南京 210023;2.江蘇省地理信息資源開發與利用協同創新中心，江蘇 南京 210023)

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

矢量要素匹配是對不同地圖中的同名要素進行互相識別的過程，是地圖合并或數據融合的前提與關鍵。道路網包括點要素和線要素，常用的點匹配算法可從距離、結構、方位等指標進行分類。歐式距離法、雙向最近距離法[3]、可信度值匹配法[4]等是常用距離指標匹配法；8角度分區、16角度分區“蜘蛛編碼”[5]是常用的結構指標匹配法；星型圖描述要素間方位關系[6]是常用的方位指標匹配法。常用的線要素匹配指標有：Hausdorff距離、Fréchet距離等距離指標[7]，線要素方向、形狀、拓撲等指標[8-9]。矢量要素融合源于地圖合并，即將同一地區兩個或兩個以上不同來源的地圖數據合并生產新的地圖過程。常用的道路網點要素融合算法主要包括基于三角網確定同名點間的轉換關系融合法[5]、基于同名點拓撲關聯的融合算法[10]、利用最小二乘原理融合算法[11]等。常用的線要素融合算法主要包括利用坐標轉換關系實現線融合[12]、基于多評價因素實現線狀要素融合[13]、基于Delaunay三角網的時空軌跡融合模型[14]等。上述匹配與融合算法多應用于地圖合并領域，在道路網VGI數據匹配中應用較少，如何選取合適的匹配與融合算法需要進一步研究。

本文根據道路網VGI數據特點結合矢量要素的匹配與融合理論，利用路段結點和路段距離相似度匹配算法與Delaunay三角剖分融合算法實現道路網VGI數據的匹配與融合，并以某大學校園道路網為例實現多人采集道路網VGI數據的匹配與融合。

1 道路網VGI數據匹配與融合算法

道路網VGI數據匹配與融合算法的目標是根據多人沿道路行走的GNSS軌跡數據建立道路網絡。其思路是，首先對每組GNSS軌跡數據分別進行必要的預處理，包括數據篩選、數據格式轉換等；然后再生成每組道路網的路段和結點，建立道路網拓撲關系；接著再利用道路網VGI數據匹配與融合算法，首先根據弧段結點相似度匹配對結點進行匹配，其次根據路段距離相似度對路段進行匹配，再次利用Delaunay三角剖分融合算法進行同名路段融合，最后依據融合后的路段生成新的道路網。

1.1 VGI數據預處理及道路網拓撲關系生成

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

2)單人道路網拓撲關系生成。拓撲關系是空間數據結構化的體現，是對空間數據自動處理的基礎，因此必須對道路網VGI數據進行拓撲處理[15]。道路網主要由弧段與結點組成，其拓撲關系包括：結點與結點的關系、結點與弧段的關系、弧段與弧段的關系等，其中結點與弧段間的關系是道路網絡主要的拓撲關系。在進行存儲時，需要記錄每一個結點編號以及相關聯弧段等信息。

首先將單人采集并經預處理的GNSS軌跡數據組織在單個圖層中，并對軌跡線數據進行結點、弧段的拓撲化處理，形成單人道路網絡數據(如圖1所示)，并按鏈狀雙重獨立編碼結構記錄單人道路網絡數據。

圖1 單人道路網絡圖

1.2 道路網VGI數據匹配

為了將多人采集的道路網VGI數據進行融合，其關鍵在于對經處理的單人道路網絡進行匹配。本文首先在路段首尾結點處建立緩沖區，對首尾結點對進行結點匹配；然后再根據路段首尾結點對間的歐式距離相似度進行路段匹配；進而實現整個道路網VGI數據的匹配。

將第一個VGI道路網絡作為參考圖層，其他VGI道路網絡作為待匹配圖層(調整圖層)，在結點匹配的基礎上再以參考圖層中各路段為標準，將各待匹配圖層中的路段與之匹配。

1)路段結點匹配。路段結點匹配是路段首尾結點處建立緩沖區，緩沖區是某一指定空間物體的一定范圍內鄰域的集合。對象Oi的緩沖區定義為

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

(1)

即距對象Oi的距離d小于R的全部點的集合，d為歐式距離。

在參考圖層的路段首尾兩結點處分別建立半徑為15 m的緩沖區，由于校園道路間距離相對較遠且較為規整，本實驗中半徑15 m緩沖區可以取得較好的匹配效果。若待匹配圖層中存在某一路段的首尾結點分別落在參考圖層路段首尾結點的緩沖區內，則待匹配圖層該路段首尾結點對與參考圖層路段的首尾結點對匹配成功。

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

(2)

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

計算匹配成功的路段結點對之間的距離相似度，若待匹配路段與參考路段的距離相似度大于0.8，則認為這兩條路段匹配成功；若無任何待匹配路段與某一參考路段距離相似度大于0.8，則該參考路段匹配失敗。

1.3 道路網VGI數據融合

路段融合是在同名路段的基礎上進行的，本文依據基于Delaunay三角網的時空軌跡融合模型[14]，通過Delaunay三角剖分融合算法來實現道路網VGI數據的融合。

道路網VGI數據的路段是由GNSS軌跡點連接而成的，如圖2所示中a，b為已匹配的同名弧段，利用路段上GNSS軌跡點根據Delaunay三角網的構網原則，在參考路段和調整路段間構建的Delaunay三角網，并將兩條路段相交處打斷生成新結點A。

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

(3)

式中：W表示權重，參考路段WⅠ=n；調整路段WⅡ=1；融合后路段WP=n+1，其中n表示已參與融合的路段數，即經多次融合后該路段的權重。

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

圖2 建立Delaunay三角網

圖3 同名路段融合

1.4 道路網VGI數據匹配與融合算法過程

①單人采集GNSS軌跡數據篩選、數據格式轉換,并將單人采集數據組織在單個圖層；

②對圖層中軌跡數據進行結點、弧段拓撲化處理，按鏈狀雙重獨立編碼記錄單人道路網絡數據；

③在參考圖層的參考路段的首尾結點處建立緩沖區，遍歷出首尾結點均落在緩沖區內的全部待匹配路段；

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

⑤重復③～④步，直至道路網全部路段完成匹配，并輸出道路網匹配結果；

⑥根據匹配結果，若匹配結果為“-1”，則該路段無同名路段，保留原路段無需融合；若匹配結果不為“-1”，則繼續進行⑦～⑧步；

⑦以參考路段為基準，稀釋調整路段點密度，并在同名路段間建立Delaunay三角網；

⑧根據權重比依次計算各分割點，連接各分割點得到融合后路段，并判斷融合后路段與參考路段方向是否一致，若不一致則反向存儲；

⑨重復⑦～⑧步直至全部路段融合完成并輸出道路網VGI數據融合結果。

2 實驗及結果分析

基于Visual Studio 2010開發環境，利用C+調用ArcGIS Engine 10.2對本文的算法予以實現，對多人沿道路行走記錄的GNSS軌跡數據進行處理，實現VGI道路采集數據的匹配與融合。

2.1 道路網VGI數據獲取

本文以某大學校園道路網為例，多人次獨立利用帶GNSS單點定位功能的智能手機進行校園道路網VGI數據的采集。所采集的GNSS軌跡數據的水平精度為10 m，垂直精度為5 m，經過預處理，本次實驗選取4組道路網VGI數據，每組包含77條路段。

四組原始觀測數據如圖4(a)所示，選取圖中圓圈內兩組原始觀測數據進行對比如圖4(b)所示。發現原始觀測數據軌跡嚴重抖動，并且兩組數據間差異明顯，這是VGI數據的典型問題。

2.2 道路網匹配與融合結果

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

圖4 原始道路網VGI數據

2.3 分析與討論

1)將融合后的道路網與Google影像圖進行疊加對比分析(如圖6所示)，可見融合后道路網與實際路網重疊度較高，沒有明顯偏移，與Google Earth影像地圖精度相近。

2)高樓附近的道路數據精度較低。融合前后均存在高樓附近道路VGI數據精度比空曠地區道路VGI數據精度低的現象，主要是由于高樓遮擋手機GNSS信號造成的。

3)VGI道路網融合后弧段的質量與匹配成功參與融合的弧段數成正相關。在樣本中共有4處點位中誤差比距離均方根差大，主要是誤匹配或匹配失敗導致參與融合路段數較少。

圖5 道路網VGI數據融合結果

圖6 融合后道路網與Google Earth地圖疊加結果

4)選擇高效的匹配算法來提高匹配率和采集多組的道路網VGI數據是提高融合后數據質量的有效方法。參與的人越多，道路網則越平順，其精度也會明顯提高。

3 結束語

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

參考文獻：

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

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

[3] 田文文.基于自發地理信息的空間數據變化發現與更新方法研究[D].武漢：武漢大學，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] 郭寧寧，盛業華，黃寶群，等.基于人工神經網絡的多特征因子路網匹配算法[J].地球信息科學學報, 2016, 18(9):1153-1159.

[9] 劉光孟,劉萬增.線目標特征點相似性匹配[J].測繪工程,2014,23(1):35-38.

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

[11] 童小華，鄧愫愫，史文中.數字地圖合并的平差原理與方法[J].武漢大學學報(信息科學版)，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] 唐文靜，趙玉新，郝燕玲，等.數字地圖點狀要素合并變換算法研究[J].系統仿真學報，2009(5):1399-1402.

[14] 唐爐亮，劉章，楊雪，等.符合認知規律的時空軌跡融合與路網生成方法[J].測繪學報, 2015(11): 1271-1284.

[15] 王鵬波,武芳,翟仁健.一種用于道路網綜合的拓撲處理方法[J].測繪科學技術學報, 2009, 26(1):64-68.