[發明專利]一種用于壓縮軌跡的地圖匹配方法

有效

• 申請號: 201910687636.0
• 申請日: 2019-07-29
• 公開（公告）號: CN110411450B
• 公開（公告）日: 2021-04-16
• 發明（設計）人: 林學練;姜家豪;馬帥;沃天宇
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G01C21/20
• 分類號: G01C21/20;G01C21/30;G01S19/42
• 代理公司: 北京中創陽光知識產權代理有限責任公司 11003
• 代理人: 尹振啟

本發明提出一種用于壓縮后軌跡的地圖匹配方法，具體包括以下步驟：步驟1，對于接收到的原始軌跡，使用在線軌跡壓縮算法進行壓縮，并在壓縮時統計輔助信息，所述輔助信息為原始軌跡在壓縮軌跡線段左右兩側的長度；步驟2，進行局部路徑恢復，所述路徑局部路徑基于行為圖進行行為權重估計，并進行最短路徑搜索，得到局部最優路徑；步驟3，基于所述局部路徑恢復計算出的局部最優路徑進行全局路徑解碼，得到整個軌跡序列找到最終的匹配結果。

技術領域

本發明涉及一種軌跡匹配方法，尤其涉及一種用于壓縮軌跡的地圖匹配方法。

背景技術

廣泛使用的GPS傳感器和移動設備收集了大量的軌跡數據。這些軌跡數據為基于位置的服務、城市交通流量分析、軌跡模式挖掘等應用提供了基礎，對于城市建設具有重要意義。然而，采集、傳輸和管理大量的軌跡數據為終端、網絡和服務器系統帶來了巨大的挑戰。首先，原始軌跡數據需要從終端設備上傳到服務器中，大量軌跡數據的上傳會造成網絡傳輸的壓力。其次，大量、冗余的原始軌跡數據，需要越來越大的存儲空間來進行存儲。最后，系統中存儲的大量軌跡數據又會增加查詢的計算量，降低查詢速度，影響系統體驗。

與此同時，軌跡上傳至服務器后，有時還需要將軌跡點匹配到路網上，以支持后續的基于位置的服務。在壓縮后的軌跡上進行地圖匹配，可以降低計算開銷，加快系統的響應速度。因此，我們需要針對壓縮后軌跡的行之有效的地圖匹配算法。然而，傳統的地圖匹配方法針對原始軌跡設計的，若直接將這些傳統方法應用于壓縮后的軌跡上，會造成匹配準確率的降低。究其原因，是壓縮軌跡有其自身不同于原始軌跡的特點，從而壓縮軌跡的地圖匹配與原始軌跡的地圖匹配有明顯的區別。首先，對軌跡進行壓縮后，軌跡變得更稀疏，在壓縮后的軌跡上進行地圖匹配固然可以減少需處理的數據量，進而減少執行時間，但是同時會對地圖匹配帶來困難。若按常規的地圖匹配方法進行匹配，將導致匹配準確率的顯著下降。其次，原始軌跡點到壓縮后的軌跡之間的距離在一個誤差界限之內。這是由軌跡壓縮算法的誤差有界要求保證的。這意味著壓縮軌跡具有特定的幾何特征，這些幾何信息可以用于輔助地圖匹配過程，從而提高匹配準確率。

發明內容

本發明提供一種用于壓縮后軌跡的地圖匹配方法，該系統基于隱馬爾科夫模型進行建模，并在路徑恢復和轉移概率的計算時考慮了壓縮軌跡的特點，以提高匹配準確率。具體包括以下步驟：步驟1，軌跡壓縮與輔助信息統計：對于接收到的原始軌跡，使用在線軌跡壓縮算法進行壓縮，并在壓縮時統計輔助信息，所述輔助信息為原始軌跡在壓縮軌跡線段左右兩側的長度L.L,L.R；步驟2，局部路徑恢復：用來在兩個相鄰軌跡點之間計算出一條局部最優路徑；步驟3，全局路徑解碼：基于局部路徑恢復計算出的局部最優路徑，為整個軌跡序列找到一條可能性最大的路徑，作為最終的匹配結果。本發明實施的流程圖如圖1所示。

附圖說明

圖1為本發明實施的流程圖；

圖2為本發明壓縮軌跡的地圖匹配方法示意圖；

圖3為本發明根據距離閾值提取子圖；

圖4為本發明的行為圖示例；

具體實施方式

為了使本發明的目的、技術方案及優點更加清楚明白，以下結合附圖及實施例，對本發明進行進一步詳細說明。應當理解，此處所描述的具體實施例僅僅用以解釋本發明，并不用于限定本發明。此外，下面所描述的本發明各個實施方式中所涉及到的技術特征只要彼此之間未構成沖突就可以相互組合。