滴滴導航地圖標注是滴滴出行旗下基于豐富的交通大數(shù)據(jù)和領(lǐng)先的算法策略，面向網(wǎng)約車及自駕場景而打造的一款技術(shù)領(lǐng)先的地圖產(chǎn)品。伴隨著海量網(wǎng)約車每日8小時+的導航使用，產(chǎn)品積累了大量的反饋并持續(xù)優(yōu)化打磨。在這個過程中，為了給用戶帶來更好的地圖導航體驗，團隊一直在積極探索技術(shù)上的突破和實踐，并取得了一定的成果。今天，我們將會對其中的MJO三維全景導航（行業(yè)唯一）、導航主輔路偏航識別及深度學習在端上抓路應(yīng)用這三個技術(shù)點給大家展開講解。

1. MJO三維全景導航

▍
1.1 應(yīng)用背景
對于絕大多數(shù)駕駛者使用2D導航地圖，都會出現(xiàn)立交上認錯路口，上錯過匝道，不知何時該并線的問題。路口圖形誘導的出現(xiàn)，一定程度上緩解了路口偏航的問題。業(yè)內(nèi)通俗幾種做法，如下圖：

矢量大圖：基于2d道路屬性制作，算法驅(qū)動可以上量。

街景大圖：路口和街景圖像做掛接，然后疊加引導箭頭。依賴街景采集成本巨大。

衛(wèi)星大圖：路口真實但只有2D視角。
上述所有方案都只能靜態(tài)展示，而且不能精確區(qū)分車道。滴滴地圖中的MJO導航技術(shù)，通過加入與實景圖同級別的精細場景模型，準確表達復(fù)雜橋區(qū)的層次穿越關(guān)系。極大地降低了讀圖成本。

三維全景導航的技術(shù)難點在于模型復(fù)雜度高，數(shù)據(jù)量較大，相比2D導航地圖需要更多的CPU和GPU資源支持。為了在更廣泛的設(shè)備上實現(xiàn)該功能，需要大幅優(yōu)化資源的內(nèi)存、CPU及GPU消耗。

▍
1.2 數(shù)據(jù)壓縮

較大的模型尺寸帶來了網(wǎng)絡(luò)傳輸?shù)膲毫?，對?shù)據(jù)壓縮提出了較高的要求。數(shù)據(jù)全國總量高達41G，無法適應(yīng)移動端的內(nèi)存需求。性能攻堅階段，團隊融合了多種壓縮技術(shù)進行優(yōu)化：

紋理壓縮

提取共享資源

模型壓縮

格式二進制轉(zhuǎn)換

次要模型過濾

▍
1.3 Metal/Vulkan技術(shù)

滴滴地圖標注渲染引擎引入了下一代的圖形API，Metal及Vulkan技術(shù)。蘋果宣稱Metal可以提供10倍于OpenGL的性能，而Vulkan則是由khronos組織提出的開放標準，可以支持Apple以外的平臺。對比傳統(tǒng)的OpenGL ES技術(shù)，Metal/Vulkan更加貼近底層硬件，可以更精確地控制GPU，有著更好的線程模型。
Metal和Vulkan可以支持更多的draw calls，非常適合應(yīng)用于MJO這種模型數(shù)量較多的場景。通過適配Metal/Vulkan，解決了渲染引擎中shared context的兼容問題，提高了多線程加載的性能，對整體性能和穩(wěn)定性都有了較大的提升。

▍
1.4 渲染性能優(yōu)化 由于模型數(shù)據(jù)量較大，數(shù)據(jù)加載耗時，使用傳統(tǒng)的加載方式會造成明顯的卡頓問題，影響用戶體驗。通過利用Metal/OpenGL ES/Vulkan的多線程技術(shù)，資源加載使用了獨立的加載線程。加載過程對渲染線程沒有直接影響，使程序更加流暢。渲染場景的管理采用了八叉樹技術(shù)，用于快速選取可見元素，降低渲染負載。對比順序遍歷的O（N）復(fù)雜度，八叉樹降到了O（logN）。

