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

付小雪，羅贊文，劉振東

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

0 引言

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

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

1 算法實(shí)現(xiàn)

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

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

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

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

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

(1)

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

除了剔除定位異常點(diǎn)之外，本研究還利用插值算法補(bǔ)全定位點(diǎn)坐標(biāo)，插值原理如圖2所示。

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

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

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)

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

1.2 候選匹配道路集合R

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

(4)

(5)

(6)

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

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)造

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

圖3 最短距離的計(jì)算Fig.3 Calculating the shortest distance

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

(9)

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

(10)

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

(11)

(12)

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

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

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

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

(13)

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

(14)

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

(15)

(16)

1.3.2 候選路段概率計(jì)算

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

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

(17)

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

1.3.3 算法的步驟和流程圖

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

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

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

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

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

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

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

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

2 算法的試驗(yàn)驗(yàn)證及仿真比較

2.1 算法的試驗(yàn)驗(yàn)證

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

2.2 算法結(jié)果分析

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

圖7 匹配準(zhǔn)確率對(duì)比Fig.7 Comparison of matching accuracies

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

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

3 結(jié)論

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

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

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

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

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

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