導讀：道路匹配是地圖數據處理方面非?；A且重要的理論，特別是道路相關(guān)業(yè)務(wù)，一定避不開(kāi)道路匹配的應用，這也是業(yè)務(wù)中普遍會(huì )碰到的痛點(diǎn)。
本文屬于「漫話(huà)地圖」系列，我們將結合地圖數據業(yè)務(wù)的特點(diǎn)，持續介紹地圖行業(yè)一些有趣的知識點(diǎn)，希望能拋磚引玉，為大家帶來(lái)一定的啟思和裨益，歡迎長(cháng)期關(guān)注。
道路匹配定義及應用場(chǎng)景
定義
道路匹配是地圖匹配理論的子集，通俗講就是兩幅地圖A和B，在沒(méi)有唯一ID關(guān)聯(lián)的情況下，如何確定地圖A上的道路是B上一條道路的過(guò)程。如果做交通軌跡或者地圖數據融合方面的研究，那么就一定會(huì )遇到地圖匹配的問(wèn)題。
地圖匹配 Map Matching:不同條件下獲取同一物景的地圖之間的配準關(guān)系。
道路匹配是刨除了點(diǎn)和面狀匹配之外的線(xiàn)狀要素理論，道路的話(huà)就是路網(wǎng)，也是實(shí)際應用中研究最多、應用最廣的一部分。
利用路網(wǎng)數據，采用適當算法，將目標定位映射到實(shí)際道路上的過(guò)程，具體來(lái)說(shuō)道路匹配是：
地圖匹配理論的首要子集
針對矢量拓撲道路數據的匹配模式
異源道路數據融合的關(guān)鍵
導航定位精度改善的重要手段
應用
最常見(jiàn)的應用場(chǎng)景
道路匹配最直觀(guān)的應用就是地圖導航。手機自帶GPS的定位精度在10米上下，單車(chē)道的寬度一般是2-3米。實(shí)際上，手機GPS定位不足以精確判斷車(chē)輛行駛的實(shí)際道路。但大家會(huì )發(fā)現，通常情況下高德導航的道路定位都是很準確的，導航過(guò)程中地圖會(huì )知道用戶(hù)在某某道路而不是附近小區或者溝河中。
究其原因，用戶(hù)導航過(guò)程中，系統一直在計算GPS位置和導航路線(xiàn)&路網(wǎng)間的配準關(guān)系，從而進(jìn)行一定程度的糾偏，這也是提高定位精度的重要手段。
大家也會(huì )經(jīng)常發(fā)現同一手機第三方客戶(hù)API定位效果比高德地圖差了不少，刨除硬件因素，實(shí)際上這里有算法水平的差異。
空間距離和評價(jià)曲線(xiàn)相似性的一般方法
離散點(diǎn)集匹配
路網(wǎng)匹配的兩個(gè)方面應用：第一個(gè)是離散點(diǎn)集匹配，相對簡(jiǎn)單，隨機離散點(diǎn)沒(méi)有形狀和拓撲關(guān)系，用歐氏距離作吸附即可，典型應用如離散熱力圖。
曲線(xiàn)擬合
實(shí)際中更有應用價(jià)值的是曲線(xiàn)擬合匹配關(guān)系，比如軌跡和路網(wǎng)，GPS序列和導航路的相似性。
曲線(xiàn)信息更多，這方面比離散點(diǎn)集有更多的評價(jià)要素，也有更高的復雜度。評價(jià)曲線(xiàn)相似性的一般要素有長(cháng)度、形狀、曲率、拓撲關(guān)系、方向比如正向逆向、距離、屬性例如交通規則左轉右轉禁行等信息。
算法分類(lèi)
曲線(xiàn)匹配方法分類(lèi)
基于幾何信息的匹配算法考慮形狀、角度等常規要素，屬于早期的一些算法，實(shí)現最簡(jiǎn)單，準確度最低?；谕負湫畔⒌乃惴?，準確度比幾何方法大大提升，應用最廣?；诟怕暑A測的算法，實(shí)現比較困難，實(shí)際上應用不多。
目前有一些比較高級的算法理論，包括隱馬模型等等，在實(shí)際應用中準確度是相對最高的。
實(shí)時(shí)算法主要用于在線(xiàn)導航，時(shí)間和空間復雜度低，離線(xiàn)算法用于數據處理的離線(xiàn)計算，算法復雜，追求最高準確度。
空間距離
線(xiàn)要素的匹配，主要通過(guò)幾何、拓撲或語(yǔ)義相似度來(lái)進(jìn)行識別，其中通過(guò)空間距離來(lái)進(jìn)行要素匹配的常用方式有：
閔可夫斯基距離(Minkowski Distance)
歐氏距離(Euclidean Distance)
曼哈頓距離(Manhattan Distance)
切比雪夫距離(Chebyshev Distance)
漢明距離(Hamming distance)
杰卡德相似系數(Jaccard similarity coefficient)
豪斯多夫距離(Hausdorff Distance)
弗雷歇距離(Fréchet距離)
評價(jià)曲線(xiàn)相似性-弗雷歇距離
什么是弗雷歇距離?
Fréchet distance（弗雷歇距離）是法國數學(xué)家Maurice RenéFréchet在1906年提出的一種路徑空間相似形描述定義。
狗繩距離
弗雷歇距離通俗的講就是狗繩距離，人和狗之間有一條狗繩約束。主人走路徑A，狗走路徑B，各自走完這兩條路徑過(guò)程中所需要的最短狗繩長(cháng)度就是弗雷歇距離。
最大距離最小化
設定t是時(shí)間點(diǎn)，該時(shí)刻曲線(xiàn)A上的采樣點(diǎn)為A(t), 曲線(xiàn)B上采樣點(diǎn)為B(t)。如果使用歐氏距離，則容易定義d (A(t),B(t)) 。在每次采樣中t離散的遍歷區間[0,1]，得到該種采樣下的最大距離。弗雷歇距離就是使該最大距離最小化的采樣方式下的值。
K-WALK和弗雷歇排列
給定一個(gè)有n點(diǎn)的路鏈P=〈p1 , p2 , … , pn 〉，一個(gè)沿著(zhù)P的k步分割成為k個(gè)不相交的非空子集，稱(chēng)為K-WALK。
給定兩個(gè)路鏈A =〈a1 , …, am 〉, B =〈b1 , …, bn 〉，一個(gè)沿著(zhù)A和B的組合步(Paired Work)是A的k-walk {Ai}i =1 …k和一個(gè)沿著(zhù)B的k-walk {B i}i =1 …k 組成(1 ≤i ≤k) 。
鏈A和B間的離散Fréchet距離(discrete Fréchet distance)就是一個(gè)沿著(zhù)鏈A和B的組合步W={(Ai ,Bi)}的最小花費，這個(gè)組合步稱(chēng)為鏈A和B的Fréchet 排列(Fréchet alignment)，也稱(chēng)為最佳組合步。弗雷歇距離實(shí)際上就是不斷的遍歷計算，嘗試找出最佳組合步的過(guò)程。
利用平均弗雷歇距離評價(jià)曲線(xiàn)相似性
采用平均Fréchet距離代替離散Fréchet距離，因為前者是從頂點(diǎn)距離集合中選取的一個(gè)最大距離，易受到局部變形較大點(diǎn)的影響。
基于離散Fréchet距離識別曲線(xiàn)上點(diǎn)與點(diǎn)之間最短路徑的方法，平均Fréchet距離通過(guò)計算離散要素點(diǎn)集之間的最短距離的平均值，來(lái)度量線(xiàn)要素間的相似性。
全局算法
兩條曲線(xiàn)之間的匹配，研究的是1:1的關(guān)系，實(shí)際應用中GPS軌跡比較長(cháng)的時(shí)候面臨M:N全局擇優(yōu)的問(wèn)題。
進(jìn)行全局路線(xiàn)匹配時(shí)，需要考慮M:N的情況來(lái)確定整體路徑，代表性的算法是使用弗雷歇距離來(lái)衡量待匹配序列和候選路段序列的匹配度，并作為路段的權重，由此構建網(wǎng)絡(luò )圖，通過(guò)計算最短路徑得到最佳匹配結果。
最準確的匹配模型-隱式馬爾科夫模型HMM
除了弗雷歇距離外，再介紹一種高級算法，也是目前應用中準確度最高的一種算法(和最通用解決方案)—隱式馬爾科夫模型HMM。
20世紀60年代，Leonard E. Baum和其它作者在一系列的統計學(xué)論文中描述了隱式馬爾科夫模型。它最初的應用之一是語(yǔ)音識別，80年代成為信號處理的研究重點(diǎn)，現已成功用于故障診斷、行為識別、文字識別、自然語(yǔ)言處理以及生物信息等領(lǐng)域。
核心特征
隱式馬爾科夫模型五要素：2個(gè)狀態(tài)集合和3個(gè)概率矩陣，Viterbi算法。
隱含狀態(tài)S：馬爾科夫模型中實(shí)際所隱含的狀態(tài)，通常無(wú)法通過(guò)直接觀(guān)測得到，這些狀態(tài)之間滿(mǎn)足馬爾科夫性質(zhì)。
可觀(guān)測狀態(tài)O：通過(guò)直接觀(guān)測而得到的狀態(tài)，在隱式馬爾科夫模型中與隱含狀態(tài)相關(guān)聯(lián)。
狀態(tài)轉移概率矩陣A：描述隱式馬爾科夫模型中各個(gè)狀態(tài)之間的轉移概率。
觀(guān)測狀態(tài)概率矩陣B：表示在t時(shí)刻隱含狀態(tài)是Sj條件下，其可觀(guān)測狀態(tài)為Ok的概率。
初始狀態(tài)概率矩陣π：表示隱含狀態(tài)在初始時(shí)刻t=1的概率矩陣
維特比算法詳見(jiàn):
https://blog.csdn.net/xueyingxue001/article/details/52396494
開(kāi)源實(shí)現Graphhopper-mapmatching，Java實(shí)現的地圖匹配項目，作為開(kāi)源導航引擎graphhopper的子項目提供，最新實(shí)現用的是隱式馬爾科夫模型，GitHub地址：
https://github.com/graphhopper/map-matching
解決三類(lèi)問(wèn)題
路網(wǎng)匹配實(shí)際是一個(gè)解碼問(wèn)題，基于HMM的路網(wǎng)匹配算法是在一系列觀(guān)察的前提下，尋找最有可能產(chǎn)生這個(gè)觀(guān)察序列的隱含狀態(tài)序列。一系列GPS位置點(diǎn)集合是可觀(guān)測狀態(tài)，尋找最有可能產(chǎn)生位置點(diǎn)集合的路網(wǎng)隱藏序列。
基于隱馬爾科夫模型的路網(wǎng)匹配過(guò)程
衍生算法集合
其中STM算法，穩定健壯，實(shí)用性強，有成熟的研究和開(kāi)源實(shí)現。
ACM SIGSPATIAL Cup
2012年ACM SIGSPATIAL Cup是由ACM主辦的全球范圍內關(guān)于地圖匹配算法的科技競賽，競賽吸引了來(lái)自全球31支專(zhuān)業(yè)級的參賽隊伍。所有算法當中匹配準確率最高的兩個(gè)都是基于HMM的匹配算法。
道路匹配在業(yè)務(wù)中的應用
道路匹配在自動(dòng)化項目中的應用，包括交通軌跡擬合度計算和道路自動(dòng)識別等。
更多場(chǎng)景，比如異源數據融合、軌跡數據挖掘、交通數據分析、城市規劃等領(lǐng)域，道路匹配都有廣泛的應用前景。
聯(lián)系客服
