鄭林江，劉 旭，易 兵

(1.重慶大學 計算機學院，重慶 400044； 2.重慶城市綜合交通樞紐開發(fā)投資有限公司，重慶 401121)

(*通信作者電子郵箱lx1848@126.com)

考慮時空特性的動態(tài)權重實時地圖匹配算法

鄭林江1，劉 旭1*，易 兵2

(1.重慶大學 計算機學院，重慶 400044； 2.重慶城市綜合交通樞紐開發(fā)投資有限公司，重慶 401121)

(*通信作者電子郵箱lx1848@126.com)

針對當前實時地圖匹配算法難以同時保證匹配高準確性和高實時性的問題，提出一種基于動態(tài)權重的實時地圖匹配改進算法。首先，算法考慮了相鄰全球定位系統(tǒng)(GPS)軌跡點在時間、速度和方向上的約束關系，以及道路網(wǎng)拓撲結構，并基于時空特性分析，建立了距離權重、方位權重、方向權重和連通性權重組成的權重模型；然后，根據(jù)GPS軌跡點自身屬性信息，建立了動態(tài)權重系數(shù)模型；最后，根據(jù)置信度水平選擇最佳匹配路段。用三條總長36 km的重慶城市公交車行駛軌跡進行測試，結果顯示：所提算法平均匹配正確率達到97.31%，單個軌跡點匹配平均延遲為17.9 ms。新算法匹配正確率和實時性較高，在Y形路口和平行路段的匹配效果上優(yōu)于對比算法。

地圖匹配；動態(tài)權重；全球定位系統(tǒng)軌跡；時空特性；智能交通系統(tǒng)

0 引言

目前，許多智能交通系統(tǒng)(Intelligent Transportation System， ITS)應用服務，如車輛導航、出行路線規(guī)劃、交通流量管理、交通事故預警與處置、公交到站時間預測等都需要位置信息。近年來，隨著智能終端技術發(fā)展與普及，各種車輛和移動終端已將全球定位系統(tǒng)(Global Positioning System, GPS)模塊作為標配，GPS已成為ITS應用服務提供位置信息的主流定位技術。

盡管GPS技術已很成熟，但由于城市道路密集且形狀復雜，在車輛經(jīng)過多層立交橋、隧道或高層建筑時，GPS信號會丟失或變差。此外，電子地圖中的道路也存在誤差，定位數(shù)據(jù)并不能直接正確顯示到電子地圖中的道路上。地圖匹配作為一種位置修正技術可以解決這個問題。

地圖匹配算法是以定位系統(tǒng)(GPS或GPS/DR等)產(chǎn)生的軌跡數(shù)據(jù)以及高精度路網(wǎng)數(shù)據(jù)作為輸入，以此來識別車輛正在行駛的正確路段并確定車輛在路段上的位置[1]。目前，實時地圖匹配算法可以分為簡單匹配算法、基于權重匹配算法和高級匹配算法三類[2]。簡單匹配算法僅考慮了道路網(wǎng)的幾何形狀，算法簡單但是在交叉路和平行路段匹配精度不高[3]；基于權重匹配算法除了考慮道路網(wǎng)的幾何形狀外，還綜合考慮了道路間的連接或連通關系，?；趲讉€度量指標如距離、方向等給每條候選路段打分，然后選擇得分最高路段作為匹配路段[4-6]；高級匹配算法會利用數(shù)學模型如隱馬爾可夫模型(Hidden Markov Model，HMM)[7-9]、模糊邏輯[10-11]、D-S(Dempster-Shafer)證據(jù)理論[12]、卡爾曼濾波等來給候選路段計算分數(shù)，并選擇得分最高路段作為匹配路段。盡管高級匹配算法匹配正確率一般比基于權重算法高，但是高級算法具有更高的復雜度，可能會產(chǎn)生較大的匹配延遲[2]。