MJO模型粒度較細，一個橋區(qū)包含2000多個模型，如果直接進行渲染會造成draw call數(shù)量過多，每個draw call都會產(chǎn)生額外的消耗。通過材質(zhì)合并模型后，draw calls降低到40多個，大幅降低了渲染和內(nèi)存消耗。

▍
1.5 導航實現(xiàn)

MJO導航雖然提供了高精度的道路模型和車道級的導航線數(shù)據(jù)，但由于移動端設(shè)備并不包含高精度的定位設(shè)備，需要利用現(xiàn)有的2D導航邏輯，將GPS點映射到MJO的導航線上。具體步驟如下：

根據(jù)2D導航的link序列過濾出經(jīng)過MJO橋區(qū)的部分

綁路服務(wù)計算映射出的MJO link序列并拼裝MJO導航線

MJO導航線和GPS點傳入導航引擎，計算出MJO中的綁路點

MJO導航線傳入渲染引擎，經(jīng)過Bezier插值進行平滑處理并渲染

綁路點在導航線上進行投影得到3D高度，并插值成平滑移動的動畫進行渲染

其中平滑算法使用了Bezier插值，p1 p4是曲線端點，p2 p3用于控制形狀，t是插值參數(shù)。

導航線由多個點構(gòu)成，端點可以從導航線中直接得到。中間的2個控制點需要進行計算。這里的技術(shù)要點是保證連接兩段線的切向一致（C1連續(xù)），在平滑的同時保證曲率不要過分偏離端點。團隊通過優(yōu)化參數(shù)和算法，得到了比較滿意的效果。

▍
1.6 總結(jié)

MJO涉及了多種渲染及建模相關(guān)的技術(shù)，范圍廣難度高。團隊在有限的人力和時間預(yù)算條件下，攻克了多個技術(shù)難點，實現(xiàn)了一套完整的動畫誘導方案。極大地降低了駕駛過程的瞬時讀圖成本，有效地緩解了復(fù)雜路口的偏航問題。

2. 滴滴主輔路偏航識別的應(yīng)用實踐

偏航是車輛實際行駛路線偏離了原定規(guī)劃路線的行為，而偏航識別用以確定車輛是否偏航，對偏航重新規(guī)劃行駛路線。主輔路作為特殊的道路場景，其由于平行的特殊性，導致主輔路偏航較一般偏航更具有挑戰(zhàn)性。本文將介紹滴滴地圖標注在主輔路偏航識別上的一些探索和實踐。

▍
2.1 應(yīng)用背景
偏航是車輛實際行駛路線偏離了原定規(guī)劃路線的行為，如圖1所示，紅色的是規(guī)劃路線，帶偏航的點是車輛gps點，整體上來看車輛已經(jīng)偏離了規(guī)劃路線，則為偏航。

圖1 普通偏航場景

圖2 主輔路偏航場景

而主輔路偏航場景如圖2所示，車輛在圖中紅框路口處車輛由主路切換到了輔路，則為一次主輔路偏航。


▍
2.2 主輔路偏航識別難點
偏航識別作為典型的二分類問題，通常會使用有監(jiān)督學習的模型求解。由于主輔路的特殊性，有監(jiān)督學習的標簽就成為整個技術(shù)方案的難點。

圖3 主輔路
如圖3的，車輛在主輔路附近有一個偏移動作，但是單純從上很難辨別車輛是切換了個車道還是有主輔路切換，無法單純從上是無法獲得真值。因此，需要引入額外的信息，而滴滴擁有廣大上報的圖像數(shù)據(jù)就是一個很好的補充。
除了標簽這個核心問題外，還有一些主要問題：
GPS點漂移：GPS點受信號強弱等影響，會出現(xiàn)位置偏差。主輔路場景下，主輔路之間距離不會很遠，則GPS的位置偏差會更容易造成誤判。路網(wǎng)形狀偏差：地圖數(shù)據(jù)往往用有向線段表示客觀道路，但是數(shù)據(jù)探查錄入等原因，和客觀世界道路位置形狀會有偏差，給識別帶來難度。 為了解決以上問題，提升用戶主輔路偏航上的體驗，我們提出了一種基于圖像識別的主輔路偏航識別系統(tǒng)。

