[發明專利]一種基于隱馬爾可夫模型的移動用戶軌跡地圖匹配方法

有效

• 申請號: 202010129640.8
• 申請日: 2020-02-28
• 公開（公告）號: CN111343585B
• 公開（公告）日: 2021-11-02
• 發明（設計）人: 許國良;王超;張軒;李萬林;雒江濤;易燕
• 申請（專利權）人: 重慶郵電大學
• 主分類號: H04W4/029
• 分類號: H04W4/029;G06F16/29;G06K9/62
• 代理公司: 北京同恒源知識產權代理有限公司 11275
• 代理人: 趙榮之

1.一種基于隱馬爾可夫模型的移動用戶軌跡地圖匹配方法，其特征在于，該方法包括以下步驟：

S1：根據移動數據建立基站與路網信息數據庫，其中移動數據包括用戶軌跡數據和基站位置數據；

S2：通過插值法對稀疏定位軌跡進行填充；

S3：考慮城市路網的復雜性以及匹配時的計算成本，根據馮洛諾伊圖制定候選路段搜索區域并計算候選路段集合，縮小隱狀態空間集合的大小；

制定候選路段搜索區域并計算候選路段集合的具體步驟為：

S31：根據定位點Tr_n的經緯度信息確定該定位點的基站編號；

S32：根據基站與路網信息數據庫獲取當前基站以及相鄰基站的編號集合Bs；

S33：生成一個空的候選路段集合Ce_n；

S34：遍歷基站編號集合Bs中的各個基站，借助基站與路網信息數據庫查詢基站覆蓋區域內道路編號，若候選路段集合Ce_n不包含某道路編號則將該道路加入集合Ce_n中；

S35：最終得到候選路段集合為候選路段；

S4：考慮定位點與候選路段的大圓距離和候選路段在搜索區域內的長度，計算隱馬爾可夫模型發射概率；

S5：考慮匹配前后軌跡相似性、當前道路與候選道路之間的連通性以及道路中存在的單向行駛的行車限制，計算隱馬爾可夫模型轉移概率；

隱馬爾可夫模型發射概率由兩部分構成，具體計算公式表示為：

其中，Tr_n為定位點，為候選路段，σ表示定位數據的標準差，||Tr_n+1-Tr_n||_GC表示定位點Tr_n與Tr_n+1的大圓距離，表示在定位點Tr_n對應的搜索區域內所有路段長度的最大值，表示候選路段在搜索區域內的長度；

隱馬爾可夫模型轉移概率由三部分構成，具體計算公式表示為：

其中，θ表示軌跡Tr_nTr_n+1與對應的候選道路Ceⁱ的夾角，矩陣元素表示候選道路Ceⁱ和Ce^j之間的連通性，||Tr_n+1-Tr_n||_GC表示定位點Tr_n與Tr_n+1的大圓距離，表示投影點與之間的最短路徑長度；

S6：將地圖匹配問題轉換為隱馬爾可夫模型(Hidden Markov Model，HMM)中的預測問題，并根據動態規劃的思想，利用維特比算法求解，得到出行行為對應的路網軌跡信息；

維特比算法遞推公式為：

其中，初始化π表示初始概率，而ψ₁初始化為0；

利用維特比算法遞推公式遞推得到候選路徑的最大概率，終點對應的匹配路徑為然后算法從終點回溯到起點，記錄每個時刻的回溯路徑最終得到最優匹配路徑

2.根據權利要求1所述的一種基于隱馬爾可夫模型的移動用戶軌跡地圖匹配方法，其特征在于，所述步驟S1中，建立基站與路網信息數據庫的具體方法為：利用地圖工具，以每個基站位置為中心，借助馮洛諾伊圖生成各自的覆蓋區域，并結合下載自OpenStreetMap的路網數據，建立基站與路網信息的匹配關系；其中，建立的數據庫中包括：基站編號、基站位置、基站覆蓋區域頂點列表、區域內道路編號、相鄰基站編號。

3.根據權利要求1所述的一種基于隱馬爾可夫模型的移動用戶軌跡地圖匹配方法，其特征在于，所述步驟S2中，插值法對稀疏定位軌跡進行填充的具體步驟為：

S21：借助建立的基站與路網信息數據庫，根據全量基站信息繪制馮洛諾伊圖；

S22：連接原軌跡中時間相鄰的兩定位點P_i、P_j，記為線段P_iP_j，生成以線段P_iP_j為對角線的矩形緩沖區域；

S23：判斷線段P_iP_j與緩沖區域內基站對應多邊形之間的拓撲關系；

S24：順次提取與線段P_iP_j拓撲關系為相交的多邊形內基站的位置信息，作為補充位置信息；

S25：時間均等地將提取出的補充位置信息內插到原軌跡序列中，得到填充后的軌跡數據。