基于迭代最少点和遗传算法的点云粗配准算法

Point Cloud Coarse Registration Algorithm Based on Iterative Minimum Point and Genetic Algorithm

摘要: 为了兼顾点云配准过程的时间和精度，提出了基于迭代最少点和遗传算法的点云粗配准算法。将源点云和目标点云的总点云进行下采样，以采样后总点云的数量作为遗传算法的目标函数，采用遗传算子指导解的搜索方向，通过新种群的迭代使下采样总点云数量最少，快速得到点云粗配准的结果。通过对6组不同的点云，以及采用多种算法进行对比试验，结果表明，该算法在保证配准精度的同时，耗时稳定在24 s左右，且对待配准点云模型无特殊要求，鲁棒性较强。

Abstract: To balance the time and precision of the point cloud registration process, a point cloud coarse registration algorithm based on the iterative minimum point and genetic algorithm is proposed. The total point clouds of the source point clouds and target point clouds are down sampled, with the number of the total point clouds after sampled as the target function of the genetic algorithm, the genetic operator guides the search direction of the solution, the total number of sampled point clouds minimizes through the iteration of the new population, and the results of point cloud coarse registration are obtained quickly. By comparing the tests of six different point clouds and using various algorithms, the results show that the proposed algorithm takes about 24 seconds stably while ensuring the registration accuracy, and treats the registration point cloud model without special requirements and has strong robustness.

1. 引言

近年来，在医疗 [1] 、工业 [2] 、文物修复 [3] [4] 、逆向工程 [5] 等各个领域中，三维重建都有着广泛的应用。生产环境和扫描设备的限制，得到的点云数据大多都存在不完整的情况，需要将多个点云进行配准，来完善物体的点云数据。一个完善的三维扫描系统除了滤波 [6] 、分割 [7] 以外，关键就在于如何快速、高效地寻找到最优的旋转平移矩阵。

目前，国内外在点云配准上取得了一定进展，比较经典的是Besl [8] 等提出的迭代最近点(Iterative Closest Point, ICP)算法，该算法基于计算欧氏距离来获得两个点云之间的对应点对，并针对对应点计算旋转平移矩阵，基于变换后的目标点云和源点云的误差函数，进行迭代的过程，直到两者误差小于所设阈值。ICP算法的精度较好，且原理较为简单，但其对两点云的初始位置要求较高，否则目标函数极易陷入局部最优。为了避免这种情况，一般采用粗配准算法搭配ICP算法来共同对点云进行配准。实现点云粗配准的重要方法之一是采用特征进行匹配。Rusu [9] [10] 等人提出了点特征直方图(Point Feature Histograms, PFH)，通过计算点云和邻域点云之间的法向量等特征来估计点云的表面情况；随后又作出改进，简化了特征的提取，优化了配准时间，提出了快速点特征直方图(Fast Point Feature Histograms, FPFH)；Tangelder [11] 等提出了三维形状上下文(3D Shape Context, 3DSC)，针对匹配向量的值来构建不同曲面的点之间的相对应的关系，用于描述曲面上指定点及邻域的形状特征；刘鸣 [12] 提出了一种利用独立成分分析(ICA)的点云配准方法；唐志荣 [13] 提出一种采用高斯混合模型对点云进行拟合，并通过最大期望算法(EMA)求解出正交因子模型的因子载荷矩阵；利用因子载荷矩阵完成对点云的配准；李宇翔 [14] 提出了一种基于内部形态描述子(ISS)及方向直方图描述子(SHOT)特征的点云配准算法；近些年也提出了一些启发式搜索算法在点云配准上的应用，马卫 [15] 通过布谷鸟算法和莱维飞行全局搜索更新策略对点云进行初始配准，得到空间变换矩阵参数；陈斯祺 [16] 采用了基于天牛须算法改进的粒子群算法，以点云分布熵为寻优目标，寻找最优空间变换矩阵的点云粗配准；孙殿柱 [17] 提出一种将遗传算法和O’Rourke算法相融合的最小包围盒求解算法，以O’Rourke算法中的体积函数作为遗传算法的目标函数来进行搜索迭代。

针对现有算法存在的精度或者时间上的问题，本文提出了迭代最少点算法(Iterative Minimum Point, IMP)，并采用遗传算法(Genetic Algorithm, GA)，以IMP为目标函数进行迭代，构建GA-IMP算法，快速完成粗配准过程，再配合ICP算法完成配准，保证从时间和精度两方面都取得较好的结果。

2. 点云配准算法

点云配准的实质是在源点云S和目标点云D中寻找到最优的旋转平移矩阵，其中 $D=R\ast S+t$ ， $R$ 为旋转矩阵， $t$ 为平移向量。本文算法由迭代最少点算法和遗传算法两部分构成，共同完成对点云的粗配准，再搭配ICP算法完成精配准。

2.1. 迭代最少点算法

通过体素栅格对点云进行下采样滤波，用体素中所有点的质心来近似显示体素中其他点，在精简点云的同时可以保留点云的几何结构。

