交叉路段的自適應(yīng)投影地圖匹配算法及應(yīng)用

付小雪，羅贊文，劉振東

(1.上海健康醫(yī)學院，上海 201318；2.上海交通運輸研究中心 大數(shù)據(jù)研究院，上海 200031)

0 引言

智慧交通有關(guān)的應(yīng)用都是基于軌跡的，其核心是對道路上車輛的GPS軌跡數(shù)據(jù)進行精確定位，即地圖匹配[1-5]。典型的GPS軌跡是一系列順序的軌跡點。每個GPS點由緯度、經(jīng)度和時間戳信息組成。但是由于GPS自身的局限性，GPS數(shù)據(jù)的采樣和計算過程以及定位數(shù)據(jù)的接收和返回過程都有可能出現(xiàn)誤差，進而導(dǎo)致不準確的GPS數(shù)據(jù)[6-11]。因此，需要對原始數(shù)據(jù)進行處理，然后在路網(wǎng)上使用，也就是地圖匹配。地圖匹配算法的輸入應(yīng)該是GPS點標記的位置信息、道路網(wǎng)的鄰接信息以及車輛的其他行駛信息。而關(guān)鍵問題是如何通過綜合各方面信息快速準確地推斷出車輛的行駛路線[12-17]。目前國內(nèi)外研究和應(yīng)用的地圖匹配算法多種多樣[18-20]。

現(xiàn)有的地圖匹配算法存在空匹配、匹配錯誤等問題[21-28]，當待匹配的數(shù)據(jù)量迅速增加時，匹配效率往往大幅降低。針對上述問題，本研究提出了一種交叉路段背景下的自適應(yīng)投影地圖匹配算法，根據(jù)道路的不同類型，自適應(yīng)調(diào)整權(quán)重和計算變量，實現(xiàn)城市復(fù)雜路網(wǎng)下的精準地圖匹配，并且即使在大規(guī)模匹配數(shù)據(jù)量情況下，減少了單點匹配時間。

1 算法實現(xiàn)

1.1 數(shù)據(jù)預(yù)處理

地圖匹配是將車輛的定位信息匹配到相應(yīng)道路上的過程。本研究中，車輛的定位信息是通過安裝在車輛的車載終端設(shè)備獲取，地圖的數(shù)據(jù)信息通過OSM(Open Street Map,OSM)官網(wǎng)下載獲取。OSM地圖數(shù)據(jù)是免費開放的，是通過全球志愿者提供的， OSM地圖數(shù)據(jù)主要有Node(節(jié)點)、Way(道路)和Relation(關(guān)系) 3種類型[29-31]。由于城市道路錯綜復(fù)雜，車輛的定位信息經(jīng)常會由于建筑物、立交橋、高架路以及地下隧道的遮擋產(chǎn)生一定的誤差，導(dǎo)致接收到異常數(shù)據(jù)。因此，為了減少定位信息的異常對匹配準確率的影響，需要提前對定位信息進行預(yù)處理。首先去除定位信息的異常數(shù)據(jù)，其次，利用插值法補全缺失的定位數(shù)據(jù)。通過車載終端設(shè)備，我們獲取的車輛定位信息包括車輛的經(jīng)緯度、車輛方向角、車速、時間等[32-35]，剔除定位信息的異常數(shù)據(jù)原理如圖1[11]所示。

圖1 去除原理示意圖Fig.1 Schematic diagram of elimination principle

根據(jù)定位的誤差和車輛的最大偏移確定距離的最大值，將大于距離最大值的定位點進行去除，距離最大值也被稱為距離閾值Rmax,計算公式見式(1)：

Rmax=(Vrmax+Vs)·δt+r,

(1)

式中，Vrmax為道路最大限速；Vs為瞬時速度誤差；δt為車輛定位信息采樣間隔時間；r為置信水平一定下的定位數(shù)據(jù)誤差圓的半徑；Rmax為車輛的最大偏移距離和誤差圓半徑的和；如果定位點到道路的距離超過Rmax,那么此定位點被剔除，反之，保留此定位點。

除了剔除定位異常點之外，本研究還利用插值算法補全定位點坐標，插值原理如圖2所示。

圖2 插值原理示意圖Fig.2 Schematic diagram of interpolation principle

其中(xi,yi)是需要補全的定位點坐標，(xi-1,yi-1)為前一時間的定位點坐標，vi-1為前一時刻車輛的速度，φi-1,φi-2分別為前兩個時刻的定位點的車輛方向角，即為車輛的行駛方向與正北方向的夾角。因此的(xi,yi)計算公式如下：

xi=xi-1+vi-1·δt·sin[(φi-1-φi-2)+φi-1]

，(2)

yi=yi-1+vi-1·δt·cos[(φi-1-φi-2)+φi-1]。

(3)

