一種改進(jìn)的快速浮動車地圖匹配方法

張健欽，李明軒，段穎超，杜明義

(1. 北京建筑大學(xué)測繪與城市空間信息學(xué)院，北京 100044； 2. 現(xiàn)代城市測繪國家測繪地理 信息局重點(diǎn)實(shí)驗(yàn)室，北京 100044)

一種改進(jìn)的快速浮動車地圖匹配方法

張健欽1,2，李明軒1,2，段穎超1,2，杜明義1,2

(1. 北京建筑大學(xué)測繪與城市空間信息學(xué)院，北京 100044； 2. 現(xiàn)代城市測繪國家測繪地理 信息局重點(diǎn)實(shí)驗(yàn)室，北京 100044)

浮動車地圖匹配算法能夠?qū)崿F(xiàn)浮動車離散點(diǎn)與路段的快速準(zhǔn)確匹配,是浮動車路況信息生成技術(shù)中的核心環(huán)節(jié)。本文針對現(xiàn)有方法的不足，實(shí)現(xiàn)了建立定位點(diǎn)的有效閾值緩沖區(qū)，并依據(jù)空間關(guān)系檢索候選匹配路段，研究實(shí)現(xiàn)了一種利用行駛速度、行駛方向、投影距離、行駛距離4個參數(shù)進(jìn)行行車軌跡判別的邏輯匹配算法。試驗(yàn)表明，該方法無需對路網(wǎng)數(shù)據(jù)進(jìn)行大量的前期處理工作,簡化了候選匹配路段的檢索過程，在保證匹配正確率的同時也表現(xiàn)出了更高的效率。

路網(wǎng)匹配；浮動車數(shù)據(jù)；路況信息；路段

路況信息是反映城市道路交通通行狀況的綜合信息，其主要表現(xiàn)為城市交通道路的擁堵或暢通情況。隨著高新信息技術(shù)在交通中的廣泛應(yīng)用，交通信息采集、處理和發(fā)布技術(shù)日趨成熟和多樣化，而浮動車系統(tǒng)是近些年發(fā)展起來的交通路況信息采集技術(shù)。一般使用具備一定樣本量的出租車或公交車作為浮動車，通過已安裝的GPS車載裝置和無線通信設(shè)備，將車輛信息(如時間、速度、坐標(biāo)、方向等參數(shù))實(shí)時地傳送到浮動車信息中心，經(jīng)過與路網(wǎng)數(shù)據(jù)匹配處理后形成實(shí)時動態(tài)路況信息，為交通管理部門提供調(diào)度依據(jù),為公眾提供出行參考,還可作為道路建設(shè)規(guī)劃、擁堵緩解等各項(xiàng)工作中定量數(shù)據(jù)分析的基礎(chǔ)[1]。

浮動車數(shù)據(jù)反映在地圖上是一個個具有空間坐標(biāo)的離散點(diǎn)要素，但受到定位系統(tǒng)、數(shù)據(jù)傳輸、地圖矢量化，以及不同空間坐標(biāo)參考系的選取和轉(zhuǎn)換過程中多種因素的共同作用，使其絕大多數(shù)游離于路網(wǎng)線要素之外，無法與道路直接匹配形成路況信息。因此，將浮動車定位點(diǎn)真實(shí)地歸屬到城市路網(wǎng)中的某路段，并確定其在路網(wǎng)線上匹配點(diǎn)的處理過程，是路網(wǎng)匹配算法及路況信息生成的核心。傳統(tǒng)的導(dǎo)航地圖匹配算法不適用于浮動車數(shù)據(jù)，原因包括:①浮動車數(shù)據(jù)量較大，且對系統(tǒng)的實(shí)時處理計(jì)算速度要求較高；②數(shù)據(jù)采樣間隔較大，導(dǎo)致定位點(diǎn)之間的空間相關(guān)性較差；③城市路網(wǎng)密集且結(jié)構(gòu)復(fù)雜，對數(shù)據(jù)的匹配容錯率要求較高。因此，近年來國內(nèi)外學(xué)者對此展開了大量研究，并主要引入邏輯條件和數(shù)學(xué)模型參與算法判別，成果顯著，對于大規(guī)模浮動車數(shù)據(jù)的匹配效率也有較大提升[2-12]。但仍存在優(yōu)化和改進(jìn)空間，一方面算法匹配精確度高但前期需對路網(wǎng)數(shù)據(jù)進(jìn)行大量處理工作；另一方面許多算法將GPS定位點(diǎn)視為獨(dú)立對象進(jìn)行匹配，較少考慮路況信息更新周期內(nèi)同名定位點(diǎn)的邏輯關(guān)系，往往導(dǎo)致效率提高而準(zhǔn)確率降低。針對這兩方面的不足，本文提出并實(shí)現(xiàn)閾值緩沖區(qū)確定候選匹配路段，利用4個參數(shù)進(jìn)行行車軌跡判別的邏輯匹配算法，在考慮匹配正確率的同時也表現(xiàn)出較高的效率，而且無需對路網(wǎng)數(shù)據(jù)進(jìn)行大量前期處理工作，擁有更好的算法實(shí)用性。

