曾錫山 ，范冰冰

(華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣州510631)

車輛導(dǎo)航地圖匹配指運(yùn)用一定的匹配算法將車輛GPS 定位數(shù)據(jù)與電子地圖中的道路網(wǎng)絡(luò)進(jìn)行比對，首先找到車輛當(dāng)前的行駛路段，然后確定車輛在路段上的位置(匹配位置)［1］.受各種干擾因素影響，GPS 定位往往存在較大誤差.地圖匹配從帶誤差的定位數(shù)據(jù)中識(shí)別出當(dāng)前行駛道路，用匹配位置來代替原始定位位置用于導(dǎo)航，能改善屏幕顯示效果，提高定位精度，是車輛導(dǎo)航的關(guān)鍵技術(shù)之一.

近年來移動(dòng)終端技術(shù)發(fā)展迅速，智能手機(jī)、平板電腦等移動(dòng)終端都配備了GPS 定位模塊，可以運(yùn)行復(fù)雜的車輛導(dǎo)航應(yīng)用. 對傳統(tǒng)車輛導(dǎo)航系統(tǒng)產(chǎn)生了巨大的沖擊.相對于專業(yè)的車輛導(dǎo)航系統(tǒng)，基于移動(dòng)終端的車輛導(dǎo)航系統(tǒng)要適應(yīng)定位精度較低、處理能力參差不齊的多種終端，對地圖匹配有著更高要求.因此，研究匹配效果較好、計(jì)算量較小的地圖匹配算法對基于移動(dòng)終端車輛導(dǎo)航具有重要意義.

常見的地圖匹配算法分為幾何匹配、拓?fù)淦ヅ洹⒏怕式y(tǒng)計(jì)法和高級匹配算法［2］，其中拓?fù)淦ヅ渌惴ɡ昧说缆肪W(wǎng)絡(luò)中路段間的連接性、連通性等拓?fù)湫畔?，消耗的?jì)算資源較少且易于實(shí)現(xiàn)，同時(shí)又具有較好的匹配效果，主要用于車輛導(dǎo)航等實(shí)時(shí)應(yīng)用［3］.本文基于Android 移動(dòng)終端設(shè)計(jì)了一種基于路網(wǎng)拓?fù)浣Y(jié)構(gòu)的地圖匹配算法，該算法計(jì)算簡單、具有較高的路段識(shí)別率，匹配后的位置精度有較大提高.

1 算法思想

基本思想是將地圖匹配分成4個(gè)相對獨(dú)立過程:(1)定位數(shù)據(jù)預(yù)處理;(2)確定車輛所在路段;(3)確定車輛匹配位置;(4)出錯(cuò)檢測.

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

預(yù)處理的作用是過濾掉異常定位數(shù)據(jù)，然后對缺失的數(shù)據(jù)進(jìn)行補(bǔ)償，以保證地圖匹配的正常進(jìn)行.當(dāng)滿足以下條件之一時(shí)，算法認(rèn)為定位異常:

1)當(dāng)可見衛(wèi)星不足4 顆(GPS 定位至少需要4顆衛(wèi)星才能獲得比較精確的位置);

2)從GPS 得到的車輛速度達(dá)到一個(gè)正常行駛不可能達(dá)到的閾值vTH，算法取vTH=200 km/h.

檢測并過濾掉異常定位數(shù)據(jù)后，使用航位推算進(jìn)行補(bǔ)償［4］:

用推算出來的坐標(biāo)(xn，yn)進(jìn)行匹配，(x0，y0)為最近的有效定位點(diǎn)坐標(biāo)，vn－1、θn－1為上一點(diǎn)處的車速和行駛方向，Δt 為定位時(shí)間間隔. 補(bǔ)償過程一直持續(xù)到GPS 定位恢復(fù)正常.

1.2 確定車輛所在路段

首先根據(jù)定位誤差模型建立候選路段集，然后使用匹配評估模型計(jì)算定位信息與各候選路段的匹配度，挑選出匹配度最高的路段作為車輛所在路段.

1.2.1 建立候選路段集 得到定位點(diǎn)后，車輛真實(shí)位置可能位于定位誤差區(qū)內(nèi)的任何一條路段(候選路段)上，建立候選路段集就是將所有候選路段信息從地圖數(shù)據(jù)庫中提取出來. 誤差橢圓［5］是最常用的定位誤差模型，即真實(shí)位置以一定置信度位于以定位坐標(biāo)為中心的橢圓區(qū)域內(nèi)，該區(qū)域可以由定位坐標(biāo)的統(tǒng)計(jì)方差計(jì)算得到.對于專業(yè)的GPS 導(dǎo)航設(shè)備，可以從輸出的電文中獲取計(jì)算橢圓方程所需的各種統(tǒng)計(jì)方差. 而對于一般的Android 移動(dòng)終端來說，通過給定的SDK 無法得到這些參數(shù). 算法采用圓形誤差區(qū)域［6］，半徑R 取移動(dòng)終端最大定位精度的3 倍(R=60 m).當(dāng)?shù)玫蕉ㄎ蛔鴺?biāo)后，分情況建立候選路段集:

