庞正雅 周志峰 钱莉

摘 要：由于激光雷达等扫描设备得到的点云存在数据量大、数据中掺杂噪声较多等一系列问题，提出一种基于特征点保持的点云精简与配准方法。首先利用K-means算法对所有点云数据聚类，滤除掉噪声点云，再进行精简化处理;随后在精简的基础上用KD-tree对数据进行最近邻搜索以加快对应点查找速度，从而为配准节省一定的时间;最后根据欧氏距离选择合适的初值减少匹配误差。实验结果表明，精简后的点云数据保持了基本特征，一定程度上减少了配准时间和误差。

关键词：K-means聚类;kd-tree;点云精简;点云配准

DOI：10. 11907/rjdk. 182261

中图分类号：TP301

文献标识码：A文章编号：1672-7800（2019）006-0025-04

Abstract： Because of  the point cloud obtained by scanning equipment such as laser radar has a series of problems， such as large data volume and high doping noise in data， a point cloud simplification and registration method based on feature point preservation is proposed. Firstly， K-means algorithm is used to cluster all point cloud data， filter out noise point cloud， and then simplify the processing.Then， on the basis of simplification， KD-tree is used to search the nearest neighbor of data to speed up the search speed of corresponding points， so as to save some time for registration. Finally， the matching error is reduced by selecting the appropriate initial value according to Euclidean distance.The experimental results show that the simplified point cloud data maintain basic characteristics and reduce the registration time and error to some extent.

Key Words： K-means clustering;KD-tree;point cloud simplification;point cloud registration

0 引言

无人驾驶汽车是人工智能的重要应用，激光雷达技术对无人驾驶安全技术起着关键作用。由于激光雷达等扫描设备得到的点云存在数据量大、数据中掺杂噪声较多等一系列问题，因而在获取点云时无法从一个角度获取完整的点云数据。实际应用中通常通过多角度采集点云数据，然后将多个视角下的数据整理到同一个坐标系下通过配准技术获得完整的点云。因此，如何对数据密度大且噪声多的数据实现去噪、精简、提高匹配精度和减少匹配时间是研究重点。

Hao Song[1]提出最小化输入和简化数据集之间的几何偏差，本质上是将输入数据集划分为固定数量的点集群，每个点集群中选取一个点作为点集群代表，然后将这些代表的集合视为简化的数据集，并根据每个集群的输入数据集对结果的几何偏差进行评估，但是当点数越来越小时这种方法可能失效。文献[2]首先采用表面法向估计方法处理数据中几何奇异性点云，然后基于改进的主成分分析法将点云去噪问题约束为非线性最小二乘法问题，从而实现点云去噪。Benhabiles等 [3]提出了一种基于聚类和由粗到细方法结合的快速点云简化算法，可简化尖角点密度高、平坦点密度低的点云。在点云的配准算法中，应用最广泛的是1992年提出的ICP算法[4]。但是传统的ICP算法存在明显缺陷，对运算初值的选择非常严格，并且需要遍历模型上所有的点，不仅配准消耗时间长，并且很难得到全局最优解[5]。文献[6]、[7]基于一种新的低重叠率多视点集配准方法，通过对点对的曲面分类、曲率和邻域曲率的匹配，选择重叠区域并利用重叠区域中的点搜索最优配准参数。

国内对点云数据的精简与配准研究比国外晚，成果相对较少。文献[8]利用K-means聚类算法在空间域内聚集相似点，利用最大法向量偏差作为聚类散度的度量，将聚类点集划分为特征域中的一系列子簇。但由于采用的是最大法向量，所以当噪声较为严重时该方法存在误差。文献[9]、[10]基于法线角和信息熵理论推导出点的重要性，删除其中最不重要的點并逐步更新法向量和重要值，直到达到用户指定的还原比率。文献[11]利用体素内部和外部的斥力约束，基于一种迭代重采样方法将重采样点投射到所有可能的表面。该方法基于几何处理，无法判断是否存在孔洞，也无法确定孔洞是否由于遮挡或扫描问题造成。文献[12]是基于熵准则遗传算法的点云粗配准算法，即使只有少部分的点云数据重合或含有噪声点云数据，配准效果也不错。文献[13]提出了基于点云特征的ICP算法，利用待测点云的曲率、面法线、点云密度等几何特征，寻找两点云的相关性，将几何特征引入误差函数中，实现两点云的精确配准。文献[14]、[15]在ICP算法基础上提出一种迭代最近线算法，利用两点云之间的连线作为配准依据，但是无法保证线段之间的对应关系。

综上所述，为有效提高点云数据处理效率，本文利用K-means聚类算法对点云数据聚类，滤除掉噪声点云，再进行精简化处理。在精简的基础上用KD-tree对数据最近邻进行搜索，加快对应点查找速度，从而为配准节省一定的时间，最后根据欧氏距离选择合适的初值减少匹配误差。经过验证，本文算法稳定，在大规模的点云数据精简后点云数据仍保持基本特征，且精简后的数据配准效果较理想。

