基于多屬性融合策略的車載導航地圖匹配算法

滕志軍，曲兆強，郭素陽，于 明，付 饒，井梓鑒

（1.東北電力大學信息工程學院，吉林吉林132012；2.中交天和機械設備制造有限公司，江蘇蘇州215000；3.國網吉林供電公司，吉林吉林132001）

基于多屬性融合策略的車載導航地圖匹配算法

滕志軍1，曲兆強1，郭素陽2，于 明3，付 饒3，井梓鑒3

（1.東北電力大學信息工程學院，吉林吉林132012；2.中交天和機械設備制造有限公司，江蘇蘇州215000；3.國網吉林供電公司，吉林吉林132001）

目前直接投影算法常用于嵌入式車載系統，但其時效性以及精確性不能滿足日益復雜的城市道路網絡.針對傳統算法檢索復雜道路耗時多等問題，提出了基于多屬性融合策略的車載導航地圖匹配算法，提高了嵌入式車載地圖匹配算法的時效性，算法采用等步長分塊策略，建立分塊網格索引減少篩選候選區域時間，從而提高算法的時效性；通過引入車輛行駛速度和歷史匹配程度改進基于權重的直接投影算法，使用多屬性融合策略確定匹配算法權重因子，提高地圖匹配的準確性.結果表明：該地圖匹配算法能夠快速、準確地匹配出行駛路徑，單點匹配時間降低至15 ms，復雜道路下，匹配準確率達到90%以上，能較好地適應于城市復雜道路網.

智能交通；地圖匹配；融合策略；車載；匹配程度

目前，由定位導航系統得到的定位數據存在難以避免的誤差，例如接收機內部噪聲、無法修正的傳播延遲誤差等［1］，為了消除定位誤差，提高定位準確性和可靠性，需引進有效的地圖匹配算法［2］.地圖匹配技術［3］是利用軟件的方法，將定位點數據匹配到車載導航地圖的道路網絡中，從而確定車輛在導航地圖上的準確位置.目前多數地圖匹配算法的基本步驟：① 按照一定的篩選準則確定車輛當前行駛的道路；② 利用投影方式將定位點匹配到道路，獲取車輛的準確位置信息［4－5］.文獻［6］采用直接投影法將定位數據點直接投影到道路網絡，該方法具有易于實現等優點，但是，定位數據本身的誤差使得該方法存在可靠性不足的弊端.文獻［7－8］提出了基于拓撲關系的地圖匹配算法，此方法對電子地圖精確度有較強的依賴性，特別在道路交叉路口，易出現匹配錯誤的狀況.文獻［9］采用模糊神經網絡建立一種新型算法模型，能夠較好地提高匹配的穩定性和時效性，同時也存在著實現難度較大，不適合車載嵌入式系統的問題.文獻［10］提出了基于多權值的概率論匹配算法，該算法依據接收到的定位數據設置一個置信區域，利用概率準則選出道路匹配信息，此種算法對地圖和定位數據精度具有較強的依賴性，存在穩定性較差的缺點.導航地圖匹配算法的性能指標主要分為精確性、時效性和穩定性3個方面［11－12］.精確性是由匹配算法的誤差、接收的定位數據誤差等方面決定；時效性體現在獲取匹配位置點的時間長短；穩定性取決于匹配算法的穩定以及接收的定位數據穩定2個部分.綜合上述性能，筆者提出一種新型的地圖匹配算法，該算法包括2個部分：①對導航地圖分塊處理，縮短搜尋匹配路段區域時間，提高系統的時效性；②采用改進的直接投影算法，將距離、速度以及方向偏角等因素預處理，能夠有效地提高地圖匹配的精確性和穩定性.

1 導航地圖分塊處理

通過對導航地圖進行分塊處理，能夠有效減小搜尋道路網的數據規模，縮短獲取匹配路段區域的時間，顯著提高系統的時效性.因此，采用等步長的網格劃分方式，建立路段信息的網格索引，定位點匹配過程中僅需考慮定位點周圍的3×3網格（依據行駛區域設定）中的路段信息，有效提高了地圖匹配過程的時效性.

