1. 论文动机

        三维点云配准作为三维视觉的重要分支，近年来在遥感、机器人、智能驾驶等场景中得到了广泛的应用，其目的是估算源点云和目标点云之间的六自由度位姿。在点云之间建立点到点的对应关系是进行三维点云位姿估计常用且有效的方法。但是，由于现有的关键点检测子和描述子检测的局限性，加之数据噪声等干扰，初始匹配集中通常掺杂大量离群点，使得问题极具挑战性。

        随机采样一致性算法（RANSAC）为最具代表性的从带有离群点的初始匹配集中估计六自由度位姿的方法，但是仍存在耗时、精度不足的问题。今天向大家介绍一篇西北工业大学等单位发表在IEEE TGRS 2021上的论文，该工作提出一种技术简单、性能优越的图引导采样一致性算法（SAC-COT），是RANSAC算法的一个变种。考虑到初始匹配集中误匹配较多，随机采样往往很难较快地选取到正确的匹配，该工作提出了一种指导性的三点采样方法，它基于一种新的三点匹配样本表征，首先将匹配集建模成为一个图，其节点连接相容的匹配；然后对图中的三元环进行排序和抽样，使得在迭代早期就能采样到正确的匹配，最终同时提升配准精度和速度的目的。

2. 论文题目

[IEEE TGRS 2021] SAC-COT: Sample Consensus by Sampling Compatibility-Triangles in Graphs for 3D Point Cloud Registration 

杨佳琪^1,2, 黄志强^1,2, 权思文³, 齐召帅^1,2, 张艳宁^1,2

(¹西北工业大学，²空天地海一体化大数据应用技术国家工程实验室,  ³长安大学)

3. 创新点

• 提出了一种引导式的三点采样方法。它基于一种新的匹配表示方法，即兼容性三角形（COT）。COT一方面继承了距离约束对常见扰动具有鲁棒性的优点，另一方面极大地缓解了它们的模糊性问题。通过对 COTs 进行排序和抽样，证明了在迭代的早期阶段即可生成正确的假设。此外，本文提出的抽样技术具有泛化性，它可以提高其他三点 RANSAC 方法的配准性能。
• 提出了一种精确、鲁棒、快速的六自由度位姿估计子SAC-COT，用于三维配准。SAC-COT凭借三点引导抽样策略，仅需较少迭代次数就可以产生合理的假设。通过在6个不同应用场景、不同数据模式的数据集上进行对比实验，证明了 SAC-COT 具有高效、准确、抗干扰性强等特点。

4. 相关工作

        2.1基于六自由度位姿估计的三维配准

        RANSAC[1]及其变种算法仍然是从带有离群点的初始匹配集中估计六自由度位姿的主流方法。当外点率很高时，传统的RANSAC算法通常会面临时间开销大、配准准确率低等问题，为克服这两个问题，Rusu等人[2] 利用Huber损失提出了一种基于样本一致性的初始对齐(SAC-IA)方法，Yang[3]等人提出了一个点云距离度量来评估姿态假设，并引入了最优样本一致性(OSAC)方法。除了 RANSAC 方法，Guo 等人[4]提出了一种基于聚类的方法，该方法首先在旋转和平移空间中生成姿态假设，然后在两个空间中定位聚类中心; Tombari 等人[5]提出了一种基于Hough投票的方法。这些方法都依赖于法线或局部坐标系，而这些法线或局部坐标系在噪声、部分重叠和遮挡情况下是不稳定的。

        2.2基于几何约束的三维配准

        由于初始匹配集中含有大量误匹配，为采样到正确匹配，Rodola[6]等人提出距离约束，Tang[7]等人提出法向偏向角约束，Yang[8]等人提出局部坐标系约束。然而，这些约束存在模糊性，对常见干扰的鲁棒性不足。遮挡、噪声等干扰仍然是几何约束下三位配准任务的重要挑战。

        2.3基于深度学习的三维配准

        随着深度学习的兴起，相关技术也被应用到三位配准上。Aoki [9]等人提出了用于3D 配准的 PointNetLK 网络的迭代方式，其中 PointNet [10]被用于描述符提取，并结合了 Lucas/Kanade-like 优化算法。Wang[11]等人提出了深度最近点(DCP) ，它包括一个点云嵌入网络，一个近似组合匹配的基于注意力的模块，和一个可微的六自由度位姿估计奇异值分解。深度学习技术已经证明了3D 配准的巨大潜力，但同时通常需要准备足够的标记训练数据，这在许多实际场景中并不可行。

5. 方法描述

        5.1问题定义

        图1为SAC-COT的算法流程图：给定两个初始点云，SAC-COT 首先对样本进行排序，指导采样过程，然后迭代进行采样、假设生成和假设评估，进行六自由度姿态估计和三维配准。SAC-COT 的主要特点是引导采样步骤: 首先将每个对应关系作为一个节点并连接相容的节点，构造一个图; 通过在图中搜索三元环生成 COTs; 然后对 COTs 进行排序，形成一个引导的基于3点的采样方案。

        为了增加可读性，表1给出文中必要的符号说明：

表1：方法变量说明

图1 SAC-COT算法流程

        5.2图的构建

        我们使用初始匹配集来构建无向图。首先，将每个匹配作为一个节点；其次，如果两个节点具有几何兼容性，则生成一条边。如图2所示，在三维刚体数据中，如果一对匹配和为正确匹配，则应满足以下约束：

