ICP系列算法的描述与对比

摘  要：根据当前计算机技术的发展，实体模型数字化产出得到了越来越广泛的应用。该文主要是针对这一应用研究了ICP算法的原理以及使用场景。实践验证ICP算法产出实体模型的过程，并加深了对ICP算法的理解。在经典ICP算法的基础上，研究了基于邻域的ICP算法的特性以及优点。在该文中，也研究了GA（遗传算法）的原理。它主要是基于生物遗传进化特性进行高效精确查找的算法。GA与ICP特性相结合，可以通过遗传算法原理精确找到点云中匹配的点的集合所构成的几何体。

关键词：ICP  GA  遗传算法  邻域

中图分类号：G423                                  文献标识码：A                          文章编号：1672-3791（2019）03（b）-0024-02

经典ICP算法是将不同坐标系中的点云数据转换为同一坐标系，并以最小的存储成本，获得精确的几何结构或拓扑结构。

在物体模型采集的过程中，因为各种各样的情况，如采集物体的体积较大或者本来就是破损为多各部分的物体无法单次完成，需要在多次采集后进行集成，然后需要将不同坐标系中的点集成到一个坐标系中，并精准地得到几何结构。

ICP算法是建立在有特征的点云基础上的算法，其是一个理想状态下的对应点云算法。使用四元数旋转模型点云数据并平移得到新的点云。对应的点集注册算法主要是计算qR和qT，知道这两者后遍可以匹配点云。然而，对应点集匹配算法的前提条件是计算中的点云数据PB和PR元素是一一对应的。由于诸如现实中的错误之类的问题，这种情况不太可能是实线，因此存在了ICP算法。

1  算法描述

1.1 GA算法

GA算法（Genetic Algorithm）即遗传算法。顾名思义，遗传算法其实源自于生物学所应用到的生物界遗传与进化机制的计算模型。该算法的本质就是通过类似于自然遗传进化的过程搜索出最优的结果。它首先根据一个可能有问题的组，再通过每个染色体对应的遗传规则算法制定解决方案。因此，从基因组到其解决方案的映射形成了一个映射。遗传算法的过程可以看作是在多变量函数中找到最优解的过程。可以尝试构想一下，在一个多维的表面上有无数的“山峰”，这些峰对应于局部最优解。而且还会有一个海拔最高的“山峰”，那么这就是全球最优解决方案。遗传算法的宗旨就是根据遗传规则尽可能地爬到最高峰，尽量避开干扰，不去落到一些小峰。此处需要留意的是遗传算法并不是一定要找到“最高峰”。如果问题的评估是尽可能小的话，那么全局最优解就应该是函数的最小值。当前情况下，遗传算法有许多有趣的应用，例如：寻路问题、8个数字问题、囚徒困境、找到圆的中心（在不规则的多边形中，查找多边形中包含的最大圆的中心）、人工生命模拟、TSP问题、运动控制、生产调度问题等。

GA算法的步骤是在特定编码方案下随机生成初始组，并使用相应的编码方法将编码的个体转换为问题空间的决策变量。并根据某种选择（即适者生存的原则）找到个体的适应值，选择一些个体形成交配池，由两个遗传算子交叉和变异操作，以随机配对交配池中的两个个体。从一些现有的父亲和后代中形成新一代人口，选择一些最好的人作为新父母，重复步骤2到4，将它们代代相传，直到满足收敛判断。

遗传算法中，主要有以下3种类型的操作：选择，交叉，变异。其中最基本的操作为选择和交叉，这两种操作就可以基本上完成遗传算法的大部分搜索功能了。变异功能则提高了遗传算法找到最優解的能力，属于锦上添花的功效，变异后被选中的可能性就越大。仔细描述下来，交叉其实是指“替换”和“重组”父类部分的结构，从而产生一个新个体的操作。可以通过交叉操作，极大地提高遗传算法的搜索效率。变异操作的基本过程则是在[0，1]之间rand生成随机数，如果rand [Pm]，则执行变异操作。交叉操作又保证了遗传算法的有效性，相对应的得到保证了遗传算法具有局部随机搜索的能力。同时又使遗传算法能够保持群体的多样性，可以防出现错误的收敛。结合选择和交叉运算符，可以避免由于选择和交叉的操作而导致一些信息不可恢复的丢失。

