一种邻域自适应的双阈值点云特征提取方法

周建钊，颜雨吉，陈 晨，杜文超

(陆军工程大学 野战工程学院，江苏 南京 210007)

0 引言

点云数据获取、点云数据处理以及模型重构是逆向工程中必不可少的三个重要环节[1]。其中，点云数据处理是逆向工程中的重要环节，其精度以及效率将直接影响着三维模型的最终效果。在点云数据处理环节中，点云数据的特征提取是其中的一项重要研究内容[2]，为几何分析、数据分割、曲线匹配和拼接、曲面重建等几何处理提供依据，对后期精确的点云配准、模型重建等研究起关键作用。

特征点是最基本的曲面几何形状的特征基元，对于几何模型的外观及其准确表达具有重要作用[3]，点云数据的特征提取是指从点云模型中识别出几何模型的轮廓、尖锐处、凸凹处和过渡光滑处等结构特征及形状特征的过程[4]。特征提取是点云数据处理底层的技术之一，为后续点云数据的存储、图像处理、模型分析、特征点匹配、曲面重建等提供支持。

目前，针对散乱点云特征提取的研究方向可以大致分两类，一类是基于网格模型的思想，将点云数据网格化，再利用网格模型的特征提取方法；而另一类是直接对点云数据进行特征提取，不需要建立网格信息。无论哪种方法提取点云数据特征点，都涉及点云几何参数的计算，计算点云几何参数就要选取采样点局部邻域，局部邻域大小的选择影响几何参数计算精度，同时现有的基于单一特征描述参数的特征提取方法的准确性有待提高，因此研究了一种邻域自适应的双阈值点云特征提取方法，实验证明该方法提高了特征点提取的准确性和稳定性。

1 基于法向量和曲率的特征提取算法

1.1 法向量提取特征点

法向量是点云数据模型中很重要的几何属性，局部邻域内点的法向量夹角可以反映曲面的变化信息[5-6]。图1是法向量反映不同曲面信息[7],区域曲面内法向量变化平缓时，表征该区域比较平坦，法向量变化较大时，反映该区域起伏大，根据邻域k内法向量的变化，设定适当的阈值可识别出点云数据的特征点。

图1 法向量反映曲面信息

求出每个点的法向量，再计算每个点与其邻近点法向量的夹角，定义点云数据中某点pi的法向量变化程度fi如下：

(1)

式中k是指与点pi欧氏距离最近的k个点，θij是指点pi与邻近点pj的法向量夹角，将某点法向量变化程度fi与设定的合适阈值比较，即可有效提取点云数据特征点。基于法向量的特征提取计算简单，但依赖于邻域的选取，同时对噪声较为敏感，对于孤立的特征点因为缺乏近邻点信息所以无法提取，对于细节特征较多、较复杂的点云数据提取效果不佳。

1.2 曲率提取特征点

图2 曲率变化反映特征信息

由微分几何知识可知，曲面的主曲率能够反映采样点处的局部特征，表1列出了点云局部曲面类型与主曲率取值的对应关系，有助于点云局部的初步判断。

表1 主曲率取值与局部曲面类型

曲率提取特征点过程概括如下[8-9]：

(1)以所求点pi为坐标原点，曲面在pi点处的法向量方向为Z轴方向，X、Y轴在pi点处的切平面上，X、Y、Z轴两两正交，建立(X，Y，Z)坐标系。

(2)根据二次曲面基本方程:

(2)

代入邻域点坐标pj(j=1,2,3…)，依据最小二乘法，可求得曲面基本方程。

(3)由曲面基本方程，求方程的一阶、二阶偏导可获得拟合所得曲面的第一基本量(E、F、G)和第二基本量(L、M、N)，结合曲面参数方程可计算出主曲率ρ1、ρ2、高斯曲率τ和平均曲率H：

(3)

(4)将上述计算所得的曲率值与设定的阈值进行比较，保留曲率值大于阈值的点作为特征点。

基于曲率的特征提取方法识别点云特征信息比较准确，对曲面突变区域和平缓区域的细节特征都可以准确提取，可以有效地保留模型特征信息。但是使用曲率提取特征点的方法对噪声点十分敏感，鲁棒性较差，因此采用曲率提取点云模型特征的方法并不适用于含有噪声点的点云数据，同时计算也比较复杂，算法的运行效率不高。

2 自适应邻域选择的双阈值特征提取算法

