郭森　秦貴和　肖曉　任鵬飛　孫銘會

摘要：

針對導航系統中電子地圖的更新代價大、耗時長的問題，結合浮動車的歷史GPS軌跡信息匹配到當前電子地圖中時匹配時效的情形，提出了一種基于失效數據篩選的新道路判定和電子地圖更新算法。首先，通過計算全部失效點的橫縱跨度判斷行駛軌跡的主方向。其次，通過飄逸篩選，剔除可能由于車載GPS采集設備因故障而產生的定位失準數據點組；利用基于直線的最小二乘法，對匹配失效的異常軌跡進行線性擬合，以確定軌跡的位置和方向；通過角度篩選，剔除誤差較大的定位數據點組。最后，將篩選所得新道路的軌跡數據進行融合并排序，結合電子地圖的路網結構，根據新道路的路段端點的匹配結果，將新道路插入到當前GIS電子地圖的路網中。通過在某城市局部區(qū)域的電子地圖路網數據上進行實驗，結果表明該方法能夠準確地判定和篩選新增道路，并將其正確地插入到電子地圖的當前路網結構中。

關鍵詞：

新道路發(fā)現；飄逸篩選；軌跡擬合；角度篩選；地圖更新

中圖分類號：

TP301.6

文獻標志碼：A

Abstract：

Aiming at the problem of high cost and long time consumption of updating the electronic map in navigation system， a new road judgment and electron map updating algorithm based on failure data screening was proposed， which utilized the circumstances of unsuccessful matching between the history GPS track of floating vehicle and the current electronic map. First of all， the main direction of the travel path was judged by calculating the horizontal and vertical spans of all the failure points. Secondly， elegant point screening was used to cull the misregistration groups of data points due to the malfunction of the onboard GPS equipment； then the linear least square method was used for the linear fitting of failurematching abnormal trajectory to determine the position and direction of the track； contributing to determination of the trajectory location and direction； through the angle screening， eliminating the large error positioning data point groups with large error were culled by angle screening. Finally， the screened trajectory data was fused and ordered by the main direction. Combined with the road network structure of electronic map， the new road was inserted into the current road network according to the matching results of the endpoints of the new road. Experiments were conducted on the electronic map of a local area network of some city. Experimental results show that the method can accurately determine and screen the new road， and rightly insert the new road into the current network structure of the electronic map.

英文關鍵詞Key words：

new road finding； elegant point screening； trace fitting； angle screening； map updating

0引言

基于位置服務（Location Based Service， LBS）的導航系統的廣泛應用給人們的生活帶來了極大的便利，尤其在移動端如手機、車載上的迅速普及使得導航服務成為日常出行中不可缺少的需求。

電子地圖作為導航服務的基礎，其完整性和正確性對導航系統有著直接的影響。而隨著交通系統的發(fā)展，每年都有著成千上萬條新增道路，如何準確及時地利用新增道路對電子地圖的路網進行更新就成為了導航系統中尤為關鍵的問題。

通常情況下，電子地圖中新增道路的數據信息主要依靠政府組織發(fā)動專門的機構進行測繪所得，這所帶來的一個嚴重問題是測繪將花費大量的人力、物力且測繪周期較長，不能及時對電子地圖的路網進行更新。為了解決該問題，很多具有實用性的新方法被開發(fā)出來。文獻[1]基于遙感影像地圖，以多尺度模板匹配為依據，通過 LSBSnake模型實現半自動化的新增道路提?。坏瞧錅蚀_率受限于影像地圖中地物的識別與提取技術，且在識別過程中需要人為干預。文獻[2]中通過高分辨率圖像進行道路的提取，采用統計區(qū)域融合的方法進行圖像分割，并利用基于輪廓劃分的骨架修剪策略進行路網的提取，實現了道路提取的自動化控制；但是該方法無法處理圖片中的被遮擋或覆蓋的路段。文獻[3]根據浮動車的大量歷史數據結合空間網格的方法來進行新增道路的識別。文獻[4]中參考浮動車的軌跡數據，通過與電子地圖進行圖層的圖像配準并結合數據清洗的方法來發(fā)現新道路。

本文針對以圖像識別為主的新道路發(fā)現算法的高時空復雜度，提出了一種結合歷史軌跡匹配失效點的篩選識別算法，并利用新增道路對電子地圖的路網進行更新，具有較低的時空復雜度和更高的靈活性。

1異常軌跡方向判定