1.2 ICP算法

ICP算法的本质实际上是基于最小二乘法的最佳配准方法。该算法重复选择对应的点对并计算最优点，直到满足正确配准的收敛精度要求。ICP算法的目的是找到待登记的点云数据与参考云数据之间的旋转参数R和平移参数T，从而在两个数据点之间满足特定度量下的最优匹配。首先计算目标点云的每个点与源点云上的每个点的距离。将每个点与目标云的最近点匹配，从而满足对应点云ICP算法的前提条件，并且每个点具有对应的映射点。然后可以根据相应的点集注册算法计算，但由于这是一个假设，因此有必要重复迭代以运行上述过程。直到均方差误差小于某个阀值。也就是说，每次迭代时，整个模型都接近一个点，每次它再次找到最近的点，然后根据相应的点集批准算法对其进行计数，并比较均方误差并继续迭代。

ICP算法关键点。

首先是原始点集的采集要保证均匀采样，随机采样和法向矢量采样。其次确定对应点集：点到点、点到投影、点到面。计算变化矩阵GA与ICP特性相结合，可以通过遗传算法原理精确找到点云中匹配的点的集合所构成的几何体。二者的相同之处在于该两种算法核心都是快速精准的查找。区别之处在于ICP算法主要是基于二叉树的查找，而遗传算法是基于生物的遗传规则进行多次“优胜劣汰”的比对后输出最优解。鉴于二者核心宗旨都为快速查找，则可将二者结合，找到点云中最优点，形成最终的拓扑图形。

1.3 基于邻域特征的ICP算法

基于邻域的ICP算法可以提高点搜索率并提高匹配点的准确性。空间中的点云数据，如果只有三维坐标的信息而没有其他的拓扑信息，那么空间中的点云无法发挥最充分的利用。因此，在应用ICP算法时，应首先找到与该点相邻的多个点以构建一个小邻域。再通过这个邻域来提取对应的几何信息。点邻域的确定方式有3种：树形存储法、k-d tree法、空间栅格法。

相邻点的计算是整个过程中最长的一步。其过程是：首先找到最近的点并使用k-d树去进行加速搜索，在根据二叉树规则生成构建k-d树的过程。空间会被分成两部分，x的值最接近平均值，然后在分割的子空间中找到Y轴的边界。将它们分成两部分，划分的子空间除以X轴......依此类推，最后在分割区域中只有一点。该分割过程对应于二叉树，并且二叉树的每个叶节点对应于一个点，二叉树的分支节点对应于一条分割线，一个完整的拓扑关系就建立了。

2  结语

该文主要研究了ICP系列算法的应用，以及算法是如何将两个坐标系的点云拟合成同一坐标系的几何体。通过此次研究更理解了ICP的实际用途和原理，也理解了基于邻域特性的ICP算法的优点。研究ICP算法的同时也理解了GA（遗传算法）的原理和使用它们的优点——GA算法基于生物优胜劣汰规则进行一系列筛选对比后输出最优解;ICP算法则是通过对比点云的最优距离等方式形成最小邻域，相似且共通，拓宽了知识面，提高了实践能力和知识结合能力。

参考文献

[1] 王磊，邢渊.反向工程中数据点云的拼合[J].模具技术，2004，6（1）：47-49.

[2] 王蕊，李俊山，刘玲霞，等.基于几何特征的点云配准算法[J].华东理工大学学报，2009，35（5）：768-773.

[3] 高珊珊.基于三维激光扫描仪的点云配准[D].南京理工大学，2008.

[4] 陆秋.基于MapReduce的决策树算法并行化[J].计算机应用，2012，32（9）：2463-2469.①作者简介：刘美池（1995—），女，朝鲜族，辽宁沈阳人，本科在读，研究方向：算法研究。