生成、更新和增强大比例尺高精度3D道路地图和多级道路图的系统和方法

摘要

本申请涉及从对应于现实世界空间内的一个或以上区域的一个或以上源获取点云数据的系统和方法，点云数据表示在一个或以上区域内检测到的结构的表面特征；基于点云数据定义至少两个一级节点，获取的点云数据对应的单个一级节点对应一个或以上区域中的单个区域；识别两个或以上一级节点之间的连接，两个或以上一级节点之间的连接基于两个或以上一级节点对应的区域的点云数据之间的连接；定义至少两个二级节点，单个二级节点对应于已识别连接的一级节点的聚合子集。

说明书

技术领域

本申请一般地涉及建筑地图和道路图，更具体地，本申请的一些实施例涉及生成、更新和增强大比例尺高精度3D道路地图和多级道路图。

背景技术

综合态势感知对于可导航技术的有效运行至关重要，其中包括智能车辆、路由和建模应用、应急响应和规划技术等。例如，对于自动驾驶汽车，综合态势感知是他们的导航能力、智能响应环境，以及其他更高级的功能的关键。道路地图和道路网络图提供了可以以多种方式使用的信息，例如，使用户能够以智能方式从一个地理点导航到另一个地理点(例如，通过识别提供A点和B点之间的道路上最短路径的路线等)。传统的3D道路地图由详细描述道路地形的3D点云组成，但当前的系统在提供大比例尺绘制的环境的高分辨率方面能力有限。也就是说，操作、计算和管理的限制决定了传统地图要么是大比例尺和低分辨率，要么是小比例尺和高分辨率。迄今为止，传统制图技术缺乏以高分辨率和高精度(例如厘米级或更好)生成、管理和更新大比例尺地图(例如，大到足以涵盖整个城市或更多)的能力。本申请提供了克服现有技术中的这些不足并能使一种系统和方法生成高分辨率的大比例尺地图以及表示同样内容的道路图的技术。

实施例的简要概述

本申请包括用于生成高分辨率的大比例尺地图以及表示同样内容的道路图的系统和方法。根据一个或以上实施例，本申请的示例系统可以包括：一种系统，包括：一个或以上处理器；存储指令的存储器，当由一个或以上处理器执行时，该指令使系统：从对应于现实世界空间内的一个或以上区域的一个或以上源获取点云数据，点云数据表示在一个或以上区域内检测到的结构的表面特征；基于点云数据定义至少两个一级节点，对应于获取的点云数据的单个一级节点对应于一个或以上区域中的单个区域；识别两个或以上一级节点之间的连接，两个或以上一级节点之间的连接基于两个或以上一级节点对应的区域的点云数据之间的连接；以及定义至少两个二级节点，单个二级节点对应于已识别连接的一级节点的聚合子集。

根据一些实施例，本申请的系统可以配置为：基于对应于节点的区域相关联的点云数据的姿态参数，识别一级节点的一个或以上姿态参数；基于对应于节点的区域相关联的点云数据相关联的GPS或IMU数据中的一个或以上，识别一级节点的一个位置参数；和/或将一级节点的点云数据与地图对齐，对齐基于一个或以上识别的姿态参数和位置参数。

根据一些实施例，存储器可以进一步存储指令，当由一个或以上处理器执行时，该指令使系统：识别对应于至少部分重叠的区域的两个或以上一级节点；按照约束将两个或以上一级节点对齐在一起。在进一步的实施例中，存储器还可以存储指令，当由一个或以上处理器执行时，该指令使系统：计算具有地图的一级节点的点云数据对齐的准确度分数；以及和/或如果一级节点的对齐的准确度分数满足预定义的高质量阈值，则锁定一级节点的位置参数和姿态参数中的一个或以上。

类似地，在一些实施例中，存储器还可以存储指令，当由一个或以上处理器执行时，该指令使系统：计算两个或以上一级节点之间的对齐的准确度分数，准确度分数的计算基于用于测量点云之间拟合质量的预定标准；和/或如果一级节点的对齐的准确度分数满足预定义的高质量阈值，则锁定两个或以上一级节点中的一级节点的位置参数和姿态参数中的一个或以上。

在一些实施例中，对应于两个或以上一级节点的区域的点云数据之间的前述连接包括区域之间的重叠区域中的匹配特征。

根据一些实施例，存储器还可以存储指令，当由一个或以上处理器执行时，该指令使系统：基于构成二级节点的一级节点的子集之间的连接，调整二级节点的姿态或位置中的一个或以上；和/或基于对应于一级节点的两个子集的两个二级节点之间的连接，调整一级节点的两个子集中的每个一级节点的姿态或位置中的一个或以上。

在更进一步的实施例中，存储器还可以存储指令，当由一个或以上处理器执行时，该指令使系统：确定新获得的点云数据是否表示由较早获得的点云数据表示的区域内的结构变化；和/或如果新获得的点云数据表示超过用于测量变化的预定义阈值的变化，则用新获得的点云数据更新地图。

本申请还扩展到用于提供本文公开的特征的方法。根据一些实施例，本申请提供了一种方法，包括：从对应于现实空间内的一个或以上区域的一个或以上源获得点云数据，点云数据表示在一个或以上区域内检测到的结构的表面特征；基于点云数据定义至少两个一级节点，对应于获得的点云数据的单个一级节点对应于一个或以上区域的单个区域；识别两个或以上一级节点之间的连接，两个或以上一级节点之间的连接基于两个或以上一级节点对应的区域的点云数据之间的连接；定义至少两个二级节点，单个二级节点对应于已识别连接的一级节点的聚合子集。

