改变物理定律加速引力点集对齐的BH-RGA方法

20800使用改变的物理定律加速引力点集对齐 *0Vladislav Golyanik 1 Christian Theobalt 1 Didier Stricker 2 , 301 MPI for Informatics 2 University of Kaiserslautern 3 DFKI0摘要0本文描述了一种基于粒子动力学原理的Barnes-Hut刚性引力点集配准方法（BH-RGA）。我们将输入解释为两个相互作用的粒子群，直接最小化系统的引力势能，使用非线性最小二乘法。与通过求解二阶常微分方程组获得的解相比，我们的方法更加鲁棒，对参数选择的依赖性更小。我们使用Barnes-Hut树加速了其他粒子相互作用，并以准线性时间高效处理大规模点集，同时保持全局多重链接的特性。BH-RGA的优点之一是可以通过改变点的质量来定义边界条件或额外的对齐线索。系统实验证明，BH-RGA在处理不完整、噪声和扰动数据时的收敛区域和准确性方面优于基线方法。所提出的方法与先前匹配的对齐方法也有积极的比较。01. 引言0在多个领域中，不同参考框架中提供的点集对齐是一个重要的算法组成部分，包括但不限于视觉里程计[33]、3D重建和增强现实[40]、[39]、机器人导航和定位[46]、计算机图形学[48]、CAD建模[52]、文化遗产[8]和医疗技术[11]、[25]。尽管刚性点集配准是一个经过深入研究的领域[6]、[11]、[43]、[20]、[12]、[18]、[25]、[50]、[41]、[38]、[14]、[21]、[15]，但仍然存在一些挑战，其中包括更广泛的收敛区域、对样本中的干扰效应（噪声、缺失数据、聚类异常值）的鲁棒性以及处理大规模点集。我们考虑相对于固定参考框架R（可能是观察者的参考框架）的刚性对齐（RA），并且已知其中一个点集X在R中的坐标。0*受ERC Consolidator Grant4DReply（770784）和BMBF项目DYNAMICS（01IW15003）和VIDETE（01IW18002）的支持。0图1：我们的BH-RGA方法概述。在每次外部迭代中，我们同时为参考点集和模板点集计算Barnes-Hut树，并指定一个优化问题。接下来，一个非线性最小二乘求解器在几次内部迭代中运行，需要O(M logN)的时间来近似全局多重链接粒子相互作用的重力势能。0我们将X称为参考。RA的目标是恢复一个非单射、非满射的对应函数f: Y →X，以及刚性变换参数，即旋转R和平移t（6个自由度），将模板点集Y注册到X。所有RA技术可以分为局部和多重链接策略。如果每个X的点与Y的每个点都相互作用，则称RA方法为全局多重链接方法，例如最近提出的基于粒子动力学的引力方法（GA）[21]。在GA中，Y的每个点通过一个力场与X的每个点相互作用。该方法被证明对大量噪声更加鲁棒。这种鲁棒性是以二次复杂度和参数敏感性为代价的，这阻碍了它在现实世界中大规模和密集点集的适用性。此外，基于物理模拟的解决方案速度较慢且不稳定。我们相信，在基于物理的RA领域可以取得相当大的改进。在实际应用中，我们关注的是参数设置方面的快速收敛和良好性质，而不是物理上准确的建模。另一方面，迄今为止，基于粒子动力学的RA的可行加速技术尚未被探索，值得研究。0Early point set registration algorithms were motivatedby emerging 3D scanners producing partial point cloudsthat need to be aligned. The seminal iterative closest point(ICP) algorithm for aligning two point clouds [6, 11] al-ternates between transformation estimation [28, 29] and lo-cal correspondence inference [17].Even though ICP iseasy to implement, its fundamentally heuristic local corre-spondence search makes it prone to erroneous local conver-gence if badly initialised, and sensitive to outliers. Differentimprovements were subsequently proposed for ICP, rang-ing from accelerating policies for nearest neighbour search[26, 41] and relaxation of one-to-one correspondences [20]to more efficient optimisation schemes [45, 18].Another class of methods models source and target pointclouds as probability density functions [12, 38, 32], such20810早期的点集配准算法是由新兴的3D扫描仪产生的需要对齐的部分点云的动机。用于对齐两个点云的开创性迭代最近点（ICP）算法[6, 11]在变换估计[28,29]和局部对应推断[17]之间交替进行。尽管ICP易于实现，但其基本的启发式局部对应搜索使其容易在错误的局部收敛情况下初始化，并且对异常值敏感。随后提出了不同的ICP改进方法，包括最近邻搜索的加速策略[26,41]、一对一对应关系的放松[20]以及更高效的优化方案[45,18]。另一类方法将源点云和目标点云建模为概率密度函数[12, 38, 32]，例如02. 相关工作0作为高斯混合模型（GMMs）。Coherent PointDrift（CPD）[38]明确地融入了均匀噪声模型。通过高斯混合解耦[16]或将GMM表示和连续域映射与支持向量机相结合[10]，可以获得更宽的对齐收敛盆地。KernelCorrelation（KC）方法通过最小化参考系统和变换模板的Renyi二次熵来最小化联合系统的Renyi二次熵[50]。与BH-RGA相比，仅涉及到局部邻域的一对多交互。最近，一些依赖于物理过程类比的方法引起了人们的关注[14, 21,3]。Deng等人将点集转化为Schr¨odinger距离变换表示，并通过在单位Hilbert球上最小化测地距离来对齐它们[14]。Golyanik等人将点集解释为在引力力场中移动的刚性粒子群[21]。最优对齐对应于系统的最小GPE状态。GA的二次复杂性和参数敏感性限制了其实际应用。我们进一步发展了全局多重链接的思想，并通过BH树加速了全对全交互，从而实现了准线性的计算复杂性。我们改变了粒子动力学的规律，并模拟了一个逆世界。在逆世界中，可以通过NLLS迭代更容易地找到具有局部最优GPE的状态。因此，我们去除了GA中的粘性（一种能量耗散器），并且引力常数作为能量的乘法因子变得多余。在RA中，大的点集通常通过子采样[25]处理，很少使用原始数据，更不用说以全局多重链接的方式处理。一些方法自然地允许嵌入先前的匹配[6,23]。与GA类似，BH-RGA使用不同的质量来定义不同的边界条件。粒子质量可以与叠加的先前对应的可靠性成比例地设置。一些方法还使用颜色作为对齐线索[13]。在BH-RGA中，点的强度也可以映射到质量上。03.牛顿引力方法[21]0考虑两个点集的全局多重链接引力对齐，其中参考[x j] = X∈ RD×N，j ∈ {1,...,N}和模板[y i] = Y ∈ RD×M，i ∈{1,...,M}。N和M分别表示参考和模板中的点数，D是点集的维度。目标是恢复参数集ϑ = {R,t}，即将Y与X对齐的旋转R（R−1 = RT，det(R) =1）和平移t。在[21]中，通过最小化由X诱导的力场中相应粒子系统的互相引力势能（GPE）U来对齐点集：0U(R, t) = -G �0i,j0∥ R y i + t - x j ∥ 2 + �, (1))1G myi mxj∥R yi + t − xj∥2 + ǫ.20820其中m y i和m xj表示质量，G是引力常数，�是用于防止局部近场奇异性的软化参数。出于[24]中强调的原因，我们在(1)和我们的能量函数(5)和(9)中不包括缩放。Golyanik等人[21]通过更新作用在粒子y i上的力�f i，加速度（使用牛顿第二定律�f i = m y i�a i），速度v t +1 i和单个点位移d t +1i[1]来隐式地最小化(1)：0�f i = -Gm y i 0j m x j � ∥ y i − x j ∥ 2 + � 2 � − 3 / 2 ˆ n i,j− ηv t i,0v t +1 i = v i + ∆t�f i m y i and d t +1 i = ∆t v t+1 i. (3)0在(2)中，η表示耗散常数，它确定每个模板粒子从系统中带走的动能的部分。在(3)中，∆t是前向积分步长（模拟的时间间隔）。在每次迭代中，一旦更新，无约束位移将添加到当前位置。使用Procrustes分析[29]找到共识刚性变换，它将先前和当前的姿势联系起来。当两个最后连续系统状态的GPE差异低于某个小阈值ρE时，算法收敛，或者当达到最大迭代次数时终止。04.提出的方法04.1.我们的重力势能函数0GPE(1)包括一个倒数关系，并通过更新作用在模板粒子上的力、点加速度和位移的二阶常微分方程（ODE）隐式地最小化。力与距离成反比，而在最佳对齐时，GPE受到限制为-∞。为了使变换参数R和t收敛，引入了额外的正则化常数(2)，即避免近场奇异性的软化距离�，以及能量耗散常数η，实际上防止无限振荡。所有这些属性的组合（倒数关系、正则化能量耗散项、�）使得GA对于参数值来说是不适定的。因此，每种情况都需要不同的参数，否则该方法将无法收敛。隐式解决方案与二阶ODE相比的另一个缺点是需要大量的迭代才能收敛（300-1000次迭代并不罕见）。此外，R是通过Procrustes拟合对无约束点位移进行更新的。理想情况下，我们希望直接在SO(D)群中进行优化。我们建议直接优化GPE并避免通过二阶ODE的隐式解决方案。此外，我们消除了(1)的所有缺点，并减少了参数的数量，同时保留了引力方法的优点。0对齐。由于我们正在解决计算机视觉问题，并且不关心准确的物理模拟，因此我们可以自由地改变模拟物理规律，只要它使我们更接近所需的属性。考虑一个负元素逐个倒数变换算子η−(∙)，它作用于任意和或向量的每个元素c，如η−�−10c � =  c .  η − ( ∙ )保持函数的单调性并且是可逆的i。我们将η−(∙)应用于（1）并得到：0ξ − � U ( R ,  t ) � = �0i,j0（4）方程（4）改变了模拟世界的模型。在逆世界中，两个粒子之间的势能与它们的质量乘积成反比，与点之间的距离成正比。质量的含义已经改变 -现在，质量被理解为物质的属性，因此其值越小，相互作用越显著。然而，我们可以保留质量的概念，并替换10m old y i =  m new0m old x j =  m new x j .注意，软化参数�可以0由于近场奇异性消失，G被省略。此外，我们摆脱了G，因为它是能量中的全局乘法常数。因此，我们的GPE E的最终形式是ii0E(R, t) = �0i0j m y i  m x j ∥ R y i  +  t  −  x j ∥ 2  .(5)0使用新的GPE（5），当GPE在局部最小时仍然实现最佳对齐，但没有互逆性。值得注意的是，在两种情况下，即U(R,t)和ξ−�U(R, t)�，两个粒子相距越远，它们之间的GPE越高：0当∥RY + T∥F →∥X∥F U(R, t) = -∞，以及（6）0当∥RY + T∥F →∥X∥F ξ−�U(R, t)� = 0，（7）0其中∥∙∥F表示Frobenius范数，我们使用简写TD×M = � t t .. . t�。注意，（5）仍然表示全局多重链接的GPE，没有明确的对应关系编码。这两个因素揭示了变换后的GPE与经典的ICP公式[6]之间的视觉相似性。进一步的区别是，ICP需要在对应关系和变换更新之间交替，而（5）在优化过程中不会改变（未加速时）。0i互逆变换是信号处理和应用数学中广泛使用的变换之一[7]。它有几种修改，例如图像处理中的互逆楔变换[49]。ii接下来，我们简化质量的表示并省略上标new。root node (entire space)iiiiiiiviii iii iviiii iii ivii iii iviii iii ivnew elementcorresponding leafempty leafmyi mxk ∥ˆyi − xk∥2 ≈ myimxk20830ii0BH树分区空间中的点集0iii0iv i0插入0空的象限i0图2：构建BH树的示例。为了可视化目的，每个点都具有不同的形状和颜色。新元素要么位于一个未占用的叶子中，要么启动单元格分割（同时更新簇的质量和质心），直到它被放置在自己的外部叶子中。04.2. 使用Barnes-Hut 2D树进行加速0为了在计算点之间的势能时超越二次计算复杂度，我们引入了一种新的BH树或2D树的变体，该变体应用于天体动力学中N体问题的加速[5]。我们通过与我们构建的BH树中提取的O(logN)个簇的交互来近似每个模板点yi与N个参考点的穷尽交互。而以前的方法实际上将交互限制在局部邻域[50,38]，我们在我们的近似中保留了全局的多重链接。假设yi与K个足够远的粒子xk相互作用，k∈{1,...,K}，而且xk彼此足够接近。为简洁起见，我们用ˆyi = Ryi +t表示。考虑到yi到每个xk的距离的方差小于某个小的ζ。如果位于足够远的地方，空间体积V中所有元素xk对yi的总影响可以很好地近似为组合单粒子˜x的影响。˜x的质量等于V上xk的质量积分，˜x的位置等于V中xk的质心[5]：0K �0� K �0�0∥ ˆ y i  −  ˜ x ∥ 2  。(8)0构建BH树。我们在点集合X ∪Y上构建一个联合的BH树。由于模板点之间互不影响，我们将所有 m y i设置为零。这样可以将模板的所有点包含在树中，但在计算势能时排除它们对其他模板点的影响（质量）。如果X和Y包含重复的点，BH树的细分将无限继续。实际上，为了避免无限分割，BH树的深度是受限制的。BH树初始化为一个根节点和2个空的外部节点。每个新的 y i的插入总是导致一个新的叶子节点（一个被占用的外部节点），并且可以启动聚类（内部节点）。子单元的大小始终是父单元所有维度上的一半。每个 y i都会影响每个聚类的质量和质心。0其中包括 y i 。图2以示例方式展示了BH树的构建过程。我们严格遵循[5 ]中提出的插入规则。此外，请参阅我们的补充材料以获取更多细节。0使用BH树。从根节点开始遍历BH树，计算位置 y i处的势能，这需要一个距离阈值 γ。假设 l是当前检查的单元格的大小，µ 是从 y i到单元格中心的距离。如果 l / µ <  γ − 1 ，则单元格对 y i的影响是累积的。否则，访问下一级的子单元格，并递归执行检查，直到满足条件 l / µ <  γ − 1 或者完全遍历整个树[5 ]。为了获得当前 y i的非零势能，我们恢复其原始质量。计算完势能后，为了避免模板点之间的相互作用，我们再次将 m y i设置为零。节点越早使用，绕过的个体粒子-粒子相互作用越多。BH树构建对于给定的 X ∪ Y的时间和内存需求取决于点分布的均匀程度，并且有一个上限，GPE计算的速度取决于γ（参见第4.4节）。图3可视化了在单个模板点和一个clean-500实验（参见第5.1节）中注册过程中获取的聚类配置，其中 γ =5.0。输入点云每个包含817个点，从BH八叉树中获取的聚类的基数在[49;62]点的范围内。其中一些聚类是无质量的，可以从相应的配置中删除，因为它们只包含无质量的模板点。示例点的轨迹在所有迭代中都是不同的。一些远离的粒子被合并成持久存在的聚类，而其他聚类的组成在迭代过程中动态变化，而模板经历刚性变换。0使用BH树的GPE。BH-RGA与2D树加速的粒子相互作用的最终GPE如下所示。0E ( R ,  t ) =0� y i m 0k j ∈K ( y i ) m k j  ∥ R y i  +  t  −k j ∥ 2  ,  (9)0其中 k j  ∈ K ( y i ) 表示每个 y i 与聚类 k j 和质量 m k j的可获取参考的表示。04.3. 重力势能优化0提出的方法总结如下：BH-RGA通过最小化加权残差的平方和f r ( ϑ ) = m y i m k j  ∥ R y i  +  t  −  k j ∥ 22来最小化GPE( 9)。残差的数量和组成取决于BH树的配置和γ。由于最小化GPE( 9)是一个过约束的非线性优化问题，我们使用Levenberg-Marquardt (LM)算法[ 34 ,  36]以最小二乘的方式来解决它，通过在当前解附近线性化GPE进行迭代求解。234562102030>3020840初始化0对齐07（最终）0持久聚类a/b/0示例模板点0c/0图3：从BH八叉树中获取的聚类（clean-500实验，参见第5.1节）：a/开始时的聚类配置；b/所有七次迭代的叠加聚类配置。a/和b/中的颜色编码了与示例模板粒子的距离（越暗，距离越远），无质量的聚类显示为黑色；c/第一次迭代的聚类配置，用于单个模板点（以三角形表示）和三个不同的γ值。右侧给出了颜色方案。每种颜色编码了聚类的质量范围。最初，所有点都被分配了单位质量。0算法1 Barnes-Hut刚性引力法0输入：参考X∈RD×N和模板Y∈RD×M0输出：将Y对齐到X的刚性变换ϑ={R，t}1：初始化：R=I，t=0；质量myi和mxj，从2D树中获取聚类的距离阈值γ 2：当未收敛时执行 3：在点集{X，RY +T}上构建2D树，TD×M=�tt...t�04：对于每个模板点yi执行5：从2D树中获取一组聚类K(yi) 6：结束7：最小化（9），即GPE E(R，t)=�0kj∈K(yi)mkj∥Ryi+t−kj∥�，使用非线性最小二乘法8：结束0为了对异常值具有更高的抗性，在评估每个fr（ϑ）时，我们应用Huber损失，定义为：0∥a∥ε=0� 1 2 a 2，如果| a | ≤ εε（| a | − 1）02ε），否则。（10）0在每次成功的∆ϑ更新后，BH树都会更新，并且在每次外部迭代中为新的fr（ϑ）集合制定目标。内部LM迭代的次数保持在[3;10]的范围内，参见图1。当两个连续的GPE值之间的差异低于某个阈值ρE时，BH-RGA收敛。04.4.计算复杂度0在每次迭代中，为联合{X，Y}构建BH树的时间复杂度为O（（M + N）log（M +N））。从参考点中获取一组聚类的复杂度为O（logN）。总体而言，这个操作对所有M个模板点执行，我们得到O（M logN）。因此，BH-RGA的计算复杂度为O（（M +N）log（M + N）+ M log N）≈ O（M logN）（假设M�N）。与GA[21]的二次复杂度相比，这是一个显着的改进，特别是对于大型点集。04.5.使用质量定义边界条件0在BH-RGA中设置模板点和参考点的不同质量可以实现不同的效果，例如嵌入先前的对应关系，提供额外的线索和平衡不均匀的点密度。0稀疏先前匹配。在BH-RGA中，不同的质量可以将先前的对应关系编码为最优对齐，当具有较大质量的点彼此靠近时，最优对齐更有可能发生。假设（i，j）∈Nc�N2是预先已知对应关系的点集。考虑到先前的匹配，BH-RGA的GPE可以表示为：0Ep（R，t）=0�E(R，t)如（9），�yi：i∈Nc，mpyi∥Ryi+t−xj∥2，否则，（11）0对于在Nc中的点，我们避免了多重链接和聚类获取。我们将锚点定义为X和Y的两个子集，已知它们彼此对应。通过将锚点的质量设置为mp，可以将锚点嵌入到BH-RGA中，而不会对（9）中的内容进行更改。因此，锚点在BH-RGA中的作用更接近于对齐或层次注册中的对齐。0点颜色。在BH-RGA中，可以将额外的对齐线索（如点颜色）转换为质量。在这种情况下，为了使GPE在局部最小值，具有相似质量的点必须重合或接近。0处理不同点密度。处理具有不均匀密度的点集被认为对许多方法具有挑战性，需要专门的技术和预处理步骤（如重新采样）来高效处理这种情况[30]。对于BH-RGA，我们提出在线性时间内对单位体积的总点质量进行归一化。在体积质量归一化（VMN）中，点集的边界框被分割成多个不重叠的体素，在每个体素中，预定义的质量均匀分布在属于该体素的所有点之间。208505.实验0在本节中，我们描述了评估方法和结果。BH-RGA是用C++实现的，使用了eigen3 [27]和Galois[42]库。对于NLLS，我们使用ceres solver[2]。实验在一台配有32 Gb RAM和四核Inteli7-6700K处理器（主频4GHz）的系统上进行。我们将我们的BH-RGA与迭代最近点（ICP）[6]、LM-ICP[18]、连贯点漂移（CPD）[38]、GMM注册（GMR）[32]和GA[21]进行比较。CPD和GMR分别作为6自由度（R，t）和7自由度（R，t和s）的变体进行评估。我们还将BH-RGA与由先前匹配引导的刚性扩展CPD（E-CPD）进行比较[23]。ICP来自Matlab仓库[51]，几种方法的实现是公开可用的[37，31，35]。在所有实验中，我们报告均方根误差（RMSE）的平均值和标准差，标记为σ。05.1.定量评估0主要测试。在使用合成数据进行测试时，我们使用了一个子采样的Stanford兔子[47]。在第一个clean-500测试中，我们通过2π的角位移对3D旋转空间进行采样。010弧度，并合成500个不同的初始配置（避免重复状态）。在这个实验中，我们测试方法在无噪声数据情况下解决旋转的能力。相反，第二个测试旨在评估RA在严重噪声下的收敛能力。我们在clean-500上添加了100%的均匀噪声，得到N500-U100数据集。噪声生成函数的范围是模板的边界球体。一些方法在N500-U100上表现不佳，我们还根据相同规则生成了N500-U50数据集，其中有50%的均匀噪声。接下来，我们选择一个可以被所有方法成功解决的单个初始配置，并向模板添加三种不同的噪声模式-100%的均匀噪声，100%的高斯噪声（范围体积与N500-U100相同），以及均值与模板点位置重合的100%的高斯噪声。生成的数据集分别缩写为100U、100G和100GS。表1总结了使用新数据集的实验结果。如果RMSE低于0.1，则认为注册成功。这个值不是随意设置的-在成功对齐的情况下，RMSE在大多数情况下要远远低于0.1。否则，在大多数情况下，它要比0.1大得多。符合我们的预期，BH-RGA在clean-500数据集上不是最准确的方法（在成功率方面是第二好的）。然而，完全匹配的数据在实际应用中并不常见。随着噪声的增加，BH-RGA相对于所有其他方法的相对准确性和性能增加。虽然CPD（7自由度）的RMSE低于BH-RGA，但在N500-U100上。0在clean-500测试中，N500-U50和N500-U100的情况发生了反转，BH-RGA的成功率接近于CPD（并且与CPD相比具有最低的RMSE）。同时，ICP、LM-ICP、CPD（6自由度）和GMR在N500-U50和N500-U100上的成功率显著降低。BH-RGA是唯一在U100上成功的方法，它解决了所有情况并具有最低的RMSE。第二好的方法是CPD（7自由度，48个案例中的50个），在N500-U100和U100上的RMSE分别比BH-RGA高50%到66%。GMR只能在6自由度模式下与ICP/LM-ICP持平。在G100和GS100上，除了GMR（6自由度）和GA只能恢复52%、25%、2%和20%的变换外，大多数方法都能成功恢复所有情况的变换。在我们的测试中，基线GA[21]的性能在大多数情况下都不如其他方法的结果。我们的实验设置与[21]中提出的设置不同，在那里初始错配角度是在[0; π]范围内随机选择的。02]。Golyanik等人[21]报告，GA在角度不匹配范围[π02]。在我们的clean-500和N500-实验中，角度采用36°步长进行采样，这意味着从第二个值开始（十个值中的第二个值），角度始终≥72°。对于U100，G100和GS100，过多的噪声阻碍了GA的收敛，尽管初始不匹配角度在GA的收敛盆地中。0扰动数据。接下来，我们提出了一种用于评估方法对受损数据的鲁棒性的测试——U256和G256实验。我们用均匀噪声和高斯噪声扰动模板点。总共有256个幅度索引，生成具有不断增加的扰动程度的状态。每个状态中的最大位移等于缩放的幅度索引乘以物体在x方向上的边界框的长度。在这两个实验中，模板的任何点都不与最优解的任何参考点物理上重合。在表2中报告了参考点和通过恢复的R，t变换的模板之间的RMSE。CPD和GMR的RMSE比ICP和BH-RGA高，即概率方法对点扰动敏感，这与我们的预期一致。ICP显示出最低的RMSE。特别是对于小的扰动，ICP的条件是最佳的。BH-RGA在小的扰动幅度下略微不及ICP，因为其RMSE稍高。另一方面，BH-RGA具有最小的σ。0先前匹配和锚点。我们使用最多三个先前匹配和锚点重复进行N500-U50测试，并将BH-RGA与扩展CPD（E-CPD）[23]进行比较，见表3的总结。后一种方法是一种条件化的对应关系CPD变体。特别是在只有一个或两个可靠的先前匹配的情况下，E-CPD具有优势[23]。因此，没有先前匹配的CPD解决了17%的情况，其成功率增加到18%和75%20860表1：对clean-500，N500-U50，N500-U100，U100，G100和GS100数据集进行比较方法的定量评估总结。0方法和指标clean-500 N500-U50 N500-U100 U100 G100 GS1000ICP [ 6 ] 成功率（%）62（12.4%）36（7.2%）19（3.8%）33（66%）50 50 50（100% 100% 100%）50 50 50（100% 100%100%）RMSE（σ）0.005（0.016）0.022（0.3）0.042（0.031）0.091（0.081）0.007 0.007 0.007（0.002 0.002 0.002）0.002 0.002 0.002（5E5E5E-444）0LM-ICP [ 18 ] 成功率（%）123（24.6%）82（16.4%）72（14.4%）49（98%）50 50 50（100% 100% 100%）50 50 50（100% 100%100%）RMSE（σ）0.002（6.3E-4）0.015（0.009）0.023（0.017）0.025（0.021）0.006 0.006 0.006（0.003 0.003 0.003）0.003 0.003 0.003（0.001 0.001 0.001）0CPD (7 DoF) [ 38 ] 成功率（%）130（26%）128 128 128（25.6% 25.6% 25.6%）109 109 109（21.8% 21.8% 21.8%）48（96%）50 50 50（100% 100% 100%）50 50 50（100% 100%100%）RMSE（σ）0.04（6E-5）0.064 0.064 0.064（0.003 0.003 0.003）0.088 0.088 0.088（0.003 0.003 0.003）0.098（0.066）0.027 0.027 0.027（1.7E1.7E1.7E-333）0.046 0.046 0.046（1.7E1.7E1.7E-333）0CPD (6 DoF) [ 38 ] 成功率（%）143 143 143（28.6% 28.6% 28.6%）98（19.6%）62（12.4%）48（96%）50 50 50（100% 100% 100%）50 50 50（100% 100% 100%）RMSE（σ）0.0060.006 0.006（0.009 0.009 0.009）0.025（0.014）0.034（0.017）0.061（0.148）0.01 0.01 0.01（0.003 0.003 0.003）7.5E7.5E7.5E-333（2.3E2.3E2.3E-333）0GMR (7 DoF) [ 32 ] 成功率（%）126（25.2%）113（22.6%）0（0%）0（0%）50 50 50（100% 100% 100%）50 50 50（100% 100%100%）RMSE（σ）7E-5（8E-5）0.084（0.005）n/a n/a 0.04 0.04 0.04（7.5E7.5E7.5E-333）1.5E1.5E1.5E-333（4.7E4.7E4.7E-444）0GMR（6自由度）[32]成功率（%）131（26.2%）79（15.8%）87（17.4%）36（72%）26（52%）25（25%）RMSE（σ）8E-5（2E-4）5E-4（2E-4）6E-4（2E-4）0.16（0.077）0.37（0.4）0.37（0.38）0GA [21]成功率（%）21（4.2%）6（1.2%）3（0.6%）19（38%）1（2%）10（20%）RMSE（σ）0.029（0.021）0.049（0.025）0.03（0.012）0.164（0.082）0.289（0.087）0.163（0.072）0BH-RGA（我们的方法）成功率（%）132（26.4%）132 132 132（26.4% 26.4% 26.4%）100 100 100（20% 20% 20%）50 50 50（100% 100% 100%）50 50 50（100% 100% 100%）50 50 50（100% 100%100%）RMSE（σ）0.009（0.004）0.032 0.032 0.032（0.013 0.013 0.013）0.059 0.059 0.059（0.021 0.021 0.021）0.056 0.056 0.056（0.017 0.017 0.017）0.04 0.04 0.04（0.01 0.01 0.01）0.022 0.022 0.022（0.006 0.006 0.006）0表2：U256和G256实验中的RMSE和σ（括号中）0方法 U256 G2560ICP [6] 9E9E9E-333（7E7E7E-333）0.015 0.015 0.015（0.012 0.0120.012）LM-ICP [18]0.077（0.041）0.113（0.063）CPD（7自由度）[38]0.051（9E-3）0.064（0.021）CPD（6自由度）[38]0.016（0.014）0.045（0.058）GMR（7自由度）[32]0.019（0.028）0.065（0.051）GMR（6自由度）[32]0.853（1.16）1.027（1.226）GA [21]0.149（0.143）0.207（0.158）BH-RGA（我们的方法）0.015 0.0150.015（4E4E4E-333）0.019 0.019 0.019（9.5E9.5E9.5E-333）0表3：E-CPD [23]和BH-RGA的比较。0评估的配置RMSE σ案例（成功率）0E-CPD[23]，仅使用先验匹配0[无先验 0.08 0.013 85（17%）] 1个先验 0.084 0.01289（18%） 2个先验 0.076 0.014 376（75%） 3个先验0.056 0.018 488（97%）0BH-RGA（我们的方法），锚点0[无先验 0.05 0.018 124（25%）] 1个先验 0.043 0.013199（40%） 2个先验 0.011 0.017 191（38%） 3个先验0.0086 0.005 165（33%）0BH-RGA（我们的方法），先验匹配01个先验 0.0191 1.1E-4 435（87%） 2个先验 0.00551.72E-5 500（100%） 3个先验 0.0001 4.5E-9500（100%）0分别使用一个和两个先验匹配。BH-RGA解决了25%的无先验情况，解决了约39%的一个或两个可用锚点情况。请注意，锚点具有较高的质量并与所有其他点相互作用，这是三个锚点成功率下降到33%的原因。相比之下，BH-RGA解决了所有具有两个或三个先验对应的情况，并且优于E-CPD。先验匹配不参与与其他点的相互作用，这是最强的边界条件。0运行时间和收敛性。我们评估了BH-RGA在不同大小和不同阈值γ的输入上的运行时间。对于BH树的每个近似级别，我们报告了实现的准确性和运行时间等。0我们以SINTELsleeping2序列[9]中的一帧作为参考，以其平移和旋转的克隆作为模板。平移大致相当于点云在x方向上的三分之一，旋转分别为5°或24°。总共有七个点云版本通过子采样获得，其基数分别为约5k、12k、25k、50k、105k、205k和446k（原始分辨率）。对于每个分辨率和模板变换的组合，我们测试γ∈[0.0625; 64.0]。运行时间评估指标0对于5个旋转，结果如图4所示，即运行时间（完整和每次迭代）、BH树生成的运行时间比例、RMSE和残差数量。运行时间统计中可以观察到几种模式。当γ固定时，不同点数的RMSE相似。相反，随着γ的增加，所有分辨率的对齐精度增加，构建BH树的运行时间比例越来越小，而不受点数的影响。对于γ >2.0，BH树的运行时间比例≤0.5%。相比之下，求解器的运行时间比例始终约为80%，表明在GPU上使用高斯-牛顿求解器可以实现最多五倍的加速。接下来，随着γ的增加，迭代次数减少并稳定。对于γ ≥ 6，迭代次数≤4。对于γ =6.0和446k个点，平均残差数量（点到聚类的相互作用数量）达到约1.8E7。对于24°旋转的情况，图形指标粗略地遵循5°旋转的图形指标的形状。更大的不对齐需要更大的γ才能成功注册，并且总体运行时间增加了两倍（请注意，在此实验中，我们不执行平移预对齐）。每次迭代的运行时间增加约40%，γ ≥ 6的迭代次数增加了一到两次。20870图4：不同运行时间评估指标与BH树阈值γ的函数图（SINTELsleeping2序列[9]，不同的子采样率和点云中的点数）。在底部一行，我们展示了根据[22]和使用的Middlebury光流编码[4]恢复的重投影位移，用于第7帧和第29帧。0研究表明，BH-RGA可以在11秒内注册两个每个点集有446k个点的点集，RMSE为0.068（γ=0.25）。对于RMSE为0.0065的点集，需要264秒（γ=3.0）。对于具有25k个点的点集，相似的RMSE为0.0067，耗时41秒（γ=12.0）。BH-RGA以可接受的时间以全局多重链接方式注册大型点集，而经过测试的竞争方法的实现无法处理这些数据。CPD论文[38]报告了使用加速技术对每个具有≈35k个点的两个点集进行10分钟的注册。BH-RGA在γ=0.25的情况下只需要约1秒钟。05.2. 使用真实世界数据进行评估0BH-RGA非常适合注册真实世界的数据，包括大型部分重叠的点集和激光雷达测量。图5包含了几个这样的场景。Vestalin和pedestal数据集代表使用结构光技术获取的雕像的部分3D重建[44]。由