高精度的地圖需要強(qiáng)大的地圖堆棧，提供路由、導(dǎo)航指令和ETA計算等服務(wù)。以往， Uber工程師使用各種反饋來識別地圖錯誤，例如，記錄和理解用戶反饋的機(jī)器學(xué)習(xí)模型，或通過評估地圖指標(biāo)來提高地圖精度。這次，Uber發(fā)布博客稱，Uber工程師構(gòu)建了CatchME系統(tǒng)。

CatchMapError（CatchME）是一個系統(tǒng)，可以通過驅(qū)動程序應(yīng)用程序中的匿名GPS跟蹤自動捕獲地圖數(shù)據(jù)中的錯誤。CatchME使用來自大型地理區(qū)域的數(shù)千萬次駕駛的匿名和聚合數(shù)據(jù)來捕獲地圖數(shù)據(jù)錯誤。通過CatchME，運營商可以快速識別并修復(fù)這些錯誤，從而在Uber平臺上實現(xiàn)更準(zhǔn)確的路線和改進(jìn)的駕駛員合作體驗。

圖1：左側(cè)地圖上缺少的路段導(dǎo)致7.6分鐘的ETA；右側(cè)的精確地圖顯著降低了ETA，為騎手和駕駛者提供了更好的體驗。

使用GPS識別地圖錯誤

CatchME的基本理念是Uber使用GPS追蹤反映地面實況。通過分析道路地圖匹配的異常，CatchME識別地圖與地面實況之間的差異。這些差異通常是由地圖數(shù)據(jù)錯誤引起的，可以通過更新地圖來解決。

CatchME的第一個挑戰(zhàn)是找出駕駛員的導(dǎo)航行為（由GPS軌跡記錄）是否與建議的地圖路線顯示不一致。CatchME，使用隱馬爾可夫模型（HMM）在地圖數(shù)據(jù)上捕捉GPS軌跡，從而報告預(yù)期路線和實際路線之間的差異。

在城市環(huán)境中，GPS軌跡并不完全準(zhǔn)確，因此無法得知平臺上車輛的確切位置。Uber工程師將車輛位置概率放入HMM中，維特比算法根據(jù)這些軌跡計算出車輛駛過的最可能的路段序列。有了這些信息，CatchME會報告此序列中的跟蹤異常，并突出顯示驅(qū)動程序行為與應(yīng)用程序建議路徑之間的差異。

下面的圖2描繪了GPS軌跡如何突出地圖數(shù)據(jù)中的不準(zhǔn)確性的示例。在這種情況下，舊金山金門公園的一條路線（a）顯示一名司機(jī)在第8大道和富爾頓街的交叉路口右轉(zhuǎn)，但司機(jī)偏離了（b）建議路線：

圖2（a）

圖2（b）

在圖2中，可以看見存在右轉(zhuǎn)限制，阻止平臺上的駕駛員向右轉(zhuǎn)。但是，根據(jù)駕駛員的行為，可以判斷這條信息可能不準(zhǔn)確。CatchME發(fā)現(xiàn)了平臺建議的導(dǎo)航和實際駕駛員行為之間的差異，使系統(tǒng)能夠識別并修復(fù)錯誤。

建議路線與GPS軌跡之間的差異不一定是由于地圖數(shù)據(jù)錯誤造成的。下面的圖3突出顯示了造成這些差異的另外兩個可能原因：（a）非法或危險的駕駛員行為；（b）噪聲GPS軌跡，即沒有提供足夠的具體數(shù)據(jù)來清楚地確定所采用的路線。

圖3（a）：一名駕駛員左轉(zhuǎn)非法，在此圖像中以紅點突出顯示。駕駛員行為導(dǎo)致實際行程路線與建議路線之間的差異。

圖3（b）：噪聲GPS信號導(dǎo)致實際行程路線與建議路線之間的差異。

CatchME錯誤檢測算法

如前所述，HMM是將GPS點與地圖數(shù)據(jù)連接起來的橋梁。從概念上講，維特比算法通過HMM中的所有可能狀態(tài)計算包括最可能狀態(tài)序列的路徑。理想情況下，此序列中的狀態(tài)轉(zhuǎn)換在所有可能狀態(tài)中應(yīng)具有高概率。但是，如果存在地圖數(shù)據(jù)錯誤，則此序列仍將包括具有低概率的狀態(tài)轉(zhuǎn)換。在這種情況下，我們將序列中的狀態(tài)之間的低概率稱為異常概率。