附图说明

根据一个或以上不同的实施例，本文公开的技术，参照所包含的附图进行详细描述。附图包括仅为说明目的而提供且仅描绘所公开技术的典型或示例实施例的附图。这些图被提供以便于读者对所公开的技术的理解，并且不应被认为是限制其宽度、范围或适用性。应该注意的是，为了清楚和便于说明，这些图不一定按比例尺绘制。

图1示出了根据本申请的一个或以上实施例的示例系统。

图2A示出了根据一个或以上实施例的一个符号图，该符号图描绘示例远程设备扫描现实世界环境，然后将收集的信息传递到本申请的计算系统，该计算系统接着生成包括表示现实世界环境中的区域的多个节点的道路图。

图2B示出了图2A中的相同符号图，其中包括由聚合的一级节点构造的二级节点的道路图的附加描述。

图3A示出了根据本申请的实施例的在本申请的合并操作之前的示例道路图，描述了覆盖映射的现实世界环境的道路网络。

图3B示出了根据本申请的实施例的在本申请的合并操作之后的示例道路图，再一次描述了为覆盖图3A中所示的相同道路网络。

图4A示出了根据本申请的一个或以上实施例生成的沿道路的示例点云。

图4B示出了根据本申请的一个或以上实施例生成的沿道路的示例点云。

图5A示出了根据本技术的一个或以上实施例构造的示例3D点云地图。

图5B示出了根据本技术的一个或以上实施例构造的道路地图的示例2D投影。

图6A示出了根据本申请的一个或以上实施例的自下而上优化流程的符号表示。

图6B示出了根据本申请的一个或以上实施例的自上而下优化流程的符号表示。

图7A示出了根据本申请的一个或以上实施例的合并操作的符号表示，其中较小且较低准确度的图与较大且较高准确度的图合并。

图7B示出了根据本申请的一个或以上实施例的合并操作的符号表示，其中，两个高质量图合并在一起。

图8示出了表示可以根据本申请的一个或以上实施例实现的过程的操作流程图。

图9示出了表示可以根据本申请的一个或以上实施例实现的过程的另一操作流程图。

图10示出了可以实现本文描述的任何实施例的计算机系统1000。

附图不旨在穷举或将本发明限制于所公开的精确形式。应当理解，本发明可以进行修改和变更来实施，所公开的技术仅受权利要求及其等同物的限制。

具体实施方式

信息的数据库可以以图形方式表示。包括地理区域(例如，城市)的视觉信息的数据库可以由包括节点(例如，地理区域内的位置相关联的图上的点)和边(例如，图上的线条表示节点之间的关系或连接)的图来表示。可以基于两个或以上节点相关联的视觉信息(例如，公共对象)之间的关系，在两个或以上节点之间建立边。节点可以与指示节点与图的其他元素(例如，其他节点、边、地理信息等)的关系的属性(节点属性)相关联。例如，节点属性可以包括指示姿态、边界框、边、位置、名称或ID的信息，以及其他信息。边可以与指示由给定边连接的两个节点之间的关系的属性(例如，边属性)相关联。例如，边属性可以指定第一节点相关联的区域内的对象的部分也在第二节点相关联的区域内。有关这种关系的信息可以与优化操作中的约束和边界条件结合使用。

指示姿态的信息可以包括节点自身相对于坐标系的姿态细节，和/或在图像捕获期间使用的传感器相对于相同或不同坐标系的姿态细节等。指示边界框的信息可以包括节点的边界框的细节(例如，与节点对应的现实世界环境中的地理边界)。指示边的信息可以包括将节点与其他节点连接的边的细节(例如，定义边的约束，用于在节点之间建立连接的匹配信息等)。表示位置的信息可以包括节点的位置细节，例如，在坐标系的上下文中。例如，位置细节可以包括与节点对应的地理位置的GPS细节(例如，精确定位给定节点的一个中心点或在边界框内或沿着边界框的其他点的GPS位置、定义给定节点的边界框的GPS范围、对应于节点的街道名称/地址)。指示名称的信息可以包括节点本身的名称/ID细节，或者落入对应于节点的区域内的对象。例如，名称/ID详细信息可以包括节点名称或ID号、落入给定节点相关联的地理区域内的建筑物或其他结构的名称或ID，等等)。

图1描述了可以根据本申请的一个或以上实施例实现的系统10。如图所示，系统10可以包括一个或以上计算系统12，其经由链路50通过网络42与一个或以上远程设备45和一个或以上外部资源44通信耦合。计算系统12可包括配置有机器可读指令的一个或以上硬件处理器，所述机器可读指令在执行时实现本文公开的技术的一个或以上特征。如图所示，计算系统12可以包括图形生成器单元20、通信电路38和电子存储器36中的一个或以上。图形生成器单元20可以包括获取代理21、对齐实用程序22、准确度评估实用程序23、聚合实用程序24、合并实用程序26、优化引擎和更新引擎等组件。

