基于 Louvain 改进的点云配准算法

针对迭代最近点(iterative closest point, ICP)算法对初始位姿敏感的缺点,文章提出一种基于Louvain改进的快速点特征直方图(fast point feature histograms, PPFH)点云配准算法。首先,使用FPFH算法提取下采样后的点云局部特征,建立待配准点云之间的几何对应关系;其次,利用成对距离约束计算对应点对的一阶空间相似性,构建一阶无向加权图,将欧氏空间中的几何对应关系转化为图空间中的节点和边;再次,采用奇异值分解对由Louvain算法迭代得到的聚类节点求解空间变换矩阵,从而完成粗配准;最后基于ICP算法完成精配准。选取斯坦福大学3组公共点云集进行实验,结果表明,相较于采样一致性初始配准(sample consensus initial alignment, SAC-IA)算法,文章算法在达到近似甚至更高配准精度的情况下,配准时间缩短了约20倍,并且运行稳定可靠。

Aiming at the disadvantage that the iterative closest point (ICP) algorithm is sensitive to the initial pose, an improved point cloud registration algorithm based on Louvain using fast point feature histograms (FPFH) is proposed. Firstly, the local features of the down-sampled point clouds are extracted by FPFH algorithm, and the geometric correspondence between the point clouds to be registered is established. Secondly, the first-order spatial similarity of corresponding point pairs is calculated by using pairwise distance constraints, and the first-order undirected weighted graph is constructed to transform the geometric correspondence in Euclidean space into nodes and edges in graph space. Thirdly, the singular value decomposition is used to solve the spatial transformation matrix of the clustering nodes obtained by Louvain, thus completing the rough registration. Finally, precise registration is completed based on ICP algorithm. Three groups of public points from Stanford University are selected for experiments. The results show that compared with sample consensus initial alignment (SAC-IA) algorithm, the registration time of this algorithm is shortened by about 20 times with similar or even higher registration accuracy. Furthermore, the algorithm is stable and reliable.