用于3D扫描之间全局配准的方法和系统

摘要

本发明提供了第一点云和第二点云之间全局配准的计算机实施方法和计算机化装置，第一点云和第二点云是扫描装置在两个独立实例的相同空间场景上获得的。该方法包括从第一点云中提取第一组判别线对和从第二点云中提取第二组判别线对，其中判别线对与随机选择的线对相比具有高判别力。在一些实施例中，然后根据与线间关系、线的几何形状和线的位置有关的一个阈值标准，以及与扫描装置的指南针误差有关的指南针角标准，来确定两组判别线对之间的多个匹配线对组。该方法还包括通过投票找到两个点云之间最可靠的对应关系，然后计算全局转换矩阵。最后，使用全局转换矩阵来对齐两个点云。本发明实施例提供准确且有效的配准，特别是对于建筑施工应用。

说明书

技术领域

本发明涉及处理三维(3D)扫描，特别涉及一种在3D扫描之间进行全局配准(global registration)的计算机化方法和系统。

背景技术

为了对来自相同空间场景的3D扫描的点云进行可视化和进一步的数据处理，必须将这些单一的扫描转换为一个公共坐标系。这个寻找空间转换以对齐3D扫描的过程称为“配准”。对于两个或多个具有共同点子集的3D点云，3D配准的目标是计算一个刚性转换(rigid transformation)，使这些点云对齐，提供它们之间相对姿态的估计。

现有的配准方法很多，但大多在鲁棒性(robustness)和处理时间上都有局限性。由于指南针数据(compass data)不稳定或其他问题，传统方法可能会在两个扫描的3D模型之间产生错位。因此，希望提供一种能够以有效方式提高配准的鲁棒性的方法和系统，从而产生这些点云之间的最佳对齐。

发明内容

鉴于上述背景，提供了替代的计算机实施的方法和装置，用于在由扫描装置获得的两个独立实例的相同空间场景上的两个点云之间的全局配准。

根据本发明的一个示例性实施例，提供了一种用于在两个独立实例的相同空间场景上由扫描装置获得的两个点云之间的全局配准的计算机实施的方法。该方法包括从第一点云中提取第一组判别线对和从第二点云中提取第二组判别线对，其中判别线对是与随机选择的线对相比具有高判别力的线对。然后确定多个匹配线对组。每个匹配线对组包括从第一组判别线对中选出的第一判别线对和从第二组判别线对中选出的第二判别线对。第一判别线对和第二判别线对满足至少一个与线间关系、线的几何形状和线的位置有关的阈值标准，以及当第一判别线对通过第一转换矩阵转换到参考坐标和第二判别线对通过第二转换矩阵转换到同一参考坐标时的指南针角标准。此外，选择第一点云和第二点云的最佳方位角，该最佳方位角是从多个匹配线对组的指南针角导出的，并根据最佳方位角、相应的第一转换矩阵和相应的第二转换矩阵的聚类，计算全局转换矩阵。然后使用全局转换矩阵来对齐第一点云和第二点云。

因此，本发明的一个示例实施例涉及一个计算机化系统，其包括处理器和连接到处理器的存储器。存储器和处理器一起被配置为使该计算机化系统执行根据上述实施例的动作。

与传统的点云配准技术相比，上述示例性实施例具有好处和优点。例如，本方法能够通过使用本发明描述的算法快速找到用于点云配准的转换矩阵并准确地对齐两个模型。

本发明的另一个优点是，计算机实施的方法对扫描装置的不稳定指南针数据具有鲁棒性。因此，在3D应用中，如建筑施工相关的应用中，可以实现智能3D建模解决方案，以显示建筑工地的全局布局。

附图说明

通过以下参考附图的详细描述，本发明实施例的上述和其他特征、优点和方面将变得更加明显。在附图中，相同或相似的附图标记表示相同或相似的元素，其中：

图1显示可以应用本发明实施例的一个示例场景；

图2是根据本发明实施例提供的两个点云之间的全局配准的方法流程图；

图3A显示从点云中提取线条以形成基于线条的模型的过程；

图3B显示从视觉角度确定匹配线对的一个实施方式；

图4A-4B显示基于线条的3D模型中的H-线和V-线，以及在这种模型的背景下的判别线对的一个示例；

图5A-5B显示线对特征的两个例子；

图6A-6B显示两个模型中由V-线和H-线组成的线对；

图7A-7B显示两个模型中由两条不平行的H-线组成的线对；

图8A-9B显示与图6A-6B中的线对有关的一个例子以及指南针角标准的应用；