▍
2.3 技術(shù)方案
2.
3.1 整體方案設(shè)計

圖4 主輔路偏航識別整體方案
如圖4，主輔路偏航識別整體方案涉及到左側(cè)的離線模型訓練部分和在右側(cè)線預(yù)測部分，其中離線訓練主要包括：
機器標注邏輯根據(jù)和路網(wǎng)連通性進行標注的樣本。由于存在路網(wǎng)連通性的約束，因此標注結(jié)果準確率高，但是路型覆蓋會有局限

圖像標注邏輯
根據(jù)上報圖像識別車輛在行為（車輛在主路/在輔路，或序列模型識別主輔路切換動作），結(jié)合和路網(wǎng)數(shù)據(jù)生成樣本。因為不受路網(wǎng)形態(tài)約束，因此路型覆蓋會更全；但是由于需要對路面圖像進行圖像識別，依賴圖像識別的準確率，存儲和計算成本較高

模型訓練
將機器標注樣本和圖像標注樣本進行合并后進行訓練，由于圖像標注樣本成本更高，所以會對圖像樣本用一些上采樣方式。
在線預(yù)測部分就是標準的線上預(yù)測流程，不做過多贅述。

2.
3.2 機器標注邏輯
機器標注邏輯是根據(jù)和路網(wǎng)連通性進行標注的邏輯。如圖5所示，有拐入“東雙貝子墳路”，但是主路根據(jù)路網(wǎng)連通性是不可能拐入的，因此可以推斷在紅框路口處，車輛從主路切換到了輔路。通過路網(wǎng)連通性的規(guī)則能很容易的篩出這類樣本，且這類樣本準確性極高。

圖5 機器標注示例

圖6 機器標注無法標注的
但是機器標注邏輯的局限也很明顯，就是諸如圖6的，機器標注是無法確認紅框的主輔路區(qū)間內(nèi)車輛是開在主路或輔路的。以北京的為例，機器標注能處理的路口小于30%，如果僅使用這部分樣本進行訓練，會因樣本有偏導致效果不理想。

2.
3.3 圖像標注邏輯

滴滴地圖標注擁有上報的圖像數(shù)據(jù)，可以根據(jù)圖像識別行為（車輛在主路/在輔路，或主輔路切換動作），再結(jié)合和路網(wǎng)數(shù)據(jù)，生成圖像標注集合。

如上圖是一個圖像數(shù)據(jù)示例，序號表示其序列關(guān)系，由圖所示，車輛由輔路切換到了主路。
圖像識別使用了兩套邏輯：

單圖識別序列中對每張圖片進行識別，給出其分類結(jié)果，類別包括：高架上主路、高架下主路、高架下輔路、主路、輔路。然后根據(jù)序列的分類結(jié)果，只要有類別的連續(xù)性變化視為切換行為，如序列（主路、主路、輔路、輔路）就可以視為切換。序列識別根據(jù)圖片序列識別是否有主輔路切換動作。采用端到端的注意力與類別層級融合損失約束模型進行特征學習與計算；為了更好的利用序列的語義信息，將主輔路單圖特征集成到序列模型中，進行序列約束，識別序列結(jié)果。
序列模型準確率更高，但是對于圖像序列要求較高（比如時間間隔不能太長）；單圖識別的召回更高，但是在有遮擋或高架下場景表現(xiàn)不好。將兩個模型的結(jié)果進行融合，引入、路網(wǎng)數(shù)據(jù)得到最終的圖像標注結(jié)果。圖像標注結(jié)果的準確率在93%以上。 

2.
3.4 模型訓練

由于線上只能使用到和路網(wǎng)的數(shù)據(jù)，因此使用特征主要分為以下幾類：
點特征：GPS點的特征，包括坐標、速度、方向等道路（link）特征：包括道路屬性（國道等）、車道數(shù)、道路方向等點-link特征：包括點方向同道路方向角度差、點到道路的距離等序列特征：包括當前點同上一個點的角度差、距離差，以及累計角度變化等
同時，針對GPS點信號不準確漂移的情況，使用卡爾曼濾波對GPS點位移，減少個別點漂移對于模型的影響；針對整段漂移，使用Frechet距離衡量其形狀相似度，加入到特征中。針對路網(wǎng)形狀偏差，使用歷史統(tǒng)計的方式（熱力圖），對路網(wǎng)進行平移、彎曲等形狀變化。
偏航是典型的二分類問題，初版模型使用Xgboost快速上線，目前在進行Wide&Deep和LSTM等模型的嘗試。

