
3D点云配准是计算机视觉领域的核心任务之一,其主要目标是估计出一个变换矩阵,从而准确地对齐一对点云数据。这周我看了丁师兄24年发在 IEEE CEC 的论文 Evolutionary Multitasking with Compatibility Graph for Point Cloud Registration ,简称 EMCGPCR,这篇论文的创新点在于把 “兼容性图” 和 “演化多任务优化” 结合了起来,有效解决了传统配准方法中容易受噪声干扰和陷入局部最优的问题。
点云配准的核心挑战和解决思路
在点云配准中,直接从源点云和目标点云中寻找正确的匹配关系是非常困难的,尤其是当数据中存在大量离群点(噪声)或出现“跨物体匹配”的误导时。为了更好地挖掘点云间的一致性关系,论文采用了构建兼容性图(Compatibility Graph)的方法。
不同的图构建方法具有不同的约束条件,这会导致图空间中搜索信息的侧重点产生差异。为此,论文巧妙地引入了演化多任务优化(Evolutionary Multitask Optimization, EMTO)框架,通过构建两个不同约束条件的图作为两个同时进行的任务,让它们在统一的搜索空间中互相传递知识、取长补短。
算法的核心架构

这篇论文的算法流程可以清晰地分为以下几个核心步骤:
-
- 降采样与特征提取:首先,算法会对原始点云数据进行降采样处理,这样不仅能减少点的数量,还能使点云分布更加平均。随后,利用 FPFH(Fast Point Feature Histograms)描述符来提取点云间的对应关系,寻找出潜在的点云匹配对。
-
- 构建双约束兼容性图(多任务构造):这是整个算法的灵魂所在,论文基于潜在的匹配对构建了两个任务:
- 任务一(一阶宽松约束图 FOG):该图利用了刚性变换不改变物体相对距离的特性。如果找到的假设匹配对是正确的,那么源点云中两点的欧式距离必定等于目标点云上对应两点的距离。这种约束能剔除部分明显错误的匹配,并为正确的匹配关系加边。但它的局限在于无法解决“跨物体匹配”问题,例如当场景中存在杯子A和杯子B时,它可能错误地将A的局部匹配到B的局部上,因为这同样满足距离相等的条件。
- 任务二(二阶严格约束图 SOG):为了弥补任务一的缺陷,论文提出了二阶的严格约束图。它进行了更为严格的判定:候选匹配对不仅要满足基础的几何一致性,同时还需要拥有大量共同一致的邻居关系。这种通过考察“周围邻居关系是否一致”的严格判定,能够在很大程度上解决跨物体匹配的问题,并进一步剔除噪声。
-
- 极大团选取与统一搜索空间:接着,算法对这两个约束图进行极大团(Maximal Cliques)的选取。通过设计的团选择策略,将它们编码成概率数组,映射到一个统一的搜索空间中。
-
- 演化优化与知识转移:在统一的空间内,两个任务的个体通过交叉和变异操作进行演化,实现双向的知识转移。任务二(严格约束)能提供更精确的引导,而任务一(宽松约束)能提供更广阔的探索空间。
-
- 最优解评估:算法最终采用鲁棒的 M-estimation 作为适应度函数来评估个体,并解算出最优的旋转矩阵(R)和平移向量(t)。
实验结果和评估
对于验证 EMCGPCR 的有效性,师兄们在包含斯坦福(Stanford)数据集在内的 11 个点云数据集上进行了大量实验。

- 评估指标:实验主要采用了旋转误差(Rotation Error)、平移误差(Translation Error)和均方根误差(RMSE)这三个主流指标。
- 抗噪能力与表现:实验结果证明该方法效果非常好。特别是在斯坦福数据集上模拟离群点(噪声)的测试中,即使向源点云中添加比例高达 50% 的离群点,该算法依然保持了非常小的 RMSE 误差,展现出了极强的稳定性和鲁棒性。
总的来说,EMCGPCR 是一次将图论、演化计算与计算机视觉经典问题深度融合的优秀尝试,不仅思路巧妙,在应对高噪声点云配准任务时的表现也令人印象深刻。