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

有效

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

本發(fā)明涉及一種基于隱馬爾可夫模型的移動(dòng)用戶軌跡地圖匹配方法，屬于移動(dòng)通信及計(jì)算機(jī)應(yīng)用技術(shù)域。該方法首先建立基站與區(qū)域路網(wǎng)信息數(shù)據(jù)庫(kù)；然后根據(jù)基站位置借助馮洛諾伊圖實(shí)現(xiàn)對(duì)基站定位軌跡的插值填充，完成匹配之前的數(shù)據(jù)預(yù)處理工作；最后基于HMM建立地圖匹配模型，并使用維特比算法求解，得到出行行為對(duì)應(yīng)的路網(wǎng)軌跡信息。本發(fā)明充分利用了移動(dòng)數(shù)據(jù)中的時(shí)空位置信息與道路拓?fù)浣Y(jié)構(gòu)信息，構(gòu)建基于隱馬爾可夫模型的地圖匹配算法，將與實(shí)際位置有偏差的定位點(diǎn)投影到位置對(duì)應(yīng)路段上，從而矯正定位誤差，提高定位精度。為基于移動(dòng)位置數(shù)據(jù)展開(kāi)的出行方式和出行目的識(shí)別等相關(guān)研究奠定了重要基礎(chǔ)。

技術(shù)領(lǐng)域

本發(fā)明屬于移動(dòng)通信以及計(jì)算機(jī)應(yīng)用技術(shù)領(lǐng)域，涉及一種基于隱馬爾可夫模型的移動(dòng)用戶軌跡地圖匹配方法。

背景技術(shù)

隨著智能手機(jī)、智能行車記錄儀等終端的應(yīng)用和普及，通信運(yùn)營(yíng)商作為數(shù)據(jù)管道，積累了海量的移動(dòng)信令數(shù)據(jù)。從移動(dòng)信令數(shù)據(jù)中解析出來(lái)的位置信息則為城市計(jì)算領(lǐng)域中智能交通系統(tǒng)(Intelligent Traffic Systems，ITS)的應(yīng)用提供了詳實(shí)的數(shù)據(jù)支撐。由移動(dòng)數(shù)據(jù)構(gòu)成的軌跡信息是用戶運(yùn)動(dòng)行為的全時(shí)空采樣，從中可以分離出用戶駐留點(diǎn)和出行行為。出行行為對(duì)應(yīng)的移動(dòng)軌跡需要借助地圖匹配(Map Matching，MM)技術(shù)匹配到城市路網(wǎng)數(shù)據(jù)中。

地圖匹配技術(shù)是一種定位糾錯(cuò)技術(shù)，其核心思想是將定位軌跡和電子地圖中的路網(wǎng)信息按照一定的邏輯進(jìn)行比較和匹配，將與實(shí)際位置有偏差的定位點(diǎn)投影到位置對(duì)應(yīng)路段上，從而矯正定位誤差，提高定位精度。當(dāng)前地圖匹配算法研究多基于采樣密度高、定位精度高、包含運(yùn)動(dòng)方向等信息的GPS(Global Positioning System)數(shù)據(jù)或浮動(dòng)車數(shù)據(jù)(Floating Car Data， FCD)。適用于GPS數(shù)據(jù)或浮動(dòng)車數(shù)據(jù)的地圖匹配算法主要有以下幾類：模糊邏輯模型(Fuzzy Logic Model，F(xiàn)LM)、權(quán)重模型(Weight Model，WM)、隱馬爾可夫模型(Hidden Markov Model， HMM)、拓?fù)淠Ｐ?Topological Model，TM)和先進(jìn)模型(Advanced Model，AM)。具體地， FLM方法利用模糊邏輯理論，將速度、方向、歷史軌跡等因素分層量化，得到路網(wǎng)匹配結(jié)果，但在復(fù)雜的城市道路網(wǎng)絡(luò)中匹配精度低且算法含有多個(gè)權(quán)重參數(shù)，算法魯棒性差；WM方法通過(guò)對(duì)速度、方向、距離等因素分配不同權(quán)重并建立各個(gè)道路的權(quán)重閾值，超過(guò)該閾值則認(rèn)為匹配成功，該類方法屬于專家系統(tǒng)模型，其匹配結(jié)果嚴(yán)重依賴權(quán)重與閾值大小；HMM方法將用戶定位軌跡作為觀測(cè)序列，實(shí)際路網(wǎng)軌跡作為隱狀態(tài)序列，考量運(yùn)動(dòng)速度、方向、與候選路段的距離等因素，其優(yōu)點(diǎn)在于對(duì)噪聲數(shù)據(jù)不敏感，但現(xiàn)有算法在低采樣速率與低精度的定位的數(shù)據(jù)中匹配效果并不理想；TM方法利用路網(wǎng)信息中的幾何形狀、連通性和連續(xù)性完成地圖匹配，這類方法對(duì)軌跡的幾何形狀有較高要求，不適用于低采樣速率的定位數(shù)據(jù)；AM 方法包括卡爾曼濾波、粒子濾波、條件隨機(jī)場(chǎng)模型等，這些模型的精確性較高，但是計(jì)算成本通常很高，如在卡爾曼濾波模型中涉及大量迭代的卡爾曼增益計(jì)算，已有研究表明先進(jìn)模型在實(shí)現(xiàn)簡(jiǎn)單性和性能方面存在一定的不足。

相比GPS數(shù)據(jù)或者浮動(dòng)車數(shù)據(jù)，移動(dòng)數(shù)據(jù)中的定位信息有如下特點(diǎn)：1)屬性信息簡(jiǎn)單，僅包含時(shí)間和位置信息；2)時(shí)空采樣率較低且采樣不均勻；3)各區(qū)域基站部署疏密程度不同，整體定位精度較低。當(dāng)前基于移動(dòng)數(shù)據(jù)的地圖匹配方法主要有三類：一是將定位數(shù)據(jù)與基站切換對(duì)數(shù)據(jù)庫(kù)進(jìn)行對(duì)比獲得用戶運(yùn)動(dòng)道路信息，但由于路網(wǎng)空間的復(fù)雜性以及用戶移動(dòng)路徑多樣性，建立和維護(hù)基站切換對(duì)數(shù)據(jù)庫(kù)比較困難；二是基于道路拓?fù)浣Y(jié)構(gòu)的匹配方法，但是在復(fù)雜道路區(qū)域中準(zhǔn)確率較低；三是針對(duì)基于GPS數(shù)據(jù)的地圖匹配算法的改進(jìn)，但現(xiàn)有研究在搜索區(qū)域的設(shè)置與發(fā)射概率的設(shè)置均沿用原算法，且使用場(chǎng)景多為區(qū)域內(nèi)簡(jiǎn)單路網(wǎng)環(huán)境。

因此，目前亟需一種能有效解決基于移動(dòng)數(shù)據(jù)的地圖匹配準(zhǔn)確率低的地圖匹配方法。

發(fā)明內(nèi)容