图10A-11B显示与图7A-7B中的线对有关的另一个例子以及指南针角标准的应用；

图12显示在一个实施例中用于选择最佳方位角的投票方案的例子；

图13是根据本发明实施例的用于两个点云之间的全局配准的计算机化装置的示意性软件图；

图14是根据本发明实施例的用于两个点云之间的全局配准的计算机化系统的示意图。

具体实施方式

如本文和权利要求书中所使用的，术语“包括”是指包括以下要素但不排除其他要素。术语“基于”应被理解为“至少部分基于”。术语“一个示例性实施例”和“一个示例性实施方案”应被理解为“至少一个示例性实施例”。术语“另一个实施例”应被理解为“至少一个其他实施例”。

如本文和权利要求书中所使用的，“3D物体”是指在3D空间中具有姿态、尺寸和形状的任何实际物体，其可以由扫描的3D场景的点云中的多个点表示。

在本发明的点云配准的背景下，如在一个示例性实施例中，要对齐的两个点云被分别命名为“参考模型”和“场景模型”。这两个模型具有不同的姿态，并且是来自真实场景中的不同视图。换句话说，两个点云中的第一点云和第二点云是由扫描装置在两个独立的实例中扫描一个相同空间场景获得的，因此一个点云的数据与另一个点云的数据具有高度的对应性。

如本文和权利要求书中所使用的，除非另有说明，否则“耦合”或“连接”是指通过一个或多个电装置直接或间接地电耦合或电连接。

以下示例性实施例单独或组合地实施，以为不同行业(例如建筑施工、自动化)的各种应用提供点云配准的方法和系统。特别是，目前缺乏记录建筑工地的3D建模解决方案，成为该行业的一个挑战。由于扫描装置的指南针数据不稳定，传统的配准方法也经常导致两个扫描的3D模型错位。

现在参考图1，图1显示可以应用本发明实施例的一种示例性场景的图100。在该场景中，提供了一个计算机化装置110，用于在(由131和132表示的两个独立实例处的)一个相同空间场景上由3D传感器120获得的第一点云和第二点云之间的全局配准。该3D场景可以是物理环境中的任何场景。这里显示为建筑施工应用中的平面图的俯视图，其中包括一个或多个房间，如房间1和房间2。

一个或多个3D传感器120被定位以捕获3D场景的3D视觉，并与计算机化装置110连接，以向计算机化装置110提供3D场景的3D数据。计算机化装置110对3D数据进行处理，以用于点云配准，下面会详细介绍。在点云配准之后，其结果可以进一步处理，用于3D建模或其他3D应用。

可在此使用的示例性3D传感器包括但不限于3D扫描仪、数码相机和其他类型的能够捕获真实世界物体和/或场景的图像以收集关于其位置、地点和外观数据的设备。在一个示例性实施例中，采用3D扫描仪来扫描3D场景以生成点云。在一个实施例中，3D扫描仪是一个光探测和测距(LiDAR)传感器。嵌入在这类3D扫描仪中的磁指南针显示用于导航和地理定位的基本方向。但是，指南针数据可能会受到附近环境干扰的磁场影响，例如MRI扫描、大型铁或钢体和附近的电机，导致指南针数据不稳定。扫描装置的最大指南针误差可从其硬件规格中得知。

如图1所示，两个独立实例131和132用同一3D场景的两个俯视图表示，其中3D传感器120在第一实例131中位于房间1中视图1的位置，3D传感器120在第二实例132中位于房间2中视图2的位置处。在一些实施例中，3D传感器120是一个单一的设备，在不同时间放置在两个地点。在其他实施例中，两个相似类型的3D传感器120被安置在两个地点。

应当理解，3D传感器120捕捉3D场景的3D视觉，以向计算机化装置110提供3D场景的3D数据。两个独立实例131和132的3D数据可以是各自的点云。为了便于清楚地描述本发明，第一点云可以由3D传感器120为3D实例131生成，第二点云可以由3D传感器120为3D实例132生成，其中第一点云指“参考模型”，第二个点云指“场景模型”。

可以看出，两个扫描的3D模型是错位的。具有计算机化装置110的本发明实现了如方框140所示的点云配准，其中通过应用旋转和平移(R&T)过程将场景模型与参考模型对齐，从而得到如方框150所示的对齐模型。本发明实施例提供了一种更准确有效的对齐方法，以补偿低端扫描装置不稳定的指南针数据，即使是具有较大指南针误差(例如+/-30度)的低端扫描装置，也能实现良好的性能。同时，对齐的模型有助于智能3D建模方案，以显示建筑工地的骨架。