式中：0和c分別代表基態(tài)和故障狀態(tài)；C表示預(yù)想故障集合；x和u分別表示由狀態(tài)變量和控制變量構(gòu)成的向量；指故障c發(fā)生后控制變量調(diào)節(jié)范圍的最大值。

1)不存在歷史匹配路段，則將誤差圓內(nèi)所有路段作為候選路段;

2)存在歷史匹配路段，則利用道路網(wǎng)絡(luò)的拓?fù)潢P(guān)系，只選擇誤差區(qū)內(nèi)與歷史匹配路段相連通的路段為候選路段.

利用歷史匹配信息和路網(wǎng)拓?fù)湫畔⑦^濾掉不可能的路段，一方面減小了候選路段集從而減少算法計(jì)算量，另一方面也可以提高匹配準(zhǔn)確率.

1.2.2 確定匹配路段 采用一種考慮距離和方向兩種要素的加權(quán)評估模型來評估定位信息與候選路段的相似度，首先計(jì)算出定位點(diǎn)到候選路段的距離相似度，再計(jì)算得到車輛行駛方向與路段走向的相似度，然后取2 種相似度的加權(quán)和作為總體相似度.距離相似度定義為:

其中d 為定位點(diǎn)到候選路段的距離，dTH是一個(gè)預(yù)先設(shè)定的距離閾值，取dTH=60 m 為誤差區(qū)域的半徑.方向相似度定義為:

其中Δθ 為車輛航向與路段走向的角度之差，大于90 度時(shí)方向相似度直接為0，小于90 度則使用余弦函數(shù)計(jì)算相似度.

總體匹配評估模型定義為:

其中wd、wθ為距離、方向相似度的權(quán)重因子，權(quán)重的大小代表相應(yīng)要素的重要程度. 算法取wd+wθ=100，則SimTotal(d，Δθ)的取值范圍為［0，100］. 用該模型對每條候選路段進(jìn)行評估時(shí)，首先應(yīng)計(jì)算方向相似度:若為0 則總相似度直接為0;否則計(jì)算加權(quán)和.這樣可以濾除方向相差太大的候選路段，減少不必要的計(jì)算.

圖1 路段匹配狀態(tài)轉(zhuǎn)換Figure 1 State transition of road matching

如圖1 所示，路段的匹配分成初始匹配和跟蹤匹配狀態(tài)，分情況處理:

1)初始匹配.將誤差區(qū)內(nèi)的所有路段加入候選路段集，統(tǒng)計(jì)連續(xù)3個(gè)定位點(diǎn)的匹配結(jié)果，當(dāng)有至少兩點(diǎn)位于同一路段上時(shí)，才認(rèn)為該路段為匹配路段，此后算法進(jìn)入跟蹤匹配狀態(tài). 否則繼續(xù)進(jìn)行初始匹配，直至找到初始匹配路段;

2)跟蹤匹配. 發(fā)生在車輛變更路段的時(shí)候，地點(diǎn)為交叉路口.利用歷史匹配信息，在建立候選路集時(shí)只將與歷史匹配路段相連通的路段納入其中，然后用匹配評估模型挑選出當(dāng)前定位點(diǎn)的匹配路段.當(dāng)算法檢測出匹配錯(cuò)誤或者不存在匹配路段時(shí)，轉(zhuǎn)入初始匹配狀態(tài).

1.3 確定車輛匹配位置

垂直投影法［7］取定位點(diǎn)到匹配路段上的垂直投影點(diǎn)作為匹配位置，該方法原理簡單，易于實(shí)現(xiàn)，但是只能消除與路段垂直方向的誤差，對與路段平行方向上的誤差(以下簡稱為徑向誤差)沒有減小效果.本文對垂直投影法進(jìn)行改進(jìn)，得到一種能夠消除部分徑向誤差的優(yōu)化方法.