除了對車輛定位信息進行數(shù)據(jù)預(yù)處理之外，還需對待匹配的原始地圖數(shù)據(jù)進行預(yù)處理。本研究中我們使用的地圖數(shù)據(jù)是從OSM地圖網(wǎng)站[36-37]下載的，因此需要對地圖數(shù)據(jù)進行處理為所需的待匹配地圖數(shù)據(jù)，主要為地圖信息的道路檢測與補全。對車輛定位信息以及地圖數(shù)據(jù)進行預(yù)處理之后，需要對整個電子地圖進行網(wǎng)格劃分，進行地圖匹配時，會首先確定定位點所在的網(wǎng)格，然后再找出本網(wǎng)格所包含的所有候選路段，可以大大提高查詢的速度，縮短路網(wǎng)匹配時間。

1.2 候選匹配道路集合R

車輛定位數(shù)據(jù)以及地圖數(shù)據(jù)進行預(yù)處理之后，對整個電子地圖進行網(wǎng)格劃分，確定了實際道路的大概區(qū)域。目前使用誤差橢圓的算法確定一個橢圓區(qū)域。計算公式如式(4)～(6)所示，其中，a為橢圓的長半軸；b為橢圓的短半軸，車輛經(jīng)緯度的標準差以及協(xié)方差分別為σX，σY，σXY，其中σ0為可變參數(shù)，橢圓長半軸與正北方向的夾角用φ表示。

(4)

(5)

(6)

根據(jù)誤差橢圓計算公式，如果采用誤差橢圓的算法，計算量比較復(fù)雜，因此在本研究中，我們簡化了誤差橢圓的計算方法，將定位點的坐標(xi,yj)作為橢圓的中心，因此計算可以簡化為公式(8)，簡化后橢圓的長軸和焦距分別為2a′和2c′。定位點所在的網(wǎng)格通過網(wǎng)格索引進行確定。

a′=R·δt，

(7)

(8)

以此網(wǎng)格為中心的3×3網(wǎng)格內(nèi)的誤差圓包含的道路作為候選路段。全部候選匹配道路集合為R={R1,R2,…,Ri，…Rn|i=1,2，…,n}。

1.3 確定匹配路段

1.3.1 概率函數(shù)分配

(1)投影距離概率構(gòu)造

定位點到某條道路的投影距離分為兩種情況，如圖3所示，因此定位點到某一道路的投影距離計算方式也分為兩種。投影距離為路網(wǎng)匹配中很重要的指標，也就是說，車輛到候選道路的投影距離越小，車輛越有可能行駛在該條道路。

圖3 最短距離的計算Fig.3 Calculating the shortest distance

(1)定位點S1到路段PQ的最短距離為d1，計算公式如式(9)[30]：

(9)

(2)定位點S2到路段PQ的投影在路段PQ的延長線上，所以S2到路段PQ的最短距離為d2,計算公式為：

(10)

假設(shè)根據(jù)網(wǎng)格索引和誤差圓的計算，我們所獲取的候選道路集合為R={R1,R2，…,Ri,…Rn|i=1,2，…,n},那么距離的概率θ1(Ri)構(gòu)造計算見式(11)和(12)。

(11)

(12)

(2)車輛道路夾角概率構(gòu)造

根據(jù)車載導(dǎo)航終端設(shè)備采集的定位信息中，車輛的方向角也是進行精準路網(wǎng)匹配的一個重要參數(shù)，假設(shè)車輛方向與道路方向的夾角為θi，如圖4所示。

圖4 車輛與道路的夾角示意圖Fig.4 Schematic diagram of angle between vehicle driving direction and road direction

其中，假設(shè)Q點的坐標為(x,y)，O為坐標原點，坐標為(0,0)，那么路段OQ與正北方向的夾角γi可以根據(jù)式(13)[11]進行計算：

(13)

如果x=0,y<0,那么γi=π，如果x=0,y>0,那么γi=0，因此可以推導(dǎo)出θi的計算如式(14)所示：

(14)

假設(shè)從誤差圓中獲取的候選道路集合為R={R1,R2，…,Ri，…Rn|i=1,2，…,n},那么方向角的概率構(gòu)造公式如式(15)～(16)所示：

(15)

(16)

1.3.2 候選路段概率計算

本研究的對象為交叉路段下的地圖匹配，計算了距離和方向角的分配概率之后，我們采用自適應(yīng)權(quán)重的方式將兩種影響因素進行結(jié)合，計算候選路段的概率。計算公式見式(17)：

p0=μ1p1p2+μ2p1p2+μ3p1p2+μ4p1p2，

(17)

式中依次分為距離和方向都能匹配到道路Ri的概率，根據(jù)距離匹配到路段的概率，根據(jù)方向匹配到路段的概率，根據(jù)距離和方向都沒有匹配到路段的概率。

1.3.3 算法的步驟和流程圖

算法的具體實現(xiàn)步驟如下。

步驟1：對車輛定位異常信息進行剔除，對OSM地圖進行補全，對電子地圖進行網(wǎng)格劃分。

步驟2：獲取候選匹配道路集合。

步驟3：投影距離和方向的分配概率計算。

步驟4：根據(jù)不同道路類型，自適應(yīng)確定權(quán)重參數(shù)。

步驟5：計算候選匹配道路的概率。

算法的流程圖如圖5所示。