基于不同特征描述参数的点云特征提取都存在一个共同的过程，就是对特征描述参数的计算，无论是利用法向量、曲率，还是基于其他参数的特征提取，都需要精确地计算这些参数才能保证提取出的特征点的准确性。而计算上述参数的过程中，都涉及采样点局部邻域信息的计算，现有的采样点局部邻域构建方法有两类：近邻点k搜索和半径搜索，如图3所示。近邻点k搜索的原理是查找距离采样点pi最近的k个点，以此构建点云局部邻域；半径搜索是通过查找以采样点pi为圆心，半径为r的球内所有的点。

图3 两种局部邻域搜索方法原理图

然而无论基于哪一种方法，都需要考虑邻域点k的个数或者半径r的大小，目前的处理方法更多地是根据实验的效果，人为主观地进行调整，直到寻找到一个合适的邻域大小，将其应用于整个点云数据的计算。这种方法的缺点有两个方面，一是通过人为调整寻找最佳邻域大小效率低下，存在主观随意性；二是通过此方法获取的邻域大小单一固定，当点云模型较为复杂，局部特征信息较丰富时，单一的邻域大小难以保证整体模型处理的效果，并影响后续过程的结果。因此寻找一种适应不同情况可进行调整的自适应邻域选取方法十分必要。

根据单一的特征描述参数对点云数据特征进行提取，得到的特征点冗余数据多，存在非特征点误识别的情况，在稳定性、准确性方面都有一定的局限性。基于以上两个方面的考虑，本文利用自适应邻域选择结合法向量和曲率双阈值判别，提出一种新的特征提取方法，并通过实验验证方法的可行性。

2.1 基于局部邻域熵函数的自适应邻域选择

由微分几何知识可知，点云数据中任意一点pi的局部邻域都可以通过一个微切平面进行拟合，pi及其k邻域局部拟合所得平面P可通过最小二乘原理进行表达，公式如下：

(4)

(5)

点pi的局部邻域协方差矩阵C是对称的半正定矩阵，因此可以将式(5)矩阵表示为：

(6)

式中λ1、λ2、λ3为矩阵C的特征值，e1、e2、e3为对应的特征向量。C是对称的半正定矩阵，所以特征值都为非负数，令λ3≥λ2≥λ1，λ2、λ3分别代表平面相应的特征向量方向偏离值，λ1代表法向方向的偏离值，根据文献[10]的理论,特征值能够反映局部邻域维度特性：

(1)λ3≫λ2≈λ1时，可判定局部邻域为线型；

(2)λ3≈λ2≫λ1时，可判定局部邻域为平面；

(3)λ3≈λ2≈λ1时，可以判断局部邻域为三维曲面。

邻域协方差矩阵C的特征值能反映邻域维度信息的特性，构建以下度量参数[11]：

(7)

式中Lλ、Pλ、Sλ分别代表局部邻域一维线型、二维平面、三维曲面维度特性，描述了点云局部邻域内数据的空间分布情况。利用信息熵理论结合构建的度量参数Lλ、Pλ、Sλ可以建立点云局部邻域熵函数的表达式如下：

Ef=-Lλln(Lλ)-Pλln(Pλ)-Sλln(Sλ)

(8)

由表达式及特征值维度特性可知Ef的值越小，局部邻域的某一种维度特征就比较突出，表示该邻域下数据点之间的空间分布特性相近，也就说明该邻域大小所对应的邻近点个数k或者邻域半径r的值趋于最优。因此最佳邻域尺寸的选取可以依赖于局部邻域熵函数的最小准则：

roptimum=argmin(Ef)

(9)

鉴于点云数据点的局部协方差矩阵的特征值能够直接反映该点邻域范围内邻域点的分布特性，文献[12]提出另一种表征邻域维度信息的度量参数μi(μi=λi/∑λi)，为计算局部邻域协方差矩阵C得到的特征值，其估计的最优邻域大小精度高于利用参数Lλ、Pλ、Sλ计算的最小熵函数所对应的邻域大小：

(10)

根据局部邻域熵函数取值判定最优邻域选取，当Eμ取极小值时对应的局部邻域大小即认定为最优邻域。自适应邻域选择算法流程如图4所示。

图4 自适应邻域选择算法流程图

2.2 基于法向量和曲率的双阈值特征判断

基于法向量和曲率的双阈值特征判断是利用点云局部邻域内点的法向量夹角和平均曲率特征权值的阈值，进行特征信息的提取，由于受法向量和曲率两个限制条件的约束，该方法在稳定性和准确性方面有明显的改善。