為了更好地描述本文的優(yōu)化方法，先考慮如圖2 所示情況.假設(shè)GPS 定位誤差保持不變，則定位點(diǎn)P1～P3剛好位于與路段N1N2平行的直線l1上，過P4作N2N3的平行線l2，再假設(shè)車輛在道路的拐彎點(diǎn)N2處剛好產(chǎn)生一個(gè)GPS 定位點(diǎn). 用向量ei(i=1，2，3，4，N)來表示各點(diǎn)的定位誤差(圖2)，顯然有e1=e2=e3=e4=eN. 由分析可知，點(diǎn)剛好是l1和l2的交點(diǎn)，可以由兩直線的方程求得，又由于N2的坐標(biāo)已知，因此可以求出定位誤差eN. 用eN對每個(gè)定位點(diǎn)進(jìn)行修正，就可以得到車輛真實(shí)位置，消除定位誤差.

圖2 車輛過彎道時(shí)的理想定位Figure 2 Hypothetical vehicle positioning around turning

在真實(shí)情況下，盡管GPS 定位誤差是隨機(jī)變化的，但也有規(guī)律可循.文獻(xiàn)［8］通過大量實(shí)驗(yàn)發(fā)現(xiàn)車輛定位軌跡與所在道路形狀相似，對于同一終端，短時(shí)間內(nèi)定位點(diǎn)大致會(huì)偏在道路的同一側(cè)，而且偏移量近似于常量.本文利用這一規(guī)律來優(yōu)化垂直投影法，減小部分徑向誤差.

車輛過彎道時(shí)的真實(shí)定位情況往往如圖3 所示.優(yōu)化方法在車輛過路段拐彎點(diǎn)N2后并在N2N3上產(chǎn)生3個(gè)定位點(diǎn)P1、P2、P3，按以下步驟求解eN:

step1.判斷P1、P2、P3是否位于N2N3的同一側(cè):是則繼續(xù);否則求解失敗.

step2.從剛經(jīng)過的路段N1N2上取最近的3個(gè)歷史定位點(diǎn)P4、P5、P6，判斷它們是否位于N1N2的同一側(cè):是則繼續(xù);否則求解失敗.

step3.使用最小二乘法分別由P1、P2、P3和P4、P5、P6擬合出直線l1、l2(圖中虛線)，計(jì)算出角度差是否滿足條件:

其中θ 是各直線與正北方向的夾角，αTH是一個(gè)角度閾值，具體取值需要通過實(shí)驗(yàn)測定.若滿足條件(5)則認(rèn)為這6 點(diǎn)的軌跡與路徑一致，誤差基本一致，滿足求解eN的條件;否則求解失敗.

step4.分別由P1、P2、P3和P4、P5、P6擬合出與路段平行的直線l'1、l'2，求出交點(diǎn)，然后求得eN.

若eN求解成功，則從N2N3上的第4個(gè)定位點(diǎn)起開始優(yōu)化.以P7為例，先通過垂直投影法求得垂直匹配點(diǎn)P7'，然后分情況討論:若該P(yáng)7到l'1的距離小于等于(P1、P2、P3到l'2的平均距離)，則使用eN在N2N3上的水平分量修正P7';否則不修正.

在車輛過第一個(gè)拐彎點(diǎn)之前，使用垂直投影法求匹配位置.以后車輛每過一個(gè)拐彎點(diǎn)，就使用上述方法更新一次eN，然后從當(dāng)前路段上的第4個(gè)定位點(diǎn)開始優(yōu)化. 顯然，該方法的優(yōu)化效果視GPS 定位誤差的情況而定:若在某一時(shí)段內(nèi)比較穩(wěn)定則效果較好;否則變?yōu)榇怪蓖队胺?

圖3 車輛過道路拐彎點(diǎn)時(shí)的定位Figure 3 Real vehicle positioning around turning

1.4 出錯(cuò)檢測

由于定位誤差的隨機(jī)性、現(xiàn)實(shí)中道路網(wǎng)絡(luò)的復(fù)雜性，再加上算法本身也難免存在一定缺陷，錯(cuò)誤匹配是不可避免的.利用歷史匹配信息的做法存在一定的隱患，一旦路段匹配出錯(cuò)，后續(xù)的定位點(diǎn)也會(huì)跟著出錯(cuò).因此必須要有匹配出錯(cuò)檢測機(jī)制及時(shí)地發(fā)現(xiàn)并處理錯(cuò)誤.正確匹配時(shí)，車輛在路段上的匹配位置和定位點(diǎn)之間的距離應(yīng)該相差不大. 由本文采用的圓形誤差區(qū)域可知，匹配點(diǎn)Pm(xm，ym)應(yīng)位于以定位點(diǎn)P(x，y)為圓心、dTH為半徑的圓內(nèi)部，因此將通過距離檢測的條件設(shè)置為:

