羅躍軍，宋向勃，鄭　莉

(1. 武漢大學(xué)資源與環(huán)境學(xué)院，湖北 武漢 430079； 2. 武漢光庭信息技術(shù)有限公司，湖北 武漢 430073；

3. 武漢大學(xué)測(cè)繪學(xué)院，湖北 武漢 430079)

Probe Vehicle Track-matching Algorithm Based on Spatial Semantic Features

LUO Yuejun，SONG Xiangbo，ZHENG Li

?

一種基于空間語(yǔ)義特征的浮動(dòng)車軌跡匹配技術(shù)

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

(1. 武漢大學(xué)資源與環(huán)境學(xué)院，湖北 武漢 430079； 2. 武漢光庭信息技術(shù)有限公司，湖北 武漢 430073；

3. 武漢大學(xué)測(cè)繪學(xué)院，湖北 武漢 430079)

Probe Vehicle Track-matching Algorithm Based on Spatial Semantic Features

LUO Yuejun，SONG Xiangbo，ZHENG Li

摘要：針對(duì)浮動(dòng)車軌跡數(shù)據(jù)挖掘中的空間語(yǔ)義分析問題，闡述了傳統(tǒng)的電子導(dǎo)航地圖匹配方法用于浮動(dòng)車軌跡地圖匹配時(shí)的主要問題，提出了基于空間語(yǔ)義特征的浮動(dòng)車軌跡匹配算法，并結(jié)合實(shí)際數(shù)據(jù)進(jìn)行了試驗(yàn)驗(yàn)證，本文提出的基于空間語(yǔ)義特征的全局路徑匹配方法取得了很好的匹配效果，并可還原浮動(dòng)車軌跡經(jīng)由的真實(shí)路徑。

關(guān)鍵詞：空間語(yǔ)義特征；浮動(dòng)車軌跡；空間數(shù)據(jù)挖掘

一、引言

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

為了利用浮動(dòng)車技術(shù)進(jìn)行空間數(shù)據(jù)挖掘，需要盡可能準(zhǔn)確地還原浮動(dòng)車軌跡經(jīng)由的真實(shí)路徑，實(shí)現(xiàn)浮動(dòng)車軌跡數(shù)據(jù)和真實(shí)道路網(wǎng)數(shù)據(jù)的空間配準(zhǔn)。由于浮動(dòng)車軌跡數(shù)據(jù)存在采樣間隔大、有位置噪聲等數(shù)據(jù)特點(diǎn)，導(dǎo)致傳統(tǒng)電子地圖匹配方法不適用于浮動(dòng)車軌跡的路徑匹配，從而導(dǎo)致針對(duì)浮動(dòng)車軌跡的空間數(shù)據(jù)挖掘難以進(jìn)行。

二、傳統(tǒng)的道路匹配算法存在的問題

傳統(tǒng)的導(dǎo)航地圖匹配方法主要以接收到的GPS位置信息，計(jì)算當(dāng)前車輛所在位置，進(jìn)而利用點(diǎn)線距離或軌跡曲線距離實(shí)現(xiàn)車輛在道路網(wǎng)上的匹配。由于GPS存在噪聲誤差，往往通過歷史軌跡和車輛運(yùn)動(dòng)信息對(duì)匹配結(jié)果進(jìn)行修正，以在一定程度消除GPS噪聲的影響[1-5]。

由于GPS采樣點(diǎn)的間隔僅為1 s，因此上述的導(dǎo)航地圖匹配算法比較容易獲得準(zhǔn)確的軌跡曲線作為匹配樣本，能夠?qū)崿F(xiàn)基于軌跡曲線的線到線的地圖匹配。然而，對(duì)于車輛浮動(dòng)車軌跡，由于采樣間隔較大，一般在幾十秒到數(shù)分鐘才上傳一個(gè)GPS點(diǎn)數(shù)據(jù)。時(shí)速40 km/h的浮動(dòng)車，每分鐘頻率的GPS點(diǎn)前后相差約600 m，而這個(gè)距離內(nèi)可能存在多種路徑。前后兩點(diǎn)間的相關(guān)性差決定了浮動(dòng)車系統(tǒng)無(wú)法采用線到線的地圖匹配方法。若仍沿用傳統(tǒng)導(dǎo)航地圖匹配方法，可能導(dǎo)致錯(cuò)誤的路徑匹配，甚至整個(gè)軌跡無(wú)法匹配出一條可通行路徑(如圖1所示)?？梢?，傳統(tǒng)的導(dǎo)航地圖匹配算法不能直接應(yīng)用于浮動(dòng)車系統(tǒng)[6]。圖1中，淺灰色為電子地圖道路網(wǎng)，深灰色為浮動(dòng)車軌跡點(diǎn)連線，黑色為軌跡匹配結(jié)果。