建立網格坐標系，選取地圖網絡中的任意一點為坐標原點O，以l（依據工程經驗一般選取200 m）為邊長劃分網格，以G（gx，gy）為分塊網格索引號.若定位點為P（i，j），則定位點的網格索引號為

道路網格分塊索引如圖1所示，將定位點P（i，j）周圍3×3的網格設置為搜索遍歷區域，區域內的道路為候選匹配路段，分別建立對應的網格索引號.

圖1 道路網格分塊索引

2 地圖匹配算法

通過對道路網的分塊處理，使得定位數據能夠快速確定其候選道路區域，綜合利用地圖匹配算法，達到快速定位的目的.由于車載嵌入式定位導航系統硬件等因素的限制，設備計算開銷有限，因此相對簡單、計算復雜度較低的直接投影地圖匹配算法符合要求.由于傳統的直接投影方法一般考慮將定位數據點到候選路段的距離和車輛行駛方向與候選道路的方向夾角等因素，通過加權計算來確定匹配路段.傳統方式存在著算法過于簡易、穩定性相對較差、權重因子需人工設置、缺少科學理論依據等問題.文中通過引進車輛行駛速度和歷史匹配程度2個因素，采用多屬性決策方法確定權重因子，從而提高直接投影方法的穩定性及精確性.

車輛行駛軌跡與候選道路的匹配程度為

式中：α為定位點到候選路段的距離權重系數；D為定位點到候選道路的距離；β為方向偏角的權重系數；θ為車輛行駛方向與候選路段的方向偏角；γ為行駛速度的權重系數；v為車輛行駛的速度；λ為歷史匹配程度權重系數；W′為歷史匹配程度.

現實道路網中存在很多弧段，道路網比較復雜，直接投影會出現如圖2所示的錯誤情況.定位點P向弧段S做投影，投影點R落到弧段端點AB的連接線上，造成了錯誤的投影.因此需要進行弧段分割處理，將弧段分割成更小的線段，并將線段信息提取出來，作為候選匹配路段.

圖2 弧段道路投影

3 算法參數設定

由于本算法涉及到定位點到候選路段的距離、車輛行駛方向與候選路段的方向偏角以及車輛行駛速度等參數，不同參數的度量單位不統一為確定當前定位點到候選路段的匹配程度帶來了麻煩.因此，提出一種新型的參數設置方法，有效解決算法參數不統一的問題，降低系統計算開銷，提高系統的匹配性能.

3.1 距離參數設定

第j個定位點到第i條候選路段的距離為dij，通常分為2種情況：①經定位點P作候選路段AB的垂線，垂足R落在候選路段，垂線長度為d1；②過定位點P做候選路段AB的垂線，垂足R處于路段的延長線上，則定位點到候選路段的距離為定位點到路段端點最近的距離d2.定位點j到候選路段i的距離dij如圖3所示.

圖3 定位點到候選路段的距離

定位點到候選路段的距離為

由于目前導航定位系統的精度為10 m左右，則設置定位點到候選路段的距離dij時，門限值選取10 m較合適.依據概率分布3倍標準差的原則，考慮到城市道路網的實際情況，最大距離選取30 m，當定位點到候選路段的距離大于30 m時，則認為定位點不會匹配到該候選路段.

3.2 方向偏角參數設定

城市道路網信息復雜多樣，如車輛行駛于交叉路口，由定位距離確定候選路段會出現錯誤匹配的情況，則依據航偏角判斷候選路段會較為準確.現定義平角八等分，數字1表示0°到22.5°，數字2表示22.5°到45.0°，依次類推.如圖4所示，道路線AB對應的值為1，BC對應的值為2，車輛行駛路線P1P2為1，P2P3為1，P3P4值為2.

圖4 定位點道路示意圖

為了篩選出候選路段，引入航偏差：

式中：a1為車輛行駛方向值；a2為道路方向值.