根据应用，计算机化装置110可以是独立计算机或嵌入式系统，包括但不限于笔记本电脑、台式电脑、平板电脑、智能电话、互联网设备、嵌入式设备等。3D传感器120可以与计算机化装置110在物理上分开，或者与计算机化装置110并置，或嵌入到计算机化装置110中。

现在参考图2和图3A-3B，图2显示根据本发明实施例在与图1中表示的场景相关的几个应用中的过程200，图3A-3B从视觉角度说明了过程200的一些操作。该过程可以在计算机化装置110处执行，用于全局配准或确定第一点云和第二点云之间的转换，这些点云是由扫描装置120在两个独立实例中相同空间场景上获得的。

在步骤210，从第一点云中提取第一组判别线对(discriminative line-pairs)，并且从第二点云中提取第二组判别线对，其中判别线对是与随机选择的线对相比具有高判别力的线对，如下文将详细描述。

两个点云，即参考模型和场景模型，可以由3D扫描仪在一个空间场景上在两个独立实例中获得。在本发明实施例中，点云配准是基于线对的，这允许准确且高效的配准，特别是在建筑施工应用中。

点云中的每个点由一个三维向量表示，对应于笛卡尔坐标系的X轴、Y轴和Z轴。此外，坐标系的定向方式是X-Y平面对应于测量环境的水平面，Z轴对应于垂直于X-Y水平面的垂直线。

首先，从两个点云中提取呈现直线结构的点，并将两个点云模型转换为3D空间中的两个线条模型。有多种方法可以可靠且准确地从点云中确定出线条，本领域技术人员可以应用这些方法中的任何一种来进行线条提取过程。本发明对此不作任何限制。如图3A所示，使用线条提取技术，可以将基于点的模型301转换为基于线条的模型302，以进行进一步处理。

每个模型中的线条形成一组线对(line-pairs)，其中的一个子集被确定为一组判别线对。判别线对是与随机选择的线对相比具有高判别力的线对。例如，判别力表示线对中两条线在3D空间中的相似程度。两条线在3D空间中的相似度越低，其判别力就越高。使用高判别力来选择线对进行进一步处理，可以提高模型对齐的准确性和效率。

接下来，在步骤220，在参考模型中的线对和场景模型中的线对之间确定多个匹配线对组(matching line-pair groups)。每个匹配线对组包括选自参考模型中第一组判别线对的第一判别线对和选自场景模型中第二组判别线对的第二判别线对。

在一个实施例中，匹配线对组需要满足以下两个标准。第一判别线对和第二判别线对需要满足：(a)与线间关系、线的几何形状和线的位置相关的至少一个阈值标准；(b)当第一判别线对通过第一转换矩阵转换到参考坐标并且第二判别线对通过第二转换矩阵转换到同一参考坐标时的指南针角标准。使用这些标准，可以很好地将实际指代真实3D场景中相同3D部分的参考模型中的线对和场景模型中的线对确定为潜在匹配。

图3B显示了从视觉角度确定匹配线对的一种实现方式，其中方框320表示基于线的参考模型，方框330表示基于线的场景模型。每个线模型都包含大量线对，如粗白线所示。在方框320中，两个线对321和322是判别线对，在方框330中，两个线对331和332也是判别线对。通过步骤220的匹配过程，确定线对322和线对332匹配，因此形成一个匹配线对组，而线对321和线对331不匹配，因此它们不会形成一个匹配线对组。

在一些实施例中，为了确定匹配的线对，为来自两组判别线对的每个线对计算相应的转换矩阵，使得每个线对以类似的方式根据相应轴被转换到相同的参考坐标。为来自第一组判别线对的相应线对计算的那些转换矩阵是指相应的第一转换矩阵，而为来自第二组判别线对的相应线对计算的那些转换矩阵是指相应的第二转换矩阵。

在步骤230，为第一点云和第二点云选择从多个匹配线对组的指南针角导出的最佳方位角(orientation angle)。对于包含来自参考模型的一个线对和来自场景模型的一个线对的每个匹配线对组，计算两个线对之间的方位角，表示它们在同一3D空间内的相对方位。然后从为所有匹配线对组计算的所有这些方位角中选择一个最佳方位角。在一个实施例中，通过投票方案完成该选择。这个最佳方位角产生了对3D扫描仪发生的指南针误差的最佳估计。