2.
3.5 效果評估

隨機抽取了2000個上報的圖像數(shù)據(jù)，對經(jīng)過的主輔路路口進行人工標注其主輔路切換行為，為人工標注集。
同時，人工只根據(jù)信息進行判定行為，識別拐彎的準確率92%、召回率91%。形成這類問題的主要原因是估計漂移，如圖7的，人工如果只根據(jù)判斷，會認為車輛在路口由主路切換到輔路，但是根據(jù)圖像可以確認其一直在主路上。

圖7 人工誤判示例
模型在人工標注集上的識別拐彎的準確率88%、召回率89%，接近人工只根據(jù)的判定的準召，但是還有一定提升空間。

▍
2.4 總結(jié)

主輔路偏航作為偏航識別里的特殊類型，由于其平行的特殊性，給識別帶來了較大的挑戰(zhàn)。本文介紹了滴滴在主輔路偏航識別上的一些探索和實踐，借助滴滴的數(shù)據(jù)優(yōu)勢，建立了一套依賴圖像識別的主輔路偏航真值標注體系，并在最后主輔路偏航識別取得了預(yù)期的效果。



3. 深度學習在偏航引擎前端的探索和實踐

▍
3.1 導讀
導航作為地圖出行的核心場景，根據(jù)起終點、路線數(shù)據(jù)及路況信息為用戶定制出行方案。導航為用戶提供規(guī)劃路徑，但現(xiàn)實出行中充滿變數(shù)，用戶隨時可能有意或無意中偏離規(guī)劃路線。這個時候，及時且智能化的提示顯得尤為重要。
偏航引擎，負責實時用戶位置，檢測用戶是否偏離規(guī)劃路線，并提供及時可靠的偏航提醒，發(fā)起新的路線規(guī)劃請求等；在實際行駛的過程中，偏航提示對用戶必不可少，其準確率和及時性對用戶體驗至關(guān)重要。

▍
3.2  傳統(tǒng)偏航算法
傳統(tǒng)偏航算法，通?；诘貓D匹配（map matching）和垂直場景下的特定規(guī)則來進行偏航判定。
地圖匹配是將一系列有序的用戶或者交通工具的位置關(guān)聯(lián)到地圖路網(wǎng)上的過程。因為GPS給定的用戶位置往往會有誤差，如果不進行地圖匹配，可能并不會顯示在路網(wǎng)上。在實際應(yīng)用中，基于隱馬爾可夫模型（HMM）的地圖匹配就有比較良好的效果。
偏航判定基于地圖匹配的結(jié)果（匹配到特定路網(wǎng)的置信度），以及當前GPS狀態(tài)信息（位置，方位角，速度，精度等），GPS與匹配點及規(guī)劃路線之間的關(guān)系，同時依據(jù)GPS歷史特征，判定用戶是否偏離規(guī)劃路線。
傳統(tǒng)的偏航判定往往基于大量人工編碼的規(guī)則。通常情況下，由于GPS的可靠性并不穩(wěn)定，偏航準確性與靈敏性存在一定的互斥關(guān)系。
為了同時提升兩方面的指標，常常需要針對特定場景進行特定的優(yōu)化。如在效果較高的時候，可以提高偏航的靈敏度；在效果較低的情況下，為了提升準確率，相應(yīng)的降低偏航靈敏度。
另外，由于低效果的GPS在不同的行駛狀態(tài)下會展現(xiàn)出不同的特征，我們也可以根據(jù)規(guī)劃路線的特征（如直行，轉(zhuǎn)彎，掉頭等），結(jié)合GPS特征（減速，掉頭，精度降低等），在垂直場景下設(shè)置不同的偏航閾值。

▍
3.3 移動端應(yīng)用深度學習模型