目前基于權重匹配算法的準確率介于簡單匹配算法和高級匹配算法之間，但其算法復雜性低，比較適合實時地圖匹配。文獻[4]就該類算法的權重系數(shù)為經(jīng)驗常數(shù)，不能適應匹配場景變化[2]的問題進行了改進：根據(jù)每個GPS軌跡點自身的水平精度、速度、與上一個GPS軌跡點的行駛距離，建立了三個權重系數(shù)函數(shù)，權重系數(shù)將隨著GPS軌跡點動態(tài)變化，算法平均匹配正確率可達到92.19%。但是，該算法權重僅考慮了當前GPS軌跡點及候選路段的拓撲信息，沒有考慮與歷史匹配路段的時空關系，因此在GPS信號質(zhì)量差時，可能會在平行路段及道路夾角很小路段出現(xiàn)誤匹配。本文針對該類問題，考慮GPS軌跡的時空特性，提出了一種改進的基于動態(tài)權重的實時地圖匹配算法。該算法主要特點表現(xiàn)在以下幾方面：

1)增加道路連通性權重，這可以解決跳段問題[2]和平行道路匹配問題；

2)除距離權重外的其他三個權重都考慮了與歷史匹配點和匹配路段的時空關系，可以解決包括Y形道路在內(nèi)的多支路道路的匹配；

3)權重系數(shù)隨著GPS軌跡點動態(tài)變化，可以解決由于候選路段得分很相近導致的“過度擬合”型匹配錯誤。

1 地圖匹配基本概念

GPS軌跡T是由裝有GPS模塊的設備采集的，由一系列按時間先后順序記錄的GPS軌跡點組成的集合，表示為T={p1,p2,…,pn}。每個GPS軌跡點具有6個屬性，表示為向量：

pi=[lon,lat,t,v,comp,hdop]

其中:pi.lon是經(jīng)度，pi.lat是緯度，pi.t是記錄時間戳，pi.v是瞬時速度，pi.comp是瞬時方向，pi.hdop是水平精度。

本文將路網(wǎng)當作一個有向圖G，G中的頂點是路網(wǎng)的道路節(jié)點，具有經(jīng)度、緯度屬性。如圖1，路段r1是連接N1、N2兩個道路節(jié)點的有向邊，表示G中道路的中心線。路段r有5個屬性，表示為向量：

r=[dir,len,type,start,end]

其中:r.dir是路段通行方向，r.len是路段長度，r.type是路段類型(國道、高速路等)，r.start是路段點，r.end是路段終點。彎道由多條路段表示。

圖1 路段

Fig. 1 Road segment

2 一種動態(tài)權重實時匹配算法

算法的總體邏輯如圖2。

圖2 算法總體邏輯框圖Fig. 2 Overview of algorithm framework

2.1 選取候選路段

地圖匹配算法實質(zhì)是從整個路網(wǎng)(解空間)尋找最優(yōu)路徑的一種搜索算法。尋找候選路段過程就是對解空間剪枝，簡單快速的候選路段選取方法能大大提高算法的匹配效率。目前已有的方案有誤差橢圓法和網(wǎng)格搜索法：誤差橢圓法[10，13]數(shù)學理論復雜，而且實現(xiàn)比較復雜，對算法效率可能影響較大；網(wǎng)格搜索法[14-15]的搜索效率非常高，但是對地圖數(shù)據(jù)建立網(wǎng)格索引是一個較復雜的過程。

圖3 基于誤差圓選取候選路段Fig. 3 Candidate road segments selection based on error circle

為了簡單但又不失效率和準確性，本文采用誤差圓法。如圖3，以GPS軌跡點pi為圓心，其精度R為半徑得到誤差圓，任何被誤差圓包含的路段和與誤差圓所在區(qū)域相交或相切的路段都將被選作pi的候選路段：

這解決了基于道路節(jié)點的誤差圓法可能找不到候選路段的問題。

2.2 計算各候選路段的總得分