点云法向量能反映曲面的信息，利用法向量夹角构建特征判断约束条件：设定采样点pi与其k邻域内一点pj的法向量夹角用θij表示：

(11)

定义点云数据中某点pi的法向量夹角变化程度fi：

(12)

定义采样点pi在其邻域k内的平均曲率局部特征权值wH[13]：

(13)

式中H为采样点pi在其邻域k内的平均曲率。通过计算得到的法向量夹角变化程度fi和平均曲率局部特征权值wH来判定点云数据中的点是否属于特征点：首先判断法向量夹角fi的变化程度是否大于设定阈值，若fi大于设定阈值，则将点划分到潜在特征点集中；若fi小于设定阈值，则为非特征点。然后再计算潜在特征点集中点的平均曲率局部特征权值wH，若wH大于设定的阈值，则该点为特征点，加入特征点集；若wH小于设定的阈值，该点为非特征点，并将点从潜在特征点集中去除。

2.3 算法步骤

综上所述，自适应邻域选择的双阈值特征提取算法的步骤如下：

(1)假定邻域搜索半径大小为r，设定邻域搜索半径的极值rmin、rmax,初始化搜索半径ri使得ri=rmin，同时规定每一次步进计算的步长Δr；

(2)从ri=rmin开始计算对应邻域大小下局部邻域协方差矩阵C的特征向量和特征值，通过计算所得特征值，计算对应的局部邻域信息熵函数值Eμ;

(3)设置ri+1=ri+Δr，若ri+1rmax;

(4)比较计算所得的每个邻域ri所对应的局部邻域信息熵的大小，根据局部邻域熵函数最小准则，确定该邻域尺寸为最优邻域大小；

(5)在步骤(4)确定的最优邻域大小内计算：点云法向量和法向量夹角变化程度fi，平均曲率局部特征权值wH；

(6)比较fi与设定的阈值大小，若fi大于阈值，将采样点加入到潜在特征点集latent-featurepoints，若fi小于阈值，将采样点加入到非特征点集normalpoints；

(7)比较潜在特征点集latent-featurepoints中点的平均曲率局部特征权值wH，若wH大于阈值，将采样点加入到特征点集featurepoints中，若wH小于阈值，将该点从latent-featurepoints中移除到非特征点集normalpoints。直到所有点搜索完毕，结束程序，点集featurepoints即为特征点。

算法的具体流程图如图5所示。

图5 邻域自适应的双阈值特征点提取算法流程图

3 实验结果与分析

本文的实验基于Microsoft Visual Studio 2015平台，使用C++作为开发语言，结合开源库PCL(Point Cloud Library)[14]和编译工具CMake3.11.1进行实验验证，实验环境配置如表2所示。本文实验数据来自于现有设备(3D CaMega CPC-400光学三维扫描仪，如图6所示)采集和网上点云数据库。

表2 实验环境配置

图6 实验数据采集环境

利用滤清器和减速器壳体点云对本文算法和基于曲率的特征提取结果进行对比分析，实验效果如图7和图8所示。

图7 滤清器点云特征提取效果

图8 减速器壳体点云特征提取效果

图7和图8分别是滤清器和减速器壳体点云数据征提取实验效果，其中图(a)是采集的原始点云数据点，图(b)是基于曲率的特征提取效果，图(c)是本文算法的特征提取效果。从两组实验中可以看出，对于模型的边界特征两种方法都能较好地取得相应的效果，而对于模型的细节方面，如减速器端盖处螺栓的效果都未取得满意的结果；第一组实验中，本文算法提取的特征点更为细致全面，基于曲率的方法提取结果在部分区域缺失明显；第二组实验中，本文算法对螺栓孔的提取效果不太理想，曲率提取的方法对噪声的抗性更差。由于利用双阈值限制特征点的判别，本文算法提取的特征点稳定性和准确性比单一曲率方法更高，也更为精简，并且能够通过有限的点有效地表达曲面的特征信息，基于曲率的特征提取有很多冗余数据，两者提取的详细数据如表3所示。

表3 不同方法特征提取数据

4 结论

本文研究了散乱点云特征提取方法，对基于法向量、曲率等不同点云描述参数的特征提取算法进行研究，针对特征提取过程中人为调参和比较机械式的最佳邻域选择以及单一的特征描述参数特征提取稳定性、准确性差等问题，基于法向量和曲率计算，研究了一种邻域自适应的双阈值特征提取算法，实验证明本文的特征点提取算法在特征点识别的稳定性、准确性方面有较大改善。