3.
3.1 為什么引入深度學習

傳統(tǒng)偏航判定中，無論是效果，還是規(guī)則編寫都具有較大的局限性。效果常常依賴于一系列固定的數(shù)學公式，難以融入大量GPS特征進行綜合考量，其準確性和召回率不盡如人意。偏航規(guī)則隨著產(chǎn)品迭代日漸復(fù)雜化，變得難以維護，特別是面對人員迭代，更是難以處理。
基于偏航判定問題的特征，我們嘗試在端上引入深度學習模型。通過自動化的模型學習，為偏航判定提供更加統(tǒng)一和簡單的特征指標，簡化編碼邏輯和維護代價，提升偏航準確性和靈敏度。

3.
3.2 移動端應(yīng)用深度學習算法的限制
推算性能由于前端機型種類繁多，性能參差不齊?？紤]兼容性，做模型推算時往往中低端機型為準。采用相關(guān)算法庫需要針對arm處理器做相應(yīng)的優(yōu)化。
模型大小移動端特別是地圖對App大小通常較為敏感。深度學習的應(yīng)用需要引入算法庫及模型文件，如果使用開源庫文件，可能需要做適當?shù)募舨茫换蛘吒鶕?jù)最終引入的模型結(jié)構(gòu)定制相應(yīng)的算法庫，從而控制庫文件大小。另外，針對不同的模型類型、深度及輸入特征，模型大小會產(chǎn)生較大的變化，最終選擇的模型可能并非最好，但綜合而言最為合適即可（比如200k模型比100k模型準確率提升0.2%，可能我們?nèi)匀粫x擇100k模型）。
算法限制使用特定第三方算法庫如tensorflow lite，不支持部分運算符等。事實上，移動端應(yīng)用深度學習也是一個多方權(quán)衡的過程，最終的目標是實現(xiàn)性能，模型大小，準確性等指標的理想平衡。

▍
3.4 GPS效果模型

前面提到，效果對于高靈敏度的偏航判定尤為重要。但基于規(guī)則的方法能夠提取的高效果GPS，在保證準確率的前提下，召回率往往較低。在偏航場景下，利用深度學習的方式來做效果判定，我們需要重新定義該問題。

3.
4.1 問題定義及樣本標準

如果以GPS偏離路線的距離或角度來認定效果的優(yōu)劣，標準會變得比較模糊。如此一來會大大增加樣本的采集的難度和統(tǒng)一性。此外，效果的判定與偏航判定不具有相關(guān)性，最終能否對偏航指標帶來提升存在很大的不確定性。

從偏航判定的角度出發(fā)，我們認為在人工校驗下：

發(fā)生誤偏航的GPS點，其效果基本是不可靠的（以上左圖）。

偏航靈敏度較低，但足以判定為偏航的情形，其效果是可靠的（以上右圖）。

為排除干擾，將GPS點聚集等不影響偏航判定的情形，歸類為其它；

于是我們的問題轉(zhuǎn)化為簡單的多分類問題。

3.
4.2 特征工程

GPS效果模型中，我們提取了兩類樣本特征。分別為GPS屬性（速度，時間，方位角，精度等），和人工屬性（距離，幾何角，角變量，積分推算偏移等）。部分人工屬性的提取雖然不能提升模型的準確率上限（比如在特定模型下適當增加神經(jīng)元數(shù)量，可以以較少的屬性達到較多屬性的準確率），但卻能降低模型復(fù)雜度，從而降低模型大小，提升性能。這對于移動端而言是非常有益的。

對于低重要度的特征，最終做了刪除，從而降低模型大小。例如我們發(fā)現(xiàn)方位角的重要度在實際模型訓練中不如角變量。方位角本身的不連續(xù)性（0 = 2pi）可能對模型訓練是一種干擾。

對于異常值，做了基本的數(shù)據(jù)清洗，如無效的速度值，無效的方位角；對于不足的GPS序列長度，用0進行填充（但需要額外注意起點屬性）等。

3.
4.
3. 模型選擇、訓練與效果