1 候選匹配路段

候選匹配路段是指位于浮動車定位點(diǎn)周圍的可能與之匹配的路段集合。從全路網(wǎng)線要素中快速檢索出每個定位點(diǎn)的候選匹配路段是一個高效路網(wǎng)匹配算法的前提。文獻(xiàn)[2]的算法在總結(jié)了以往算法的基礎(chǔ)上開展了以下研究：基于網(wǎng)格的候選路段確定，基于距離、航向、可達(dá)性權(quán)重的定位點(diǎn)匹配，以及基于最短路徑的行駛軌跡選擇的算法研究，算法能夠滿足浮動車地圖匹配準(zhǔn)確性與實(shí)時性的要求。雖然基于網(wǎng)格劃分法的定位點(diǎn)周邊路段查找具有索引方法靈活、提取目標(biāo)要素快速等特點(diǎn)，但在實(shí)際應(yīng)用中也存在著一些不足。

1.1 基于網(wǎng)格法的不足

1.1.1 大量零碎路段

由于地圖格網(wǎng)的網(wǎng)格大小相同，而城市路網(wǎng)疏密程度不同，因而不易控制由格網(wǎng)斷開后的路段長度，在實(shí)現(xiàn)過程中往往會出現(xiàn)大量被截?cái)嗲议L度較小的零碎路段，給匹配處理額外增加了一定程度的性能負(fù)擔(dān)。如對北京市區(qū)全路網(wǎng)進(jìn)行200 m×200 m的網(wǎng)格劃分，路段總長小于10 m的占到了一定比例，其中部分路段信息及其局部放大圖如圖1所示。

圖1 過多的零碎路段

1.1.2 格網(wǎng)確定過程較為復(fù)雜

基于網(wǎng)格劃分的檢索方法通常是利用GPS定位點(diǎn)距離網(wǎng)格4條邊的距離，并對比GPS定位點(diǎn)精度的閾值范圍來判斷是否獲取當(dāng)前網(wǎng)格或周邊鄰域網(wǎng)格中的路段。但由于鄰域網(wǎng)格數(shù)量隨定位點(diǎn)位置有3、5、8個，隨方向有上、下、左、右、左上、左下、右上、右下多種情況(如圖2(a)所示，黑色為定位點(diǎn)網(wǎng)格，陰影為鄰域網(wǎng)格)，因而一方面查找過程較為復(fù)雜，另一方面容易將本身不符合條件的路段也作為候選對象(如圖2(b)所示路段1、2、3、4)，需要進(jìn)一步判斷才能排除。

圖2 網(wǎng)格查找法的幾點(diǎn)問題

1.2 閾值緩沖區(qū)法

