点云配准算法之super-4pcs

本文介绍super-4pcs配准算法，以下讲述的是我在阅读论文之后对次算法的理解，如有不当之处，欢迎指正，详情请参考作者的论文。
4pcs论文地址
super-4pcs论文地址
Super-4PCS算法来源于4PCS算法，其基本思想是基于RANSAC算法，总体来看，其算法框架与基于RANSAC算法的配准框架基本一致，只是对确定对应点对的策略进行了优化，将原本的随机选择三个不同的点修改为以源点云中共面的四点为基，在目标点云中确定对应的四点，以构成四组对应点，在一定程度上可增强算法的鲁棒性。四点一致集算法的理论基础在于共面四点对的仿射不变性。在仿射变换中，由三个确定的共线点a、b和c所确定比例是不变的，那么，对于给定的非全共线的共面四点a、b、c和d，有ab与cd相交于点e，可确定以下两个比例：。则r1与r2在仿射变换中也是不变的，即由源点云中的四个共面点所确定的r1与r2和由目标点云中对应的四个点所确定的r1与r2是相同的。
基于仿射不变性确定对应点对的原理可描述为：假设给定源点云P中一组共面四点所组成的基，以及由这四点所确定的比例r1与r2，如下图(a)所示:

对于目标点云Q中的任意点对q1和q2，计算可能的交点e1和e2：

若在Q中存在两对这样的点使得一对的e1与另一对的e2在误差允许的范围内是相等的，那么这两对点可认为是P中所给的基的对应共面点，如上图中的(b)所示，其中灰色点代表e1，黄色点代表e2，则q5、q3、q4、q1与a、b、c、d相对应。
在给定源点云P，目标点云Q，距离不确定度度量ε和两片的点云的预估重叠率f的情况下，Super-4PCS算法的基本原理如下：
1) 从P中选择共面四点组成一个基（用B来表示）。选取基时遵循距离最大化原则，即保证点与点之间的距离较大但又不超过某个阈值，这个阈值可由重叠率f来确定。选取点时采用三加一的策略，即先在可能为重叠区域的点云表面选择3个不同的点，然后以共面不共线为原则确定第4个点。确定基后，可以得到相应的比例r1与r2，以及两个点距。
2) 在Q中确定集合S1与S2，

对于Q中的每一点qi，以它为球心，分别以R=d1和R=d2为半径画球，qi与那些落在范围内的点即满足S1的条件，而qi与那些落在范围内的点即满足S2的条件。
3) 在Q中提取与基对应的四点集并剔除错误的四点集。如下图所示，对于P中给定的基B（如下图(a)所示），在Q中存在对应的点集，但也可能存在错误的对应点集（如下图(b)所示），传统的4pcs算法在剔除错误的对应点集时会耗费较多的时间，而Super-4PCS算法可以在提取四点集的同时去除错误的点集，即得到唯一与基对应的四点集，从而加快算法执行速度。

由上图可知，如果给定基的就可以在目标点云中确定唯一对应的四点集。已知S1与S2中的点对分别满足点距近似为d1和d2的条件，现基于第2步中的球体计算S1与S2中每对点连线的方向向量并存储。基于仿射不变性的原理，对于S1与中的每一对点，计算由比例r1确定的交点e1，即，同理，对于S2中的每一对点，计算e2，即，在S1与S2中搜索满足与近似相等的点对，同时满足两点对连线的夹角近似等于θ，即可在Q中提取出唯一的与基对应的的四点集。
4) 由对应点集与计算刚体变换矩阵T，使用T对源点云P进行变换，统计变换后的点云与目标点云中最近点距离小于某个阈值δ的点的数目用以表征T的质量，迭代进行上述4个步骤，直至找到最优的T使得两片点云足够接近。