在步骤240，基于最佳方位角、相应第一转换矩阵和相应第二转换矩阵的聚类，来计算全局转换矩阵。然后在步骤250，全局转换矩阵用于对齐第一点云和第二点云。参考模型和场景模型之间的点云配准可以通过计算出的全局转换矩阵进行。作为配准的结果，可以进一步处理对齐的模型以用于3D建模和其他应用。

需要说明的是，虽然上述操作是以特定的顺序描述的，但是这些操作不一定要按照上述特定的顺序来执行。例如，一些操作可以以多任务方式或并行方式进行。

在一些实施例中，特别是在建筑施工场景中，基于线的3D模型中的线可以归类为垂直线(V-线)、水平线(H-线)或两者都不是。以下段落详细描述了3D空间中的点、线和平面，以表征V-线和H-线。此外，本发明实施例使用该特征来建立判别线对。

已知直线上的任意一点Q都可以用下式表示：

Q＝P+td

其中P是直线上的一个点，d是方向向量，t是一个标量实数。

如果一条线的方向向量接近Z轴的方向，则该线被称为垂直线。在一个实施例中，作为一个示例，当d或-d与Z轴之间的锐角小于5度时，这条线被归为垂直线(V-线)。类似地，在一个实施例中，作为一个示例，如果d(或-d)与Z轴之间的角度在85度和95度的范围内，这条线被称为水平线(H-线)。在此容差范围内，水平线被视为位于一个水平X-Y平面上。不同的水平线可能位于不同的水平面上，每个平面在Z轴上有不同的垂直值。如果两条线被映射到一个参考水平X-Y平面上，并且映射的线在该参考水平面内彼此不平行，则这两条水平线被称为不平行。在一个实施例中，这意味着两条非水平线在映射到同一参考水平面时会相交，并且这两条线形成的锐角可能大于20度。然而，应当理解，一般而言，非平行水平线不一定位于3D空间中的同一水平X-Y平面上。

图4A-4B显示了基于线的3D模型中的H-线和V-线以及在这种模型的背景中的判别线对的一个示例。如图4A所示，在3D扫描仪位置上，在具有原点O的笛卡尔坐标系的X轴、Y轴和Z轴中，标号401表示的线为垂直线，标号402指示的线是水平线。

在一个实施例中，判别线对包括一条V-线和一条H-线，或两条不平行的H-线，如图4B所示。判别线对411包括一条V-线和一条H-线，而判别线对412包括两条不平行的H-线。实验结果表明，与其他组合(例如两条V-线、两条平行H-线或其他随机选择的线对)相比，这些判别线对的选择具有更高的判别力。

在本发明的一些实施例中，3D模型中的每个线对被表示为一个线对特征向量，由一个或多个线对特征组成。线对特征可能与线间关系、线的几何形状和线的位置有关。在一个实施例中，线对(Lp，Lq)的线对特征向量是一个6×1向量I(dc,angle(lp,lq),len_p,len_q,z_p,z_q)，其中

dc是一个线对的两条3D线之间的最小距离，angle(lp,lq)是两条线之间的锐角，表示一个线对的线间关系；

len_p是线p的长度，len_q是线q的长度，表示线对的线的几何形状；

z_p是线p的中心点的垂直值(即沿笛卡尔坐标中的Z轴)，z_q是线q的中心点的垂直值，表示线的位置。

图5A-5B显示了线对特征的两个例子。图5A和图5B分别显示包括线Lp和线Lq的线对。对于每个线对，计算其线对特征，包括计算最小距离、第一条线Lp和第二条线Lq之间的锐角、线Lp和线Lq的长度、以及线Lp和线Lq的中心点位置。

对于每个判别线对，计算其相应的线对特征向量，用于进一步处理以寻找参考模型和场景模型之间的匹配线对。图6A-图11B显示了与上述步骤220有关的确定匹配线对组的一些示例性实施例。

在一些实施例中，确定两个模型之间的匹配线对组，涉及以下至少一项：使用至少一个与线对特征相关的阈值标准来过滤掉不匹配的线对；使用指南针角标准过滤掉不匹配的线对。下面将讨论一起使用这两个标准来找到匹配线对的过程。应当理解，任一种都可以用作用于此目的的方法，即，任一种方法都可以以独立模式或结合使用。

在一个实施例中，阈值标准涉及来自参考模型的第一判别线对的线对特征向量与来自场景模型的第二判别线对的线对特征向量之间的差异。在一个实施例中，阈值标准还包括以下子标准：

第一判别线对的最小距离与第二判别线对的最小距离之间的绝对差小于第一预设阈值；

第一判别线对的第一线条的长度与第二判别线对的第一线条的长度之间的绝对差小于第二预设阈值；

