滕志軍，李昊天，張 宇，何義昌

(1.東北電力大學 a.現(xiàn)代電力系統(tǒng)仿真控制與綠色電能新技術(shù)教育部重點實驗室；b.電氣工程學院,吉林 吉林 132012；2.中國聯(lián)合網(wǎng)絡(luò)通信有限公司 菏澤市分公司,山東 菏澤 274000)

0 引言

定位數(shù)據(jù)和電子地圖均存在難以避免的誤差[1]，導致車輛的定位結(jié)果顯示錯誤。地圖匹配算法可以解決誤差干擾的問題，將定位點匹配到正確的路段上。現(xiàn)有的地圖匹配算法可分為4種類型：基于幾何信息的算法，基于拓撲關(guān)系的算法，基于概率統(tǒng)計的算法以及復(fù)合匹配算法?；趲缀涡畔⒌乃惴ㄎ纯紤]道路拓撲結(jié)構(gòu)，易造成錯誤匹配[2-5]?；谕負潢P(guān)系的算法易受噪聲、數(shù)據(jù)稀疏性等因素的影響，難以解決復(fù)雜路網(wǎng)匹配的問題[6-7]?；诟怕式y(tǒng)計的算法涉及復(fù)雜的公式證明與推導，算法穩(wěn)定性不佳[8-9]?？柭鼮V波、D-S證據(jù)理論等復(fù)合匹配算法雖然準確率很高，但低頻采樣時錯誤率較高[10-15]。基于隱馬爾可夫模型的地圖匹配算法，可以很好地解決低頻采樣錯誤率較高的問題，但是隨著城市道路拓撲結(jié)構(gòu)越來越復(fù)雜，導致該算法準確率不穩(wěn)定，單點匹配耗時長[16-17]。

綜上所述，單一算法很難較好地權(quán)衡準確率和時效性，因此，本文結(jié)合了幾何匹配算法和基于隱馬爾可夫匹配算法兩種思想，重新定義匹配程度的概念。對傳統(tǒng)點到線的匹配算法進行改進，提出了一種融入動態(tài)距離權(quán)重因子的隱馬爾可夫模型(hidden Markov model，HMM)地圖匹配算法。借助仿真實驗，驗證了本文HMM地圖匹配算法的單點匹配時間更少且準確率更高。

1 確定路段檢索區(qū)域

經(jīng)典算法選擇以車輛定位位置為區(qū)域中心的方形或圓形區(qū)域作為路段檢索區(qū)域。為了提高算法的運行效率，本文通過兩次篩選確定路段檢索區(qū)域，第1次篩選利用網(wǎng)格索引對電子地圖進行劃分，合理選擇以車輛當前定位位置為中心的九宮格區(qū)域，盡可能減少候選道路數(shù)量；第2次篩選以行車方向為長軸作橢圓形，剔除沒有經(jīng)過橢圓形區(qū)域的候選路段，進一步減少計算量，確定最終的路段檢索區(qū)域。

建立網(wǎng)格索引，以l(依據(jù)工程經(jīng)驗一般選取200 m)為邊長劃分網(wǎng)格，以G(gx，gy)為分塊網(wǎng)格索引號。若定位點為P(i，j)，則定位點的網(wǎng)格索引號為：

(1)

圖1 路段檢索區(qū)域示意圖

圖1為路段檢索區(qū)域示意圖。如圖1所示，以定位點P(i，j)為中心的3×3的網(wǎng)格區(qū)域為經(jīng)過第1次篩選后的路段檢索區(qū)域，此時候選路段為A、C；接著以行車方向為長軸作橢圓形，則可以排除路段C，區(qū)域內(nèi)的路段A為經(jīng)過第2次篩選后的候選路段，確定路段A作為車輛定位點P的最佳匹配路段。

圖1中，a為路段檢索區(qū)域長軸的1/2，b為短軸的1/2，Ψ為a與正北方向之間的角度，且Ψ≤π。a、b和Ψ由以下公式確定[18]：

(2)

(3)

(4)

2 匹配程度

點到線的匹配算法把全部路段都視為候選路段，計算定位點到所有路段之間的垂直距離，由最小距離確定最佳匹配路段。如果點到幾條路段的距離都相等，那么會造成無法執(zhí)行匹配的情況，從而發(fā)生錯誤。與點到點的匹配算法相比較，點到線的匹配算法的準確率有所提升，但是未考慮道路拓撲結(jié)構(gòu)和車輛行駛軌跡曲線等因素，因此穩(wěn)定性相對較差，容易產(chǎn)生錯誤匹配。

本文在傳統(tǒng)算法的基礎(chǔ)上，引入車輛行駛速度和歷史匹配程度兩個因素，采用多個因素重新定義匹配程度的概念，并將距離權(quán)重因子改為動態(tài)，應(yīng)用到基于HMM的地圖匹配算法中，可在一定程度上改善本文算法的時效性和準確率。定位點與候選匹配路段的匹配程度為：

