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

在審

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

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

(1)根據一份電子地圖數據，將電子地圖數據信息導入地圖并生成網格矩陣；

(2)對需要匹配的GPS組進行排序、學習和分類；

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

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

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

3.根據權利要求1所述的基于隱馬爾科夫模型的地圖匹配算法，其特征在于：電子地圖數據為POSTGIS數據庫以及庫表信息，讀取到之后將對應數據保存成.bmap格式，方便下一次快速讀取數據；網格矩陣是對電子地圖網格化，同時對加載進內存的電子地圖數據分塊。

4.根據權利要求1所述的基于隱馬爾科夫模型的地圖匹配算法，其特征在于：GPS組排序首先按照傳遞過來每一個點的GPS時間進行排序，其次將數據進行格式化，并且使用前不定數量的點來進行初始候選點的生成，對道路的最大速度和時間進行計算，去除一些在間隔時間內使用最大道路速度也無法經過的點，確認為GPS誤差，當絕對誤差GPS點都被排除，同時按照時間順序對點進行格式化之后，算法將會首先利用K-nearest，即K最近鄰算法來對那些沒有正好在道路上的GPS進行計算，按照K最近鄰算法，這個GPS坐標點可以匹配到三個點，這三個點都會作為機器學習算法的候選點，等待進行下一輪迭代。

5.根據權利要求2所述的基于隱馬爾科夫模型的地圖匹配算法，其特征在于：車輛的軌跡序列S包括以下步驟：(a1)針對S中的每一個觀測點si，估計si對應的實際位置集合Ni，這樣就得到了實際狀態集合和觀測狀態集合；(a2)估計生成概率，在Ni中的每一個點和si之間；(a3)估計轉移概率，在Ni中的每個點和Ni+1的每個點之間；(a4)求解序列S對應的最可能的實際位置序列，這個實際位置序列就是匹配后的路徑。

6.根據權利要求5所述的基于隱馬爾科夫模型的地圖匹配算法，其特征在于：根據觀測點和對應的實際位置的具體位置和下一個需要計算的點的實際位置，來推測他的狀態轉移矩陣A：d_t＝|||o_t-o_t+1||_greatcircle-||r_i-r_j||_route|；同時把所有計算出來的候選點和觀測到的點進行計算，可以得到觀測到的點實際位置在候選點中的概率矩陣B：。

7.根據權利要求6所述的基于隱馬爾科夫模型的地圖匹配算法，其特征在于：利用Viterbi算法，針對于得到的每一個狀態，最可能的路徑被稱為部分最優路徑，通過計算出來t-1時刻的部分最優路徑，然后利用這部分路徑，計算出來t時刻的部分最優路徑；以此類推，可以直到最后一個時刻也就是即計算的終點，得出出來全局最優路徑，得到最終軌跡的匹配結果。