通過航偏差得出車輛行駛方向與候選路段的方向偏角為

考慮到航偏差作為車輛行駛方向與候選路段的方向偏角的判斷標準時，Δ取值相對較小，車輛方向偏角得出的匹配結果越精確，則航偏差小于1時，方向偏角參數取到最大值1.考慮到航偏差大于6時，車輛相當于掉頭行駛，則方向偏角不能作為匹配因數.

3.3 車輛行駛速度參數設定

現城市交通路段大多數有速度限制，當匹配車輛無法確定車輛候選路段時，可以依據車輛行駛速度、道路網信息篩選出符合條件的匹配路段.然而，依據車輛在某一時刻的瞬時速度無法做出判斷，則需要車輛第i時刻和前一個時刻i－1的平均速度：

式中：li為車輛由i－1時刻行駛到i時刻的距離；ti－1→i為行駛時間.

當接收到定位點數據后，經過計算可得車輛行駛速度，通過對候選區域內道路網速度信息限制條件比對，當v小于候選道路速度限制條件時，設置其參數為1；否則，認為車輛不會行駛在該路段，其參數設置為0，綜合利用道路網信息能夠更加有效地篩選出候選匹配路段.

3.4 歷史匹配程度參數設定

當前匹配路段與歷史匹配路段有關，候選路段的歷史匹配程度越高，下一時刻匹配到該路段的可能性就越大.

歷史匹配程度為

式中：Wik為第k個定位點到第i條候選路段的匹配程度，由式（2）可以得出；j為當前定位點數，j－1為歷史定位點數.

歷史匹配程度W′采用取平均的方式計算得出.

3.5 算法參數權重設定

傳統算法權重因子由人工主觀確定，使得匹配結果差異性較大，穩定性較弱，因此采用多屬性決策方法來確定權重系數，較大程度地提高匹配的穩定性.考慮到距離因素d和方向偏角θ與候選路段的性質可以采用多屬性決策方法來確定權重因子.然而車輛行駛速度由道路網信息決定，則可以設置：當車輛行駛速度參數為1時，其權重因子也設置為1；當車輛行駛速度參數為0時，其權重因子設置為0.歷史匹配程度W′與之前的匹配程度有關，則其權重因子λ可以設置為

定義ρij為第i條候選路段的第j個屬性值，根據上文權重因子的設置可知j分為2種情況，現定義ρi1為第i條候選路段對應的定位點到該候選路段的距離屬性值，ρi2為第i條候選路段對應的方向偏角屬性值.設區域內有m個候選路段，相應的評價定義為

定義ψj為第j個屬性對應的權重系數，j＝1時，ψj為定位點到候選路段的距離權重系數α；j＝2時，ψj為方向偏角的權重系數β.

由設定好的參數計算出各定位點對應候選路段的匹配程度，選取匹配程度最大的候選路段作為匹配路段，再采用垂直投影得出匹配點，完成整個匹配過程.

4 仿真結果分析

地圖匹配算法以時效性、準確性作為判斷標準，為了驗證所提出的算法的性能，將本算法以編程語言實現，應用于仿真測試系統中.該系統可以模擬城市復雜區域道路網信息，經過坐標轉換，將道路網信息顯示于二維坐標系中，模擬定位數據點進行匹配并在模擬地圖中顯示出匹配結果.模擬地圖包含平行路段、交叉路段等復雜道路網絡，可以有效驗證提出的匹配算法的性能.通過對嵌入式車載常用的3種地圖匹配算法仿真比較分析，驗證了提出的匹配算法的時效性、準確性較優.

4.1 算法仿真比較分析

為了比較提出的匹配算法的性能，分別對傳統的直接投影地圖匹配算法與D S匹配算法和與GPS／DR組合導航的地圖粗匹配算法進行匹配統計分析.對4種地圖匹配算法的單點匹配時間仿真統計比較如圖5，6所示.

圖5 文中算法與GPS／DR粗匹配算法單點匹配時間比較