(5)

其中：α為距離權(quán)重因子；D為待匹配點與候選路段間距離的特征值參數(shù)；dlp為定位點P到候選路段l的投影距離；β為角度權(quán)重因子；θ為車輛此時行進方向與候選路段之間夾角的特征值參數(shù)；ω為車輛行駛方向與路段方向的夾角；γ為速度權(quán)重因子；v為車輛此時速度的特征值參數(shù)；τ和lτ分別為行駛時間和距離；λ為歷史匹配程度權(quán)重因子；M′為歷史匹配程度；Mik為第k個定位點到第i條候選路段的匹配程度；j為當前定位點數(shù)。

3 基于HMM的改進算法

本文提出的改進算法主要包括兩部分：數(shù)據(jù)預(yù)處理以及改進地圖匹配算法。匹配算法流程圖如圖2所示。數(shù)據(jù)預(yù)處理是除去全部無效的、異常的以及冗余的定位數(shù)據(jù)；改進地圖匹配算法包含標準差σ的估計、4個特征值參數(shù)的權(quán)重因子計算等。

圖2 匹配算法流程圖

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

定位數(shù)據(jù)會受到多種因素的影響，比如對流層、電離層傳播延時，從而產(chǎn)生不可避免的定位誤差，使定位點遠離候選路段，產(chǎn)生大幅度漂移，這些有誤差的定位數(shù)據(jù)會給地圖匹配算法的準確率和時效性帶來嚴重的影響，可能會增加計算量和工作難度。所以，在執(zhí)行地圖匹配算法之前要先將獲取的定位數(shù)據(jù)進行分類、匯總，然后除去全部無效的、異常的以及冗余的定位數(shù)據(jù)。具體篩選規(guī)則如下：

(Ⅰ)如果定位數(shù)據(jù)遠離候選路段，根據(jù)定位點構(gòu)建的路段檢索區(qū)域內(nèi)沒有候選路段，則這些定位數(shù)據(jù)為漂移點，視為無效的數(shù)據(jù)并刪除。

(Ⅱ)如果定位數(shù)據(jù)記錄中，在連續(xù)時間段內(nèi)車輛的經(jīng)緯度坐標出現(xiàn)多次重復(fù)，則判定該條數(shù)據(jù)記錄為異常數(shù)據(jù)并剔除。

(Ⅲ)如果定位數(shù)據(jù)記錄中，同一車輛出現(xiàn)采集時間多次重復(fù)的若干條記錄，則判定此數(shù)據(jù)記錄為冗余數(shù)據(jù)，經(jīng)過處理后只需保留一條格式正確的、不再重復(fù)的數(shù)據(jù)記錄，將冗余數(shù)據(jù)全部刪除。

3.2 改進地圖匹配算法

為了權(quán)衡地圖匹配算法的準確率和時效性，本文首先使用多模態(tài)魯棒回歸估計，對觀測概率矩陣B中的標準差σ進行估計，選取概率最大的兩條候選路段；然后引入動態(tài)的距離權(quán)重因子α，通過多個因素構(gòu)建的函數(shù)分別計算兩條候選路段的匹配程度M，其數(shù)值較大的候選路段所對應(yīng)的為最終確定的候選路段。

文獻[19]結(jié)合時空特性，包括幾何、拓撲以及速度等約束條件，采用均值μ=0、標準差σ=20 m的高斯分布表示在隱含狀態(tài)下得到的觀測概率矩陣B：

(6)

可以用一個定位點和候選路段之間距離的高斯分布來表示定位點的誤差。文獻[20]仍然使用均值μ=0的高斯分布，而標準差σ是采用絕對中位差來進行魯棒估計，得到了噪聲的合理值，σ的計算公式為：

(7)

(8)

本文采用多個因素構(gòu)造的函數(shù)確定匹配程度，并引入動態(tài)的距離權(quán)重因子，使匹配準確率在一定程度上更優(yōu)。在路段檢索區(qū)域內(nèi)，對于定位點P及其候選路段，若路段檢索區(qū)域內(nèi)只有一條候選路段，則該路段為最佳匹配路段；若候選路段不只一條，此時需要對候選路段進行篩選，對候選路段的觀測概率進行排序，通過上述方法得到觀測概率排名前兩位的候選路段la和lb,計算兩條候選路段的匹配程度M，其數(shù)值較大的候選路段所對應(yīng)的為最終確定的候選路段。

一些匹配算法的權(quán)重因子大多是由主觀經(jīng)驗確定的，使得匹配算法的結(jié)果差異很大，準確率不穩(wěn)定[22-24]，針對這個問題，引入動態(tài)距離權(quán)重因子，使其不再由主觀經(jīng)驗確定，可在一定程度上提高本文算法的穩(wěn)定性。文中提出的匹配程度由4種參數(shù)確定，歷史匹配程度M′與之前匹配的軌跡數(shù)據(jù)有關(guān)聯(lián)，可以將其權(quán)重因子λ設(shè)置為：

