基于Android移動終端的車輛導航地圖匹配算法研究

曾錫山 ，范冰冰

(華南師范大學計算機學院，廣州510631)

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

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

常見的地圖匹配算法分為幾何匹配、拓撲匹配、概率統(tǒng)計法和高級匹配算法［2］，其中拓撲匹配算法利用了道路網絡中路段間的連接性、連通性等拓撲信息，消耗的計算資源較少且易于實現(xiàn)，同時又具有較好的匹配效果，主要用于車輛導航等實時應用［3］.本文基于Android 移動終端設計了一種基于路網拓撲結構的地圖匹配算法，該算法計算簡單、具有較高的路段識別率，匹配后的位置精度有較大提高.

1 算法思想

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

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

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

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

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

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

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

1.2 確定車輛所在路段

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

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

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

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

2)存在歷史匹配路段，則利用道路網絡的拓撲關系，只選擇誤差區(qū)內與歷史匹配路段相連通的路段為候選路段.

利用歷史匹配信息和路網拓撲信息過濾掉不可能的路段，一方面減小了候選路段集從而減少算法計算量，另一方面也可以提高匹配準確率.

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

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

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

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

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

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

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

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

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

1.3 確定車輛匹配位置

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

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

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

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

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

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

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

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

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

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

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

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

圖3 車輛過道路拐彎點時的定位Figure 3 Real vehicle positioning around turning

1.4 出錯檢測

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

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

2 算法實現(xiàn)

2.1 詳細流程

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

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

2.2 獲取車輛行駛方向

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

3 結果與分析

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

圖5 不同權重下的路段識別正確率Figure 5 Road segment identifying rate under different weights

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

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

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

4 結論

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

［1］王美玲，程林. 浮動車地圖匹配算法研究［J］. 測繪學報，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］王敏，魏衡華，鮑遠律. GPS 導航系統(tǒng)中的地圖匹配算法［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］王忠民，王青，張榮，等. 一種基于位置點的地圖匹配改進算法［J］. 計算機應用研究，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］柳林，李萬武，王志佘，等. 實時高精度地圖匹配技術的研究與實現(xiàn)［J］. 測繪科學，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ǒng)研究［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 的智能交通路網數(shù)據(jù)的構建［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.