本文基于四個指標，即距離權重、方位權重、方向權重和連通性權重，對每條候選路段打分。具體細節(jié)將在稍后各小節(jié)詳述。

2.2.1 距離權重

圖4 GPS軌跡點到候選路段距離Fig. 4 Perpendicular projection distance to candidate road segment of GPS points

(1)

將其值歸一化到[0，1],得到距離權重計算公式：

(2)

(3)

利用5 700個GPS軌跡點計算出σg=17.15。

2.2.2 方位權重

(4)

(5)

圖5 計算方位權重的兩種情況Fig. 5 Two cases of heading weight calculation

當車輛轉彎時，GPS軌跡點瞬時方向隨著道路方向變化而變化，因此當pi有歷史匹配信息時，如圖5(b)，結合歷史軌跡點和歷史匹配路段的方向信息描述該變化趨勢，用式(6)計算方位權重，降低方位權重對方向誤差的敏感度：

(6)

2.2.3 方向權重

圖6 方向權重Fig. 6 Direction weight

(7)

(8)

2.2.4 連通性權重

全局匹配算法的正確率一般比實時匹配算法高，原因是全局算法考慮了歷史GPS軌跡點及路匹配段的信息。而實時匹配算法很多都只考慮了當前GPS軌跡點及其候選路段的信息，沒有考慮歷史因素。本文提出連通性權重來描述當前GPS軌跡點與歷史GPS軌跡點及匹配路段的時空關系。

圖7 連通性權重Fig. 7 Connectivity weight

(9)

2)GPS軌跡點采樣間隔大于5 s。這時用第一種方式計算平均速度就不合適了，此時ltravel近似等于相鄰GPS軌跡點間的歐拉距離，即ltravel=lpi-1→pi。

3)當車輛在經(jīng)過隧道或立交橋時， GPS信號丟失導致采樣時間間隔變大，可能長達數(shù)分鐘。這期間車輛的速度變化可能會很大，這時ltravel=lpi-1→pi。

圖8 連通性權重對平行道路匹配的影響Fig. 8 Influence of connectivity weight on parallel road’s matching

2.3 權重系數(shù)的確定

[4]，本文選擇以下函數(shù)來計算各個權重的權重系數(shù)，對于不同的GPS軌跡點進行匹配時將采用不同權重系數(shù)。

Wdisti=

(10)

Wheadi=

(11)

(12)

(13)

2.4 獲取最佳匹配路段

以往實時匹配算法一般分三個階段[2]：初始位置匹配、跟蹤匹配、路口路段匹配。路口路段匹配階段需要進行路口檢測，這無疑增加了算法的復雜性。本文算法將跟蹤匹配和路口路段匹配合并為一個階段，不再進行路口檢測以算法簡化模型，即分為兩個階段：初始位置匹配、后續(xù)位置匹配。

(14)

(15)

2.4.1 初始位置匹配

(16)

2.4.2 后續(xù)位置匹配

(17)

其中Ki為匹配置信度水平，該值越大匹配正確的信心越高。如果pi僅有一條候選路段，則直接將點匹配到該路段。參考文獻[4]，本文用式(18)計算置信度Ki,匹配不同GPS軌跡點采用不同的置信度。

在計算出pi的匹配路段ri后，將pi垂直投影到ri,投影點就是車輛當前的位置。如果投影點在ri的延長線上，則將ri更靠近pi的端點作為車輛當前的位置。

(18)

3 算法評估與結果

3.1 實驗環(huán)境準備

地圖數(shù)據(jù)為開源地圖OpenStreetMap；GPS軌跡為三條重慶市區(qū)公交車軌跡，包含道路類型有立交橋、隧道等特殊路段，軌跡點采集時間間隔為1～3 s；地理信息系統(tǒng)(Geographic Information System， GIS)引擎為github開源項目GraphHopper, 用于計算候選路段方向、最短路徑等。實驗平臺基于Java實現(xiàn)，平臺硬件配置為：內(nèi)存4 GB，CPU型號為Intel Core i3- 2310M 2.1 GHz。