電子地圖的構建基于MapInfo格式[5-6]，拓撲路網中以路段為基本單位，單路段長度的選取以測繪為基準。單路段通常選取直線或近似直線的路段，并由道路方向、路段上離散點經緯度坐標等信息所組成。

在利用地圖匹配算法[7-9]將浮動車的GPS軌跡信息匹配到電子地圖中時，有時會出現多輛車的行駛軌跡在電子地圖的某特定區(qū)域內匹配失效的情形，即無法將行駛軌跡有效地匹配到電子地圖中的具體路段上。本文中稱一條匹配失敗的軌跡為一個異常軌跡，它所包含的定位點為一個異常點組。

在地圖匹配過程中，由匹配算法檢測出的匹配失敗的異常點組如表1所示。其中時間戳屬性標識GPS定位數據產生的時刻，以30s為采集周期。匹配結果為1表示定位點正確匹配到路網，匹配結果為0表示匹配失敗。

根據上述所確定的異常點組的主方向，對各個異常點組內的定位點分別進行主方向排序。若方向為主經向，則對定位點進行排序時，先按照經度值進行排序，若兩點的經度值相等，則再按照緯度值進行排序，反之亦然。

2有效異常軌跡的篩選

異常軌跡的產生，有兩種可能的情形：1）車輛端的GPS采集設備由于故障或“飄逸”而產生的定位失準；2）其所描述的路線是一條在實際環(huán)境中已存在的新路徑，而在電子地圖中尚未被更新。為了排除因故障或“飄逸”而產生的定位失準的情形，進而得到準確的新道路軌跡信息，必須對異常軌跡進行篩選，以剔除定位失準數據。

2.1飄逸篩選

經車載GPS采集設備而得到的車輛行駛軌跡的定位數據，可能由于采集設備未校準或故障等原因，而使軌跡信息產生大幅度飄逸，這類數據不能反映軌跡的真實信息，在進行篩選時應予以剔除。本文選取已排序的各個異常點組的中位點作為篩選依據。選取中位點是為了避免選取端點而可能引入的潛在誤差，因為軌跡的端點可能會因為與路網中其他路段的交匯，而使匹配結果更加復雜化。

對主方向排序后的N組異常點，選取各組的中位點，計算任意兩中位點間的歐氏距離Dij，并統計每個中位點與其他組中位點間距離超過閾值θ的個數Si。若Si大于組數N的一半則將該失效點組剔除。對于任意兩中位點Gi（loni， lati）和Gj（lonj， latj），有如下公式：

其中：Si

根據城市道路分級規(guī)范，城市主干道最大寬度約為50m，由于GPS定位數據在采集及傳輸過程中均有一定的誤差，定位數據會在道路兩側呈現一定的擺動，本文中設定距離閾值θ取值對應實際距離100m。經緯度坐標與兩點間的實際距離的轉換，則采用文獻[10]中的方法。

2.2軌跡擬合

由匹配算法檢測出的異常點組，所包含的是以30s為周期采集到的車輛位置的離散定位點，其只能反映車輛在某一具體時刻的位置，為了從一組定位點中得到車輛的更直觀的軌跡信息，本文采用基于離散點的最小二乘法[11]對異常點組中的離散定位點進行直線擬合。

若異常軌跡的方向為主緯向，對一個異常點組：

A[M]=[（lon1，lat1），（lon2，lat2），…，（lonM，latM）]

其由最小二乘法擬合所得的在直線方程為：lon=a*lat+b，則有：

a=1c∑Mi=1（lat-latlat-）（lon-lonlon-）（5）

b=lon-a*lat（6）

其中：lon=1M*∑Mi=1loni，lat=1M*∑Mi=1lati，c=∑Mi=1（lati-lat）2。

通過上述擬合方式得到的直線為通過異常點組所能得到的車輛軌跡線性化的最優(yōu)解，由此得到的軌跡的位置及方向信息是角度篩選的關鍵。

2.3角度篩選

對于異常點組，通過飄逸篩選可以剔除由于設備故障或未校準而產生的明顯錯誤數據，但是，仍會有部分異常點組相對于全部異常點組所反映的新道路的真實軌跡具有相對較大的誤差。為了盡可能減少由這些具有較大誤差的異常點組所帶來的誤差，必須對飄逸篩選后的異常點組數據作進一步的篩選，去除較大誤差的異常點組。