设一个体素栅格内包围的点共有n个， $p_i=\left\{\begin{array}{c}{x}_i\\ y_i\\ z_i\end{array}\right\},i=1,2,3,\cdots ,n$ ，则其重心c满足

$c=\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{p}_i}$ (1)

滤波结果用一个质心点代替体素栅格内的n个点，因此体素栅格包围的点越多，则去除的点越多。

设源点云的点的数量为 $N_S$ ，目标点云D的点的数量为 $N_D$ ，源点云S和目标点云D的总点云为T，总点云T的点的数量为 $N_T$ ，且 $N_T=N_S+N_D$ ，体素栅格的边长为l。

如图1所示，点云 $S,D,T$ 经过边长为的l体素栅格滤波后，形成了新点云 $F_S,F_D,F_T$ ，点的数量分别为 $N_{FS},N_{FD},N_{FT}$ 。

Figure 1. Point cloud before and after filtering

图1. 滤波前后点云

当下采样体素栅格不变时，滤波后的源点云数量 $N_{FS}$ 和目标点云数量 $N_{FD}$ 是保持恒定的，唯一变化的是随着源点云的移动和目标点云的相交情况而变化的总点云数量 $N_{FT}$ 。在一个体素栅格内的所有点都会近似为一个质心点，所以相交部分越多，则滤波后的总点云数量 $N_{FT}$ 越少。

设迭代过程中源点云和目标点云的实际相对应点的数量为，当可得：

$N_{FS}+N_{FD}-N\le N_{FT}\le N_{FS}+N_{FD}$ (2)

当且仅当点云S和D无相交部分，且S所有关于D的对应点的距离大于体素栅格边长l时， $N_{FT}$ 取最大值， $\max \left(N_{FT}\right)=N_{FS}+N_{FD}$ 。

当且仅当源点云S和目标点云D的对应点完全重合，或者S所有关于D的对应点的距离小于体素栅格边长l时， $N_{FT}$ 取最小值， $\min \left(N_{FT}\right)=N_{FS}+N_{FD}-N$ 。

特别的，当源点云S和目标点云D为同一模型时，有 $N=N_{FS}=N_{FD}$ ，因此当 $N_{FT}=N_{FD}$ 时，源点云S和目标点云D即完全配准。

实验验证：

采用Bunny完整点云模型，体素栅格边长为0.08进行实验。源点云和目标点云的初始位置完全不相交。

在源点云S向目标点云D移动的过程中，选取其中的6个阶段如图2所示，下采样滤波后的点云为 $F_{T1},F_{T2},F_{T3},F_{T4},F_{T5},F_{T6}$ 。

Figure 2. Point cloud in registration process

图2. 配准过程中的点云

可以清楚的看到，随着配准的逼近，两点云重合的部分越来越多，因此滤波对总点云数量的影响变大，滤波前后各点云点的数量如表1所示。

Table 1. Number of points during the registration process

表1. 配准过程中点的数量

通过实验，证明了在配准过程中，随着重合部分的增大，滤波后的总点云数量在减少，两者成负相关，因此用滤波后总点云的数量来表征配准的有效程度是可行的。

2.2. 遗传算法

遗传算法(Genetic Algorithm, GA)起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解，算法流程如图3所示。

Figure 3. Flow chart to the genetic algorithm

图3. 遗传算法流程图

2.2.1. 染色体编码

待求的旋转矩阵一共有六个参数，因此染色体有六个基因，分别是绕 $X,Y,Z$ 轴旋转的角度 $\alpha ,\beta ,\gamma$ 和平移的距离 $a,b,c$ 。

$\alpha ,\beta ,\gamma$ 的取值范围为 $\left[0,\text{2}\pi \right]$ ， $a,b,c$ 的取值范围为 $\left[x_{\min },x_{\max }\right]$ ， $\left[y_{\min },y_{\max }\right]$ ， $\left[z_{\min },z_{\max }\right]$ ，其中 $x_{\min },x_{\max },y_{\min },y_{\max },z_{\min },z_{\max }$ 分别为点云D在 $X,Y,Z$ 轴方向上的最小值和最大值。各基因分别用10位二进制来表示，可以表示的范围在[0, 1024)， $\alpha ,\beta ,\gamma$ 的精度可以达到0.351˚， $a,b,c$ 的精度为 $\left(x_{\max }-x_{\min }\right)/1024$ ， $\left(y_{\max }-y_{\min }\right)/1024$ ， $\left(z_{\max }-z_{\min }\right)/1024$ 。

在每次迭代前通过对染色体解码，计算出旋转矩阵 $\alpha ,\beta ,\gamma$ 和 $a,b,c$ 的值，通过公式3计算得到旋转平移矩阵 $R$ 。