針對上述不足，本文提出閾值緩沖區(qū)法檢索候選匹配路段，利用功能性節(jié)點(diǎn)層劃分路網(wǎng)形成路段單元，在定義索引編碼的前提下，對每個浮動車定位點(diǎn)動態(tài)生成其最大閾值緩沖區(qū)，進(jìn)而利用空間面線關(guān)系來判別和獲取候選匹配路段集合。該方法能一次性確定各個點(diǎn)的候選匹配路段，即只要是該集合中的元素，都是需要進(jìn)行后續(xù)判別的候選路段對象。具體如圖3所示，P1、P2、P3、P4分別是定位點(diǎn)生成的緩沖區(qū)，其半徑設(shè)定為浮動車數(shù)據(jù)的最大有效閾值(允許半徑不同)；seg1、seg2、…、seg11分別為各功能性節(jié)點(diǎn)形成的路段單元。綜合考慮二者的空間面線關(guān)系，得到關(guān)于P1的相交路段seg2、P2的相切路段seg5、P3的相交路段seg7和seg9。其中，P1、P2、P3與路段相切或相交，對應(yīng)定位點(diǎn)與路段距離小于或等于最大有效閾值，屬于有效漂移點(diǎn)；P4與路段seg3和seg11相離，屬于漂移嚴(yán)重的無效點(diǎn)。seg2是對應(yīng)P1、seg5是對應(yīng)P2、seg7和seg9是對應(yīng)P3定位點(diǎn)的候選匹配路段。

圖3 閾值緩沖區(qū)法查找候選匹配路段

2 行車軌跡判別

對于浮動車數(shù)據(jù)，其在城市路網(wǎng)中的整體表現(xiàn)是一個時間段上的點(diǎn)集。在理想情況下不同車輛在一段時間內(nèi)擁有相同的點(diǎn)數(shù)，但實(shí)際上每輛車的一個時間序列很可能會因漂移嚴(yán)重或建筑物遮擋造成部分定位點(diǎn)丟失。因此，可以綜合考慮各車輛自身屬性及同名車輛在時間序列中的邏輯規(guī)則，進(jìn)行行車軌跡的推測和判別，并最終確定匹配路段和匹配點(diǎn)。具體判別過程主要包含以下4個參數(shù)：

2.1 行駛速度

圖4 行駛速度參數(shù)判別分析

2.2 行駛方向

行駛方向判別方法是根據(jù)GPS記錄中車輛行駛方向與路段方向的相似度進(jìn)行判別的方法。一方面浮動車數(shù)據(jù)中記錄有車輛某時刻的方位角，另一方面候選匹配路段由于已經(jīng)過了各類功能性節(jié)點(diǎn)的打斷處理，各路段單元近似為一條直線，因而該路段方向完全可以由其矢量起終點(diǎn)的連線方向表示。研究發(fā)現(xiàn)，雖然行駛方向是一個瞬時概念，在實(shí)際行車過程中會隨著當(dāng)時的駕駛情況(直行、左轉(zhuǎn)、右轉(zhuǎn)等)發(fā)生較大的偏差，其取值不總是與道路或路段方向保持一致。但是，在正常行駛狀態(tài)(即不發(fā)生逆行、倒車等突發(fā)狀況)的前提下，車輛行駛方向與所屬路段方向的夾角總能保持在一定的變化區(qū)間內(nèi)，即夾角差的絕對值不超過90°。圖5分別是在直線道路和曲線道路條件下根據(jù)行駛方向來取舍候選匹配路段的處理方法。如圖5(a)所示，已知nodei和nodej是某道路的兩個相鄰節(jié)點(diǎn)，浮動車P行駛在它們生成的路段segi,j內(nèi)，其正常行駛狀態(tài)下的眾多方向dir1、dir2、dir3始終與道路方向Dirroad保持著一定范圍內(nèi)的一致性；如圖5(b)所示，浮動車定位點(diǎn)P位于曲線道路road的路段segi,j中，匹配點(diǎn)P′的方向記為dirp′，根據(jù)幾何關(guān)系容易得出dirp′即是過匹配點(diǎn)P′并與路段segi,j相切的切線方向，而此時由于road方向不能代表某個區(qū)間的走向，因此通過連接匹配點(diǎn)所在路段始末節(jié)點(diǎn)nodei和nodej形成的有向線段，并以它的方向作為道路方向參與方向夾角判斷。

2.3 投影距離

圖5 行駛方向參數(shù)判別分析

圖6 投影距離參數(shù)判別分析

2.4 行車距離

2.5 匹配流程

基于上述方法設(shè)計(jì)完整的路徑匹配算法，其主要步驟和具體流程如圖8所示。

2.6 路況生成