1 点云去噪与精简

1.1 K-means聚类算法

1.2 点云去噪

在激光雷达采集点云数据过程中，由于设备精度、人为因素、环境因素等影响，最终得到的点云数据有密度不规则、数据中掺杂噪声较多等一系列问题。点云数据还存在离散点，这是由于外部干扰如视线遮挡、障碍物等因素影响而产生的离被测物点云较远的点。这些点有两个特点：①远离表面点云;②与相邻点云连接形成的区域不平坦，因此通过计算欧式距离和曲率作为判断噪声点的标准。

算法流程：①设聚类后得到的一个点云集合为：[S=][{pi，i=1，2，？n}]，求每个点[pi]的K-1个[pj]邻近点集;②计算[pi]到其K-1个邻近点集的欧式距离，求k-1个欧式距离的平均值，记为该点的K邻近点距离[di];③计算所有[pi]的K邻近点距离的均值[μ=1Ni=1Ndi]和标准方差[σ=][1Ni=1N（di-μ）2];④通过均值和标准方差共同决定阈值，当点的K邻近距离比阈值大时则判断为噪声点。

1.3 点云精简

随着市场上激光雷达扫描系统扫描速度和精度的迅猛发展，快速获取目标物体的高精度海量点云已不是问题。但是如果直接对海量数据进行点云重建，会因为数据量密集而影响处理效率，严重阻碍特征信息的提取。为加快配准、曲面重建、形状识别等算法速度，必须在尽量保留点云数据特征信息的前提下，滤除大量冗余数据以减少点云数据量[17]。

本文使用体素化网格方法对点云进行精简化处理。首先对聚类去噪后的点云数据创建一个三维立方体集合，其体积按照具体情况设定;然后用三维立方体的重心近似表示立方体范围内的其它点，这样该三维立方体内所有点均可通过一个重心点最终表示。对所有三维立方体都进行处理后则可得到过滤后的点云。

2 点云配准技术

激光雷达采集点云数据过程中，由于采集环境光照不均匀、扫描物体的角度、被测物体被遮挡等因素，无法从一个角度得到完整的点云数据，因此实际应用中通常是多次、多角度采集点云数据，然后将多个视角下的数据根据变换矩阵整理到同一个坐标系下，通过配准技术获得完整的点云[18]。

点云配准方法包括两两配准、对应估计、迭代最近点算法、采样一致性初始配准算法等，经常使用的是迭代最近点算法。迭代最近点算法是基于最小二乘法的最优配准算法[19]，主要是将两个不同坐标系下的点云经最小二乘法提供的变换矩阵，旋转、平移后得到二者重叠部分。虽然传统的迭代最近点算法配准时精度可达到一定要求，但效率较低。

ICP处理流程如下：①减少初始点云数据数量;②确定初始对应点集;③去除错误对应点对;④坐标变换求解。这4个步骤中求最近点集耗费的时间较多[20]。本文首先在目标点云中寻找若干特征点，采用kd-tree对数据最近邻搜索以加快对应点查找速度，从而为配准节省一定的时间;然后根据欧氏距离选择合适的初值减少匹配误差。

算法流程：①减少初始点云数据量，读取精简后的目标点集[Xt]和参考点集[Yt]，并对[Yt]建立KD-Tree;②通过点的曲率特征，从目标点集[Xt]随机选取N个特征点记为[Xt];③计算特征点集[Xt]中的每一点[xi]到[Yt]中每一点[yj]的距离，找出[xi]到[Yt]距离最短的点[yj]作为匹配点对，并计算匹配点对的曲率相似度;④根据最小二乘法计算得到的旋转和平移矩阵，进行特征点坐标转换;⑤迭代直到满足误差最小为止。

坐标系旋转变换原理如图3所示。设目标点集[Xt]里某一点在[XOY]坐标系下的坐标为[（x，y）]，直角坐标系旋转[θ]角度后在[XOY]坐标系下的坐标为[（x1，y1）]，通过点[（x，y）]和旋转角度可得到[x1]、[y1]的值。

3 实验结果及分析

本文基于Windows7系统进行实验平台搭建，首先在Windows下安装VMware-workstation并在虚拟机VMWare上运行Ubuntu 14.04，然后在Ubuntu 14.04下安装一些必要的环境工具，如CMAKE、QT、VTK、boost库等，最后安装PCL 1.8.1、Microsoft Visual Studio 2013。仿真实验主要利用C与C++语言，结合PCL库，在虚拟机环境下利用Microsoft Visual Studio 2013开发平台进行编程开发实现。