由于OpenStreetMap地圖數(shù)據(jù)并不完備，一些非主干道數(shù)據(jù)存在缺失，導致GPS軌跡中部分軌跡點無法找到正確的匹配路段，因此將這部分GPS軌跡點提前去除。表1中列舉了實驗軌跡的一些特征信息。 根據(jù)三條軌跡中所有GPS軌跡點的pi.v和pi.hdop確定距離權重系數(shù)函數(shù)和方位權重系數(shù)函數(shù)中的常數(shù)，利用MAD公式計算得到：V1=2.35 m/s,V2=3.35 m/s,HDOP1=4,HDOP2=7。

3.2 實驗結果

表2是本文提出算法的性能評估結果?？梢钥吹狡骄?5.6%的GPS軌跡點被匹配到了道路上，表明計算出的平均延遲比較可靠，不會因為太多軌跡點未被匹配到道路而導致算法長時間不更新車輛位置。

如圖9(a)，從軌跡點的候選路段可以看出車輛經(jīng)過了一個Y形路口，盡管GPS軌跡點距離誤差很大，但算法仍匹配正確，而以往實時匹配算法在Y形路口很容易發(fā)生誤匹配[1]。如圖9(b)，從立交橋處軌跡點的候選路段平行且方向一樣可以看出這是平行路段，最終算法將軌跡點匹配到了正確路段。如圖9(c)，車輛經(jīng)過U形路口(圓圈處)時，由于連續(xù)多個GPS軌跡點速度為0，導致匹配錯誤軌跡點的方向權重和方位權重都為0。而且在U形路口，兩條候選路段與歷史匹配路段都能連通，導致連通權重也失效。最終起作用的只有距離權重，但是GPS軌跡點距離誤差很大，因而導致了匹配錯誤。

表3將本文算法與其他幾種實時地圖匹配算法進行了對比。本文算法匹配正確率比以往基于權重匹配算法都高，甚至超過了高級匹配算法[7]基于HMM的匹配準確率。

表1 GPS軌跡數(shù)據(jù)特征Tab. 1 Characteristics of GPS trajectories

表2 本文提出算法的性能評估結果Tab. 2 Performance evaluation results by proposed map matching algorithm

圖9 實驗匹配情況Fig. 9 Experimental results of map matching表3 本文提出算法與已有算法性能比較Tab. 3 Comparison of the proposed algorithm with other exsiting algorithms

算法路段匹配基準測試環(huán)境導航傳感器類型地圖匹配模型文獻中給出的匹配準確率/%本文算法距離、方位變化、方向變化、連通性重慶市區(qū)GPS基于權重97.31文獻[4]方法距離、方位變化、方向變化、連通性芝加哥市區(qū)GPS基于權重92.19文獻[6]方法距離、方位變化、方向變化倫敦市區(qū)GPS/DR基于權重88.60文獻[7]方法距離、連通性新加坡市區(qū)GPSHMM92.10文獻[11]方法距離、方位變化、方向變化、連通性倫敦市區(qū)GPS/DR模糊邏輯98.50

4 結語

在總結以往全局地圖匹配算法和實時匹配算法的優(yōu)缺點后，本文提出了一種改進的基于動態(tài)權重的實時地圖匹配算法?；趯Φ缆肪W(wǎng)和GPS軌跡時空信息的分析，該算法建立了由四個權重組成的權重模型：1)距離權重，即GPS軌跡點到候選路段距離；2)方位權重，即相鄰GPS軌跡點瞬時方向的變化程度與候選路段相對上一條匹配路段方向的變化程度間的相似性；3)方向權重，即相鄰GPS軌跡點間連線的方向與候選路段方向間的相似性；4)連通性權重，即連通性候選路段和上一條匹配路段間的連通性。然后利用GPS軌跡點的速度、水平精度衰減因子hdop等信息建立各權重對應的動態(tài)權重系數(shù)函數(shù)，進而得到每條候選路段的總得分。最后，算法根據(jù)每個軌跡點的匹配置信度水平得到最佳匹配路段。

