CN110574071B - 用于对齐3d数据集的设备，方法和系统 - Google Patents

Abstract

本发明属于3D测量，绘图和成像领域。特别地，本发明涉及3D数据集的旋转对齐。实施方式包括用于3D数据集的旋转和可选地平移对齐的装置方法和程序。将3D数据集存储为点云，将其转换为向量集，并将向量集表示为一个单位球面或高斯球面，并进行比较以获得最佳对齐。找到的最佳对齐用于将两个3D数据集旋转，已达到彼此的旋转和平移对齐。

Description

用于对齐3D数据集的设备，方法和系统

技术领域

本发明属于3D测绘和成像领域。特别指出，本发明涉及3D数据集的旋转对齐。

背景技术

3D测量数据集可用于创建计算机化的3D数据集，模型和网格，用于分析，计算，测量和监测所测量的空间。通常的情况是成像装置在单一位置的视野并不能包括待测量空间中的所有场景。这就需要在不同时间，成像装置处于不同的位置和方向拍摄多个图像，扫描或测量，或者使用具有同时多定位和定向的扫描仪采集并且随后合并多个图像。

目前，用于确定多个3D数据集的旋转和平移对齐技术要求大量人力介入。在为无障碍阻挡的感兴趣的对象成像时，人工目标点或特征必须放置在要合并的两个图像所共同的成像位置。

对于有障碍阻挡的感兴趣的对象(例如，地下的地质测绘，或者人体)，就需要准备一个特定的目标点(可以是虚拟的或自然的目标点)以实现特征识别。自然目标点通过图像处理识别，并用于创建锚点从而实现两个图像的数据合并。目标点可以是自然的(对齐之前在图像中识别)，也可以是人工的(通过测绘视野引入)。

因此，提供一种可靠的，自动的，用于重叠3D数据集的旋转对齐的技术成为了一种期望和诉求。

发明内容

说明1

第一方面的实施方式包括一种装置，该设备包括：3D数据集采集单元，其配置为：在第一个位置和方向，由成像装置采集在第一个时间点上，第一个空间内的第一个3D数据集，该数据集即为第一个三维点云，此第一个点云中的每个点表示成像装置在第一个空间内的读数；并且在第二个位置和方向，由成像装置采集在第二个时间点上，第二个空间内的第二个3D数据集，第一个空间和第二个空间重叠成为第二个3D数据集，即第二个三维点云，此第二个点云中的每个点表示成像装置在第二个空间内的读数；一个存储单元，其构造为将第一个和第二个3D数据集分别存储为公共坐标系中的相应点云；一个旋转对齐处理器，其构造为：将存储的第一个点云变换为第一个向量集，并将存储的第二个点云变换为第二个向量集，其中第一个或第二个向量集中的每个向量表示其相应点云中相应的点和相邻点之间的关系；寻找到第二个向量集，相对于第一个向量集，围绕三个旋转轴中的一个或多个轴的旋转角度，从而在定义的公共坐标系中，获取第一个向量集与第二个向量集的角度分布之间的最大匹配度。旋转对齐处理器还被进一步配置为存储或输出所计算出的围绕每个或多个旋转轴匹配程度最大的旋转角度；或者旋转第二个点云，旋转的角度为公共坐标系中，所存储的围绕相应的一个或多个旋转轴的旋转角度，并在公共坐标系中，输出旋转后的第二个点云。

其优点是，实施方式提供了一种通过确定旋转向量来改进3D成像装置和成像处理的机制，旋转向量的确定是通过旋转一个现有的3D数据集以使其与另一个重叠的3D数据集达到旋转对齐而实现。重要的是，该机制是解析的，并且避免了对人工目标点进行手动定位的现有要求，并且在需要高精度的情况下，在要成像的空间内单独测量，并且不需要识别和获取自然目标点的位置和方向。可以通过扫描仪(成像装置)扫描空间，产生代表所述扫描的单独数据集，而不需要在数据集之间保持成像设备的一致取向和/或位置，从而加速成像过程的建立，并且避免例如用于成像装置的固定支架或三脚架等要求。

3D数据集的旋转对齐使随后高度精确地测量对齐的数据集，扫描，点云，模型或网格上的距离成为可能，而无需返回到采集点进行测量。

当然，通过依次对齐各对重叠扫描，可以扩展此实施方式以处理同一空间的两个以上扫描(即多于2个3D数据集)。

通过对感兴趣的对象的两个重叠数据集，可以容易地创建高质量3D数据集和模型，既无需知道成像装置从数据集到数据集的相对方向，成像装置相对于感兴趣的对象的相对方向，也无需知道人工目标点的放置情况及位置记录，或者确定自然目标点的位置和方向。重叠包括两个数据集在它们所代表的物理空间方面彼此重叠，而且/或者可以重叠一个或几个常见的自然特征，这些常见的自然特征可以是一个平面，例如地板或墙壁，或者可以是一个杆状物，例如，管道，铁路线或吊线。例如，数据集是扫描数据集或图像数据集，换句话说，该数据是通过对物理空间扫描或成像而生成的。

3D数据集可以由3D点云表征并且被视为3D图像。

另一个优点在于可以容易地将数据集的后处理过程应用于输出已旋转对齐的数据集。而如果没有这些已旋转对齐的数据集，若干其他优秀的平移对齐方法和模式识别方法将不能使用。

扫描

每个由3D数据集采集单元获得的数据集包括在成像过程中的连续点处记录的数据，每个点与其相邻点的距离由成像的分辨率和方向决定，每个点记录相对于成像装置或者相对于已扫描(在相同扫描中)的位置数据，并且每个点由成像装置的读数响应而生成，换句话说，数据集中的每个点代表着成像装置的一个读数。反过来说，一个读数是当扫描仪处于活动状态时，成像装置所接收的询问点与发射或反射光束的相互作用的响应的记录。或者说，如果物体正在发射某中物质，则成像设备正在接收它。以测量电阻为例，发射的物质则为电流。

这里所说的数据集是3D数据集。成像装置可以是3D扫描仪或者其他装置。每个数据集包含代表感兴趣的对象3D图像的数据。

输入信号，即第一个和第二个3D数据集，可能局限在一个物理空间的扫描中。此外，实施方式也可以采集虚拟空间的2D或3D数据集作为第一个和第二个3D数据集中的一个或两个。3D点云通常会以虚拟空间中的网格模型的形式来表征，这样可以减少内存，存储，旋转和平移计算速度以及传输带宽的要求。出于类似的原因，3D数据集通常生成为网格模型，以便在虚拟空间中使用。为了将网格模型与点云或其他网格模型对齐，可以将网格模型转换为点云，例如，通过将网格节点更改为点或通过插值和采样生成新的点，并作后续处理。关于后续处理的方法，会在之后做详细的阐述。此外，可以使用本专利所描述的向量表征方法，即直接从网格模型中提取向量集，以用于本专利所描述的旋转对齐方法。

第一个和第二个3D数据集可以是从相同的成像装置采集获得，也可以是从不同的成像装置采集获得。成像装置获取一个空间内的读数。举例说明，这些读数可以是成像装置所检测到的波或粒子的发射，反射或吸收的位置。成像装置将3D空间内的物理特征诠释为读数，并且在与读数相对应的点云中生成一个数据点。这里，物理特征可以是一个表面或者两种材料的交界面。用于生成第一个和第二个3D数据集的成像装置可以使用不同的成像技术进行成像。例如，第一个成像装置可以是X射线扫描仪，第二成像装置可以是MRI扫描仪。此外，有一个将相应数据集降维至一维数组的非必需的步骤，即通过平移，改变比例或放大率这个额外变量，直到找到最佳解。增加或减少一个扫描相对于另一个扫描的尺寸，同时所有其他步骤保持不变。

