保留灰度特征的配准点云数据精简算法∗

仇倩雨 黎 宁 李亚红 李明磊

（南京航空航天大学电子信息工程学院 南京 211106）

1 引言

近几年，随着3D 传感技术的迅猛发展，点云成为三维物体及其周围环境的一种重要而有效的表现形式，广泛应用于诸多领域，如虚拟现实、3D 打印、移动道路测量和历史文物扫描［1］等。

典型地，我们可由激光扫描仪从真实物体的表面捕获原始数据点，并在几分钟内产生包含数百万个采样点的点云，这些点云通常是无序的。同时，对于复杂物件，我们需从多个视点扫描，并将其进行配准。Besl和McKay［2］于1992年提出的ICP算法是最经典的点云配准算法，但其全局最优的收敛性和运行速度严重依赖于初始配准位置。因此，在此基础上许多改进的方法被提出，Chetverikov［3］提出按照配准的重叠率保留用于计算变换参数的点数，从而解决部分重叠点云的配准问题；戴静兰［4］等在利用主方向贴合法完成粗略配准后，根据曲率特征点及KDTree 查找最邻近点，有效地提高了ICP 算法的效率；Per Bergström［5］等通过迭代重加权的最小二乘法来提升配准的鲁棒性。李彩林［6］等在已知点云配准初值的基础上，实现了一种自动全局优化的整体配准方法，用于处理无序的多视角激光扫描的三维点云。周朗明［7］等提出了基于旋转平台的点云数据配准策略，不需要提取点云特征完成匹配，只需记录旋转平台每次转动的角度，以此来推导多视点云间的旋转矩阵，从而完成自动配准。然而，经过配准最终获取的点云不可避免地存在数据冗余，庞大的数据量会影响后续处理的运行效率。同时，由于配准存在的误差及厚度和间距间的不均匀分布等问题，会导致法向量计算的不准确。而三维点的定向法向量在物体识别和表面重建中至关重要，因为它们提供了局部表面信息并且帮助区别底层形状的内部和外部［8～9］。因此，提升配准后的点云的分布质量，对点云进行精简是点云数据处理的一个重要课题。

针对过密的散乱点云数据，国内外许多学者已经提出了大量的精简算法。Sun［10］等提出了包围盒法，通过对点云建立最小包围盒并将其划分为多个小栅格，用距离栅格中心最近的点来代替栅格中的所有点来实现点云的精简。在此基础上，李忠仁［11］等结合包围合法对输入数据进行K 邻域距离计算法线估计来确定栅格重心，以重心代替中心作为栅格内的保留点，能够较好地保留数据的几何特征，但是此类方法特征丢失较严重。因此，Lee［12］等提出非均匀栅格法，通过计算栅格内数据点的法矢偏差，将大于阈值的栅格继续划分来实现部分模型特征的保留。Song 等［13］根据每点是否可以由其邻域内的点代替来评估每点的重要性，迭代去除重要性小的点，可在简化点云的同时保留其尖锐边缘，但是对时间和内存的消耗很大。Benhabiles［14］等通过基于体素的聚类算法，利用曲率将点云划分为尖锐边缘点和简单点，实现保留点云尖锐特征的快速精简。陈龙［15］等提出了一种自适应K-means 聚类点云精简算法，通过混合多判别参数法［16］提取点云数据内的尖锐点及边界特征，然后利用自适应八叉树提供初始化聚类中心，将曲率差大于阈值的聚类继续迭代细分，以此保留点云的细节特征。傅思勇［17］等提出了一种基于栅格动态划分的点云精简方法，用栅格内点平面拟合后的平整度代替点云的微分信息来区分特征和非特征区域，再根据区域采取合适的精简方法，以此提高精简后模型的偏差。

然而，当前主流的点云精简算法没有考虑精简后点云分布的均匀性，均匀分布的点云能够增加点云法向量估计的准确性，提高后续处理的可靠性。同时，很多点云精简算法没有考虑灰度信息，而灰度信息作为点云的一种重要特征在某些实际应用中不可或缺。因此，本文针对配准后厚度和间距分布不均的点云数据，提出了一种有效的点云精简算法。首先，利用基于体素格的方法生成一个粗点云，然后将其投影到给定的点云上，用每点领域内的近似重心点来代替原点位置。同时，加上正则化约束，掺入局部排斥力为距离过近的点增加罚项来保证点云的均匀分布，通过不动点迭代算法实现点云的重采样。最后，利用KDTree 在初始点云内查找重采样后点的最邻近点，将最邻近点的灰度信息映射至重采样后的点。针对配准后点云数据的特点，本文算法通过以上三个步骤，获取分布密度均匀，同时保留原始形状及灰度特征的点云。

