SDRSAC：基于半确定性的随机点云无对应鲁棒配准算法

1i=1j=1SDRSAC：基于半确定性的随机点云无对应鲁棒胡米Le1、Thanh-Toan Do2、3、Tuan Hoang1和Ngai-Man Cheung11新加坡科技与设计大学2利物浦大学3AIOZ Pte Ltd摘要本文提出了一种新的鲁棒的点云配准随机算法，没有对应关系。这两个点集可能很小，导致大量的异常值，即，非重叠点。因此，需要以稳健的方式进行注册，以便最终估计不受污染的影响大多数现有的注册方法需要一组PU-形式上，令S={si∈R3}Ns且D={dj∈R3}Nd通过提取不变量de-编剧然而，这种描述符在嘈杂和污染的环境中可能变得不可靠。在这些设置中，直接处理输入点集的方法是优选的。然而，如果没有对应关系，传统的随机-表示源和目标（目标）点云，因此，鲁棒刚性配准的问题可以公式化为ΣNs离子化技术需要非常大量的样品以达到令人满意的解决方案。在本文中，我们提出-minR∈SO（3），t∈R3i=1ρ（Rsi+t-dj），（1）提出了一种新的方法来解决这个问题。特别是，我们的工作使得能够使用随机方法进行点云配准，而不需要假定的对应关系。通过将点云对齐视为图匹配的一种特殊情况，并采用一种有效的半定松弛算法，提出了一种新的采样机制，使得采样子集的大小可以大于最小值。我们的紧松弛方案能够快速拒绝抽样集中的离群值，从而产生高质量的假设。我们进行了广泛的实验，以证明我们的方法优于其他国家的最先进的方法。重要的是，我们提出的方法作为一个通用的框架，可以扩展到其中，符号dj·t表示d2范数，dj是目标集合D中最接近变换点Rsi+ t的点，即，dj= arg min <$Rsi+t-dk<$，（2）dk∈D并且ρ是鲁棒损失函数。这里，SO（3）表示旋转矩阵的空间。为了使配准是鲁棒的，ρ通常选自一组鲁棒核[27，1，33]。在这项工作中，我们使用了流行的最大一致性准则[26]，其中ρ定义为.如果x≤0，已知的对应问题。1ρ（x）=（三）1否则。1. 介绍点云配准在许多计算机视觉应用中是重要的，包括范围扫描对准[37]、3D对象识别和定位[18，48]、大规模重建[2，44]。给定三维欧氏空间中的两个点集，目标是寻找最优刚性变换，该变换包括旋转矩阵R∈SO（3）和平移向量t∈R3，使两个输入点集最优对齐.在许多实际应用中，输入数据包含大量的噪声。此外，重叠区域在1源代码可在https://github.com/intellhave/SDRSAC上获得。阈值λ>0是用户定义的参数，其指定将被视为内点的对应对的最大允许距离直观地说，通过求解（1），ρ定义为（3），我们搜索最大化重叠点集的最佳对齐（R，t），其中如果变换（R，t）将si带到位于球（dj，d j）内的新位置，则si ∈ S与d j ∈D重叠。问题（1）由于其计算复杂性而在计算机视觉中是活跃的研究主题许多现有的算法需要将一组的假定对应，这通常是获得（作为预处理步骤）通过提取局部不变特征的给定点集，并执行多个routines的最近邻搜索，以提出初始的关键。124125点匹配[5，25]。 几种类型的三维局部有限元分析-Tures [45，15，52，43]已证明在各种具有挑战性的数据集中提供了有然而，噪声和污染会降低提取特征的质量.此外，为了精确计算局部特征，许多特征提取器要求表面表示是密集的;然而，稀疏点云在实践中是常见的。特别是，在[4]中已经证明，对于具有高比例离群值的噪声数据集，与使用原始数据相比，使用特征的比对具有较差的结果。因此，有兴趣开发直接对齐原始点云数据而不需要先验对应关系的配准算法[11，4，9，36，21]。由于不同输入设置下问题的计算复杂性，随机假设与验证算法（如RANSAC [22]及其变体[17，16，47，46，42，32]）是流行的方法。随机技术已被用来解决已知对应的问题。另一方面，类似于RANSAC的随机抽样策略也可以应用于无对应的问题具体地，在每次迭代时，可以对每个点云上的最小子集（三个点）进行采样以形成三对对应关系，这三对对应关系用于估计和验证一个假设。然后可以重复这样的过程，直到获得满意的解决方案。然而，在噪声和离群值的情况下，挑选无离群值子集的可能性迅速下降。因此，已经做出了很多努力来开发更好的采样策略，特别是[4]中提出的4点同余集（4PCS）方法及其改进变体[38]。尽管4PCS提供了比传统随机方法更大的优势，但在处理具有大量点和高离群值率的点云时，该算法的（近似）全等集的枚举是主要问题。事实上，对于密集的点云，4PCS及其变体需要在进行采样过程之前对点云进行下采样以减少处理时间。在本文中，我们解决了上述限制。具体来说，通过采用一个特殊的图匹配公式的情况下，我们提出了一个新的大于最小采样策略的点云配准没有对应。我们的方法的优点是，搜索对应的任务是快速近似，imated通过解决一个放松的凸问题，而不是子集枚举。这使得我们可以采样任意大的子集，其中的对应集是从凸半定规划的解中得到的。然后，这些对应关系可以用于估计和验证假设。源点云中的大的点子集更好地表示其结构，并且通过识别其在目标集中的对应点，可以更快地粗略对准两个点云，然后可以通过局部方法，例如，ICP [8]。实验结果表明，该方法是非常有竞争力的。我们的主要贡献是：• 我们应用图匹配的配准问题，没有对应关系，使用一种新的成本函数，以加强鲁棒性和紧半定（SDP）松弛。• 从SDP制定，然后我们开发了一个新的大于最小子集抽样方案，导致一个有效的随机算法，优于其他国家的最先进的方法。2. 相关工作在实践中，如果两个输入点云粗略对齐，则通常采用众所周知的迭代最近点（ICP）[8]。与其他迭代算法一样，ICP在建立对应关系和估计变换之间交替。该方法的主要缺点在于它需要良好的起始点（初始姿态）以防止其自身收敛到差的对准。此外，在鲁棒性方面，ICP具有与最小二乘估计相同的弱点，即，它很容易被错误的异常值所偏置。已经提出了几项工作[13，7，40]来改善ICP的这些缺点。然而，这些变体仍然需要通过下降初始姿势来引导。因此，ICP通常用作局部细化过程，其在点云通过某种类型的全局对准算法粗略地配准之后执行。提供全局最优解的算法也在文献中积极开发。为了解决ICP的初始化依赖问题，Go-ICP [50]采用分支定界策略在R空间中搜索而t是最优变换。但由于Go-ICP的最小二乘目标，其返回的最优so-解对于离群值仍然是不鲁棒的。Go-ICP的鲁棒性可以通过引入鲁棒损失函数来代替最小二乘法来提高另一种全局最优的算法是由Buffett等人提出的，用于解决无对应性的鲁棒配准问题。[11]第10段。与Go-ICP不同，[11]直接求解（1），其解对离群值具有鲁棒性。分支定界也是后面的机制[11]，具有用于快速匹配查询和更严格的定界计算的新颖立体投影实现。虽然这些方法保证了全局最优解的收敛，但由于其昂贵的计算成本，它们对于大型数据集仍然是不切实际的。如前所述，在某些点云配准应用中，随机化策略（具有著名的RANSAC [22]代表性）仍然是主要方法。我们的工作也属于这一类。Gener-126i=1j=1PQ：，1：，N总之，对于大多数随机化方法，基本的对于没有对应关系的情况，甚至更难，因为需要识别两个无离群值的子集，每个输入点云中有一个，并且这两个子集中的元素必须形成正确的对应关系。文献中提出了不同的采样策略[17，16，49]。例如，在具有已知对应性的问题中，RANSAC的显著改进之一是LO-RANSAC（局部最优RANSAC）[17]，其提出在RANSAC解更新时对大于最小值的子集这种改进的策略已被证明是显着优于传统的RANSAC。随机方法也可以使用局部细化技术进行改进[31，12，41]。然而，在没有对应关系的鲁棒点云对齐的背景下，大于最小采样的想法还有待于彻底探索。与已知对应的情况不同，在每次RANSAC迭代处的“内点”集合可能不是真正的内点，并且纯粹地将LO-RANSAC应用于这些子集可能没有任何帮助，而运行时间增加。此外，即使真正的内点位于子集中，大于最小值的子集也可能被离群值污染，这可能会使估计恶化，因为它仅通过对采样子集求解最小二乘来完成从上面讨论的观点本文对这一思想进行了分析，提出了一种新的算法，该算法能够对任意大的子集进行采样。这种采样方案与一个预言机相结合，允许有效地丢弃采样点集中的离群值。我们的实验表明，这种新提出的al-出租m优于以前的方法。我们的工作与4PCS [3]密切相关，这是最先进的采样方法，也解决了与我们相同的代替随机挑选三个点的最小该方法后来由Su-per 4PCS [38]改进，其中同余集提取的复杂性相对于点的数量从二次降低到线性。虽然高效，特别是在[38]中引入的改进，但4PCS仍然具有与RANSAC相同的弱点，例如，在存在高异常值的情况下快速挑选出正确子集的可能性低事实上，对于每个4个共面点这项工作中开发的技术也受到了使用图匹配[21，35，34]和最近半定方法解决3D配准问题的方法的启发。非刚性配准的松弛[19，28，30]。然而，这些算法只能对少量数据点起作用，如果直接应用于大型点云，则效率非常低。另一方面，我们建议将图匹配作为子问题嵌入到随机采样框架中。这允许我们结合两类方法的优点，即，随机化技术和图形匹配，以导出用于点云配准的有效采样机制。3. 基于半确定性的随机方法3.1. 匹配问题当没有给出假定的对应时，求解（1）的任务可以被视为联合估计变换（R，t）和对应的最佳子集C。因此，如果提供了C，则可以以直接的方式计算最佳对准，反之亦然。考虑到这一点，在本节中，我们首先介绍了寻找C的对应问题。在后面的部分中，我们讨论了它的半定（SDP）松弛，它可以作为一个快速的假设生成机制，是我们的有效的随机算法的核心为了简化公式，现在让我们假设我们被给定两个3D点集P={pi}N和Q={pi} N。{qj}N，每个包含N个数据点。 任务是找到最优对应集C可用于鲁棒地对齐P和Q。请注意，与（1）相比，我们在这里对输入数据使用了不同的符号，因为这个新问题将被用作求解（1）的子问题，这将在后面的章节中阐明。设X∈ {0，1}N×N是置换矩阵，其中第i行第j列的元素（记为Xi，j）被赋值为1，如果pi∈ P和qj∈ P属于对应集，否则赋值为0为了解释离群值，让我们进一步假设最优解包含m≤N对对应。m的值可以选择为大于或等于3（最小子集的大小），或者基于手头问题的已知离群值比率进行估计请注意，与m的引入，X现在是子置换矩阵。用X表示通过堆叠其列获得的矩阵X的向量化在一个点云上，4PCS需要枚举另一个点云上的所有一致子集因此，这种方法X=[XT不*，2. . .XT[T]，（4）需要在进行采样之前将点集子采样为更小的子集其中X：，j表示X的第j-列。为了搜索最佳对应分配，请考虑X127以下优化问题：设计的基础上，如果pa∈ P对应于qb∈ Q和pc∈ P对应于qd∈ Q，因为MaxXXTAX，（5a）变换是刚性的，两条线段的长度设Xi，j∈ {0，1} ∈i，j∈ {1，. . .，N}，（5b）ΣNXi，j≤1 <$i∈ {1，. . .，N}，（5c）j=1ΣNXi，j≤1 <$j∈ {1，. . .，N}，（5d）i=1papc和qbqd必须近似相同（由于噪音的影响）。对于新公式（6），我们只允许长度相差较小值γ的线段对被视为匹配候选，而拒绝具有较大间隙的线段对，而不是将匹配势分配给A的所有元素。3.2. 半定松弛ΣN ΣNXi，j=m，（5e）让我们先考虑（5）的等价公式设Y=X<$X<$T∈RN2×N2，问题（5）变为i=1j =1其中A∈RN2×N2是表征点（线）对间匹配势MaxX为oh迹线（AY），（7a）在P和Q中。特别地，我们将矩阵A的元素定义为：.服从Y=X<$X<$T，（7b）迹线（Y）=m，（7c）0≤Xi，j≤1i，j，（7d）Aab，cd=f（pa，pc，qb，qd）如果|δ（pa，pc）− δ（qb，qd）|≤ γ，否则，（六）（5c）、（5d）、（5e）。（7e）注意，在（7）中，可以去除约束（5b）而不影响等式（7）和（5）之间的等式。的确，其中a，b，c，d ∈ {1. N}是点索引，ab = a+（b-1）N和cd=c+（d−1）N是行的索引由于trace（Y）=m，它必须保持i，2i、j=m。对另一方面，由于约束（5e），i，jXi，j=m。和A列;pa，pc∈ P; qb，qd∈ Q;γ>0是预定义阈值，δ（p1，p2）计算Σ这些条件导致i、j2i、jΣ=i，j Xi，j. 还有，两个3D点p1和p2之间的欧几里得距离;f是将两对点（pa，pc）和（qb，qd）作为输入并输出表示这两对的匹配潜力的标量通常，（6）中的f被选择为惩罚两个线段之间的长度差的函数 为了简单起见，我们选择f为exp（−|δ（pa，pc）− δ（qb，qd）|）的情况。（5）中的约束是为了确保X必须位于置换矩阵空间具体来说，除了XX128由于条件0≤Xi，j≤1，Xi，j只能是ei-1。0或1。换句话说，X现在可以被约束在子置换矩阵的凸包中[39]。通过引入Y，将问题提升到RN2×N2的区域中，放松了X的二元约束，而不改变问题的解然而，在这方面，由于秩一约束（7b），问题（7）仍然是非凸的为了近似（7），我们采用常见的凸松弛方法，其中（7b）被重新构造。二进制约束（5b）限制Xi、j{0，1}，它也la x ed到半定约束Y−X<$X<$T≥0。然后，要求每个点pi∈ P只能被分配给Q中的至多一个点，反之亦然，这反映在我们得到下面的凸优化问题：约束（5c）和（5d）。最后，通过执行（5e），操作-MaxX为oh迹线（AY），（8a）（5）的最小解将仅包含m对对应的子。dences. （5）的解提供了最优分配，使得从对应对获得的匹配潜力的总和最大化。虽然已经在几个刚性和非刚性配准问题中探索了图匹配的使用[21，35，30，28]，但大多数以前的工作考虑解决整个输入数据的图匹配，这对于大型数据集是不可行的。本文提出了一种基于极小点集的图匹配算法，并将其嵌入到随机采样框架中。此外，我们还提出了一个更好的公式矩阵A的特殊情况下，强大的刚性配准。特别地，矩阵A是在Y-X<$X<$T≥0的条件下，（8b）(5c)、（5 d）、（5 e）、（7c）、（7 d）。（8c）上面介绍的问题（8）是凸半定规划（SDP），其全局最优解可以使用许多现成的SDP求解器来获得。在这项工作中，我们在所有实验中使用SDPNAL+ [51]。3.2.1收紧放松由于（8）被求解为具有秩一约束的（7）的近似，因此可以预期两个解为：129AB尽可能接近。受[30]的启发，我们将以下约束添加到（8）以收紧松弛：如果a=c，b/=d，具有最高分数的被选作（5）的近似解。在我们的整个实验中，这种方法已经被经验证明是非常有效的。Yab，cd≤0，如果b=d，ac，（九）3.4.主要算法n（X，X），否则，CD算法1SDRSAC（9）背后的直觉是S中的一个点不是al-降低到与D中的多个点匹配，反之亦然。此外，由于Yab，cd=XabXcd，并且这些是二进制数，因此必须保持Yab，cd≤min（Xab，Xcd）。此外，由于鲁棒寄存器的特殊情况，（8）可以进一步加强。观察到，基于公式化矩阵A的讨论，可以强制执行以下约束：要求：输入数据S和D，最大值，内部值，采样子集的大小N样本1：iter←0;最佳得分← 0;2：whileitermax iterdo<3： S′ ←从S中随机抽取N个样本点4： 对于t=1到内部iters，5：D′ ←从D随机采样N个采样Yab，cd =0，如果Aab，cd=0，（10）6：{M，R，t} ← SDR匹配（S，D，S′，D′）/* 在Alg中描述2 */这意味着如果对papc和pbpd在长度上相差太多（大于γ），则我们直接不允许它们匹配。最后，加上（9）和（10），我们的SDP松弛变为：7：如果|M|>最佳成绩8：最佳成绩←| M|; R<$R;t<$t9：如果结束10：结束11：iter←iter+inner iters12：T←满足proba的迭代次数MaxX为oh痕量（AY）（11a）bilistic停止标准（第二节）3.5）13：如果iter≥T，则受第（8b）、（7c）、（7d）、（8c）、（9）、（10）（11b）项限制注意，（11）仍然是凸SDP，因为附加约束（9）和（10）是线性的。3.3. 置换矩阵解的投影14：返回15：如果结束16：结束while十七： return最佳转换（R，t），最佳得分在使用一个控制器求解（11）直到其全局最优性vex求解器，剩下的任务是将其解投影回置换矩阵的空间。这一任务可以通过不同的策略来完成[23]。在这项工作中，我们应用线性分配问题[10]，其中投影可以通过求解线性规划（LP）来有效地计算具体地说，设X是（11）的最优解。的LP对于投影，可以用公式表示为算法2SDR匹配要求：输入数据S和D，采样子集S′和D′，阈值λ。1：使用等式1生成的←矩阵（6）P=S′，Q= D′2：X←Sol v e（11），其中A由步骤1生成。3：X←Solv e（12），其中X从步骤2获得。4：M ′ ← {（s′∈ S ′，d′∈ D ′）|Xi，j= 1}I jMaxXX，XΣ Σ5：（R，t）←基于对应集M ′的估计变换[20，29].0≤Xi，j≤1Xi，j=1，Xi，j=1I j（十二）其中，n·，·n表示两个矩阵的内积。（12）的解为我们提供了一组N个对应。然而，在（5）中，我们只想挑选m对。为了用一个简单的启发式来解决这个问题，观察在（5）的最优解X中，只有m行/列的X包含值1，而其余的行/列包含全零。因此，根据从（12）获得的对应集合，我们将每对对应（pi，qj），其得分等于Xi，j。最后，y，m对130226：（R，t）←使用ICP的细化，由（R，t）初始化7：M ← {（si∈ S，dj∈ D）|Rsi+ t-d j<$<$ ≤ < $}/*dj 在（2）中定义 */8：返回M，R，t虽然（11）是凸的，但由于提升变量Y属于RN×N的域，所以对于N的大值求解它是低效的。然而，对于较小的N值（通常，N≤20），该问题可以有效地优化，并且（11）为原始问题（7）提供了良好的近似。利用这一观察，可以131我我开发一种采样方法，其中每个样本中的点的数量可以是任何大小，直到所采用的求解器可以有效处理的极限（11）。更具体地，在每次迭代中，分别从S和D随机采样点S′ = S和D′ = D的两个子集。S′和D′的基数可以根据所采用的凸解算器的能力来控制。通过求解（11），可以拒绝采样子集中的离群值，并且保留每个样本中的最佳子集以用于估计变换。像其他随机化范例一样，这个过程可以在固定次数的迭代之后重复，或者直到满足停止标准。该策略的启示在于，通过在每次迭代时对大子集进行采样，更有可能遇到包含内点的正确子集，因为如果任何采样子集被污染，则可以通过求解第3.1节中讨论的SDP近似来有效地拒绝离群值算法1总结了我们的方法。3.5. 停止标准我们遵循[4]推导出我们的停止准则。让我们用pi表示选择一个内点（正确对应对）的概率，用T表示试验次数。请注意，从统计数据[24]来看，最优算法，我们还将SDRSAC与Go-ICP [50]及其具有修剪的鲁棒版本（TrGoICP）进行了比较。请注意，传统的RANSAC方法[22]对于这种类型的问题表现不佳，并且在许多情况下，它变成了蛮力类型的算法。因此，为了节省空间，我们只显示上面列出的已建立方法的结果。当我们专注于验证鲁棒全局配准的有效性时，在整个实验中，我们测量并报告每种方法的匹配数量（目标函数所有的实验都是在一个16GB RAM的标准Ubuntu机器 上执 行的 。SDRSAC 、ICP 、 TrimmedICP 均 使用MATLAB实现。对于4PCS，Su-per 4PCS [38]，Go-ICP [50]，我们使用发布的C++代码以及作者建议的参数。 通过对20次不同运行所得结果取平均值报告随机化方法的所有结果。在下文中，我们仅报告具有代表性的结果。更多的结果，实施细节和扩展的情况下，与已知的对应关系，可以在补充材料中找到。4.1. 合成数据我们首先评估的性能SDRSAC上的synn- thetically生成的数据。来自样本量N样品也是pI。 此外，在运行斯坦福数据集2被加载并均匀采样，Alg. 2，只剩下m对对应，允许我们基于m计算停止准则。表示算法在T次试验后未能找到全内点对应集的概率，pf=（1−pm）T，（13）因此，为了使成功概率大于ps，我们必须使迭代次数大于T≥log（1 −p s）。（十四）log（1−pm）由于实际的内点率pi事先未知，因此遵循几种随机化方法的常见做法，我们在采样过程中更新该值，即，使用当前迄今为止最佳解的内围值比率迭代地更新Pl4. 实验结果为了评估我们提出的算法（SDRSAC）的性能，我们对多组合成和真实数据集进行了实验，并将我们的方法与几种可用于解决无对应点云配准的最先进算法进行了比较，包括ICP [8]，Trimmed ICP（TrICP）[13]、迭代再加权最小二乘（IRLS）[6]、4PCS [4]及其改进的Super4PCS [38]。在全球包含Ns= 10，000个点的源点云S。到生成目标集合D，我们对S应用随机变换（R，Rt）。然后，D中的每个点被零均值的高斯噪声和σ噪声= 0的方差扰动。01.为了模拟部分重叠，我们随机选取并重新移动D中r%的点. 为了评估算法在不同离群值比率下的性能，我们重复了r = 10，15，. . . ，50%。将 阈 值 （ 3 ） 选 择 为 0 。 01 所 有 的 方 法 对 于SDRSAC，我们选择样本大小为N 样本= 16，m=4。(TheN 样 本 和 m 的 选 择 将 在 第 二 节 中 进 行 研 究 。4.3）。 图1显示了匹配（内点）和所有方法的运行时间。 很明显，SDRSAC在以更快（或相当）的激发时间获得的对应性方面优于其他方法。请注意，SDRSAC的运行时间非常接近Super4PCS，尽管SDRSAC始终获得更高的解决方案质量。如预期的，ICP的性能由于初始化的影响（即，错误的初始化可能导致收敛性差），如图所示。1.此外，随着离群值比率的增加，大多数基于ICP的方法产生的共识4.2. 真实数据在本节中，我们将评估我们提出的方法在真实数据集上的性能，并将其与现有的方法进行2http://graphics.stanford.edu/data/3Dscanrep/132图1.合成数据实验结果。左：对应的数量（（1）的目的）。右：运行时间（对数刻度）。对SDRSAC4PCSS-4PCSICPTrICPIRLSGoICPTrGoICP1，2校正次数时间（s）69908.69592211.18638810.0524334.6944554.3524293.16266450.9682833.42018年8月9日校正次数时间（s）43539.53418415.08290115.0621324.4412054.4521254.06225363.2410138.315，16校正次数时间（s）49927.56495415.95493315.456554.354874.636734.19151360.3141337.61951年，52校正次数时间（s）449010.05299815.45371415.03604.296124.551784.3955460.584838.5生活1，2校正次数时间（s）58178.34560215.09459015.3936094.2645994.9640165.13406032.5565535.6Living1生活25，26校正次数时间（s）47689.27361515.07432715.9513504.3413644.4242404.35439865.3456736.1Living生活54，55校正次数时间（s）55589.2515515.05543315.6541044.2947834.3240095.19512061.2525035.9Living1生活32，33校正次数时间（s）55708.32545915.15326915.2320284.6515194.4428085.1233434.6531933.3表1.真实数据实验的结果。对于每个对，第一行是对应的数量（#Corrs），第二行显示运行时间（秒）。请注意，S-4PCS代表Super 4PCS。方法。本实验的输入点云来自具有挑战性的Redwood3D数据集[14]。我们从Of-133ObjectiveandLivingRoomrepository 中 随 机 选 取 8 对 点云，然后对点集进行统一采样，以在每个输入集上获得10，000个点将输入阈值Rmin（3）选择为在0的范围内。01到0。05，对于每组输入数据，选择所有基准测试方法相同的SNR图2.使用SDRSAC的比对示例。从上到下：8号办公室和9号办公室;1号客厅和2号客厅表1显示了每个方法的匹配数和运行时间。样品定性结果见图2。可以看出，平均而言，SDRSAC与其他竞争者相比获得更高的匹配。我们还观察到，局部方法，如ICP或IRLS有时可以快速收敛到非常好的结果，但不稳定，由于不良的初始化的影响。健壮版本TrGo-ICP的性能略好于Go-ICP，但134N16在某些情况下，由于输入数据中存在高的离群值比率4.3. 消融研究本节分析了不同参数设置对我们提出的方法性能的影响，并建议了超参数的选择。4.3.1样本量N样本的影响图3.不同N样本值的性能分析。左：共识大小，中：迭代次数，右：运行时间。图3绘制了准确度（一致性大小），迭代次数（以满足停止标准（14）），以及当N 样本从8增加到18且m=4时合成数据集的4.1)其中N=10，000且p<30%（绘制的结果是20次运行的中值）。所得结果与统计理论[24]一致。 具体来说，在亚-N个样本的集合。点具有pI和标准de vi的平均值停止标准（14））。观察到在不同的m值下性能相当稳定，这证明了SDP拒绝离群值的有效性和我们提出的抽样方案的优势。在图4（右）中，我们还绘制了直到终止所需的运行时间。显然，尽管不同m值的解质量与上述相似，但运行时间受以下因素的影响M. 具体地，随着m的增加，SDRSAC在满足停止准则（14 ）之前进行更多的迭代这可以通过回忆（13）式来解释，大的m增加了失效概率pf。此外，对于任何采样子集，内点的预期数量为Nsample×pI，因此如果m大于该值，则可能包括离群点。在我们的实验中，m=4的选择在大多数sce中效果最好narios（m=3的最小情况可能不是很稳定由于3D数据点中的噪声和3个对应关系，可以在空间上彼此靠近）。图4.不同m值下的共识大小（左）和运行时间（右）图。（SD）pI（1−pI）。从图3、我们观察到，样品小的N个样本（N个样本16），获得的一致性大小低，并且算法需要大量的迭代。<特别地，如果N样本很小，则在采样子集中，内点率的SD很大，因此一些子集可能被大量的离群值污染，这影 响了 质 量 和稳 定性。我们的算法。 当N样本达到16左右时，SD为0。三块钱。七块钱。1，因此内点率在子集之间仅略有变化，从而导致稳定的性能，如图所示3（左，中）。虽然从统计学的角度来看，使用大N样本是好的，但SDP求解器在每次迭代时对于大N样本将花费更多时间，从而导致更长的总运行时间，如图所示。3（右）。根据经验，我们发现N样本=16在算法稳定性（AC，curacy）和运行时间。4.3.2m的影响进行该实验以研究m（在第2节中介绍）的影响。3.1）对解决方案的质量和运行时间我们的方法。我们对每个点云包含N=5，000个点的合成数据集重复实验，其中10%为离群值。样本大小N样本设置为16。所有结果均以20次运行的中位数获得。图4（左）绘制了终止时获得的内点数量（使用5. 结论提出了一种新的、有效的随机点云配准方法。我们应用图匹配公式的对应问题。我们提出了一个新的成本函数和一个紧SDP松弛计划。我们将公式嵌入到一个新的采样策略中，该策略对大于最小子集的样本进行采样。在多个人工数据集和真实数据集上的大量实验表明，该算法具有较好的竞争力。我们的框架也可以扩展到已知对应的问题。确认这项工作得到了ST Electronics和新加坡总理办公室国家研究基金会（NRF）在Corporate Laboratory @ Uni-versity Scheme下的部分支持（项目名称：STEE Infosec-SUTD Corporate Laboratory）。引用[1] Khurrum Aftab和Richard Hartley。迭代重加权最小二乘对稳健m-估计的收敛性。在计算机视觉应用（WACV）中，2015年IEEE冬季会议，第480-487页。IEEE，2015年。135[2] Sameer Agarwal、Yasutaka Furukawa、Noah Snavely、Ian Si-mon 、 Brian Curless 、 Steven M Seitz 和 RichardSzeliski。一天建成罗马。Communications of the ACM，54（10）：105[3] Sameer Agarwal，Noah Snavely，and Steven M Seitz.多视图几何l问题的快速算法。计算机视觉和模式识别，2008年。CVPR 2008。IEEE会议，第1-8页。IEEE，2008年。[4] Dror Aiger，Niloy J Mitra，and Daniel Cohen-Or. 4-点全等集合，用于稳健的成对表面配准。ACMTransactionson Graphics（TOG），第27卷，第85页。ACM，2008年。[5] Aitor Alberti，Zoltan-Csaba Marton，Federico Tombari，Walter Wohlkinger，Christian Potthast，Bernhard Zeisl，Radu Bogdan Rusu，Suat Gedikli，and Markus Bogzze.教程：点云库：三维物体识别和6自由度姿态估计。IEEE Robotics Automation Magazine，19（3）：80[6] PerBe r gst romandO v eEdlund. 用迭代重加权最小二乘法重建点计算优化和应用，58（3）：543[7] PerBe r gst romandO v eEdlund. RO必须使用改进的迭代最近点算法和信赖域方法对表面进行重建数值算法，74（3）：755[8] Paul J Besl和Neil D McKay。三维形状配准方法。在Sensor Fusion IV 中 ： Control Paradigms and DataStructures，第1611卷，第586-607页。国际光学与光子学学会，1992年。[9] 托马斯M布鲁尔。几何分支定界匹配方法的实现技术计算机视觉与图像理解，90（3）：258[10] Rainer E Burkard和Eranda Cela。线性分配问题及其推广。在组合优化手册中，第75-149页。施普林格，1999年。[11] A'lv aroParraBustos，Tat-JunChin，AndersEriksson，Hong-dong Li，and David Suter.用于三维配准的快速立体投影旋转 搜索 。IEEE Transactions on Pattern Analysis andMachine Intelligence，38（11）：2227[12] Zhipeng Cai，Tat-Jun Chin，Huu Le，and David Suter.双凸规划的确定性一致最大化在欧洲计算机视觉会议（ECCV）的会议记录中，第685-700页[13] Dmitry Chetverikov，Dmitry Svirko，Dmitry Stepanov，and Pavel Krsek.裁剪迭代最近点算法。模式识别，2002年。诉讼第16届国际会议，第3卷，第545-548页。IEEE，2002年。[14] Sungjoon Choi，Qian-Yi Zhou，and Vladlen Koltun.室内场 景 的 鲁 棒 重 建 在 Computer Vision and PatternRecognition（CVPR），2015 IEEE Conference on，第5556-5565页中IEEE，2015年。[15] Chin Seng Chua和Ray Jarvis点签名：一种新的三维物体识别表示方法。国际计算机视觉杂志，25（1）：63[16] Ondrej Chum和Jiri Matas。与prosac匹配-渐进样本共识。在2005年IEEE计算机计算机视觉和图案识别的国际会议（CVPR'05），第1卷，第220-226页。IEEE，2005年。[17] Ondˇrej Chum、Jiˇr´ı Matas和Josef Kittler。局部优化的ransac。在DAGM。施普林格，2003年。[18] Bertram Drost Markus Ulrich Nassir Navab 和 SlobodanIlic。全局建模，局部匹配：高效而稳健的三维物体识别。在计算机视觉和模式识别（CVPR），2010 IEEE会议，第998IEEE，2010年。[19] Nadav Dym ， Haggai Maron ， and Yaron Lipman.DS++：一个灵活的，可扩展的，可证明的紧松弛匹配问 题 。 ACM Transactions on Graphics （ TOG ） ， 36（6）：184，2017。[20] David W Eggert，Adele Lorusso，and Robert B Fisher.估计三维刚体变换：四种主要算法的比较机器视觉与应用，9（5- 6）：272[21] Olof Enqvist，Klas Josephson，and Fredrik Kahl.成对约束的最优对应。在计算机视觉，2009年IEEE第12届国际会议上，第1295-1302页。IEEE，2009年。[22] Martin A Fischler和Robert C Bolles。随机样本一致性：一个范例模型拟合与应用程序的图像分析和自动制图。Communications of the ACM，24（6）：381[23] Fajwel Fogel ， Rodolphe Jenatton ， Francis Bach ， andAlexan- dre置换问题的凸松弛。神经信息处理系统进展，第1016-1024页，2013年[24] 大卫·福赛斯。计算机科学中的概率与统计。Springer，2018.[25] 兰·加尔和丹尼尔·科恩-奥尔部分形状匹配和相似性的显著几何特征ACM Transactions on Graphics（TOG），25（1）：130[26] Richard Hartley和Andrew Zisserman。计算机视觉中的多视几何学。剑桥大学出版社，2003年。[27] Peter J Huber等.一种定位参数的鲁棒估计。数学统计年鉴，35（1）：73-101，1964年。[28] M Hullin，R Klein，T Schultz和A Yao。二次分配问题的有效提升松弛。2017年。[29] Wolfgang Kabsch求两组向量的最佳旋转关系的一种方法。晶体学报A部分：晶体物理，衍射，理论与普通晶体学，32（5）：922 -923，1976.[30] Itay Kezurer ， Shahar Z Kovalsky ， Ronen Basri ， andYaron Li