路段上車輛的平均速度是表征路況的主要信息，因此在進(jìn)行浮動車數(shù)據(jù)的路網(wǎng)匹配之后，還需要按順序計(jì)算各路段上同名車輛匹配點(diǎn)的平均速度，以及整條路段上所有車輛的平均速度，從而最終完成由“車的信息”向“路況信息”的轉(zhuǎn)換過程。此外，還可以根據(jù)路段與各道路路鏈、興趣線路或區(qū)間的從屬關(guān)系，對相應(yīng)道路平均行車速度值進(jìn)行符號化和地圖渲染，生成能夠直觀表達(dá)出道路擁堵狀態(tài)的路況專題圖，以及計(jì)算區(qū)域的交通擁堵指數(shù)等。

圖7 行駛距離參數(shù)判別分析

3 實(shí)例研究

目前參與北京市浮動車系統(tǒng)的車輛約35 000輛，每輛車如果每分鐘上傳一個GPS數(shù)據(jù)，那么數(shù)據(jù)處理中心每天接收到的數(shù)據(jù)量就有5000余萬條，為了研究算法的實(shí)用性，選取北京市市區(qū)道路網(wǎng)和2008年某日1000輛出租車GPS數(shù)據(jù)(采集頻率30 s一次)作為試驗(yàn)對象，將本文算法運(yùn)行于2.53 GHz、2 GB內(nèi)存的計(jì)算機(jī)上進(jìn)行驗(yàn)證，結(jié)果見表1，分別是以5 min為路況更新周期下的連續(xù)1個、2個和5個周期的10次匹配結(jié)果均值。

表1 不同數(shù)量下匹配算法耗時結(jié)果

結(jié)果表明，算法的平均正確匹配率為97.4%，單點(diǎn)的平均匹配時間為0.882 ms。相對于現(xiàn)有實(shí)時運(yùn)轉(zhuǎn)的浮動車地圖匹配算法，正確匹配率平均在95%左右，單點(diǎn)匹配時間在幾毫秒至幾十毫秒之間。本文算法在保證較高準(zhǔn)確率的基礎(chǔ)上，極大地提高了匹配效率，能夠滿足目前北京市浮動車系統(tǒng)地圖匹配的準(zhǔn)確性要求及每分鐘35 000點(diǎn)的計(jì)算速度要求，同時對比文獻(xiàn)[2]的方法，本文的方法解決了網(wǎng)格法的不足，同時匹配正確率和匹配效率也有提高。

圖8 路網(wǎng)匹配算法流程

4 結(jié)束語

本文提出并實(shí)現(xiàn)了一種基于閾值緩沖區(qū)確定候選匹配路段，并利用行駛速度、行駛方向、投影距離和行車距離4個參數(shù)進(jìn)行行車軌跡邏輯判別的匹配算法。試驗(yàn)表明，該方法能夠高效且準(zhǔn)確地篩選和判斷出浮動車定位點(diǎn)的匹配路段，對浮動車路況信息的生成具有很好的實(shí)用價值。本文研究的路況信息匹配生成算法所考慮的因素較多，對于一些非常復(fù)雜的路段區(qū)域，隨著待定方案的增多會導(dǎo)致部分性能的降低。后續(xù)研究工作將針對這些特殊區(qū)域路段的特點(diǎn)，對算法性能的穩(wěn)定性進(jìn)行改進(jìn)和優(yōu)化。

[1] 邵春福,熊志華,姚智勝.道路網(wǎng)短時交通需求預(yù)測理論、方法及應(yīng)用[M].北京:清華大學(xué)出版社,2011.

[2] 王美玲，程林.浮動車地圖匹配算法研究[J].測繪學(xué)報(bào),2012,1(41),133-138.

[3] 劉培.基于浮動車數(shù)據(jù)的地圖匹配算法研究[D].北京:北京交通大學(xué),2007.

[4] 尹相勇,賈順平. 基于MapObjects的浮動車中心地圖匹配綜合算法開發(fā)[J]. 計(jì)算機(jī)工程與應(yīng)用, 2008, 44(36): 881-884.

[5] 諸彤宇,郭勝敏. 浮動車信息處理技術(shù)研究[J]. 中國圖象圖形學(xué)報(bào), 2009, 14(7):1230-1237.

