[發明專利]基于隱馬爾科夫模型的地圖匹配算法

在審

• 申請號: 201810681574.8
• 申請日: 2018-06-27
• 公開（公告）號: CN109059939A
• 公開（公告）日: 2018-12-21
• 發明（設計）人: 李湘黔
• 申請（專利權）人: 湖南智慧暢行交通科技有限公司
• 主分類號: G01C21/30
• 分類號: G01C21/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明涉及地圖定位糾錯領域，尤其為基于隱馬爾科夫模型的地圖匹配算法，該算法包括以下幾個步驟：(1)根據一份電子地圖數據，將電子地圖數據信息導入地圖并生成網格矩陣；(2)對需要匹配的GPS組進行排序、學習和分類；(3)利用GPS點組初始化該匹配的隱馬爾科夫概率矩陣；(4)以當前路段序列為候選點，進行迭代和尋優，尋找到最優的路段序列。本發明，部署方便，可擴展性強；匹配計算用時少，匹配效率高；占用機器性能少；匹配精度高；可與其他系統無縫銜接。

技術領域

本發明涉及地圖定位糾錯領域，具體為基于隱馬爾科夫模型的地圖匹配算法。

背景技術

地圖匹配是一種定位糾錯的技術。其基本思想是根據車輛或其他方式提供的GPS定位信息，結合當前電子地圖中的路網信息，將兩者按照一定的邏輯進行比較和匹配，找到車輛所在的路段，根據一定的方法計算出車輛在路段上的準確位置，將車輛的定位點投放到路段上，從而改進定位不穩定或不準確所造成的誤差。當前學術和工業界已經有很多相關方案，同時也有了許多應用實例。

當前地圖匹配的主流思想和方法是百度/高德及其衍生的傳統匹配，其核心思想是將電子地圖按照網格劃分，將GPS提供的定位數據和道路的虛擬網格做XY投影，將定位數據投影至道路上，然后把多個GPS點按照最短距離(最短路)的思想連接，同時基于最短距離權重、最短路徑權重以及軌跡方向權重等來進行最短路徑的取舍。

例如《廖佳，俞薦中，李俊峰.一種利用網格劃分及方向加權的地圖匹配算法[J].測繪通報，2017(3):124-127.》這篇文獻，其利用了電子地圖的網格劃分和方向的加權，但是該文章中所描述的方法沒有考慮每一條路徑的權重，也就是有可能出現有大路有小道，大路相對于小路來說較遠，所以匹配結果是車輛從小道行駛，這是有違常理的。

再如《汪洪濤，趙靖，馮文秀.考慮行駛路徑的出租車GPS數據地圖匹配算法[J].物流工程與管理，2017，39(5):82-85.》這篇文獻，其有效結合了路段間距、車輛航向角、車輛速度、路網拓撲條件、交叉口轉向以及相鄰兩點間最大行駛距離等因素，但是這種方法對于間隔距離較長的兩個GPS點就會顯得無能為力，會出現自動去除點或者隨意導航路徑(無規律)的狀況。

綜上來說，現在有的方法或者技術存在著匹配精度低、匹配效率差等缺點。因此研究低復雜度、低成本、高精度、高效率的地圖匹配算法具有重要的現實意義。

發明內容

本發明的目的在于提供基于隱馬爾科夫模型的地圖匹配算法，以解決上述背景技術中提出的問題。所述基于隱馬爾科夫模型的地圖匹配算法具有部署方便，可擴展性強；匹配計算用時少，匹配效率高；占用機器性能少；匹配精度高；可與其他系統無縫銜接的特點。

為實現上述目的，本發明提供如下技術方案：

基于隱馬爾科夫模型的地圖匹配算法，該算法包括以下幾個步驟：

(1)根據一份電子地圖數據，將電子地圖數據信息導入地圖并生成網格矩陣；(2)對需要匹配的GPS組進行排序、學習和分類；

(3)利用GPS點組初始化該匹配的隱馬爾科夫概率矩陣；

(4)以當前路段序列為候選點，進行迭代和尋優，尋找到最優的路段序列。

進一步的，隱馬爾科夫概率矩陣包括建立一個實際狀態和一個觀測狀態，其中：觀測狀態為設備采集得到的GPS坐標，以GPS點為中心，以指定或動態半徑畫圓，圓內所有道路在做一條垂線，垂線和道路的交點就是可能的實際位置，利用K-nearest最近鄰方式可以估計出若干個可能的實際狀態，和一個真正的觀測狀態，求出車輛的軌跡序列S。

進一步的，電子地圖數據為POSTGIS數據庫以及庫表信息，讀取到之后將對應數據保存成.bmap格式，方便下一次快速讀取數據；網格矩陣是對電子地圖網格化，同時對加載進內存的電子地圖數據分塊。