$R=\left[\begin{array}{cccc}\cos \left(\beta \right)\cos \left(\gamma \right)& -\cos \left(\alpha \right)\sin \left(\gamma \right)+\sin \left(\alpha \right)\sin \left(\beta \right)\cos \left(\gamma \right)& \sin \left(\alpha \right)\sin \left(\gamma \right)+\cos \left(\alpha \right)\sin \left(\beta \right)\cos \left(\gamma \right)& a\\ \cos \left(\beta \right)\sin \left(\gamma \right)& \cos \left(\alpha \right)\cos \left(\gamma \right)+\sin \left(\alpha \right)\sin \left(\beta \right)\sin \left(\gamma \right)& -\sin \left(\alpha \right)\cos \left(\gamma \right)+\cos \left(\alpha \right)\sin \left(\beta \right)\sin \left(\gamma \right)& b\\ -\sin \left(\beta \right)& \sin \left(\alpha \right)\cos \left(\beta \right)& \cos \left(\alpha \right)\cos \left(\beta \right)& c\\ 0& 0& 0& 1\end{array}\right]$ (3)

2.2.2. 适应度函数

由2.1节可知，遗传算法种选择的目标函数为在迭代过程中的总点云T滤波后的点云数量 $N_{FT}$ 。

为了便于遗传算法的选择，首先计算在相同体素栅格下目标点云D滤波后的点云数量 $N_{FD}$ ，然后每次迭代计算 $N_{FT}$ 和 $N_{FD}$ 的差值，使得变化幅度相对变大，更有利于子代的选择。

步骤如下：

1) 通过对染色体解码，得到参数 $\alpha ,\beta ,\gamma$ 和 $a,b,c$ ，并计算得到旋转平移矩阵 $R$ ；

2) 计算变换后的源点云：

$S_{\text{new}}=R\ast S$ (4)

3) 计算迭代一次的总点云：

$T=S_{\text{new}}+D$ (5)

4) 通过滤波函数 $F\left(x\right)$ 对总点云T和目标点云D进行滤波并作差，得到目标函数：

$Fitness\left(\alpha ,\beta ,\gamma ,a,b,c\right)=F\left(T\right)-F\left(D\right)$ (6)

3. 实验与分析

3.1. 迭代次数

遗传算法迭代次数太多会增大配准时间，次数太少则会影响配准效果，因此通过四次重复实验来确定迭代次数，实验对象同样为1.1节所采用的Bunny完整点云模型。遗传算法交叉概率，变异概率，种群数量为80。

实验结果如图4所示，点云数量在迭代30次之前已趋于稳定，因此将迭代次数设为30次较为合理。

Figure 4. Iterative process of genetic algorithm

图4. 遗传算法迭代过程

3.2. 对比试验

采用本文所提出的GA-IMP算法配合ICP精配准算法对公共点云Horse，Dragon，Happy Buddha和实验室采集的私有点云Cochlea，以及公共点云库的Bun000和Bun045单面点云进行试验。

为了评价本文算法的耗时和精度，加入了经典的PFH算法、FPFH算法和3DSC算法分别搭配ICP精配准算法完成配准对比实验。

结果如图5、图6、图7、图8、图9以及表2所示。

Figure 5. Horse point cloud

图5. Horse点云

Figure 6. Dragon point cloud

图6. Dragon点云

Figure 7. Happy Buddha point cloud

图7. Happy Buddha点云

Figure 8. Cochlea point cloud

图8. Cochlea点云

Figure 9. Bun000 and Bun045 point cloud

图9. Bun000和Bun045点云

由表2可知，对于各点云，3DSC算法在精度上表现最优，但同时耗时也远多于其他算法；而PFH算法相对于FPFH算法精度略高，但耗时也较多；本文所提GA-IMP算法则在保证精度与FPH和3DSC相近的情况下，耗时基本稳定在24 s左右。

Table 2. The registration results for different algorithms

表2. 不同算法配准结果

FPFH算法是基于PFH算法对特征进行了简化，因此牺牲了一定精度，提高了配准速度；3DSC算法则采用了一种针对形状轮廓的特征描述，获得的特征较为复杂；这三种算法都需要对点云进行特征提取，而特征的计算往往需要大量的时间，且根据不同形状所需时间差异较大；例如Dragon和Happy Buddha模型表面变化较大，细节较多，因此需要进行特征提取的方法耗时就会显著增加。

本文所提的GA-IMP算法只需要计算总点云滤波后点的数量，时间复杂度低，耗时主要取决于遗传算法种群数量和迭代次数，对于模型表面复杂程度不敏感，鲁棒性较强。

4. 结论

为了避免ICP算法可能陷入局部最优以及配准时间不稳定的情况，本文采用遗传算法和迭代最少点相结合的GA-IMP粗配准算法搭配ICP精配准算法共同完成对点云的配准。通过对不同的点云进行试验，结果表明该算法适用于不同的模型，在保证精度的同时，耗时根据种群数量和迭代次数保持在24 s左右，证明了该算法的有效性和稳定性。

但该算法也存在不足，遗传算法部分的种群数和迭代次数，以及迭代最少点算法部分的体素栅格边长等，都是影响算法速度的重要因素。现阶段这些参数都基于人工设置，如何自动根据不同的点云去计算得到合适的参数，则是下一步需要研究的内容。