尺度可变的快速全局点云配准方法分析

覃锡森

广东省国土资源测绘院 广东 广州 510599

1 研究背景

通过查阅相关资料，处理三维点云模型配准的研究非常广泛，迭代最近点“Iterative Closest Point，ICP”是使用最广泛最经典的形式[1]。但是这一优化过程中有非凸性质，基于局部的搜索不够全面，局部获取信息有限，在信息的限制下局部配准不全面，无法满足精准性，加上噪声存在，明显地影响了配准结果，基于全局优化的角度出发，以点云配准方式就可以解决上述问题，但是解决空间会随着点云规模增大，导致迭代算法的使用效率低下，甚至无法得到目标结果。

2 配准方式

2.1 局部配准方式

局部配准中，以ICP为主，这种局部搜索为迭代方式的配准方式整体呈现出非线性特征，如果使用中初值不确定，很难得到最优配准，且对噪声、重合区域等都很敏感。在后续的研究中，需要逐步进行改进从而克服这些缺陷，借助Robust Kernel函数对目标函数进行非线性优化可以改变所存在的缺陷，且其配准性能具备良好的抗噪能力。除了Robust Kernel之外也可以加入点云法向量、颜色等辅助信息提升配准结果，另外正态分布变换方法Normal Distributions Transform,NDT也可以实现配准。基于统计学算法的配准将配准问题转化为概率密度函数，并得到优化后的高斯混合模型，该点云配准方式的优势在于不用建立两片点云模型间的点点对应，从而避免了噪声等错误问题，提升了Robust Kernel性。

2.2 全局配准

为避免初值等因素对配准所产生的影响，因此出现了全局配准研究，该研究的范围比较广，如Branch-and-Bound, BnB、模拟退火法等，全局配准都是找到两片点云的配准误差度量函数最小值，虽然效果良好，但是缺陷在于全局优化需要消耗更多时间，以及大量数据的处理很难完成。为实现这一方面，人们采用在原本的研究基础上进行特征空间的初始配准，建立其对应关系来解决配准的问题。虽然人们提出了不同的解决方式，但是由于尺度不一致等问题，导致点云匹配的问题仍旧存在，无法得到精准配准后的结果。

3 算法

假设数集P、Q，两者之间可以建立对应关系，其对应关系为K={(p、q)|p∈P,q∈Q}，计算中最佳缩放用s表示、旋转为R、平移用T表示，通过对应点的均方误差计算Mean Squared Error最小表示为：

考虑实际物体建模的需要，配准中的K值并不确定，运用最小二乘的意义下优化会因为受到噪声的限制导致优化不理想。为兼顾鲁棒性与优化效率，顾虑全局配准可能会减少这些不理想因素，因此优化函数的计算形式为：

4 配准中局部特征的降维、配准

其特征对应关系K由所描述子集来决定，这里论述其细节；假设点云P、Q，其特征描述为

其匹配可以分为三步：①将L2距离最近的F（q）的最近点设置为集合K2；②在集合K1里加入每一个子集，如果F（q）是最近点，也加入到K2中；③在K2中随机选择三个子集，将其标记形成对应三角，分别记为Tp、Tq，根据匹配关系导出对应，计算其比例，对其进行验证。由于尺度不一致，正确的匹配管理可以保证对应的三角形，验证其相似性。运用分类法来进行分析，可以分为Signature、Histogram两类，其中Signature的描述极强，但Histogram的鲁棒性特征更强，因此配准更全面，但是因为描述性不强而存在错误配准的可能，Signature的描述性更强，配准成功概率也更高[2]。针对不同类型的点云数据选取不同的特征描述子部来得到足够多的配准数目，能够得到正确的比例关系，确保后续推算的精准。为得到更好的效果使用高效的优先搜索算法，通过加速分析计算，该方式建树与查询复杂度均与子维数成正比，要求建树复杂度与点云成正比，而完成大规模点云的CSHOT描述子配准需要消耗大量时间，这是三维建模中端到端处理的瓶颈。

两片点云表现三维图形的过程存在相似性，CSHOT描述运用在高维空间分布呈现出明显的可循规律，因此用来进行降维处理将会取得更快的配准效果。

5 目标函数计算

在不考虑尺度变化对上述公式的优化，但是引入尺度缩放变量之后无法以线性方程来表示空间变换增强，因此必须考虑尺度的方式。通过优化步骤，不增加算法复杂度的基础上对所放量优化。通过将线过程与稳健统计相结合给出求解方式，以构造特征的对应关系K的权重结合L＝｛lp、q｝，将得到优化后的变量与联合目标函数：

为优化E，将关于化整为零，整理得到目标函数最小数值，目标函数最小用lp、q来表示：

其中，s、R、T均是迭代步的值，是为固定相。从上述表示可以看出lp、q来表示的数值与点云对应点距离间呈现反相关，视为对应点的权重趋向于错误匹配点的无效化。在研究中，逐渐减少的数值，可以在配准优化中减少噪声与异常点所产生的影响。

在计算中，合成数据集中进行测试，得到了优化之后的配准情况，实验中的25组数据计算之后，标准差配准重叠区域47%～90%之间[3]。由于该数据的分析不考虑颜色信息等，这以数据集的测试数据间没有尺度差异，在无尺度差异中取得了极好的精度、时间效率。

6 结束语

综上，在设计分析中，尺度可变的全局快速配准算法能够得到理想成果，且与最终的计算目标相近，最终获得数据证明尺度可变的全局配准方式可以取得理想效果。但是在研究中应注意配准结果依赖特征匹配结果，因此选择好的特征描述也是决定配准质量的关键。在充分借助计算机技术的基础上，仍旧需要研究针对局部特征描述探索好的配准结果，解决这一问题需要具备理论作为基础。