排放概率（EP）和轉(zhuǎn)移概率（TP）將首先放入HMM中。EP表示車輛在某些時刻出現(xiàn)在某些路段上的可能性。TP表示車輛在一定持續(xù)時間內(nèi)從一個路段移動到另一個路段的可能性。因此，對于附近具有m個路段的一個GPS點，將存在m個EP，其表示每個路段上的該GPS軌跡的可能性。對于GPS點G1，其中有米附近的部分，和G2，其中有?鄰近段，有m*n個TP。這些概率在HMM中，維特比算法從中獲取具有最大概率的狀態(tài)序列，該概率最可能代表車輛正在移動的路段。

圖4

上面的圖4顯示出了用于計算某個路段上的GPS點的EP所考慮的因素。公式概述如下：

GPS點與路段上的捕捉點之間的半徑距離在哪里。EP表示如果車輛實際上在路段上，GPS將被觀察的可能性。（在MicrosoftResearch論文中了解有關(guān)發(fā)射概率的更多信息，通過噪聲和稀疏性匹配隱藏馬爾可夫地圖）。

圖5：通過在其捕捉點S1到S2之間創(chuàng)建路線并測量該路線的距離來計算從G1到G2的轉(zhuǎn)換概率。

圖5顯示出了用于計算關(guān)于一個點的GPS轉(zhuǎn)移概率考慮到的因素上的特定段到另一GPS點上的特定段，使用下面的公式計算：

是兩個GPS點的半徑距離與兩個與GPS點相關(guān)聯(lián)的捕捉點之間的可路由距離之間的差值的絕對值。當(dāng)發(fā)射GPS位置時車輛穿過這兩個部分的可能性小于其他部分。

在該計算中，EP和TP形成矩陣。維特比以最大概率獲取全球最佳路段序列，這些概率最有可能是車輛正在行駛的路線。下面的圖6示出了G1，G2和G3是GPS點的示例，S1到S7是段，綠色圓圈是發(fā)射概率，黑色箭頭是轉(zhuǎn)換概率。運行維特比算法后，得到路段序列S4，S3和S1，以及G1，G2和G3的表示繼續(xù)這些序列。

圖6：在該示例中，維特比算法通過使用HMM來計算道路過渡S4，S3和S1的最可能的分段序列。這三個段代表GPSG1，G2和G3。

圖7：路段A和B之間存在缺失段。但是，由綠色和藍(lán)色點標(biāo)記的GPS點顯示駕駛員穿過A到B。從GPS點G1到GPS點G2的轉(zhuǎn)換概率異常低，表明G1和G2周圍可能存在地圖錯誤。

通常，維特比算法從HMM中拾取的路段序列表示車輛經(jīng)過的路段。但是，如果地圖數(shù)據(jù)有錯誤，例如圖7中描繪的段，則該序列將包括異常低的轉(zhuǎn)移概率，表明車輛無法在段上行進(jìn)或在地圖數(shù)據(jù)上下文中的某些段之間轉(zhuǎn)換。

CatchME通過使用綠色和藍(lán)色顏色可視化可疑的GPS點來識別GPS軌跡之間的差異，這些顏色指示給定路線上的異常過渡（圖7）。在這些情況下，操作員可以快速找到該區(qū)域并修復(fù)這些錯誤（圖2）。

縮放準(zhǔn)確性

由于建議路線和現(xiàn)實路線之間的差異不一定表示地圖數(shù)據(jù)中的錯誤，因此捕捉給定路線上的錯誤不能僅依賴于一次駕駛的結(jié)果。相反，CatchME使用來自大地理區(qū)域的數(shù)千萬次駕駛的匿名和聚合數(shù)據(jù)來捕獲地圖數(shù)據(jù)錯誤。

CatchME采用分而治之（D＆C）方法在不同行程中橫向擴(kuò)展。D＆C的主要目標(biāo)是對GPS軌跡和地圖數(shù)據(jù)進(jìn)行分片，以便可以并行處理它們。分片基于跟蹤和地圖數(shù)據(jù)的S2單元�？缭蕉鄠�S2細(xì)胞的跡線被分成多個子跡線，每個子跡線由單個S2細(xì)胞完全包含。檢測在不同的S2細(xì)胞中平行獨立運行。下面的圖8說明了這種高級分片。為了保證每個S2單元包括可用于檢測錯誤的所有地圖數(shù)據(jù)，我們通常擴(kuò)展S2單元邊界，以便所有地圖數(shù)據(jù)及其相關(guān)的GPS點都在范圍內(nèi)。

