一种自适应点云特征点提取算法

韩磊，陈宇，王春阳，于艳鑫

（长春理工大学电子信息工程学院，长春 130022）

0 引言

三维激光扫描技术现已在考古研究、生物医学、汽车工业、水利工程地形测绘等工程领域有了广泛的应用[1-2]，但其测得的点云数据密度高、数量大，存在大量的冗余点[3]。因此针对这类点云数据首先要进行简化即去除冗余点，为保证模型最基本的几何形状保留完整，需要先提取出点云特征点，进而对点云数据进行简化和三维曲面重建等。另外，特征点检测对于点云配准也具有重要意义。所以模型的特征点提取是处理三维散乱点云数据的关键步骤之一[4]。

Charlie等采用双边滤波来检测和重建特征,需要优化给定模型的网格连通性，否则尖锐的边缘区域顶点坐标会发生漂移和拥挤[5]。Mian等人通过构造一个品质因数Qk，该品质因数Qk包括高斯曲率和主曲率，特征点为其品质因数Qk大于某阈值的点[6]。王小超等提出基于局部重建的点云特征点提取方法，该方法可以处理分片光滑曲面上采集的点云数据，但对于两个弯曲程度较大的曲面相交形成的特征点该方法不适用[7]。王晋疆等提出一种基于点签名的特征点检测方法，根据具有正态分布特性的点签名的均值与方差设制曲率阈值，该方法抗噪性能佳但时间复杂度高[8]。

针对现有算法存在的效率低、特征点提取不准确等问题，本文提出一种改进的自适应点云特征点提取算法，通过计算数据点到k邻域点（k可以根据数据密度进行改变）的平均距离、该点的曲率以及该点的法向与k邻域点法向夹角的和，设定一个特征参数，根据特征参数正态分布规律，利用均值与方差的和自适应地设置阈值来提取特征点。该方法适用于复杂的模型数据，能够准确高效地提取出点云特征点。

1 特征点提取方法

1.1 散乱点云空间划分

本文采用Hash法划分点云P，建立空间长方体包围盒，将空间等间距切割成体积相同的若干个立方体栅格（示意图如图1），确定离散点所在的子立方体，标记索引号，便于查找k邻域点[9]。求出X,Y,Z三个坐标轴上的最大值与最小值Xmax,Xmin,Ymax,Ymin,Zmax,Zmin。

长方体包围盒的边长为：

定义小立方体边长：

其中，N为点云数目，根据经验k一般取值为15-25。通过下式对数据点进行定位，求出任一点在小立方体的索引号m,n,l：

求每个数据点的欧氏距离最近的k个邻域点时，搜索范围限定在其本身所在小立方体及其上下左右前后的27个立方体。

图1 立方体栅格示意图

1.2 基于曲率和密度的特征点检测算法

一般模型的特征区域数据点比较密集，曲率较大，该算法综合考虑数据点与邻域点的平均距离、数据点曲率，以及数据点与邻域点法向夹角的和。利用八叉树法对点云进行细分求点云密度，再结合模型整体信息确定特征检测阈值[10]。邻域点的平均距离计算公式如下：

其中M(pi)为数据点pi的邻近点集。

点云数据的法向和曲率也是判断是否为特征点的重要因素，采用基于最小二乘平面拟合法求pi法向量ni，如下所示：

其中n为平面P(n,d)的法向量，d为平面P(n,d)到坐标原点的距离。利用主元分析法求解，最小特征值对应的特征向量即为点云法向量。

，设λ1＜λ2＜λ3，e1可近似曲面在点pi的法向量ni，即ni≈e1。

τi近似为点云模型在数据点pi的平均曲率。数据点与邻域点的法向夹角也是衡量曲面弯曲程度的标准，定义法向夹角参数wa(pi)为数据点与所有邻域点的法向夹角的和：

θpipj可由下式求得：

特征区域内的点比较密集，数据点与邻域点距离小，所以数据点到k邻域点（k可以根据数据密度进行改变）的平均距离与特征参数成反比，曲率越大模型特征越明显，所以曲率与特征参数成正比，特征点与邻近点的法向量夹角较大，所以法向夹角参数与特征参数成正比，定义特征参数：

其中λn曲率系数和λd是距离系数。

用八叉树计算特征检测阈值，子节点中包含的数据点个数小于8，计算所有叶子节点的平均对角线长度，作为点云密度ξ。由点云模型边到中心点的最大距离dc表示模型的尺寸，定义特征检测阈值为σ=ξ/dc。特征参数大于检测阈值σ的数据点为特征点。

1.3 自适应点云特征点提取算法

由于基于曲率和密度的特征点检测算法的特征参数需要人为输入和调整曲率系数和距离系数，这两个系数仅作为控制特征点数量，且计算点云密度和模型边到中心点的最大距离较耗时。因此本文将曲率系数与距离系数去掉，重新定义特征参数如下：

选取斯坦福兔子模型、Horse模型和椅子模型三个在形状上具有代表性的模型计算其特征参数，特征参数分布如图2。

图2 特征参数分布图