图形生成器单元20配置为生成包括节点层次结构的道路图，该节点的层次结构包括两个或以上节点-例如，第一级的节点和一个或以上更高级的节点。在一些实施例中，在层次结构中，任何给定的更高级的节点具有比它下面的级更少的节点数量和比它上面的级(如果有的话)更多的节点数量。第一级(即层次结构的最低级)的节点对应于被映射的地理区域内的单个区域。这样的区域可以是给定应用所需的任何大小，并且可以基于任何数量的因素(例如，相机类型、道路剖面、距离、速度限制、处理能力、流量等)来确定对应于任何给定节点的区域的大小。另外，这样的区域可以重叠相邻节点。换言之，第一级的相邻节点与重叠区域相关联。在一些实施例中，单个节点可对应于物理环境中在一个或以上方向上跨越约100至200米之间的区域。在其他实施例中，单个节点可以对应于跨越大于或小于100米的区域。层次结构最低级(即第一级)的节点包括表示区域内的对象或其他结构的表面的3D点云。

获取代理21配置为获得点云数据并将这样的数据(或这样的数据的表示)馈送到图形生成器单元20以使得图形生成器单元20能够构建第一级的节点。这样的节点累积可能涉及在地理区域内为先前未映射区域添加新节点，以新的或附加的点云数据更新图的当前节点，以及相对于先前获得的点云数据和节点信息(例如姿态，位置等)的这种点云信息的注册。获取代理21可以从任何源获得点云数据。在一些实施例中，获取代理21可以与一个或以上远程设备45通信耦合，所述一个或以上远程设备45包括用于扫描现实世界环境和/或生成代表此类现实世界环境内的表面的点云的传感设备46。如图所示，这样的远程设备45可以与移动系统(例如车辆)耦合，该移动系统可以在感兴趣的地理区域(即，被映射的区域)的整个环境中移动。例如，为了给城市诸如洛杉矶构建道路图，当一辆或多辆配备LiDAR的车辆沿着洛杉矶市区范围内的道路行驶时，获取代理21可以从它们获取点云数据。

此类工具可能包括输出点云数据的任何类型的成像设备(例如，LiDAR检测系统)或输出可用于生成点云数据的其他数据的成像设备(例如，输出环境立体图像的立体成像系统，该立体成像系统可以使用计算机视觉技术来创建成像环境的点云)。获取代理21还可以用于获得除点云数据之外的数据(例如，立体图像数据)并从这些之外的数据生成点云数据。换言之，获取代理21可以单独或与图形生成器单元20的其他元件一起应用计算机视觉操作以从接收到的不是点云形式的数据生成点云数据。

图2A象征性地展示了示例远程设备扫描现实世界环境，将收集到的信息传递到计算系统12，计算系统12接着生成包括表示现实世界环境内的区域的多个节点的道路图。在所示示例中，远程设备45是配备有LiDAR系统46的车辆，所述系统在其扫描范围47内沿道路扫描环境，并在沿道路行驶时(例如，沿着街道102，转向右转街道104，然后再次右转到街道106，然后再次右转到街道108并返回其起始位置)生成点云数据。远程设备45扫描环境并生成点云数据，然后将这样的点云数据(或其表示)传输到系统12以供图形生成器单元20获取和处理。图形生成器单元20可以生成包括节点的道路图200由覆盖现实世界空间(例如3D空间)的特定区域的点云组成。在图2A的道路图200的示例说明中，节点可以由点(例如，点201b)表示，并且对应于该节点的区域可以包括由虚线边界框(例如，边界框201a)围绕点201b，并且相邻或附近节点的区域之间的重叠区域由交叉影线区域(例如，交叉影线区域220)表示。道路图200中的节点之间的线表示基于节点之间的关系(这里，重叠区域)的节点之间的连接(也称为“边”)。

尽管本申请不要求，但是为了简单起见，图2A中所示的节点相关联的区域是统一的形状(正方形)和大小。为了更清楚，在图2A的图例中示出了单个点201b和边界框201a以提供相同点的描述，而没有示例道路图中所示的重叠区域。然而，应当理解的是，构成与节点对应的区域的空间体积可以被任何边界构造包围，它不必是立方体，也不必与其他节点的区域一致，也不必与其他节点的区域相同或相似大小等。进一步理解，虽然所述描述是道路图的简单二维局部视图，但包围区域的边界框201a是三维的(例如，立方体或其他3D形式)。如图所示，道路图200示出了与区域201a-212a对应并由点201b-212b表示的一系列十二个节点201-212。

因为相邻节点的点云重叠(如上所述)，从一个相邻节点到下一个节点的点云可以基于两个节点之间可用的信息对齐或以其他方式连接。这在本文中称为注册。对齐实用程序22配置为对点云执行对齐操作以将它们与给定的坐标系(例如，全球坐标系)对齐和/或对点云执行注册操作以对齐，或增强地图中两个或以上连续点云之间的对齐。对齐实用程序22配置为执行操作以实现跨多个节点的感兴趣的地理区域内的环境的3D地图的有效构建。

为了对齐或“注册”点云，可以采用各种算法。例如，在一些实施例中，对齐实用程序22可以应用迭代最近点(ICP)算法来估计点云数据的3-D刚性变换，并基于刚性变换执行点云注册操作。在一些实施例中，这样的算法可以使用第一点云作为参考(例如，常数)，然后将估计的变换应用于原始的第二点云。在一些实施例中，这可能涉及识别用于将第二点云与第一点云对齐的刚性变换，然后使用刚性变换将第二点云变换到由第一点云定义或第一点云相关联的参考坐标系。