第一判别线对的第二线条的长度与第二判别线对的第二线条的长度之间的绝对差小于第三预设阈值；

第一判别线对的第一线条的中心点的垂直值与第二判别线对的第一线条的中心点的垂直值之间的绝对差小于第四预设阈值；

第一判别线对的第二线条的中心点的垂直值与第二判别线对的第二线条的中心点的垂直值之间的绝对差小于第五预设阈值；

第一判别线对的锐角与第二判别线对的锐角之间的绝对差小于第六预设阈值。只有当满足这组子标准时，这两个线对才相互匹配，它们形成一个匹配线对组。可以理解的是，第一预设阈值至第五预设阈值中的每一个或一些值可以相同，也可以不同。

图6A-6B显示了两种模型中的由V-线和H-线组成的线对。正如所见，这两个图分别说明了基于线的3D模型，即参考模型610和场景模型620。对于参考模型610中第一组判别线对中的每个线对，例如由V-线和H-线组成的线对601，将其线对特征向量与场景模型620中第二组判别线对中的线对的各线对特征向量进行比较。然后，如果线对601的线对特征向量和第二组判别线对的一个或多个特征向量满足上述阈值标准，则可以将场景模型620的一个或多个线对确定为与线对601匹配的候选匹配线对。

作为一个示例，线对601的线对特征向量可以被计算并表示为Ig(dc_g,angle_g,len_p_g,len_q_g,z_p_g,z_q_g)，其中每个元素的定义与上面讨论的相同。场景模型的线对可以以类似方式计算和表示。在场景模型620中也可能存在由V-线和H-线组成的线对602和其他线对，其线对特征向量表示为Is(dc_s,angle_s,len_p_s,len_q_s,z_p_s,z_q_s)。

如果线对601和线对602的线对特征向量满足以下所有条件，那么它们为匹配线对。

|dc_s–dc_g|

|angle_s–angle_g|

|len_p_s–len_p_g|

|len_q_s–len_q_g|

|z_p_s–z_p_g|

|z_q_s–z_q_g|

其中|x|是x的绝对值，以D

类似地，对于由两条不平行的H-线组成的判别线对，执行相同的过程。如图7A-7B所示，这两个图分别说明了基于线的3D模型，即参考模型710和场景模型720。对于参考模型710中由两条非平行H-线组成的线对701，如果线对701和场景模型720中的另一线对702的线对特征向量满足上述阈值标准，那么场景模型720中的另一线对702可以被确定为与线对701匹配。

这样，在参考模型中的线对和场景模型中的线对之间确定多个匹配线对组。每个匹配线对组包括选自参考模型中第一组判别线对的第一判别线对和选自场景模型中第二组判别线对的第二判别线对。

进一步对匹配线对组应用指南针角标准，一些判别线对将被滤除，仅保留最可靠的线对用于进一步处理。

图8A-9B显示了与图6A-6B中的线对和指南针角标准的应用有关的一个示例。线对601来自由V-线和H-线组成的参考模型，线对602来自由V-线和H-线组成的场景模型。两个模型都被映射在同一参考坐标系中。此外，根据上述过程，这两个线对可能已经被确定为匹配线对。

接下来，对于包括来自两个模型的至少两个判别线对的每个匹配线对组，计算第一判别线对的第一转换矩阵，使得第一判别线对的第一线条与参考坐标的X轴对齐；并计算第二判别线对的第二转换矩阵，使得第二判别线对的第一线条与参考坐标的X轴对齐。

在图8A的例子中，计算了一个转换矩阵Mg，使得在线对601上应用Mg将其映射到参考坐标系中的线对801。这里，线对601的第一线条被映射为一条与X轴对齐的线，线对601的第二线条同样被映射为参考坐标系中的线对801的第二线条。由于将第一线条映射到X轴的要求将唯一地定义转换矩阵Mg，因此第二线条在映射后有一个特定的方向或方位。计算这条线条在Y-Z平面803上的投影，得到该参考坐标系的Y-Z平面上的投影线805。然后可以计算投影线805与Y轴之间的锐角α

同样，如图8B所示，计算一个转换矩阵Ms，使线对602被映射到线对802，允许线对602的一条线与同一参考坐标的X轴对齐。然后，线对802的另一线条投影到Y-Z平面810，得到如标号812所示的投影线。投影线812是第二线条在Y-Z平面810上的投影。结果，可以计算Y-Z平面上的投影线812与Y轴之间的锐角α

可以理解，转换矩阵Mg和Ms的推导和投影线以及锐角α