本文基于總長36 km的3條真實軌跡對算法進行評估，結果表明：1)本文算法能正確匹配Y形道路、平行道路，甚至能對立交橋的彎道有比較好的匹配效果，然而在U形路口處匹配錯誤表明算法在對低速下行駛車輛的匹配仍有待提高；2)本文算法的平均匹配正確率為97.31%，優(yōu)于現(xiàn)有的基于權重匹配算法，單個軌跡點匹配平均延遲為17.9 ms，滿足ITS應用對準確性和實時性的要求。研究也說明充分利用路網(wǎng)和GPS軌跡點信息，權重匹配算法也可以達到高級算法的匹配正確率，但由于它不像高級算法那樣復雜，實時性能更高。但本文算法的性能也可能受到了實驗平臺和電子地圖精度的限制，以及低速下的匹配精度仍有進一步提升的空間，這將成為未來的研究方向。

參考文獻(References)

[1] QUDDUS M A, OCHIENG W Y, NOLAND R B. Current map-matching algorithms for transport applications: State-of-the art and future research directions [J]. Transportation Research Part C: Emerging Technologies, 2007, 15(5): 312-328.

[2] HASHEMI M, KARIMI H A. A critical review of real-time map-matching algorithms: Current issues and future directions [J]. Computers, Environment and Urban Systems, 2014, 48: 153-165.

[3] KIM J-S. Node based map matching algorithm for car navigation system [C]// Proceedings of the 29th International Symposium on Automotive Technology & Automation. Croydon, England: Automotive Automation Ltd., 1996.

[4] HASHEMI M, KARIMI H A. A weight-based map-matching algorithm for vehicle navigation in complex urban networks [J]. Journal of Intelligent Transportation Systems, 2016, 20(6): 573-590.

[5] VELAGA N R, QUDDUS M A, BRISTOW A L. Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems [J]. Transportation Research Part C: Emerging Technologies, 2009, 17(6): 672-683.

[6] QUDDUS M A, OCHIENG W Y, ZHAO L, et al. A general map matching algorithm for transport telematics applications [J]. GPS Solutions, 2003, 7(3): 157-167.

[7] GOH C Y, DAUWELS J, MITROVIC N, et al. Online map-matching based on hidden Markov model for real-time traffic sensing applications [C]// ITSC 2015: Proceedings of the 2012 15th International IEEE Conference on Intelligent Transportation Systems. Piscataway, NJ: IEEE, 2012: 776-781.

[8] LOU Y, ZHANG C, ZHENG Y, et al. Map-matching for low-sampling-rate GPS trajectories [C]// Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2009: 352-361.

[9] NEWSON P, KRUMM J. Hidden Markov map matching through noise and sparseness [C]// GIS ’09: Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems. New York: ACM, 2009: 336-343.

[10] 鄭學遠.基于模糊邏輯的綜合地圖匹配方法研究與實現(xiàn)[D].北京：北京交通大學,2014:29-53. (ZHENG X Y. The research and realization of integrated map matching method based on fuzzy logic [D]. Beijing: Beijing Jiaotong University, 2014: 29-53.)

[11] QUDDUS M A, NOLAND R B, OCHIENG W Y. A high accuracy fuzzy logic based map matching algorithm for road transport [J]. Journal of Intelligent Transportation Systems, 2006, 10(3): 103-115.

[12] 肖維麗,岳春生,奚玲.基于高程的改進D-S證據(jù)理論地圖匹配算法[J].計算機應用與軟件,2015,32(7):262-265. (XIAO W L, YUE C S, XI L. Improved D-S evidence theory map maching algorithm based on elevation information [J]. Computer Applications and Software, 2015, 32(7): 262-265.)

