基于平移搜索的三维点云配准的快速BnB算法

基于平移搜索刘银龙1，2 [0000−0002−6468−8233]，王晨 1，2 [0000−0003−2922−5345]，宋志坚1，2 [0000−0001−9873−216X]，王曼宁 1，2[0000−0002−9255−3897]1复旦大学基础医学院数字医学研究中心，上海200032{yinlongliu15，wangchen17，zjsong，mnwang}@ fudan.edu.cn2上海市医学影像计算与计算机辅助介入重点实验室，上海200032抽象。三维刚性点云配准在计算机视觉和机器人领域有着广泛的应用当相对变换较大或重叠率较小时，局部方法往往会失败，从而需要全局方法大多数现有的全局方法利用SE（3）的6D参数空间上的BnB优化这样的方法通常非常慢，因为BnB优化的时间复杂度在参数空间的维度上是指数的在本文中，我们解耦的平移和旋转的优化，我们提出了一个快速的BnB算法全局优化的三维平移参数。然后，通过利用由BnB算法找到的全局最优平移来计算最优旋转 利用一种新提出的旋转不变特征，实现了平移和旋转的分离优化。在具有挑战性的数据集上的实验表明，该方法在速度和准确性方面优于最先进的全局方法。关键词：点云配准·全局优化·旋转不变特征1介绍三维刚性点云配准是计算机视觉、机器人和计算机辅助干预等领域的常见问题[1传统的局部方法仅在相对变换较小并且存在较大比例的真实重叠时才足够相反，当存在大的相对变换或当重叠比例小时，需要全局方法示例应用包括同步定位和映射（SLAM）[1]中的闭环和计算机辅助定位和映射中的空间配准。前两位作者对这项工作的贡献相当。通讯作者是宋志坚和王曼宁2Y. Liu等人干预[5]。近年来，使用分支定界（BnB）优化来全局配准3D点云的情况激增。然而，BnB优化的时间复杂度在问题的维度上是指数的。大多数现有的全局方法在SE（3）的参数空间中优化目标函数，其具有六个维度;因此，它们通常非常慢。受[6]的启发，其中SE（3）被解耦为SO（3）和R3，并且旋转和平移分别在SO（3）和R3中被优化，我们还通过新提出的旋转不变特征在低维空间中分别优化旋转和平移以实现高效率在[6]中提出的方法中，首先使用BnB优化来全局优化旋转以对齐从原始点云构造的平移不变特征，即表面法向分布。一旦获得SO（3）中的全局最优旋转，则执行R3与[6]相比，我们提出了一个新的旋转不变特征（RIF），它允许我们首先全局优化R3中的平移，以对齐为原始点云计算的特征。我们提出的RIF是一个三元组构造的一对点。RIF的前两个元素是两点到原点的距离，第三个元素是两点之间的距离。从概念上讲，该RIF的元素是由两个点和原点形成的三角形的边长，其相对于两个点围绕原点的旋转显然是不变的。我们最大限度地提高了目标函数定义的共识集之间的两个RIF集构建的两个点云注册，并推导出这个目标函数的上限在R3的参数空间的翻译。在此上界的基础上，提出了一种高效的BnB优化算法，保证了算法的全局最优性。使用真实数据的实验证明了所提出的6D刚性点云配准方法在具有挑战性的现实世界条件下的效率和准确性，例如大的相对变换和部分重叠。2相关工作给定两个3D点云X和Y，在它们之间执行3D刚性配准是找到最佳变换T∈SE（3）以对准它们的过程，如下所示：T* = arg maxT∈SE（3）O（Y，T（X））（1）其中X是移动点云，Y是参考点云，并且O是测量对准的函数。如果这些之间的某些对应关系如果已知两个点云，则可以稳健地解析计算变换。然而，如果不知道对应关系，则该配准变成困难的优化问题，因为目标函数O是高度非凸的。基于RIF匹配的全局点云配准32.1局部方法作为一个非凸优化问题，点云配准首先用迭代方法局部求解，其中最流行的是迭代最近点（ICP）方法[7]。ICP方法从初始变换开始，并在找到与当前变换的对应关系和用新建立的对应关系更新变换之间迭代。ICP算法的优化方案是期望最大化（EM）型，只能收敛到局部最优。此外，原始ICP算法通过最小化在迭代期间找到的对应点对之间的平均距离来根据L2距离ICP算法的目标函数和优化方案使其对野值非常敏感，且收敛域很小。已经提出了大量的变体来提高ICP算法的收敛性和鲁棒性[8]。用于改进收敛性的另一研究路线是将ICP算法的目标函数替换为根据概率密度定义的新目标函数[9]。在这些方法中，借助于核（诸如高斯核）从原始点云构造概率密度，并且使从要配准的两个点云构造的两个概率密度之间的差最小化。可以使这种目标函数比ICP目标函数平滑得多，从而扩大收敛范围。然而，所有这些方法仍然只能收敛到局部最优。2.2全局方法全局点云配准的第一次尝试使用启发式方法，例如模拟退火[10]或粒子群优化[11]。无论初始化条件如何，这种方法都具有达到全局最优的增加的概率但是，不能保证全局最优。目前的趋势是使用保证全局优化的方法来解决全局点云配准问题。这些方法中的大多数使用BnB优化，并且几乎每个新开发的方法都涉及导出目标函数的新界限[12]是关于全局点云配准的开创性工作，其中点云配准问题在变换和对应方面被参数化，并且通过将BnB优化与Lipschitz优化相结合来解决仅在旋转下的简化问题Go-ICP[13]是第一个实用的全局点云配准方法。基于在[14]中提出的引理，其陈述了当向量被旋转通过两次旋转时，两个新向量之间的角度差不大于两次旋转之间的角度差，Go-ICP在SO（3）的三次分支中在旋转通过任意旋转的点上建立Go-ICP通过BnB优化来优化与传统ICP算法相同的目标函数，并且使用修整技术来解决异常值。[15]提出了一个更严格的界限，并优化了一个更强大的4Y. Liu等人j=1i=1基于共识集的目标函数，并且在[16]中进一步收紧了该界限。解决离群值的另一种方法是根据概率密度定义目标函数，如在GOGMA[17]中所做的，其最小化从具有高斯核的原始点云构建的两个概率密度之间的L2距离。上述全局点云配准方法优化SE（3）的六维空间中的目标函数。非对称点匹配（APM）优化了根据变换和点对应矩阵定义的目标函数[18]。虽然原始参数空间的维数非常高，但通过假设点对点对应，在具有与空间变换的维数相同的维数的低维空间中开发了一个界限这种假设使得APM难以配准部分重叠的点云或具有总异常值的点云。该方法的优点是可以进行仿射配准。BnB优化的时间复杂度在维度上是指数级的。问题的本质。因此，现有的全局点云配准方法通常非常慢，主要是因为SE（3）的参数空间具有六个维度。提高时间效率的一种方法是将SE（3）解耦为SO（3）和R3，然后分别优化3D旋转和3D平移。[6]利用平移不变特征来首先优化3D旋转，然后使用所计算的全局最优旋转来优化3D平移;然而，构造平移不变特征的过程非常耗时。2.3贡献本文还分别对旋转和平移进行了优化，以达到较高的效率。我们的第一个贡献是，我们提出了一个简单的RIF，使我们能够首先在全球范围内搜索两个点云之间的翻译，以对齐从原始点云构建的功能我们定义了一个强大的目标函数的共识集的基础上，并推导出一个严格的约束，以实现快速BNB优化的翻译搜索。其次，提出了一种基于全局平移搜索的6D点云配准算法具有挑战性的真实数据上的实验表明，所提出的方法的优越性，在运行时间和准确性方面的国家的最先进的全球方法3方法3.1旋转不变特征设Y={ yj}Y且X={ xi}X是两个相关的通过从X到Y的3D刚性变换。对于一对对应点yj和xi，我们有yj=R*（xi+t*）（2）当r*∈R3和R*∈SO（3）时，分别是从X到Y的随机变换.基于RIF匹配的全局点云配准5对于移动点云中的一对点{xi1， xi2}，我们提出了一个三元组{<$xi1<$，<$xi2<$，<$xi1−xi2 <$$>}的构造，其中<$·<$表示R3中的欧氏范数。如图1，这个三元组的三个元素是由两个点xi1和xi2与原点形成的三角形的边长。显然，这个三元组相对于围绕原点的旋转是不变的，因此，我们称之为RIF。这意味着对于任何R∈SO（3），我们有ǁRxi1ǁǁxi1ǁ我的处方i2=简体中文中文（简体）R（xi1−xi2）图1（b-d）显示了RIF随点平移的变化。10.80.60.40.20-0.200.20.40.60.8（一）1.110.90.80.70.60.50.40.60.81（b）第（1）款1.110.90.80.70.60.50.40.60.811.2（c）第（1）款1.110.90.80.70.60.50.60.811.2（d）其他事项Fig. 1. RIF的插图以及它们如何随着翻译而变化。仅示出了RIF的前两个维度，因为第三维度不随着点的平移而改变。(a)四个参考点（蓝色圆圈）和四个移动点（红色十字）。两个点云之间存在相对旋转，但没有相对平移。这两个三角形表示从参考点云和移动点云的对应点对构造的两个RIF。(b)根据（a）中的参考云和移动云构建的RIF。这两组RIF彼此匹配，因为在参考点云和移动点云之间不存在相对平移。(c)（d）当两个点云之间分别存在（0.1，0.1）和（0.2，0.2）的相对平移时的RIF。3.2译文检索的目标函数我们使用p i1，i 2={x i1，xi2，xi1−xi2}表示由一对移动点{x i1，x i2}构造的RIF，使用q j1，j 2={y j1，yj2，yj1− y j2}表示由一对参考点{y j1，y j2}构造的RIF。根据等式（3），如果两个点对通过平移t和旋转R相关，则我们有ǁyj1ǁǁR(xi1+ t)ǁǁxi1+tǁqj1，j 2=yj2=yj1−yj2R（xi1−xi2）xi1−xi2（四）6Y. Liu等人n=1m=1mm=1我们发现两个RIF通过平移t相关，并且我们定义函数F（t）来表达这种关系。函数F（t）的参数空间是R3。这意味着，如果两个点云通过平移t和旋转R相关，则从对应的点对构造的RIF仅通过函数F（t）的平移t设Q={ qn}Q是由点对{yj1，yj2}构造的RIF的集合，其中yj1，yj2∈Y且j1/= j2。设P={ pm}P是RIF的集合由p对{xi1，xi 2 }构成的结构，其中xi 1，xi2∈X且i1=/i2. 此找到从X到Y的最佳平移的问题变成以下优化问题：t*=argmaxt∈R3E（Q，F（P，t））（5）其中E（t）是测量两个RIF集合之间的比对的函数。通过在R3上求解（5）中的优化问题，我们可以找到最优值*，其形成在SE为了使目标函数对离群值具有鲁棒性，我们基于共识集定义E（t）如下：E（Q，F（P，t））=Σmax <$$>F（pm，t）− qn<$∞≤ε<$（6）nM其中·是一个指示符函数，如果条件·为真，则返回1，否则返回0。·Q和P的大小都非常大。从RIF的定义中，我们可以看到RIF的第三个元素，即对中两点之间的距离，相对于平移是不变的。这意味着相应RIF in和Q和P的第三个元素彼此相等。在在实践中，我们不需要匹配Q和P的整体。相反，我们匹配Q和P中的RIF的子集，其第三个元素落在特定的RIF范围我们用Q′Q′′={ qn}n=1且P={ p}P′得双曲正弦值.本文中使用实际目标函数是 ΣE（Q′，F（P′，t））=maxF（pm，t）−qn∞≤ε（7）nM3.3边界和基于分支定界的算法为了通过BnB优化来最大化（7），我们需要在参数空间的分支中对该目标函数进行上界在我们的BnB算法中，我们在R3中的立方体中搜索最佳翻译，并迭代地将参数空间划分为子立方体。如图2，对于对角线长度为2r且中心在tc的平移立方体T，我们有x+ tc基于RIF匹配的全局点云配准7(a)（b）第（1）款图二.从原点到由平移立方体平移的点的距离的界限。为了更清楚地说明，使用了二维坐标。平移立方体是T，并且点x在平移任意t∈T之后的可能位置由灰色正方形表示T的对角线长为2r，中心在tc. 因此，从原点到灰色正方形中任意一点的距离介于x+ tc− r和x+ tc+ r之间。（a）和（b）示出了两种情况，其中原点分别位于以tc为中心、半径为r的圆的外部和内部。设Pm是由来自移动点云的点对{xm1， xm2}构造的RIF，并且设qn是由来自参考点云的点对{yn1， yn2}构造的RIF然后，对于任何t∈T，使用公式（8），我们有F（pm，t）− qnǁxm1+ t ǁ − ǁ y n1ǁǁxm2 + t ǁ − ǁ yn2ǁǁxm1−xm2：=C（t）（9）其中xm1−xm2−yn1−yn2是关于t的常数。因为我们可以从方程（8）计算出xm1+ t和xm2+ t的界，所以我们可以很容易地计算出xm1+ t−yn1和xm2+ t− yn2的绝对值的界。然后我们可以计算F（pm，t）− qn∞的上界和下界，我们用C（t）表示这个下界因此，我们有F（pm，t）− qn它遵循<$$>F（pm，t）−qn<$∞≤ε<$≤ <$C（t）≤ε<$（11）然后，我们可以将上限函数定义为Σ对于任何t∈T，我们有E（T）=maxC（t）≤ε（12）nME（Q’，F（P’，t））≤E（T）（13）利用公式（12）给出的上界，我们可以搜索平移空间以找到使目标函数（7）最大化的全局最优平移算法概述于算法1中。+的+的R+的+的R∞8Y. Liu等人d=1算法1：基于RIF的全局最优翻译搜索输入：点集X和Y输出：操作将X和Y放在一起。1 构造两组RIF三元组P′和Q′。2 InitializetranslationbranchT0;E*←0，t*←0. I_s_rt_T_o_i_n以优先级E（T_o）进行查询。3 当q不为空时4从q中获得最高优先级的立方体T。5如果E（T）=E，则6终止。7端8tc← cubeT9如果E（tc）>E*，则10UpdateE*←−E（tc），t*←tc11端12将T细分为八个立方体{Td}8。13对于每个Tddo14如果E（Td）>E*，则15将Td插入q，优先级为E（Td）。16端17端18 端19 Obtaintheoptimaltranslatint*。3.4六维配准只要找 到X和Y之间的最优旋转方向，就可以很容易地计算出两个点云之间的最优旋转R *。例如，我们可以使用[15]或[16]中提出的全局旋转搜索方法;然而，实际上可以以更容易的方式获得最佳旋转。当我们获得最佳的viaAlgorithm1时，我们获得了P ′和Q ′之间的一致RIF，这为我们提供了原始点云X和Y中的点之间的潜在对应。当然也在这些对应中会有一些异常值，估计R*的问题就变成了一个鲁棒估计问题，可以快速可靠地解决。在本文中，我们通过随机抽样一致性（RANSAC）算法[19]估计R*我们参考我们的6D刚性配准方法就像GoTS。许多全局优化方法为了速度和全局最优性而牺牲精度，并且随后进行局部细化以提高精度。类似地，可以将局部细化过程添加到GoTS;我们将具有局部计算精度的算法称为GoTS+。4实验和结果在本节中，我们将报告使用管理差异对GoTS和GoTS+的性能进行评估的结果，并将这些结果与适当的评估进行比较。基于RIF匹配的全局点云配准9针对以下三种全局方法：Go-ICP[13]、Glob-GM[15]和APM[18]的流程图 我们没有与[6]和[17]的方法进行比较，其中使用了G PU。 G oTS和GoTS+在MATLAB中实施。其他方法的代码来自作者。在GoTS中，为RIF的第三个元素设置范围，RIF用于构建翻译搜索的P’和Q’。我们将该范围的下限设置为原始点云在X、Y和Z方向上的最短延伸的65%，并将范围宽度设置为内点阈值的0.01倍。在补充材料中，我们研究了注册时间相对于用于选择RIF进行翻译搜索的范围宽度这些实验中使用的原始点云非常密集，我们使用MATLAB的pcdownsample函数以指定的网格大小对其进行下采样。在第4.1节和第4.2节中使用合成数据的实验中，我们缩放点以使它们落入[-1，1]3的立方体内，并将0.01设置为GoTS的内点阈值;在第4.3节和第4.4节中使用真实数据的实验中，我们将网格大小设置为GoTS的内点阈值。在Glob-GM中，匹配列表和局部优化选项被打开。在Go-ICP中，使用距离变换来加速最近邻距离计算。所有实验都在具有2.80GHz Intel（R）Core（TM）i7- 7700 HQCPU和16 GB RAM的计算机上进行。每个方法的运行时间包括方法特定的预处理时间。4.1与其他全局方法的运行时比较我们首先比较了运行时间的GoTS配准点云与其他三种方法的运行时间的不同数量的点在该实验中，我们使用来自Stanford 3D扫描库的兔子点云，并将原始数据下采样为具有不同数量的点的将下采样点云缩放到[-1，1]3的立方体内并视为移动点云，并通过随机变换将其变换到新的位置以形成参考点云。由此，我们知道了从移动点云到参考点云的地面实况转换以及两个点云之间的点对应。然后用四种方法中的每一种将移动点云配准到参考点对于每个点的数量，我们用不同的随机地面实况变换执行20次配准，并且相对于点的数量的平均运行时间在图中示出。3（a）和图3（b）款。Glob-GM和APM在注册400点时的运行时间超过1000秒 为了更好地说明GoTS和Go-ICP之间的差异，我们在图中只显示了这两种方法的运行时间。3（b）款。我们可以看到，GoTS和Go-ICP比其他两种方法快得多，GoTS的速度大约是Go-ICP的四倍。在本实验中，所有的方法都可以成功地注册的移动和参考点云。图3（c）显示了在1000个移动点和1000个参考点之间的一次配准期间算法1的上限和下限的演变，其中GoTS仅用了5.2秒就收敛。10Y. Liu等人APMGlob-GMGo-ICPGOTSGo-ICPGoT时间（s）客观价值100080050 10040 80600 30 60400 20 40200 10 20050010001500200025003000N（点数）（一）050010001500200025003000N（点数）（b）第（1）款00123456时间（s）（c）第（1）款图三. (a)GoTS、Go-ICP、APM和Glob-GM相对于点数的运行时间。（b）仅GoTS和Go-ICP相对于点数的运行时间，以更好地说明这两种(c)当配准1000个点时，作为时间的函数的全局最优平移搜索方法（算法1）中的上限和下限的演变。4.2对离群值的在该实验中，我们评估了GoTS对离群值的鲁棒性，并将其与其他三种方法的鲁棒性进行了比较。点云配准中经常遇到离群点;在本节中，我们仅研究不属于由点云表示的真实对象的总异常值的影响。总异常值可能源于用于获得点云的设备的缺陷。在部分重叠曲面的配准中，不与另一点云重叠的区域中的点也可视为离群点;下一节将报告针对这种情况的实验。我们以0.0121的网格大小对来自Stanford 3D扫描存储库（http：//graphics.stanford.edu/data/3Dscanrep/）的兔子数据进行下采样以获得500个点，然后将这些点缩放以落入[-1，1]3的立方体内。缩放的数据点被用作干净的移动点云。将均匀分布的随机离群点添加到该干净点云中，然后经由随机变换来变换所得到的点云以形成参考点云。添加不同数量的离群值以生成具有五种不同离群值百分比的参考点云：10%、20%、30%、40%和50%。图4（c）和（d）分别示出了具有10%和50%离群值的参考点云的示例对于每个离群值比率，我们运行每个算法20次。表1报告了每种方法的内点的均方根误差。GoTS和Go-ICP都实现了高准确度，表明它们对离群值都非常稳健。虽然Go-ICP的误差小于GoTS的误差，但在实践中GoTS的精度足够高。GoS+s的算法显示，通过后续局部细化可以有效地对齐，这需要少于一秒的额外时间。Glob-GM的配准误差远大于GoTS，且随着离群值比例的增大而增大。考虑到所有点都位于边长为2的立方体中，Glob-GM的配准误差表明上界下界时间（s）基于RIF匹配的全局点云配准11APMGlob-GMGo-ICPGOTS时间（s）在许多情况下，它不能对准两个点云。APM的误差更大;这些大误差的原因可能是APM中采用的一一对应的假设在这些具有异常值的实验中是无效的。表1.配准后相应内点之间的均方根误差方法GOTSGoTS+Go-ICPGlob-GMAPM百分之十1.03E-021.38E-158.95E-061.10E-012.17E-01百分之二十1.20E-029.72E-167.51E-061.21E-01-百分之三十1.14E-029.50E-154.65E-061.14E-01-百分之四十1.09E-021.38E-154.12E-061.12E-01-百分之五十1.17E-021.19E-156.22E-061.41E-01-四种算法相对于异常值比率的平均运行时间如图所示。第4（a）段。APM的运行时间随着我们向500个内点添加更多的离群值而迅速增加，并且当离群值比率为20%时超过1000秒。 当异常值比率大于20%时，Glob-GM的运行时间缩短;这是因为算法在两个点云未对准的不正确解处较早终止。同样，我们在图1B中分别绘制了GoTS和Go-ICP的平均运行时间4（b）更好地说明它们之间的区别。1000 50800 40600 30400 20200 1000.1 0.2 0.3 0.40.5异常值比率（一）00.1 0.2 0.3 0.4 0.5异常值比率(b)（c）（d）见图4。(a)四种方法相对于离群值比率的运行时间。(b)仅GoTS和Go-ICP相对于异常值比率的运行时间，以更好地说明它们之间的差异（c）、（d）分别具有10%异常值和50%异常值的参考点云Go-ICPGoTS时间（s）12Y. Liu等人4.3真实3D扫描在本节中，我们报告了使用真实数据在部分重叠的点云上测试所提出的方法的性能的结果。在此实验中，我们比较了GoTS和GoTS+与Go-ICP和Glob-GM。本文没有使用APM，但由于其难以处理离群值，因此可以预期其配准误差在本实验中会很大。在 本 实 验 中 ， 我 们 使 用 了 来 自 Stanford 3D 扫 描 库 的 bun000 、bun045、bun090、ArmadilloStand60、ArmadilloStand30和ArmadilloStand0前三个点云是从三个不同方向扫描的兔子，最后三个是从三个不同方向扫描的犰狳。原始点云被下采样为由1000到2000个点组成的云，所有这些点都位于边长为0.3的立方体中。同一对象的每对扫描之间的地面实况变换在数据集中提供。使用这四种方法，我们执行了四对点云之间的配准：ArmadilloStand 60/ArmadilloStand 30，Armadil-loStand30/ArmadilloStand 0，bun 045/bun 000和bun 090/bun 000。配准前后的点云对如补充材料所示。表2.使用四种不同方法配准犰狳AmadilloStandd60/30 ArmadilloStand30/0方法GOTS GoTS+ Go-ICP Glob-GM GOTS GoTS+ Go-ICP Glob-GM传输[m] 0.00370.00390.00230.280.00650.00630.00050.014◦Rot[]0.940.844.131721.821.701.7338.10时间[s] 27.1127.3330.6744717.0017.2232.083136表3.使用四种不同方法配准兔bun045/000 bun090/000方法GOTS GoTS+ Go-ICP Glob-GMGOTSGoTS+ Go-ICP Glob-GM传输[m] 0.00580.00570.00240.0250.0069 0.00740.100.14◦Rot[]3.953.944.1019.413.823.5590.24137.02时间[s] 14.0214.2530.44236156.3956.62603.63868基于RIF匹配的全局点云配准13表2和表3列出了每种方法的平移和旋转误差以及运行时间在这些实验中，对于Armadillo数据，Glob-GM的内点阈值被设置为0.05，对于兔子数据，Glob-GM的内点阈值被设置为0.029，因为当我们使用等于下采样函数的网格大小的内点阈值时，Glob-GM不能在1000秒内终止。我们可以看到，GoTS在这些具有挑战性的配准中实现了高精度。 特别地，通过算法1中的全局最优翻译搜索方法实现的翻译误差都非常小。Go-ICP在bun 090/000上失败，这是一个困难的情况，因为两个点云之间的相对变换非常大，重叠率很小。在这种情况下，Go-ICP的运行时间仔细调整微调比率可以提高Go-ICP的准确性，但在实践中，在配准之前无法知道最佳微调比率。Glob-GM在所有四种情况下都失败了，并且它的运行时间非常长。在这些实验中，为全局翻译搜索生成的RIF的数量在150和160之间4.4客厅扫描的登记我们测试了所提出的方法的性能上的大规模的现场数据使用的“liv ingR oom。MAT LAB实验室的“3- D点集和拼接”，其由通过连续扫描起居室获得的我们使用GoTS、Go-ICP和Glob-GM来配准这些数据的第一帧和第六帧的点云。原始点云由300，000多个点组成，所有这些点都位于边长为4米的立方体。它们以0.1米的网格大小(a)初始化（b）GoTS（c）Go-ICP（d）Glob-GM图五.配准前后的LivingRoom结果列于表4中。GoTS在25.90秒内成功配准了两个点云。相比之下，当均方误差阈值设置为0.05时，Go-ICP无法配准点云。当我们使用0.01的均方误差阈值时，算法不能在半小时内终止。对于Glob-GM，当我们将内点阈值设置为0.1时，算法无法在半小时内终止然后，我们将内点阈值设置为0.8;14Y. Liu等人算法在633.8秒后终止，但结果不正确。从参考点云和移动点云生成的RIF的数量分别为1434和1866。更多的结果可以在补充材料中找到。表4.配准livingRoom点云的结果。方法GOTSGo-ICPGlob-GM传输[m]0.10471.1580.4555◦Rot[]4.382158.397.59时间[s]25.90489.6633.85结论我们介绍了一种快速的全球3D刚性点云注册方法的基础上解耦的平移和旋转优化，通过新提出的旋转不变的功能。我们首先使用BnB算法来匹配从两个点云构建的旋转不变特征集，然后使用优化的平移来计算最佳旋转将平移和旋转的优化解耦，使得该算法比现有的方法更有效在真实数据上的实验表明，该算法在部分重叠，大角度差异和高离群值比率的情况下的优越性。所有代码都将在网站上提供（www.fudanmiccai.org）。确认本 研 究 得 到 了 国 家 自 然 科 学 基 金 项 目 （ 81471758 、 81701795 和60972102）的资助。本研究还得到了国家重点研究发展计划（2017YFC 0110700）和上海市学术/技术研究带头人计划（16 XD 1424900）的部分支持。引用1. T. Whelan ， M.Kaess ， H.Johannsson ， M.Fallon ， J.J. Leonard 和J.McDonald，第34页。598-626，2015。基于RIF匹配的全局点云配准152. P. Henry，M. Krainin，E. Herbst，X. Ren和D. Fox，“RGB-D建模：用于机 器 人 的 3D 建 模 的 U s i n g K i n e c t -styled e p t h c a m e ra s” ， IN-INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH ， vol. 31 ， pp. 647-663，2012。3. R. A. 纽科姆，S。伊扎迪河希利格斯，D。莫利诺，D。Kim，A.J. 戴维森P. Kohli，J. S. Hoddges，andA. Fitzgibon，“K i n e c t F u s i o n：R eal-T i m e De n s e S u rfa c e M a pp i n g and T ra c k i n g，”InIn 127-1364. J. Salvi，C. Matabosch，D. Fofi和J. 例如，“A review of rec e n t rang ge i m a g e regis-t ra t i o n m e t h o d s with it h a cc u r a l u a t i o n”，I MA G E AN D V I S I O N CO M P U T I N G，第25卷，第110 - 111页。578-596，2007.5. X. Xu和M. Wang，“A S u r fa c e - B a s e d S p a t i a l R e g i s t ra t i o n M e th o d B a s e d o n S e n s e T h re e -D i m e n s i o n a l S c a n e r（第28卷，第157页，2017）”，J O U R NA L O F C R A N-IOF ACIAL SURGERY，第28卷，第157页，2017）。28，第1581-1581页，2017年。6. J. Straub，T. Camp belll，J. P. How，andJ. W. I. 例如，“Efficient G lob al P o n t C loud A lig n m e n t u s in B ayes i an N o np a ra m e t r i c M ixtures”，in IEEE C o n fe re n c e on Computer Vision and Pattern Recognition，2017，pp. 2403-24127. P. J. BESL和N。D. MCKAY，“A ME T H O D FOR R E G I S T R A TIO N O F 3- D S HA PE S”，IEEE T R A N S A C T IO N S O N P A T TE R N ANA L Y S I S A N D M A C H I N E INTELLIGENCE，vol.第14页。239-256，1992.8. D. Chetverikov，D. StepanovandP. Krsek，“R 〇 bus t e u u u c I d e a n a l ig n m e t o f 3D p o i t s e t s t s：t h e r i m m e d i t e t e r i v e c l o s t p o i t a l it h m”，I M A G E AN D V I S I O N COMPUTING，vol.第23页。299-309，2005.9. B. JianandB. C. 例如，“R obus t P oi t S e t R e g i s t r t t i o n U s i n g Ga u s i n M i x t u re M o d e l s”，IEEE T R AN S A C T I O N S O N P AT T E R NA L Y S I S AN D M A C H I N E INTELLIGENCE，vol. 33，pp.1633-1645，2011。10. S. KIRKPATRICK，C. D. GELATT和M。 P. VECCHI，“O P T I M I Z AT IO N B Y S I M U L A T E D ANN E A L I N G，”S CI E N C E，第1卷。220，pp. 671 -680，1983。11. M. P. Wachowiak，R. Smolikova，Y. F.郑振明<英>香港实业家。Zurada和A.S.例如，“A napp ro a c h t o m u l t i m o d a l b imd ic a l i m a g e r g i s t a t it i n u t i i z i n g p a t i z i c l e s w a r m o p t i m i z a t i N g i c l e s”，IEEETERANSAC T IO N S O N E V O L U T IO N A R Y COMPUTATION，vol.第8页。289-301，2004.12. H. Li和R。 例如，“The 3D-3D registra tion prob le m rev i s i t ed”，在EEE国际计算机视觉会议上，2007年，pp. 1947-1954年。13. J. 是的，H。 Li，D. Campp bell，andY. Jia，“G0-ICP：AGloballyOptimalSolu-tionto3DICPoint-SetRegistration“，IBUTRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE，vol. 第38页。2241-2254，2016。14. R. I. 你好，我是F。 Ka h l，“G lo b a l O p t i m i z a t io n t h rou g h R o t a t io n S p a c e S e a r c h“，International Journal OFComputer Vision，vol.第82页64-79，2009.15. A. P. Bustos，T. Chin，A. Eriksson，H. Li和D. Suter，“FastRotationSearchwithStereroraticProjectionsfor3DRegistatin“，ICTRANSatioNSONPatternAnalysisANDMachineIntelligence，vol. 第38页。2227 -2240，2016。16. D. Camp bell，L. 佩特松湖。 Kneip和H。 Li，“Globally-Opt imal Inlier Set M ax imi s a t ion for Si mul t a n e us C am m e ra P os e and F e a t ure C o rre s p o n e e e“，在IEEE International Conference on ComputerVision，2017，pp. 1-1017. D. Camp bellandL. Peterson，“G O G M A：G l o b a lly-O p t i m a l G a us i an M i x t u re A lig n m e n t，”in I E E E C o n fe re c e o n C o m u t er V i s i n and P a t t e r n R e cogn i t i n，2016，pp. 5685-569416Y. Liu等人18. W. Lian，L. Z和M。 例如，“A n E ffi c i n t G l o b l y O p t i m a l A lgo ri t hm o r A s y m m e t r i c P o n t M a t c h i n g .，“IEEE trans a c t i o n s o n p a te r n a l y s i s a n a l y s a n a19. M. A. FISCHLER和R。 C. BOLLES，“