准确度评估实用程序23配置为确定节点姿态和/或对齐的准确性。准确度评估实用程序23可以基于一个或以上准确度参数做出这样的确定。这些参数可以包括但不限于：(i)给定节点或节点集的对齐前姿态和对齐后姿态之间的差异(差异越大表示准确度越低，差异越小表示准确度越高)，(ii)点云中对象或特征的方向、尺寸或比例与区域中已知的现实世界对象或特征的一致性(点云中的对象或特征与已知的现实世界的对象或特征之间的参数更接近，表明准确度更高)——例如，与节点2相关联的点云对象的尺寸相比，与节点1中与停止标志相关联的点云对象的尺寸更一致的停止标志的已知尺寸表明节点1的姿态和/或对齐可能比节点2更准确，(iii)给定节点的姿态或对齐相对于已知(或已确定)相对于全球坐标系具有高度准确姿态或对齐的已连接节点之间的差异等。

在一些实施例中，注册的质量取决于多种因素，当系统10例如从远程设备45或外部资源44经由获取代理21获得新的或附加的信息时，可以对其进行优化。优化引擎27可以配置为基于约束将优化操作应用到点云数据，约束被关于结合两个或以上节点之间的关系的因子所定义。在一些实施例中，优化可以是使与一个或以上因子相关的约束的误差最小化的过程。这里可能有多种类型的约束和/或因子。

例如，因子可以包括与两个相邻第一节点相关联的两个点云的公共点之间的平均距离；针对此类因子定义的约束可能是要求公共点之间的平均距离小于特定值(例如，平均距离≤3个距离单位)；并且优化操作可能涉及调整点云的相对位置，使得它们以实现最佳或接近最佳结果的方式对齐，最佳结果由与节点相关联的点云中的公共点之间的平均距离给出。

以上只是因子、约束和优化操作的一个示例。也可以根据需要使用和定义其他因子和/或约束，以形成特定优化操作的基础。其他这样的因子可以包括数据噪声、节点的姿态参数、与获取的对齐的点云相关联的车辆的姿态信息、GPS信息、IMU信息，以及来自与节点对应的区域内的对象或特征信息(例如，已知的物体大小、尺寸、位置等)；计算来用于对应于上级节点的相关第一节点的集合的对齐分数等。

其他此类约束(例如，限制定义了一个因子的限制，该因子定义了两个或以上节点的点云之间可能的对齐后的关系集)可以包括两个或以上节点的公共点之间的中值距离点云小于特定值；位于彼此特定距离内的两个或以上点云中的公共点数。优化操作可以为点云之间的对齐定义目标结果，并且可以对点云之间的对齐进行调整以实现目标结果，或者得出一个比另一个可能的结果更接近目标结果的结果。例如，在节点相对于其原始位置不能移动超过预定义量的约束下(或者它的姿态不能相对于其原始姿态被重新定向超过预定义量)，优化操作可以为点云之间的对齐定义目标结果，以最小化相对于原始状态的位置或方向的变化。

其他优化操作可以包括，仅作为示例，最小化与两个或以上点云相关联的姿态参数之间的差异、最大化两个点云之间的重叠等。应当理解的是，“优化操作”可以指达到在约束范围内最小化或最大化特定变量的结果的操作。然而，还应当理解的是，本文使用的“优化操作”还可以指实现比约束范围内的另一个可能结果更接近目标结果的结果的操作，但不一定最小化或最大化作为约束主题的给定变量。也就是说，优化操作可以配置为简单地减少作为约束对象的变量——例如，减少公共点之间的平均距离，但不一定“最小化”这样的距离。例如，优化操作可以配置为调整点云对齐，使得与使用先前优化操作实现的先前对齐相比，公共点之间的平均距离减小。在一些实施例中，优化操作可以配置为调整点云对齐，使得公共点之间的平均距离保持在预定值范围内。

聚合实用程序24配置为通过聚合来自节点层次结构中它下面的级的两个或以上相邻节点来生成或定义上级节点。为了识别可能适合聚合以生成或定义更高级的节点的一个级中的节点，聚合实用程序24可以确定较低级的哪些节点共享共同特征或以其他方式连接。例如，聚合可以识别一组10个第一节点，沿着城市道路网络中一条道路的一部分，每一个节点都与下一个节点相邻。在该示例中，因为每个第一节点与所考虑的十个节点中的至少一个其他第一节点重叠，所以节点可以被聚合并且被认为是节点层次结构中更高级的单个节点。因此，在每个连续的级上，道路图都可以简化，从而产生几个优点。例如，可以更有效地优化道路图。例如，为了优化整个道路图，可以首先在较高级的节点上执行优化操作，从而一起优化整组较低级的节点(而不是每个节点单独地)。