然后，将两个角度α

图9A-9B从更直观的角度显示了一个示例，其中在参考模型910中确定了一个判别线对902，并且在场景模型920中确定了两个判别线对904和906。根据上述过程分别计算线对902和线对904之间的绝对角度差以及线对902和线对906之间的绝对角度差。当应用指南针角标准时，由于线对902和线对904之间的绝对角度差小于α

图10A-11B显示了与图7A-7B中的线对有关的另一个例子以及指南针角标准的应用。判别线对701来自由两条不平行H-线组成的参考模型，判别线对702来自由两条不平行H-线组成的场景模型。两个模型都被映射在同一参考坐标系中。

按照与上述类似的过程，计算一个转换矩阵Mg，通过将转换矩阵Mg应用于线对701的所有点，线对701转换为线对1001，使线对1001中的一条线与X轴对齐，而另一条线是参考坐标系中具有特定方向的线。然后，线对1001的该另一条线被投射到Y-Z平面1003，产生如标号1005所示的投影线。因此，可以计算出Y-Z平面1003上的投影线1005与Y轴之间的锐角α

同样，如图10B所示，计算一个转换矩阵Ms，并将其应用于线对702，将其转换为线对1002。然后，线对1002的另一条线被投影到Y-Z平面1010，产生如标号1012所示的投影线。投影线1012是第二条线在Y-Z平面1010上的投影。因此，可以计算出Y-Z平面1010上的投影线1012与Y轴之间的锐角α

图11A-11B从更直观的角度显示了一个示例，其中在参考模型1110中确定了一个判别线对1102，在场景模型1120中确定了两个判别线对1104和1106。当应用指南针角标准时，由于线对1102和线对1104之间的绝对角度差小于α

在确定可靠的匹配线对之后，通过投票方案在多个匹配线对组的所有判别线对中，从计算的指南针角差中选择一个指南针角差作为参考模型和场景模型之间的最佳方位角。

图12显示了一个实施例中的投票方案的例子。在该投票方案中，建立投票表1201，其中投票表的行表示来自参考模型1210的一组判别线对，投票表的列表示对应于量化的绝对指南针角差α的有限数量的角度区间(angular bins)，并且投票表中的所有单元格都初始化为零。这里，来自场景模型1220的一组判别线对用于投票，获得最高票数的指南针角差α被选为最佳方位角。这些线对可以是被转换到参考坐标的那些转换线对。

作为投票的一个示例性实施例，指南针角差被量化为高达α

对于投票表中的每一行(其对应于来自参考模型1210的判别线对)，从多个匹配线对组中确定来自场景模型1220的判别线对的一个候选集。对于候选集中的每个条目，检索对应于该条目的来自场景模型的判别线对和对应于该行的来自参考模型的判别线对之间的指南针角差α。在一个实施例中，如果检索到的指南针角差落入该行的一个特定角度区间，则将该行的该角度区间对应的投票表单元的值设置为1。在另一个实施例中，投票表单元的值被递增。如图12所示的例子，一些投票表单元的值为0或1，而其他单元的值为正整数+n。

在处理完所有行之后，对每一列的单元格值进行汇总，表示该列的总计数。创建一个新行并将其附加到此表以存储这些计数。与具有最大计数值的列相对应的指南针角差被确定为最佳方位角。如图12所示的例子，第i列的累积计数V

在一些实施例中，如与图2的步骤240和250相关所述，全局转换矩阵是基于最佳方位角、用于转换参考模型中的线对的转换矩阵(例如Mg)以及用于转换场景模型中的线对的转换矩阵(例如Ms)的聚类来计算的。例如，获得全局转换矩阵M的一个候选集。这里M是上述参数的一个函数，可以表示为