圖6 直接投影與D S匹配算法單點匹配時間比較

為了驗證地圖匹配算法時效性性能指標，從不同的候選路段隨機選取240個定位匹配點，對各個匹配點的匹配時間進行統計分析.由圖5可以看出：提出的匹配算法單點定位時間約為15 ms，GPS／DR組合粗匹配算法單點定位時間為21ms左右；由圖6可以看出：直接投影地圖匹配算法單點定位時間與D S匹配算法相當，約為50 ms.由仿真統計可以得出，文中提出的地圖匹配算法單點匹配時間較小、算法的時效性較優.

通過選取單一路段、平行路段、交叉路段以及相對復雜的組合路段對4種不同的地圖匹配算法的匹配準確率進行統計比較，如圖7所示.

圖7 不同候選路段匹配算法準確率比較

從圖7可以看出：單一路段各匹配算法匹配準確率相當，當車輛行駛入平行路段、交叉路段以及復雜的組合路段時，文中提出的地圖匹配算法相對于其他算法匹配準確率較高，則該算法的準確性較好，能夠更好地適應日益復雜的城市道路網絡.

4.2 算法模擬驗證

為了使算法更具有說服力，選取復雜程度相對較高的城市道路網作為仿真模擬的區域，其定位點匹配仿真模擬的結果如圖8所示.“☆”為模擬定位點，“o”為車輛的匹配位置點.

圖8 算法模擬仿真圖

從圖8可以看出：提出的匹配算法能夠較為準確地匹配車輛真實位置，但是，當車輛行駛于道路交叉路口時，該匹配算法依然會受到影響，雖然能夠較為準確匹配車輛行駛路段，但路口交叉處會出現匹配點集中的現象.考慮到嵌入式車載地圖匹配算法的實際應用情況，交叉路口的匹配問題可以忽略不計.因此由圖8可以得出：提出的匹配算法能夠較為準確地匹配出車輛真實位置，匹配算法性能有較大的提高.

5 結 論

隨著現代道路網絡日益復雜，傳統的地圖匹配算法不能有效、準確地匹配車輛行駛位置.在傳統投影算法的基礎上，引入車輛行駛速度和歷史匹配程度2個因素，考慮到各因素之間單位不統一的情況為匹配性能帶來了影響，對各參數進行了統一設置，采用多屬性融合策略確定權重因子.仿真結果表明：文中提出的地圖匹配算法能夠實時、準確地匹配出車輛行駛位置，適用于復雜的城市道路網.但引入速度參量時僅考慮車輛正常行駛情況，未對超速行駛作出分析，如何實現非正常狀態行駛的道路匹配是下一步研究的方向.

（References）

［1］ CHEN F，SHHEN M Y，TANG Y N.Local path searc hing based map matching algorithm for floating car data［J］.Procedia Environmental Sciences，2011，10（7）：576－582.

［2］ LIX，WANG Y N，WANG M，et al.Map matching al gorithm design based on GPS information［C］∥IEEE Workshop on Electronics，Computer and Applications.USA：IEEE，2014：898－901.

［3］ BLAZAQ CA，VONDEA A P.Effects of controlling pa rameters on performance of a decision rulemap matching algorithm［J］.Journal of Transportation Engineering，2009，135（12）：966－973.

［4］ 李清泉，黃練.基于GPS軌跡數據的地圖匹配算法［J］.測繪學報，2010，39（2）：207－211.LIQ Q，HUANG L.A map matching algorithm for GPS tracking data［J］.Acta Geodaetica et Cartographica Si nica，2010，39（2）：207－211.（in Chinese）

［5］ JIA B，LIU C.Map matching algorithms based on inva riantmoments［J］.Journal of Computational Information Systems，2011，7（16）：5668－5673.

［6］ 蘇奎峰，鄧志東，黃振.基于曲率特征的自主車輛地圖匹配定位方法［J］.機器人，2012，34（4）：440－446.