在一些实施例中，可以将聚合设计为一个道路网络。例如，从一个路口到另一个路口的道路上的第一个节点可以聚合为二级节点。进一步扩展该技术，然后可以聚合特定区域(例如数十或数百公里)的道路以生成或定义三级节点。正如第一个节点可以连接是因为它们彼此相邻并且在它们的点云中至少有一些重叠一样，如果有两个或以上上级节点在它们的点云中至少有一些是重叠的，则它们可能会被连接——也就是说，在第一个二级节点的至少一个第一节点(这里也称为子节点)与第二个二级节点的至少一个第一节点重叠，随着层次结构的继续，对于N级节点，以此类推。图2B显示了由所提出的技术生成或定义的二级节点的示例集，通过聚合多个一级节点来构建。再次，正如在图2B中，道路图300中的节点之间的线代表基于节点之间的关系(这里叫做重叠区域)的节点之间的连接(也称为“边”)。应当理解，任何两个上级节点之间的连接的准确性(或强度)随着给定上级之下的级中的连接增加而变得更大(例如，如果存在更多的下级重叠，则节点之间的连接会更强)。

图2B展示了上面介绍的例子，参考图2A，这里描述了另一个级的节点(例如，一个二级节点)，它可以通过聚合两个或以上连接的较低级节点(例如，一个一级节点)来生成或定义。道路图300描绘了一个二级节点301-304。节点301对应于边界框301a所围成的区域相关联的点云数据，边界框301a是由聚合实用程序24对两个或以上连接节点进行聚合构造而成。

例如，如图2B所示，二级节点301b是由边界框301a所围成区域相关联的点云数据组成，对应于现实世界环境100中所描绘的102路沿线的道路图200的边界框201b-204b所围成区域的点云数据的聚合；二级节点302b包含边界盒302a所围区域相关联的点云数据，该点云数据对应于现实世界环境100中所描绘的104公路沿线的道路图200的边界盒205b-206b所围区域相关联的点云数据的聚合；二级节点303b包含边界框303a所围区域相关联的点云数据，该点云数据对应的是现实世界环境100中所描绘的道路图200中沿106路的边界框207b-210b所围区域相关联的点云数据的聚合；二级节点304b包含与边界框304a所围区域相关联的点云数据，该点云数据对应于现实环境100中描绘的108路沿线的道路图200的边界框211b-212b所围区域相关联的点云数据的聚合。根据聚合实用程序24所希望/应用的标准，可以选择任何连接的低级节点的组合来构建上级节点。文中指出,当前技术延伸到N级节点,根据比例尺所需的映射(例如,道路图对应一个小城市的地图)有可能只是一级节点(也称此为第一个节点)和二级节点；对于一个大城市地图对应的道路图，可能有一级、二级、三级节点；对于对应于整个州地图的道路图，可能存在一级、二级、三级和四级节点；对于对应于多个州地图的道路图，可能存在一级、二级、三级、四级和五级节点等。

现在回到图1，在一些实施例中，系统10可以包括许多远程设备46，其将点云数据发送到计算系统12以填充到地图中。周期性地，多个远程设备45将覆盖同一区域，或者在某些情况下，同一远程设备45可能多次覆盖同一路线。在这种情况下，可以生成覆盖基本相同空间的多个节点。代替保留覆盖基本相同区域的单独定义的节点，合并实用程序26可以被配置为确定两个或以上定义或生成的节点何时覆盖基本相同的区域并实现合并操作。

合并操作将两个重复节点的点云数据合并为一个节点，从而简化道路图的节点表示，并增密点云以丰富给定区域内的映射结构。因此，当道路图的节点被锁定时，可以通过合并覆盖基本相同空间的附近节点来简化图，同时仍然保持更广泛的道路网络结构。因此，与给定区域相关联的点云数据可以(例如，通过合并实用程序26)与同一区域的其他点云数据合并以简化/减少覆盖被映射空间所需的第一节点的数量，并且还可以增密与道路图中这些第一节点相关的点云。在图3A-3B提供的图示中表示了这种合并操作的示例。

图3A表示了合并操作之前的示例道路图，表示了覆盖根据本申请映射的现实世界环境的道路网络。图3B示出了根据本申请的合并操作之后的示例道路图，再次示出覆盖图3A中所示的相同道路网络。

如示例道路图所示，图3A描绘了基于从至少两个远程设备45获取的点云数据生成或定义的一系列节点，这些点云数据已捕获在一些情况下覆盖大致相同区域的点云数据。例如，图3A中的白点215可以对应于沿着第一条路径的点云数据，图3A中的蓝点216可以对应于沿着第二条路径的点云数据，并且图3A中的黄点217可以对应于沿第三条路径的点云数据。如图3A所示，一些节点彼此非常接近，这可能是例如当不同的远程设备45(车辆)在同一道路上的不同车道行驶时收集点云数据的结果，从而从它们生成的节点离开并略微移位，但点云仍然覆盖基本相同的空间(或相同的相关空间)。合并实用程序26可以合并来自此类重复节点的点云数据，从而简化/减少用于表示道路图特定部分的第一节点的数量，同时以对与剩余/结果节点(即数据合并到的节点)相关联的点云进行增加密度和增强的方式保留来自所有节点的信息。

图3B表示了合并实用程序26应用了一个或以上合并操作之后的简化道路图。如图所示，许多白点215(代表节点)已经合并成蓝点216(代表其他节点)或黄点217(代表其他节点)；类似地，许多蓝点216(代表节点)已合并为白点215(代表其他节点)或黄点217(代表其他节点)；并且类似地，许多黄点217(代表节点)已经合并成蓝点216(代表其他节点)或白点215(代表其他节点)。总之，由合并实用程序26实现的合并操作组合了来自覆盖基本重复空间区域的节点的点云数据，并且仅用来自其他重复节点的点云数据填充这样的节点之一。