為此，本文采用角度篩選的方法來提煉異常點組。首先，將由飄逸篩選后所得的所有異常點組的數據進行融合并排序，并采用2.2節(jié)中的方法對其進行軌跡擬合，此時得到的軌跡稱為綜合軌跡：lon=a0*lat+b0。其次，對每單個異常點組進行軌跡擬合，稱為單線軌跡：lon=ai*lat+bi。最后，分別計算每個單線軌跡與綜合軌跡的間的最小夾角角度α，若該角度超過閾值δ，則認為相應單線軌跡的異常點組具有較大誤差，在該角度篩選中應予以剔除。

α=π2，a0*ai=-1

arctan（ai-a01+a0*ai），a0*ai≠-1 （7）

若α<δ則保留異常點組，否則剔除異常點組，其中閾值δ設定為15°。

3路網更新

對由匹配算法檢測出的匹配失效的異常點組，通過飄逸篩選剔除失準數據，通過軌跡擬合后的角度篩選剔除較大誤差數據，此時篩選所得的異常點組即為描述新道路的軌跡信息。將篩選所得的所有異常點組數據進行融合并排序，即得新道路的路段信息，可利用該新道路對電子地圖的路網進行更新。

在對路網進行更新時，根據電子地圖路網結構的特點，首先需要判斷新道路在路網中的插入位置，即新道路路段的兩個端點在路網中路段上的匹配位置。新道路的端點匹配結果有三種可能的情形分別如圖1所示。

圖1（a）所示，新道路的端點落在路網中的節(jié)點上，此時需要在路網的拓撲結構中將該新道路加入到節(jié)點處所有連接路段的鄰接路段表中，并將節(jié)點處的所有連接路段加入到新道路的鄰接路段表中。圖1（b）所示的情形，新道路的端點落在某一路段之內，根據電子地圖的構建結構，應以該端點建立一個節(jié)點，并將該路段從端點處將該路段拆分成兩個子路段，

并同時更新自己的鄰接路段表。由失效點組可知，新道路的兩個端點至少有一端是可以匹配成功的，圖1（c）所示的情形，即新道路的某一端點未落入路網中的任一路段上及節(jié)點處，那么此時新道路的另一端點一定是匹配成功的，此時新道路是一條單通的路段，即該新道路僅有一端與路網中的其他路網相連通，另一端為一封閉的節(jié)點。此時僅需根據另一端點的匹配結果進行更新即可。

由此可得，本文實現的基于新道路發(fā)現的GIS地圖更新算法的流程如圖2所示。

4實驗結果

為了驗證本文提出的算法，在Linux操作系統下，在Qt環(huán)境中編碼實現該算法，并在Qt Graphics View框架下使用MapInfo公司的MIF格式的電子地圖進行顯示。本文選取某市某局部地區(qū)的地圖，利用該市某出租車公司的車輛軌跡的數據進行實驗。由地圖匹配算法所檢測出的匹配失效點組如表1所示。

通過Google地圖對該區(qū)域進行地圖抓取如圖3所示。

本文構建的該區(qū)域的電子地圖的路網結構如圖4（a）所示，由此圖可看出實際路網結構與電子地圖的路網結構存在明顯差異，若直接將表2中各個失效點組的軌跡直接顯示在該路網中則如圖4（b）所示。

對表2所示的各失效點組，利用本文提出的算法進行處理后所得路網結構如圖5中所示。

由圖5可以看出，本文算法能夠有效地進行軌跡信息的篩選過濾，并準確地將該路段插入到路網中。

為了進一步驗證本文算法的正確率，在浮動車的歷史軌跡覆蓋的局部路網中，手動拆除原本已經存在并且被有效匹

配過的多個路段，然后對浮動車的歷史軌跡重新進行匹配，統計匹配過后被手動拆除的路段的重建率，結果如表2。

由表2可知，本文算法能夠準確高效地判定新增路段并將其正確地插入路網中，表2中的重建率之所以未能達到100%，分析原因是因為軌跡數據不夠充分，在某些待重建路段上的軌跡未能完整覆蓋該路段，若增加浮動車的歷史軌跡數據，重建率可有效提高。

5結語

