一種基于空間語義特征的浮動車軌跡匹配技術

羅躍軍，宋向勃，鄭　莉

(1. 武漢大學資源與環境學院，湖北 武漢 430079； 2. 武漢光庭信息技術有限公司，湖北 武漢 430073；

3. 武漢大學測繪學院，湖北 武漢 430079)

Probe Vehicle Track-matching Algorithm Based on Spatial Semantic Features

LUO Yuejun，SONG Xiangbo，ZHENG Li

?

一種基于空間語義特征的浮動車軌跡匹配技術

羅躍軍1，2，宋向勃2，鄭莉3

(1. 武漢大學資源與環境學院，湖北 武漢 430079； 2. 武漢光庭信息技術有限公司，湖北 武漢 430073；

3. 武漢大學測繪學院，湖北 武漢 430079)

Probe Vehicle Track-matching Algorithm Based on Spatial Semantic Features

LUO Yuejun，SONG Xiangbo，ZHENG Li

摘要：針對浮動車軌跡數據挖掘中的空間語義分析問題，闡述了傳統的電子導航地圖匹配方法用于浮動車軌跡地圖匹配時的主要問題，提出了基于空間語義特征的浮動車軌跡匹配算法，并結合實際數據進行了試驗驗證，本文提出的基于空間語義特征的全局路徑匹配方法取得了很好的匹配效果，并可還原浮動車軌跡經由的真實路徑。

關鍵詞：空間語義特征；浮動車軌跡；空間數據挖掘

一、引言

隨著城市化進程的不斷加快和經濟的飛速發展，汽車在人們的生活中迅速普及。隨著汽車市場的蓬勃發展，大量問題也隨之出現，浮動車技術作為一種新的高級導航數據采集方式，為解決上述問題提供了更多可能。浮動車也稱為GPS探測車，是近年來國際智能交通系統(ITS)中所采用的獲取城市道路交通狀態的重要途徑和有效方式[1]，也是一種先進的道路交通信息采集技術[2]。浮動車技術的數據范圍能夠遍布整個地區，能全天候24 h進行數據采集，利用無線實時傳輸、中心式處理大大提高信息采集效率；同時，利用現有的GPS和通信網絡資源，也使得采集設備維護和安裝成本較低[3]。綜上，浮動車技術是比較經濟、高效的方法。

為了利用浮動車技術進行空間數據挖掘，需要盡可能準確地還原浮動車軌跡經由的真實路徑，實現浮動車軌跡數據和真實道路網數據的空間配準。由于浮動車軌跡數據存在采樣間隔大、有位置噪聲等數據特點，導致傳統電子地圖匹配方法不適用于浮動車軌跡的路徑匹配，從而導致針對浮動車軌跡的空間數據挖掘難以進行。

二、傳統的道路匹配算法存在的問題

傳統的導航地圖匹配方法主要以接收到的GPS位置信息，計算當前車輛所在位置，進而利用點線距離或軌跡曲線距離實現車輛在道路網上的匹配。由于GPS存在噪聲誤差，往往通過歷史軌跡和車輛運動信息對匹配結果進行修正，以在一定程度消除GPS噪聲的影響[1-5]。

由于GPS采樣點的間隔僅為1 s，因此上述的導航地圖匹配算法比較容易獲得準確的軌跡曲線作為匹配樣本，能夠實現基于軌跡曲線的線到線的地圖匹配。然而，對于車輛浮動車軌跡，由于采樣間隔較大，一般在幾十秒到數分鐘才上傳一個GPS點數據。時速40 km/h的浮動車，每分鐘頻率的GPS點前后相差約600 m，而這個距離內可能存在多種路徑。前后兩點間的相關性差決定了浮動車系統無法采用線到線的地圖匹配方法。若仍沿用傳統導航地圖匹配方法，可能導致錯誤的路徑匹配，甚至整個軌跡無法匹配出一條可通行路徑(如圖1所示)。可見，傳統的導航地圖匹配算法不能直接應用于浮動車系統[6]。圖1中，淺灰色為電子地圖道路網，深灰色為浮動車軌跡點連線，黑色為軌跡匹配結果。

圖1　浮動車軌跡及其真實路徑和道路網

三、基于空間語義特征的全局匹配模型

傳統導航地圖匹配問題模型只是根據GPS接收點的位置及其附近時間段內的車輛位置和車輛行為來進行匹配，相對于整個行駛路徑而言，是一種局部路徑匹配。對于浮動車軌跡而言，由于采樣間隔過大，相鄰采樣點之間的相關性較差，因此不能通過歷史位置點對GPS噪聲進行修正。同時，每個采樣的GPS位置點都受到噪聲影響，單純利用局部位置點進行路徑匹配，很可能匹配到錯誤的道路上去，最終導致整個軌跡匹配到錯誤的路徑上。文獻[7—8]提出了軌跡點模糊匹配的方法，在一定程度上可以減輕噪聲的影響，但仍然是在局部進行最優路徑選擇。

針對浮動車軌跡離線地圖匹配[9]，從信息融合的角度[10]，可以同時考察整個行駛軌跡上的所有采樣點的位置信息，這些不同的采樣點之間存在可通達、通達時間受限等一些行為相關性。因此，可以考慮面向浮動車軌跡整體進行全局的最優軌跡匹配。

基于上述分析，本文提出用于浮動車軌跡的基于空間語義特征的全局路徑匹配方法，具體如下：

1) 將每個軌跡點看作一條對軌跡的真實路徑還原的證據信息。

2) 每個軌跡點在道路網上進行一定范圍內的模糊匹配。

