转自：http://36kr.com/p/5060994.html
编者按：本文来自《程序员》，作者 陈辰、刘少山，36氪经授权发布。
高精地图是无人驾驶核心技术之一，精准的地图对无人车定位、导航与控制，以及安全至关重要。本文是“无人驾驶技术系列”第七篇，首先介绍高精地图与传统地图的区别，然后介绍其特点及制作过程。在了解高精地图基础知识后，探索其在无人驾驶场景中的应用。
我们日常使用的用于导航、查询地理信息的地图都属于传统电子地图，其主要服务对象是人类驾驶员。而与传统电子地图不同，高精度电子地图的主要服务对象是无人驾驶系统。本节讨论两者的不同。
如图1所示，我们日常使用的用于导航、查询地理信息的地图，如Google、百度、苹果地图等，都可以并入传统电子地图。尽管电子地图出现还不到一百年，对传统地图的研究和开发已有几千年历史，并发展出“制图学”这一门学科。在制图学的基础上，电子地图的出现极大提高了检索效率，并且能快速查找最优路径，极大方便了人们出行。
传统电子地图是对路网的一种抽象：都将路网抽象成有向图的形式——图的顶点代表路口，边代表路口与路口的连接。路名、地标以及道路骨架信息都可以被抽象成存储于这些有向图顶点或边中的属性。这种抽象的地图表征形式能很好地适应人类驾驶员需求，其原因在于人类生来就有很强的视觉识别及逻辑分析能力。在驾驶过程中，人类驾驶员一般都能有效判别如下信息：识别路面及路面标示线，确定自己在路面的大致位置，寻找并辨认路标等。参照辨识出的信息，结合当前GPS（一般精度在5-10米）在当前电子地图中的位置，人类驾驶员便大致知道自己在实际路网中的位置，并计划下一步如何驾驶。
正是基于人类驾驶员的这些能力，传统电子地图可被极大精简，比如一条弯曲的道路可以被精简到用只有几个点的线段来表示，只要大致轮廓符合现实路网结构，人类驾驶员即可结合驾驶信息定位自己的当前位置。
与传统电子地图不同，高精度电子地图的主要服务对象是无人驾驶车，或者说是机器驾驶员。和人类驾驶员不同，机器驾驶员缺乏与生俱来的视觉识别、逻辑分析能力。比如，人可以很轻松、准确地利用图像、GPS定位自己，鉴别障碍物、人、交通信号灯等，但这对当前的机器人来说都是非常困难的任务。因此，高精度电子地图是当前无人驾驶车技术中必不可少的一个组成部分。高精度电子地图包含大量行车辅助信息，其中，最重要的是对路网精确的三维表征（厘米级精度）。比如，路面的几何结构，道路标示线的位置，周边道路环境的点云模型等。有了这些高精度的三维表征，车载机器人就可以通过比对车载GPS、IMU、LiDAR或摄像头数据来精确确认自己的当前位置。此外，高精地图还包含丰富的语义信息，比如交通信号灯的位置及类型，道路标示线的类型，识别哪些路面可以行驶等。这些能极大提高车载机器人鉴别周围环境的能力。此外，高精度地图还能帮助无人车识别车辆、行人及未知障碍物。这是因为高精地图一般会过滤掉车辆、行人等活动障碍物。如果无人车在行驶过程中发现当前高精地图中没有的物体，便有很大几率是车辆、行人或障碍物。因此，高精地图可以提高无人车发现并鉴别障碍物的速度和精度。
相比服务于GPS导航系统的传统地图而言，高精地图最显著的特点是其表征路面特征的精准性。传统地图只需要做到米级精度即可实现GPS导航，但高精地图需要达到厘米级精度才能保证无人车行驶安全。
此外，高精地图还需要比传统地图有更高的实时性。由于路网每天都有变化，如整修、道路标识线磨损及重漆、交通标示改变等。这些变化需要及时反映在高精地图上以确保无人车行驶安全。实时高精地图有很高的难度，但随着越来越多载有多种传感器的无人车行驶在路网中，一旦有一辆或几辆无人车发现了路网的变化，通过与云端通信，就可以把路网更新信息告诉其他无人车，使其他无人车更加聪明和安全。
和传统地图相似，高精地图也具有分层的数据结构。如图3所示，最底层是基于红外线雷达传感器所建立的精密二维网格。一般这个二维网格的精度保证在5×5厘米左右。可以行驶的路面、路面障碍物，以及路面在激光雷达下的反光强度都被存储于相应的网格当中。无人车在行驶的过程中，通过比对其红外线雷达搜集到的数据及其内存中的高精二维网格，就能确定车辆在路面的具体位置。
除了底层的二维网格表征外，高精地图还包含很多有关路面的语义信息。如图4所示，在二维网格参照系的基础上，高精地图一般还包含道路标识线的位置及特征信息，以及相应的车道特征。由于车载传感器可能会因为恶劣天气、障碍物，以及其他车辆的遮挡不能可靠分析车道信息，高精地图中的车道信息特征能帮助无人车更准确可靠地识别道路标识线，并理解相邻车道之间是否可以安全并道。
高精地图中的车道信息
图5 高精地图中的道路标识线及路牌信息
此外，如图5所示，高精地图还会标明道路标示牌、交通信号等相对于二维网格的位置，这些信息起两方面作用：
提前预备无人车，告知其在某些特定的位置检测相应的交通标示牌或交通信号灯，提高无人车的检测速度。
在无人车没有成功检测出交通标示牌或信号灯的情况下，确保行车安全。
无人车使用的高精地图是个2D网格，数据主要由激光雷达产生，由于激光雷达的精度大约是5厘米，所以地图的最高精度可以达到每个网格5×5厘米。在如此高的精度下，如何有效管理数据是一大挑战。首先，为了尽量让地图在内存里中，我们要尽量去掉不需要的数据。一般激光雷达可覆盖方圆100米范围，假设每个反光强度可以用一个字节记录，那么每次激光雷达扫描可产生4MB数据。扫描会包括公路旁边的树木及房屋，但无人车行驶并不需要这些数据，只需记录公路表面的数据即可。假设路面的宽度为20米，就可以通过数据处理把非公路表面的数据过滤掉，这样每次扫描的数据量会下降到0.8MB。在过滤数据的基础上，还可以使用无损压缩算法，如LASzip压缩地图数据，可以达到超过10倍的压缩率。经过这些处理后，1TB硬盘就可以存下全中国超过10万公里的高精地图数据。
传统电子地图主要依靠卫星图片产生，然后由GPS定位，这种方法可以达到米级精度。而高精地图需要达到厘米级精度，仅靠卫星与GPS是不够的。因此，其生产涉及多种传感器, 由于产生的数据量庞大，通常会使用数据采集车（如图6所示）收集，然后通过线下处理把各种数据融合产生高精地图。
图6 高精地图数据采集车
高精地图的制作是个多传感器融合的过程， 包括了以下几种：
陀螺仪（IMU）： 一般使用6轴运动处理组件，包含了3轴加速度和3轴陀螺仪。加速度传感器是力传感器，用来检查上下左右前后哪几个面都受了多少力（包括重力），然后计算每个上的加速度。陀螺仪就是角速度检测仪，检测每个上的加速度。假设无人车以Z轴为轴心，在一秒钟转到了90度，那么它在Z轴上的角速度就是90度/秒。从加速度推算出运动距离需要经过两次积分，所以，但凡加速度测量上有任何不正确，在两次积分后，位置错误会积累然后导致位置预测错误。所以单靠陀螺仪并不能精准地预测无人车位置。
轮测距器（Wheel Odometer）： 我们可以通过轮测距器推算出无人车的位置。汽车的前轮通常安装了轮测距器，分别会记录左轮与右轮的总转数。通过分析每个时间段里左右轮的转数，我们可以推算出车辆向前走了多远，向左右转了多少度等。可是由于在不同地面材质（比如冰面与水泥地）上转数对距离转换的偏差，随着时间推进，测量偏差会越来越大。所以单靠轮测距器并不能精准预测无人车位置。
GPS：任务是确定四颗或更多卫星的位置，并计算出它与每颗卫星之间的距离，然后用这些信息使用三维空间的三边测量法推算出自己的位置。要使用距离信息进行定位，接收机还必须知道卫星的确切位置。GPS接收机储存有星历，其作用是告诉接收机每颗卫星在各个时刻的位置。在无人车复杂的动态环境，尤其在大城市中，由于各种高大建筑物的阻拦。GPS多路径反射（Multi-Path）的问题会更加明显。这样得到的GPS定位信息很容易就有几十厘米甚至几米的误差，所以单靠GPS不可以制作高精地图。
激光雷达（LiDAR）： 光学雷达通过首先向目标物体发射一束激光，然后根据接收－反射的时间间隔来确定目标物体的实际距离。然后根据距离及激光发射的角度，通过简单的几何变化可以推导出物体的位置信息。LiDAR系统一般分为三个部分：一是激光发射器，发出波长为600nm到1000nm的激光射线；二是扫描与光学部件，主要用于收集反射点距离与该点发生的时间和水平角度（Azimuth）；三是感光部件，主要检测返回光的强度。因此我们检测到的每一个点都包括了空间坐标信息以及光强度信息＜i＞。光强度与物体的光反射度（reflectivity） 直接相关，所以从检测到的光强度也可以对检测到的物体有初步判断。
图7展示了通用的高精地图制作流程。首先陀螺仪（IMU）及轮测距器 （Wheel Odometer）可以高频率地给出当前无人车的位置预测，但由于其精确度原因，位置可能会有一定程度偏差。为了纠正这些偏差，可以使用传感器融合计技术（比如使用Kalman Filter) 结合GPS与激光雷达（LiDAR）的数据算出当前无人车的准确位置。然后根据当前的准确位置与激光雷达的扫描数据，把新数据加入地图中。
图7 高精地图计算架构
公式1是个高度简化的高精地图计算模型, Q代表优化方程，z代表激光雷达扫描出的点，h为方程预测最新扫描点的位置与反光度，m为扫描到的点在地图中的位置，x代表无人车当前位置。这个方程的目的是通过最小化J求出测量点在地图中的准确位置。在计算模型中，m与x开始都是未知的，可以先通过多传感器融合求x，再求出测量点在地图中的准确位置m。
如上文所述，高精度电子地图包含大量的行车辅助信息，包括路面的几何结构、标示线位置、周边道路环境的点云模型等。有了这些高精度的三维表征，无人驾驶系统就可以通过比对车载GPS、IMU、LiDAR或摄像头的数据来精确确认自己当前的位置，并进行实时导航。
无人车对可靠性和安全性要求非常高，所以我们默认已由高精度LiDAR和多种传感器融合建好了地图，在这个前提下，再谈一谈无人车的跟踪和定位技术。
无人车定位主要通过粒子滤波进行。所谓粒子滤波就是指：通过寻找一组在状态空间中传播的随机样本来近似表示概率密度函数，用样本均值代替积分运算，进而获得系统状态的最小方差估计的过程，这些样本被形象地称为“粒子”，故而叫粒子滤波。比较常见的（如在Sebastian Thrun的经典无人车论文中）是粒子滤波维护一个姿态向量（x, y, yaw），默认roll/pitch相对足够准，运动预测可以从IMU中取得加速度和角速度。粒子滤波需要注意样本贫化和其他可能的灾难定位错误（catastrophic error），一小部分粒子可以持续从现在GPS的位置估计中获得。正如前文所说，对样本数量的自适应控制也需要根据实际情况有效调整。
因为已经有了高精度LiDAR点云地图，所以很自然地就可以用实时点云数据和已经建好的地图进行匹配。而3D点云匹配必然要说到Iterative Closest Point (ICP)，ICP的目标是在给出两组点云的情况下，假设场景不变，算出这两组点云之间的pose。最早的ICP原理，就是第一组点云的每个点在第二组点云里找到一个最近的匹配，之后通过所有的匹配来计算均方误差（MSE)，进而调整估计的pose，这样进行多次迭代，最终算出两组点云的相对pose。因此，预先有地图的情况下，用实时的点云加上一个大概pose猜测就可以精准算出无人车的当前pose，且时间相邻的两帧点云也可以算出一个相对pose。
另一方面，因为无人车是个复杂的多系统融合，所以当前标配是LiDAR，Camera、IMU（六轴陀螺仪）都必须拥有。拥有了Camera和IMU，做各种VO (Visual Odometry)和最近的VIO （Visual Inertial Odometry）SLAM就是自然选择。前面提到的粒子滤波，还有各种版本的卡尔曼滤波，加上Graph和关键帧概念，都属于SLAM范畴。笔者之前曾详细介绍了SLAM的各种应用探讨和相对应的工程细节 (参见《SLAM刚刚开始的未来》），在此不再一一讨论，但值得注意的是，多传感器多信息源融合只要算法正确并工程实现扎实，效果一定会比单一传感器要好。举两个具体的例子：ICP虽然后来有了很多改进(比如point-to-distance的测量改进，又比如用kd-tree加速查找改进)，但需要很好的初始化pose，否则ICP很容易掉入局部最优而搞不定全局最优，这时非常需要图像视觉补充。图像的特征点提取描述计算可以让匹配更精准，速度也不慢，但距离太远精准度会下降，而且有很多图像视觉无法搞定的情况（比如无人车或者别的物体阴影，又比如光照变化，获取illumination-invariant特征非常困难），所以笔者认为，多传感器多信息源融合不是“让它变好”，而是“没你不行”。更明显的是，GPS在户外已经很可靠，没有理由不用它先告诉无人车的大概位置。
跟踪和定位技术还是被动的感知方案，而真正意义的无人车也就是全自主驾驶而不是辅助驾驶需要无人车自己智能地来做路径规划，这里从技术层面略作探讨。
路径规划是个范畴很大的话题，需要先做几个限定：一是地图已知，如果未知，就无“规划”可言，机器人或无人车如果完全对世界未知，那么问题实际是“SLAM+探索”；二是对无人车领域来说，一般还是2D或2.5D地图，而不是在3D地图上六个自由度运动规划（那是室内全自主无人机飞行)；三是路径规划默认无人车按照规划的路径每一步执行后的pose准确，也就是说，这里刻意把定位和路径规划分开，但实际工程中这两者紧密联系，因为如果定位不准，路径规划一定会受影响。
即使有了这几个设定，路径规划本身有多个教科书版本。这里简单谈有代表性又被广泛应用的两种。一是明确寻找最佳路径的搜索A*算法，核心理念是：如果有最好的路径便一定将其找到。如果单位路径成本（cost）不一样，最好的路径不一定是最短的。A*是搜索了所有可能后，选择了最好的，而且运用了启发式算法来决定。其数据结构实现是priority queue，不停选取“最小成本”节点来扩建路径。
另一类是基于抽样（sampling based）的路径规划——并不知道最优路径是什么，所以从起点开始随机抽样（怎么随机很有讲究）来扩建可能的路径集。有一个很重要的因素可以加速抽样——障碍物的检测。若遇到障碍物，在其方向再扩建路径便没有意义。典型的算法是RRT (Rapidly-exploring Random Tree)。但需要注意，这种算法侧重有效率地让树往大面积没有搜索过的区域增长，实际运用中（特别是在无人车应用中），如果有了启发式算法，实时的路径规划很注重效率，需根据实际情况优化。这方面的研究包括RRT变种或两类算法的结合（如A*-RRT）。
笔者想强调：在无人车工程实现中，路径规划一定要根据传感器情况和地图质量来做实际算法选择和调整。无论地图有多准，传感器的数据质量如何，优化永远需要在安全的前提下进行。
高精度电子地图的信息量与质量直接决定了无人驾驶系统的安全性、可靠性，以及效率。与传统电子地图不同，高精地图更精准（厘米级），更新更快，并且包含了更多信息（语义信息）。由于这些特性，制作高精地图并不容易，需要使用多种传感器互相纠正。在初始图制作完成后，还需要进行过滤以降低数据量达到更好的实时性。在拥有了这些高精度地图信息后，无人驾驶系统就可以通过比对车载GPS、IMU、LiDAR或摄像头数据来确认当前的精确位置，并进行实时导航。
作者简介：
陈辰，斯坦福大学电子工程博士，研究方向大数据挖掘、计算几何，以及机 器学习。期间主要侧重的应用方向包括基于分布式传感器数据的地图 更新与重建。目前就职于DeepMap并从事面向无人车的高清地图开发。
刘少山，PerceptIn联合创始人。加州大学欧文分校计算机博士，研究方向智能 感知计算、系统软件、体系结构与异构计算。现在PerceptIn主要专注 于SLAM技术及其在智能硬件上的实现与优化。
