point cloud registration 点云配准算法

在初步认识点云和学习了点云与计算机视觉之后，大家是否对点云在图像处理中的应用产生好奇呢？下面小编将过介绍高层次的点云处理方法之一——配准和点云特征来为大家构建点云配准的基础认知，然后就是多种常用点云配准算法大放送哦！

点云处理之配准

粗配准

粗配准是在源点云与目标点云完全不知道任何初始相对位置的情况下，所进行的配准方法。该方法的主要目的是在初始条件未知的情况下，快速估算一个大致的点云配准矩阵。整个计算过程要求比较高的计算速度，对于计算结果的精确度则不做过高的要求。常见的粗配准算法的思路包括了：基于局部特征描述的方法、基于全局搜索策略以及通过统计学概率等方法。

1）基于局部特征描述的方法是通过提取源点云与目标点云的邻域几何特征，通过几何特征快速确定二者之间的点对的对应关系，再计算此关系进而获得变换矩阵。而点云的几何特征包括了很多种，比较常见的即为快速点特征直方图（FPFH）。

2）基于全局搜索策略的代表算法是采样一致性算法（SAC_IA），该算法在源点云与目标点云之间随机选取几何特征一致的点组成点对。通过计算对应点对的变换关系，得到最优解。

3）正态分布算法（NDT）利用统计学概率的方法，根据点云正态分布情况，确定了对应点对从而计算源点云与目标点云之间的变换关系。

精配准

精配准就是在已知一个旋转平移的初值的情况下（初值大概已经是正确的了）,进一步计算得到更加精确的旋转平移矩阵。精配准是利用已知的初始变换矩阵，通过迭代最近点算法等算得到较为精确的解。

点云特征

点云特征按照特征的物理属性，可以将特征分为：几何域，强度域；而按照特征的空间尺度则可以分为：单点特征，局部特征，全局特征。下面小编就用空间尺度的分类方法带大家看看点云都有哪些特征呢。

单点特征

单点特征主要包括：三维坐标（X, Y, Z）, 回波强度 Intensity, 法线 （Nx, Ny, Nz），主曲率（PCx, PCy, PCz, 及两个特征值 PC1, PC2）等。

局部特征

在几何域内，常见的局部特征有：PFH，FPFH，SHOT，C-SHOT，RSD，ESF描述子、3D形状描述子、Lalonde 特征（谱特征）等。

在强度域内，常见的局部特征有：强度梯度（IGx, IGy, IGz)、局部强度均值与均方差和强度旋转图。

全局特征

常见的几何域全局特征有VFH、CVFH、三维不变矩、三维尺寸、投影密度×距离、高程差、平面拟合残差/均方差、GFPFH、协方差矩阵特征值/比值/谱特征。

常见的强度域全局特征有平均强度、最大强度以及强度方差/均方差。

点云配准算法

1、ICP算法

ICP算法通过计算源点云与目标点云对应点距离，构造旋转平移矩阵RT，通过RT对源点云变换，计算变换之后的均方差。若均方差满足阈值条件，则算法结束。反之继续重复迭代直至误差满足阈值条件或者迭代次数终止。下面就是ICP算法的具体流程哦。

ICP算法有以下特点：

优点：ICP算法的应用度较高，且应用范围较广，计算速度快；

缺点：对于两片点云的初始位置要求较为严格，否则容易陷入局部收敛且会影响配准速度，因此需要通过粗配准来为ICP提供较好的点云初始位置。

想不想直观地看到ICP算法的配准结果呢，滑动下面图片即可了解！

2、NDT算法

NDT算法根据参考数据构建多维变量的正态分布，如果变换参数能使得匹配的很好，那么变换点在参考系中的概率密度将会很大。

一般来说NDT算法的基础流程如下：

1）将空间划分成各个格子cell；

2）将参考点云投到各个网格中并计算正态分布概率密度函数的参数；

3）通过计算概率分布和最大似然函数得到最优变化参数。

但是在实际应用中NDT算法的适应度并不高呢。

3、Fgr算法

Fgr算法较之于其他算法有着独特的流程哦！

1）对特征点进行描述；

2）根据最近点原则寻找目标点；

3）根据互为对应点原则去除一些异常值。

同时这也造成了这种算法的特点：

优点：对误差的测量，相比于均匀方误差具有更好的抗噪性；

缺点：当关联的噪声率比较高的时候，权重估算不准，无法达到鲁棒估计的效果。

当我们用Fgr算法处理modelnet40数据集的时候点云配准速度可以达到489ms/张哦！配准结果也在下方展示啦！

4、PcrNet算法

PcrNet算法的独特之处在于：PointNet利用池化技术，有效地提取了点云的全局特征，不需要计算点云之间的一一对应关系，包括提取特征层和回归层。

PcrNet算法具有以下特点：

优点：计算效率高，有效的学习了大规模样本的配准规律，且对噪声的鲁棒性具备一定优势；

缺点：由于提取的是全局特征，在精度上有所欠缺。

5、iterative PcrNet算法

iterative PcrNet算法通过将PCRNet反复进行配准就可以得到迭代式的配准模型，得益于迭代方式更加精确，为了提高迭代的效率，将PCRNet算法中的5层FC改成了3层。

iterative PcrNet算法具有以下特点：

优点：计算效率高，提高了PcrNet的匹配精确度，且利用对象的特殊性能够产生精确的结果；

缺点：由于需要学习全局特征，可能会因网络的学习容量限制了性能。

虽然iterative PcrNet算法在处理modelnet40数据集点云配准速度较之于Fgr算法惊人的489ms/张只有为65ms/张，但ADI AUC高达94.4%。同样，配准结果划划手指即可观看。

6、reAgent混合算法

reAgent算法有许多独特之处让它具有算法的稳定性和效率较高的优点，例如：

1）基于模仿学习（IL）和强化学习（RL）的结合。

2）通过采用模仿学习来初始化其基于稳定专家策略的离散配准策略。

3）基于提出的对齐奖励，与策略优化的集成进一步提高了智能体的配准性能。

reAgent算法处理modelnet40数据集的点云配准速度就更紧张了，目前只能达到11ms/张。下面我们将用一个视频去呈现配准结果。

在学习了粗配准和精配准的定义和点云特征的基础知识之后，大家有没有对后面这么多点云配准算法有了自己的理解呢？想了解更多点云相关知识，可以持续关注本系列哦！

-The End-

文案：葛俊杰

指导老师：曹菁菁 赵强伟

排版：邓诗怡