圖5 投影距離的自適應(yīng)地圖匹配算法流程Fig.5 Flowchart of adaptive map matching algorithm for projection distance

2 算法的試驗驗證及仿真比較

2.1 算法的試驗驗證

為了驗證自適應(yīng)投影地圖匹配算法性能，采用1 800多輛常州市出租車中采集的實時定位信息對算法進行實測驗證。車輛的定位信息通過車載導(dǎo)航終端獲取，包括車輛的經(jīng)緯度、車輛速度、方向角等。采樣時間間隔為10 s。主要在交叉路段的情景下進行實測，圖6為車輛在某一塊區(qū)域的匹配結(jié)果，由圖可以看出，在復(fù)雜的交叉路段背景下，車輛的每一個定位點都能很好地匹配到道路上，具有極高的匹配準確率。

2.2 算法結(jié)果分析

在城市復(fù)雜的交叉路段背景下，分別對自適應(yīng)投影算法、傳統(tǒng)投影算法、隱馬爾科夫模型算法和曲線擬合匹配算法，這4種算法進行了匹配準確率的對比，算法準確率的計算為匹配正確的定位點與全部定位點之比。由圖7可以看出，本研究算法在交叉路段的匹配準確率達98%以上，對比其他3種算法，準確率至少提高了4%，由于本研究算法在計算候選路段概率時，加大了方向角的權(quán)重參數(shù)，因此在平行路段的匹配準確率不如其他3種算法。但在組合路段的情景下，本研究算法的準確率明顯優(yōu)于其他3種算法，這表明，在交叉路段和組合路段下，本研究算法的匹配準確率最高，尤其適用于城市復(fù)雜的交叉路段。

圖7 匹配準確率對比Fig.7 Comparison of matching accuracies

對匹配算法的評價，除了計算4種不同算法的匹配準確率之外，還分別計算了4種算法的單點匹配時間，單點匹配時間是指將待匹配點匹配到確定路段所用的平均時間，圖8顯示的是4種算法分別在2，3,4,5條候選道路下的匹配時間，由圖可以得出，當候選道路為2條時，本研究所提出的算法匹配時間為3.8 ms，當候選道路為5條時，匹配時間約為5.5 ms,隨著候選道路的增加，4種算法的單點匹配時間均有所增加，但是，本研究提出的算法匹配時間均低于其他3種算法，其單點匹配時間大約可以降低1.5 ms左右，具有較好的實時性。

圖8 不同算法對應(yīng)的單點匹配時間Fig.8 Single point matching time of different algorithms

3 結(jié)論

本研究以城市交叉路段的地圖匹配為研究對象，提出交叉路段背景下的自適應(yīng)投影地圖匹配算法，通過距離閾值方法剔除定位異常點，并且通過與高德地圖進行對比，補全開放街道地圖缺失的道路信息，對開放街圖地圖進行網(wǎng)絡(luò)劃分，生成網(wǎng)格索引，結(jié)合誤差圓的計算確定候選道路集合，提高了地圖匹配速度，分別計算投影距離和方向角的分配概率，自適應(yīng)調(diào)整權(quán)重系數(shù)，對候選道路的概率進行計算，選出最優(yōu)匹配路段。通過進行試驗驗證，得出的結(jié)論如下：

(1)利用設(shè)定距離最大值的方法，去除異常定位點，對采集到的車輛定位信息進行預(yù)處理，同時通過將OSM地圖與高德地圖進行對比，對OSM地圖缺失的道路進行信息補全，為后續(xù)的地圖匹配算法提供了精準的原始數(shù)據(jù)信息，是決定地圖匹配準確度非常關(guān)鍵及重要的過程。

(2)通過對城市的OSM電子地圖生成網(wǎng)格索引，以及計算誤差橢圓的方法，確定候選道路所在的大致區(qū)域，可以提高候選道路集的查詢效率，大大減少了地圖匹配的計算時間。

(3)通過對常州市出租車車輛實時行駛數(shù)據(jù)進行試驗驗證以及算法的仿真比較，本研究提出的自適應(yīng)投影地圖匹配算法，與其他3種地圖匹配算法相比，雖然在平行道路下，匹配準確率有所下降，但是在交叉道路背景下，匹配準確率提高了4%左右，很好地解決了交叉路段背景下的地圖匹配難的問題。

(4)與其他3種地圖匹配算法相比，通過分別對2,3,4,5條候選道路情況下的單點匹配時間進行計算，計算結(jié)果表明，自適應(yīng)的投影地圖匹配算法，在多條候選道路的情況下，單點匹配時間縮短了1.5 ms左右，提高了算法性能，實現(xiàn)了交叉路段背景下的快速地圖匹配。

本研究的對象是城市交叉道路背景下的地圖匹配算法及應(yīng)用，由于城市道路網(wǎng)絡(luò)的復(fù)雜性，城市道路網(wǎng)絡(luò)還包含大量的高架路，立交橋等，下一階段的研究內(nèi)容將為研究如何對車輛在高架路或者立交橋進行精準的定位，實現(xiàn)復(fù)雜路網(wǎng)下的高精度地圖匹配，提高路網(wǎng)匹配算法的性能。