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

有效

• 申請(qǐng)?zhí)枺?/td>: 202010129640.8
• 申請(qǐng)日: 2020-02-28
• 公開（公告）號(hào): CN111343585B
• 公開（公告）日: 2021-11-02
• 發(fā)明（設(shè)計(jì)）人: 許國(guó)良;王超;張軒;李萬林;雒江濤;易燕
• 申請(qǐng)（專利權(quán)）人: 重慶郵電大學(xué)
• 主分類號(hào): H04W4/029
• 分類號(hào): H04W4/029;G06F16/29;G06K9/62
• 代理公司: 北京同恒源知識(shí)產(chǎn)權(quán)代理有限公司 11275
• 代理人: 趙榮之

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

S1：根據(jù)移動(dòng)數(shù)據(jù)建立基站與路網(wǎng)信息數(shù)據(jù)庫，其中移動(dòng)數(shù)據(jù)包括用戶軌跡數(shù)據(jù)和基站位置數(shù)據(jù)；

S2：通過插值法對(duì)稀疏定位軌跡進(jìn)行填充；

S3：考慮城市路網(wǎng)的復(fù)雜性以及匹配時(shí)的計(jì)算成本，根據(jù)馮洛諾伊圖制定候選路段搜索區(qū)域并計(jì)算候選路段集合，縮小隱狀態(tài)空間集合的大小；

制定候選路段搜索區(qū)域并計(jì)算候選路段集合的具體步驟為：

S31：根據(jù)定位點(diǎn)Tr_n的經(jīng)緯度信息確定該定位點(diǎn)的基站編號(hào)；

S32：根據(jù)基站與路網(wǎng)信息數(shù)據(jù)庫獲取當(dāng)前基站以及相鄰基站的編號(hào)集合Bs；

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

S34：遍歷基站編號(hào)集合Bs中的各個(gè)基站，借助基站與路網(wǎng)信息數(shù)據(jù)庫查詢基站覆蓋區(qū)域內(nèi)道路編號(hào)，若候選路段集合Ce_n不包含某道路編號(hào)則將該道路加入集合Ce_n中；

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

S4：考慮定位點(diǎn)與候選路段的大圓距離和候選路段在搜索區(qū)域內(nèi)的長(zhǎng)度，計(jì)算隱馬爾可夫模型發(fā)射概率；

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

隱馬爾可夫模型發(fā)射概率由兩部分構(gòu)成，具體計(jì)算公式表示為：

其中，Tr_n為定位點(diǎn)，為候選路段，σ表示定位數(shù)據(jù)的標(biāo)準(zhǔn)差，||Tr_n+1-Tr_n||_GC表示定位點(diǎn)Tr_n與Tr_n+1的大圓距離，表示在定位點(diǎn)Tr_n對(duì)應(yīng)的搜索區(qū)域內(nèi)所有路段長(zhǎng)度的最大值，表示候選路段在搜索區(qū)域內(nèi)的長(zhǎng)度；

隱馬爾可夫模型轉(zhuǎn)移概率由三部分構(gòu)成，具體計(jì)算公式表示為：

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

S6：將地圖匹配問題轉(zhuǎn)換為隱馬爾可夫模型(Hidden Markov Model，HMM)中的預(yù)測(cè)問題，并根據(jù)動(dòng)態(tài)規(guī)劃的思想，利用維特比算法求解，得到出行行為對(duì)應(yīng)的路網(wǎng)軌跡信息；

維特比算法遞推公式為：

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

利用維特比算法遞推公式遞推得到候選路徑的最大概率，終點(diǎn)對(duì)應(yīng)的匹配路徑為然后算法從終點(diǎn)回溯到起點(diǎn)，記錄每個(gè)時(shí)刻的回溯路徑最終得到最優(yōu)匹配路徑

2.根據(jù)權(quán)利要求1所述的一種基于隱馬爾可夫模型的移動(dòng)用戶軌跡地圖匹配方法，其特征在于，所述步驟S1中，建立基站與路網(wǎng)信息數(shù)據(jù)庫的具體方法為：利用地圖工具，以每個(gè)基站位置為中心，借助馮洛諾伊圖生成各自的覆蓋區(qū)域，并結(jié)合下載自O(shè)penStreetMap的路網(wǎng)數(shù)據(jù)，建立基站與路網(wǎng)信息的匹配關(guān)系；其中，建立的數(shù)據(jù)庫中包括：基站編號(hào)、基站位置、基站覆蓋區(qū)域頂點(diǎn)列表、區(qū)域內(nèi)道路編號(hào)、相鄰基站編號(hào)。

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

S21：借助建立的基站與路網(wǎng)信息數(shù)據(jù)庫，根據(jù)全量基站信息繪制馮洛諾伊圖；

S22：連接原軌跡中時(shí)間相鄰的兩定位點(diǎn)P_i、P_j，記為線段P_iP_j，生成以線段P_iP_j為對(duì)角線的矩形緩沖區(qū)域；

S23：判斷線段P_iP_j與緩沖區(qū)域內(nèi)基站對(duì)應(yīng)多邊形之間的拓?fù)潢P(guān)系；

S24：順次提取與線段P_iP_j拓?fù)潢P(guān)系為相交的多邊形內(nèi)基站的位置信息，作為補(bǔ)充位置信息；

S25：時(shí)間均等地將提取出的補(bǔ)充位置信息內(nèi)插到原軌跡序列中，得到填充后的軌跡數(shù)據(jù)。