仍然参考图3B，但是现在回到上面介绍的聚合实用程序24，图形生成器单元20可以通过聚合连接的低级节点来定义或生成更高级的节点。例如，图形生成器单元20的聚合实用程序24可以聚合由白点215表示的所有节点以构建单个二级节点；聚合实用程序24可以进一步聚合由蓝点216表示的所有节点以构建另一个二级节点；聚合实用程序24可以进一步聚合所有由黄点217表示的节点以构建另一个二级节点。因此，图3B中所示的道路图可以被进一步简化，并且仅由所述较低级节点组成的三个二级节点表示。

在某些情况下，在一个或以上节点相关联的一个或以上区域内存在结构变化，并且可能需要对道路图和地图进行更新。为了以智能方式提供这样的更新，图形生成器单元20可以配备更新引擎28。

更新引擎28配置为检测何时已经被映射的区域获取的新点云信息与先前的点云信息足够不同以授权对地图进行更新。新的点云信息是否“足够不同”可能取决于所需的应用程序，以及某些更新对使用地图的应用程序的重要性。例如，对于一个简单的地图路由应用程序，用户可能正在跑步以帮助他们从一个位置开车到另一个位置(例如，谷歌地图)，在道路上增加一条人行道，使实际道路变窄四英尺，这可能被认为不足以授权对地图进行任何更新。然而，另一方面，道路宽度的这种四英尺变化可能足够重要以需要对全部或部分使用的道路网络地图应用程序进行更新，作为道路上的智能或自动驾驶汽车作为控制道路移动的输入。因此，为了确定为已经映射的区域获取的新点云信息是否与现有的点云信息足够不同以授权更新，更新引擎28可以配置为确定与之前获取的点云信息相比所检测到的新点云信息之间的变化是否超过预定义阈值到的。预定义阈值可以由用户定义，并且可以基于任何感兴趣的标准(例如，道路结构变化、人行横道变化、交通标志变化、建筑物变化等)。在检测到足以授权更新的变化时，更新引擎28可以为相应的节点实现更新——不管是用新的(例如，对于被移动或被移除的结构，例如被移除的桥)替换旧的点云数据，还是将新点云数据与旧点云数据合并(例如，仅用于添加，例如新的停车灯)。通过这种方式，涉及对点云进行重大更改的更新仅在需要时填充到地图框架中。

图4A示出了先前获得的点云数据410(以第一种颜色表示)和新获得的点云数据412(以第二种颜色表示)的区域的点云。新获得的点云数据412可以包括与先前获得的点云数据不同的点、相似点或重复点。出于图4A-4B的目的，应当理解，以绿色示出的点来自先前获得的点云数据，蓝色的点是相对于先前获得的点云数据410的重复点(或相似点)，并且红色的点是表示相对于先前获得的点云数据发生显著变化的不相似的点。

如图4A所示，图4A示出了区域的点云，其中先前获得的点云数据410以第一种颜色显示(以绿色表示)并且新获得的点云数据412以第二种颜色显示(以蓝色表示)。新获得的点云数据412可以是相对于先前获得的点云数据410的重复点或相似点(例如，蓝色点是先前点的重复(如果没有重叠的蓝色，它将显示为绿色)，或先前获得的点云数据410足够类似(例如，基于预定义的阈值例如相似性阈值来确定，以形成这种确定的基础))。这种重复或相似的点云数据可由更新引擎28确定为无关紧要的以致于对地图进行更新是不必要的。

如图4B所示，图4B示出了一个区域的点云，其中先前获得的点云数据410以第一种颜色显示(以绿色表示)并且新获得的点云数据414以第二种颜色显示(以红色表示)。新获得的点云数据414可能与先前获得的点云数据410不相似(例如，红色点与先前的点不相似(例如，基于预定义的阈值例如相似性阈值来确定，以形成这种确定的基础))。这种不相似的点云数据可以由更新引擎28确定为足够重要以致于对地图进行更新是必要的。

图5A示出了根据本技术的一个或以上实施例构造的示例地图。地图510是具有厘米级分辨率的大比例尺地图的示例。图5B表示了根据本技术的一个或以上实施例构造的示例地图。地图512是根据本技术的一个或以上实施例构建的道路网络的2D地图投影。

再返回参考图1，获取代理21、对齐实用程序22、准确度评估实用程序23、聚合实用程序24、合并实用程序26、优化引擎27可以用于协同工作以构建新图、优化图，合并两个或以上图或两个或以上图的片段。如前所述，优化操作可以定义点云之间对齐的目标结果，并且可以对点云之间的对齐进行调整以实现目标结果，或者比另一个可能的结果更接近目标结果的结果。通过本申请的多级节点道路图技术，可以利用上级节点进行自顶向下的优化，利用下级节点进行自下而上的优化。

优化可以在图的任何级和任何部分执行。在一些实施例中，优化引擎27执行自下而上的优化操作。当优化引擎27在定义上级节点的下级节点的聚合组上执行优化操作，然后根据下级优化操作的结果对上级节点进行更改时，发生自下而上的优化操作。图6A描绘了自下而上优化的符号表示。如图所示，优化引擎27对定义上级节点614的下级节点610的聚合组和定义上级节点616的下级节点612的聚合组执行优化操作，然后基于对下级节点的优化操作的结果传播上级节点614和616的变化。即下级节点的约束影响上级节点的优化(例如，下级节点的优化可能会推到上级节点)。