首先滤除桌子点云数据中的噪声点，如图4所示。图4（a）中初始点云共有460 400个数据，图4（b）中经过去噪后的点云共有451 410个数据，图4（c）为被去掉的噪声点云，共8 990 个数据。

然后对滤除噪声数据的点云進行精简化处理，在保留点云数据特征信息的前提下，对过密的点云数据进行精简，去除大量冗余数据，如图5所示。图5（a）中白色为初始点云共451 410个数据，绿色为经过精简后的点云共  36 993个数据，虽然只保留了原来数据的1/12，但从图5（b）中可以看出，点云的边缘和特征信息得到很好的保留。最后对精简后的数据进行配准处理，如图6所示。图6中白色点云为原始点云，绿色点云为经过一定转换后的目标点云，红色为配准后的点云。经过24次迭代后完成配准，误差值达到最小（见封二彩图）。

本文还对不同数据量的点云进行配准比较。图7、图8、图9分别是对bunny、horse、dragon数据的配准。表1为以上数据的配准结果。

4 结语

本文对点云数据进行了聚类、去噪和精简化处理，并对精简后的数据进行配准。通过上述实验结果可知，基于特征点保持的点云精简与配准方法对于大规模的点云数据去噪和精简效果都很好，且减少了配准时间。

本文虽然一定程度上提升了配准速度和精度，但点云配准算法本身具有一定的复杂性，使得在配准数据量庞大的点云时没有明显效率优势，这是下一步工作改进方向。

參考文献：

[1] HAO S，HIS Y F. A global clustering approach to point cloud simplification with a specified data reduction ratio[J]. Computer-aided Design，2008，40（3）：281-292.

[2] CASTILLO E，LIANG J，ZHAO H. Point cloud segmentation and denoising via constrained nonlinear least squares normal estimates[M]. Germany：Springer Berlin Heidelberg ，2013.

[3] BENHABILES H， AUBRETON O， BARKI H， et al. Fast simplification with sharp feature preserving for 3D point clouds[J]. International Symposium on Programming and Systems （ISPS），2013（11）： 47-52.

[4] BESL P，MCKAY N D. A method for registration of 3D shapes[C]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1992：239-256.

[5] 杨现辉，王惠南. ICP算法在3D点云配准中的应用研究[J]. 计算机仿真，2010，27（8）：235-238.

[6] LI Q D，GRIFFITHS J G. Iterative closest geometric objects registration[J]. Computers and Mathematics with Applications，2000，40（10）：1171-1188.

[7] GE X M. Non-rigid registration of 3D point clouds under isometric deformation[J].  ISPRS Journal of Photogrammetry and Remote Sensing，2016（121）：192-202.

[8] SHI B Q，LIANG J，LIU Q. Adaptive simplification of point cloud using K-means clustering[J]. Computer-aided Design，2011，43（8）：910-922.

[9] HAN H Y，HAN X，SUN F S，et al. Point cloud simplification with preserved edge based on normal vector[J]. Optik - International Journal for Light and Electron Optics，2015，126（19）：2157-2162.

[10] WEI X，HUA X G，CHEN X J. A new progressive simplification method for point cloud using local entropy of normal angle[J]. Journal of the Indian Society of Remote Sensing，2018，46（4）：581-589.

[11] LI M L，SUN C M. Refinement of lidar point clouds using a super voxel based approach[J]. ISPRS Journal of Photogrammetry and Remote Sensing，2018（143）：213-221.

[12] 陈杰. 散乱点云配准技术优化研究[D]. 绵阳：西南科技大学，2018.

[13] HE Y，LIANG B，YANG J，et al. An iterative closest points algorithm for registration of 3D laser scanner point clouds with geometric features[J]. Sensors （Basel， Switzerland），2017，17（8）：1862-1865.

[14] WU Y F，WANG W，LU K Q，et al. A new method for registration of 3D point sets with low overlapping ratios[J]. Procedia CIRP，2015（27）：202-206.

[15] JOAQUIM SALVI，MATABOSCH C，DAVID FOFI，et al. A review of recent range image registration methods with accuracy evaluation[J].  Image and Vision Computing，2006，25（5）：578-596.

[16] 杨辉华，王克，李灵巧，等. 基于自适应布谷鸟搜索算法的K-means聚类算法及其应用[J]. 计算机应用，2016，36（8）：2066-2070.

[17] 李仁忠，杨曼，刘阳阳，等. 一种散乱点云的均匀精简算法[J]. 光学学报，2017，37（7）：97-105.

[18] 孙威，黄惠. 机器人辅助的三维点云自动配准[J]. 集成技术，2015，4（6）：37-45.

[19] 邱世聪，罗意. 改进ICP算法的点云配准[J]. 河南科技，2017（7）：40-42.

[20] 戴静兰，陈志杨，叶修梓. ICP算法在点云配准中的应用[J]. 中国图象图形学报，2007（3）：517-521.

（责任编辑：杜能钢）