當(dāng)定位點(diǎn)與匹配點(diǎn)的距離大于dTH，則認(rèn)為是錯(cuò)誤匹配，需要重新執(zhí)行確定匹配道路的過程.需要明確的是，出錯(cuò)檢測并不能馬上檢測出匹配錯(cuò)誤，而是具有一定的滯后性，滯后的時(shí)間跟道路的形狀、車輛速度等都有一定的關(guān)系.

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

2.1 詳細(xì)流程

匹配的詳細(xì)流程如圖4 所示.算法的輸入包括GPS 定位數(shù)據(jù)(可見的衛(wèi)星數(shù)量、經(jīng)緯度坐標(biāo)、行駛速度)和車輛行駛方向. 算法的輸出視匹配結(jié)果而定:當(dāng)成功找到匹配路段且匹配位置正確時(shí)，輸出的結(jié)果為匹配路段和匹配位置坐標(biāo);若未找到匹配路段(匹配失敗的原因可能是車輛離開道路網(wǎng)絡(luò)或者地圖數(shù)據(jù)庫不完成而未包含當(dāng)前路段信息)，則直接輸出未經(jīng)匹配的原始定位點(diǎn)坐標(biāo). 在進(jìn)行跟蹤匹配時(shí)首先判斷車輛是否已經(jīng)變換了路段，若行駛到了新的路段則需要執(zhí)行跟蹤匹配過程重新確定匹配路段，否則直接在當(dāng)前路段上確定匹配位置.

圖4 匹配的詳細(xì)流程Figure 4 Flow of the map-matching algorithm

2.2 獲取車輛行駛方向

車輛行駛方向可以從GPS 定位數(shù)據(jù)中直接獲取，也可以由相鄰兩定位點(diǎn)坐標(biāo)計(jì)算得到.但是這2種方法得到的方向信息受車速的影響較大:車速越大則方向信息越準(zhǔn)確;車速越小則越不可靠，得到方向信息與實(shí)際行駛方向有較大出入. 當(dāng)車速小于3 m/s 時(shí)，從GPS 定位數(shù)據(jù)得到的行駛方向?qū)⑼耆豢煽浚?］. 本文采用從Android 移動(dòng)終端自帶傳感器獲取行駛方向的方法.為了獲取行駛方向，需要利用方向傳感器，這是一個(gè)虛擬的感應(yīng)器.方向傳感器將磁感應(yīng)器和重力加速度計(jì)的數(shù)據(jù)融合得到行駛方向，具體算法已經(jīng)封裝在Android 的SDK 中，具體實(shí)現(xiàn)可以參考文獻(xiàn)［9］.

3 結(jié)果與分析

實(shí)驗(yàn)硬件環(huán)境為一款普通Android 平板電腦(CPU 為ARMv6 單核245 MHz，內(nèi)存402 MB，配備加速度計(jì)、磁感應(yīng)器等傳感器)，測試表明終端的GPS 定位精度為5 ～20 m. 搭載該終端在廣州市進(jìn)行大量的跑車實(shí)驗(yàn)，終端每隔1 s 記錄一次當(dāng)前的經(jīng)緯度坐標(biāo)、車輛速度和可見衛(wèi)星數(shù)，并用一個(gè)DGPS(Differential GPS，差分GPS)接收機(jī)同步地記錄差分定位坐標(biāo). 定位數(shù)據(jù)采集完成后，使用OSM［10］(Open Street Map，開放街道地圖)矢量地圖數(shù)據(jù)進(jìn)行地圖匹配實(shí)驗(yàn)，從路段識(shí)別正確率和匹配后的位置精度來評價(jià)地圖匹配的效果. 如圖5 所示，用不同距離權(quán)重(0，5，10，…，100)下的匹配評估模型對定位數(shù)據(jù)進(jìn)行評估，找出相應(yīng)的匹配路段，然后將匹配路段與真實(shí)行車線路進(jìn)行比對，得到每種權(quán)重下的路段識(shí)別正確率.當(dāng)wD=65 時(shí)，正確率達(dá)到最大值92.64%.

圖5 不同權(quán)重下的路段識(shí)別正確率Figure 5 Road segment identifying rate under different weights