在一些实施例中，优化引擎27执行自上而下的优化操作。当优化引擎27在上级节点上执行优化操作时根据上级节点的操作结果在定义上级节点的下级节点中改变发生自上而下的优化。图6B描绘了自上而下优化的符号表示。如图所示，优化引擎27在上级节点614和上级节点616以及定义上级节点616的下级节点612的聚合组上执行优化操作，然后传播节点中的变化。基于对上级节点614和616的优化操作的结果来定义上级节点614和616的下级节点610和612的聚合组。也就是说，上级节点之间的约束可能会影响下级节点的优化(例如，上级节点的优化可能会推到下级节点)。

再次参考图1，如上所述，合并实用程序26可以配置为确定何时两个或以上定义或生成的节点覆盖基本相同的区域并实现合并步骤。在进一步的实施例中，合并实用程序26不仅可以配置为单独地合并或组合两个或以上节点的点云，而且还可以用于将道路图的较大部分合并在一起，其中每个部分已经包含多个节点。即合并实用程序26可以配置为通过在时间图的节点之间建立连接并基于这样的连接执行优化来构建新图；和/或合并实用程序26可以配置为通过在图的某些部分之间建立连接并基于这样的连接执行优化来将两个先前构建的图合并在一起来扩展图。无论哪种情况，准确度评估实用程序23可通过提供可用作优化中的加权因子的准确度分数来影响优化。

即，在一些实施例中，如果准确度评估实用程序23确定一个节点(在合并两个节点的情况下)或一个图(在合并图的情况下)的质量比被合并的点或图更高(即，更高的准确度)，则优化引擎27可以定义约束，使得与较低质量节点或图的初始状态(例如，位置、姿态等)相比，较高质量节点或图的状态更抵抗变化。在一些实施例中，地图质量(即，地图准确性)可以形成为可以根据本申请生成的地图和/或图形的一个或以上约束分配不同协方差的基础。

在一些实施例中，如果准确度评估实用程序23确定一个节点(在合并两个节点的情况下)或一个图(在合并图的情况下)比与其合并的节点或图具有更高的质量(例如，高准确度)，则优化引擎27可以优化较低质量节点的整个图以及来自高质量图的节点的仅仅一部分，从而使较高质量图的更大部分保持不变(例如,不变)并为低质量图的优化提供边界条件。

图7A示出了合并操作的符号表示，其中较小且较低准确度的图与较大且较高准确度的图合并。如图所示，图7A包括包含一系列节点710(黄色阴影)的高质量道路图与包含一系列节点714(蓝色阴影)的低质量道路图合并。需要优化(并因此重新对齐)的区域由虚线轮廓716表示，其中，提供边界条件的重叠区域由实线轮廓712表示。

在其他实施例中，准确度评估实用程序23可以确定寻求合并的两个节点，或者寻求合并的两个具有相似质量的图，例如都是高质量或者都是低质量。在合并两个低质量图的情况下，可以使用两个图之间的较大部分的支持区域来为优化提供边界条件。在合并两个高质量地图的情况下，两个图之间的较小部分支持区域可能会采取优化操作(以及较小数量的支持区域用于提供边界条件)。

图7B示出了合并操作的符号表示，其中两个高质量图被合并在一起。如图所示，图7A包括包含一系列节点710(黄色阴影)的高质量道路图与包含一系列节点714(绿色阴影)的另一高质量道路图合并。需要优化(并因此重新对齐)的区域由虚线轮廓线716表示，其中提供边界条件的重叠区域由实线轮廓线712表示。通过观察图7A和图7B可以理解，当两个高质量图合并时，需要优化的节点比涉及低质量图时要少。

由于准确度评估实用程序23确定节点、节点集或整个图足够准确，图形生成器单元20可以“锁定”这样的节点、这样的节点集或这样的整个图。“锁定”是指限制进一步优化或对齐。可以锁定高质量的节点，这样就不会花费更多的算力来尝试更改已经确定为准确的内容；此外，一旦一个节点、一组节点或图被锁定，它就可以用于提供边界条件，以便在其他节点、节点组或图与锁定的节点、节点组或图添加/合并时优化其他节点、节点组或图。结果是，由于准确度评估实用程序23、合并实用程序26和优化引擎27(以及在将上述应用于更高级节点时的聚合实用程序24)可以协同步骤，使得图形生成器单元20构建和扩展大比例尺高分辨率地图和相关道路图的构建和管理效率更高，优化和更新获得的计算成本更低。

图8示出了根据本申请的一个或以上实施例实现的示例方法。在操作810，方法800可以包括获得点云数据。例如，操作810可以包括从对应于现实世界空间内的一个或以上区域的一个或以上源获得点云数据，点云数据表示在一个或以上区域内检测到的结构的表面特征。在操作820，方法800可以包括构建一级节点。例如，操作820可以包括基于点云数据定义至少两个一级节点，对应于获得的点云数据的单个一级节点对应于一个或以上区域中的单个区域。在操作830，方法800可以包括识别一级节点之间的连接。例如，操作830可以包括识别两个或以上一级节点之间的连接，其中两个或以上一级节点之间的连接基于两个或以上一级节点对应的区域的的点云数据之间的连接。在操作840，方法800包括构建至少两个二级节点。例如，操作840可以包括定义对应于已识别连接的一级节点的聚合子集的单个二级节点。