圖8：使用S2單元對GPS軌跡和地圖數(shù)據(jù)進(jìn)行分片使我們能夠大規(guī)模地收集有關(guān)地圖數(shù)據(jù)錯誤的見解。

但是，使用靜態(tài)S2單元分區(qū)行程和映射數(shù)據(jù)有時無法提供足夠的并發(fā)性。例如，舊金山國際機(jī)場（SFO）等某些地區(qū)的S2小區(qū)的駕駛次數(shù)遠(yuǎn)遠(yuǎn)多于農(nóng)村地區(qū)相同水平的S2小區(qū)。

為了進(jìn)一步提高CatchME的性能，為每個高密度單元制作了多個副本。每個副本具有相同的地圖數(shù)據(jù)，但是具有不同且均勻分布的行程集，如下面的圖9所示：

圖9：一個S2單元中的跡線被劃分為具有相同地圖數(shù)據(jù)的兩個S2單元。

這種方法消除了由高密度單元引起的瓶頸，并且導(dǎo)致更準(zhǔn)確的結(jié)果，因為每個單元仍然足夠大，以包含用于地圖匹配和錯誤檢測的完整地圖數(shù)據(jù)上下文和GPS點。

過濾誤報

作為縮放CatchME的結(jié)果，足夠的差異信號（異常概率）提供了用于評估數(shù)據(jù)錯誤的統(tǒng)計視圖。聚合來自大量駕駛的結(jié)果背后的哲學(xué)是，如果看到在駕駛報告的給定地點的異常概率的一致性，這種差異的根本原因更可能是地圖數(shù)據(jù)錯誤而不是非法駕駛行為或噪聲GPS信號。

由于CatchME已經(jīng)確定了位于具有16級大�。⊿2小區(qū)統(tǒng)計）的某些S2小區(qū)中的GPS點之間的異常概率方面的差異，平均大小為19，793平方米，因此CatchME將每個S2小區(qū)視為基本錯誤單元。通過聚合這些單元，CatchME可以確定哪些錯誤更有可能影響驅(qū)動程序合作伙伴應(yīng)用程序的用戶體驗。

如圖3（b）所示，差異不一定是錯誤。CatchME連接GPS點，其中視差信號（或異常轉(zhuǎn)移概率）作為多邊形鏈存在（通常該多邊形鏈包括大約40個GPS點）。如果此鏈的幾何無效，CatchME將忽略此錯誤信號。CatchME還觀察到一定數(shù)量的錯誤警報，這些錯誤警報是由于下面的圖10所示的GPS軌跡偏移引起的，其中GPS軌跡穿過建筑物而不是靠近道路移動。如果這些GPS點跨越多個物理建筑大于某個閾值，CatchME將忽略這種差異。

圖10：由黃點動畫顯示的GPS跟蹤顯示GPS跟蹤移位。CatchME忽略了這種情況，即使它引發(fā)了視差信號。

更好的地圖，更好的用戶體驗

CatchME的結(jié)果已經(jīng)證明了一種非常有前景的方法。在推出后的前三個月內(nèi)，CatchME檢測到超過28，000個地圖錯誤。在Uber的地圖上糾正這些錯誤大大提高了駕駛ETA，導(dǎo)航和用戶體驗的準(zhǔn)確性。

未來，Uber計劃通過增強(qiáng)算法和利用衛(wèi)星圖像等其他證據(jù)來進(jìn)一步提高CatchME的精度。結(jié)合客戶報告的地圖錯誤，CatchME發(fā)現(xiàn)的地圖錯誤將為駕駛員提供更好的體驗。

參考資料：

[1] https://eng.uber.com/mapping-accuracy-with-catchme/

[2] Newson P , Krumm J . [ACM Press the 17th ACMSIGSPATIAL International Conference - Seattle, Washington(2009.11.04-2009.11.06)] Proceedings of the 17th ACM SIGSPATIAL InternationalConference on Advances in Geographic Information Systems - GIS "09 -Hidden Markov map matching through noise and sparseness[J]. 2009:336.