读数可以记录从成像装置到该点的距离。读数可记录位置数值，诸如x，y，z笛卡尔坐标，圆坐标，球坐标，地理坐标或其他坐标(如空间-时间坐标)。读数可以包括日期和时间以及进行记录的人或仪器，也可以是所使用的激光仪器的分辨率设置和功率。读数可以记录来自激光或声波的反射，透射或吸收信号的强度。读数可记录从某个点发射并由装置检测到的任何光，辐射或声音的强度和颜色。读数还可以包括该点及其相邻点的属性，例如表面的曲率以及表面法向量。表面法向量用来代表拟合到某一点及其相邻点的小平面块的位置和取向。读数还可以包括推导出的属性，例如表面法向量的散度和方向，以及曲率的正负。读数可以记录电阻率，电导率，电容率，电感率，介电常数或磁导率，也可记录电磁波或声波在该点的传播速度。读数可以以r，g，b坐标或以下任何颜色坐标来记录物体表面的颜色：CIELAB，CIELUV，CIExyY，CIEXYZ，CMY，CMYK，HLS，HSI，HSV，HVC，LCC，NCS，PhotoYCC，RGB，Y'CbCr，Y'IQ，Y'PbPr和Y'UV(参考文献https://people.sc.fsu.edu/～jburkardt/f_src/colors/colors.html)。读数可记录表面的纹理或粗糙度，表面的材料，或表面下空间的材料。读数可以通过使用诸如多普勒等方法，记录瞬态上的点的任何局部移动速度，加速度，周期和向量方向。有一点值得注意，当成像装置在一个方向上采集时，它可以接收多于一个的读数。如果扫描的是一个坚固的不透明表面，通常只会有一个读数。但是，如果扫描的表面是稍微透明的，或者没有表面并且它只是虚像，则可能存在到数千个读数，且到成像装置距离不同。举一个例子，读数可以是x，y，z，r，g，b格式。

所谓的成像装置的第一个和第二个位置和方向是相对于被成像空间而言的。

重叠

第一个空间和第二个空间的重叠。重叠的程度取决于实现的方式，并且将根据每对数据集而变化。重叠的程度取决于重叠区域中的对齐的特征的数量。要达到高精度对齐则需要足够的共同特征。这里所谓的重叠是指共同特征的重叠。重叠可以是部分重叠，也可以是完全重叠。例如，在不同时间扫描或者使用不同技术的扫描仪进行的扫描就有可能达到完全重叠。例如，重叠可以是在第一个和第二个数据集中呈现的一个共同物理空间。实施方式可以包括预处理步骤，即作为3D采集单元获取数据的一部分，已达到从输入数据集中移除一些非重叠数据的处理步骤。

第一个和第二个的空间重叠。一个可能出现的推论是，第一个和第二个的空间都与一个扩展特征重叠，此特征为两个空间共同的，但是这两个空间在空间中不直接重叠。这样的扩展特征具有可能重叠的特征，例如线，平面，圆柱等，基于一些常识，他们可以从第一个空间延伸到第二个空间。因此，第一次的扫描可以扫描直线铁路线或墙壁的一部分，第二次的扫描可以扫描不同的物理空间，但是包括铁路线或墙壁的另一部分。如果已知铁路线或墙壁是直的，那么该装置可以将两次扫描旋转对齐至该铁路线或墙壁。我们可以使用模式识别来识别每一个扫描中的轨道或墙壁。在平移对齐的步骤中，该扫描将与垂直于轨道的二维平面对齐，或者与垂直于墙壁的一维直线对齐。如果在两个非直接重叠的扫描(扫描类似于数据集)中共有几个相互成一定角度的特征(例如杆状或边缘)，则该装置可以精确地沿着杆的方向将一个扫描相对齐到另一个扫描，因为只有一种可能将第二个扫描中的杆方向与第一次扫描中的杆的延长方向精确匹配。依此类推，对于彼此不同角度的几个平面，甚至对于平面，杆，边缘，圆柱，环形，锥体和其他形状的混合，均可将两个扫描通过该特征对齐。这一点非常重要，因为它意味着没有必要让所有扫描在空间中物理重叠，只要在特征中存有一些共性即可，即两者中都出现一个特征。举一个自动驾驶汽车的例子，可以扫描道路上的边石，白线或黄线，铺平板边缘,墙面和边缘等特征，从而对齐较窄的非重叠扫描。

共同坐标系

在存储单元处，第一个和第二个3D数据集以相应的点云形式存储在公共坐标系中。公共坐标系是一个工作空间。第一个和第二个3D数据集都有其各自的原始坐标系，在其中定义了各个点云。实施方式的先决条件是第一个和第二个3D数据集的坐标系与存储单元的公共坐标系兼容。例如，原始坐标系可以将该数据集的成像装置的位置作为坐标系的原点，其方向为成像装置的方向。第一个点云可以在旋转和平移之后放入工作空间，而第二个点云则在不同地旋转和平移后放入工作空间。

点到向量的变换

在变换过程中执行的精确方法是特定于情况实现的。例如，实施方式可以将已存储的第一个点云变换为第一组表面单位法向量，并将已存储的第二个点云变换为第二组表面单位法向量。旋转对齐处理器在两组向量之间执行最佳匹配，因此，这两组向量需要是可比较的。例如，使用相同的技术，方法或算法将第一个点云变换为第一组向量，同时将第二个点云变换为第二组向量。

举例说明，向量可以代表一个由相对应的点和其相邻点形成的假想表面。或者，向量也可以代表这个点所在的一些其他几何或其他属性。再例如，如果数据集代表一个物体(如体内器官)，则向量可能不代表任何表面，只是3D空间不同的读数集。向量可以通过逐点在读数中的每个变量的最大梯度来计算。

第一个点云被变换为第一组向量，第二个点云被变换为第二组向量。点和向量之间可能存在一个一一对应的关系，或者可能存在一个采样率以相对于点的数量，减少向量的数量。点云中的点代表成像装置的读数。数据集中的相邻点形成假想表面，也就是说，假想表面可以被拟合到点云内的点的不同分组上。对于每个查询点，变换包括生成向量以代表拟合到查询点及其相邻点的假想表面。因而，假想表面被理解为由相应的点和相邻点所代表的信息。这样的好处是，可以根据不同的应用要求，以不同的方式选择相邻点。另外，另一个好处是，可以选择不同的算法来将假想表面拟合到这一组点上，并且用于生成代表这个假想表面的向量。

可以将与各个点相关联的点本身，相关联的读数或者属性变换为向量。

找寻最佳匹配

旋转对齐处理器在第一和第二组向量之间，通过找到围绕着两组向量中的各个可能的转轴达到最大程度匹配的那个角度作为最佳拟合的方向。这样有效地，一组向量围绕着另一组向量可能的每个旋转轴上旋转，直到找到最佳匹配。可以通过使用例如数学相关函数/算子来比较两组向量的角分布来测量匹配程度。例如，数学相关函数/算子可以是适合于特定应用的现有数学相关函数/算子。

三个旋转轴可以是正交的，或者可以是两个共面的(但如果两个轴是共面的，则它们必须是不平行的)和一个非共面的轴。

输出结果

输出结果可以由旋转对齐处理器旋转得到的第二个点云组成。输出的第二个点云与存储的第一个点云是旋转对齐的。输出结果还可以包含存储的第一个点云的副本。例如，如果公共坐标系与第一个3D数据集的原始坐标系不同，则为了实现两个旋转对齐的数据集，装置可以输出旋转的第二个3D数据集和第一个3D数据集在共同坐标系中相应的点云。已旋转对齐的数据集可以合并且输出为单个图像数据文件。已旋转对齐的数据集标志着这两个数据集中描述的物理实体在两个数据集的公共坐标系中共同对齐。

对于一些应用，输出结果包括围绕每个轴执行的旋转量的一个向量或者其他形式，因为这表示成像装置旋转了多少以及它在成像过程之间如何旋转。因此，如果成像装置在车辆上，则该旋转数据可用于指示车辆旋转了多少。这种输出结果比在惯性测量单元(IMU)中使用光纤陀螺仪得到的结果更为准确。因为当采集数据集时，两次采集之间的时间很长时，IMU传感器会存在漂移。

输出结果可以包括将第二个点云与第一个点云合并，并输出合并的点云。此外，第一个点云也可以作为输出结果。另外，如果第一个点云在存储时被旋转和平移，则它可以在与第二个点云相同的坐标空间中输出。

公共坐标系中的第一个点云的位置也可作为输出结果。如果之前不知道或者此前未被输出，输出结果还可以包括公共坐标系中的第一个点云的位置。

说明2

存储单元用于选择性地存储第一个点云和输出旋转的第二个点云。该装置还额外包括一个平移对齐处理器，其配置为：对于公共坐标系中的三条或更多条线中的每条线，其中三条线中的每两条线是不平行的，并且三条线中的至少一对线是非共面的：相对于任意原点，记录第一个点云中每个点投影到这条线上的位置；将记录的位置存储为第一个一维位置数组，并/或存储在相应的记录的位置上的各个点的一个或多个属性或读数作为第一个一维位置数组；相对于任意原点，记录旋转的第二点云每个点投影到这条线上的位置；将记录的位置存储为第二个一维位置数组，并/或存储在相应的记录的位置上的各个点的一个或多个属性或读数作为第二个一维位置数组；找到沿着第二个一维位置数组的线，相对于第一个一维位置数组的线的平移，该平移是第一个和第二个一维数组之间的最大匹配度所对应的平移值，并记录该平移；并且输出：第一个点云和旋转的第二个点云在公共坐标系中的合并点云，和先旋转而后按相应的记录的平移结果，沿公共坐标系中的三条线中的每条线平移的第二个点云；和/或一个向量来代表三条线和分别沿三条或多条线的平移数值，以及一个向量来代表三个旋转轴和分别绕各旋转轴的旋转角度；和/或先旋转而后按相应的记录的平移结果，沿公共坐标系中的三条线中的每条线平移的第二个点云。

其优点是，包括平移对齐处理器的实施方式提供了一个计算定位两个点云所需的位置偏移(平移)的机制，使得两个点云中代表扫描空间中相同特征的点在公共坐标系中对齐。因此，可以合并两个单独的输入数据集并将其视为单个数据集。实施方式以有效的计算方式实现合并两个点云，并且不需要将目标点手动放置在成像空间的重叠区域中，或者测量其位置，也无需手动识别自然目标点并且记录它们的位置和方向，并且不需要手动识别两次扫描中的相应特征并且手动旋转和平移扫描以使相应的特征对齐。

一维数组将每个点云的数据点记录为一维空间维度中的点。可选择性地，每个数据点的权重可以通过局部点密度的倒数来缩放设定，以便使描述方法更少地依赖于点对点距离并且使得扫描距离不是很敏感。这里应注意，除了一维的位置之外，每个点可具有一个或多个属性，这些属性包括例如点密度，颜色，每个点的反射强度等。这些附加属性也可用于计算数学相关性。每个点的属性或读数可以是已计算的，代表点和相邻点关系的已计算的向量。一维数组可以被称为直方图，因为在数组在一维空间维度中每个区间都存在至少一个数字，例如点的总数，颜色，读数或向量的组合。

点投影到的三条线对于两个点云都是共同的。这三条线可以是在笛卡尔坐标轴，地理坐标系，球坐标或者柱坐标中定义。注意的是，最少需要三条线，并且可以使用多于三条线。

属性或读数也可以是每种不同类型的向量的方向。在向量的情况下，通过计算两个数组中向量的点积或内积，然后进行求和或积分来计算相关性。

投影到线上的做法实际上是将三维点云降维至一维的杆或线上。将点投影到线上的方向可以是沿着垂直于线的向量，也可以是与线成一角度，抑或是沿着与线相交的曲线。投影的线可以是笛卡尔坐标系，地理坐标系，球或柱坐标系的坐标轴。

平移对齐处理器将沿着三条或更多条线中的每条线，分别将一个一维数组向另一个数组平移，以达到两个一维数组之间的最佳匹配。测量的量可以是点的空间分布，也可以是颜色，放射率读数，或者与该点相关联的向量(该向量可以是该点处的法线向量，和向量，代表该数据集中的点的任意一种向量中的一个，也可以同时使用多个向量)。匹配的属性越多，对齐就越准确。为了增加从任何单次扫描所得到的数据的值，每个属性将独立地相关，因此计算成本会更高。最初步可以使用空间点密度，例如，使用低通滤波器或平滑方法，从而获得一些近似对准的位置，然后在近似对准的那些位置附近增加分辨率。可以通过使用最佳匹配搜索和优化算法(例如最速下降法，模拟退火法或Levenberg-Marquardt方法)来找到最佳匹配位置来实现提高对齐的准确性。平移对齐结果包括两个数组相对于彼此在两个极值之间迭代平移，并且在每次迭代时计算匹配度。例如，这两个极值，一个可以是第一个一维位置数组中的最大值与第二个一维位置数组中的最小值重合时的平移数值，另一个是第一个一维位置数组中的最小值与第二个一维位置数组中的最大值重合时的平移数值。另一种方法是卷积定理，实施方式可以首先将每个扫描中的每个读数和特性的一维数组做傅立叶变换。然后，将相同的读数和特性的傅里叶变换，用相同的缩放比例和原点重叠在一起并且相乘。最后，将得到的一维读数和属性数组做傅里叶逆变换。结果与执行通常在计算上和编程上使用的相关性的结果相同。或者，在非必须的点云分割过程之后，实施方式可以识别3D物体和特征，并在将它们降维到线上之前标记与它们相关联的点。3D模式识别可以通过例如3D模板匹配，几何匹配或通过诸如深度学习卷积神经网络的人工智能技术来实现。当计算两个降维的扫描沿着一条线相互平移的相关性时，与特定类型物体或特征相关联的点仅与来自相似类型的对象或特征的点做相关性计算。对代表每种类型的物体或特征的点集，或者对每个读数或特性的相关性计算应是独立的。将这些相关性的幅度以加权方式组合起来，以获得这些扫描的总相关或匹配。此举的优点是：一般来说，来自一种类型的物体或特征的点不会来自不同类型的物体或特征的点相关联，因为它们各自具有不同的特性，从而获得更好的对齐结果。另外，为了加速相关性计算，可以用一个单一适当的标记点来替换已识别的3D物体和特征，并且在计算总相关性时，调整权重以在组合相关性时进行补偿。

值得注意的是，任何两条线都会位于一个共同的平面中。点云也可以投射到这个或者其他公共平面上。在此公共平面上的投影可以是沿着垂直于公共平面的向量，与公共平面成一角度，或者沿着任意曲线映射到公共平面上。投影的线可以是笛卡尔坐标轴，地理坐标系，球坐标或柱坐标坐标轴。每个点云将在公共平面上形成一个降维图像。来自两个重叠扫描的图像可以沿着两条线在平面中横向移动，直到沿着每条线达到最大匹配或相关程度。该方法与投影到线上的方法的不同之处在于，降维图像的特征的相对位置保持不变，也即沿两条线的坐标保持不变。因此，降维图像的特征可用二维坐标标记。而当点云单独降维到线而非平面上时，它们仅保留沿每条线的一维坐标。在降维平面上，可以通过卷积定理有效地计算相关性：通过对共同平面上的两个扫描的两个图案做2D傅里叶变换，将它们以相同比例，相同原点，重叠在一起，将它们相乘并施加傅里叶逆变换。然而，沿着两条单独的线计算两个一维匹配或相关性，要比在公共平面上降维图像的一个二维匹配或相关性的计算量要小得多。而将点云降维到多于三条线上会相对减少丢失特征的二维坐标的可能。另外，可以通过使用降维平面图像中的x，y坐标作为每个点的标记，读数或属性，这些标记，读数或属性将随相应的点一起移动，因此这些信息在降维和计算相关性时不会丢失。此外，这两种方法可以一起使用，即通过将点云降维到一个公共平面，再降维至该公共平面的法线上或与该平面成一定角度的线上。通常，公共平面可以选择水平的平面，而线则是竖直的坐标轴。

对于一些应用，输出结果包括沿每个轴的平移量的向量或其他表征方式，并且记录在成像过程之间，成像装置的位移以及方向。因此，如果成像装置在车辆上，则该平移对齐数据可用于表示车辆移动了多少。当在不同时间采集数据集而且两次数据集之间的时间很长时，这方法比在惯性测量单元(IMU)中使用加速度计更准确。更具优势的是，此方法可以非常精确有效地记录车辆的3D轨迹。换句话说，点对齐是计算车辆轨迹和方向。

作为替代，输出结果可以包括正确旋转和平移的第二个点云，或者在公共坐标系统中正确定向和平移的第一个和第二个点云，亦或者是合并的两个点云。

说明3-7

用于实施方式的旋转和平移对齐机制不仅仅局限于成像技术。该机制具有成像设备不可知，波长不可知和成像技术不可知(在这些情况下不可知意味着独立)的性质。此外，实施方式提供了一种机制，用于对齐来自不同成像装置的数据集，或者相同的成像装置在不同位置或不同时间采集的数据集，或者通过不同成像机制获得的数据集。例如，MRI扫描可以与X射线扫描在重叠的空间(对象)对齐。

示例性成像机制和成像对象如下所述：

可选地，第一个3D数据集和第二个3D数据集中的一个或两者是由激光探测与测距(LIDAR)扫描仪采集的。

被成像的空间可以是建筑物的内部，建筑物的外部，景观，露天矿，海岸线，管道或管道网络的内部或外部，洞穴，隧道例如采矿隧道，道路，人或动物的一部分或骨架，等等。

激光探测与测距(LIDAR)还可以写成Lidar,LiDAR,or LADAR的形式，意思为光探测和测距。扫描仪使用的波可以是紫外线，可见光或近红外线。

第一个和第二个3D数据集之间的空间重叠可以是基本上完全重叠的，但两个数据集的采集时间不同，也即可以在不同时间对同一空间进行成像(例如，观察随时间的变化)，无需要求采集两个数据集时，LIDAR使用相同位置和方向。

LIDAR扫描仪可以是2D扫描仪，其通过相对于扫描仪的移动或对象相对于扫描仪的移动来进行3D扫描。或者，LIDAR扫描仪可以3D扫描仪。可替代光学的3D扫描设备包括干涉仪，摄影测量，投影成像仪，扫描焦平面，阴影的形状，或者光流场。其他替代方案在下文的“图3的描述”中阐述。

另举一例，从其获得第一个和第二个3D数据集中的一个或两者的成像装置是穿地雷达或使用偏振或非极化电磁波的穿墙雷达，并且成像空间是地下的或被可见光，墙或其他结构阻挡的空间。穿地雷达应用于探测地下材料，管道，考古遗迹，未爆弹药和隧道的湿斑反射。

例如，穿地雷达中使用的极化或非极化电磁波的频率范围为100MHz至2.6GHz的微波频带，对于穿壁雷达而言可以在1.6GHz至10GHz的频率范围内，并使用2.4GHz的WIFI辅助穿壁雷达。穿地雷达或穿壁雷达可以是多普勒雷达，以检测表面或对象的移动。

可选地，获得第一个和第二个3D数据集中的一个或两者的成像装置是插入地面的电阻率断层扫描仪，并且成像空间位于地面下方。

作为用于地下扫描的替代成像技术，获得第一个和第二个3D数据集中的一个或两者的成像装置可以是检测地震波的地震层析成像扫描仪。

另外，获得第一个和第二个3D数据集中的一个或两者的成像装置可以是电阻抗断层摄影扫描仪，其包括用于放置于受试动物的皮肤上的电极，并且成像空间是受试动物的体内结构。

作为扫描受试动物体内结构的替代技术：

可选地，获得第一个和第二个3D数据集中的一个或两者的成像装置可以是MRI扫描仪或检测核四极共振的扫描仪，其成像空间是受试动物的体内结构。

更具优势的是，实施方式可以将来自电阻抗断层摄影扫描仪的扫描与来自MRI或核四极杆扫描仪的扫描对齐，而不需要相应扫描仪的相对位置或方向等任何信息。

核四极杆扫描仪是用来检测核四极共振的扫描仪。

另一个扫描受试动物(例如人类)体内结构的替代技术是超声扫描仪，并且成像空间是受试动物的体内结构。

另一个可选的替代技术是声纳扫描仪。

声纳是基于声波检测的扫描技术，并且实实施方式可以用被动(收听声音)或主动(发出声音并收听其反射)声纳扫描仪来实现。声纳可以被认为是声音导航和测距，并且可以包括多普勒检测表面或对象的移动。

例如，扫描的空间可以是浸没式的，例如潜水艇。特别地，扫描空间也可以包括海床。

说明8

可选地，3D数据集采集单元包括去噪处理器，即在第一个和第二个采集的3D数据集时，在第一个和第二个点云上分别施加去噪算法。

更具优势的是，去噪算法重点施加于成像空间中的感兴趣的对象的物理特征相关的读数。因此，当数据集(即向量或数组)由平移和旋转对齐处理器对齐时的匹配强度得到有效的增强。

本文中的去噪意味着噪声滤波，也就是说，去除噪声的信号处理，其可以滤除噪声。去噪处理器通过信号处理以增强各个数据集的信噪比。

去噪算法可以是双边去噪算法，去卷积函数或者维纳滤波器。在搜寻扫描仪的运动轨迹的应用中，除了插值方法之外，去噪算法可以是卡尔曼滤波器，均值或中值滤波器，粒子滤波器或基于启发式的离群点检测。

说明9

可选地，第一组向量是表面单位法向量，第二组向量是表面单位法向量；并且将第一个点云变换为第一组表面法向量，并将第二点云变换为第二组表面法向量，以下方式生成生成第一组和第二组表面法向量：逐点地，对于相应点云中的每个点作为查询点：选择一组邻居点集，计算该组邻居点集和查询点的协方差矩阵；处理协方差矩阵，找到协方差矩阵的三个特征值和三个特征向量，确定具有最小特征值的特征向量，将特征向量归一化到预定的单位长度，将归一化单位向量加到相应的第一组或第二组法向量上。

另一种方法是，可以将小平面块与查询点附近的点对齐，以使点与平面的距离达到最小值。这样，该小平面块的表面法线可以被认为是该点处的表面法线。选择表面法线的方向，使其指向扫描仪，以确保表面法向量与从点到扫描仪的向量之间的角度始终小于180度。

该转换技术产生一组准确代表点云的表面单位法向量，从而两个数据集中代表的物理特征在两组表面单位法向量中保持一致。如此，可以计算上高效地在两组向量的角度(和空间)分布之间找到最佳匹配。

可选地，在选择该组邻居点集之前，该过程可以(取决于点云的类型及其密度分布)包括使用采样算法。该采样算法将分别标准化第一个和第二个点云的点面密度或点体密度。

具体例子如下：

采样算法可以利用八叉树(Octree tree)或K维树(kd tree)数据结构来存储非结构化的3D数据，从而可以对该数据进行快速空间搜索。采样算法可以使用随机采样，或者点之间的基本均匀的欧几里德距离。如果将八叉树或K维树用作要采样的数据结构，则通过现有树结构，选择一组邻居点的过程得以简化。如果使用另一数据结构，则处理过程可以包括在选择相邻点集之前，为各个点云建立并填充树结构。

邻居点集合的选择可以包括固定距离邻居点方法，该方法用于查找以查询点为中心的预定义半径范围内的所有点，或者K-近邻算法来找到离查询点距离最近的N个点，这里的距离指的是欧几里得距离。

在采样算法方面，需要注意的是：

这种点的体密度的标准化不能用于点的密度梯度向量的计算，否则所计算的密度梯度向量会忽略点向密度的变化。

该采样算法不是必须的，但有利于找到向量(除了点密度梯度矢量)。未采样或已采样数据可用于平移对齐处理。

未采样或已采样的数据可用于识别3D形状。如果该方法涉及找到任何向量(点密度梯度向量除外)，则对于某些类型的向量，可能必须在计算向量之前进行采样以获得均匀的点密度。计算表面法线的方法不需要均匀的点密度。在从采样后均匀分布的点云中识别尽可能好的形状及其位置和方向之后，算法可以返回被移除的点(所有属于该形状的点)，然后进行最后一步精确对齐：使用所有点最小化形状的误差以获得最高精度。

说明10

实施方式还可以包括用于选择邻居点集的以下过程：选择一个查询点并在其周围形成一个小的搜索半径球体。在球体内的所有点上使用主成分分析(PCA)。如果存在平面，则从PCA输出的分量其中两个将位于平面内，并且另一个分量则垂直于平面。幅度最小的一个分量是平面的法线。沿此方向绘制单位向量作为法线方向。在每一点重复该操作。

为查询点选择一组邻居点集的方法可以包括：选择以查询点维中心，预定义半径的球体内的每个点，或者使用K-近邻算法，选择找到距查询点最接近(基于欧氏距离)的N个点；之后将第一个点云变换为第一组表面单位法向量和/或将第二个点云变换为第二组表面单位法向量。之后：存储相应的这组表面单位法向量作为表面单位法向量的参考组；逐渐缩小球的半径，重复计算相应的表面单位法向量组。直到达到最小半径时，终止计算并且将参考组的表面单位法向量设置为相应的这组表面单位法向量。在每次重复计算时：确定在重复中产生的相应的表面法向单位向量组与参考组匹配的置信度，并且如果确定的置信度满足预定标准，则将参考组的表面单位法向量设置为相应的表面单位法向量组，并终止变换；如果确定的置信度不满足预定标准，则将所存储的表面单位法向量参考组替换为此次循环中得到的相应的表面单位法向量组，并继续重复。

这样的优点是，用于设置上述通过改变半径的重复计算技术提供了一个用于找到固定距离相邻点方法的最佳半径的经验主义技术。此外，在逐个区域(这些区域可以由分割算法确定)内使用上述技术在计算上是有效的。作为另一替代方案，一旦变换了一个数据集，此半径值可以是用于第二个数据集的初始半径。如果下一个数据集不满足预定标准，则可以在更大的范围内扫描半径以找到最佳半径。

预定标准可以是，例如，一个置信度阈值(即，是否确定的置信度超过该置信度阈值)。或者，预定标准可以是关于重复中的转折点，也就是说，当置信度停止增加并开始减小时，则在置信度最大时使用此时的半径值。

上面阐述的用于选择邻居点的技术可以针对整个点云使用，或者仅针对特定区域使用，然后针对其他区域重复选择。

上述的“相应的”表示在转换为向量处理中将第一个或第二个点云。

说明11

作为表面单位法向量的替代或附加向量集：第一组向量中的向量是和向量，第二组向量是和向量；将第一个点云变换为第一组和向量并将第二个点云变换为第二组和向量，包括：可选择性地使用采样算法，该采样算法被配置为分别标准化第一个和第二个点云的点面密度或点体密度(此操作是非必需的，具体取决于点云的类型和密度分布)；逐点地，对于相应点云中的每个点作为查询点：在查询点周围形成预定半径的搜索半径球或找到最近的指定数量的最近邻点；计算从查询点到搜索半径范围内的所有相邻点或指定数量的最近相邻点中每一个点的向量；进行向量求和以得向量和(这里称为“和向量”)。

说明12-16

可选地，在公共坐标系中定义的三个正交旋转轴中的一个或多个中找到第二组向量相对于第一组的旋转角度，可探究第一组与第二组向量的角度分布之间的最大匹配度，过程包括：将第一和第二组向量中的向量置于公共的坐标原点；将以公共原点为中心并且半径等于向量长度的假想球面划分为表面区域；在公共坐标系中定义的三个正交旋转轴中的一个或多个中的每一个中，找到第二组向量相对于第一组的旋转角度，使得来自第一组向量的向量点分布与第二组向量的向量点分布，在此表面区域内达到最佳匹配。

以表面法向量为例，上述过程还包括分别归一化第一组和第二组向量的向量长度。

表面区域可以是相等面积的区域。区域的大小取决于具体应用。考虑因素包括所需的旋转对齐精度，这可能取决于扫描特征的尺寸和计算成本。向量点分布是向量点在每个表面区域内的频率分布。使用滤波以将每个点面密度低于预定阈的表面区域的点密度减少到零。另一种方法是，选择局部向量点密度较大区域的峰值，形心或众数(众数是最常出现的值)，即匹配这些高频分布的峰值或形心，而非匹配向量点的分布。如果向量集已经归一化，则可以省略归一化这一步骤。上述所谓的“三个正交旋转轴中的一个或两个”，可能是三个旋转轴。或者，如果已知两个现有的数据集已经围绕一个或两个轴旋转对齐，则上述所谓“三个正交轴中的一个或多个”就会是这一个或两个。

为了围绕一个轴对齐，向量可以沿着经线旋转到与已知水平平行的赤道平面上。这样可以节省内存和计算成本。因此，此处作为向量点分布的点密度，是被划分为多个部分的圆线上的点密度，而不是球面上的点密度。围绕起始于此圆线中心，方向为圆所在平面的法线方向的旋转轴，执行单轴旋转。

例如，可以通过数学相关函数找到最佳匹配。

这样做的优点是，基于每个表面区域的向量点的频率分布，对两组向量进行比较是在计算上高效的，并且为对齐两个向量集以致于对齐两个数据集，确定所需的旋转角度，提供了一个可靠的机制。

作为一个替代方案，将已经属于共同原点的向量沿着平面的法线方向，投射到赤道平面上，使得点密度的模式出现在赤道平面上。一个数据集的赤道平面投影相对于另一个数据集的赤道平面投影旋转，直到找到最佳匹配相对旋转。值得注意的是，以这种方式只能找到一个旋转角度。其优点是，该技术可以解决一些其他技术不易解决的问题，例如当天花板倾斜或处于屋顶内部时。

再一种替代方案是，可以将已属于共同原点的向量投影到圆上，并将该圆分成若干区域。向量点分布以与上述球面示例中相同的方式进行比较。值得注意的是，这种方式也只能找到一个旋转角度。

第一组向量中的向量和第二组向量中的向量可以分别是以下向量类型中的一种：

-由自动编码器(用于提取3D空间内的特征的无监督深度学习算法)生成并代表其一阶特征的向量，

-由自动编码器生成并代表其二阶特征的向量，

-由自动编码器生成并代表其三阶特征的向量，

-由自动编码器生成并代表第一，第二和/或第三阶特征的向量，

-表面单位法向量，

-和向量，

-散度向量，

-边缘向量，

-圆柱向量，

-复杂物体的向量，

-平面向量，

-点密度梯度向量，

-点密度梯度的散度向量，和

-梯度向量。

其中，需寻找的最大匹配度可以是：第一组向量的角度分布和第二组向量的角度分布之间；和/或在第一个一维数组和第二个一维数组之间；和/或在第一个二维数组和第二个二维数组之间；逐一类型计算相同特定类型的向量子集之间的匹配度，此任何平移或旋转角度下的匹配度是各个特定类型的匹配度的组合，或者是该组合的平均值或加权平均值。

在上述每一中匹配度搜寻过程中，都可以使用或不使用适当的滤波，平滑，阈值处理，平均，形心选择。

在一个实施方式中使用的每种类型的向量代表不同种类的特征，属性或物体。

此外，第一组向量的向量和第二组向量的向量均包括多个向量子集，多个子集中的每个子集代表着相应的点云的特定类型的向量，特定类型与其他子集的种类不同；其中，特定种类包括上面列表中的一个或多个类型。

可选地，在找到第一和第二组向量的角度分布之间的最佳匹配之前，对旋转对齐处理器进行进一步配置：过滤第一组和第二组向量，保留表面单位法向量代表任一一种模板形状的向量，并删除那些表面单位法向量不代表任一模板形状的向量。

作为进一步的选择，通过分别对第一组表面单位法向量和第二组表面单位法向量使用分割算法来实现识别。

模板形状是一个或多个边缘，大于最小阈值的平面，圆柱体，圆环，圆锥体，球体。此外，模板形状可以是原始形状的组合(边缘，大于最小阈值的平面，圆柱体，圆环，圆锥体，球体)。再者，模板形状可以是原始形状以预设角度互成角度的的组合。

分割可以基于一个或多个属性。可以是表面纹理，表面纹理的周期性，表面曲率，表面颜色，或表面粗糙度。

对于模板形状是边缘的情况，可以使用和向量代替表面单位法矢量。通过选择长度大于某个阈值，局部最大长度，或与局部表面法向量具有一定角度的和向量来提取边缘。之后，点云中具有这种和向量的点，在任何有边缘的球体中或球体上，形成线条或可区分的图案。和向量的方法会在本文档的其他地方更详细地描述。

寻找模板形状的另一种方法是应用阈值来选择高斯球上的高点密度区域并忽略其他点。或者找到局部密度最高的区域并丢弃其余区域。一种方法是计算球体上每个点的点密度，然后计算点密度的指数或对数，以此给出一些加权函数来分别突出高点或低点密度。或者找到高点密度区域中点的形心。或者将球体表面上某个区域内的点的所有向量叠加在一起。之后可以基于叠加的向量长度进行阈值处理。剩余的向量可以归一化为单位长度。另一种方法是识别和去除可能导致不正确对齐的任何周期性特征。这可以通过2D或3D傅立叶变换来完成，之后在傅立叶逆变换之前抑制或去除高密度点。

优点是，使用模板形状可以突出在各个数据集中的强(即高点密度)物理特征。因此，有助于找到具有代表性的向量集的角度分布之间的最佳匹配，从而以较小的计算成本获得精确的结果。

说明17-22

实施方式包括权利要求书中定义的系统。

实施方式包括权利要求书中定义的方法。

实施方式包括权利要求书中定义的点云的数据结构。

说明23-30

实施方式的第二方面包括的装置有：数据集采集单元，操作配置如下：在第一个时间点，采集代表感兴趣的对象的第一部分的第一个数据集，此数据集是n维扫描数据集；在第二个时间点，采集代表感兴趣的对象的第二部分的第二个数据集，此数据集是m维扫描数据集；获得三维坐标系中的一个或多个轴的指示，指示该三维坐标系内所需求的数据集的一个或多个轴旋转对齐；其中第一部分和第二部分包括重叠特征，并且m和n等于2或3。该装置还包括一个点云生成处理器，用于生成并存储代表第一个数据集的第一个点云和代表第二个数据集的第二个点云，第一个和第二个点云定义在三维坐标系中。该装置还包括一个对齐处理器，被配置为：围绕一个点云的坐标轴，或者围绕与每个轴分别成一定角度的组合，迭代旋转另一个点云中的每个点，并且对于三维坐标系中的一个或多条特定线中，在每次迭代时：将第一个和第二个点云投射到线上；沿着线，相对于彼此移动投影，以找到两个投影之间的最大相关性；并记录这个最大的相关性；识别所记录的最大相关性相对应的一个点云的旋转角度或旋转角度的组合；输出所识别的旋转角度，作为围绕第一个和第二个存储的点云的相应指示轴的旋转对齐角度，或者输出围绕第一个和第二个存储的点云的相应指示轴的旋转角度组合。

优点是，该装置可以以自动方式，确定相同感兴趣的对象的不同数据集之间的旋转角度，并且在扫描仪的视野内，无需放置物理目标点，也无需手动识别特定的自然目标点，从而在数据集中表征。

数据集是2D或3D数据集，也可以将其视为图像。成像装置可以是3D扫描仪等。每个数据集包含代表二或三维度空间中感兴趣的对象的2D或3D数据。其他维度(例如颜色)也可以包括在数据集中。

输入信号，即第一个和第二个3D数据集，可能局限在一个物理空间的扫描中。此外，实施方式也可以采集虚拟空间的2D或3D数据集作为第一个和第二个3D数据集中的一个或两个。

扫描数据集被描述为n维和m维，其中m和n定义空间的维数。可以在数据集中的每个空间点上记录附加信息，例如，时间，三个或更多个旋转角度，r，g，b的颜色坐标，或以下任何颜色坐标CIELAB，CIELUV，CIExyY，CIEXYZ，CMY，CMYK，HLS，HSI，HSV，HVC，LCC，NCS，PhotoYCC，RGB，Y'CbCr，Y'IQ，Y'PbPr和Y'UV(参考文献https://people.sc.fsu.edu/～jburkardt/f_src/colors/colors.html)以及从数据推导出的其他量，例如表面法向量或纹理的散度。空间维度可以用笛卡尔坐标，x，y，z，圆坐标，极坐标，经纬度，或任何其他空间坐标系表示。

一个或多个轴的指示可以由用户输入，也可以是装置中的默认值。

所测区域的第一个和第二个部分包括重叠的特征。这些特征要么在空间中直接重叠，要么具有可能重叠的特征，例如线，平面，圆柱等。基于某些常识，这些特征可以从第一个部分延伸到第二个部分。因此，一次扫描可以扫描直线铁轨或墙壁的一部分，第二次扫描可以扫描不同的物理空间，但是包括铁轨或墙壁的另一部分。如果已知铁轨或墙是直的，那么该装置可以将两次扫描旋转对齐至铁轨或墙。对每个扫描，可以使用模式识别来识别轨道或墙壁。在平移对齐的步骤中，该扫描将与垂直于轨道的二维平面对齐，或者与垂直于墙壁的一维直线对齐。如果在一定范围内存在多个杆或边缘特征互称角度，且他们都存在与两个非直接重叠的扫描内。然后，该设备可以沿着杆方向精确地定位一个相对于另一个扫描的扫描，并且在第一次扫描中仅存在第二扫描中的杆与延伸杆精确匹配的一个位置。则该装置可以精确地沿着杆的方向将一个扫描相对齐到另一个扫描，而且此对齐结果为唯一解。相似的，对于彼此不同角度的几个平面，甚至对于平面，杆，边缘，圆柱，环形，锥体和其他形状的混合，均可将两个扫描通过该特征对齐。这一点非常重要，因为它意味着没有必要让所有扫描在空间中物理重叠，只要在特征中存有一些共性即可，即两者中都出现一个特征。举一个自动驾驶汽车的例子，可以扫描道路上的边石，白线或黄线，铺平板边缘，墙面和边缘等特征，从而对齐较窄的非重叠扫描。

此外，在将各个数据集缩减为一维数组的步骤中，可以调整一个额外变量，例如比例或放大率，直到找到最佳对齐。此额外变量值随着平移而改变。增加或减少一个扫描相对于另一个扫描的尺寸，所有其他步骤相同。如果每个扫描来自不同的技术扫描仪，或者一个是2D的和一个3D的，那么它们的比例可能不会相同。有两种方法可以解决这个问题。第一种方法是，扫描相同的人工制品，如光罩或精确校准的标尺作为校准手段，然后调整比例，使得每个扫描的尺寸相同。另一种方法是，逐步变化放大率，并且逐步地围绕两个轴旋转，直到找到沿着所有线的最大相关性。换句话说，在寻找最大相关性的过程中改变附加维度(比例)。找到最大相关性后，将该放大系数应用于逐步变化的那个数据集以使两个数据集对齐。

可选地，对齐处理器还被用来修改所存储的第一个和第二个点云。具体实施方法为，围绕所指示的一个或多个轴中的每个轴或者某个轴，通过对应的已识别的旋转角度，相对于一个点云，旋转另一个点云，并将修改过的第一个和第二个点云存储为旋转对齐的点云。

可选地，对齐处理器还被配置为：在每次迭代时，记录沿着某条线的两个投影的平移值(可以被认为是相对移动)。这个平移值是在两个投影之间所发现的最大相关性所对应的平移值。对于所指示的一个或多个轴中的每个轴或者某一个轴：识别已识别的旋转对齐角度所对应的最佳平移值，从而到达最大相关性，并记录此最大相关性；并且通过沿着相应的特定线，将点云相对于彼此，以所识别的平移的长度和方向平移，从而修改所存储的第一个和第二个点云；并将修改后的第一个和第二个点云存储为单个合并的点云。

可选地，对齐处理器还被配置为：在每次迭代时，记录沿着某条线的两个投影的平移值。这个平移值是在两个投影之间所发现的最大相关性所对应的平移值。对于所指示的一个或多个轴中的每个轴或者某一个轴：识别已识别的旋转对齐角度所对应的最佳平移值，从而到达最大相关性，并记录此最大相关性；并输出每个指示的一个或多个轴的平移值。

特别地，平移以移动的量和方向的形式输出。方向由投影线决定，沿线的平移方向和平移量由投影的平移决定。

可选地，寻找两个投影之间的最大相关性，包括：将每个投影表示为一维点密度分布；迭代计算两个一维点密度分布之间的相关性；在每次迭代时，其中一个一维点密度分布沿着线相对于另一个点密度分布移动；并找出沿线的一系列运动之间的最大相关性。

可选地另一种方法来寻找两个投影之间的最大相关性，包括：将线划分为一系列相邻且具有预定长度的区间，并且对于每个投影，计算每组不同区间内的投影中的点数，每个区间内点的数量构成一维点密度分布；并且其中一个点密度分布在每次迭代中沿着线相对于另一个点密度分布移动，直到两组区间相互重合。该相关性是将一个投影在每个区间的点数与另一个投影在相对应的重合区间的点数，先乘积再求和得到的。

可选地，为了获得更精细的精度，可以减小预定的长度。但是当数组元素的间距太窄时，由于缺少每个区间相关的数据，该方法则会无效。这就需要一个方法以获得更精细间距，在间距足够大以使拟合有意义的条件下，尽可能精细地内插数组，从而将曲线拟合到直方图(一维点分布)。临界间距约等于平均点间距的几倍(例如，10倍)。

可选地，除了相应数据点的位置之外，点云还包含每个数据点的一个或多个属性中的每一个属性的数值，数据点在线上的投影除了包括数据点的位置以外，还包括一个或多个属性相应地数值；寻找最大相关性，除了包括计算两个一维点密度分布之间的相关性之外，还包括对于一个或多个属性中的某一个或每个属性，沿着该线，计算相应属性数值分布之间的相关性，并将两个一维点密度分布之间的相关性与一个或多个属性的数值分布之间的(某一个或每一个)相关性进行拟合，最大相关性是最大的拟合相关性。

优点是，这种拟合地方法更具鲁棒性和精确性。扫描仪可能可以记录除了x，y，z位置之外的有关数据点的其他信息。如激光探测与测距仪，它可以记录红外激光束的反射强度，而有些激光探测与测距同时还有高分辨率彩色摄像头，因此它们记录颜色，rgb，hsl，hsb或hsi的数据。此外，可以从每个位置的x，y，z点得到额外的数据，例如表面法线的散度，表面纹理等。因此，在投影到线上之后，可以计算每一个附加属性和其他不同变量的分布的相关性。所有这些相关性在正确旋转时，达到它们的最大相关幅值的角度应该相同。例如，如果大多数变量达到其最大相关值但其中一个变量不是，则该旋转仍然被视为正确的旋转，因为如果其中一个变量由于某种原因在一个数据集中不正确，其他变量仍将给出正确的旋转。举一个特别的例子，每个颜色变量rgb分别相关，因此红色分布应与红色分布相关。

拟合可以是相关性的和，也可以是找到一个旋转角度，在该旋转角度，一个预定比例或数量的变量达到相关性的最大值。

如权利要求中所定义的，实施方式包括一个计算机程序。

说明31-38

实施方式的另一方面包括一种图像处理方法，该方法包括获得一个点云来描述所测对象，该点云表征由多个单独的扫描组成，每个扫描是对该对象其中一部分的点云表示，每个扫描与一个或多个其他扫描重叠，并且与所述一个或多个其他扫描具有一个特定的旋转和平移关系，其中至少存在一个扫描，与其他多于一个的扫描相重叠。该方法的特点在于应用了一个全局对齐过程，该过程包括：多个单独扫描的每一个扫描都被看作是一个对象点云，将与对象扫描重叠的一个或多个其他扫描设置为参考点云，对于作为参考点云的每个单独扫描(以下称参考扫描)，在对象点云与该参考扫描之间执行旋转和平移对齐算法。并在描述所测对象的点云中，将所计算的对象点云和该参考扫描的旋转和平移关系作为初始估计。相对于该参考扫描，旋转和平移对象点云，直到满足过程误差标准，从而获得一个被修证的，对象点云和该参考扫描之间的旋转和平移关系；在参考点云中，合并对象点云与每个单独扫描之间的被修证的的旋转和平移关系；在描述所测对象的点云中，使用对象点云与参考点云之间的被合并和修证的旋转和平移关系。

更具优势的是，实施方式使用了一种技术来代替使用简单的成对的对齐，即使用一个扫描附近的所有其他扫描(不仅是与其相邻的单个扫描)来调整扫描的位置(即，相对于其余点云的旋转和平移位置)。依次对所有扫描重复此操作。这种“全局”对齐方法比简单的成对对齐更精确，并且迭代次数更少。

全局对齐过程包含多个步骤。“全局”表示多个扫描中的每一个是依次或并行地(或者是串行和并行处理的组合)单独处理。旋转对齐算法和平移对齐算法可以是相同的算法(同时施行平移和旋转对齐)，或者可以是两个单独的算法(一个算法的结果作为另一个算法的输入)。每一个旋转和平移对齐算法均可以是本文别处所描述的处理过程之一。算法可以是迭代最近点(ICP)算法。“迭代最近点”反映了算法的本质，即用于修证对象点云和参考点云之间的旋转和平移关系。这里使用的以及本文其他地方提到的迭代最近点算法可以是基于点对点的，或是基于点对面的。

通过在各分量(例如，三个成分包括三个旋转分量和三个平移分量)上找到旋转和平移关系的平均修订值，从而合并被修正的定义的对象点云与参考点云中的每个单独扫描之间的旋转和平移关系。

可选地，实施方式可以包括一次或多次重复全局对齐过程，每次重复中的过程误差的标准更加收紧。

例如，过程误差标准可以是在旋转和平移对齐中，用户期望的误差的总体目标容忍度。

实施方式可以被配置为，将旋转和平移对齐中的初始误差值与总目标容忍度之间的差值划分为有限步，每一步是全局对齐过程的一次迭代。

附图说明

实施方式将纯粹通过示例的方式描述，参考附图如下：

图1是一个实施方式的示意图；

图2是另一个实施方式的示意图；

图3是一个实施方式的系统示意图；

图4是一个实施方式中的处理流程图；

图5展示了实施方式的一个硬件设置；

图6-12展示了边缘检测算法；

图13是实施方式的另一方面的示意图；且

图14是展示图像处理方法的处理流程图。

具体实施方式

第一方面的详细描述

图1的描述

组件和组件互联概述

图1中所示的实施方式是体现本发明的3D数据集对齐装置10。装置10包括一个3D数据集采集单元12，一个存储单元14和一个旋转对齐处理器16。展示了某些组件互连和输入/输出。这里并不是展现组件之间的所有互连和交互，而仅仅示出了对于详细描述装置10而言重要的一些交互。

3D扫描采集单元

3D数据集采集单元12是被配置为成像装置从第一个位置和方向，采集第一个时间点的描述，第一个空间的第一个3D数据集的功能组件，第一个3D数据集是第一个三维点云，第一个点云中的每个点表示成像装置在第一个空间内的读数。3D数据集采集单元12还用于成像装置从第二个位置和方位，采集第二个时间点，描述第二个空间的第二个3D数据集，第二个空间和第一个空间重叠，第二个3D数据集为的第二个三维点云，第二个点云中的每个点表示成像装置在第二个空间内的读数。

在硬件方面，3D数据集采集单元12包括用于实时处理的可编程的CPU，和/或GPU，和/或FPGA，或者它们的阵列以及用于并行处理的计算机云中的存储器阵列，以及I/O(输入/输出)硬件配置为接收或读取第一个和第二个3D数据集。3D数据集采集单元12还可以包括易失性或非易失性存储器，用于在处理期间存储处理指令和图像数据。

成像装置可以是用于生成摄影测量扫描的装置，其使用两个或更多个相邻，并排或略微间隔的相机来观测3D场景。然后，使用一张照片中的稍微不同的特征间距与另一张照片中的特征间距来计算每个特征的深度。LIDAR的输出格式为点云。

成像装置可以是用于投影映射的装置：这利用投影到3D场景上的投影结构光图案。例子包括Kinect和Hololens。投影的图案可以是线条，网格或随机点。然后使用相机，通常使用一个广角镜头，观看场景。投射的光通常是红外线，以使人眼看不到它。

其他格式，诸如从视频流或网格生成的未对齐的拍照之类，可以在预处理步骤中被转换为点云，然后输入到实施方式。

输入3D数据集可能的数据格式包括.fls，.ptx，.leica格式，.ptl，.e57，.xyz，.pod，.wrl，.obj，.las，.laz中的一个或多个，它们通常用于测量应用，和DICOM.dcm，PAR/REC，.ima，NIFTI，它们通常用于医疗应用和其他格式的其他应用。数据格式可以是笛卡尔坐标或球面角度和径向坐标，或者是有利地选择的其他坐标以适合3D扫描体积或扫描方法的对称性。.pod有利于后处理清理和过滤。

几乎所有MRI扫描仪都以DICOM.dcm格式输出神经影像数据，这是一种标准化的医学图像格式。供应商特定格式通常是默认数据导出类型，例如，飞利浦扫描仪上的PAR/REC。制造商特定的DICOM格式的一个实例是“.ima”格式。对神经影像数据的分析通常从将供应商特定数据转换为称为NIFTI的数据格式开始，因为大多数分析组件不能直接读取原始数据。这些格式中的任何一种都可以用作实施方式的输入。

有关功能的更多细节

3D数据集采集单元是装置10的输入机制。输入是两个3D数据集。数据集的先决条件是它们与存储在公共坐标系中(此文档中“公共”的意思是对于两个数据集是共同的)的点云相兼容，并且它们是空间的3D数据集，并且至少是部分重叠的。第一个和第二个3D数据集可以是由同一成像装置采集的。然而，这里对成像装置和成像技术并没有要求，装置10被配置为旋转对齐来自不同成像装置的3D数据集，甚至是使用不同成像技术的成像装置。

第一个和第二个3D数据集可以从例如成像装置或预处理器发送，并且由3D数据集采集单元12接收。或者，第一个和第二个3D数据集可以存储在3D数据集采集单元12可访问的地址的物理存储器中，以便由此进行检索。

3D数据集采集单元12可以由装置用户配置，以实现从中获取3D数据集的存储位置的详细信息，例如通过接口。或者，3D数据集采集单元可以包括存储位置或界面，3D数据集由成像装置的用户提交或传输到该存储位置或界面(这里的“用户”意味着成像装置操作者，或者是分析或处理成像装置产生的3D数据集的任何一方)。

所示的3D数据集采集单元12和存储单元14之间的互连表示由3D数据集采集单元12将所采集的第一个和第二个3D数据集提交到存储单元14。存储单元14将第一个和第二个3D数据集存储为公共坐标系中的点的云。

获得的3D数据集是三维点的云。3D数据集采集单元12可以对获得的3D数据集执行处理，以定义公共坐标系中的各个点云(“公共”的意思是对于两个数据集是共同的)。在3D数据集中设置围绕三个正交旋转轴的旋转关系(即相对方向)，此旋转关系被提交以存储在存储单元14中或由存储单元14存储。

存储单元

存储单元14被配置为将第一个和第二3D数据集存储为公共坐标系中的相应点云。存储单元14是易失性或非易失性存储硬件，其可由3D数据集采集单元12和旋转对齐处理器16访问。存储单元14可包括控制器或管理单元，以控制对存储数据的读和写访问。

存储单元-通用坐标系

对于两个点云，不需要以相同的方式表达公共坐标系。然而，在存储两个点云的坐标系之间存在一个定义的空间和角度关系，使得无论存储中的点云如何表达，它们都在公共坐标系中定义。

旋转对齐处理器

旋转对齐处理器16被配置为：将存储的第一个点云变换为第一组向量，并将存储的第二个点云变换为第二组向量，其中第一组或第二组向量中的每个向量表示其相应点云中相应的点和相邻点之间的关系；在公共坐标系中定义的三个正交旋转轴中的一个或多个中，通过寻找到第一组向量的角度分布与第二组向量的角度分布之间的最大匹配度，找到第二组向量相对于第一组的旋转角度；存储围绕着所计算的最大匹配度的一个或多个正交旋转轴中的每一个轴的旋转角度；在公共坐标系中，围绕着所述三个正交旋转轴中的相应的一个或多个旋转轴，以所存储的旋转角度旋转第二个点云；并输出旋转后的第二个点云。

在硬件方面，旋转对齐处理器16是用于执行存储的处理指令的可编程处理器，以便实现变换，查找，旋转和输出的功能。另外，旋转对齐处理器16可包括或可访问易失性或非易失性存储器，用于在处理期间存储数据和存储处理指令。此外，它可以具有用于实时处理的CPU，和/或GPU，和/或FPGA，或者它们的阵列，以及用于并行处理的计算机云中的存储器阵列。可选地，每个节点具有处理器和存储器，并且存在节点阵列。

旋转对齐处理器-更多细节(包括嵌套球体)

旋转对齐处理器被配置为搜寻第一组与第二组向量的最佳匹配的那个旋转角度。在寻求围绕三个旋转轴的旋转对齐时，一个示例性的处理如下：将第一和第二组向量中的向量置于公共的坐标原点；将以公共原点为中心并且半径等于向量长度的假想球面划分为球面区域；针对第一组向量，计算每个球面区域的向量点的频率分布之间的数学相关性；旋转第二组向量，并重复计算；对第一组和第二组向量中的的每个表面法向量，执行长度标准化。可以对三个旋转角度中的每一个角度，以递增的方式完成旋转，直到在预定义的粒度范围内，围绕着每个旋转轴的预定义的角度范围内的所有角度组合都完成旋转计算。可以使用最佳匹配算法，例如模拟退火，以找到存在最佳匹配的角度组合。

如何量化匹配度

通过将角度空间划分为相等大小的区域，并比较每个区域中每组的向量数，可以找到两组向量的角度分布之间的数学相关性。通过对所有区域求和来计算积分值，其中来自每个区域的对积分值的贡献度与来自该区域中的两个向量组的向量数量的相似性成比例(例如，根据向量总量进行调节，或单个区域中一组向量的最大数量)。举一个特别的例子，比较可以包括将来自一个区域中的一组向量的向量点的数量乘以来自相同区域中的另一组向量的向量点的数量，并且将此乘积在所有球体区域上求和。

可能出现的情况包括，第一个和第二个3D数据集之间的旋转对齐仅需要围绕着一个或两个旋转轴，并且该结果被限制为，仅围绕着所已寻找到的与旋转对齐对应的旋转轴，旋转第二组向量。

旋转对齐处理器输出

结果可以输出到数据集的设备，装置，或3D数据集采集单元12获得数据集的位置。例如，数据集可以从一个成像装置获得，并输出到该成像装置，或者输出到与成像装置结合使用的计算机或其他设备，使得成像装置和数据集对齐设备10组合形成的改进的成像装置。输出可以仅包括旋转后的第二个3D数据集，例如，如果第一个3D数据集的原始坐标系与公共坐标系相同，则所获得的第一个3D数据集与输出旋转后的第二个3D数据集对齐。或者，可以输出第一个3D数据集和旋转后的第二个3D数据集，这里输出的是在一个定义的坐标系中旋转对齐的两个数据集。作为另一替代方案，可以输出到存储单元14，以便在下游处理中进行访问。

作为一个替代或附加输出(由图1中的第二个输出箭头表示)，输出是使扫描对齐的旋转角度，该角度对于跟踪成像装置的旋转运动是有用的。

在输出是旋转和/或平移对齐后的3D数据集的点云或其他格式的情况下，数据可以是以下一种或多种数据格式：fls,.ptx,.leica格式,.ptl,.e57,.xyz,.pod,.wrl,.obj,.las,.laz中的一个或多个，它们通常用于测量应用，和DICOM.dcm，PAR/REC，.ima，NIFTI，它们通常用于医疗应用和其他格式的其他应用。数据格式可以是笛卡尔坐标或球面角度和径向坐标，或者是有利地选择的其他坐标以适合3D扫描体积或扫描方法的对称性。

多种向量类型

通过利用每个点云的多于一个向量形式来进行对齐处理，可以获得特别鲁棒的和精确的对齐结果。本文件在图4的描述中列出了向量类型可能的不同选择。更多信息可以在英国专利申请GB1701383.0的公开版本的附录B中找到。

每种类型的向量表示3D感兴趣的对象的不同方面或数量，或者以不同方式表示它们。因此，表面法向量表示表面或表面的一部分。和向量表示边缘，角落，平面中的开口，和遮挡。散度向量表示边缘和角落，球体和圆柱体以及粗糙纹理表面。边缘向量表示边缘。圆柱向量表示圆柱体，管道和柱子。复杂的物体向量代表复杂的物体，如椅子。平面向量代表整个平面区域。点密度梯度向量代表点密度增加的方向，也可能是真实的密度或反射率，点密度梯度散度表示点密度梯度向量发散的终点，如局部高点密度的近点。梯度向量表示读数参数增加的方向，读数参数如颜色，亮度，曲率，粗糙度。因此，有利的是使用几种类型的向量来表示3D感兴趣的对象内存在的特征，结构和密度。这可以通过并行地将每一类型地向量构造一个相同地用来描述表面法向量的球面表示结构，将球体旋转在一起，依次对每个不同向量球体执行每个向量的相关或匹配来完成。或者将所有不同类型的向量绘制在相同的球面中，但标记为相应的类型。然后，当球体旋转并相关时，在每种类型的向量与相同类型的向量之间分别计算相关性。对于非标准化地向量，最小和最大向量长度之间的球体内部和外部空间被分成径向和周向体积分割段，每个分割段内的向量点或尖端的数量乘以另一个扫描的向量点或尖端的数量，并求和计算数学相关性。另外，也可以使用其他形式的匹配，例如将对齐的分割段求和，然后对所有的和求和。

诸如椅子之类的复杂物体可能需要由多个向量表示，例如，一个从椅子的底部指向顶部，以查看它是直立还是向哪个方向倒下，另一个向量从椅子的后面指向前面，表示椅子面向哪个方向。这两种类型的向量必须保持分离，因为它们必须仅与重叠扫描中的相同类型的向量计算相关和进行比较。

实施方式可以使用不同的向量形式，重复旋转对齐(以及可选的平移对齐)处理，并且合并结果。例如，表面法向量可用于第一次处理，和向量可用于第二次处理。本文件中公开的两个或更多个向量形式的任何组合都可以以相同的方式合并。

使用不同向量形式的处理结果可以以如下方法合并：

该方法包括：分别就每种类型的向量，找到所有旋转角度中，局部的最大相关性对应的旋转角度，并且对于所有其他类型的向量，记录该旋转的相关性。搜索方法可以使用粗略角度步长来找到几个高相关值，然后可以通过使用精细角度步长，来收敛并获得这些旋转中的最大相关性。该方法包括制作一个表(见下表1)，将这些旋转值填入第一列中，并在每个相邻列中填入每种类型的向量的相关性幅值。将每行中的所有相关性加在一起，并将总和填入最右侧的那一列中。在最右侧的那一列中查找具有最大值的那一行，并读取左侧列中的旋转角度，作为所需的旋转角度。更加有利的做法可以是，在执行整行的相关性求和之前，将每个不同向量类型的每列的相关性幅值乘以不同的加权因子。这些加权因子是通过实验确定的，或者通过了解不同类型的向量对于不同感兴趣的对象的相对重要性来确定，这可以在过程开始时指定。

表1：用于对齐处理的不同向量的组合表示

图2的描述

组件和组件互联概述

图2中所示的装置是本发明的3D数据集对齐装置10。装置10包括图1中所示的组件(上文中提供了图1的详细描述，在此不再重复)，和平移对齐处理器18。平移对齐处理器18与旋转对齐处理器16互连，即第一个和第二个3D数据集可以通过旋转对齐处理器16输出到平移对齐处理器18。或者，如平移对齐处理器18和存储单元14之间的互连所示，平移对齐处理器可从存储单元14检索旋转对齐的3D数据集。

作为另一替代方案，平移对齐处理器18从除旋转对齐处理器16之外的数据源，接收旋转对齐的3D数据集。

平移对齐处理器

平移对齐处理器18被配置为：对于公共坐标系中的三条线中的每条线，其中三条线中的每对线是不平行的，并且三条线中的至少有一对线是非共平面的：相对于任意原点的，记录第一个点云每个点在这条线上投影的位置；将记录的位置存储为第一个一维位置数组；相对于任意原点，记录旋转的第二点云每个点在这条线上投影的位置；将记录的位置存储为第二个一维位置数组；找到沿着第二个一维位置数组的线，相对于第一个一维位置数组的线的平移，该平移是第一个和第二个一维数组之间的最大匹配度所对应的平移值，并记录该平移。平移对齐处理器18被配置为，在公共坐标系中输出第一个点云和旋转的第二个点云合并的点云，其中旋转的第二个点云是沿公共坐标系中的三条线中的每条线以相应平移量平移而得的。平移对齐处理器18将所接收的旋转对齐的数据集存储在存储单元14上，以备合并点云时使用。这样，保留所接收的旋转对齐的数据集的副本，而在沿着线找到平移对齐的过程中的信息未予保存。作为输出合并点云的替代或补充，平移对齐处理器18可输出平移量(即沿三条线的距离)以供使用，例如，用于跟踪成像装置在成像过程之间(对于两个数据集)的移动。

作为进一步的选择，可以针对不同的三条线重复该过程，并且在输出步骤之前，比较各个记录的平移对齐。例如，每组三个记录的平移，可以由公共坐标系中的单个点表示(从共同原点，沿着的三条线，依次平移记录的距离，以到达这个单个点)。如果这些点在彼此的阈值距离内，则沿着相应线的任一组平移可用于生成输出结果。反之，则可以重复该过程。

平移对齐处理器18可以被配置为避免使用投影有周期性的线。

作为用于找到平移以对齐点云而不将点云降维的替代方法，该方法可以包括在两个扫描中找到对应可匹配的3D物体和特征。找到使这些3D物体和特征对齐的平移向量。然后找到这些平移向量中最吻合的平移向量。通过绘制向量长度和向量相对于三个正交轴的角度的直方图来完成的。然后选择最吻合的长度和角度，并且选择在最吻合向量的小范围内的那些向量，并丢弃其余的向量，作为去除异常值的方法。此异常值是由两个扫描中的3D物体和特征之间的不正确对应性引起。

平移对齐处理器-投影的细节

例如，三条(或更多条)线可以是相互正交的。两条线的平面可以是水平平面。或者两条线的平面也可以是场景中的地板，墙壁或平面。线上的投影是沿着与线成一定角度的向量或沿曲线的云中的每个点到该线的投影。对于云中的所有点，投影到线的向量角度是相同的向量。或者，该向量可以是点的位置的函数，所述函数对于两个点云都是一致的。可以是沿着一条曲线，投影到线上。例如，一个圆柱体围绕其圆周移动所有点以位于一条直线上，或者径向投影到圆柱的轴线上。此外，在行星尺度上或对于另一个成像的球形物体，可以投影到纬度和经度线以及球体的半径上。这意味着纬度和经度线不是直线，而是圆形线。

图3的描述

组件和组件互联概述

图3中所示的系统是本发明的3D数据集对齐系统10。装置10包括图2中所示的组件(上文中提供了图2的详细描述，在此不再重复)，和成像装置20。成像装置20被配置为，通过读取读数并将读数转换为三维位置，以对空间进行成像或测量。多个这样的读数形成由数据集代表的空间(或对象)的图像。

扫描

成像装置20可以生成一个点云，每个点对应于一个读数，或者成像装置20可以生成具有某种其他格式的数据集，其中由3D数据集采集单元12执行到点云的转换。由成像装置20生成的每个数据集可以包括在成像过程中的连续点处记录的数据(例如扫描视场)，每个点与其邻居点，以分辨率和方向指示的程度，相互分开。在成像过程中，每个点记录关于点相对于成像装置20的位置的数据，并且每个由成像装置生成的点，响应于读数，换句话说，数据集中的每个点代表一个成像装置20的读数。尽管图3示出了单个成像装置20，但是也可以是不同的成像装置20负责采集每个数据集。

扫描仪与输出的关系

成像装置20的用户，或生成数据集的一方，也可以是装置10的输出的目的地。从生成数据集的一方的角度来看，对于成像方，包括成像装置20和装置10的系统是成像装置20的一个改进的系统。

扫描仪举例

成像装置20可以是例如：

·一个手持式的激光探测与测距(LIDAR)扫描仪，

·一个基于静态三脚架的LIDAR扫描仪，

·一个穿地雷达，

·一个3D LIDAR扫描仪，或一个生成3D数据集的2D LIDAR扫描仪，

·一个电阻率断层扫描(ERT)或电阻率成像(ERI)扫描仪，

·一个CT(计算机断层扫描)或CAT(计算机轴向断层扫描)扫描仪，

·一个正电子发射断层扫描(PET)扫描仪，

·一个MRI(磁共振成像)扫描仪，

·一个核四极杆扫描仪，

·一个3D太赫兹波扫描仪，

·一个基于结构光图案的投影映射扫描仪，

·一个使用间隔开的2D相机的摄影测量扫描仪，

·一个3D超声扫描仪，

·一个3D地震扫描仪，或者

·一个3D声纳扫描仪，

·一个光学干涉仪，

·一个摄影仪，

·一个投影成像仪，

·一个表面3D分析仪器，如Alphastep，Talystep，原子力显微镜，SNOM，

·一个焦平面扫描仪，Z-stack

扫描可能包括：

·焦点的形状，

·阴影的形状，

·纹理的形状，

·剪影的形状，

·阴影的形状，

·模板的形状，

·对称的形状，

·不同照明和视点的形状，

·运动或光流的形状，

·互动的形状，

·位置对比的形状，

·散焦的形状，

·计算机辅助设计，计算机生成的模型或计划生成的虚拟3D计算机的图像，

关于示例性扫描仪的更多细节在英国专利申请GB1701383.0的公开版本的附录A中提供。

图4的描述

概述及与其他图像的关系

图4是示出实施方式的方法或由实施方式执行的流程图。成像步骤S101是成像装置20的功能示例。预处理步骤S102是成像装置20或3D图像采集单元12的功能示例。点云存储步骤S103是与存储单元14协作操作的3D图像采集处理器12的功能示例。点云到向量的变换和滤波步骤S104，寻找向量角分布的最佳匹配的步骤S105，并且旋转对齐点云步骤S106是旋转对齐处理器16的功能示例。映射点云到线的步骤S107，寻找投影最佳匹配的步骤S108，和平移对齐步骤S109是平移对齐处理器18的功能示例。步骤被分成“a”和“b”，表示分别对两个图像执行。

扫描

在步骤S101a中，3D场景或对象的一个部分由成像装置20成像以获得第一个点云。在步骤S101b中，由3D场景或对象的另一部分，获得第二个点云。这个另一部分与在步骤S101a中成像的3D场景或对象重叠或具有共同部分，例如，完全重叠但在不同的时间点拍摄，使得3D扫描或对象具有随着时间的推移而改变。步骤S101a和步骤S101b可以同时或在不同的时刻执行。在负责采集各个图像的成像装置中，其扫描方向可能存在差异，围绕三个旋转角度的旋转对齐差异被称为α，β和γ，此三个差异至少部分未知。在负责采集各个图像的成像装置，扫描位置可能存在差异，即Δx，Δy和Δz的平移位置差异，此三个变量也是至少部分未知。

可选地，相对于点云点或相对于外部参考坐标，可以直接记录扫描仪在每次扫描内的位置(例如，在x，y，z坐标中)。该信息可以与每个数据集产生的3D数据集，作为元数据一起存储，或者它可以是从3D数据集本身导出的信息(例如，如果位置坐标是相对于与扫描仪位置相对应的原点)。扫描仪的位置可以另外存储在代表3D数据集的.xyz文件中。

滤波

在步骤S102a和S102b中，在3D图像采集单元12(即通过成像装置采集)采集之前或者在采集(即通过3D图像获取单元12采集)之后，对各个图像执行可选的预处理。

是否执行预处理以及执行哪个预处理可以由装置的用户选择，例如两个3D数据集一起提交的参数。此外，装置10可以提供一个接口(例如GUI或文本接口)，用于接收执行指令，例如在实施方式中选择算法，此实施方式存储用于执行且目的相同的多个算法，或者可选执行的算法。

更详细的滤波

预处理可以包括以下中的一个或多个步骤：

-执行清理算法，通过移除浮动在3D空间中的孤立点的假象或群集，来过滤和清理图像，这些孤立点通常出现在成像装置询问与远处物体处于相同视线中的附近物体的边缘时，或者当光束从有光泽的表面反射或从烟雾中散射出来时；

-执行测距算法，通过使用范围过滤来过滤和清理图像；

-空间采样，以使点密度均匀化；

-在扫描时检测和移除由于物体或人在场景中移动而引起的杂散点；

-检测和移除与场景中的物体或几何形状相对应的点，这些点可能使之后的配准过程更加困难(例如，检测树和灌木树叶，或其他不规则形状，这些由于其不均匀的空间分布，会使扫描配准更加困难)或者因为用户对这些不感兴趣(例如，当用户仅对墙壁位置感兴趣时，可移除房间内的家具和人员)。

-通过将平面拟合到平坦表面，或将弯曲的低阶多项式表面拟合到曲面，来平滑数据。

去噪

预处理还可以包括在各个点云上执行去噪算法。有许多种去噪算法可用于此目的。例如，可以使用双边去噪算法。实施方式还可以使用描述噪声的函数来执行反卷积，所述函数是距离和角度的函数，该距离和角度在3D图像采集单元采集时必须预先测量。此外，预处理可以包括使用维纳(Weiner)滤波器，可自动测量噪声并将其滤除。另一种方法是卡尔曼滤波器，对于实时噪声消除是最佳选择，例如在自动驾驶汽车应用中去噪。

存储

在步骤S103a和S103b中，图像以定义在一个公共坐标系的格式，存储在存储单元14上。该公共坐标系可以是一个概念上的3D工作空间。公共坐标系中两个图像的相对位置和方向可以是任意的，或者可以通过图像的原始坐标系之间的关系来确定。如果成像装置记录了关于水平，罗盘方位，高度者这些信息，那么该信息可以用于工作空间中，以使之后的穷举匹配计算量最小化。

生成向量

在步骤S104a和S104b中，将点云转换为相应的向量集。可选地，可以在变换之前稀疏点云，使得点密度在两个图像上近似均匀。可以使用八叉树或K维树算法来执行稀疏化，每个算法将点与相邻点结合，以获得均匀的粒度或采样。

八叉树算法将空间切割成围绕着一个立方体的8个相同的立方体，查询点在这个立方体的中心。每个立方体中的所有点都被该立方体中心的单个点替换。使用K维树算法在三维空间中找到K个最近点。沿着x，y，z轴将3D空间切割成小立方体。每个立方体中的所有点都被每个立方体中心的单个点替换。

表面法线

在两个点云上执行相同的向量生成技术/算法。

向量集可以是表面单位法向量。在这种情况下的变换包括选择一组邻居点，例如使用K个附近最近的固定距离邻近点，计算协方差矩阵，其中记录查询点和邻居点集的位置，并求解协方差矩阵，找到这些点的三个特征值和三个特征向量。具有最小特征值的特征向量即是查询点的法向量，并且将它归一化。此外，可以将小平面块与查询点附近的点对齐，以使点与平面的距离最小化。然后，该小平面块的表面法线可以被认为是该点处的表面法线。选择表面法线的方向，使其指向扫描仪，方法是确保表面法向量与从该点到扫描仪的向量之间的角度始终小于180度。这确保了，例如，楼层中的所有表面法向量应该大致向上指，向并且天花板中的所有法向量通常向下。

实施方式中的扫描仪的位置，与3D数据集一同存储为元数据，或者是从扫描数据导出的位置。表面单位法向量可以被配置，使得它们都指向扫描仪。作为替代方案，表面单位法向量可以被配置，使得它们都指向远离扫描仪。无论选择哪个方向，两个3D数据集都是一致的。这是通过要求表面法向量和从该点到已知扫描仪参考位置的向量之间的角度总是小于180度(或者在大于180度的替代情况下)来完成的。如果不然，则反转表面法线的方向。这确保了，例如，楼层中的所有表面法向量应该大致向上，并且天花板中的所有法向量通常向下。

其他向量表示

作为表面单位法向量的替代，或者为了生成一个或多个其他类型的向量，使得可以在扫描之间比较多个种类的向量(彼此独立并且合并相应的旋转比齐)，可以是使用以下技术中的一种或多种生成向量场(即，向量集)：

可选择性地使用采样算法，该采样算法被配置为分别标准化第一个和第二个点云的点面密度或点体密度(此操作是非必需的，具体取决于点云的类型和密度分布)；逐点地，对于相应点云中的每个点作为查询点：在查询点周围形成预定半径的搜索半径球或找到最近的指定数量的最近邻点；计算从查询点到搜索半径范围内的所有相邻点或指定数量的最近相邻点中每一个点的向量；进行向量求和以得向量和(这里称为“和向量”)。

为了减少角度噪声，通过在每个点周围创建一个具有适当半径的计算球空间来执行平滑处理，并且将其中所有的和向量相加在一起。或者，计算球空间可以用计算圆柱空间代替，其所有边缘以适当的半径为中心。可以基于和向量的长度或角度方向来过滤和移除，或选择，或标记点云中的点，例如，可用于提取边缘，在计算平移对齐时可以仅对齐这些边缘。

当和向量变换到高斯球时，它们的头部轨迹通常表现为几乎连续的“飘带”特征，从高斯球的中心向外辐射，但不一定沿着半径，而飘带的末端远离原点，且沿远离径向最快的角度发散。因此，应该使用有利的滤波方法来选择一个和向量长度范围，以选择在两个重叠扫描的每一个扫描中清晰显示的同一个飘带的共同部分。然后飘带的这个部分可以用于对齐。有利地，可以首先对飘带使用空间滤波，以通过将线段或低阶多项式曲线拟合到飘带，来平滑它们。有利地，在滤波之后，可以对和向量进行归一化处理，以将飘带的图案投影到高斯球的表面上。在这种情况下，可以在高斯球的表面上方便地执行二维相关计算，而不需要在3D空间内进行三维相关计算。

如果查询点位于平面的中间，则和向量的幅度几乎为零，并且向量的方向几乎是随机的。如果查询点靠近平面的边缘，则和向量的幅度要非常大，其幅度随着查询点朝向平面的边缘移动而增大。和向量处于平行于平面的位置，则指向远离并垂直于任何附近的平面边缘。如果边缘在两个平面之间的拐角，那么当查询点接近该拐角时，和向量开始指向平面之外，并且位于该拐角，此时和向量的长度最长，并且指向与两个平面大致相等的角度。对于3个或更多平面之间的拐角，结果相似。通过适当的过滤和区域生长，可以识别位于边缘或拐角处的点。可以通过和向量或归一化的和向量与附近平面或局部表面法线的角度，来区分边拐角处的边缘。

和向量的长度表示点云中的点起始位置位于边缘或拐角处的可能性。它与附近表面法向量的夹角可以通过向量点积，再除以两个向量的长度的乘积，并找出这个值对应的角度的余弦来计算。该角度表示该点是否在边缘或拐角，如果是，属于什么类型的边缘，例如两个平面相交的边缘，或平面中的遮挡或洞，例如门口或窗口。这些向量的相关或匹配是高斯球内的体积相关或匹配，因为它们具有不同的长度。为了避免这种复杂性，可以将向量的长度视为与这些归一化的向量相关联的读数或参数。这些读数或参数将被合并到高斯球表面上的图案中，这可以被当作是这些图案的亮度或颜色。这意味着这些读数或参数必须保持不同，并且与其自身类型的读数或参数相关或匹配。

可以通过将其长度除以计算球内或邻域中的点数来对和向量进行归一化。或者，可以将其归一化为单位长度，在这种情况下，它可以称为“中值向量”(使用中值向量来确定查询点是特征边缘的一部分还是特征内部的一部分的算法，在图8中展示)。可以过滤未归一化的和向量，以选择长度最长的或大于阈值的那些和向量，或者可以在首先平滑分布之后完成过滤，以找到与边缘相关联的点。可以根据它们与局部表面法向量的角度，来过滤未归一化或归一化的和向量，以找到与边缘或拐角相关联的点，并确定边缘或拐角的类型。

找到中值向量的另一种方法是，选择一个查询点并在其周围形成一个小的搜索半径球，或找到最近的指定数量的最近邻点。计算包括查询点在内的所有这些近邻点的形心。然后计算从查询点到形心的向量。该向量的长度可以是查询点和形心之间的欧几里德距离，或者更常见的是长度被归一化为单位长度。

用于将点云转换成相应的向量集的另一个技术/算法包括：

选择性地执行采样算法，该算法被配置为分别标准化第一个和第二个点云上的点面密度或点体密度(该操作是可选的，取决于点云的类型和密度分布)；对于每个点云单独执行；对于各个点云中的每个点作为查询点：计算表面法线。然后计算查询点处的法线与，小搜索半径球内的所有近邻点或者指定数量的最近邻点之间所有近邻点的法线之间的角度偏差。这可以通过找到相邻点的表面法向量，或某个搜索半径内的点的表面法向量之间的点积，然后找到此点积的反余弦来找到角度来完成。找出平均角度偏差。局部“散度向量”则是与该点处的表面法向量在相同方向上的向量，但其幅度或长度与平均发散角度相等或成比例。实际上，表面法向量是通过它们的散度缩放而得。图10-12示出了用于找到散度向量的算法。在另一种方法中，在每个点上计算表面法向向与和向量，并计算它们的点积或内积。点积的大小可用于缩放一个向量的长度。选择的散度向量可以是表面法向量或该点处的和向量。这样做的好处是点积为正或负，可以决定散度向量的方向，以及边缘是凸的还是凹的。当用于对齐时，它意味着凸边缘将与凸边缘对齐，同样地，凹边缘与凹边缘对齐，因此减少了错误对齐的可能性，如凹边缘与凸边缘的错误对齐。为了减少角度噪声，通过在每个点周围创建一个具有适当半径的计算球空间来执行平滑处理，并将计算球空间中的所有散度向量加在一起是有效的。或者，计算球空间可以用计算圆柱空间代替，其所有边缘以适当的半径为中心。可以基于散度向量的长度或角度取向来过滤和去除，或选择，或标记点云中的点，例如，在计算平移对准时，提取边缘，该边缘之后仅可以与边缘对齐。

可以使用滤波来选择到某个小的计算局部区域最长的局部散度向量，或那些长于某个特定的阈值的向量。这可以在预先平滑散度向量分布之后进行，以减小角度和长度噪声和浮动。所提到的小计算局部区域通常会大于用于找到表面法线的计算球或邻域的大小，并且需要合理地选择。

由于散度在平面相交的边缘处最大，并且在平坦的平滑平面的中间最小，因此与滤波后的散度向量相关联的点与那些边缘相关联。此外，散度的空间分布可用于区分边缘是锐利的还是圆形的，以及它是否是3个或更多个平面之间的边缘或拐角，并且这些可以通过适当的滤波来分离。散度向量的长度也将指示曲面的局部半径。因此，通过适当的过滤和基于长度的区域增长，例如，可以从3D扫描数据集中将球体和圆柱体分割出来。这些向量的相关或匹配，需要在高斯球内执行体积相关或匹配，因为它们具有不同的长度。为了避免这种复杂性，可以将向量的长度视为与这些归一化向量相关联的读数或参数。这些读数或参数将被合并到高斯球表面上的图案中，这可以被当作是这些图案的亮度或颜色。这意味着这些读数或参数必须保持不同，并且与其自身类型的读数或参数相关或匹配。散度向量的方向可以是正是负，这取决于散度或曲面的局部半径是正还是负，正值表示边缘是凹的，负值表示边缘是凸的。

当平面的表面是粗糙的或有表面纹理时，平面中间的散度向量将有一定的幅度。在这种情况下，滤波必须排除长度与这种平面中心相关联的散度向量，但是要包括长度更长，且与与边缘或拐角偏离更大的散度向量。平面上的散度向量的长度也表示了表面纹理或粗糙度，其通常与制造表面的材料有关。因此，可以识别具有相似长度散度向量的区域，这些区域通常由相同材料制成，并且链接在一起成为一个物体，以实现物体分割。

用于将点云变换成相应的向量集的另一技术/算法包括：

查找与边缘相关联的点云中的点。这可以通过找到和向量并对其进行滤波，或通过找到散度向量并对其进行滤波，或通过使用其他已知技术(例如角度准则或BAO算法)，或通过使用诸如随机抽样一致(RANSAC)平面检测算法，或霍夫变换平面检测等技术完成。然后应用RANSAC线检测算法，找到每个平面的边界。RANSAC线检测算法可以直接单独使用，但首先找到平面，然后再找到边缘更为可靠。角度准则技术的一个示例如图6所示。图7示出了BAO算法的示例。“边缘向量”是通过使用已知方法，将直线或直线段拟合到边缘点来生成的，例如最小化该线与该线范围内所有点的垂直距离。这些线段的方向形成边缘向量的方向，并且它们的大小可以是将点拟合到一定精度内的最长线的长度，或者幅度可以归一化为单位长度。向量是否沿着线指向一个方向或其反方向，可以通过将它们全部朝向或全部指向扫描仪来确定，或者通过将它们向上指向凸边缘并向下指向凹边缘来确定，反之亦然。这样的边缘向量位于平面或边缘中，并且通常与这些点处的和向量或散度向量成一角度，通常是直角。对边缘的多个点执行一定程度的平均，从而降低噪声。这些向量的相关或匹配是高斯球内的体积相关或匹配，因为它们具有不同的长度。为了避免这种复杂性，可以将向量的长度视为与这些归一化的向量相关联的读数或参数。这些读数或参数将被合并到高斯球表面上的图案中，这可以被当作是这些图案的亮度或颜色。这意味着这些读数或参数必须保持不同，并且与其自身类型的读数或参数相关或匹配。或者，可以使用分割算法来找到并区分边缘。这可以基于例如曲率，反射率，尺寸，面积，形状，纹理，表面粗糙度，颜色，到扫描仪的方向和距离，以及相邻平面或相邻平面法线之间的角度等参数组合来完成。然后，可以将每个不同的分割后边缘的边缘向量标记为不同类型的边缘向量，这可以通过基于边缘上的点的长度或数量，设置其长度或者仅标记它来完成。这确保了可区分的相同类型的边缘，仅与重叠扫描中的相同类型的其他边缘相关联。

作为表面单位法向量的替代或附加向量集：第一组向量包括圆柱向量，第二组向量包括圆柱向量；并且将第一个点云变换为第一组圆柱向量，并将第二个点云变换为第二组圆柱向量，包括：使用一种方法识别三维数据集中的圆柱体，并找到它们的半径，位置和方向。然后，“圆柱向量”沿着，位于并平行于所找到的圆柱的轴的方向，并且向量幅值或长度与每个找到的圆柱的半径的大小相关。圆柱向量是否沿着圆柱轴线指向一个方向或反方向，可以通过将它们全部朝向扫描仪或者全部远离扫描仪来确定。圆柱向量也可以归一化到单位幅度。一个用于生成向量场的曲率算法的示例在图9中示出。

几种已知的识别圆柱体的方法有，例如高效霍夫变换，高效霍夫变换与RANSAC，或者投影到高斯球体后找到较大的圆圈等方法。但是，如果高斯球上有许多圆柱和其他特征，则会导致噪声增大，可能很难用上述方法检测圆柱，在这种情况下，下面的方法更有效。

首先计算表面单位法向量。使用分割算法识别具有相同曲率或在一定曲率范围内的所有区域，并保留与这些区域相关联的点以供进一步处理。可以使用已知技术计算曲率，例如：使用PCA计算表面法线时得到的特征值，或者是过滤散度向量使其幅值分布在一定范围内时得到的特征值，选用最小特征值λ0，(λ0/(λ0+λ1+λ2))，或(λ0/(λ0+λ1)，或λ0/λ1，或某些组合来表示曲率。一个分割算法可用于查找和区分圆柱。分割可用来减少需要搜索的点的数量，此算法基于曲率，反射率，大小，面积，形状，纹理，表面粗糙度，颜色，到扫描仪的方向和距离，表面法线的方向等参数的组合，并在下一部分中详细介绍。然后，可以将表示每个不同的已分割的圆柱体的圆柱向量标记为不同类型的圆柱向量。这可以通过基于圆柱上的点的长度或数量，设置其长度或者仅标记它来完成。这确保了可区分的相同类型的圆柱，仅与重叠扫描中的相同类型的其他圆柱相关联。

随机选择两个点和它们的法向量，并假设它们都位于同一个圆柱体上，根据圆柱体的几何特性将点拟合到圆柱体模型上，计算圆柱体模型的方向，半径和位置。在位于彼此的一定距离内，选择两个随机点是有益的。计算云点的所有点与圆柱体表面的法向距离。使用阈值并仅保留到该柱面模型的特定距离内的点。在其他可使用的滤波技术中，检查每个点的表面法线与圆柱模型的轴的夹角是否在可接受的范围内。记录拟合到该圆柱模型的点数。然后重复整个过程，找到拟合点数最多的圆柱体。在重复整个过程之前，使用所有拟合到该圆柱模型的点来重新计算圆柱模型的方向，半径和位置参数通常很有帮助。一旦找到了良好的圆柱体模型及其表面曲率，表面角度偏差或粗糙度，就可以研究其表面附近的点，看它们是否在这些圆柱参数的范围内，以使用区域生长技术。

这些向量的相关或匹配是高斯球内的体积相关或匹配，因为它们具有不同的长度。为了避免这种复杂性，可以将向量的长度视为与这些归一化的向量相关联的读数或参数。这些读数或参数将被合并到高斯球表面上的图案中，这可以被当作是这些图案的亮度或颜色。这意味着这些读数或参数必须保持不同，并且与其自身类型的读数或参数相关或匹配。

类似地，可以定义其他向量来表示环形，圆锥形，截头锥体，抛物面，双曲面，椭圆体等。

用于将点云变换成相应的向量集的另一技术/算法包括：

使用方法识别3D数据集中的3D复杂物体并找到它们的位置和方向。虽然该算法可针对任何类型的复杂物体，但是这里为清楚起见而用椅子作为复杂物体的一个例子。如果3D物体是可用的，则可以使用诸如3D物体模板匹配的已知方法。或者可以使用更普适的深度学习方法，使用数量庞大的数据库来训练深度学习模型，数据库包括涵盖不同方位和尺寸，不同类型的椅子，以及其他类型物体，例如通常可以在带有椅子的房间中包含其他区分于椅子的物体。然后，一个或多个复杂物体向量可以与复杂物体的位置，方向和可能的比例相关联。因此，就椅子为例，一个向量可以沿着椅子的后部向上指向椅子的座位，而第二个向量可以与第一个向量成一定角度，并且位于椅子座位的平面中，且指向远离椅背的方向。这些不同类型的向量中的每一个向量都需要可区分的，并且必须仅在高斯球上与相同类型的向量相关或匹配。因此，垂直于椅子座位的向量不得与位于椅子座位平面内的向量相关或匹配。此外，可以首先使用分割算法来查找和区分复杂物体。分割算法可以基于曲率，反射率，尺寸，面积，形状，纹理，表面粗糙度，颜色，到扫描仪的方向和距离等参数的组合来完成。然后，可以将表示每个不同的分割的复杂物体的向量标记为不同类型的复杂物体向量。这可以通过根据复杂物体上的点的面积或数量，纹理，或反射率，设置其长度或仅标记它来完成。这确保了可区分的相同类型的复杂物体，仅与重叠扫描中的相同类型的其他复杂物体相关联。

用于将点云变换成相应的向量集的另一技术/算法包括：

寻找表面法向量。通过已知方法执行平面检测，例如RANSAC平面检测，霍夫变换平面检测，区域生长，或是上述方法的结合。他们是基于表面曲率，表面法线角度偏差，颜色，反射率，粗糙度，或距平面的距离。也可以通过将向量表示在高斯球上，并寻找表面法向量的集中或高密度区域来找到平面。计算表面法向量密度的形心来确定平面的向量。

一旦找到平面，就计算每个平面的面积，或者找到与该平面相关的点的数量。然后，每个找到的平面由“平面向量”表示，该平面向量是表面法向量，但其长度等于平面的面积，或者是与该平面相关的点的数量，并且位于形心或是平面的重心。或者，可以使用分割算法来找到并区分平面。这可以基于例如曲率，反射率，尺寸，面积，形状，纹理，表面粗糙度，颜色，到扫描仪的方向和距离的组合来完成。然后，可以将每个不同分割的平面的平面向量标记为不同类型的平面向量。这可以通过基于平面上的点的面积或点数来设置其长度或仅标记它来完成。这确保了相同类型的可区分平面仅与重叠扫描中的相同类型的其他平面相关联。或者，可以将小模板平面拟合到点云，以使点到平面的误差最小化。然后，如果小模板平面的法线和其他属性的方向相似，则它们可以连接在一起，增长区域并延伸平面。此外，在分割并找到平面之后，可以通过最小化点到平面的误差，来拟合与平面类似的区域的大模板平面。这有效地使平面上的所有点均匀化，因此可以使局部噪声和误差最小化。或者，在分割并找到平面之后，可以将分割物体上的所有表面法线加在一起。然后可以用平面的点数或面积来重新缩放。或者，除了找到平面，还可以将指向彼此的小角度范围内，相对靠近并且方向相似的所有表面法向量都加在一起，生成向量的和。在高斯球上识别高密度表面法向量的位置，并找到形心，然后在形心的一个小的角度范围内将所有表面法向量执行向量求和，这样可以最方便地将表面法向量表征到高斯球上。这些向量的相关或匹配是高斯球内的体积相关或匹配，因为它们具有不同的长度。为了避免这种复杂性，可以将向量的长度视为与这些归一化的向量相关联的读数或参数。这些读数或参数将被合并到高斯球表面上的图案中，这可以被当作是这些图案的亮度或颜色。这意味着这些读数或参数必须保持不同，并且与其自身类型的读数或参数相关或匹配。

这样的优点是可以显著地减少在高斯球体上必须旋转的向量的数量，从而加快计算速度，并且通过提取单个平面来平均各个点的噪声和表面法向量的角度噪声。因为平面通常含有不同的区域，每个区域有效地充当区分每个平面的标签，这样还避免了一个平面在另一个扫描中不正确地对齐另一个不同平面的问题。

用于将点云变换成相应的向量集的另一技术/算法包括：

计算每个点的点密度，并计算该点周围的点的点密度。然后找到点密度最大的增加方向，它给出了点密度梯度向量的方向，其长度与点线密度变化量成正比。在每个点计算出点密度之后，可以使用梯度或向量梯度运算符计算。然而，这个向量与所有其他向量不同，因为为了计算它，我们不能通过采样使点密度均匀(即如我们在其他方法中可选择的第一步骤)。如果我们这样做，我们将找不到点密度梯度，因为采样后，不存在点密度的梯度。我们可以应用阈值来选择具有最高点密度梯度的区域，并查看这些区域是否相邻，从而形成例如曲面的区域。如果需要，然后可以将剩余的点密度梯度向量归一化，并作为表面法向量处理。这些向量的相关或匹配是高斯球内的体积相关或匹配，因为它们具有不同的长度。为了避免这种复杂性，可以将向量的长度视为与这些归一化的向量相关联的读数或参数。这些读数或参数将被合并到高斯球表面上的图案中，这可以被当作是这些图案的亮度或颜色。这意味着这些读数或参数必须保持不同，并且与其自身类型的读数或参数相关或匹配。

当空间体积内没有平面，边缘或圆柱形，复曲面或圆锥曲线特征时，此向量会非常有用。因此，对象可能是一定体积的雾，其中某些部分比其他部分更密集，或者它可能是人体器官的内部密度变化的区域。

用于将点云变换成相应的向量集的另一技术/算法包括：

找到如上所述的点密度梯度向量。使用点密度梯度向量而不是使用表面法向量来计算如上所述的散度向量。所计算得到的向量即是点密度梯度的散度向量。

用于将点云变换成相应的向量集的另一技术/算法包括：

使用上述方法来计算点密度梯度向量，而不是点密度的梯度。计算每个读数中其他参数和变量的梯度。这些参数和变量可能包括颜色，色调，饱和度，亮度，反射率，每秒物体的运动量，表面粗糙度，表面曲率等。

可以用作将点云转换为向量云的一部分，即获得点云的向量表示的技术之一，是使用深度学习中的学习算法训练的人工神经网络自动编码器。自动编码器从点云，和/或由点云表示的读数，和/或表示相应点和相邻点的向量，提取3D空间中的特征。可以若干复杂程度提取特征：一阶，二阶，三阶以及可选地还有更高阶。第一阶特征非常简单，例如点密度，点读数或边缘中的较大梯度值。例如，在所有3D立体像素中，来自表面法向量，和/或和向量，和/或散度向量的分布。可以仅使用点密度，或者还可以包括反射强度或亮度，颜色和其他读数，也可以包括表示相应点和相邻点的向量的位置，方向和大小。二阶特征结合多个一阶特征，以提供更复杂的特征。例如，如果第一阶特征是边缘的一部分，那么二阶特征可以将它们连接成一个表示拐角的边缘图案。三阶特征结合多个二阶特征，从而组合的几个边缘和拐角以描述房间的轮廓。虽然这个例子使用了边缘，但是平面和曲面也可以作为特征来表示二阶和三阶特征。这些一阶，二阶和三阶特征均由向量表示，因此可用作3D数据集的旋转对齐的基础。这样做的优点是，不需要先验证3D数据集的对齐，例如，在未知的3D环境中，任何特征将被自动识别并用于执行对齐。

高斯球体

无论使用何种技术来生成向量，在步骤S105比较角度分布(对于多种向量类型的情况下的每种类型的向量)，对于该比较，处理可以包括对各组向量，生成两个嵌套，同心的的高斯球体或单位球体。一个高斯球体或单位球体由第一組向量(即来自第一张图像)形成，另一个由第二组向量(即来自第二张图像)形成。如果向量是表面法线，则向量点将全部位于球面上。否则，这是非高斯球的球形表示。

滤波器

作为可选的处理步骤，非线性滤波器可以应用于向量集或点云，其中边缘，平面，圆柱，圆环，圆锥，球体和其他形状被识别，并且保留与它们相关联的点或向量以进行进一步处理，而其余部分被删除。复杂特征的选择取决于3D场景，例如对于建筑物而言，边缘和平面是有效的特征。如果成像装置噪声很大并且场景已知包含某些复杂特征，则通过拟合已知形状来找到那些复杂特征，可有效地减少由于噪声引起的点的离散性。然后可以将点沿最近的曲面法线投影到复杂特征上。如果只识别和提取边缘，这将可以节省大量内存和计算成本。对于具有清晰边缘的一些场景，这个方法是可行的。此方法可以很大程度地对齐存在许多线框的3D场景。这种非线性滤波器可以应用于点云或向量集，取决于哪种模式识别算法最方便。作为另一替代方案，实施方式的步骤S105中的最佳匹配处理包括生成向量组的共原点的球体，并在该球体(可以是高斯球体)上使用非线性滤波。例如，在高斯球体形式中，位于高斯球体上高点密度的点是来自场景中的平面，大圆圈上和其附近的点是出自场景中的圆柱形物体，非大圆圈上和其附近的点是来自完整的或部分的圆锥形物体。因此，该方法利用所有上述物体或其他物体来建立旋转对齐。因此，也可以在旋转对齐之前选择性地增强平面，圆柱或圆锥。

为了识别像椅子这样的复杂形状，可以使用数量足够大的示例椅子的数据集训练诸如深度学习之类的人工智能算法，然后用于识别椅子。该方法通常需要在深度学习识别之前首先进行分割。

边缘检测算法

非线性滤波器可以包括执行边缘检测算法，并且在进一步处理中去除不表示边缘的任何数据点(在点云中)或向量(在向量集合中)。边缘检测算法的例子包括BAO算法，RANSAC线检测算法(例如，在RANSAC或霍夫变换平面检测算法进行平面检测之后)或三线性插值算法。

图6-12展示了示例性的边缘检测技术。进一步的细节在英国专利申请GB1701383.0的公开版本附录C中提供了详细的解释。

分割算法

非线性滤波器可以包括以下分段算法：

-执行分割算法，该分割算法可以是曲率分割算法或“平滑约束分割”算法；

-执行曲率分割算法和区域增长；

-执行基于几何属性的曲率分割算法和区域增长。

以上(在图4描述)提供了关于分割算法的更多细节，并且在英国专利申请GB1701383.0的公开版本的附录D中提供了进一步的细节。

识别算法

寻找模板形状可以在分割算法的输出上，在点云上，在向量集上或在高斯球上执行。寻找模板形状可以包括执行圆柱识别算法(例如霍夫变换算法)和/或平面识别算法(例如RANSAC算法)。诸如椅子之类的更复杂的形状也可以使用诸如深度学习之类的人工智能算法来识别，其需要使用大量数据集进行先前训练。

关于圆柱和平面识别算法以及替代向量类型的更多细节在图4中描述。此外，英国专利申请GB1701383.0的公开版本的附录E提供了进一步的细节。

以下文献详述了从高斯球体中识别圆柱体的技术：Toony,Z.,Laurendeau,D.&Gagné,C.Describing 3D Geometric Primitives Using the Gaussian Sphere and theGaussian Accumulator.3D Res(2015)6:42.doi:10.1007/s13319-015-0074-3

一旦匹配了模板形状，则可以在进一步(最佳匹配)处理中去除剩余的数据点或向量。

寻找最佳匹配

在步骤S105，对两组向量执行算法以确定围绕一到三个旋转轴中的每一个的旋转角度，向量组的角度分布表现出最佳或最接近的匹配(即，置信度最高的集合匹配)。

例如，步骤S105可以包括：

-可以保持向量不变，也可以计算高斯球表面上向量点的密度。点密度表示减少了数据存储和计算要求。独立地重复该步骤，对与向量分布相关联的每个读数和属性进行处理。

-沿着α，β和γ正交角度，围绕高斯球体原点，旋转一个图像的的向量，同时通过执行沿着α，β和γ正交角度的向量点密度的数学相关来计算一个图像的向量与另一个图像的向量之间的匹配。最高匹配或相关的α，β和γ的值组成配准旋转向量。或者，使用众所周知的梯度搜索算法，例如模拟退火和遗传算法以及最大下降法，以找到一个图像与另一个图像的向量点密度的乘积，在球体上积分最大值的位置。或者，可以将高斯球表面上的图案展开或映射到平面上的图案，使得图像和图案可以在该平面上彼此滑动以计算相关性。这可以通过将例如经度和纬度映射到平面上的x和y轴上，或者通过将球体表面上的图像投影到共轴的圆柱上(如墨卡托投影)来完成。或者这可以通过将方位角和仰角以及径向距离映射到3D笛卡尔坐标来完成。或者使用高尔-彼得斯正交投影，保留相对区域。或者使用以下参考网站中列出的许多其他投影方法，https://en.wikipedia.org/wiki/List_of_map_ projections。或者，利用卷积定理计算相关性是有利地，即通过2D傅里叶变换两次扫描的球体表面上的两个图案，将它们相同比例地覆盖在相同原点上，将它们相乘之后进行傅立叶逆变换。

-在计算匹配度或相关性时，记录出现匹配度或相关性最大值时的三个角度，α，β和γ(即围绕相应旋转轴的角度，注意的是只能以这种方式计算一个或两个角度)。这些角度形成配准向量的旋转部分，用于对齐两个图像。

一旦计算，可以输出一个，两个或三个角度。这些角度表示成像装置与成像对象的相对方向的变化，因此可用于跟踪成像装置的旋转运动。

对于除表面法向量之外的其他类型向，例如和向量，散度向量或平面向量。它们具有不同的长度，并且没有归一化。因此，它们将填充单位球体内外的全部或部分空间。因此，为了计算相关性，有必要将该3D空间分割成延伸到最长向量距离的径向分段，将其以方位角和仰角的角度形式分割成3D分段。计算每个(体积)分段中的向量尖端点的密度，并将结果输入到该数组元素中。数组是3D的。然后当两个球体围绕各个轴旋转时，它们与最近的分段对齐。然后计算相关性。在这种情况下，对于每个分段，必须将第一次扫描的一个数组分段中的点密度与第二次扫描的对齐数组分段中的点密度相乘。然后将所有乘积相加，以获得相关性。可以通过在对齐的分段中添加点密度，然后求和来找到相关性。这意味着必须相对于另一个旋转一个球体，以得到方位角和仰角的最终旋转对齐结果。因此，在3D数据集中计算2D相关，这比计算3D数据集的3D相关的计算成本低得多。

可选地，第一组向量和第二组向量组各自包括多个向量子集，每个子集代表相应点云的一个特定类型的向量，该特定类型与其他子集的特定类型不同。在这种情况下，计算每种类型的向量的最大匹配度的角度，然后组合这些角度(例如，通过找到平均值，或过滤后去除异常值的平均值)以找到对于相应的旋转轴最大的计算匹配度。向量类型可以包括以下中的一个或多个：

-由自动编码器生成的向量(在深度学习中使用学习算法训练的人工神经网络自动编码器)并表示一阶特征，

-由自动编码器生成并表示二阶特征的向量(即一阶特征的组合)，

-由自动编码器生成并表示三阶特征的向量(即二阶特征的组合)，

-由自动编码器生成并表示四阶，五阶或更高阶特征的向量(在每种情况下，第n阶特征是第(n-1)阶特征的组合)，

-由自动编码器生成并表示第一，第二和/或第三阶特征的向量，

-表面单位法向量，

-和向量，

-散度向量，

-边缘向量，

-圆柱向量，

-复杂物体向量，

-平面向量，

-点密度梯度向量，

-点密度梯度的散度向量，以及

-梯度向量。

步骤S105(直方图)的替代

作为上述在S105处的高斯球处理的一个替代，每个点云可以表示成点密度或者向量分布的一维直方图，例如沿着一个或多个轴或其他方向的表面单位法向量分布。点云中的所有点都可以投影到直线，或轴(1D直方图)，或平面(2D直方图)上。在一些实施方式中，可以选择性地获得表示点子集的直方图。例如，对于所有点，其表面法向量近似平行于扫描的垂直方向，所有这些点的点密度分布一维直方图可用于显示扫描中水平表面的位置，例如房间中地地板和天花板。

作为另一替代方案，一个或多个平面中的表面法向量分布的点密度2D直方图可用来表示点云。点云中的所有点都可以投影到平面上，或者可以选择性地来获得表示点子集的直方图。例如，与扫描的水平面的方向一致的平面，与代表表面法线大致位于平面中的点的点密度地直方图一起，表示垂直表面的位置和放向，例如房间中的墙壁。作为另一个例子，对于向量场方向的2D直方图，直方图的两个轴可以指示极坐标中向量的仰角和方位角，或者它们可以在笛卡尔坐标中，或在适合于3D环境的其他坐标系中。用作数据的向量分布，包括但不限于例如表面法向量或者和向量。

另外，在1D和一些2D直方图的情况下，各个点对直方图的贡献值，可以通过参考方向(例如，1D直方图的轴，2D直方图的平面法线，或不同类型向量)与直方图中的所研究的向量数量的点积的符号来确定。这样做的结果是直方图包含正负符号的峰值，与只包含正峰值相比，信息量有效地加倍。在扫描中沿垂直方向的一维直方图的情况下，此直方图显示水平扫描的点密度，可以通过直方图中指示的正负幅度峰值，来区分地板和天花板。

在直方图替代中，为了对齐两个点云，通过在1D和2D直方图上执行1D和2D互相关来计算互相关性，假设1D和2D直方图是互相关的。

旋转

在步骤S106中，将第二个点云以所述角度旋转，以使两个点云旋转对齐。步骤S106是可选的，可以将使两个点云旋转对齐所需的旋转变换，作为一个或两个数据集的属性来存储和/或输出。

平移对齐

流程前步骤S107到S109是平移对齐处理。平移对齐处理的输入是代表重叠空间的两个点云。

线上投影

在步骤S107a和S107b，将图像分别投影到三条线上，使得每个图像被记录为三个一维数组。两个图像都投影到相同的线上，这可以通过使用公共坐标系来实现。

选择彼此成一定角度的三条线，也可以选择三条以上的线。例如，可以选择十条线，包括满足以下要求的三条线。第三条线不能与其他两条线在同一平面上，并且可以预先设定第三条线和前两条线的平面之间的最小角度。方便地，三条线可以是正交的并且形成x，y，z三个轴。在构建图像时也很方便，图像可以与地板和墙壁的边缘对齐。可选地，可以使用线选择算法，即将两个图像中的一个(即，投影点云)投影到一条线上，投影的点是自相关的，并且分析相关的匹配峰值，在每次分析时旋转投影线，直到相关的匹配峰达到一个大于其他相关峰的阈值的峰值。

两个点云被分别投影(降维)到三条线中的每条线上，每点云产生三个一维位置数组(其中每个点都是线上的一个位置)。如果线是正交的坐标轴，通过将两个坐标设置为零，并投影到第三个坐标轴线上。类似操作于其他三个轴。这种降维表示沿着垂直于轴的向量在轴上的投影。可以使用其他的投影或降维方式，即沿着与轴成一定角度将点投影到曲线或线上，或以非线性方式实现。

可选地，使用非线性或线性幅度缩放，用于每个轴上的数据表示分布，例如，使用指数或幂函数来强调较大的幅度，或者例如使用对数函数来抑制较大的幅度。可以对装置预定义这种缩放，或者可以根据成像域的性质来配置这种缩放。

寻找最佳匹配的投影

在步骤S108，对于每个共线的投影对(此文中，投影意味着位置或点的一维数组)，执行处理以找到最佳的相对位置(即，沿着线的移位量)。最佳的相对位置出现在投影之间数学相关性最大值的时候。

寻找投影的最佳匹配

用于找到每条线的投影之间最佳匹配的相对位置的处理可以如下进行：

-沿着线(投影图像的位置)以小步长滑动一个图像的投影，使其开始滑过另一个图像的投影并越过另一个图像的投影

-对于3条线或轴其中的一条，在每个滑动步骤中，通过计算匹配来计算两个投影的匹配程度，该匹配可以通过下面列出的多种方式完成，其中一种方式是数学相关函数。值得注意的是，这是一维相关性，因此可以最小化计算成本

-对于3条线或轴其中的一条，找到投影之间匹配的最大值，并记下中间结果，例如方向和距离。第二图像投影必须沿线移动，以得到这个最大匹配值

-对三个轴中的每个轴重复以获得三个平移距离(以及沿着线的方向，正或负)，这形成了配准向量的平移部分

-根据在滑动投影时使用的步长的大小，可能需要进一步对齐。平移对齐处理可以包括一个精细对齐步骤，可使用迭代最近点(ICP)或最小二乘对齐算法。可以使用诸如Levenberg-Marquardt(LM)算法的误差最小化技术来实现收敛。

可以输出三个获得的平移距离(以及定义计算距离的线的信息)作为合并点云的替代或补充。找到两个一维数组的最佳匹配位置可以以多种方式完成，例如：

-数学相关性：一个已知的数学运算符，它有效地将一个函数平移到另一个函数的所有可能的相对位置上，将两函数的点积求积分，当两函数没有重合时，将此时的点积设为零。然后，也可以将计算的积分值在平面上绘制为另一个函数，最高点表示最佳的对齐；

-局部增益：将一个函数平移到另一个函数的所有可能的相对位置上，选择一个区域，将这两个函数求和并在该区域内积分，并除以该函数未平移时的积分，得到函数的局部增益或放大。如果两次扫描是同时从相同位置拍摄，并且是完全对齐的，那么局部增益将是均匀的，并且将取值为2。对于部分重叠并完全对齐的函数，在重叠区域中增益更高，趋近于2，并且在其他地方均是1。因此，可以通过设置略大于1的阈值来提取重叠区域。目的是在重叠区域找到最均匀的局部增益。通过计算重叠区域上的局部增益的标准偏差或方差，可以计算局部增益的均匀性。除了详尽搜索两个函数的所有相对位置之外，还有许多众所周知的搜索方法，例如模拟退火，遗传算法，直接梯度搜索，以最小化诸如均匀性方差的函数。

-势能：在3D空间中绘制两个函数到表面上，并且每个都由刚性固体表面代表。然后，将一个函数平移到另一个函数的所有可能的相对位置。为了将一个函数平移到另一个函数上，一个函数上的最低点必须滑过另一个函数的最高点。让我们假设一个函数是静止的，并且计算当平移到静止函数上时，另一个函数的平均高度以找到势能。目的是是势能最小化。除了详尽搜索两个函数的所有相对位置外，还有许多众所周知的搜索方法，如模拟退火，遗传算法，直接梯度搜索，以最大限度地减少诸如势能等函数。交换两个函数，并重复该操作是有利的。这样做的原因是，如果有人在第一次扫描中进入房间而不在另一次扫描中，则两次扫描在对齐时不会具有低势能，因为在第一次扫描中的人将阻止它们足够接近。但是，一旦交换两次扫描重复计算，这个人对势能没有影响。因此，选择两个互换计算中的最低势能作为对齐位置；

-最小二乘法或ICP：可以使用这两种已知方法中的任一种，可选择地在通过数学相关，局部增益或势能进行粗略对齐之后使用。

平移对齐

在步骤S109中，通过沿着所选择的3条线移动第二图像，使两个点云平移对齐。点云现在处于旋转和平移对齐的状态，因此可以被认为是单个的合并点云。例如，合并的点云可以输出到获得图像的一方或设备，或输出到存储单元。所有点云可以作为在同一坐标系中定义的单独点云分别输出，或作为一个点云(在某一个坐标系中)输出。

可以获得一个空间，与为第一个和第二个原始图像中的任一个或两个图像的空间重叠的新图像，并且对其进行旋转(步骤S102至S106)和/或平移(S109)对齐处理，其中，来自两个原始图像的合并点云，是两原始图像合并的新图像，或者是在成像空间中与新图像重叠的两个原始图像中的单个图像，在对齐处理之后的图像的坐标系中定义。以这种方式添加的新图像数量没有限制。

检查对齐的扫描

可以对使用实施方式的对齐过程或者对齐到装置的任何一对扫描执行可选的检查步骤。如果扫描仪位置在每个3D数据集中存储为元数据，或者扫描仪位置可从3D数据集中导出，则扫描仪位置可在将各个3D数据集彼此对齐时，识别误报(尽管在检查之前，算法的第一部分将结果记录为正确的对齐，但是实际上是不正确的对齐结果)。例如，如果在合并之后，合并的3D点云代表来自第二个3D数据集的读数与扫描仪位置之间的视线中的第一3D数据集的读数(即点)，则它可以是作为判断第一个和第二个3D数据集的配对是否正确的指示。该过程可以称为“射线追踪”。这可以通过围绕某一个轴，旋转某一扫描，校正对齐结果。例如，校正时可以选择围绕垂直轴，旋转90，180和270度以检查对齐是否正确，另外可选择性地，围绕水平轴，旋转180度。校正旋转结果对于包含对称特征的建筑物或其他对象的扫描特别有用。

实施方式在任何配置中的一对扫描或扫描网络上操作，只要网络中的每个扫描与至少一个其他扫描之间存在重叠即可。对于扫描网络，可以对网络中的所有重叠扫描对执行使用本文公开的技术的旋转和平移对齐。扫描网络可以伴随一个扫描对文件，该扫描对文件针对每次扫描，标记至少一个与该扫描重叠的其他扫描。使用此基本信息，可以通过以下步骤，构建单个合并点云：依次在每个扫描与其一个或多个重叠的邻居之间找到正确的旋转和平移对齐(即正确的位置关系)，将该扫描及其一个或多个重叠的邻居合并到使用正确的旋转和平移对齐的新公共点云，之后，要么将公共点云视为新的输入扫描并逐个添加其他重叠扫描；要么将公共点云合并到单个点云中，方法是将所有公共点云放入一个公共坐标系，并共同定位出现在多个公共点云中的同一个扫描的实例(例如，通过使用边缘处的扫描)。如果仅识别单个扫描的最佳相关性，公共点云可以被称为成对的点云。

作为使用扫描对文件的替代，实施方式可以通过找到每个扫描配对组合之间的相关性或匹配程度来发现重叠的扫描，并且假设对于每个相应扫描(这里所谓的扫描是3D数据集)，它与其表现出最佳匹配度的另一扫描重叠，并且剩余的每个扫描与该扫描的相关性(或匹配程度)均在最佳相关性(或最佳匹配度)的一个定义的范围内。此范围可以是与一个给定重叠扫描的数量相关联的，也可以是固定的。相应的扫描和“其表现出最佳匹配程度的其他扫描”被视为一个扫描配对。

特别地，对于扫描配对的每个组合，执行以下步骤：将第一个第二个3D数据集存储为共同坐标系中的各个点云；将存储的第一个点云变换为第一个向量集，并将存储的第二个点云变换为第二个向量集，其中第一个或第二个向量集中的每个向量表示其相应点云中相应的点和相邻点之间的关系；寻找到第二个向量集，相对于第一个向量集，围绕三个旋转轴中的一个或多个轴的旋转角度，从而在定义的公共坐标系中，获取第一个向量集与第二个向量集的角度分布之间的最大匹配度；存储围绕每个或多个旋转轴所计算的最大匹配程度的的旋转角度，并存储所述最大计算匹配度。可选地，第一组向量和第二向量组各自包括多个向量子集，每个子集代表对应特定向量类型的点云，该特定类型与其他子集的特定类型不同。对于每个子集，为每种类型的向量计算最大匹配度的角度，以及角度组合(例如，通过找到平均值，或过滤后去除异常值的平均值)以找到对于相应的旋转轴的最大的计算匹配度。

然后，基于所计算的匹配程度，比较所存储的包括特定扫描的所有配对的计算匹配度，以找到与特定扫描具有最大相关性的扫描。特别地，该实施方式识别存储的最大匹配度中最大的配对。可以通过假设在最大匹配度的限定范围内，特定的扫描还与具有最大匹配度(注意这表示任何一对扫描之间最可能的未旋转对齐的角度)的其他扫描重叠来识别其他配对。此范围可以是与给定重叠扫描的数量相关联的，也可以是固定的。

在更复杂的示例中，执行附加处理以在网络中更好地连接扫描。该处理基于一个扫描(例如，扫描A)的最大匹配度。包括扫描A并且在预定最大匹配度阈值内(可以是成比例的，也可以是绝对的阈值)表现出最大匹配度的其他扫描对，也可以被确定为网络中的重叠配对，并用扫描A对其进行旋转和平移对齐处理。对于任一其他配对，如果其与扫描A的最大匹配程度小于匹配程度最大值，且其差值超过一个进一步预定义的阈值，则可以认为此扫描配对为非重叠。这个进一步预定义的阈值可以与预定义的阈值相同，或者可以小于预定义的阈值。这两个阈值的间隙，可使其中一些扫描配对既不被确定为重叠，也不被确定为非重叠。例如，可以手动检查落在此间隙中的对。如果网络是成对的链结构或分支树结构(可以用户定义，并告知该实施方式)，则假设一些扫描在链的末端，并且一些扫描在分支树中的分支点上。在末端的扫描只有一个扫描与之连接。在链上或树分支上的扫描有两个扫描与之连接。在树分支点上的扫描有三，四或更多个扫描与之连接。例如，扫描A和扫描B的重叠率可以大于扫描A和扫描C之间的重叠率(换句话说，最大匹配度的最大值在A-B处，而在A-C处，最大匹配度小于所述最大值)。然后比较A-B和A-C的最大匹配程度，如果它们之间的差异值大于进一步预定义的阈值，我们则知道A在分支的末端。如果差异小于预定义的阈值，那么我们知道A与B和C都是重叠配对，并且可能位于链或分支树的中部。类似地，如果所有扫描对A-B，A-C和A-D的最大匹配度之间的差异小于预定阈值，那么它们全部以重叠对的方式连接在一起，扫描A位于分支点处。

在链或分支树结构的情况下，被确定为与扫描A重叠的所有相邻扫描用于计算与扫描A的对齐。如果A位于一个分支的末端，那么我们仅使用其与扫描B的对齐来确定其位置。

可能的是，实施方式在计算扫描的旋转和位置时，以重叠量的倒数(或匹配程度与最大匹配程度的接近度，越接近更高的权重)加权对任何重叠扫描的影响。这意味着使用每对扫描，从扫描存在的方向和位置，来计算旋转和平移向量的校正。然后通过在每个校正向量上使用该加权因子，执行向量加权平均，来合并这些校正向量。该加权可以是线性的或非线性的，并且可以与阈值一起使用，以忽略重叠率小于绝对阈值的扫描，或忽略那些与该扫描的最大匹配程度高于阈值，且与阈值的差值小于最大匹配程度的最大值的扫描。可以自动调整预定阈值，以使在对齐计算中使用最多的(例如6个)扫描。

由于该扫描对已经旋转对齐，因此执行平移对齐程序以确定两者之间的完整且准确的位置关系。假设两个扫描在公共坐标系中，则平移对齐过程包括：对于公共坐标系中的三条或更多条线中的每条线，其中三条线中的每两条线是不平行的，并且三条线中的至少一对线是非共面的：相对于任意原点，记录第一个点云中每个点在这条线上投影的位置；将记录的位置存储为第一个一维位置数组，并/或存储在相应的记录的位置上的各个点的一个或多个属性或读数作为第一个一维位置数组；相对于任意原点，记录旋转的第二点云每个点投影在这条线上投影的位置；将记录的位置存储为第二个一维位置数组，并/或存储在相应的记录的位置上的各个点的一个或多个属性或读数作为第二个一维位置数组；找到沿着第二个一维位置数组的线，相对于第一个一维位置数组的线的平移，该平移是第一个和第二个一维数组之间的最大匹配度所对应的平移值，并记录该平移。

然后获得该配对中的两个扫描，旋转扫描以至旋转对齐(如果尚未执行)，并且使用平移对齐过程中计算且记录的平移值，分别沿着各条线将扫描平移，从而获得成对的点云，以代表这对单独的3D数据集，和在该对之间固定的旋转和平移关系。最后，实施方式通过共同定位出现在多个成对的点云中的相同单独3D数据集的实例(例如，通过使用边缘处的扫描)，将此扫描配对的成对的点云合并成单个点云。

在扫描仪位置作为元数据与每个3D数据集一起存储的实施方式中，或者扫描仪位置可从3D数据集导出的实施方式中，扫描仪位置可在将各个3D数据集彼此对齐时，识别误报。例如，如果在合并之后，合并的3D点云代表来自第二个3D数据集的读数与扫描仪位置之间的视线中的第一3D数据集的读数(即点)，则它可以是作为判断第一个和第二个3D数据集的配对是否正确的指示。该过程可以称为“射线追踪”。这可以通过从合并的点云中移除第一个或第二个3D数据集来校正，并且重复识别匹配程度最大的扫描对的步骤，并且从候选者中排除包括第一个和第二个3D数据集的配对，从而为3D数据集找到一个新的配对。可以对此新配对执行旋转和平移对齐过程，并且3D数据集在所得到的新位置中合并到合并点云中。另外，可以通过围绕某一个轴，旋转某一扫描。例如，可以选择围绕垂直轴，旋转90，180和270度以检查对齐是否正确，另外可选择性地，围绕水平轴，旋转180度。校正旋转结果对于包含对称特征的建筑物或其他对象的扫描特别有用。

作为用于识别各个数据集的配对中的误报的另一替代技术，可以使用手动处理过程，即合并的3D点云由图形用户界面呈现给用户，例如，一个2D或3D图像，各个3D数据集在合并的3D点云内可识别(例如，通过颜色编码)，并且图形用户界面使用户能够相对于合并的3D点云的其余部分重新定位各个3D数据集。在这样的实施方式中，手动重新定位受到限制，因为在重新定位的单个3D数据集(数据集A)与合并的3D点云中的至少一个其他单独的3D数据集(数据集B)之间必须存在至少一部分的重叠。然后将数据集A和数据集B视为一配对。在数据集配对的每个组合执行旋转对齐计算，并且此对齐结果可以被检索(围绕一个或多个轴或旋转轴中的每一个的旋转角度，此旋转角度是计算的匹配程度对于该旋转轴达到最大值时所对应的旋转角度)。然后对该对进行平移对齐处理。由此获得数据集A和数据集B之间的完整位置关系，并且可以将其存储为一个向量(或两个向量：一个用于旋转，另一个用于平移)，代表使数据集A(或B)和数据集B(或A)正确的旋转对齐所需的旋转和平移变换。或者，对每个数据集，存储该向量(或两个向量)，并且该向量是数据集中的点的坐标所需的一个变换，以将它们在公共坐标系中呈现在相对于其他数据集的正确位置。或者，数据集A和B可以根据所获得的完整位置关系存储在合并的3D点云中。

图14示出了实施方式中的处理过程。

在S1401，将用于多对扫描(3D数据集)的成对变换转换为全局变换。此步骤可视为预处理，可能不是必须的，具体取决于输入扫描的配置。每个扫描的变换矩阵从成对变换转换为全局变换。此步骤是可选的，只有在用户提供输入扫描和成对的相对转换时，才需要此步骤。在步骤S1401之后，每个扫描的位置和方向，均相对于一个共同的共享参考点而表征。换句话说，多个扫描在公共工作空间或公共坐标系中表示。

在S1402，创建扫描连接图(映射)。该步骤可以被认为是预处理。在S1402，对于每个扫描，其在被处理时可以被认为是“对象”扫描，识别与此对象扫描共享一些重叠区域的一组相邻“参考”扫描。将每个扫描所识别的参考扫描或一组参考扫描作为一个对象扫描，存储为一个对象扫描到参考扫描的映射。参考扫描的选择标准可能包括以下内容：

距离：参考扫描必须在距对象扫描的某个定义的最大距离内。例如，在半径15米范围内。

重叠率：每个参考扫描必须与对象扫描有足够的重叠比例，例如至少10％。重叠率通过在彼此的某个阈值距离内，计算相对于总点数的点对的数量。附加约束条件包括匹配表面法线方向，读数值，表面曲率，表面粗糙度或表面法线的散度等。

创建的扫描连接图(或映射)的约束条件可以是下列标准：

每个扫描必须至少有一个参考扫描。但是，连接网络或环路中的多个扫描可能会降低(或更均匀地分散)对齐错误。这意味着在连接图中允许(并且首选)环路。

必须至少选择一个扫描作为固定参考扫描。例如，这可以是连接到此扫描数目最多的那个扫描。还可以使用多个固定扫描，其位置可以例如基于使用全站仪，GPS或其他方法的精确测量。

所有扫描必须连接到单个图形(扫描组)。

步骤S1403是全局对齐步骤：在“全局对齐步骤”中，基于所有参考扫描，计算每个扫描的改进变换。如图14所示，首先在S1403A中对扫描A进行处理，然后在S1403B中对扫描B进行处理，依此类推，直到在S1403N中对扫描N进行处理。这些改进都是独立于其他扫描计算的，因此可以在单台计算机或许多计算机的集群上顺序或并行执行计算。对于扫描连接图中的每个扫描(即，多个扫描中的每一个)作为对象(或源)点云，每一个与对象点云重叠的扫描被设置为参考点云。在对象点云表示中定义的对象点云与参考点云之间的旋转和平移关系作为初始估计，然后在对象点云和参考点云上执行对齐算法(可以是在别处提到的旋转或平移对齐算法，或者可以是迭代最近点算法)，相对于目标点云，旋转并平移对象点云，直到满足过程误差标准，获得对象点云与参考点云之间的修正的定义的旋转和平移关系。

然后在S1404中，合并定义的旋转和平移关系的修订，例如，作为平均或加权平均(加权可以根据重叠程度)，并且合并修订应用于对象点云的位置信息。此合并的修订可以意味着存在一个合并的点云，其中在对象点云中移动位置，或者它可以意味着修改在公共坐标系中的对象点云的存储的位置信息的信息。

该过程在匹配范围内发现具有高度重叠的多个扫描。这些多个扫描通常在对象扫描的附近。然后，分别计算对象扫描到每一个这些多个扫描的对齐向量。每对重叠扫描给出旋转和平移向量的校正，以移动对象扫描当前的位置和方向。然后平均来自每对扫描的这些校正向量，可选地作为基于重叠程度的加权平均值(与重叠程度成比例的加权)。

该过程可以在S1404处结束。可选地，在S1405中，使用一个标准以确定是否重复S1403以获得进一步的修订。例如，如果所有更新的转换都足够小(低于用户设置或预定义的某个阈值)，则算法已收敛，得到最终结果，并结束该步骤。然而，如果一个或多个变换不满足收敛标准，则重复“全局对齐步骤”S1403。可替代地或另外地，用户可以设置要执行的最大数量的“全局对准步骤”S1403，之后即使尚未实现期望的解决方案容差，它也终止。

在S1406，保存修改的旋转和平移关系，并且可以可选地在根据保存的旋转和平移关系，将多个扫描合并到单个点云，作为一个修正点云表征。

图5的描述

图5是体现本发明的计算设备(例如服务器)的框图，该计算设备可用于实现任何实施方式的方法。特别地，图5中的计算设备可以是3D图像采集单元12，存储单元14，旋转对齐处理器16和平移对齐处理器18中的一个或多个的硬件配置。图5中的计算设备可用于实现任一个图4和6-14中的方法。

计算设备包括计算机处理单元(CPU)993，诸如随机存取存储器(RAM)995的内存，以及诸如硬盘的存储器996的存储器。可选地，计算设备还包括网络接口999，用于与实施方式中的其他这样的计算设备通信。例如，实施方式可以由如云计算集群操作的计算设备的网络组成。可选地，计算设备还包括只读存储器994，诸如键盘和鼠标998的一个或多个输入设备，以及诸如监视器997的一个或多个显示单元。这些组件可通过总线992相互连接。

CPU 993被配置为控制计算设备并执行处理操作。RAM 995存储由CPU 993读取和写入的数据。此外，可以使用一个GPU。存储单元996可以是例如非易失性存储单元，并且被配置为存储数据。

可选的显示单元997显示由计算设备存储的数据的界面，并显示光标，对话框和屏幕，使用户与程序之间交互，并存储在计算设备上的数据。输入设备998使用户能够向计算设备输入数据和指令。显示器可以是使用立体眼镜的3D显示器，或诸如Hololens的头盔，或者是不需要特殊的眼镜的全息显示器或自动立体显示器之类的头盔。

网络接口(网络I/F)999连接到诸如因特网的网络，并且可通过网络连接到其他计算设备。网络I/F 999控制经由网络从/向其他装置输入/输出的数据。网络I/F可以提供一个到获取3D数据集的计算设备的连接，并且可以接收用于定义处理元素(例如，选择算法)的参数或指令。

其他外围设备，例如麦克风，扬声器，打印机，电源单元，风扇，机箱，扫描仪，轨迹球等可以包括在计算设备中。

3D图像对齐装置10可以实施由诸如图5中所示的计算设备实现的功能。3D图像对齐装置10的功能可以由单个计算设备或通过网络连接协同工作的多个计算设备来实现。体现本发明的方法可以在诸如图5中所示的计算设备上执行或由其实现。可以使用一个或多个这样的计算设备来执行实施方式的计算机程序。体现或用于实现实施方式的计算设备不需要具有图5中所示的每个组件，而可以由其中一些组件组成。体现本发明的方法可以由单个计算设备来执行，此计算设备通过网络与一个或多个数据存储服务器通信。

3D图像采集单元12可以包括存储在存储单元996上的处理指令，用于执行处理指令的处理器993，以及用于在执行处理指令期间存储信息对象的RAM 995。

旋转对齐处理器16和平移对齐处理器18可以是可编程的处理器硬件，包括存储在存储单元996上的处理指令，用于执行处理指令的处理器993，以及用于在执行处理指令期间存储信息对象的RAM 995。

在任何一种情况下，处理器可以是CPU，GPU，FPGA或它们的阵列。

另一方面的详细描述

点云生成处理器

第一个和第二个数据集中的每一个可以是点云，或者可以是某种其他形式的扫描数据。数据集采集单元获得第一个和第二个数据集作为数据文件，并且还可以包括用于将物理读数转换为扫描数据集的硬件。也就是说，数据集采集单元可以包括用于将物理读数转换为数据集的成像装置。或者，数据集采集单元可以以例如通过网络或某种其他形式的数据连接，从相应的成像装置接收第一个和第二个数据集。成像装置可以是与其他实施方式有关的本中在其他地方详述的成像装备的任何示例。

另外，通过扫描获得的数据集可以是CAD模型，或网格模型，或在某些位置处采样的任何其他3D形式，同时数据集也可以从以上模型合并，对齐或采集而得，以生成点云。这可以在建筑设计中具有应用，其中建筑师希望合并来自CAD模型的元素(例如，扩展)与要与扩展规划对齐的物理建筑物的扫描。这也可能应用于建筑施工，建筑工程师希望将“按设计”的CAD模型与物理构造的“竣工”建筑物的扫描进行比较。这也可以应用于电影制作和增强现实技术中，其中电脑三维动画(CGI)，网格模型需要与真实的3D扫描环境精确对齐。

第一个和第二个数据集可能已经通过图1的装置进行了初步对齐处理。数据集采集单元获取第一个和第二个数据集作为点云，通过图1的装置，旋转平移(平移是可选的)对齐到指定的精度水平。其中一个点云围绕旋转轴的迭代旋转是通过点云的当前旋转对齐角度附近的一系列角度。例如，该范围由粗略对齐的精度确定，并且基本上等于当前旋转对齐加上/减去任一方向上的指定精度水平的角度范围。

感兴趣的对象是在数据集中表示的物理实体，其可以是例如空间区域，或者一个或多个物体的全部或部分。

输入数据集(统一指第一个和第二个数据集)可以是点云，或者可以是通过某些其他手段(例如，线和形状)表示感兴趣的对象的数据集。

当输入数据集已经是点云时，点云生成处理器可以将点云转换至公共坐标系中，并存储点云。此外，点云生成处理器可以执行采样以增加或减少点密度，例如，为了符合两个点云的预定义公共点密度。处理器还可以从一种点云格式转换为另一种格式，例如从.fls到.xyz格式，因为原始格式可能不在笛卡尔坐标中。

当输入数据集尚未采用点云的形式时，点云生成处理器执行转换过程以将数据集转换为点云。例如，在转换过程中，进行采样的两个输入数据集，可能存在共同的预定义点密度。

在生成的点云中，第一个和第二个点云在公共坐标系中定义。公共坐标系可以是任一数据集或两个数据集的原始坐标系。如果任一数据集是二维的，则其此点云定义了三维公共坐标系中的一个平面。两个数据集都是至少二维的，并且其中一个或两个可以是三维的。从2D数据集获取点云的一种方法是，根据部分图像的暗度或亮度来改变点密度。在2D数据集中，暗度表示某些特征的密度或强度，可以与暗度成比例地增大附近的点密度。一种方法是创建一个高密度的随机点阵列，并叠加在2D数据集上。然后根据一个部分比最暗的部分亮多少，来随机地减少点数。另一种方法是使用随机点生成器，需要点密度作为输入。然后在2D图像上使用此生成器，并在每个点输入图像的暗度。另一种方法是在2D数据集上放置精细的规则地网格。然后在每个单元格中放置一个随机分布点，其中点数取决于在该单元格上平均的2D数据集的暗度或亮度。还有其他方法可以从绘图或模型中获取点云。

三维公共坐标系中的两个点云的相对旋转对齐可以是任意的。或者，可以提供两个数据集，其形式为：定义两个数据集共有的一个或多个轴(例如，水平轴或垂直轴)，并且公共轴或轴在公共坐标系中对齐(当然，如果已知，围绕所述公共轴或轴旋转对齐相应数据集)。

类似地，三维公共坐标系中的两个点云的相对平移位置可以是任意的，或者可以使用先前的近似平移值来近似地放置它们。

对齐处理器被配置为确定扫描对象在两个数据集之间的围绕一个或多个旋转轴地相对旋转角度。旋转轴可以是例如三个轴，根据这三个轴定义各个点云中的点。围绕一个或多个轴的旋转角度可能是已知的，例如，由于在两个获得的数据集中指定了公共线或平面，例如水平线或平面。可以向装置的用户呈现用户界面，该用户界面能够指示一个或多个轴，对齐处理器将围绕该轴确定旋转角度。

对于每个感兴趣的旋转轴，两个点云在公共坐标系中相对于彼此旋转。旋转是迭代的(逐步地)并且在每次迭代时，将两个点云投射到一条或多条线上，并且对于每条线，沿着线(再次，以迭代或逐步的方式)相对于彼此滑动两个投影，在每个步骤/迭代中找到两个投影之间的相关值，以便确定相对旋转角度的最佳或最大相关值。一旦在期望的角度范围内(例如，可以是完全旋转)，对每个步骤重复该过程，计算最佳/最大相关值中的最大值，并且将相对旋转角度值(可为最大值)确定为两个数据集围绕此旋转轴的旋转对齐的角度。另外，记录得到的所述最大值的平移，此平移是沿着相应线表示两个数据集沿线的空间分离，并且因此将数据集以所需的方向和大小平移以对齐。

投影点的线对于两个点云都是共同的。这至少三条线可以是笛卡尔坐标轴，地理坐标系，球坐标，或柱坐标轴。可选地，就每个感兴趣的轴分析这些线。

线上的投影实际上是三维点云降维映射到杆或线上。线上的投影可以沿着垂直于线的，并与线成一定角度向量，或沿着与线相交的曲线。投影的线可以是笛卡尔坐标轴，地理坐标系，球坐标，或柱坐标轴。

可以执行精细对齐程序：减小连续角度之间的步长，在相对旋转角度与初始步骤中每个方向上的其相邻邻居之间的角度范围内做再次处理，以便确定产生最佳/最大相关值的相对旋转角度是否大于先前确定的最大值，如果是，则将所述相对旋转角度记录为新的旋转对齐角度。可迭代地执行此精细对齐过程，每次减少步骤。每次迭代步骤中减少地量可以是例如1/10。

图13是详细说明另一方面的示例性旋转对齐过程的流程图。

在步骤S201a和S201b中，获得第一个和第二个数据集。例如，通过扫描3D场景的一部分以获得作为第一数据集的3D点云数据，来获得第一个数据集。通过扫描3D场景的一部分，且此部分与第一个数据集中扫描的区域重叠，或具有共同部分，则此部分作为第二个数据集的3D点云，以获得第二数据集。该扫描可以在获得第一数据集之前，之后或同时完成。在将相同的成像装置用于两次扫描的示例中，成像装置在两个扫描中的平移位置deltax，deltay，deltaz，以及相对于相同3D场景的旋转角度α，β，γ，将以完全或部分未知的方式改变。

在步骤S202a和S202b中，执行所获得的数据集的预处理。预处理之后，数据集在公共三维坐标系中表示为点云，即具有单个坐标系的名义3D工作空间。预处理可以包括以下中的一个或多个步骤：

-将第一个和第二个数据集转换为.xyz格式；

-空间采样以均匀点密度；

-如果成像装置记录有关水平，罗盘方位，高度等信息，则使用该信息将相应数据集放置在共同的三维坐标系内；

-选择并实施数据集的适当表示方式；

-通过移除浮动在3D空间中的孤立点的假象或群集，来过滤和清理数据集，这些孤立点通常出现在成像装置询问与远处物体处于相同视线中的附近物体的边缘时；

-通过删除不需要的物体(包括人员和家具)来过滤和清理扫描；

-通过使用范围过滤来过滤和清理扫描；

-可以使用非线性滤波器，识别边缘，平面，圆柱体，球体和其他形状，并保留与它们相关的点以进行进一步处理，移除其余点。附件E列出了实现此功能的已知和新颖算法清单。复杂特征的选择取决于3D场景，例如对于建筑物而言，边缘和平面是有效的特征。如果成像装置噪声很大并且场景已知包含某些复杂特征，则通过拟合已知形状来找到那些复杂特征，可有效地减少由于噪声引起的点的离散性。然后可以将点沿最近的曲面法线投影到复杂特征上。

-在S203中，确定旋转轴以及投影线，并且开始旋转对齐处理。对于寻求对齐角度的每个旋转轴，重复步骤S203至S210的旋转对齐处理。可以针对两个或三个轴，并行执行步骤S203至S210的旋转对齐处理。在处理过程方面，可能是使用一些优化技术将所有三个角度一起改变，以同时最大化沿所有投影线的相关性。一种方法是通过粗略的角度搜索参数空间，然后在沿所有线给出最高相关性的角度上进行归位，然后进行精细搜索。优化技术包括梯度下降，模拟退火，遗传算法或Levenberg Marquardt。

例如，投影线(即，扫描被降维映射的线)可以被选择为彼此成一定角度的三条线。在三条线的情况下，第三条线不能与其他两条线在同一平面上，理想情况下应与该平面成较大角度。可选地，三条线是正交的并且形成三个轴x，y，z。还可选地，在建筑物扫描中，可以选择与地板和墙壁的边缘对齐的线。可选地，选择轴以使第一个点云在降维到轴上并与其自身相关时，不会产生类似幅度的周期性匹配峰值。如果这样做，则旋转第一个点云，直到围绕着每个轴的自相关中分别出现一个清晰的峰值。

可选地，可以使用多条线。2D图像的平面中的多条线处于不同的角度，并且理想状态下垂直于图像中的线或部分线特征。理想情况下，3D点云中的线应垂直于曲面或曲面段，或平行于点密度最高变化的方向。为了节省计算成本而不是使用数千条线，仅选择与最大平面表面区域相关联的线。一种方法是找到本文所述的表面法向量，并将它们绘制在高斯球上。然后使用球面上的相等面积块计算高斯球表面上的点密度。然后阈值只选择最高点密度的区域。另一种方法是使用非线性处理来强调高点密度值和对比度，方法是将点密度提高到一个数字的幂，或者将10或e提高到以点密度为底的幂。然后找到每个峰值点密度集的形心。高斯球上到这些形心的向量是每条投影线的方向，因为最大区域具有最多的表面法向量，因此给出最高峰值点密度。因此，在一个房间里，它将是墙壁，地板和天花板。在房间的屋顶，线会在地板和两个倾斜的屋顶墙和两个侧壁上。在圆柱形房间中，装置投影到地板上，在投影到作为墙壁底部的圆形线上。高斯球上的点密度图案也可用于找到垂直于圆柱轴的平面。该装置在高斯球周围，寻找或拟合一个大圆圈到峰值点密度。这个大圆平面是垂直于圆柱轴的平面。该设备也可以投射到地板上的两条正交直线上，并试图找到旋转，假设房间中存在一些非对称特征。选择线，使得在理想情况下，与线上的其他点相比，沿着线的某些点或所有点拥有非常高的点密度和对比度。在投影之后和相关之前，可以通过将点密度提高到一个数字的幂或者将10或e提高到点密度的幂，来强调高点密度值和对比度。

对于特定的旋转轴，以逐步的方式考虑两个极值范围内的旋转角度。这些步长可以处于一个期望的精度水平，并且该范围可以是完整的旋转。可选地，步长可以比期望的精度水平更大一些，过程S203至S208以逐步增加精度水平迭代地执行，直到达到期望的精度水平。一种方法可能是寻找给出最高相关性的粗糙角度，然后在它们周围进行精细搜索，而不是在所有角度进行。其中，可以由装置用户指定一个期望精度水平。其中一个点云保持固定，而另一个点云旋转。旋转的点云旋转到范围的开始位置。

在步骤S204中，将两个点云降维映射到相应旋转轴的线上，并存储为两个投影(即沿着线的一维数组)。例如，S204包括将所有第一个和第二个点云降维或投射到线上。如果线是坐标轴，则通过将这两个坐标轴的坐标设置为零，来完成对第三个坐标线的投影。这种类型的降维表示沿着垂直于轴的向量在轴上的投影。沿着与轴成一角度的曲线或线，或以非线性方式等其他类型的投影或降维也是可能的。

可选地，可以将非线性或线性幅度缩放应用于相应的投影，例如，使用指数或幂函数强调更强的幅度，或者使用对数函数抑制更强的幅度。

值得注意的是，由步骤S204至S208定义的循环可以针对多条线并行执行。S208中的旋转是两个点云的相对角度关系的变化，并且可以是关于一个，两个或三个旋转角度的变化。经由循环S204至S208，迭代围绕一个，两个或三个旋转角度的角度范围以找到最大相关值。注意在使用多条线的情况下，在所有或一个预定比例的多条线之间达成一致，以使围绕每条轴的角度达到最大的相关值。

在步骤S205，投影在两个极值平移范围内，以逐步的方式沿着线相对于彼此平移。在每步中，计算两个投影之间的匹配程度(例如，数学相关值)，使得在逐步平移的结束时找到最大程度的匹配，由最大相关值表示(即，当前旋转的数学相关值中的最大值)。在S206，记录当前旋转的角度(注意，重要角度是相对于S203开始之前的点云的角度)，逐步滑动期间计算的最大相关值，以及点云沿线的平移，此线相对于它们在S202结束时的位置。

在S207，检查是否已达到角度范围的末尾。如果不是，则流程进行到步骤S208，在该步骤中，点云以该范围内的下一个角度旋转，并且重复步骤S204到S207。如果是，则流程进行到S209，确定点云旋转的步长是否与期望的精度水平匹配。如果不是，则流程前进到步骤S210，在此步骤设置一个新范围(新范围可以是记录的角度左右均加上一个之前的步长)和一个新的步长(可以是满足所需的精度水平的步长)。如果第一次旋转使用非常粗略的角度步长，则可能存在几个角度拥有相同的相关量。因此，围绕每一个角度进行精细搜索。或者，新步长可以是该范围的预定数量的划分，例如，100或1000，使得步长取决于范围的大小，并且继续迭代该过程，直到满足期望的精度水平。

在步骤S211，在旋转轴中记录的所有旋转角度，平移和最大相关值中，找到最大的最大相关性(同时对于所有投影线)，以及获得的相应的旋转角度和平移(即，在S202结束时，每个点云相对于其存储位置沿着线移动量，以获得最大的相关值—注意的是，只有一个点云需要移动，因此平移可以表示为仅为移动的点云的值)。旋转角度(表示为点云围绕各自旋转轴的旋转角度，此旋转角度是相对于在S202结束时存储的点云围绕相同转轴的旋转角度)表示该旋转的点云需要围绕相应的旋转轴旋转多少，以与另一个点云旋转对准。沿着已识别的线的平移，表示在S205期间点云(沿着什么线和在什么方向上)移动了多少，以与另一点云平移对齐。一旦针对每个感兴趣的旋转轴完成了步骤S203至S210，就获得旋转角度的向量以获得旋转对齐，并获得平移向量以获得平移对齐。这两个向量本身可以在S211输出，或者用于旋转和平移对齐点云，在S211处作为合并点云输出。

当存在多条投影线时，必须沿着向量移动，该向量是到多条线中的每条线上的投影最接近记录的平移值。这是通过创建试验向量并计算每条线上的误差，然后调整向量的角度和长度以最小化这些误差来完成的。例如，此试验向量是沿着每条线的所有向量的向量和给出的方向。例如，此试验向量幅度是沿每条线的向量的幅度最大值。或者，可以通过统计搜索和优化收敛来完成，例如遗传算法，梯度下降，模拟退火或Levenberg Marquardt，以最小化沿每条线的误差总和，或得到沿每条线更小的误差。

图13中所示的方法将3D数据对齐到2D数据，且将一个3D空间中的旋转平移的2D数据对齐到此3D空间中的另一个旋转平移的2D数据。如果扫描仪与汽车速度相比，旋转速度非常快，则3D空间中的2D到2D对齐与自驾车上的线扫描LIDAR相关。如果汽车较慢，则线扫描LIDAR将扫描螺旋，并从一个扫描到下一个扫描旋转，因此通过该方法可以找到螺旋中的弯曲和扭曲。值得注意的是，在前进移动车辆的所有连续相邻线扫描中没有重叠。在这种情况下，一条(投影)“线”可以是以螺旋中心为中心的圆。该装置允许此操作实时完成。因此，先前的几个扫描将对齐到3D空间中，并且最近的新扫描将与此3D空间对齐。有利地，由于移动物体或噪声而在记录中先前的一个扫描到另一个扫描的对齐中的任何误差将被平均。以这种方式只能进行少量的先前扫描，因为周围环境可能仅具有某些特征，这些特征在一次扫描到另一次扫描中保持着相对于车辆的相同位置。当车辆进入或离开隧道时，则不能使用平均值。这可以通过检测突变轻松检测到，并且可以通过使用LIDAR或多个LIDAR进行补偿。若使用一个LIDAR，则此LIRDAR的扫描与前行方向成一定角度，若使用多个LIDAR，其扫描彼此成一定角度，比如在前行方向上加上和减去一个角度。当有两个LIDAR扫描仪时，来自一个扫描仪的每个新扫描与来自该扫描仪的先前扫描的对齐，应该与另一个扫描仪的等效对齐同时进行，并且计算的平均或优化的旋转和平移向量结果，应与两个扫描仪的结果保持一致，且与车辆的速度测量系统，以及任何车载加速度计，陀螺仪，气压计，磁力计以及测斜仪读数保持一致。

另一方面，实际上任何其他方面，可以由诸如图5中所示的及如上所述的计算装置来实现。

Claims (36)

1.一种装置，所述装置包括：

3D数据集采集单元，其被配置为：

从处于第一位置和取向的成像装置获得第一时刻的第一空间的第一3D数据集，所述第一3D数据集是三维的第一点云，所述第一点云中的每个点表示所述成像装置在所述第一空间内的读数；以及

从处于第二位置和取向的成像装置获得第二时刻的第二空间的第二3D数据集，所述第二空间与所述第一空间重叠，所述第二3D数据集是三维的第二点云，所述第二点云中的每个点表示所述成像装置在所述第二空间内的读数；

存储单元，其被配置为存储所述第一3D数据集和所述第二3D数据集作为公共坐标系中的相应点云；以及

旋转对齐处理器，其被配置为：

将所存储的第一点云转换为第一向量集，并且将所存储的第二点云转换为第二向量集，其中，所述第一向量集的每个成员和所述第二向量集的每个成员表示相应的点和相邻点；

寻找获得所述第一向量集的角度分布与所述第二向量集的角度分布之间的最大匹配度时所述第二向量集在所述公共坐标系中定义的三个旋转轴中的一个或更多个旋转轴中相对于所述第一向量集的旋转角度，所述匹配度被测量以比较所述第一向量集的角度分布和所述第二向量集的角度分布；并且：

输出绕所述一个或更多个旋转轴中的每个旋转轴的、所计算出的匹配程度最大的旋转角度；或者

在所述公共坐标系中使所述第二点云绕相应的一个或更多个旋转轴以找到的旋转角度旋转，并且在所述公共坐标系中输出旋转后的第二点云；

其中，

所述装置还包括：

平移对齐处理器，其被配置为：

针对所述公共坐标系中的线和平面，其中，所述线与所述平面成角度或垂直于所述平面：

记录所述第一点云中的每个点在所述线上的投影相对于任意原点的位置，并且存储所记录的位置作为第一1维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第一1维数组；

记录所述第一点云中的每个点在所述平面上的投影相对于任意原点的位置，并且存储所记录的位置作为第一2维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第一2维数组；

记录旋转后的第二点云中的每个点在所述线上的投影相对于任意原点的位置，并且存储所记录的位置作为第二1维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第二1维数组；

记录旋转后的第二点云中的每个点在所述平面上的投影相对于任意原点的位置，并且存储所记录的位置作为第二2维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第二2维数组；

寻找所述第二1维数组相对于所述第一1维数组沿所述线的平移，在该平移处计算出所述第一1维数组与所述第二1维数组之间的最大匹配度，并且记录计算出该最大匹配度时的平移；以及

寻找所述第二2维数组相对于所述第一2维数组在所述平面中的平移，在该平移处计算出所述第一2维数组与所述第二2维数组之间的最大匹配度，并且记录该平移；

输出：

所述第一点云和所旋转的第二点云，作为所述公共坐标系中的合并点云，其中，旋转后的第二点云以相应记录的平移在所述公共坐标系中沿所述线以及在所述平面中平移；和/或

所记录的、沿所述线以及所述平面中的平移的向量表示，以及所述三个旋转轴和相应找到的旋转角度的向量表示；和/或

旋转后的第二点云，其通过相应的记录的平移在所述公共坐标系中沿所述线以及在所述平面中平移。

2.一种装置，所述装置包括：

3D数据集采集单元，其被配置为：

从处于第一位置和取向的成像装置获得第一时刻的第一空间的第一3D数据集，所述第一3D数据集是三维的第一点云，所述第一点云中的每个点表示所述成像装置在所述第一空间内的读数；并且

从处于第二位置和取向的成像装置获得第二时刻的第二空间的第二3D数据集，所述第二空间与所述第一空间重叠，所述第二3D数据集是三维的第二点云，所述第二点云中的每个点表示所述成像装置在所述第二空间内的读数；

存储单元，其被配置为存储所述第一3D数据集和所述第二3D数据集作为公共坐标系中的相应点云；以及

旋转对齐处理器，其被配置为：

将所存储的第一点云转换为第一向量集，并且将所存储的第二点云转换为第二向量集，其中，所述第一向量集的每个成员和所述第二向量集的每个成员表示相应的点和相邻点；

寻找获得所述第一向量集的角度分布与所述第二向量集的角度分布之间的最大匹配度时所述第二向量集在所述公共坐标系中定义的三个旋转轴中的一个或更多个旋转轴中相对于所述第一向量集的旋转角度，所述匹配度被测量以比较所述第一向量集的角度分布和所述第二向量集的角度分布；并且：

输出绕所述一个或更多个旋转轴中的每个旋转轴的、所计算出的匹配程度最大的旋转角度；或者

在所述公共坐标系中使所述第二点云绕相应的一个或更多个旋转轴以所找到的旋转角度旋转，并且在所述公共坐标系中输出旋转后的第二点云；

其中，

所述第一向量集的向量和所述第二向量集的向量各自包括多个向量子集，所述多个向量子集中的每个子集将相应的点云表示为特定类型的向量，该特定类型不同于其它子集的类型；其中，所述特定类型包括以下中的一个或更多个：

-表面单位法向量，其中，所述第一点云和所述第二点云中的每个点表示的读数是表面或两种材料之间的交界面的读数，

-和向量，

-散度向量，散度向量是与同一点处的表面法向量在同一方向上的向量并且其幅值和该点与相邻点集合之间的平均散度角成比例，所述相邻点集合的每个成员与该点之间的角度偏差是所述相邻点集合的成员处的法线与该点处的法线之间的角度偏差；

-边缘向量，边缘向量表示边缘，

-圆柱向量，圆柱向量表示圆柱、管道或柱子，

-平面向量，平面向量表示平面区域，

-点密度梯度向量，点密度梯度向量表示点密度增加的方向，

-点密度梯度散度向量，点密度梯度向量表示点密度梯度向量发散的位置，以及-梯度向量；

其中，在寻找以下项的过程中：

所述第一向量集的角度分布与所述第二向量集的角度分布之间的最大匹配度；和/或

第一1维数组与第二2维数组之间的最大匹配度；和/或

第一2维数组与第二2维数组之间的最大匹配度，

同一特定类型的向量子集之间的匹配度是逐个类型计算的，并且在任何平移或旋转角度下的匹配度是针对相应特定类型的匹配度的组合，该组合是平均值或加权平均值；

并且其中，在所述特定类型之一是和向量的情况下：

所述第一向量集的向量为和向量，并且所述第二向量集的向量为和向量；并且将所述第一点云转换为第一和向量集并将所述第二点云转换为第二和向量集包括：

分别针对每个点云，针对相应点云中作为查询点的每个点：围绕所述查询点形成预定半径的搜索半径球体，或者寻找特定数量的最近邻点；计算从所述查询点到所述搜索半径球体内或附近区域内所有其它点的向量；对所计算出的向量求和以获得所述和向量。

3.根据权利要求2所述的装置，其中，

所述装置还包括：

平移对齐处理器，其被配置为：

针对所述公共坐标系中的三条或更多条线中的每条线，其中，所述三条或更多条线中的每对线是不平行的，并且所述三条或更多条线中的至少一对线是不共面的：

记录所述第一点云中的每个点在所述线上的投影相对于任意原点的位置；

存储所记录的位置作为第一1维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第一1维数组；

记录所述第二点云中的每个点在所述线上的投影相对于任意原点的位置；

存储所记录的位置作为第二1维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第二1维数组；

寻找所述第二1维数组相对于所述第一1维数组沿所述线的平移：在该平移处计算出所述第一1维数组与所述第二1维数组之间的最大匹配度，并且记录计算出该最大匹配度时的平移；以及

输出：

所述第一点云和旋转后的第二点云作为所述公共坐标系中的合并点云，其中，旋转后的第二点云以相应记录的平移在所述公共坐标系中沿所述三条或更多条线中的每条线平移；和/或

所述三条线和所记录的沿所述三条或更多条线中的每条线的平移的向量表示，以及所述三个旋转轴和相应的找到的旋转角度的向量表示；和/或

旋转后的第二点云，其以相应记录的平移在所述公共坐标系中沿所述三条或更多条线中的每条线平移。

4.根据权利要求2所述的装置，其中，

所述装置还包括：

平移对齐处理器，其被配置为：

针对所述公共坐标系中的线和平面，其中，该线与该平面成角度或垂直于该平面：

记录所述第一点云中的每个点在所述线上的投影相对于任意原点的位置，并且存储所记录的位置作为第一1维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第一1维数组；

记录所述第一点云中的每个点在所述平面上的投影相对于任意原点的位置，并且存储所记录的位置作为第一2维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第一2维数组；

记录旋转后的第二点云中的每个点在所述线上的投影相对于任意原点的位置，并且存储所记录的位置作为第二1维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第二1维数组；

记录旋转后的第二点云中的每个点在所述平面上的投影相对于任意原点的位置，并且存储所记录的位置作为第二2维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第二2维数组；

寻找所述第二1维数组相对于所述第一1维数组沿所述线的平移，在该平移处计算出所述第一1维数组与所述第二1维数组之间的最大匹配度，并且记录计算出该最大匹配度时的平移；以及

寻找所述第二2维数组相对于所述第一2维数组在所述平面中的平移，在该平移处计算出所述第一2维数组与所述第二2维数组之间的最大匹配度，并且记录所述平移；

输出：

所述第一点云和所旋转的第二点云作为所述公共坐标系中的合并点云，其中，旋转后的第二点云以相应记录的平移在所述公共坐标系中沿所述线以及在所述平面中平移；和/或

所记录的沿所述线以及在所述平面中的平移的向量表示，以及所述三个旋转轴和相应找到的旋转角度的向量表示；和/或

旋转后的第二点云，其以相应记录的平移在所述公共坐标系中沿所述线以及在所述平面中平移。

5.根据权利要求1或4所述的装置，其中，

对所述第一点云和所述第二点云执行3D模式匹配算法，以识别描述能够由所述算法识别的特征实例的点集，以将所述点集的成员标记为相应的识别特征的实例的成员，用于标记所述点集的成员的标签是所标记的点的属性；其中，

在寻找所述第一1维数组与所述第二1维数组之间的最大匹配度和/或所述第一2维数组与所述第二2维数组之间的最大匹配度的过程中，针对同一特征的实例的匹配度是逐个特征计算的，并且所述匹配度是逐个特征的匹配度的、根据被标记为相应特征的实例的成员的标记点的数量加权的加权组合。

6.根据权利要求1至5中任一项所述的装置，其中：

获得所述第一3D数据集和所述第二3D数据集之一或两者的所述成像装置是LIDAR扫描仪、包括摄影测量的光学3D扫描装置、或者声纳扫描仪。

7.根据前述权利要求中任一项所述的装置，其中，

获得所述第一3D数据集和所述第二3D数据集之一或两者的所述成像装置是电阻率断层成像扫描器，该电阻率断层成像扫描器被插入到地面中并且成像空间在地下；或者

获得所述第一3D数据集和所述第二3D数据集之一或两者的所述成像装置是电阻抗断层成像扫描器，该电阻抗断层成像扫描器包括用于放置在受试动物的皮肤上的电极，并且成像空间是所述受试动物的内部。

8.根据前述权利要求中任一项所述的装置，其中，

获得所述第一3D数据集和所述第二3D数据集之一或两者的所述成像装置是MRI扫描器或检测核四极矩共振的扫描器，并且成像空间是受试动物的内部。

9.根据前述权利要求中任一项所述的装置，其中，

所述3D数据集采集单元包括去噪处理器，其中，获得所述第一3D数据集和获得所述第二3D数据集包括：所述去噪处理器对所述第一点云执行去噪算法，并且对所述第二点云执行所述去噪算法。

10.根据前述权利要求中任一项所述的装置，其中，

所述第一点云和所述第二点云中的每个点表示的读数是表面或两种材料之间的交界面的读数；并且

所述第一向量集的向量是表面单位法向量，并且所述第二向量集的向量是表面单位法向量；并且

将所述第一点云转换为第一表面法向量集并将所述第二点云转换为第二表面法向量集包括通过以下步骤生成所述第一表面法向量集并且生成所述第二表面法向量集：

分别针对每个点云，针对相应点云中作为查询点的每个点：选择一组相邻点，计算该组相邻点和所述查询点的协方差矩阵；求解所述协方差矩阵以找到所述协方差矩阵的三个特征值和三个特征向量，确定具有最小特征值的特征向量，将该特征向量归一化为预定单位长度，将归一化的单位向量与相应的第一法向量集或第二法向量集相加。

11.根据权利要求10所述的装置，其中，

针对所述查询点选择所述一组相邻点包括：选择具有与所述查询点重合的原点的预定半径的球体内的每个点，或者选择距所述查询点最近的N个点；并且

将所述第一点云转换为第一表面单位法向量集和/或将所述第二点云转换为第二表面单位法向量集还包括：

存储相应表面单位法向量集作为单位法向量的参考集；

重复生成具有逐渐减小的球体半径的相应表面单位法向量集，直到达到最小半径为止，在该点处终止重复，并且表面单位法向量的参考集被设置为相应表面单位法向量集，在每次重复时：

确定在该重复中生成的相应表面单位法向量集与表面单位法向量的参考集相匹配的置信度，

并且

如果所确定的置信度满足预定标准，则将表面单位法向量的参考集设置为相应的表面单位法向量集，并终止所述转换，以及

如果所确定的置信度不满足预定标准，则利用在所述重复中生成的相应的表面单位法向量集替换所存储的表面单位法向量的参考集，并继续所述重复。

12.根据权利要求2所述的装置，其中，

利用所述和向量执行边缘检测，其中，所述和向量的幅值用于检测表示边缘的和向量和表示角的和向量，其中，较大的幅值指示表示边缘的向量；并且

通过计算源自所述点云的点的所述和向量与一个或更多个附近表面法向量的向量点积来执行表面特征检测，具有等于所计算出的向量点积的余弦的角指示存在表面特征，并且将该表面特征识别为边缘、角或孔或遮挡。

13.根据权利要求1至11中任一项所述的装置，其中，

将所存储的第一点云转换为第一向量集，并且将所存储的第二点云转换为第二向量集，其中，所述第一向量集的每个成员和所述第二向量集的每个成员表示相应的点和相邻点，包括：对所存储的第一点云和第二点云或对表示所述点云的向量集执行自动编码器；

所述自动编码器是用于提取3D空间内的特征的无监督深度学习算法；其中，

所提取的特征由对应的向量表示，其中，向量的位置、取向和幅值由所提取的特征的位置、取向和维度确定。

14.根据权利要求1或2所述的装置，其中，将所存储的第一点云转换为第一向量集并且将所存储的第二点云转换为第二向量集包括：对所述点云或所述向量集应用非线性滤波器，其中，应用所述非线性滤波器包括从所述点云中排除未被边缘检测算法识别为表示边缘的任何点或者从所述向量集中排除未被边缘检测算法识别为表示边缘的任何向量，从而不对这些点或向量进行进一步处理。

15.根据权利要求1或2所述的装置，其中，所述旋转对齐处理器被配置为通过以下方式分别将所存储的第一点云和第二点云转换为第一向量集和第二向量集：

针对相应点云中作为查询点的每个点：

计算表面法线；

计算所述查询点处的表面法线与小搜索半径球体内的所有近邻点或指定数量的最近邻点的表面法线之间的角度偏差；

计算针对所述查询点所计算出的角度偏差的平均值；

获得散度向量作为相应向量集中的所述查询点的向量，该散度向量是具有针对所述查询点计算出的表面法线的方向并且长度与所计算出的平均值成比例的向量；以及

通过选择长于某个特定阈值的那些散度向量，对所述第一向量集和所述第二向量集进行滤波。

16.根据权利要求1或2所述的装置，其中，将所存储的第一点云转换为第一向量集并且将所存储的第二点云转换为第二向量集包括：

通过以下中的一种或更多种来寻找平面：RANSAC平面检测，Hough变换平面检测，以及基于表面曲率、表面法向角度偏差、颜色、反射率或粗糙度以及与所述平面的距离的区域生长；

寻找每个平面的面积；

其中，相应的向量集包括每个找到的平面的向量，该向量是平面向量，该平面向量是长度等于所述平面的面积的表面法向量。

17.根据权利要求1或2所述的装置，其中，

所述第一向量集的向量包括圆柱向量，并且所述第二向量集的向量包括圆柱向量；并且分别将所述第一点云转换为第一圆柱向量集并将所述第二点云转换为第二圆柱向量集，包括：

使用识别相应3D数据集中的圆柱的方法，并且寻找每个识别出的圆柱的半径、位置和取向；

在相应的向量集中包括每个识别出的圆柱的圆柱向量，所识别出的圆柱的圆柱向量沿着并平行于所识别出的圆柱的轴的取向，并且具有与所识别出的圆柱的半径有关的长度。

18.根据权利要求17所述的装置，其中，

识别3D数据集中的圆柱的方法包括：

执行分割算法以寻找可能的圆柱候选；

选择彼此处于一定距离内并处于同一可能的潜在圆柱上的两个随机点；

计算所述两个随机点所在的可能的圆柱的圆柱模型，该圆柱模型包括取向、半径和位置；

基于所述圆柱模型的表面曲率或表面角度偏差，调查圆柱表面的预定距离内的点，并且针对表面曲率或表面角度偏差在所述圆柱模型的表面曲率或表面角度偏差的预定阈值范围内的任何调查点，区域生长所述圆柱模型以包括所述调查点。

19.根据前述权利要求中任一项所述的装置，其中，

寻找获得所述第一向量集的角度分布与所述第二向量集的角度分布之间的最大匹配度时所述第二向量集在所述公共坐标系中定义的三个旋转轴中的一个或更多个旋转轴中相对于所述第一向量集的旋转角度，包括：

将所述第一向量集和所述第二向量集中的向量归于公共原点；

将以所述公共原点为中心的假想球体划分为表面区域或体积区域；

寻找获得所述表面区域或体积区域中的所述第一向量集中的向量的向量点分布与所述第二向量集中的向量的向量点分布之间的最佳匹配时所述第二向量集在所述公共坐标系中定义的三个旋转轴中的一个或更多个旋转轴中的每个旋转轴中相对于所述第一向量集的旋转角度。

20.根据权利要求1至14中任一项所述的装置，其中，

所述第一点云和所述第二点云中的每个点表示的读数是表面或两种材料之间的交界面的读数；

所述旋转对齐处理器还被配置为在寻找所述第一向量集的角度分布与所述第二向量集的角度分布之间的最佳匹配之前：

通过在所述第一向量集和所述第二向量集中识别表示模板形状之一的表面单位法向量并且从相应的向量集中移除未被识别为表示所述模板形状之一的表面单位法向量，对所述第一向量集和所述第二向量集进行滤波。

21.根据权利要求20所述的装置，其中，

所述识别表示模板形状之一的表面单位法向量的步骤是通过分别对第一表面单位法向量集和第二表面单位法向量集执行分割算法来实现的。

22.根据权利要求3所述的装置，其中，

所述成像装置的旋转运动是利用所述旋转对齐处理器输出的旋转角度来跟踪的；以及

所述成像装置在获得所述第一点云与所述第二点云之间的移动是利用所述三条线的向量表示以及所记录的由所述平移处理器输出的、沿所述三条线中的每条线的平移来跟踪的。

23.根据权利要求22所述的装置，其中，

所述成像装置安装在车辆上，并且车辆轨迹是从所述三条线的向量表示和所记录的沿所述三条线中的每条线的平移获得的。

24.根据权利要求1或2所述的装置，所述装置还包括：

平移对齐处理器，其被配置为在所述第一点云中寻找与所述第二点云中的3D对象和特征匹配的3D对象和特征；

寻找使所述第一点云和所述第二点云中的所述3D对象和特征对齐的平移向量；

通过绘制相对于三个正交轴的平移向量的长度和角度的直方图，从所述平移向量中寻找最共同的平移向量，选择最共同的长度和角度，并且选择最共同的向量的小范围内的任何向量，并且丢弃其余向量；

基于所述最共同的平移向量和所选择的向量执行所述第一点云和所述第二点云的平移对齐。

25.一种系统，所述系统包括：

第一成像装置，其被配置为在第一位置和取向上生成第一3D数据集，该第一3D数据集是第一时刻的第一空间的3D数据集；

第二成像装置，其被配置为在第二位置和取向上生成第二3D数据集，该第二3D数据集是第二时刻的第二空间的3D数据集，所述第二空间与所述第一空间重叠，其中，所述第二成像装置是所述第一成像装置并且所述第二时刻不同于所述第一时刻，或者所述第二成像装置与所述第一成像装置不同；

根据权利要求1或2所述的装置，其中，处于所述第一位置和取向的成像装置是所述第一成像装置，并且处于所述第二位置和取向的成像装置是所述第二成像装置。

26.一种方法，所述方法包括：

获得第一时刻的第一空间的第一3D数据集，所述第一3D数据集是三维的第一点云，所述第一点云中的每个点表示成像装置在所述第一空间内的读数；以及

获得第二时刻的第二空间的第二3D数据集，所述第二空间与所述第一空间重叠，所述第二3D数据集是三维的第二点云，所述第二点云中的每个点表示所述成像装置在所述第二空间内的读数；

存储所述第一3D数据集和所述第二3D数据集作为公共坐标系中的相应点云；

将所存储的第一点云转换为第一向量集，并且将所存储的第二点云转换为第二向量集，其中，所述第一向量集的每个成员和所述第二向量集的每个成员表示相应的点和相邻点；

寻找获得所述第一向量集的角度分布与所述第二向量集的角度分布之间的最大匹配度时所述第二向量集在所述公共坐标系中定义的三个旋转轴中的一个或更多个旋转轴中相对于所述第一向量集的旋转角度，所述匹配度被测量以比较所述第一向量集的角度分布和所述第二向量集的角度分布；并且：

存储绕所述一个或更多个旋转轴中的每个旋转轴的旋转角度，针对该旋转角度计算出的匹配度最大；或者

在所述公共坐标系中使所述第二点云绕相应的一个或更多个旋转轴以所存储的旋转角度旋转，并且在所述公共坐标系中输出旋转后的第二点云；

其中，

所述装置还包括：

针对所述公共坐标系中的线和平面，其中，该线与该平面成角度或垂直于该平面：

记录所述第一点云中的每个点在所述线上的投影相对于任意原点的位置，并且存储所记录的位置作为第一1维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第一1维数组；

记录所述第一点云中的每个点在所述平面上的投影相对于任意原点的位置，并且存储所记录的位置作为第一2维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第一2维数组；

记录旋转后的第二点云中的每个点在所述线上的投影相对于任意原点的位置，并且存储所记录的位置作为第二1维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第二1维数组；

记录旋转后的第二点云中的每个点在所述平面上的投影相对于任意原点的位置，并且存储所记录的位置作为第二2维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第二2维数组；

寻找所述第二1维数组相对于所述第一1维数组沿所述线的平移：在该平移处计算出所述第一1维数组与所述第二1维数组之间的最大匹配度，并且记录计算出该最大匹配度时的平移；以及

寻找所述第二2维数组相对于所述第一2维数组在所述平面中的平移：在该平移处计算出所述第一2维数组与所述第二2维数组之间的最大匹配度，并且记录所述平移；

输出：

所述第一点云和旋转后的第二点云作为所述公共坐标系中的合并点云，其中，旋转后的第二点云以相应的记录的平移在所述公共坐标系中沿所述线以及在所述平面中平移；和/或

所记录的沿所述线以及在所述平面中的平移的向量表示，以及所述三个旋转轴和相应的找到的旋转角度的向量表示；和/或

旋转后的第二点云，其以相应的记录的平移在所述公共坐标系中沿所述线以及在所述平面中平移。

27.一种方法，所述方法包括：

从处于第一位置和取向的成像装置获得第一时刻的第一空间的第一3D数据集，所述第一3D数据集是三维的第一点云，所述第一点云中的每个点表示所述成像装置在所述第一空间内的读数；以及

从处于第二位置和取向的成像装置获得第二时刻的第二空间的第二3D数据集，所述第二空间与所述第一空间重叠，所述第二3D数据集是三维的第二点云，所述第二点云中的每个点表示所述成像装置在所述第二空间内的读数；

存储所述第一3D数据集和所述第二3D数据集作为公共坐标系中的相应点云；

将所存储的第一点云转换为第一向量集，并且将所存储的第二点云转换为第二向量集，其中，所述第一向量集的每个成员和所述第二向量集的每个成员表示相应的点和相邻点；

寻找获得所述第一向量集的角度分布与所述第二向量集的角度分布之间的最大匹配度时所述第二向量集在所述公共坐标系中定义的三个旋转轴中的一个或更多个旋转轴中相对于所述第一向量集的旋转角度，所述匹配度被测量以比较所述第一向量集的角度分布和所述第二向量集的角度分布；并且：

存储绕所述一个或更多个旋转轴中的每个旋转轴的旋转角度：针对该旋转角度计算出的匹配度最大；或者

在所述公共坐标系中使所述第二点云绕相应的一个或更多个旋转轴以所存储的旋转角度旋转，并且在所述公共坐标系中输出旋转后的第二点云；

其中，

所述第一向量集的向量和所述第二向量集的向量各包括多个向量子集，所述多个向量子集中的每个子集将相应的点云表示为特定类型的向量，该特定类型不同于其它子集的类型；其中，所述特定类型包括以下中的一个或更多个：

-表面单位法向量，其中，所述第一点云和所述第二点云中的每个点表示的读数是表面或两种材料之间的交界面的读数，

-和向量，

-散度向量，散度向量是与同一点处的表面法向量在同一方向上的向量并且其幅值和该点与相邻点集合之间的平均散度角成比例，所述相邻点集合的每个成员与该点之间的角度偏差是所述相邻点集合的成员处的法线与该点处的法线之间的角度偏差；

-边缘向量，边缘向量表示边缘，

-圆柱向量，圆柱向量表示圆柱、管道或柱子，

-平面向量，平面向量表示平面区域，

-点密度梯度向量，点密度梯度向量表示点密度增加的方向，

-点密度梯度散度向量，点密度梯度向量表示点密度梯度向量发散的位置，以及

-梯度向量；

其中，在寻找以下项的过程中：

所述第一向量集的角度分布与所述第二向量集的角度分布之间的最大匹配度；

和/或

第一1维数组与第二1维数组之间的最大匹配度；和/或

第一2维数组与第二2维数组之间的最大匹配度，

同一特定类型的向量子集之间的匹配度是逐个类型计算的，并且在任何平移或旋转角度下的匹配度是针对相应特定类型的匹配度的组合，该组合是平均值或加权平均值；

并且其中，在所述特定类型之一是和向量的情况下：

所述第一向量集的向量为和向量，并且所述第二向量集的向量为和向量；

并且将所述第一点云转换为第一和向量集并将所述第二点云转换为第二和向量集包括：

分别针对每个点云，针对相应点云中作为查询点的每个点：围绕所述查询点形成预定半径的搜索半径球体，或者寻找特定数量的最近邻点；计算从所述查询点到所述搜索半径球体内或附近区域内所有其它点的向量；对所计算出的向量求和以获得所述和向量。

28.根据权利要求26或27所述的方法，其中，

所述输出包括输出公共坐标系中定义的旋转后的第二点云和所存储的第一点云，和/或输出具有一个或更多个存储的旋转角度的相应坐标系中的所述第一点云和所述第二点云。

29.根据权利要求27或28所述的方法，所述方法还包括：

平移对齐过程，其包括：

针对所述公共坐标系中的三条或更多条线中的每条线，其中，所述三条或更多条线中的每对线是不平行的，并且所述三条或更多条线中的至少一对线是不共面的：

记录所述第一点云中的每个点在所述线上的投影相对于任意原点的位置；

存储所记录的位置作为第一1维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第一1维数组；

记录旋转后的第二点云中的每个点在所述线上的投影相对于任意原点的位置；

存储所记录的位置作为第二1维数组，和/或存储相应记录的位置处的每个点的一个或更多个属性或读数作为第二1维数组；

寻找所述第二1维数组相对于所述第一1维数组沿所述线的平移：在该平移处计算出所述第一1维数组与所述第二1维数组之间的最大匹配度，并且记录计算出该最大匹配度时的平移；以及

输出：

所述第一点云和旋转后的第二点云作为所述公共坐标系中的合并点云，其中，旋转后的第二点云以相应的记录的平移在所述公共坐标系中沿所述三条或更多条线中的每条线平移；和/或

所述三条或更多条线和所记录的沿所述三条或更多条线中的每条线的平移的向量表示，以及所述三个旋转轴和相应的存储的旋转角度的向量表示；和/或

旋转后的第二点云，其以相应的记录的平移在所述公共坐标系中沿所述三条或更多条线中的每条线平移。

30.一种方法，所述方法包括：

获得表示受试体的相应部分的多个单独3D数据集，所述多个单独3D数据集之间的平移和旋转关系是未知的；

执行根据权利要求27所述的方法，包括，

针对所述多个单独3D数据集中的一对单独3D数据集的每个组合：

执行根据权利要求27所述的方法的存储、转换、寻找和存储的步骤，

并且除了存储绕相应的一个或更多个旋转轴的旋转角度之外，还存储所述第一向量集的角度分布与所述第二向量集的角度分布之间的对应的最大匹配度的幅值；

针对所述多个单独3D数据集中的每个单独3D数据集：

针对包括该单独3D数据集作为成员的所有3D数据集对，识别所存储的最大匹配度最大的数据集对，可选地识别所存储的最大匹配度在所定义的最大值范围内的任何数据集对，并且对所识别数据集对或每个识别的数据集对执行根据权利要求29所述的平移对齐过程；

执行根据权利要求27所述的获得步骤，其中将所识别的数据集对或每个识别的数据集对作为所述第一3D数据集和所述第二3D数据集，对所识别的数据集对、利用针对该数据集对存储的绕相应的一个或更多个旋转轴的旋转角度执行根据权利要求27所述的旋转步骤，并且旋转后的第二点云沿所述公共坐标系中的三条或更多条线中的每条线平移来自权利要求29所述的平移对齐过程的相应的记录的平移，从而获得彼此之间具有固定旋转和平移关系的所述一对单独3D数据集的成对点云表示；

通过对在超过一个所述成对点云表示中出现的同一单独3D数据集的实例进行共同定位，将所述数据集对的所述成对点云表示合并为单个点云。

31.一种点云对，所述点云对是在公共坐标系中定义的、通过根据权利要求27至30中任一项所述的方法获得的。

32.一种图像处理方法，所述图像处理方法包括：

获得受试体的点云表示，该点云表示由多个单独扫描组成，每个扫描是所述受试体的一部分的点云表示，每个扫描与一个或更多个其它扫描重叠并且具有与所述一个或更多个其它扫描的定义的旋转和平移关系，其中，所述扫描中的至少一个扫描与超过一个其它扫描重叠，

其特征在于，执行全局对齐过程，该过程包括：

针对所述多个单独扫描中作为受试体点云的每个单独扫描，将与该受试体扫描重叠的一个或更多个其它扫描设置为参考点云，

针对所述参考点云的每个单独扫描，利用所定义的所述受试体点云与所述对象的点云表示中的所述参考点云的单独扫描之间的定义的旋转和平移关系来对所述受试体点云和所述参考点云的单独扫描执行旋转对齐算法和平移对齐算法作为初始估计，使所述受试体点云相对于所述参考点云的单独扫描旋转和平移，直到满足过程误差标准为止，以获得所述受试体点云与所述参考点云的单独扫描之间的修改后的定义的旋转和平移关系；

将所述受试体点云与所述参考点云的各个单独扫描之间的修改后的定义的旋转和平移关系组合起来；

在所述受试体的点云表示中实现所述受试体点云与所述参考点云之间的组合的修改后的定义的旋转和平移关系；

其中，

执行所述旋转对齐算法包括：通过根据权利要求26至29中任一项所述的方法，在根据权利要求25所述的系统中，在根据权利要求1至24中任一项所述的装置中，将作为第一3D数据集和第二3D数据集的一对扫描进行旋转对齐；

所述方法还包括：

重复所述全局对齐过程一次或更多次，其中，每次重复具有逐步严格的过程误差标准。

33.根据权利要求32所述的图像处理方法，所述图像处理方法还包括：

执行所述平移对齐算法包括：在根据权利要求3所述的装置或根据权利要求29所述的方法中对齐作为第一3D数据集和第二3D数据集的一对扫描，所记录的平移是所定义的平移关系。

34.根据权利要求32或33所述的图像处理方法，其中，所述过程误差标准是最大允许误差。

35.一种计算机存储介质，所述计算机存储介质存储有计算机程序，所述计算机程序在由计算装置执行时，使所述计算装置执行根据权利要求32至34中任一项所述的方法。

36.一种图像处理装置，所述图像处理装置包括存储器硬件和处理器硬件，所述存储器硬件存储处理指令，所述处理指令在由所述处理器硬件执行时使所述处理器硬件执行根据权利要求32所述的图像处理方法。