由图 2（a）（c）（e）可以看出斯坦福兔子模型表面较平坦，数据点较紧凑；Horse模型四条腿相对身体较凸出且分散；椅子模型有镂空部分，数据点不完全连续。这三个模型的特征参数分布如图 2（b）（d）（f），图上曲线为正态分布曲线，横坐标为参数值，纵坐标为点云数。可以看出特征参数近似服从正态分布，因此，可以认为散乱点云的特征参数具有正态分布的特点，根据这一特点来确定特征点提取阈值。阈值改进如下，取特征参数的均值与方差：

确定阈值：

若某个数据点的特征参数w(pi)大于阈值δ，那么这个点pi为特征点qi。若特征参数w(pi)小于阈值δ，pi为非特征点。

2 实验结果分析

本文实验在MATLAB 2016a环境下进行特征点提取，操作系统为Windows 10，主频2.5GHz，处理器为Intel Core i7-6500U。图3、图4为本文方法提取特征点效果。

图3 特征点提取

图3 （a）为斯坦福兔子模型，共35947个点，提取出的特征点个数为4797。特征点云颜色与原始点云相对应。可以看出，模型的耳朵、头部、腿部和尾部等纹理信息可以提取出来。图3（b）为椅子模型，共49960个点，提取出的特征点个数为7290。椅子的靠背、凳腿及座板边框特征可以有效的提取出来，座板内部为非特征信息被过滤掉。

图4 Skull模型及特征点提取

图4 为Skull模型，原始点云共有20002个点，提取特征点个数为3830。可以看出模型头部的字母很好地保留下来，模型的牙齿信息也基本保留，以及模型的棱角纹理较好地提取出来。

图5为本文方法取k=15与文献[8]方法取k=20,e=1和文献[10]方法取λn=400，λd=100在无噪声干扰下和随机添加3000个噪声点的情况下，对Horse模型的特征点提取效果。

如图5所示，可以看出模型头部、腹部和腿部等是特征点密集区域，文献[8]（图5（a））、文献[10]（图5（c））和本文方法（图5（e））在无噪声干扰下都能比较好的提取出特征点。但文献[8]（图5（b））和文献[10]（图5（d））在噪声的干扰下，可以明显看出将很多噪声点识别为特征点，影响后续重建效果。本文方法（图5（f））对噪声敏感度更低，可以保持相对稳定的特征提取效果。

图5 文献[8]方法、文献[10]方法与本文方法特征点提取结果

表1 未加噪特征点提取对比

表2 加噪特征点提取对比

表1为在无噪声情况下文献[8]方法、文献[10]方法与本文方法对Horse模型（48485个点）特征点提取对比，表2为加3000个噪声点的情况下特征点提取对比结果。文献[8]方法由于要经过两次筛选：先根据散乱点云具有正态分布规律的点签名设定曲率阈值进行筛选，然后再对候选特征点在其主曲率方向上投影，进行进一步筛选，时间复杂度较高。该方法提取出特征点1621个，耗时 16.5s；加噪后特征点为 2120，耗时16.8s。文献[10]方法根据点云法向夹角、数据点平均距离和曲率计算特征参数，选取数据点密度与模型到中心点最大距离的比值作为阈值，提取出特征点1128个，耗时10.6s；加噪后特征点为10334，耗时13.2s。该方法需人为根据经验设定系数。本文方法根据特征参数的正态分布特点选取阈值，提取出7025个特征点，耗时8.2s；加噪后特征点为7382，耗时8.3s。可以看出加噪后识别出的特征点与未加噪相差不大。由此得出本算法能够较完整地保留模型的特征信息，耗时短，效率较高。

3 结语

本文采用Hash函数法求出数据点邻域点，通过计算数据点到k邻域点距离的平均、该点曲率、该点的法向与k邻域点法向夹角的和，设定点云特征参数，根据特征参数的均值与方差自适应地设置阈值来提取特征点，不需要输入系数。实验结果表明，本文的方法准确提取出点云模型特征点，提取出的点少而精，不会遗漏特征点，是一种有效的特征点提取算法。

参考文献：

[1]高艳芳,豆贺,佟晗,韩胜松.反求工程的研究现状与发展趋势[J].现代化农业,2017,09,58-60

[2]刘晓芳,田兰芬.三维激光扫描技术在水利工程地形测绘中的应用[J].科技创新与应用，2017,27,141-143

[3]解则晓,刘静晓,潘成成等.一种散乱分层点云的有序化精简方法[J].几何设计与计算,2016,37（3）：359-366

[4]杨斌杰,鲁铁定.点云数据特征点提取方法的比较[J].江西科学,2015,33（1）：10-14

[5]Charlie C L.Wang.Bilateral Recovering of Sharp Edges on Feature-insensitive Sampled Meshes[J].IEEE Transactions on Visuallization and Computer Graphics,2006,12（4）.

[6]Mian A,Bennamoun M,Oture-based 3D Object Retrieval from Cluttered Scenes[J].International Journal of Computer Vision,2010,89（2）：348-36.

[7]王小超,刘秀平,李宝军等.基于局部重建的点云特征点提取[J].计算机辅助设计与图形学学报,2013,25（5）：659-665.

[8]王晋疆，陈阳，田庆国等.一种基于点签名的散乱点云特征点检测方法[J].计算机工程,2014,40（7）：174-178.

[9]王楠.基于三维散乱点云的网格重构技术研究[D].大连：大连大学,2013.

[10]王丽辉,袁保宗.三维散乱点云模型的特征点检测[J].Signal Processing,2011,27（6）：932-938.