SU K F，DENG Z D，HUANG Z.A novel localization approach for autonomous vehicles based on map matc hing with curvature features［J］.Robot，2012，34（4）：440－446.（in Chinese）

［7］ YANG H Q，CENG SW，JANG H F，et al.An en hanced weight based topologicalmap matching algorithm for intricate urban road network［J］.Procedia Social and Behavioral Sciences，2013，96（6）：1670－1678.

［8］ SALAMAT N，ZAHZAH E H.On the improvement of combined fuzzy topologicaland directional relations infor mation［J］.Pattern Recognition，2012，45（4）：1559－1568.

［9］ 李洋，張曉冬，鮑遠律.多權值概率論實時地圖匹配［J］.電子測量與儀器學報，2012，26（2）：166－170.

LIY，ZHANG X D，BAO Y L.Algorithm on real time map matching ofmulti weight probability［J］.Journal of Electronic Measurement and Instrument，2012，26（2）：166－170.（in Chinese）

［10］ DEKA L，QUDDUSM.Network level accident mapping：distance based pattern matching using artificial neural network［J］.Accident Analysis＆Preventin，2014，65（4）：105－113.

［11］ 方凌，賴際舟，張小山，等.基于故障狀態監測的慣性／衛星信息融合技術［J］.江蘇大學學報（自然科學版），2011，32（1）：94－98.FANG L，LAIJZ，ZHANG X S，et al.Information fu sion technology of INS／GNSS based on fault state detec tion［J］.Journal of Jiangsu University（Natural Science Edition），2011，32（1）：94－98.（in Chinese）

［12］ 楊英杰，欽鵬明.一種改進的GPS微弱信號捕獲算法［J］.東北電力大學學報，2013，33（5）：57－60.YANG Y J，QIN P M.An improved GPS weak signal capture algorithm［J］.Journalof Northeast DianliUniver sity，2013，33（5）：57－60.（in Chinese）

Vehicle navigation map matching algorithm based on multiple attribute integration strategy

TENG Zhijun1，QU Zhaoqiang1，GUO Suyang2，YU Ming3，FU Rao3，JING Zijian3
（1.School of Information Engineering，Northeast Electric Power University，Jilin，Jilin 132012，China；2.Tianhe Mechanical Equipment Manufacturing Co.，Ltd.，Suzhou，Jiangsu 215000，China；3.State Grid Jilin Power Supply Company，Jilin，Jilin 132001，China）

The present direct projection algorithm is often used in embedded vehicle system，while the timeliness and accuracy can notmeet the increasingly complex urban road network.To solve the time consuming problem of complex road in traditional retrieval algorithm，a matching algorithm for vehicle navigation map fusion strategy was proposed based on multi attribute matching algorithm to improve the efficiency of embedded vehicle map.The equal step block strategy was adopted for building block grid index to reduce screening candidate regions and improve the algorithm efficiency.The direct projection algorithm based on weightwas improved by the introduction of vehicle speed and historymatching degree，and themultiple attribute fusion strategy was used to determine thematching algorithm ofweighting factor and improve themap matching accuracy.The experimental results show that themap matching algorithm can quickly and accurately match the driving path，and the single pointmatching time is reduced to 15 mswith accurate rate more than 90%under complex roads.The proposed algorithm is suitable for the complex city road network.

intelligent transportation；map matching；integration strategy；vehicle；matching degree

10.3969／j.issn.1671－7775.2018.01.003

TN967.1

A

1671－7775（2018）01－0014－05

2016－11－25

國家自然科學基金資助項目（51277023）

滕志軍（1973—），男，吉林吉林人，教授（tengzhijun＠163.com），主要從事無線電通信研究.

曲兆強（1990—），男，山東泰安人，碩士研究生（753731087＠qq.com），主要從事地圖匹配算法研究.

滕志軍，曲兆強，郭素陽，等.基于多屬性融合策略的車載導航地圖匹配算法［J］.江蘇大學學報（自然科學版），2018，39（1）：14－18，25.

（責任編輯 賈國方）