[13] 夏州.GPS車輛導航中的數(shù)據(jù)處理與地圖匹配研究[D]. 北京：北京交通大學, 2009: 37-40. (XIA Z. Research of GPS data processing and map matching in vehicle navigation system [D]. Beijing: Beijing Jiaotong University, 2009: 37-40.)

[14] TANG Y, ZHU A D, XIAO X. An efficient algorithm for mapping vehicle trajectories onto road networks [C]// SIGSPATIAL ’12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York: ACM, 2012: 601-604.

[15] TAYLOR G, BLEWITT G, STEUP D, et al. Road reduction filtering for GPS-GIS navigation [J]. Transactions in GIS, 2001, 5(3): 193-207.

[16] OCHIENG W Y, QUDDUS M, NOLAND R B. Map-matching in complex urban road networks [J]. Brazilian Journal of Cartography, 2003, 55(2): 1-14.

This work is partially supported by Project Funded by China Post Doctoral Science Foundation (2014T70852), the Post-Doctoral Research Funds of Chongqing (XM201305), the Fundamental Research Funds for the Central Universities (106112014CDJZR188801), Key Projects of Chongqing Application Development Plan (cstc2014yykfB30003).

ZHENGLinjiang, born in 1983, Ph. D., associate professor. His research interests include intelligent transportation system, big data.

LIUXu, born in 1991, M. S. candidate. His research interests include intelligent transportation system, big data.

YIBing, born in 1971, senior engineer. His research interests include traffic engineering.

Dynamicweightedreal-timemapmatchingalgorithmconsideringspatio-temporalproperty

ZHENG Linjang1, LIU Xu1*, YI Bing2

(1.CollegeofComputerScience,ChongqingUniversity,Chongqing400044,China；2.ChongqingIntegratedTransportHubDevelopmentInvestmentCompanyLimited,Chongqing401121,China)

Focusing on the issue that current real-time map matching algorithms are difficult to keep high efficiency and high accuracy simultaneously, an improved dynamic weighted real-time map matching algorithm was proposed. Firstly, considering the temporal, speed, heading and direction constraints of Global Positioning System (GPS) points and the topological structures of road network, a weighted model was constructed in the algorithm based on spatio-temporal analysis, which consisted of proximity weight, heading weight, direction weight and connectivity weight. Then according to the properties of GPS points, a dynamic weighted coefficient model was created. Lastly, the best matching road segment was selected according to the confidence level of current GPS point. The experiments were conducted on three city bus trajectories with length of 36 km in Chongqing. The average matching accuracy of the algorithm was 97.31% and the average matching delay of each GPS point was 17.9 ms. The experimental results show that compared with the contrast algorithms, the proposed algorithm has higher accuracy and efficiency, and has better performance in matching Y-junctions and parallel roads.

map matching; dynamic weight; Global Positioning System (GPS) trajectory; spatio-temporal property; Intelligent Transportation System (ITS)

TP391.41

A

2017- 02- 20;

2017- 03- 21。

中國博士后科學基金特別資助項目(2014T70852)；重慶市博士后科研項目特別資助項目(XM201305)；中央高?；究蒲袠I(yè)務費資助項目(106112014CDJZR188801)；重慶市應用開發(fā)計劃重點項目(cstc2014yykfB30003)。

鄭林江(1983—)，男，四川鄰水人，副教授，博士，CCF會員，主要研究方向：智能交通系統(tǒng)、大數(shù)據(jù)； 劉旭(1991—)，男，四川南充人，碩士研究生，主要研究方向：智能交通系統(tǒng)、大數(shù)據(jù)； 易兵(1971—)，男，湖南邵陽人，高級工程師，主要研究方向：交通工程。

1001- 9081(2017)08- 2381- 06

10.11772/j.issn.1001- 9081.2017.08.2381