為了解決電子地圖的路網依靠人工測繪及更新的代價大、耗時長的問題，本文提出了一種基于浮動車軌跡匹配失效的新道路發(fā)現及電子地圖路網更新算法。根據車輛的歷史軌跡的匹配結果，對特定區(qū)域的匹配失效點組利用飄逸篩選排除定位失準產生的數據；采用基于直線的最小二乘法對失效點組進行軌跡擬合，通過各個失效點組間的夾角進一步剔除誤差較大的失效點組；最后根據篩選所得定位點進行融合排序，根據路網結構準確高效地將新道路插入到路網中，實現地圖的更新。在某城市局部區(qū)域的電子地圖中，根據真實浮動車歷史軌跡的實驗可得，本文算法可有效解決基于新道路發(fā)現的電子地圖更新問題，為靠人工實現的測繪和更新提供了一種新思路。

參考文獻：

[1]

董明，張海濤，祝曉坤，等.基于遙感影像的地圖道路網數據變化檢測研究[J].武漢大學學報（信息科學版），2009，34（2）：178-182.（DONG M， ZHANG H T， ZHU X K， et al. Change detection of road networks based on remote sensing image [J]. Geomatics and Information Science of Wuhan University， 2009， 34（2）： 178-182.）

[2]

ANIL P N， NATARAJAN S. Automatic road extraction from high resolution imagery based on statistical region merging and skeletonization [J]. International Journal of Engineering Science and Technology， 2010， 2（3）： 165-171.

[3]

張淑玲，官剛宇，鄒復民，等.浮動車與空間網格結合的新增道路自動檢測[J].科學技術與工程，2012，12（22）：5496-5501.（ZHANG S L， GUAN G Y， ZOU F M， et al. Combine the floating cars with space grid for automatic detection of the new road [J]. Science Technology and Engineering， 2012， 12（22）： 5496-5501.）

[4]

蔣新華，廖律超，鄒復民，等.基于浮動車移動軌跡的新增道路自動發(fā)現算法[J].計算機應用，2013，33（2）：579-582.（JIANG X H， LIAO L C， ZOU F M， et al. Automatic detection algorithm for new roads based on trajectory of floating cars [J]. Journal of Computer Applications， 2013， 33（2）： 579-582.）

[5]

何江艷，趙琦.無人直升機地面監(jiān)控電子地圖的設計與實現[J].北京航空航天大學學報，2011，37（5）：615-618.（HE J Y， ZHAO Q. Design and realization of the electronic map for UAV GCS [J]. Journal of Beijing University of Aeronautics and Astronautics， 2011， 37（5）： 615-618.）

[6]

王凌艷，謝婷婷，劉鎮(zhèn)瑜，等.基于MapInfo和Vega Prime的飛行器航跡顯示系統的設計與實現[J].中國電子科學研究院學報，2013，8（3）：300-304.（WANG L Y， XIE T T， LIU Z Y， et al. Design and implementation of aircrafts flight path display system based on MapInfo and Vega Prime [J]. Journal of China Academy of Electronics and Information Technology， 2013， 8（3）： 300-304.）

[7]

孫麗娜，董勁男，鄭嘯天，等.一種基于浮動車移動軌跡與電子地圖融合的道路匹配算法[J].吉林大學學報（理學版），2015，53（4）：710-714.（SUN L N， DONG J N， ZHENG X T， et al. A roadmatching algorithm based on fusion of moving trajectory and electronic map [J]. Journal of Jilin University （Science Edition）， 2015， 53（4）： 710-714.）

[8]

HE Z， SHE X， ZHUANG L， et al. Online mapmatching framework for floating car data with low sampling rate in urban road networks [J]. IET Intelligent Transport Systems， 2013， 7（4）： 404-414.

[9]

ZHAO Y， QIN Q， LI J， et al. Highway map matching algorithm based on floating car data [C]// Proceedings of the 2012 IEEE International Geoscience and Remote Sensing Symposium. Piscataway， NJ： IEEE， 2012： 5982-5985.

[10]

黎珍惜，黎家勛.基于經緯度快速計算兩點間距離及測量誤差[J].測繪與空間地理信息，2013，36（11）：235-237.（LI Z X， LI J X. Quickly calculate the distance between two points and measurement error based on latitude and longitude [J]. Geomatics and Spatial Information Technology， 2013， 36（11）： 235-237.）

[11]

韓慶瑤，肖強，樂英.空間離散點最小二乘法分段直線擬合的研究[J].工業(yè)儀表與自動化裝置，2012（4）：107-109.（HAN Q Y， XIAO Q， YUE Y. Study of space discrete points piecewise linear fitting on least square method [J]. Industrial Instrumentation and Automation， 2012（4）： 107-109.）