圖1　浮動(dòng)車軌跡及其真實(shí)路徑和道路網(wǎng)

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

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

針對(duì)浮動(dòng)車軌跡離線地圖匹配[9]，從信息融合的角度[10]，可以同時(shí)考察整個(gè)行駛軌跡上的所有采樣點(diǎn)的位置信息，這些不同的采樣點(diǎn)之間存在可通達(dá)、通達(dá)時(shí)間受限等一些行為相關(guān)性。因此，可以考慮面向浮動(dòng)車軌跡整體進(jìn)行全局的最優(yōu)軌跡匹配。

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

1) 將每個(gè)軌跡點(diǎn)看作一條對(duì)軌跡的真實(shí)路徑還原的證據(jù)信息。

2) 每個(gè)軌跡點(diǎn)在道路網(wǎng)上進(jìn)行一定范圍內(nèi)的模糊匹配。

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

4) 按照某種空間語(yǔ)義評(píng)價(jià)標(biāo)準(zhǔn)，在全局匹配路徑中尋找一條全局最優(yōu)的匹配路徑。

為了評(píng)價(jià)所選路徑的優(yōu)劣，本文提出了以{長(zhǎng)度，道路種別的變化數(shù)，轉(zhuǎn)彎數(shù)，道路數(shù)，經(jīng)過的軌跡點(diǎn)數(shù)}在描述的路徑的空間語(yǔ)義特征Φ={L,K,C,M,N}，即路徑pt的空間語(yǔ)義特征為Φt={Lt,Kt,Ct,Mt,Nt}。

四、基于空間語(yǔ)義特征的浮動(dòng)車軌跡路徑還原方法

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

1. 浮動(dòng)車軌跡點(diǎn)模糊路徑匹配

2. 軌跡點(diǎn)間路徑探索

在相鄰兩個(gè)軌跡點(diǎn)所匹配的所有l(wèi)ink間進(jìn)行路徑探索，探索出每對(duì)道路間的路徑。如在第i個(gè)軌跡點(diǎn)和第i+1個(gè)軌跡點(diǎn)之間進(jìn)行探索時(shí)，對(duì)于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算法在一定道路數(shù)閾值s0內(nèi)探索一條可通行路徑rijk(lij,lin1,…,lini,li+1,k)，其中ni≥0。如果在閾值范圍內(nèi)找不到可通行路徑，則放棄該組合。

3. 基于空間語(yǔ)義特征的全局最優(yōu)路徑選擇

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

五、試驗(yàn)驗(yàn)證

利用本文所述方法，對(duì)實(shí)車采集軌跡隨機(jī)抽樣300條進(jìn)行了路徑匹配還原試驗(yàn)。在本試驗(yàn)中，軌跡點(diǎn)模糊匹配閾值r0為50 m，Dijkstra算法路徑探索道路數(shù)目閾值s0為15條。

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

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

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

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

六、結(jié)束語(yǔ)

本文針對(duì)浮動(dòng)車軌跡數(shù)據(jù)挖掘中的空間語(yǔ)義分

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

參考文獻(xiàn)：

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

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

[3]諸彤宇，郭勝敏．浮動(dòng)車信息處理技術(shù)研究[J]．中國(guó)圖象圖形學(xué)報(bào)，2009，14(7)：1230-1237．

[4]蘇潔，周東方，岳春生．GPS車輛導(dǎo)航中的實(shí)時(shí)地圖匹配算法[J]．測(cè)繪學(xué)報(bào)，2001，30(3)：252-256．

[5]唐進(jìn)君，曹凱．一種自適應(yīng)軌跡曲線地圖匹配算法[J]．測(cè)繪學(xué)報(bào)，2008，37(3)：308-315．

[6]王美玲，程林．浮動(dòng)車地圖匹配算法研究[J]．測(cè)繪學(xué)報(bào)，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.

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

作者簡(jiǎn)介：羅躍軍(1978—)，男，博士，高級(jí)工程師，研究方向?yàn)榈貓D學(xué)與空間數(shù)據(jù)處理。E-mail： lingfengyang@aligun.com

基金項(xiàng)目：國(guó)家863計(jì)劃(2013AA12A202)；數(shù)字制圖與國(guó)土信息、應(yīng)用工程國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室開放研究基金

收稿日期：2014-01-29

中圖分類號(hào)：P208

文獻(xiàn)標(biāo)識(shí)碼：B

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