交叉路段的自適應投影地圖匹配算法及應用

付小雪，羅贊文，劉振東

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

0 引言

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

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

1 算法實現

1.1 數據預處理

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

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

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

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

(1)

式中，Vrmax為道路最大限速；Vs為瞬時速度誤差；δt為車輛定位信息采樣間隔時間；r為置信水平一定下的定位數據誤差圓的半徑；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)

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

1.2 候選匹配道路集合R

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

(4)

(5)

(6)

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

a′=R·δt，

(7)

(8)

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

1.3 確定匹配路段

1.3.1 概率函數分配

(1)投影距離概率構造

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

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

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

(9)

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

(10)

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

(11)

(12)

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

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

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

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

(13)

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

(14)

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

(15)

(16)

1.3.2 候選路段概率計算

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

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

(17)

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

1.3.3 算法的步驟和流程圖

算法的具體實現步驟如下。

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

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

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

步驟4：根據不同道路類型，自適應確定權重參數。

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

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

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

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

2.1 算法的試驗驗證

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

2.2 算法結果分析

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

圖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 不同算法對應的單點匹配時間Fig.8 Single point matching time of different algorithms

3 結論

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

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

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

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

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

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