(9)

(Ⅰ)確定α值

引入動態(tài)的距離權(quán)重因子，通過對20 000個定位點的分析得出，距離D小于Dmax=50 m的定位點所占比例接近99%，距離D小于Dmin=0.5 m的定位點所占比例不足1%。綜上所述，定義動態(tài)的距離因子α為：

(10)

(Ⅱ)確定β值

根據(jù)上文分析，路段檢索區(qū)域內(nèi)有兩條候選路段，得到觀測概率排名前兩位的候選路段la和lb，定義ρ1和ρ2為兩條候選路段的觀測概率，相應(yīng)的評價Rz和β分別為：

(11)

(12)

(Ⅲ)確定γ值

車輛當前的行駛速度與道路網(wǎng)的信息、駕駛?cè)藛T的行為都有著密不可分的關(guān)系，在500 s的時間內(nèi)對車輛的速度誤差進行仿真實驗分析，結(jié)果如圖3所示。

(a) 東向速度誤差

(b) 北向速度誤差

(c) 天向速度誤差

圖3 車輛的速度誤差

圖3a為東向速度誤差，經(jīng)過多次仿真發(fā)現(xiàn)速度誤差最大值在0.5 m/s以內(nèi)，并通過計算500 s內(nèi)的速度誤差得出標準差約為0.27 m/s。圖3b為北向速度誤差，其最大值約為0.8 m/s，取平均值經(jīng)計算得出標準差約為0.35 m/s。圖3c為天向速度誤差，其速度誤差最大值約為0.5 m/s，取平均值經(jīng)計算得出標準差約為0.18 m/s。由以上數(shù)據(jù)可以看出：3個方向速度誤差的標準差最大值為0.35 m/s，該值在可接受的誤差范圍之內(nèi)，低頻采樣條件下，完全可以適應(yīng)各種道路拓撲結(jié)構(gòu)。因此，根據(jù)速度誤差的仿真結(jié)果，當車輛在一定區(qū)間內(nèi)行駛的平均速度小于路網(wǎng)的限制速度時，將其權(quán)重因子γ置為1；否則，認為車輛不具備在該路段上行駛的條件，將其權(quán)重因子γ置為0。

4 仿真實驗

首先通過仿真實驗驗證本文算法的運行效率，分別從4種不同的路段中隨機選取240個定位點，對其單點匹配時間進行統(tǒng)計分析。圖4為本文算法與其他3種對比算法的單點匹配時間的仿真結(jié)果比較。從圖4中可以看出：本文算法的單點匹配時間在5 ms上下浮動，約為5.20 ms；點到線匹配算法的單點匹配時間大部分集中在20～25 ms，約為22.73 ms；固定權(quán)重匹配算法的單點匹配時間和傳統(tǒng)HMM算法的單點匹配時間大致相同，約為13.81 ms。本文提出的改進算法的單點匹配時間相對較少，在時效性上更加具有優(yōu)勢。

在單一路段、平行路段、交叉路段以及復(fù)雜路段4種路段拓撲結(jié)構(gòu)下，對本文算法與其他3種地圖匹配算法的準確率進行比較，結(jié)果如圖5所示。

圖4 單點匹配時間仿真結(jié)果比較

圖5 匹配準確率比較

由圖5可知：當車輛在簡單路段行駛時，4種匹配算法的準確率都比較高，本文改進算法的匹配準確率和其他3種算法的準確率相近。當車輛駛?cè)肫叫?、交叉甚至更為?fù)雜的路段時，本文改進算法的匹配準確率依然能達到90%以上。隨著路況復(fù)雜程度的增加，本文算法的準確性明顯優(yōu)于其他3種對比算法的準確性。

當車輛駛?cè)霃?fù)雜路段時，對4種地圖匹配算法位置誤差的標準差進行統(tǒng)計，結(jié)果見表1。從表1中可以看出：本文算法東向位置誤差的標準差為4.30 m，北向為4.36 m，天向為4.26 m，本文算法3個方向的誤差比其他3種對比算法的誤差都要小，并且位置誤差波動的幅度均在可以接受的范圍之內(nèi)。

表1 不同地圖匹配算法位置誤差的標準差對比 m

5 結(jié)束語

本文以基于HMM的匹配算法為基礎(chǔ)，采用多個因素定義匹配度，引入動態(tài)的距離權(quán)重因子，結(jié)合幾何匹配算法和基于HMM匹配算法的思想，提出一種改進的地圖匹配算法，以降低定位點的單點匹配時間，提高算法整體的運行效率，使算法在時效性上更加具有優(yōu)勢。通過仿真驗證，改進后的匹配算法準確率有所提高，即使在低頻采樣條件下，復(fù)雜路況的準確率依然可以達到90%以上，與3種傳統(tǒng)的匹配算法進行比較，本文算法在時效性和準確性上均有所改善。下一階段將重點研究高頻采樣時的算法優(yōu)化，在保證時效性的前提下獲得更高的準確率。