在操作910，方法900可以包括获得点云数据。例如，操作910可以包括从对应于现实世界空间内的一个或以上区域的一个或以上源中获得点云数据，点云数据表示在一个或以上区域内检测到的结构的表面特征。在操作920，方法900可以包括构建一级节点。例如，操作920可以包括基于点云数据定义至少两个一级节点，对应于获取的点云数据的单个一级节点对应于一个或以上区域中的单个区域。在操作930，方法900可以包括识别一级节点之间的连接。例如，操作930可以包括识别两个或以上一级节点之间的连接，其中两个或以上一级节点之间的连接基于两个或以上一级节点对应的区域的点云数据之间的连接。在操作940，方法900可以包括构建多个二级节点。例如，操作940可以包括定义对应于已识别连接的一级节点的聚合子集的单个二级节点。在操作950，方法900可以包括优化二级节点并将这样的优化向下推到较低级的节点。例如，操作950。例如，操作950可以涉及基于对应于一级节点的两个子集的两个二级节点之间的连接来调整一级节点的两个子集中的每个一级节点的姿态或位置中的一个或以上。操作960，方法900可以包括锁定满足预定质量阈值(例如，具有超过预定数字的准确度分数)的一个或以上一级或二级节点(或更高级的节点，如果有的话)。

图10示出了可在其上实施本文描述的任何实施例的计算机系统1000的框图。计算机系统1000包括总线1002或其他用于传递信息的通信机制、一个或以上与总线1002耦合用于处理信息的硬件处理器1004。硬件处理器1004可以是例如一个或以上通用微处理器。

计算机系统1000还包括主存储器1006，例如随机存取存储器(RAM)、高速缓存和/或其他动态存储设备，耦合到总线1002用于存储信息和由处理器1004执行的指令。主存储器1006还可用于由处理器1004执行的指令执行期间存储临时变量或其他中间信息。当这些指令存储在处理器1004可访问的存储介质中时，使得计算机系统1000成为专用于执行指令中指定步骤的专用机器。主存储器1006可以包括非易失性介质和/或易失性介质。非易失性介质可以包括例如光盘或磁盘。易失性介质可以包括动态存储器。常见形式的介质可以包括，例如，软盘、软盘、硬盘、固态驱动器、磁带或任何其他磁性数据存储介质、CD-ROM、任何其他光学数据存储介质、任何物理数据存储介质、具有孔图案的介质、RAM、DRAM、PROM、EPROM、FLASH-EPROM、NVRAM、任何其他存储芯片或盒式存储器以及它们的网络版本。

计算机系统1000可以使用定制的硬连线逻辑、一个或以上ASIC或FPGA、固件和/或程序逻辑来实现本文中描述的技术，这些与计算机系统结合的技术使得或编程计算机系统1000成为专用机器。根据一个实施例，响应于处理器1004执行包含在主存储器1006中的一个或以上指令的一个或以上序列，本申请中的技术由计算机系统1000执行。此类指令可从另一存储器，例如存储设备1008，读入主存储器1006介质。包含在主存储器1006中的指令序列的执行使处理器1004执行本文描述的处理步骤。

例如，计算系统1000可用于实现图1所示的计算系统12或计算系统12的一个或以上组件。作为另一个例子，图8-9中所示并结合本申请所描述的过程/方法可以通过存储在主存储器1006中的计算机程序指令来实现。当这些指令由处理器1004执行时，它们可以执行如图8-9所示以及上面所描述的步骤。在替代实施例中，硬连线电路可以代替软件指令或与软件指令结合使用。

计算机系统1000还包括耦合到总线1002的通信接口1010。通信接口1010提供耦合到连接一个或以上网络的一个或以上网络链路的双向数据通信。作为另一示例，通信接口1010可以是局域网(LAN)卡以提供数据通信连接给兼容LAN(或与WAN通信的WAN组件)。也可以实现无线链接。

某些操作的执行可以分布在处理器之间，不仅驻留在单个机器内，还能跨多个机器部署。在一些实施例中，处理器或处理器实现的引擎可以位于单个地理位置中(例如，在家庭环境、办公室环境或服务器群内)。在其他实施例中，处理器或处理器实现的引擎可以跨多个地理位置分布。

虽然所公开原理的示例和特征已在本文进行了描述，但是在不脱离所公开实施例的精神和范围的情况下，修改、改变和其他实施方式是可能的。此外，“包括”、“具有”、“含有”和“包含”等词和其他类似形式在含义上是等效的，并且是开放式的，因为这些词中的任何一个之后的一个或以上条目不是旨在详尽列出此类条目或项目，或仅限于列出的条目。还必须注意，如本文和所附权利要求中所使用的，单数形式“a”、“an”和“the”包括复数参考，除非上下文另有明确规定。

本文示出的实施例以充分的细节进行了描述以使本领域技术人员能够实现所公开的内容。可以使用其他实施例并由此衍生，从而可以在不脱离本申请的范围的情况下进行结构和逻辑的替换和改变。因此，详细描述不应理解为限制性的，并且各种实施例的范围仅由所附权利要求以及这些权利要求所赋予的等效物的全部范围定义。