4PCS与Super4PCS算法原理介绍

一、概述

  目前最先进的点云配准方法是基于一致性四点集（4-Point Congruent Sets,4PCS）的一系列算法，也是目前对于低重叠率点云最有效的配准方法，可以处理任意初始位置的点云数据。4PCS利用RANSAC的思想，首次将运算复杂度从$O(n^3)$降低到$O(n^2)$，Super 4PCS算法使用和4PCS相同的原理，并在搜索方式上做出了改进，将复杂度$O(n^2)$ 降低到$O(n)$ 。
  基于局部几何特征的配准算法在点云数据包含的噪声点较多、重叠率较低的点云数据中往往可靠性不高，导致配准结果不理想。Dior Aiger 等人通过 RANSAC 的思想，利用点云数据刚体变换中相交线段的交比不变这一性质，在全局范围内搜索对应的一致性四点集，并根据最佳的一致性对应关系计算变换矩阵，完成点云数据的配准。但是这个算法在配准时间上有两个瓶颈，因此激发了 Super 4PCS 配准算法，该算法以 4PCS 为基础，在搜索阶段做出一些改进，引入了角度约束和智能索引，将复杂度从二次降低到线性时间，提高一致性四点集的查找速度。 由于 Super4PCS 算法的基本原理与最基础的 4PCS 算法相同，首先详细介绍4PCS 的原理，说明 Super4PCS 算法相对于 4PCS 的改进内容。

1、四点一致性集算法（4PCS）

2、Super 4PCS

二、代码

• PCL 4PCS算法实现点云粗配准【2024最新版】
• PCL Super4PCS算法实现点云粗配准（版本一）
• PCL Super4PCS算法实现点云粗配准（版本二）