[6] 章威, 徐建閩, 林綿峰. 基于大規(guī)模浮動車數(shù)據(jù)的地圖匹配算法[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2007, 7(2):40-45.

[7] 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.

[8] NAJJAR M E E,BONNIFAIT P.A Road-matching Method for Precise Vehicle Localization Using Belief Theory and Kalman Filtering[J]. Autonomous Robots, 2005,19(2):173-191.

[9] JABBOUR M, BONNIFAIT P, CHERFAOUI V. Map-matching Integrity Using Multihy Pothesis Road-tracking[J]. Journal of Intelligent Transportation Systems, 2008, 12(4): 189-201.

[10] 呂衛(wèi)鋒,吳東東,諸彤宇. 基于向量識別的啟發(fā)式路徑推測算法[J]. 計(jì)算機(jī)學(xué)報(bào),2009,32(7):1443-1450.

[11] 李宇光,李清泉. 利用地圖柵格化的海量浮動車數(shù)據(jù)道路匹配快速算法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2014,39(6):724-728，733.

[12] RAHMANI M,KOUTSOPOULOS H N.Path Inference from Sparse Floating Car Data for Urban Networks[J]. Transportation Research Part C:Emerging Technologies, 2013(30):41-54.

[14] CHERITON D R, BECHTOLSHEIM A V. Method for Traffic Management,Traffic Prioritization,Access Control,and Packet Forwarding in a Datagram Computer Network: U.S. Patent 6,091,725[P]. 2000-07-18.

[15] MCCLOGHRIE K,GAI S,MOHABAN S. Method and Apparatus for Identifying Network Data Traffic Flows and for Applying Quality of Service Treatments to the Flows: U.S. Patent 6,286,052[P]. 2001-09-04.

[16] DE FABRITIIS C,RAGONA R, VALENTI G. Traffic Estimation and Prediction Based on Real Time Floating Car Data[C]∥Proceedings of the 11th International IEEE Conference on Intelligent Transportation Systems. Beijing：IEEE, 2008: 197-203.

[17] LEDUC G. Road Traffic Data: Collection Methods and Applications[J]. Working Papers on Energy, Transport and Climate Change,2008(1): 55.

[18] FUSHIKI T, YAMANE K, INOUE T, et al. Method of Presuming Traffic Conditions by Using Floating Car Data and System for Presuming and Presenting Traffic Conditions by Using Floating Data: U.S. Patent 6,721,650[P]. 2004-04-13.

[19] EHMKE J F, MEISEL S, MATTFELD D C. Floating Car Data Based Analysis of Urban Travel Times for the Provision of Traffic Quality[M].New York：Springer, 2010: 129-149.

[21] YOSHIDA M. Traffic Information System: U.S. Patent 5,699,056[P]. 1997-12-16.

AnImprovedAlgorithmforFastMap-matchingofFloatingCar

ZHANG Jianqin1,2,LI Mingxuan1,2, DUAN Yingchao1,2,DU Mingyi1,2

(1. School of Surveying and Urban Spatial Information, Beijing University of Civil Engineering and Architecture,Beijing 100044,China; 2. Key Laboratory for Urban Geomatics of National Administration of Surveying, Mapping and Geoinformation，Beijing 100044, China)

Floating car map-matching algorithm enables fast and accurate matching between the discrete points of floating car and the road segments. It is the core part of floating car traffic information generation technology. For the deficiencies of the prior method, an efficient logical matching method is proposed and implemented. Firstly it establishes buffer zones with effective threshold for the anchor points, and then searches the road segments that intersect with the buffer zones. After that, it discriminates the driving track by four parameters(driving speed, driving direction, projection distance and driving distance). The experiments show that this method does not require extensive work to deal with road network data. It simplifies the process of searching candidate matching road segments and ensures matching accuracy while also shows a higher efficiency.

road network matching; floating car data; traffic information; road segments

P283

A

0494-0911(2017)01-0087-06

張健欽，李明軒，段穎超,等.一種改進(jìn)的快速浮動車地圖匹配方法[J].測繪通報(bào)，2017(1)：87-92.

10.13474/j.cnki.11-2246.2017.0019.

2016-02-27

張健欽(1977—)，男，博士，副教授，研究方向?yàn)榻煌℅IS、三維GIS及智能交通系統(tǒng)。E-mail：yc.duan@qq.com