可证明的点云配准算法

Ibrahim Jubran1, Alaa Maalouf1, Ron Kimmel2, Dan Feldman11University of Haifa, 2Technion{ibrahim.jub, alaamalouf12, dannyf.post}@gmail.com{ron}@cs.technion.ac.il1132690可证明的点云配准0摘要0对齐问题的目标是将给定的点云 � = { � 1 ,  ∙ ∙ ∙  , � � }对齐到另一个观察到的点云 � = { � 1 ,  ∙ ∙ ∙  , � � }。也就是说，计算一个旋转矩阵 � ∈ R 3 × 3和一个平移向量 � ∈ R 3 ，使得每个变换后的点 �� �  −  �到其对应点 � � 的距离之和最小，其中 � ∈ { 1 ,  ∙ ∙ ∙  , � }。更困难的版本是配准问题，其中对应关系是未知的，并且最小值也是对所有可能的对应函数从 � 到 �的情况下取的。诸如迭代最近点（ICP）及其变种的算法被提出用于解决这些问题，但没有一个能够给出全局最优解的可证明的非平凡近似。我们证明，� × �中总是存在一个“证人”集合，通过新的对齐算法，它对这个全局最优解提供了一个常数因子的近似（在最坏情况下）。然后，我们提供了在 �中恢复这个证人集合并在多项式时间内得到第一个可证明的常数因子近似的算法：（i）对齐问题的期望时间，（ii）配准问题的多项式时间。这样的小证人集合存在于许多变体中，包括 �维空间中的点，抗离群值的成本函数以及不同的对应类型。对真实和合成数据集的大量实验结果表明，实际上我们的近似常数接近 1 ，我们的误差比最先进的算法小了多达 x 10倍。01. 引言0考虑已知的汽车上的一组3D地标 �，以及通过外部3D相机当前观察到的相同3D地标的一组 �，比如几秒钟后。假设我们希望计算新汽车相对于其起始点的位置和方向。这可以通过恢复将 � 对齐到 �的刚性变换（旋转和平移）来推断出来。在这个对齐问题中，我们假设每个点的对应关系（匹配）已知。0图1：使用Armadillo模型进行配准可视化，其中 � = 1000个点，20% 是离群值。（左）ICP（ �, � ），（中）P-ICP（ �,�,  cost , � ），（右）P-ICP-Refined（ �, �, �,  cost ）。 cost是具有阈值M-estimator和 � = 3000的SSD；参见第3.2节。0每个点 � 到 �的对应关系已知。当这种匹配是未知的并且需要计算时，问题被称为配准问题。它是计算机视觉中的一个基本问题[33,28, 40, 47]，在机器人[27, 37,13]和自动驾驶[51]中有许多应用。0对齐。在对齐问题中，输入由两个有序集合 � = { � 1 ,  ∙ ∙ ∙  , � �} 和 � = { � 1 ,  ∙ ∙ ∙  , � � } 组成，其中 � = 3是前面应用中的维度，目标是最小化 � ∑�0对于每个对齐（刚性变换）（ �, � ），其中包括一个旋转矩阵� ∈ R � × � （行列式为 1 的正交矩阵）和一个平移向量 � ∈ R �，其中 � ( �, � ) =  ‖ �  −  � ‖ 是一对点 �, � ∈ R � 之间的欧氏（ ℓ 2）距离。这里，求和是在每个点 � � ∈ � 到其对应点 � � ∈ �之间的距离上进行的。这种对应关系可以使用一些辅助信息获得，例如点描述符，如SIFT [25]，点的视觉跟踪[36,44]，或预定义的形状和特征[32,39]。据我们所知，对于其变体，唯一可证明的对最优全局最小值的近似是将 � ( �, � ) 替换为 ℓ ( � ( �, � )) =  ‖ �  −  � ‖ 2，即平方欧氏距离。在这种特殊情况下，最优解Table 1: Example contributions. Variants of the problems (1)–(3) that we approximate in this paper, either using: (i) Theo-rem 3 (known correspondence), or (ii) Theorem 5 (unknown correspondence). Let 𝑃 = 𝑝1,, 𝑝𝑛 and 𝑄 = 𝑞1,, 𝑞𝑛Sum of distances ⋆‖𝑣‖1𝑥‖𝑝 − 𝑞‖2Sum of squared distances ⋆‖𝑣‖1𝑥2‖𝑝 − 𝑞‖2Sum of distances withnoisy data using M-estimators‖𝑣‖1min {𝑥, 𝑇}‖𝑝 − 𝑞‖2Sum of ℓ𝑧 distances to thepower of 𝑟 ⋆‖𝑣‖1𝑥𝑟‖𝑝 − 𝑞‖𝑧Sum of the 𝑛 − 𝑘smallest entries of 𝑣𝑥𝑟‖𝑝 − 𝑞‖𝑧𝑖∈𝑆⊂{1,··,|𝑆|=𝑛−𝑘1327002 | . 形式上，我们希望最小化cost(�, �, (�, �)) = �(ℓ(�(��1 − �, �1)), ∙ ∙ ∙ , ℓ(�(��� − �, ��)))，其中�：R�×R� → [0, ∞)，ℓ：[0, ∞) → [0, ∞)和�：R� →[0, ∞)，如定义2所示。带有�标记的行也可以使用定理4在线性时间内以很高的概率和更大的近似因子进行近似。0用例�(�)ℓ(�)�(�, �)优化问题cost(�, �, (�, �))0近似因子0匹配�输入是否必要？0∑� � � =1 �� �� � − � − ��(�) ��(1 + √02）� 不是的0∑� � � =1 �� �� � − � − ��(�) �� 2(1 + √02）2 � 不是的0∑� � � =1 min{��� �� � − � − ��(�) �� , 0(1 + √02）� 不是的0∑� � � =1 �� �� � − � − ��(�) �� �� ��(1 + 02）�� 不是的0ℓ�距离的�次幂的和，其中� ≥1个异常值0∑�0�� �� � − � − ��(�) �� �� ��(1 + √02）�� 是的0是唯一且易于计算的：�只是连接�和�的两个质心的向量，� ∈ R�×�0可以使用奇异值分解[14]计算，如[22]中所述。在存在异常值的情况下，已经有很长一系列的工作来处理这个问题；例如，参见[6，52，49]。其中许多工作都是RANSAC类型的算法[12]。本文提供了第一个可靠的非平凡近似算法来解决（1），同时还处理了更广泛的函数范围。0配准问题。配准问题不假设�和�之间的对应关系已知，也就是说，我们不知道�中的哪个点与�� ∈�匹配。因此，除了刚性运动外，还需要仅基于给定的两个点云提取对应关系，从而导致一个更复杂的问题，具有大量局部最小值；参见图1。形式上，它旨在最小化0� =1 ℓ(��(�� � − �, ��(�)))�，(2)0对于每个对齐（�，�）和对应函数�：{1，...，�} →{1，...，�}；参见最近的调查[41]。这里，ℓ的一个自然选择是ℓ(�) =�2。这里假设�的大小为�，仅仅是为了简单起见，但可以是任何不同的大小。与（1）不同，我们不知道（2）的可靠近似，即使对于ℓ(�) =�2也是如此。这个问题的最常用解决方案，无论是在学术界还是在工业界，都是迭代最近点（ICP）启发式算法[4]。我们的主要贡献是ICP的一个可靠替代方法，它近似求解这个更难的问题的全局最优解。0更复杂的成本函数。在处理真实世界的数据时，噪声和异常值是不可避免的。因此，可以考虑使用替代的成本函数，而不是上述的平方距离和（SSD），因为它对这种情况非常敏感。0损坏的输入。一个更自然的更一般的成本函数可以选择例如，ℓ(�) = ��，对于� > 0，当� ∈ (0,1]时，它对噪声更具鲁棒性。或者，为了处理异常值，一个更合适的函数可以是ℓ(�) = min{�, �}，其中� >0，或者常见的Tuckey或Huber损失，或者任何其他鲁棒统计函数[17]。为了完全忽略这些（未知的）某些配对数据的错误子集，我们可以考虑解决0min(�,0� ∈ � �{1，∙∙∙，�}，|�| = � − �ℓ(��(�� � − �, ��(�)))�，(3)0其中 � ≤ �是要忽略的异常值的数量。本文提出了一个通用的框架，用于可靠地近似求解对齐和配准问题的全局最小值，包括公式（1）-（3）。01.1. 相关工作0在(2)中解决配准问题的最常见方法是ICP算法[7, 4]，其中 ℓ(�) = �2。ICP是一种局部优化技术，它在解决对应问题和刚性对齐问题之间交替进行，直到收敛。多年来，已经提出了许多ICP算法的变体；详见[38]中的调查和相关文献。然而，如果没有适当初始化，这些方法通常只能收敛到局部最小值，而不是全局最小值。估计最大化方法。为了克服ICP的局限性，已经提出了概率方法，利用GMMs，将一个点集视为GMM的质心，将另一个点集视为数据点[18, 46, 8, 26, 29, 16,5]。这类方法还包括广泛使用的Coh- erent Point Drift(CPD)方法[31]。基于学习的方法。学习专门的特征可以提高输出对齐[45]。在[3]中，将深度学习模型与已知的Lukas &Kanade算法的修改版本相结合。最近，在[15]中提出了一种无监督的基于深度学习的方法。几何和替代方法。一些工作，例如[1, 34, 2]，利用计算几何技术设计了解决方案。[1,34]还提供了可证明的保证。其他结果使用分支和界限方案来计算全局最小值[35, 10,50]。工作[30]使用智能索引数据组织来解决问题。一些结果使用傅里叶域[28]，并使用核密度估计的相关性[42]。然而，上述方法在输入规模增加时的扩展性较差。常见限制。前面提到的方法具有类似的特性，要么(i)仅支持简单的平方距离函数或 � =3，(ii)由于初始化不良而收敛到局部最小值，(iii)仅在配准流程的子任务上给出最优性保证，并且缺乏相对于配准问题的全局最优解的这种保证，(iv)它们的收敛时间不切实际或取决于数据本身，或者(v)需要大量的训练数据。据我们所知，尚未提出可证明的近似算法来解决(2)，即使对于 ℓ(�) =�。Coresets。一些工作建议将输入点云压缩为具有可证明压缩误差上界的小子集。现有的低效算法因此可以运行得更快。[32]提出了一种无误差的压缩方法用于对齐问题；在[20]中有更多示例。虽然我们的方法受到开发coresets时使用的近似技术的启发，但我们的论文提出了一个“证人集”，而不是coreset。132710与已知的Lukas &Kanade算法的修改版本相结合。最近，在[15]中提出了一种无监督的基于深度学习的方法。几何和替代方法。一些工作，例如[1, 34, 2]，利用计算几何技术设计了解决方案。[1,34]还提供了可证明的保证。其他结果使用分支和界限方案来计算全局最小值[35, 10,50]。工作[30]使用智能索引数据组织来解决问题。一些结果使用傅里叶域[28]，并使用核密度估计的相关性[42]。然而，上述方法在输入规模增加时的扩展性较差。常见限制。前面提到的方法具有类似的特性，要么(i)仅支持简单的平方距离函数或 � =3，(ii)由于初始化不良而收敛到局部最小值，(iii)仅在配准流程的子任务上给出最优性保证，并且缺乏相对于配准问题的全局最优解的这种保证，(iv)它们的收敛时间不切实际或取决于数据本身，或者(v)需要大量的训练数据。据我们所知，尚未提出可证明的近似算法来解决(2)，即使对于 ℓ(�) =�。Coresets。一些工作建议将输入点云压缩为具有可证明压缩误差上界的小子集。现有的低效算法因此可以运行得更快。[32]提出了一种无误差的压缩方法用于对齐问题；在[20]中有更多示例。虽然我们的方法受到开发coresets时使用的近似技术的启发，但我们的论文提出了一个“证人集”，而不是coreset。01.2. 我们的贡献0(i)一种新颖的对齐算法，给定�中的一组特定的�个点和�中对应的�个点，我们称之为证人集，可以得到一个可证明的常数近似。我们还证明了R�中的每一对输入点云都可以为对齐和配准问题的所有版本提供这样的证人集，包括问题(1)-(3)；详见定理1。0(ii)RANSAC风格的算法用于恢复对齐和配准问题以及其变体，例如(1)-(3)。在合成和真实数据集上进行了大量实验，证明了我们建议的算法的有效性和准确性，与现有方法相比；详见第3节。结果表明，实际上获得的近似因子要比理论预测的因子小得多。我们为我们的算法提供了完整的开源代码[21]。0(iii)正式证明，运行我们建议的算法多项式次数的迭代可以得到对齐和配准问题的可证明的常数近似。0图 2：（左）：两个对应的点集 � （蓝色）和 �（红色），其中 � 1 和 � 1 是所有配对中距离最小的。（右）：将 � 平移 � = � 1 − � 1 （即， � 1 现在与 � 1相交）。根据三角不等式，每个距离 ‖ � � − � − � � ‖（绿线）最多是 2 ∙ ‖ � � − � � ‖ （蓝线）。0图 3：（左上）：两个对应的点集 � （蓝色）和 � （红色）。（右上）：旋转 � ，使得某个 � 1 ∈ � 与其对应的 � 1 ∈ �对齐。 （左下）：将旋转后的集合 � 和集合 � 投影到与 � 1正交的平面上。 （右下）：旋转投影的 �，使得其中一个点与其对应的点从 �对齐。注意，初始对齐的一对点 ( � 1 , � 1 )不受后续步骤的影响。0包括距离的幂次和 M-估计的求和问题；参见定理 3 和 5，表 1 和算法 2 和 4 。0（iv）一种概率线性时间算法用于解决对齐问题，还支持例如M-估计的求和；参见算法 3 和定理 4 。01.3. 新技术：证明集0现在我们介绍我们的新技术。我们首先假设 � 和 �之间的对应关系已知。然后我们推广到未知对应关系的情况。我们的主要技术结果是对于每个对应的有序点集 � = { � 1 , ∙∙ ∙ , � � } ， � = { � 1 , ∙ ∙ ∙ , � � } � R �，每个满足一些属性的成本函数 cost （参见定义 2），以及每个可能的对齐 ( � * , � * ) ，都存在 �的一个子集和一个子集(ii) Similarly, we prove there is a corresponding pair of points𝑝′𝑃 ′, 𝑞𝑄 such that aligning their direction vectors via2.1. Existence of a Witness Set132720对于 � 的子集，其大小等于维度 �，我们称之为证明集。使用这些子集，我们的算法可以确定一个近似于 ( � * , � * ) 成本的对齐 ( � ′ , � ′ ) ，即 cost( �, �,  (′ )) ≤ � ∙ cost( �, �,  ( � * , � * )) ，其中 � > 0是一个小常数。这里，cost为每对输入点集和对齐分配一个非负值，而 ( � * , � * )可能是全局最优（未知）对齐。仅供分析目的，我们假设 ( �* , � * ) 在之前已知。该证明假设点云的初始位置已经应用了( � * , � * ) 到 �。然后，它应用一系列步骤来改变这个初始对齐 ( � * , � * )，直到获得一个不同的对齐 ( � ′ , � ′ ) ，其中来自 � 和 �的（证明）点集满足足够数量的已知约束，使得在给定这个证明集的情况下可以恢复 ( � ′ , � ′ )。该系列中的每一步都保证近似于其前一步的成本。因此，(� ′ , � ′ ) 的成本近似于 ( � * , � * )的初始（最优）成本。步骤如下：0（i）考虑将最优（未知）对齐 ( � * , � * ) 应用于 � 后得到的集合 � 。现在，考虑 � ′ 中的单个对应点对 � ′ = � * � − � * ∈ � ′ 和 � ∈，它们之间的距离 ‖ � ′ − � ‖是所有匹配对中最小的。使用三角不等式，可以证明将集合 � ′平移 � ′ − � （即，使得 � ′ 现在与 �相交）不会使其他点对的成对距离增加超过一个乘法因子 2；参见图 2 。因此，我们证明了存在一个平移 � ′ 的 � ′，其中某个 � ∈ � 与其对应的 � ∈ �相交，并且成本比初始最优成本增加的最多是一个常数因子。现在，假设 � ′ 和 � 位于原点。0‖ � ‖ ，将不会使其他点对的成对距离增加超过一个小因子。�′ 和 � 是夹角最小的一对。0(iii)我们可以按照以下方式迭代地重复步骤(ii)：找到这样一对(�′,�)，对齐它们的方向向量，将这两组点投影到与�的方向向量正交的超平面上，并重复最多�-2次。这样的投影确保下一个未揭示的旋转将保持(�′,�)的对齐；参见图3。每个这样的步骤都证明了存在另一对对应的点，这些点对�′至少提供了1个约束，而且不会使成本增加超过一个常数因子。因此，存在�-1对点，它们唯一确定了我们的近似旋转�′。我们将上述步骤中的�(未知)对称为证据集。给定一个证据集，可以恢复近似对齐(�′,�′)。0恢复这样一个证据集需要从�中恢复�个点（其中�是�的维数），这对于我们来说是困难的。0在已知对应关系的情况下，从�中找到�个对应的点。当对应关系未知时，唯一的区别是我们需要从�中恢复�个点以及从�中恢复�个独立点；参见定理5。02.可证明的近似0我们现在证明了上述对齐和注册问题及其变体的证据集的存在性。然后，我们提出了针对每个问题恢复这样一个证据集的算法。由于篇幅有限，我们的所有证明都放在了补充材料中。符号表示。我们用[�]={1,∙∙∙,�}表示任何整数�≥1。我们假设每个向量都是列向量。令SO(�)表示R�中所有旋转矩阵的集合。对于�∈R�和�∈SO(�)，对(�,�)称为对齐。我们定义ALIGNMENTS(�)为所有可能的�维对齐的并集。对应函数(或匹配函数)�是一个简单的函数�:[�]→[�]。对于对应函数�和有序集合�={�1,∙∙∙,��}，我们定义�[�]={���(1),∙∙∙,��(�)}�为从�重新排序其元素得到的新的有序集合，根据�。0在接下来的内容中，我们介绍了我们的主要对齐算法和主要技术结果；请参见算法1和定理1。定理1证明了存在某个证据集，当将其插入算法1中时，可以产生具有一些可证明保证的对齐结果。算法1的概述。算法1的输入是两个集合{�1,∙∙∙,��}和{�1,∙∙∙,��}，它们属于R�，并且实现了第1.3节中描述的方案。在第1行，我们将两个集合进行平移，使得��和��在原点相交。在第4行，我们计算一个旋转矩阵�，将�1和�1的方向对齐。在第5-6行，我们计算一个正交矩阵�，其列空间跨越与�−1正交的(�-1)维子空间�，并将��2,∙∙∙,���,�2,∙∙∙,��投影到�上，并重复�-1次。因此，在第�次迭代中，我们计算一个旋转�，将��的方向对齐（经过�-1次旋转和投影）和��（经过�-1次投影），同时保持先前对齐的对�1,�1,∙∙∙,��−1,��−1的对齐。这样的矩阵存在，因为��,∙∙∙,��,��,∙∙∙,��是与�1,∙∙∙,��−1,�1,∙∙∙,��−1正交的；参见图3。我们输出一个对齐结果，复制上述步骤的组合。定理1的概述。考虑�={�1,∙∙∙,��}和�={�1,∙∙∙,��}，以及对齐或注册问题的任何变体，例如(1)-(3)。现在，假设(�*,�*)和�*分别是所需任务的全局最优对齐和对应函数。注意，在对齐问题中，�*作为输入给定。定理1证明了存在一组�个点的集合ation matrix that satisfies𝑆𝑝𝑧‖𝑝𝑧‖ =5𝑊 :=𝑊cost(𝑃, 𝑄, (𝑅, 𝑡))= 𝑓 (ℓ (𝐷 (𝑅𝑝1 − 𝑡, 𝑞1)) , · · · , ℓ (𝐷 (𝑅𝑝𝑛 − 𝑡, 𝑞𝑛))) .Theorem 3. Let 𝑃 and 𝑄 be two ordered sets of 𝑛 points132730算法1：A LIGN ( { � 1 , ∙ ∙ ∙ , � � } , { � 1 , ∙ ∙ ∙ , � � } )0输入：两个在 R � 中各自跨越 � - 1维子空间的点集。输出：一个对齐 ( �, � )；参见定理101 � � := � � - � � 以及 � � := � � - � � ，对于每个 � ∈ [ � 02 � := R � 中的单位矩阵03 对于每个 � ∈ [ � - 1]做如下操作0‖ � � ‖ ，且 �� � = � � ，对于每个 � ∈ [ � -0‖ � � ‖ ]� ∈ R � × � 形成 R � 的一组基。06 � � := �� � �� � 以及 � � := �� � � � ，对于每个 � ∈ [ 07 � � := �� �08 � := ��09 � := �� � - � �010 返回 ( �, � )0从 � 和 � 中选择 �个点，当它们被插入到算法1中时，会产生一个对齐 ( �, � )，它保证：�� �� � - � - � � * ( � ) �� ≤ � ∙ �� � * � � - � * - � � * ( � ) �� ，对于所有 �∈ [ � ]0对于某个小的 � ≥ 1。对于 � = 3，常数 � <15。换句话说，使用 ( �, � ) 我们可以逼近最优对齐 ( � * , � * )的每个 � 成对距离。在配准问题中，� *可以在之后通过最近邻算法恢复。因此，定理1成功地将恢复对齐和恢复对应函数的两个问题解耦。0定理1（证明集合）。令 � = { � 1 , ∙ ∙ ∙ , � � } 和 � = { � 1 , ∙ ∙ ∙ 分别为 R � 中的两个有序点集，每个点集包含 �个点。那么，对于每个对齐 ( � * , � * ) 和匹配函数 � * ，存在 �′ � � 和 � ′ � � ，使得 | � ′ | = | � ′ | = � ，使得调用 A LIGN ( 到算法1的输出 ( �, � ) 满足对于每个 � ∈ [ � ] ：�� �� � - � -(1 + √02）� ∙ �� � * � �  -  � *  -  � � 0此外，( �, � ) 的计算时间为 � ( � 3 ) 。0在第2.2节中，我们证明了像定理1中那样逐个逼近成对距离意味着对于广泛范围的成本函数可以立即进行逼近。虽然定理1保证至少存在一个这样的证明集合，但我们在实践中观察到 � 和 �的许多子集都可以作为良好的证明集合，因为它们产生的逼近因子小于定理中预测的因子。这些因子通常甚至接近于1。因此，在第2.3-2.4节中，我们应用RANSAC类型的算法来恢复一个证明集合。定理1还暗示了0运行建议的算法足够多次可以保证对所涉及问题的全局最优解进行常数因子逼近。02.2. 泛化0接下来，我们定义了一类广泛的成本函数，包括 ( 1 )–( 3 )中的成本函数。然后我们展示了定理1中获得的逼近保证足以逼近每个这样的成本函数；参见表1中的示例。在接下来的内容中，对于 � >0，�-对数Lipschitz函数是一种函数，在每个维度上可能很大，但不能增长得太快（增长速率取决于 �）；参见附录中B节的正式定义。0定义2（成本函数）。令 � = { � 1 , ∙ ∙ ∙ , � � } �  R �0并且 � = { � 1 , ∙ ∙ ∙ , � � } �  R � 。令 � : R � × R � → [0 , ∞ )为一个函数，为 R � 中每对点分配非负权重， ℓ : [0 , ∞ ) →[0 , ∞ ) 为一个 � -log-Lipschitz函数，� : [0 , ∞ ) � → [0 , ∞ )为一个 � -log-Lipschitz函数。令 ( �, � )为一个对齐。我们定义0从成对距离到复杂成本函数。[19]中的观察5（见附录中的第B节）指出，为了近似给定的成本函数（相对于全局最优对齐和对应关系 ( � * , � * )  和  � * ），同时近似每对成对距离�� � * � �  −  � *  −  � � * ( � ) ��  对于每个  �  ∈  [ � ]，是足够的。根据定理 1，存在一个证明集，为上述成对距离提供所需的近似。将上述内容结合起来，可以得到对于定义 2中的任何成本函数的可证明近似。只需恢复一个指定的证明集，这是第2.3节和第2.4节的目标。02.3. 对齐问题的近似0我们现在提供一个算法，用于计算对齐问题（1）及其变体的可证明近似，即当 � 与 �的匹配已知时。这是通过恢复指定的证明集来实现的。算法2 的概述。使用定理 1 并假设 � 与 �的匹配已知，可以构造一个类似 RANSAC的算法，该算法迭代 � 个 � 和 � 的子集，每个子集的大小为 �，对每两个相应的子集应用算法 1来获得一个候选对齐，并返回使得成本函数最小化的对齐。算法 2 实现了上述方案。02 | . 令 cost ,  �  和  �  如定义 2 中所述，对于  � ( �, � ) =1 𝑀 := .ALIGN( 𝑝𝑖1,, 𝑝𝑖𝑑 , 𝑞𝑖1, · · · , 𝑞𝑖𝑑})5𝑀 := 𝑀 ∪ {(𝑅′, 𝑡′)}6 (𝑅, 𝑡) ∈ arg min(𝑅′,𝑡′)∈𝑀cost (𝑃, 𝑄, (𝑅′, 𝑡′))cost(𝑃, 𝑄, (𝑅, 𝑡)) ≤ 𝑤𝑟𝑠·(1+√2)𝑑𝑟𝑠· min(𝑅′,𝑡′) cost(𝑃, 𝑄, (𝑅′, 𝑡′)),𝑖8𝑆 := an arbitrary rotation matrix that satisfies𝑆𝑝𝑗‖𝑝𝑗‖ =9𝑊 :=𝑊 |10𝐽 := 𝐽132740算法 2:  A PPROX -A LIGNMENT ( �, �, �,  cost)0输入：一对集合  �  �  R � 和  �  �  R � ，迭代次数  � >  0，以及一个成本函数。输出：一个对齐  ( �, � )；参见定理  302  �  :=  从 [ � ] 中随机抽取 � 个不重复的 �个索引的元组集合。  //  | � |  =  �03  对于每个 ( � 1 ,  ∙ ∙ ∙  , � � )  ∈  �，执行以下操作0// 参见算法  107  返回  ( �, � )0‖ �  −  � ‖ � . 令 ( �, � ) 为调用 A PPROX - A LIGNMENT ( �, �, �,cost) 的输出；参见算法 2 . 那么，0其中最小值是对于每个  ( � ′ , � ′ )  ∈  A LIGNMENTS。此外，( �, � ) 在 � � ( � ) 时间内计算。02.3.1 运行时改进0我们现在提出一个随机算法（参见算法  3），其目标与算法  1相同，但成功的概率是恒定的。通过多次运行此算法，我们可以恢复一个对齐，其保证与算法  2的输出相同的概率接近  1。然而，这个新的随机算法需要线性时间，而不是多项式时间。算法  3 的概述。与期望输入一个证明集的算法  1不同，算法  3接受两个完整的点云作为输入，并在内部识别出一个潜在的证明集。直观地说，当正确对齐时，�中的范数较大的点对我们的成本函数的影响比范数较小的点更大；参见附录中的图  11 。因此，算法  3 以依赖于 �的范数的概率采样一对对应点  ( �, � ) ，并旋转  � 以使  �  和  �的方向向量对齐。然后，类似于算法  1，它将集合投影到与  �  正交的超平面上并重复此过程。0定理 4.  设  �  和  �  是两个有序的包含 � 个点的集合，其中  �  0 ，cost 如定义 2 所示，对于  �  =  ‖ � ‖ 1 ，某个 � -logLipschitz 函数  ℓ 以及  � ( �, � ) =  ‖ �  −  � ‖ � 。设  ( �, � )  P ROB -A LIGN ( �, �, � ) 的输出；参见算法 3 。那么，至少有1 2 � 的概率，0cost( �, �,  ( �, � ))  ≤  � ∙ min ( � ′ ,� ′ ) ∈ A LIGNMENTS ( �( � ′ , � ′ )) ，0算法 3:  P ROB -A LIGN ( �, �, � )0输入：一对集合  �  =  { � 1 ,  ∙ ∙ ∙  , � � }  和 �  =  { �1 ,  ∙ ∙ ∙  , � � } ，其中 �  >  0。输出：旋转矩阵；参见定理 401  从 [ � ] 中均匀随机地抽取一个索引  �02  �  :=  �  −  � � ，对于每个  �  ∈  �03  �  :=  �  −  � � ，对于每个  �  ∈  �04  �  :=  { � } ，�  :=  � 维单位矩阵05  对于每个  �  ∈  [ �  −  1]，执行以下操作0� ∈ [ � ] ‖ � � ‖ � ，对于每个  �  ∈07 从 [ � ]  �  � 中随机抽取一个索引  � ，其中 �  =  �的概率为  � � 。0‖ � � ‖ 和  �� �  =  � � ，对于每个  �  ∈  � 。0‖ � � ‖ ]� ∈  R � × � 形成了  R �的一组基。011 �  :=  �� ，对于每个  �  ∈  �012 �  :=  �� � � ，对于每个  �  ∈  �  � { � �  |  �  ∈  � }013 �  :=  �� � � ，对于每个  �  ∈  �  � { � �  |  �  ∈  � }015  �  :=  �� �  −  � �16  返回  ( �, � )0对于依赖于 � 和 � 的常数 � ，计算 ( �, � ) 需要 � ( �� 3 ) 的时间。0成功概率。对于 �  = 3 的常规情况，算法 3的成功概率至少为 1 / 8 。因此，重复不超过 6 次的算法 3可以将定理 4 中的成功概率放大至 1 / 2 以上。02.4. 注册问题的近似解0如第 1.3 节所述，从 � 和 � 中存在一个证据集，即使在匹配 �和 �之间是未知的更困难的情况下也是如此。我们现在提供了一个算法，可以针对注册问题的任何给定变体恢复一个证据集。该正式陈述如定理 5 所示，这是我们的主要贡献之一。0算法 4 的概述。与算法 2 不同，算法 4 采样用于索引 � 和 �的 � 个索引，我们现在需要独立采样 � 个索引用于 �中的点以及 � 个索引用于 �中的点。此外，在评估代价函数之前，我们需要对由算法 1返回的每个候选对齐进行最近邻匹配。算法 4将上述方案应用 �次，并返回最小化给定代价函数的对齐和匹配函数。0定理 5.  设  �  =  { � 1 ,  ∙ ∙ ∙  , � � } ，  �  =  { � 1 ,  ∙ ∙ ∙  , � � }是两个有序的包含 � 个点的集合，�  ∈  Ω( � 2 � ) ，  � >  0 ，1 𝑀 := .ALIGN( 𝑝𝑖1,, 𝑝𝑖𝑑 , 𝑞𝑗1, · · · , 𝑞𝑗𝑑})restneighbour matching between 𝑄,*/and 𝑤 = 𝑑1𝑧 −132750算法 4:  A LIGN - AND -M ATCH ( �, �, �,  cost)0输入：一对集合  �  �  R � 和  �  �  R � ，迭代次数  � >  0，以及一个代价函数。输出：一个对齐和匹配函数；参见定理 502  �  :=  随机抽取，不重复地从 [ � ] 中抽取  � 个 2 �个索引的元组  ( � 1 ,  ∙ ∙ ∙  , � � , � 1 ,  ∙ ∙ ∙  , � � ) ，其中  � 1 ,∙ ∙  , � �  是不同的，� 1 ,  ∙ ∙ ∙  , � �  是不同的。  //  | � |  =  �0对于每个( � 1 ,  ∙ ∙ ∙  , � � , � 1 ,  ∙ ∙ ∙  , � � )  ∈  �，执行以下操作：0// 见算法105 � := � ∪ { ( �', �', NN ( �, �, ( �', �' ))) }06 ( ˜ �, ˜ �, ˜ � ) ∈ arg min ( �',�',�' ) ∈ � cost ( �[ �' ], �, ( ) ) .0返回 ( ˜ �, ˜ �, ˜ � )02 | . 令 cost 和 � 如定义2所示0对于 � = ‖ � - � ‖ � 和 � ( � ) = ‖ � ‖ 1 。令 ( ˜ �, ˜ �, ˜ � ) LIGN-AND-M ATCH ( �, �, �, cost)的输出；见算法4。那么，对于 � = � 02) �� ，我们有0cost ( �[ ˜ � ], �, ( ˜ �, ˜ � ) ) ≤ � ∙ min ( �,�,� ) cost ( �[ � ], 0其中最小值是在每个对齐 ( �, � ) 和排列 � 上取的。此外，( ˜ �, �, ˜ � ) 在 � � ( � ) 时间内计算得出。0将 � = � = 2 代入定理 5可以得到ICP的可证明近似替代方法。与RANSAC的比较。RANSAC与算法2和4在某种意义上有些相似，它们都从 � 和 �中随机采样点。然而，虽然RANSAC通过对这些候选 �对进行普通最小二乘法来恢复候选对齐（见第1节），我们的算法利用了一种新颖的方法（算法1），这种方法对于这些 � 对来说不一定是最优的，但对于所有 �对的整体成本来说是（几乎）全局最优的。理论上，与我们的算法不同，RANSAC不能保证全局最优性；见第3.1节中的比较。我们的近似常数。虽然上述定理3-5中的近似常数可能看起来很大，但在悲观最坏情况理论中它们只是大约小于14，实际上它们比2小，并且可以比建议的时间更快地获得；见第3节。03. 实验结果0我们现在将我们的算法应用于解决对齐问题或配准问题。来自SUN3D数据集[48]的真实世界扫描的额外实验放置在附录的第F节中。数据集。我们使用了斯坦福3D扫描库[9, 23,43]中的Bunny、Armadillo和Asian Dragon模型。这些模型被缩放到[-0.5,0.5]的范围内。0由于某些竞争方法的约束（例如GO-ICP），我们还使用了一个合成数据集，其中包含在 [ -0.5, 0.5] �范围内均匀采样的 � 维点。生成 � 和 �。在所有实验中，给定某个数据模型（真实或合成），我们均匀采样了名为 � 的 � 点。生成一个对齐 ( �, � ) ，其中 �均匀采样，使得 ‖ � ‖ ≤ 0.1 ，并且 �将数据绕每个轴旋转一个从 [ -�, � ]均匀采样的角度。然后，通过将 ( �, � ) 应用于 �并添加均值为零、方差为 �^2 的高斯噪声来获得 �。在第3.2节中，我们还对 �进行了随机洗牌。评估。我们提供了两个评估指标：（i）最小化成本函数本身的值，例如（1）或（3）的值。如果没有给出，可以通过应用 ( �, � ) 到 �后，通过最近邻方法轻松计算出最优对应关系。（ii）旋转和平移误差：�� � �  � *  −  � �� � 和 ‖ �  −  � * ‖ 2 ，其中 ( � * , � * ) 和( �, � )分别是真实对齐和恢复对齐。本节中的每个实验都进行了20次并取平均值。方差在图表中呈现。03.1. 对齐实验0在这里，我们假设对应函数已经给出。我们应用了三种算法：（i）P-RANSAC：Provable RANSAC -算法2的Python实现，（ii）RAN