2 算法介绍

本算法用于解决配准后点云存在的数据冗余及厚度和间距间的不均匀分布等问题。算法利用体素栅格及重采样步骤中关于重心点处理的相关性，将两者结合，利用体素栅格下采样后的数据作为LOP 算法的初始迭代点云，加快迭代速度。同时，在改善点云分布情况基础上，可以通过控制栅格大小直接决定点云精简的比例。算法输入配准后的点云，输出一个新的点集，保持原点云的形状和灰度，同时使点云的分布密度均匀。

2.1 体素格下采样

点云配准将从各角度获取的点云数据转换到相同坐标系下，由于重叠区域的存在，配准后的点云必然存在冗余的部分，为后续处理的计算增加了难度。对于给定的点集，可以利用基于体素栅格的方法进行下采样，通过控制体素栅格的大小来决定下采样的比例，在减少数据量的同时保持点云的形状特征。

我们可以通过以下几步完成体素栅格的创建及点云的下采样。首先根据点云数据在xyz 三个方向的最大及最小坐标值计算包围点云的最小边界框盒，框盒的边长定义如下：

其中，λ 是修正边长的参量，用于保证数据包含于框盒的内部。然后将框盒划分为若干个边长为d的三维体素栅格，d 的选值与点云的平均密度成反比，定义如下：

其中，α 是比例因子，用于控制下采样的比例；s 是比例系数；N 表示点云数据中点的总数。体素栅格划分完成后，去除没有数据点的小栅格。对于现存的小栅格，将距离重心最近的点保留，去除栅格内的其他点，以实现点云的下采样。

采用体素栅格进行下采样的原因如下：首先，经过体素栅格下采样后的点云可以覆盖原点云的整个表面，符合采样前的几何特征。其次，根据式（2）的变形，简单地通过调整体素栅格d 的大小即可控制下采样的比例，从而控制点云数据下采样后的密度。图1 通过经典的bunny模型展示了体素格边长的大小对下采样率的影响。其中，bunny 模型的Lx=0.12，Ly=0.15，Lz=0.15 ，N 约为3.6 万。当体素边长选择0.002 和0.004时下采样的比例分别为50%和10%。

图1 不同体素大小对bunny模型的下采样率的影响比较

2.2 点云重采样

经过上一步的操作，可以滤除大量的冗余数据，但是点云不均匀分布的问题没有得到很好的改善。Lipman［18］等于2007 年提出LOP 算子，将其用于点云的几何重建。本文应用与其相似的数学机制，来解决配准后点云数据分布不均的问题。

式（4）的右边两项形式相似，但是表达的意义不同，第一项可以理解为每点领域内的近似重心点，使得结果对离群点及噪声具有鲁棒性；第二项是正则化约束项，通过掺入局部排斥力为距离过近的点增加罚项来保证点云的均匀分布。我们可以通过调整参数μ 的值来调整两项间的平衡。根据经验，通常选取μ=0.45 可以获得较好的效果。收敛时，就是最后重采样的结果点。

2.3 灰度映射

点云在重采样的过程中，不动点迭代算法仅考虑了点与点之间的位置信息，因而会丢失灰度信息。由于点云重采样的过程可以看做是对配准点云的投影，因此重采样后的点云与配准点云位于同一坐标系下相同的空间位置。为了获取精简后点云的灰度信息，本文在配准点云数据内查找距离重采样后的点最近的点，将最邻近点的灰度信息映射到重采样后的点上。为了加快最邻近点的搜索速度，本文采用了一种分割k 维数据空间的数据结构KDTree，省去对大部分数据的搜索，从而减少计算量。具体步骤如下：

1）对配准点云数据构建KDTree；

2）对重采样后点云数据内的每一点，根据欧式距离在配准后点云数据内搜索最邻近点；

3）将最邻近点的灰度值映射至重采样后的点云。

3 实验结果与分析

我们利用多种真实世界的点云数据来测试本文提出的方法，实验结果证明我们提出的点云精简算法的有效性。