DNN：只需要相對簡單的算法實現(xiàn)，引入較小的模型庫。然而GPS數(shù)據(jù)具有典型的時間序列特征，在4萬樣本下，應(yīng)用利用DNN模型調(diào)參優(yōu)化后，訓練結(jié)果準確率最高達到91%。Bad case中存在大量時間不敏感的情形，最典型的情形就是——由差轉(zhuǎn)優(yōu)時，判定結(jié)果未能及時轉(zhuǎn)變?yōu)楦咝Ч?/p>

CNN：這里可以嘗試兩種實現(xiàn)方式，一種是通過生成bitmap進行識別，然而GPS跨度不確定性較高，方向性不易表達，在實現(xiàn)上具有一定困難。第二種將序列化數(shù)據(jù)轉(zhuǎn)化為二維數(shù)組，C模型能夠識別出前后時間戳之間的變化特征，但并不能保留更長的時間的變化特征。最終訓練出的準確率在93%左右。另外，CNN模型應(yīng)用在移動端有一個明顯的缺點，即模型尺寸一般較大。

LSTM（長短期記憶網(wǎng)絡(luò)）：一種特殊的RNN模型，相比前述模型對效果序列判定有明顯優(yōu)勢。在效果由好轉(zhuǎn)差，或由差轉(zhuǎn)好的識別上具有非常高的靈敏度，使用128個unit能夠達到97%的準確率。缺點是LSTM模型訓練速度相對較慢，算法庫實現(xiàn)相對復(fù)雜。

最終我們選擇了使用LSTM模型。使用LSTM的訓練結(jié)果，準確率大幅提升。在剩余3%的錯誤樣例中，很多在形態(tài)上表現(xiàn)出較高的真實性，但卻無法同路網(wǎng)進行匹配。理論上通過引入路網(wǎng)屬性能夠上帶來準確率的進一步提升，然而這種數(shù)據(jù)的耦合脫離了效果判定的初衷——服務(wù)于偏航引擎專家系統(tǒng)，而非直接用于偏航判定。對此我們將會在最后進行更詳細的介紹。

3.
4.
4. 移動端性能優(yōu)化

模型推算性能對于移動端尤為重要。偏航場景下，GPS更新頻繁，選擇在必要的時候進行模型推算能夠避免不必要的計算開銷。通常我們會計算當前GPS點與規(guī)劃路線的偏離度，只有偏離度大于閾值時才會進行效果判定。

▍
3.5 基于深度學習的專家系統(tǒng)探索

效果模型作為偏航判定的重要依據(jù)，能夠以較小的代價移植到移動端。如果不考慮前端性能及數(shù)據(jù)限制，我們完全可以定義整個偏航判定問題，訓練相應(yīng)的偏航模型。然而偏航場景種類繁多，過于復(fù)雜，訓練出一套通用的偏航模型需要大量的數(shù)據(jù)，充足的路網(wǎng)信息，和較大的模型存儲，這對于移動端而言不太現(xiàn)實。  

傳統(tǒng)偏航算法類似于實現(xiàn)一套基于規(guī)則的偏航專家系統(tǒng)。推算過程依賴了大量復(fù)雜的規(guī)則，這些規(guī)則難以概括和抽象為更簡單的模塊，算法的優(yōu)化和維護都比較困難。因此我們考慮將偏航場景重新細化分類，依據(jù)不同的場景訓練相應(yīng)的偏航模型。例如效果較差的直行或轉(zhuǎn)彎路線，能夠分別能訓練出不同的模型。用這些模型替代原有的復(fù)雜規(guī)則，對移動端而言，可移植性及可控性都會更好。這種基于深度學習的專家系統(tǒng)，是我們接下來完善優(yōu)化偏航算法的重要方向。

滴滴地圖標注與公交事業(yè)部泛前端及導航引擎團隊，負責為滴滴地圖標注平臺上的司乘雙方提供優(yōu)秀的地圖產(chǎn)品體驗。通過不斷的產(chǎn)品打磨及技術(shù)創(chuàng)新來提升用戶體驗，具體包括在業(yè)內(nèi)首推司乘同顯創(chuàng)新功能，在跨端技術(shù)、圖像渲染及導航引擎等方向持續(xù)深耕等。