M＝F(Mgi,R(α

其中α

然后，通过使用来自候选集M的相应的转换矩阵，计算来自第二组判别线对的多个匹配线对组中的每条线的估计姿态。通过寻找相似的估计姿态，从场景模型中的第二组判别线对中形成线簇(Line clusters)，并获得该线簇的平均转换矩阵作为最终的全局转换矩阵。

最终的全局转换矩阵用于对齐参考模型和场景模型。参考模型和场景模型之间的点云配准可以基于计算出的全局转换矩阵来进行。作为配准的结果，对齐的模型可以进一步处理以用于3D建模和其他应用。

下面的表1-3显示了本发明实施例与其他传统方法之间的一些对比实验结果。如下表1所示，在使用其他基于线的方法的传统方法和本发明方法之间，使用LiDar扫描数据进行了五次房间之间配准测试。

表1

尽管传统方法使用的线对数量明显较多，这不可避免地减慢了配准过程，但测试表明，本发明找到95％的匹配线对是实际物理场景的实际线对。

表2-3显示了使用其他基于线的方法的传统方法与本发明方法之间的姿态估计误差的比较数据。

表2

表3

从表2可以看出，同样进行了5次测试，使用传统方法的旋转误差大多超过1度，而使用本发明方法的旋转误差极少超过1度。表3显示了平移误差的比较。传统方法下的大部分平移误差超过5cm，而使用本发明方法的平移误差极少超过5cm。这证明在采用本发明方法后，可以省略精细对准过程，如迭代最近点(Iterative closest point，ICP)。

还进行了另一个使用不同3D扫描的实验，以研究处理时间。该实验在一台采用8核i7英特尔处理器、频率为3.5GHz、并使用64G内存的计算机上运行。一次扫描包含19,105,334个点，另一次扫描包含17,795,259个点。在这两种情况下，处理时间均为0.5s左右。这表明，使用本发明方法，处理时间大大减少。

通过本发明，可以实时使用一种高效的、全自动化的、易于使用的3D计算机处理方法和系统，并且它还可以在多个平台上工作。如上面更详细描述的，本发明的有利技术可以容忍3D扫描装置的指南针误差导致3D模型的错位。此外，整个过程是完全自动化的，减少了人工后期处理的需要，以形成适用于许多商业和消费应用的完整、准确、完全成型的3D模型。本发明的方法和系统被设计成甚至可以在低成本、低功率、基于片上系统(SoC)的处理器平台上高效运行——例如运行Android

图13是根据本发明实施例的计算机化装置1300的示意图，该计算机化装置1300用于在两个单独实例上通过扫描装置获得相同空间场景的第一点云和第二点云之间的全局配准。计算机化装置1300可用于执行参照图2-12描述的方法/过程。

为此，计算机化装置1300包括线提取模块1302，其被配置为从第一点云(即参考模型)提取第一组判别线对和从第二个点云(即场景模型)提取第二组判别线对。此外，计算机化装置1300包括线对特征生成模块1304，其被配置为为每个提取的线对生成线对特征。这些线对特征用于在两个点云之间寻找相似的线对。

计算机化装置1300还包括线对匹配模块1306，其中在参考模型中的线对和场景模型中的线对之间确定多个匹配线对组。在一些实施例中，线对匹配模块1306被配置为在线对上应用与线间关系、线的几何形状和线的位置有关的阈值标准和指南针角度标准，以找到两个模型之间的匹配线对。

计算机化装置1300还包括转换矩阵生成模块1308和对齐模块1310。转换矩阵生成模块1308被配置为计算如上所述的全局转换矩阵，对齐模块1310被配置为使用全局转换矩阵来对齐第一个点云和第二个点云并获得对齐的模型。

在一些实施例中，计算机化装置1300还可以包括3D应用模块1312，其被配置为基于对齐的模型执行3D建模应用。

本发明的装置或系统和方法可以以在计算机化系统上运行的软件应用程序的形式实现。此外，方法的一部分可以在一个这样的计算机化系统上执行，而其他部分在一个或多个其他这样的计算机化系统上执行。计算机化系统的例子包括大型机、个人电脑、手持电脑、服务器等。软件应用程序可以存储在计算机化系统本地可访问的记录介质上，并可以通过硬连线或无线连接到网络如局域网或互联网进行访问。

计算机化系统可以包括例如处理器、随机存取存储器(RAM)、打印机接口、显示单元、局域网(LAN)数据传输控制器、LAN接口、网络控制器、内部总线、以及一个或多个输入设备如键盘、鼠标等。该计算机化系统可以连接到数据存储设备。

本公开的装置或系统和方法可以以在计算机化系统上运行的软件应用程序的形式来实现。图14是根据本发明的一个实施例的用于在第一点云和第二点云之间进行全局配准的计算机化系统1400的示意图，所述第一点云和第二点云由扫描装置在两个独立实例的相同空间场景上获得的，该计算机化系统包括可用于实施本发明实施例的硬件和软件组件。

本实施例中的硬件组件还包括处理器1410、存储器1411和多个接口。计算机化系统1400中连接到I/O接口1420的多个组件包括输入单元1412、输出单元1413、存储设备1414和通信单元1415，例如网卡、调制解调器、无线电通信收发器等。在另一实施例中，本公开还可以部署在分布式计算环境中，该分布式计算环境包括通过一个或多个网络连接在一起的多个计算机化系统1400。网络可以包括互联网、内联网、外联网、蜂窝网络、局域网(LAN)、家庭局域网(HAN)、城域网(MAN)、广域网(WAN)、蓝牙网络、公共和专用网络等中的一个或多个。

处理器1410可以是中央处理器(CPU)、微处理器、微控制器、数字信号处理器(DSP)、现场可编程门阵列(FPGA)、专用集成电路(ASIC)等，用于控制存储器(例如用于临时数据存储的随机存取存储器(RAM)、用于永久数据存储的只读存储器(ROM)和固件)的整体操作。一个或多个处理器可以彼此通信并与存储器通信，并执行实现本文讨论的流程图的一个或多个步骤的操作和任务。

例如，存储器1411存储应用程序、数据、程序、算法(包括用于实施或辅助实施示例实施例的软件)和其他数据。存储器1411可以包括动态或静态随机存取存储器(DRAM或SRAM)或只读存储器，例如可擦除和可编程只读存储器(EPROM)、电可擦除和可编程只读存储器(EEPROM)以及闪存、以及其他存储器技术，单独或联合使用。在一些实施例中，处理器1410可以被配置为执行上述各种过程和处理，如参照图2-12描述的方法/过程。

存储设备1414通常包括持久性存储设备，例如固定和可移动磁盘等磁性磁盘；包括磁带在内的其他磁性介质；光盘(CD)或数字多功能磁盘(DVD)等光学介质；以及半导体存储设备，如闪存卡、固态驱动器、EPROM、EEPROMS或其他存储技术，单独或组合使用。注意，上述软件的指令可以提供在计算机可读或机器可读存储介质上，或者可以提供在多个计算机可读或机器可读存储介质上，分布在一个可能有多个节点的大型系统中。这种计算机可读或机器可读介质被认为是物品(或制造品)的一部分。物品或制造品可以指任何制造的单个部件或多个部件。

输入单元1412是将计算机化系统1400连接到数据输入设备如键盘、小键盘、基于笔的设备、鼠标或其他点设备、语音输入设备、扫描仪或其他输入技术的接口部件。根据本发明的一个实施例，输入单元1412可以包括至少一个3D传感器，其捕获3D场景，用于向计算机化系统1400提供3D场景的3D数据。输出单元1413是计算机化系统1400的接口部件，用于将数据发送到输出设备，如CRT或平板显示器、打印机、语音输出设备、扬声器或其他输出技术。通信单元1415通常可以包括串行或并行接口和USB(通用串行总线)接口，以及其他接口技术。通信单元1415还可以使计算机化系统1400通过数据通信网络如个人局域网(PAN)、局域网(LAN)、广域网(WAN)、互联网、和其他数据通信网络体系结构，与外部数据处理设备交换信息。通信单元1415可以包括以太网接口、无线LAN接口设备、蓝牙接口设备和其他联网设备，单独地或组合使用。

软件进一步包括操作系统以及如图14所示的应用软件系统。操作系统将管理所有硬件资源，并为所有任务和进程安排执行优先级，以使四个应用软件系统都能有序地执行。

本文讨论的步骤和/或方法可以由用户、用户代理(包括机器学习代理和智能用户代理)、软件应用、电子设备、计算机、固件、硬件、程序、计算机系统和/或智能个人助理执行和/或进行。此外，本文讨论的步骤和/或方法可以在有或没有用户指示的情况下自动执行。

对于本领域的技术人员来说，应该理解硬件和软件之间的划分是为了便于理解而进行的概念性划分，并且在某种程度上是有些随意的。此外，可以理解的是，一台计算机中安装的外围设备可以集成到另一计算机的主机中。此外，应用软件系统可以在分布式计算环境中执行。软件程序及其相关数据库可以存储在单独的文件服务器或数据库服务器中，并被传输到本地主机上执行。因此，如图14所示的计算机化系统1400是如何实现本发明的一个示例性实施例。本领域技术人员会理解，可以采用替代性实施例来实现本发明。

本发明的示例性实施例由此得到充分描述。尽管描述中涉及特定的实施例，但是对于本领域的技术人员来说，可以清楚看到，本发明可以通过改变这些具体细节来实施。因此，本发明不应被解释为仅限于本文所阐述的实施例。

在不同图中讨论的方法可以添加到其他图中的方法或与之交换。此外，具体的数字数据值(例如具体的数量、数字、类别等)或其他具体信息应被解释为讨论示例性实施例的说明性信息。提供这样的具体信息并不是为了限制示例实施例。