3) 按照某種路徑探索方法，將所有軌跡點的模糊匹配結果依次連通，得到所有可能的全局匹配路徑。

4) 按照某種空間語義評價標準，在全局匹配路徑中尋找一條全局最優的匹配路徑。

為了評價所選路徑的優劣，本文提出了以{長度，道路種別的變化數，轉彎數，道路數，經過的軌跡點數}在描述的路徑的空間語義特征Φ={L,K,C,M,N}，即路徑pt的空間語義特征為Φt={Lt,Kt,Ct,Mt,Nt}。

四、基于空間語義特征的浮動車軌跡路徑還原方法

根據上述基于空間語義特征的全局匹配模型和選用的空間語義特征，本文提出了基于空間語義特征的浮動車軌跡路徑還原方法。

1. 浮動車軌跡點模糊路徑匹配

2. 軌跡點間路徑探索

在相鄰兩個軌跡點所匹配的所有link間進行路徑探索，探索出每對道路間的路徑。如在第i個軌跡點和第i+1個軌跡點之間進行探索時，對于lij(j=1,2,…,mi)和li+1,k(k=1,2,…,mi+1)的任一組合

(lij,li+1,k)j∈{1,2,…,mi}，k∈{1,2,…,mi+1}

利用Dijkstra算法在一定道路數閾值s0內探索一條可通行路徑rijk(lij,lin1,…,lini,li+1,k)，其中ni≥0。如果在閾值范圍內找不到可通行路徑，則放棄該組合。

3. 基于空間語義特征的全局最優路徑選擇

圖2　全局完整路徑生成流程

五、試驗驗證

利用本文所述方法，對實車采集軌跡隨機抽樣300條進行了路徑匹配還原試驗。在本試驗中，軌跡點模糊匹配閾值r0為50 m，Dijkstra算法路徑探索道路數目閾值s0為15條。

經過處理，300條軌跡都匹配出了完整的行駛路徑，經過目視檢查，軌跡的路徑還原比較理想的有269條，占總路徑的89.66%，圖3—圖5分別為一些軌跡的實際匹配結果。圖中，淺灰色為電子地圖道路網，灰色為浮動車軌跡點連線，黑色為軌跡匹配結果。

圖3　軌跡1匹配的整體圖和局部放大圖

圖4　軌跡2匹配的整體圖和局部放大圖

圖5　軌跡3匹配的整體圖和局部放大圖

六、結束語

本文針對浮動車軌跡數據挖掘中的空間語義分

析問題，闡述了傳統的電子導航地圖匹配方法用于浮動車軌跡地圖匹配時存在的主要問題，并提出了基于空間語義特征的浮動車軌跡匹配技術。通過實際數據，對本文提出的匹配方法進行了試驗驗證。結果表明，本文提出的匹配方法得到了較好的匹配效果，并還原了浮動車軌跡經由的真實路徑。由于本文提出的方法需要在整個浮動車軌跡的所有可能路徑集合中進行比較運算，以便選擇最優路徑，因此運算量偏大，對硬件資源的消耗較大，因此當浮動車軌跡中包含的軌跡點比較多的時候，在算法性能上需要進一步調優。

參考文獻：

[1]耿小峰，王山東，季軍．浮動車快速道路匹配算法[J]．水利與建筑工程學報，2013，11(1)：122-125．

[2]郝勇剛，吳廣君，周雙全．1種基于浮動車數據的多車車速融合算法[J]．交通信息與安全，2012，30(169)：56-61．

[3]諸彤宇，郭勝敏．浮動車信息處理技術研究[J]．中國圖象圖形學報，2009，14(7)：1230-1237．

[4]蘇潔，周東方，岳春生．GPS車輛導航中的實時地圖匹配算法[J]．測繪學報，2001，30(3)：252-256．

[5]唐進君，曹凱．一種自適應軌跡曲線地圖匹配算法[J]．測繪學報，2008，37(3)：308-315．

[6]王美玲，程林．浮動車地圖匹配算法研究[J]．測繪學報，2012，41(1)：133-138．

[7]KIMS，KIMJH．AdaptiveFuzzy-network-basedC-measureMap-matchingAlgorithmforCarNavigationSystem[J].IEEETransactionsonIndustrialElectronics，2001，48(2)：432-441.

[8]KIMS，KIMJH．Q-factorMapMatchingMethodUsingAdaptiveFuzzyNetwork[C]∥IEEEInternationalFuzzySystemsConferenceProceedings．Seall：IEEE，1999．

[9]PEREIRAFC，COSTAH，PEREIRANM．AnOff-lineMap-matchingAlgorithmforIncompleteMapDatabases[J].EuropeanTransportationResearchReview，2009，1(3)：107-124．

[10]BRAKATSOULASS．OnMapmatchingVehicleTrackingData[C]∥Proceedingofthe31stVLDBConference．[S.l.]:[s.n.],2005.

引文格式： 羅躍軍，宋向勃，鄭莉. 一種基于空間語義特征的浮動車軌跡匹配技術[J].測繪通報，2015(3)：108-110.DOI:10.13474/j.cnki.11-2246.2015.0090

作者簡介：羅躍軍(1978—)，男，博士，高級工程師，研究方向為地圖學與空間數據處理。E-mail： lingfengyang@aligun.com

基金項目：國家863計劃(2013AA12A202)；數字制圖與國土信息、應用工程國家測繪地理信息局重點實驗室開放研究基金

收稿日期：2014-01-29

中圖分類號：P208

文獻標識碼：B

文章編號：0494-0911(2015)03-0108-03