图2 通过水杯点云数据来展示本文提出方法的主要处理步骤。输入的点云数据如图（a）所示，该数据是基于结构光［19］的三维重建实验平台［20］获取的多角度点云配准结果，点云数据量约为22 万个，图（c）用深色标注出由于配准造成的重叠区域，该部分属于冗余数据。结合图（c）及图（a）的放大区域，我们可以看出点云分布不均匀，因配准造成的重叠区域的点云密度大于非重叠区域。为了获得分布均匀且保持原有几何和灰度特征的点云数据，首先，我们利用体素栅格对输入数据进行简化，选取的体素栅格的边长为0.8mm，下采样后的结果如图（d）所示，下采样后的点云数据量约为6.3 万，该步骤在去除大量无用数据的同时保留了形状特征。然后，我们经过一个迭代投影步骤重采样（d）中的点云数据，通过平衡原始分布和点与点间斥力的约束，生成一个分布均匀的新点集，如图（e）。最后，为了恢复重采样后丢失的灰度信息，利用KDTree 在输入点云内搜索（e）内各点的最邻近点，并将灰度信息进行映射，最终得到的点云数据如图（b）所示。与原始数据相比，简化率约为71.36%，精简后的点云保留原始的几何特征和灰度特征。同时，根据图（a）和图（b）的放大部分可知，由于配准造成的重叠区域数据冗余及点云密度不均的问题得到了解决。

图2 使用本文算法对水杯数据进行实验得到的结果

为了说明本文方法对于点云精简均匀性方面的优越性，我们将本文算法与文献［11］及经典的移动最小二乘法（MLS）［21］进行对比。开源点云库PCL 内的Surface 模块内的模板类Moving-LeastSquares 提供了一种重采样方法，通过对点云进行MLS映射，可以用于精简配准后的数据。我们这里采用定量的度量规则，数据点到邻域点距离的平均标准偏差来评价点的分布情况，表达式如下：

其中Npi表示pi点的邻域表示点集内元素的个数，μ 表示pi与其邻域内点距离的均值。σˉ越小表明点的分布越均匀。具体的对比结果如图3 及表1 所示，图（a）为机械部件点云数据模型，该数据是基于结构光的三维重建实验平台获取的多角度点云配准结果，点云数据量约为46 万，数据点到邻域点距离的平均标准偏差为1.08mm。图（b）、（c）、（d）分别是文献［11］、MLS 方法和本文方法精简后的点云模型，在简化率均为84%左右时，通过式（5）计算可得，模型数据点到邻域点距离的平均标准偏差分别为0.544mm、0.537mm 和0.421mm。由此可得，通过本文模型精简后的点云较文献［11］和MLS方法而言分布更加均匀。

图3 机械部件点云数据实验结果

表1 算法均匀性比较

本 文 的 实 验 平 台 为Intel（R）Core（TM）i7-6500U CPU@2.6GHz，8GB 内存，Windows 10，64位操作系统。表2 展示了图2、3 中例子的统计信息。根据表2 内的结果可知，我们可以通过控制体素栅格边长的大小来决定点云下采样率，体素格边长越大，点云的简化率越高。同时，通过对比处理前后σˉ的计算结果可知，精简后的点云分布较初始点云相比更加均匀。

表2 实验统计结果

此外，我们还分析了精简操作对法向量估计的影响，如图4 所示。我们展示了原始点云的法向量结果和精简后点云的法向量结果，法向量的计算均采用经典的加权PCA 法［9］。由于配准造成的误差及密度分布不均等问题，计算出的法线结果在点云重叠区域存在明显的错误和噪声。这些会干扰诸如特征提取、表面重建等后续处理。而经过本文算法处理后的数据有均匀的点分布，去除了重叠区域的冗余数据，提高了法向量估计的准确性，增加了后续处理步骤的可靠性。

图4 点云法向量估计

4 结语

在本文中，我们提出了一种有效的配准点云数据精简算法，用于处理配准后的点云数据，解决其存在的数据量过大、点密度不均等问题，同时可以保留点云的灰度特征。本算法结合了体素栅格法与基于能量优化的LOP 算法的思想，并应用基于KDTree 的最邻近搜索，以此来获取保留初始点云形状及灰度特征同时分布均匀的点集。实验结果表明，本文的算法能够成功应用于各类配准后点云数据的精简。此外，它可以为常规的点云处理技术提供精确的数据点，如法向量估计，物体识别和曲面重建。