基于FPFH特征和NDT算法的树木点云配准
Tree Point Cloud Registration Based on FPFH Feature and NDT Algorithm

为了提高海量林地三维点云数据配准的效率和精度，提出了一种基于快速点特征直方图（fast point feature histograms,FPFH）初始匹配与正态分布变换（normal distributions transform,NDT）精确配准相结合的配准算法。首先计算2个待配准点云的法向量，再使用k-d树结构对点云的FPFH特征进行加速计算。然后，根据2个点云相似的FPFH特征，使用采样一致性初始配准算法（sample consensus initial alignment,SAC-IA）求解初始变换矩阵、完成初始配准。最后，用DNT算法对点云体素化，并使用点云密度概率分布函数进行点云数据的精确配准。结果表明，FPFH-NDT算法的平均配准误差（相应点对的平均距离）为0.032 3 m，运行时间为256.376 s；在0.05~0.1 m的点云采样阈值范围内，FPFH-NDT算法的配准误差基本不受采样阈值变化的影响，其值稳定在0.03 m左右；当采样阈值>0.1 m时，配准误差随采样阈值的增大而增大；算法的配准时间整体上随点云采样阈值增大而减少。传统ICP算法的平均配准误差和时间分别为0.526 3 m和14.5 s；FPFH-ICP算法的平均配准误差和时间分别为0.042 5 m和289.346 s。FPFH-NDT算法与传统ICP算法相比在配准精度上有了很大的提高，与FPFH-ICP算法相比，在保证点云的配准精度的基础上，FPFH-NDT算法降低了算法的运行时间，提高了点云配准效率。
Point cloud registration is one of the key issues in 3D digital processing technology and visual modeling.In order to improve the efficiency and accuracy of 3D point cloud data registration in massive forest land,a fast point feature histogram (FPFH) initial registration combined with normal distribution transformation (NDT) precise registration algorithm was proposed.The registration algorithm first calculated the normal vectors of two point clouds to be registered,and used the k-d tree structure to accelerate the calculation of the FPFH features of the point cloud and then according to the similar FPFH features of the two point clouds,the initial transformation matrix was solved by using the sampling consistency initial alignment algorithm (SAC-IA),and the initial registration was completed.Finally,the DNT algorithm was used to prime the point cloud,and the point cloud density probability distribution function was used to precisely register the point cloud data.The experimental results showed that the average registration error of the FPFH-NDT algorithm (the average distance of the corresponding point pairs) was 0.032 3 m,and the running time was 256.376 s.In the range of 0.05 m~0.1 m point cloud sampling threshold,the registration error of the FPFH-NDT algorithm was basically unaffected by the sampling threshold change,and its value was stable at about 0.03 m.When the sampling threshold was greater than 0.1 m,and the registration error increased with the increase of the sampling threshold.The registration time of the FPFH-NDT algorithm generally decreased with the increase of point cloud sampling threshold.The average registration error and time of the traditional ICP algorithm were 0.526 3 m and 14.5 s,respectively; while the average registration error and time of the FPFH-ICP algorithm were 0.042 5 m and 289.346 s,respectively.Compared with the traditional ICP algorithm,the FPFH-NDT algorithm had