[發(fā)明專利]車輛匹配方法和裝置、計算設備以及計算機可讀存儲介質

有效

• 申請?zhí)枺?/td>: 202110103464.5
• 申請日: 2021-01-26
• 公開（公告）號: CN112685531B
• 公開（公告）日: 2021-12-03
• 發(fā)明（設計）人: 王魯許;廖正中
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06F16/245;G06Q10/04
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 孫之剛;陳嵐

本公開提供了一種車輛匹配方法，用于將車輛匹配到地圖中的地圖線路。該車輛匹配方法基于隱馬爾科夫模型和動態(tài)規(guī)劃，能夠利用站點匹配、名稱匹配、實際線路映射關系等對觀察概率和轉移概率進行調整，并且基于調整后的觀察概率和轉移概率將車輛匹配到對應的地圖線路。該車輛匹配方法不僅提高了匹配正確率，而且還能夠區(qū)分車輛的諸如區(qū)間線路、快車線路之類的復雜線路。此外，該車輛匹配方法還降低了對數據提供商的數據依賴，增大了對不同數據提供商的數據的兼容性。

技術領域

本公開涉及計算機技術領域，具體地，涉及一種基于隱馬爾科夫模型的用于將車輛匹配到地圖中的地圖線路的車輛匹配方法和裝置、計算設備以及計算機可讀存儲介質。

背景技術

隨著互聯網的普及和網絡技術的高速發(fā)展，地圖服務已經非常深入地影響著人們的日常出行。線路匹配技術作為地圖服務的重要支撐技術，實現了車輛軌跡與電子地圖的地圖線路之間的關聯，進而能夠為用戶的交通出行提供諸如路線規(guī)劃以及導航等服務。

現有的車輛軌跡到電子地圖的地圖線路的匹配方法主要包括以下幾種：利用名稱進行匹配；利用網格法進行車輛軌跡到地圖線路的匹配；利用離散Frechet距離進行車輛軌跡到地圖線路的匹配。然而，現有的這些方法各自存在不足。

對于利用名稱進行匹配的方法而言，一方面僅依靠名稱來確定關聯關系會導致匹配率低下，另一方面該方法嚴重依賴數據提供商提供的靜態(tài)線路的站點序列數據，如果缺乏該站點序列數據，則該方法無法使用。此外，利用名稱進行匹配還需要數據提供商提供的靜態(tài)線路和運行線路之間存在穩(wěn)定的一一對應關系，否則匹配結果無法應用。因此，利用名稱進行匹配的匹配正確率低，可用性、普適性不強。

對于利用網格法進行車輛軌跡到地圖線路的方法而言，由于網格法本身的算法是基于面積投影的方式，因此只能從全部GPS軌跡點覆蓋的區(qū)域來匹配可能的線路，這可能導致難以區(qū)分復雜線路。因此，利用網格法進行車輛軌跡到地圖線路的匹配存在匹配正確率和車輛召回率低下的問題。

對于利用離散Frechet距離進行車輛軌跡到地圖線路的方法而言，由于需要計算GPS軌跡點與所有線路形狀點的Frechet距離，因此計算復雜度高，計算量大。而且，由于計算的是GPS軌跡點到線路形狀點的最短距離，所以該方法對GPS軌跡點的精度要求很高。

發(fā)明內容

有鑒于此，本公開提出了一種車輛匹配方法和裝置，期望克服上面提到的部分或全部缺陷以及其它可能的缺陷。

根據本公開的一個方面，提供了一種車輛匹配方法，用于將車輛匹配到地圖中的地圖線路，其中地圖包括至少一條地圖線路，各地圖線路包括多個站點和多個線路段，車輛匹配方法包括：獲取車輛的包括軌跡點序列的車輛軌跡數據；確定地圖中與每一個軌跡點對應的至少一條候選線路段；生成每一個軌跡點的各候選線路段的第一觀察概率；生成每一個軌跡點的各候選線路段的站點匹配調整系數；生成每一個軌跡點的各候選線路段的第二觀察概率，其中第二觀察概率等于第一觀察概率乘以站點匹配調整系數；生成每一個軌跡點的各候選線路段分別到下一個軌跡點的各候選線路段的轉移概率；基于全部軌跡點的候選線路段的第二觀察概率和轉移概率確定最優(yōu)線路段集合，最優(yōu)線路段集合具有全局最大概率；以及，基于最優(yōu)線路段集合確定地圖中與車輛軌跡數據對應的地圖線路。

在本公開的一些實施例中，該車輛匹配方法，還包括：將地圖劃分為M×N個網格，其中，M和N都是大于0的整數，并且每個網格具有對應的網格索引編號；將地圖中每一條地圖線路的各線路段投影到M×N個網格中，并與對應網格的網格索引編號關聯。

在本公開的一些實施例中，確定地圖中與每一個軌跡點對應的至少一條候選線路段包括：將一個軌跡點投影到M×N個網格中；基于一個軌跡點被投影到其中的網格的網格索引編號，確定由a×b個網格構成的候選區(qū)域，其中，a為大于0且小于等于M的整數，b為大于0且小于等于N的整數；以及基于候選區(qū)域的網格的網格索引編號確定相關聯的線路段，并且將相關聯的線路段確定為一個軌跡點的候選線路段。