桔妹导读：滴滴导航是滴滴出行旗下基于丰盛的交通大数据和当先的算法策略，面向网约车及自驾场景而打造的一款技术当先的地图产品。随同着海量网约车司机每日 8 小时 + 的导航应用，产品积攒了大量的反馈并继续优化打磨。在这个过程中，为了给用户带来更好的地图导航体验，团队始终在积极探索技术上的冲破和实际，并获得了肯定的成绩。明天，咱们将会对其中的 MJO 三维全景导航（行业惟一）、导航主辅路偏航辨认及深度学习在端上抓路利用这三个技术点给大家开展解说。
1. MJO 三维全景导航
▍1.1 利用背景
对于绝大多数驾驶者应用 2D 导航地图，都会呈现立交上认错路口，高速上错过匝道，不知何时该并线的问题。路口图形诱导的呈现，肯定水平上缓解了路口偏航的问题。业内艰深几种做法，如下图：
从左到右程序：
- 实景图：基于事实建模，然而只展现了一个角度的图像，老本过高。
- 模式图： 1 对多的映射关系，跟事实路口状态路线蜿蜒度差别会很大。
- 矢量大图：基于 2d 路线属性制作，算法驱动能够上量。
- 街景大图：路口和街景图像做挂接，而后叠加疏导箭头。依赖街景采集老本微小。
- 卫星大图：路口实在但只有 2D 视角。
上述所有计划都只能动态展现，而且不能准确辨别车道。滴滴地图中的 MJO 导航技术，通过退出与实景图同级别的精密场景模型，精确表白简单桥区的档次穿梭关系。极大地升高了读图老本。
三维全景导航的技术难点在于模型复杂度高，数据量较大，相比 2D 导航地图须要更多的 CPU 和 GPU 资源反对。为了在更宽泛的设施上实现该性能，须要大幅优化资源的内存、CPU 及 GPU 耗费。
▍1.2 数据压缩
较大的模型尺寸带来了网络传输的压力，对数据压缩提出了较高的要求。原始数据全国总量高达 41G，无奈适应挪动端的内存需要。性能攻坚阶段，团队交融了多种压缩技术进行优化：
- 纹理压缩
- 提取共享资源
- 模型压缩
- 格局二进制转换
- 主要模型过滤
▍1.3 Metal/Vulkan 技术
滴滴渲染引擎引入了下一代的图形 API，Metal 及 Vulkan 技术。苹果声称 Metal 能够提供 10 倍于 OpenGL 的性能，而 Vulkan 则是由 khronos 组织提出的凋谢规范，能够反对 Apple 以外的平台。比照传统的 OpenGL ES 技术，Metal/Vulkan 更加贴近底层硬件，能够更准确地管制 GPU，有着更好的线程模型。Metal 和 Vulkan 能够反对更多的 draw calls，非常适合利用于 MJO 这种模型数量较多的场景。通过适配 Metal/Vulkan，解决了渲染引擎中 shared context 的兼容问题，进步了多线程加载的性能，对整体性能和稳定性都有了较大的晋升。▍1.4 渲染性能优化 因为模型数据量较大，数据加载耗时，应用传统的加载形式会造成显著的卡顿问题，影响用户体验。通过利用 Metal/OpenGL ES/Vulkan 的多线程技术，资源加载应用了独立的加载线程。加载过程对渲染线程没有间接影响，使程序更加晦涩。渲染场景的治理采纳了八叉树技术，用于疾速选取可见元素，升高渲染负载。比照程序遍历的 O（N）复杂度，八叉树降到了 O（logN）。
MJO 原始模型粒度较细，一个桥区蕴含 2000 多个模型，如果间接进行渲染会造成 draw call 数量过多，每个 draw call 都会产生额定的耗费。通过材质合并模型后，draw calls 升高到 40 多个，大幅升高了渲染和内存耗费。
▍1.5 导航实现
MJO 导航尽管提供了高精度的路线模型和车道级的导航线数据，但因为挪动端设施并不蕴含高精度的定位设施，须要利用现有的 2D 导航逻辑，将 GPS 点映射到 MJO 的导航线上。具体步骤如下：
- 依据 2D 导航的 link 序列过滤出通过 MJO 桥区的局部
- 绑路服务计算映射出的 MJO link 序列并拼装 MJO 导航线
- MJO 导航线和 GPS 点传入导航引擎，计算出 MJO 中的绑路点
- MJO 导航线传入渲染引擎，通过 Bezier 插值进行平滑解决并渲染
- 绑路点在导航线上进行投影失去 3D 高度，并插值成平滑挪动的动画进行渲染
其中平滑算法应用了 Bezier 插值，p1 p4 是曲线端点，p2 p3 用于管制形态，t 是插值参数。
导航线由多个点形成，端点能够从导航线中间接失去。两头的 2 个控制点须要进行计算。这里的技术要点是保障连贯两段线的切向统一（C1 间断），在平滑的同时保障曲率不要过分偏离端点。团队通过优化参数和算法，失去了比较满意的成果。
▍1.6 总结
MJO 波及了多种渲染及建模相干的技术，范围广难度高。团队在无限的人力和工夫估算条件下，攻克了多个技术难点，实现了一套残缺的动画诱导计划。极大地升高了驾驶过程的刹时读图老本，无效地缓解了简单路口的偏航问题。
2. 滴滴主辅路偏航辨认的利用实际
偏航是车辆理论行驶路线偏离了原定布局路线的行为，而偏航辨认用以确定车辆是否偏航，对偏航从新布局行驶路线。主辅路作为非凡的路线场景，其因为平行的特殊性，导致主辅路偏航较个别偏航更具备挑战性。本文将介绍滴滴在主辅路偏航辨认上的一些摸索和实际。
▍2.1 利用背景
偏航是车辆理论行驶路线偏离了原定布局路线的行为，如图 1 所示，红色的是布局路线，带偏航的点是车辆 gps 点，整体轨迹上来看车辆曾经偏离了布局路线，则为偏航。
而主辅路偏航场景如图 2 所示，车辆在图中红框路口处车辆由主路切换到了辅路，则为一次主辅路偏航。
▍2.2 主辅路偏航辨认难点
偏航辨认作为典型的二分类问题，通常会应用有监督学习的模型求解。因为主辅路的特殊性，有监督学习的标签就成为整个技术计划的难点。
图 3 主辅路轨迹如图 3 的轨迹，车辆在主辅路左近有一个偏移动作，然而单纯从轨迹上很难分别车辆是切换了个车道还是有主辅路切换，无奈单纯从轨迹上是无奈取得真值。因而，须要引入额定的信息，而滴滴领有宽广司机上报的图像数据就是一个很好的补充。除了标签这个外围问题外，还有一些次要问题：
- GPS 点漂移：GPS 点受信号强弱等影响，会呈现地位偏差。主辅路场景下，主辅路之间间隔不会很远，则 GPS 的地位偏差会更容易造成误判。
- 路网形态偏差：地图数据往往用有向线段示意主观路线，然而数据探查录入等起因，和主观世界路线地位形态会有偏差，给辨认带来难度。
为了解决以上问题，晋升用户主辅路偏航上的体验，咱们提出了一种基于图像识别的主辅路偏航识别系统。
▍2.3 技术计划
2.3.1 整体方案设计
整体计划如图 4，主辅路偏航辨认整体计划波及到左侧的离线模型训练局部和在右侧线预测局部，其中离线训练次要包含：
- 机器标注逻辑 依据轨迹和路网连通性进行标注的样本。因为存在路网连通性的束缚，因而标注后果准确率高，然而路型笼罩会有局限
- 图像标注逻辑 依据司机上报图像识别车辆在行为（车辆在主路 / 在辅路，或序列模型辨认主辅路切换动作），联合轨迹和路网数据生成样本。因为不受路网状态束缚，因而路型笼罩会更全；然而因为须要对路面图像进行图像识别，依赖图像识别的准确率，存储和计算成本较高
- 模型训练 将机器标注样本和图像标注样本进行合并后进行训练，因为图像标注样本老本更高，所以会对图像样本用一些上采样形式。
在线预测局部就是规范的线上预测流程，不做过多赘述。
2.3.2 机器标注逻辑
机器标注逻辑是依据轨迹和路网连通性进行标注的逻辑。如图 5 所示，轨迹有拐入“东双贝子坟路”，然而主路依据路网连通性是不可能拐入的，因而能够推断在红框路口处，车辆从主路切换到了辅路。通过路网连通性的规定能很容易的筛出这类样本，且这类样本准确性极高。
然而机器标注逻辑的局限也很显著，就是诸如图 6 的轨迹，机器标注是无奈确认红框的主辅路区间内车辆是开在主路或辅路的。以北京的轨迹为例，机器标注能解决的路口小于 30%，如果仅应用这部分样本进行训练，会因样本有偏导致成果不现实。
2.3.3 图像标注逻辑
滴滴领有司机上报的图像数据，能够依据图像识别司机行为（车辆在主路 / 在辅路，或主辅路切换动作），再联合轨迹和路网数据，生成图像标注汇合。
如上图是一个图像数据示例，序号示意其序列关系，由图所示，车辆由辅路切换到了主路。图像识别应用了两套逻辑：
- 单图辨认 序列中对每张图片进行辨认，给出其分类后果，类别包含：高架上主路、高架下主路、高架下辅路、主路、辅路。而后依据序列的分类后果，只有有类别的连续性变动视为切换行为，如序列（主路、主路、辅路、辅路）就能够视为切换。
- 序列辨认 依据图片序列辨认是否有主辅路切换动作。采纳端到端的注意力与类别层级交融损失束缚模型进行特色学习与计算；为了更好的利用序列的语义信息，将主辅路单图特色集成到序列模型中，进行序列束缚，辨认序列后果。
序列模型准确率更高，然而对于图像序列要求较高（比方工夫距离不能太长）；单图辨认的召回更高，然而在有遮挡或高架下场景体现不好。将两个模型的后果进行交融，引入司机轨迹、路网数据失去最终的图像标注后果。图像标注后果的准确率在 93% 以上。
2.3.4 模型训练
因为线上只能应用到轨迹和路网的数据，因而应用特色次要分为以下几类：
- 点特色：GPS 点的特色，包含坐标、速度、方向等
- 路线（link）特色：包含路线属性（国道等）、车道数、路线方向等
- 点 -link 特色：包含点方向同路线方向角度差、点到路线的间隔等
- 序列特色：包含以后点同上一个点的角度差、间隔差，以及累计角度变动等
同时，针对 GPS 点信号不精确漂移的状况，应用卡尔曼滤波对原始 GPS 点位移，缩小个别点漂移对于模型的影响；针对整段轨迹漂移，应用 Frechet 间隔掂量其形态类似度，退出到特色中。针对路网形态偏差，应用历史轨迹统计的形式（热力求），对原始路网进行平移、蜿蜒等形态变动。偏航是典型的二分类问题，初版模型应用 Xgboost 疾速上线，目前在进行 Wide&Deep 和 LSTM 等模型的尝试。
2.3.5 成果评估
随机抽取了 2000 个司机上报的图像数据，对通过的主辅路路口进行人工标注其主辅路切换行为，为人工标注集。同时，人工只依据轨迹信息进行断定轨迹行为，辨认拐弯的准确率 92%、召回率 91%。造成这类问题的次要起因是预计漂移，如图 7 的轨迹，人工如果只依据轨迹判断，会认为车辆在路口由主路切换到辅路，然而依据图像能够确认其始终在主路上。
在人工标注集上的辨认拐弯的准确率 88%、召回率 89%，靠近人工只依据轨迹的断定的准召，然而还有肯定晋升空间。
▍2.4 总结
主辅路偏航作为偏航辨认里的非凡类型，因为其平行的特殊性，给辨认带来了较大的挑战。本文介绍了滴滴在主辅路偏航辨认上的一些摸索和实际，借助滴滴的数据劣势，建设了一套依赖图像识别的主辅路偏航真值标注体系，并在最初主辅路偏航辨认获得了预期的成果。
3. 深度学习在偏航引擎前端的摸索和实际
▍3.1 导读
导航作为地图出行的外围场景，依据起起点、路线数据及路况信息为用户定制出行计划。导航为用户提供布局门路，但事实出行中充斥变数，用户随时可能无意或无心中偏离原始布局路线。这个时候，及时且智能化的提醒显得尤为重要。偏航引擎，负责实时跟踪用户地位，检测用户是否偏离布局路线，并提供及时牢靠的偏航揭示，发动新的路线布局申请等；在理论行驶的过程中，偏航提醒对用户必不可少，其准确率和及时性对用户体验至关重要。
▍3.2 传统偏航算法
传统偏航算法，通常基于地图匹配（map matching）和垂直场景下的特定规定来进行偏航断定。
地图匹配 是将一系列有序的用户或者交通工具的地位关联到地图路网上的过程。因为 GPS 给定的用户地位往往会有误差，如果不进行地图匹配，可能并不会显示在路网上。在理论利用中，基于隐马尔可夫模型（HMM）的地图匹配就有比拟良好的成果。
偏航断定 基于地图匹配的后果（匹配到特定路网的置信度），以及以后 GPS 状态信息（地位，方位角，速度，精度等），GPS 与匹配点及布局路线之间的关系，同时根据 GPS 历史轨迹特色，断定用户是否偏离布局路线。
传统的偏航断定往往基于大量人工编码的规定。通常状况下，因为 GPS 的可靠性并不稳固，偏航准确性与灵敏性存在肯定的互斥关系。
为了同时晋升两方面的指标，经常须要针对特定场景进行特定的优化。如在轨迹品质较高的时候，能够进步偏航的灵敏度；在轨迹品质较低的状况下，为了晋升准确率，相应的升高偏航灵敏度。
另外，因为低质量的 GPS 在不同的行驶状态下会展现出不同的轨迹特色，咱们也能够依据布局路线的特色（如直行，转弯，掉头等），联合 GPS 轨迹特色（加速，掉头，精度升高等），在垂直场景下设置不同的偏航阈值。
▍3.3 挪动端利用深度学习模型
3.3.1 为什么引入深度学习
传统偏航断定中，无论是轨迹品质，还是规定编写都具备较大的局限性。轨迹品质经常依赖于一系列固定的数学公式，难以融入大量 GPS 特色进行综合考量，其准确性和召回率不尽如人意。偏航规定随着产品迭代日渐复杂化，变得难以保护，特地是面对人员迭代，更是难以解决。基于偏航断定问题的特色，咱们尝试在端上引入深度学习模型。通过自动化的模型学习，为偏航断定提供更加对立和简略的特色指标，简化编码逻辑和保护代价，晋升偏航准确性和灵敏度。
3.3.2 挪动端利用深度学习算法的限度
- 推算性能
因为前端机型品种繁多，性能参差不齐。思考兼容性，做模型推算时往往中低端机型为准。采纳相干算法库须要针对 arm 处理器做相应的优化。
- 模型大小
挪动端特地是地图对 App 大小通常较为敏感。深度学习的利用须要引入算法库及模型文件，如果应用开源库文件，可能须要做适当的剪裁；或者依据最终引入的模型构造定制相应的算法库，从而管制库文件大小。另外，针对不同的模型类型、深度及输出特色，模型大小会产生较大的变动，最终抉择的模型可能并非最好，但综合而言最为适合即可（比方 200k 模型比 100k 模型准确率晋升 0.2%，可能咱们依然会抉择 100k 模型）。
- 算法限度
应用特定第三方算法库如 tensorflow lite，不反对局部运算符等。事实上，挪动端利用深度学习也是一个多方衡量的过程，最终的指标是实现性能，模型大小，准确性等指标的现实均衡。
▍3.4 GPS 轨迹品质模型
后面提到，轨迹品质对于高灵敏度的偏航断定尤为重要。但基于规定的办法可能提取的高质量 GPS 轨迹，在保障准确率的前提下，召回率往往较低。在偏航场景下，利用深度学习的形式来做品质断定，咱们须要从新定义该问题。
3.4.1 问题定义及样本规范
如果以 GPS 偏离路线的间隔或角度来认定轨迹品质的优劣，规范会变得比拟含糊。如此一来会大大增加样本的采集的难度和统一性。此外，轨迹品质的断定与偏航断定不具备相关性，最终是否对偏航指标带来晋升存在很大的不确定性。
从偏航断定的角度登程，咱们认为在人工校验下：
- 产生误偏航的 GPS 点，其轨迹品质根本是不牢靠的（以上左图）。
- 偏航灵敏度较低，但足以断定为偏航的情景，其轨迹品质是牢靠的（以上右图）。
- 为排除烦扰，将 GPS 点汇集等不影响偏航断定的情景，归类为其它；
于是咱们的问题转化为简略的多分类问题。
3.4.2 特色工程
GPS 轨迹品质模型中，咱们提取了两类样本特色。别离为原始 GPS 属性（速度，工夫，方位角，精度等），和人工属性（间隔，几何角，角变量，积分推算偏移等）。局部人工属性的提取尽管不能晋升模型的准确率下限（比方在特定模型下适当减少神经元数量，能够以较少的属性达到较多属性的准确率），但却能升高模型复杂度，从而升高模型大小，晋升性能。这对于挪动端而言是十分无益的。
对于低重要度的特色，最终做了删除，从而升高模型大小。例如咱们发现方位角的重要度在理论模型训练中不如角变量。揣测方位角自身的不连续性（0 = 2pi）可能对模型训练是一种烦扰。
对于异样值，做了根本的数据荡涤，如有效的速度值，有效的方位角；对于有余的 GPS 序列长度，用 0 进行填充（但须要额定留神终点属性）等。
3.4.3 模型抉择、训练与成果
DNN：只须要绝对简略的算法实现，引入较小的模型库。然而 GPS 轨迹数据具备典型的工夫序列特色，在 4 万样本下，利用利用 DNN 模型调参优化后，训练后果准确率最高达到 91%。Bad case 中存在大量工夫不敏感的情景，最典型的情景就是——轨迹由差转优时，断定后果未能及时转变为高质量。
CNN：这里能够尝试两种实现形式，一种是通过生成 bitmap 进行辨认，然而 GPS 跨度不确定性较高，方向性不易表白，在实现上具备肯定艰难。第二种将序列化数据转化为二维数组，C 模型可能辨认出前后工夫戳之间的变动特色，但并不能保留更长的工夫的变动特色。最终训练出的准确率在 93% 左右。另外，CNN 模型利用在挪动端有一个显著的毛病，即模型尺寸个别较大。
LSTM（长短期记忆网络）：一种非凡的 RNN 模型，相比前述模型对轨迹品质序列断定有显著劣势。在轨迹品质由恶化差，或由差转好的辨认上具备十分高的灵敏度，应用 128 个 unit 可能达到 97% 的准确率。毛病是 LSTM 模型训练速度绝对较慢，算法库实现绝对简单。
最终咱们抉择了应用 LSTM 模型。应用 LSTM 的训练后果，准确率大幅晋升。在残余 3% 的谬误样例中，很多轨迹在状态上体现出较高的真实性，但却无奈同路网进行匹配。实践上通过引入路网属性可能上带来准确率的进一步晋升，然而这种数据的耦合脱离了轨迹品质断定的初衷——服务于偏航引擎专家系统，而非间接用于偏航断定。对此咱们将会在最初进行更具体的介绍。
3.4.4 挪动端性能优化
模型推算性能对于挪动端尤为重要。偏航场景下，GPS 更新频繁，抉择在必要的时候进行模型推算可能防止不必要的计算开销。通常咱们会计算以后 GPS 点与布局路线的偏离度，只有偏离度大于阈值时才会进行轨迹品质断定。
▍3.5 基于深度学习的专家系统摸索
轨迹品质模型作为偏航断定的重要依据，可能以较小的代价移植到挪动端。如果不思考前端性能及数据限度，咱们齐全能够定义整个偏航断定问题，训练相应的偏航模型。然而偏航场景品种繁多，过于简单，训练出一套通用的偏航模型须要大量的数据，短缺的路网信息，和较大的模型存储，这对于挪动端而言不太事实。
传统偏航算法相似于实现一套基于规定的偏航专家系统。推算过程依赖了大量简单的规定，这些规定难以概括和形象为更简略的模块，算法的优化和保护都比拟艰难。因而咱们思考将偏航场景从新细化分类，根据不同的场景训练相应的偏航模型。例如轨迹品质较差的直行或转弯路线，可能别离能训练出不同的模型。用这些模型代替原有的简单规定，对挪动端而言，可移植性及可控性都会更好。这种基于深度学习的专家系统，是咱们接下来欠缺优化偏航算法的重要方向。
本文作者
延长浏览
内容编辑 | Charlotte
分割咱们 | DiDiTech@didiglobal.com
</pre>
滴滴技术 出品