由于DGPS 定位坐標(biāo)的精度較高(2 ～5 m)，這里將其視為車輛的真實(shí)位置. 以DGPS 定位坐標(biāo)為參照，計(jì)算出地圖匹配前GPS 坐標(biāo)的平均位置精度(即GPS 坐標(biāo)到DGPS 坐標(biāo)之間的距離)為12.46 m.使用本文的優(yōu)化方法對每個(gè)點(diǎn)進(jìn)行匹配，得到不同αTH值下匹配后的位置精度(圖5).當(dāng)αTH=0°時(shí)，優(yōu)化方法相當(dāng)于垂直投影法，此時(shí)平均位置精度為8.23 m，比匹配前提高了4.23 m.當(dāng)αTH=30°時(shí)，平均位置精度達(dá)到5.22 m，比垂直投影法提高了3.01 m(圖6).圖7 給出了復(fù)雜路段的匹配效果，GPS 定位點(diǎn)經(jīng)過匹配之后都落到了正確的道路上面，匹配之后視覺效果有較大改善.

圖6 不同αTH值下匹配后的平均位置精度Figure 6 Average positioning accuracy under different αTH values

圖7 地圖匹配效果Figure 7 Effect of the map-matching algorithm

4 結(jié)論

本文基于Android 移動(dòng)終端的地圖匹配算法利用了路段拓?fù)湫畔砜s小候選路段范圍，采用綜合考慮距離和方向兩種要素的加權(quán)匹配評估模型來確定匹配路段，在確定匹配位置時(shí)對垂直投影法進(jìn)行了優(yōu)化.通過大量實(shí)驗(yàn)確定了算法的最佳參數(shù)設(shè)置，實(shí)驗(yàn)結(jié)果表明，該算法具有較高的路段識(shí)別正確率，優(yōu)化方案相對于直接投影法在匹配后的位置精度上有所提高，地圖匹配效果較好.

［1］王美玲，程林. 浮動(dòng)車地圖匹配算法研究［J］. 測繪學(xué)報(bào)，2012，41(1):133－138.Wang M L，Cheng L. Study on map-matching algorithm for floating car［J］.Acta Geodaetica et Cartographica Sinica，2012，41(1):133－138.

［2］Quddus M A，Ochieng W Y，Noland R B. Current mapmatching algorithms for transport applications:State-ofthe art and future research directions［J］. Transportation Research Part C:Emerging Technologies，2007，15(5):312－328.

［3］Velaga N R，Quddus M A，Bristow A L. Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems［J］. Transportation Research Part C:Emerging Technologies，2009，17(6):672－683.

［4］Wu Q P，Guo Z Y，Wang Y L. Study on GPS/DR/MM integrated navigation system for vehicle based DSP［C］.IEEE Xplore，2012:1591－1595.

［5］王敏，魏衡華，鮑遠(yuǎn)律. GPS 導(dǎo)航系統(tǒng)中的地圖匹配算法［J］. 計(jì)算機(jī)工程，2012，38(14):259－261.Wang M，Wei H H，Bao Y L.Map-matching algorithm in GPS navigation system［J］. Computer Engineering，2012，38(14):259－261.

［6］陳濱，王平，施文灶，等. GPS 軌跡數(shù)據(jù)的綜合地圖匹配算法研究［J］. 電子科技，2014，27(12):20－23.Chen B，Wang P，Shi W Z，et al. An integrated mapmatching algorithm based on GPS［J］. Electronic Science and Technology，2014，27(12):20－23.

［7］王忠民，王青，張榮，等. 一種基于位置點(diǎn)的地圖匹配改進(jìn)算法［J］. 計(jì)算機(jī)應(yīng)用研究，2013，30(11):3318－3323.Wang Z M，Wang Q，Zhang R，et al. Improved map-matching algorithm based on position points［J］. Application Research of Computers，2013，30(11):3318－3323.

［8］柳林，李萬武，王志佘，等. 實(shí)時(shí)高精度地圖匹配技術(shù)的研究與實(shí)現(xiàn)［J］. 測繪科學(xué)，2010，35(5):51－53.Liu L，Li W W，Wang Z Y，et al. Research and implementation of real-time high accuracy map-matching technique［J］.Science of Surveying and Mapping，2010，35(5):51－53.

［9］徐兵，廖友成，劉文杰，等. 基于Android 平臺(tái)的車載導(dǎo)航系統(tǒng)研究［J］. 計(jì)算機(jī)測量與控制，2014，22(2):601－603.Xu B，Liao Y C，Liu W J，et al. Research on vehicle navigation system based on Android［J］. Computer Measurement ＆ Control，2014，22(2):601－603.

［10］張絳麗，張笑非，徐丹，等. 基于OpenStreetMap 的智能交通路網(wǎng)數(shù)據(jù)的構(gòu)建［J］. 道路交通與安全，2014，14(1):41－47.Zhang J L，Zhang X F，Xu D，et al. Road_net data construction for intelligent transportation based on the Open Street Map［J］. Road Traffic＆Safety，2014，14(1):41－47.