基于上式，兼容性函数可定义为：

其中是一个常数。如果大于一个阈值则定义两个节点具有几何兼容性，对应的两个节点之间有一条边。

图3 距离约束的模糊性

5.3兼容性三角形生成与排序

        相比于随机采样，引导采样的目的是尽量选取到正确的匹配。通过计算匹配之间的兼容性，可以剔除初始匹配集里兼容性测度得分较低的部分错误匹配。但如图3所示，由于距离约束的模糊性，兼容性测度得分较高的匹配也可能是错误匹配，因此我们提出兼容性三角形（COT）来衡量匹配的正确性。

        兼容性三角形在图中是连通的，因此三角形的顶点两两相互兼容。COT 加强了对应的三重距离约束，可以有效地消除成对距离约束的模糊性。为了生成指导采样的机制，我们需要按照特定规则对COTs进行排序，因此如图4所示，为COT定义了两个属性：

（1）COT的度：其中表示顶点的度

（2） COT的兼容性得分：其中

        然后，我们将 COTs 按照度或兼容性得分降序排列，之后通过抽样排名最高的 COTs 来执行基于3点的抽样。

图4 兼容性三角形的属性

5.4假设生成与评估

        因为一个COT包含三根匹配，足够进行六自由度位姿估计。经过N迭代采样之后需要评估选出最优的位姿，作为SAC-COT的输出。我们使用MAE作为评价函数:

其中表示旋转误差，是一个常量，用于判断是否为内点。在N次迭代中，产生最小的假设即为SAC-COT的输出。

6. 实验结果

6.1分析实验

        论文在U3M数据库下进行分析实验。图5（a）和（b）分别表示迭代次数对SAC-COT和传统RANSAC算法配准准确率的影响。从数据可以看出，SAC-COT 在 N 从10到1000变化时始终优于 RANSAC。且SAC-COT 在10次迭代就实现了与 RANSAC 1000次迭代相当的性能。这表明 SAC-COT 能够在早期迭代阶段识别出正确样本。

图5 不同迭代次数对配准准确率的影响

        图5(c)表示不同评价函数下，SAC-COT与RANSAC和SAC-IA算法配准准确率对比情况。可以发现，基于COT指导的采样方法适用于各种RANSAC假设评价函数。

6.2对照实验

        论文在U3M、BMR、U3OR、BoD5等4个数据集下开展了对照试验，对比各个算法在4个数据集下的配准准确率。如图6所示，可以发现，SAC-COT算法在各个数据集上的配准性能均由于其它现有算法。

图6 不同数据库下各个算法配准率对比

        此外，如图7所示，论文在 RESSO-LO (row1-row3)和 ETH LiDAR (row4-row5)室外激光雷达数据集上使用SAC-COT算法对点云进行配准，发现 SAC-COT 算法同样适用于大规模户外点云，进一步验证了 SAC-COT 算法的泛化能力。

图7 SAC-COT在户外数据集配准结果可视化

7. 参考文献

[1] M. A. Fischler and R. C. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography,” Communications of the ACM, vol. 24, no. 6, pp. 381–395, 1981

[2] R. B. Rusu, N. Blodow, and M. Beetz, “Fast point feature histograms (fpfh) for 3d registration,” in Proc. IEEE International Conference on Robotics and Automation, 2009, pp. 3212–3217.

[3] J. Yang, Z. Cao, and Q. Zhang, “A fast and robust local descriptor for 3d point cloud registration,” Information Sciences, vol. 346, pp. 163–179, 2016.

[4] Y. Guo, F. Sohel, M. Bennamoun, M. Lu, and J. Wan, “Rotational projection statistics for 3d local surface description and object recognition,” International Journal of Computer Vision, vol. 105, no. 1, pp. 63–86, 2013.

[5] F. Tombari and L. Di Stefano, “Object recognition in 3d scenes with occlusions and clutter by hough voting,” in Proc. Pacific-Rim Symposium on Image and Video Technology. IEEE, 2010, pp. 349–355.

[6] E. Rodola, A. Albarelli, F. Bergamasco, and A. Torsello, “A scale ` independent selection process for 3d object recognition in cluttered scenes,” International Journal of Computer Vision, vol. 102, no. 1-3, pp. 129–145, 2013.

[7] K. Tang, P. Song, and X. Chen, “3d object recognition in cluttered scenes with robust shape description and correspondence selection,” IEEE Access, vol. 5, pp. 1833–1845, 2017.

[8] J. Yang, Y. Xiao, Z. Cao, and W. Yang, “Ranking 3d feature correspondences via consistency voting,” Pattern Recognition Letters, vol. 117, pp. 1–8, 2019

[9]. Y. Aoki, H. Goforth, R. A. Srivatsan, and S. Lucey, “Pointnetlk: Robust & efficient point cloud registration using pointnet,” in Proc. IEEE Conference on Computer Vision and Pattern Recognition, 2019, pp. 7163–7172

[10]. R. Q. Charles, S. Hao, K. Mo, and L. J. Guibas, “Pointnet: Deep learning on point sets for 3d classification and segmentation,” in Proc. IEEE Conference on Computer Vision and Pattern Recognition, 2017, pp. 195– 205.

[11]. Y. Wang and J. M. Solomon, “Deep closest point: Learning representations for point cloud registration,” in Proceedings of the IEEE International Conference on Computer Vision, 2019, pp. 3523–3532