基于FPFH的点云特征点提取算法

贾 薇 舒 勤* 黄燕琴

1(四川大学电气信息学院 四川 成都 610065)2(漳州职业技术学院 福建 漳州 363000)

0 引 言

随着三维扫描技术的快速发展，通过激光扫描技术获得的点云模型成为近几年几何模型的通用表达形式[1]。目前，三维模型特征提取已成为计算机视觉、数字几何处理技术中的研究热点[2]。

Kim[3]利用移动最小二乘法拟合局部三次曲面计算曲率和主方向，通过计算曲率沿主方向的极值点来提取点云脊谷特征点，可以较好地检测模型细节特征。Wang等[4]通过移动最小二乘法计算曲率，再将曲率绝对值较大点标定为点云脊谷特征点。庞旭芳等[5]使用类似的方法提取出曲率较大的点后通过特征点投影得到增强特征点，最后对特征点进行平滑后生成特征线。Gumhold等[6]使用平均曲率计算邻向图边的惩罚权重大小，通过最小化邻向图边的权重来提取特征点。上述方法都是通过拟合局部平面来计算曲率，再在此基础上提取脊谷特征点，但是算法的时间代价高。Pauly等[7]将多尺度分类算子作为算法核心，使用局部邻域的大小作为离散尺度参数，计算在不同尺度下一点为特征点的可能性。Demarsin等[8]利用PCA计算离散点云法向量，根据法向变化对点云数据进行分类，将相对较小的点簇作为特征区域，最后通过构造最小生成树得到特征线。Daniels等[9]利用鲁棒最小二乘的概念，在点的邻域内进行曲面拟合，将点投影到多个曲面交点得到增强特征点，最后连接并平滑特征线。张雨禾等[10]提出一种基于密度空间聚类的散乱点云特征提取方法，将反K近邻的尺度作为点密度，引入特征的全局约束性信息，建立新的特征识别准则。然而法线和曲率只是点的近邻的几何特征估计，不能捕获点云模型的细节特征，且上述方法都是针对某一类特征进行特征点提取，在处理模型时，难以提取完整的多种类型的特征点。

快速点特征直方图(FPFH)通过参数化查询点与邻域点之间的空间差异，形成一个多维直方图对点的几何属性进行描述，由Rusu等[11]于2008年提出。该方法有较好的抗噪性能，广泛用于机器人目标定位、点云分割和点云配准的研究中。然而针对点云特征点提取技术，还未出现引用FPFH方法的文献。

针对以上问题，本文提出一种基于FPFH的提取点云特征点的新方法。将FPFH引入点云特征点提取技术中，并提出FPFH各子区间均值这一参数概念。通过判断各点FPFH各区间值与均值的距离大小提取初始特征点；根据扫描的点云模型数据排列特点，提出判断特征点邻近点夹角的方法对初始特征点进行优化；采用基于投影点夹角的方法对点云轮廓特征进行增强。实验结果表明，该方法简单高效，无须计算点云曲率特征，为点云特征提取提供了新思路；提取出的特征点不仅可以反映模型脊谷细节特征，还可以完整地表征模型的轮廓信息。

1 法向量估算

法向量作为点云必不可少的属性之一，其估计方法在点云数据处理中具有重要的位置。目前，基于PCA的法向量估计被广泛使用，该方法由Hoppe等[13]在基于有向距离函数的表面重建法中提出。

由于散乱点云不具备拓扑信息，首先提取点云K近邻点构建局部邻域。设点r的K近邻为{r1,r2,…，rk}，则协方差矩阵可以表示为：

(1)

对协方差矩阵C进行特征值分解,对应C最小特征值的特征向量即为点r的法向量。

需要注意的是，算出的法向只得到了法向量所在直线，而没有确定以直线的哪个方向为法向量的最终方向[11]，本文用文献[13]的方法对法向进行调整，调整后的法向均指向模型外侧。

2 特征点初提取

2.1 快速点特征直方图原理

点云模型中，任意点pq的点特征直方图(PFH)计算规则如下：以点pq为圆心，构造半径为r的球形区域，寻找点pq的K近邻(见图1)。

图1 PFH计算的影响范围

假设球体内两点ps、pt的法向为ns、nt，以ps法向ns为u轴，根据右手定则建立局部坐标系uvw如图2所示。

图2 建立局部坐标系

将uvw局部坐标系平移到点pt，设pt的法向nt与坐标轴v的夹角为α，nt在平面uw的投影与u的夹角为θ，ns与点pt、ps连线的夹角为φ。

α=v·nt

(2)

(3)

(4)

PFH计算过程中点的影响区域如图1所示，依次计算球体内两点之间的α、φ、θ值，将三个特征值的取值范围分别划为等分的b个子区间，共形成3b个区间。再分别统计每个落入子区间的数量，最终根据各子区间数量所占总数的百分比来构建查询点pq的点特征直方图。

由于PFH的计算复杂度高，文献[11]提出快速点特征直方图(FPFH)算法，对PFH进行简化，在保留PFH特性的同时，提高了运算效率。FPFH特征计算的影响区域如图3所示，只计算pq与K近邻的PFH值，称为SPSH，然后分别计算pq邻域点的SPFH值，最后进行加权计算，得到最终的FPFH值：

(5)

式中：ωi是点pq到邻域点pi的欧式距离。

图3 FPFH计算的影响范围

2.2 基于FPFH的特征点初提取

FPFH值中涵盖了点云的局部特征信息，三个特征值间接反映了点云的平均曲率和几何特征，本文将曲率阈值提取特征点的方法推广到FPFH，对点云模型特征点进行初提取。

由于FPFH是基于法向之间的关系建立起来的，考虑了法向方向之间所有的相互作用，因此特征点与非特征点的FPFH值存在明显差异，可利用此特性提取点云初始特征点。

由于在三维模型中，大部分所在表面较为平缓，因此，可用FPFH在各子区间的均值代替非特征点的FPFH各区间的值，引入点云模型FPFH各区间的均值，记为MFPFH：

(6)

在此基础上计算每一点的FPFH各区间的值与MFPFH的欧式距离：

(7)

式中：f代表直方图子区间个数；pi表示点云的FPFH第i个区间的值；ui表示点云第i个区间的MFPFH值。若d超出阈值，则标记为特征点。

3 特征点优化与增强

通过阈值提取出的点云数据中，不仅包含特征点，还包含了部分非特征点。本节首先采用判断特征点临近点夹角的方法对脊谷特征点进行优化，再通过判断点云邻近投影点相邻向量夹角大小的方法来增强模型整体轮廓特征。

3.1 脊谷特征点优化

脊点和谷点作为曲面上局部区域内曲率沿主方向变化的极值点，充分表征了对应曲面的重要几何形状特征。点云模型数据由大型扫描仪扫描获得，图4(a)为典型的点云模型，其内部排列规则如图4(b)所示。可以看出，点云脊谷特征点的最临近点均匀分布于其两侧，距特征点的距离几乎相等，基于此特点和脊谷点的凹凸性，本文提出判断特征点临近点夹角大小的方法对脊谷特征点进行优化。

(a) 点云模型 (b) 局部放大图图4 典型点云模型

如图5所示，若点云为脊谷特征点，则特征点与两近邻点向量之间的夹角较小，特征越尖锐，夹角越小；若点云为非特征点，则特征点与近邻点向量之间的夹角较大。根据此原理，可对提取出的特征值进行优化，剔除曲率较小的特征点。

图5 特征点与非特征点夹角图

3.2 边界特征点增强

Q为内部点 Q为边界点图6 边界点判别

4 实 验

FPFH是基于点云法向之间的关系建立起来的，法向估算的精确程度取决于搜索半径的大小，因此法向搜索半径rn对FPFP具有一定影响。图7、图8是在改变法向搜索邻域范围大小的情况下，特征点和非特征点FPFH值变化，其中t为邻域搜索范围内的点数，t越大，代表邻域搜索半径越大。在邻域半径较小时，特征点与非特征点差别较小，这是因为邻域搜索半径过小，法向估计结果不准确；随着法向搜索半径的增大，非特征点的FPFH值无明显变化，而特征点FPFH值出现较大的跳跃，在t=30后趋于稳定。整体来说，在合适邻域范围内，特征点与非特征点的FPFH值存在较大差异。因此，本文将t设为35，可以得到较理想的结果。

图7 不同法线搜索邻域下特征点的FPFH值

图8 不同法线搜索邻域下非特征点的FPFH值

为验证本文方法的有效性，在MATLAB上进行实验验证。设参数t为邻域搜索点的个数。图9为Armadill模型，取t=35，共提取出特征点6 727个。Armadill模型中有较多的细节特征，如眼睛、嘴巴等，可以看出，该方法在细节特征提取上表现较好，能完整地提取出模型的轮廓特征。图10为bunny模型，该模型为经典点云模型，取t=35，共提取出特征点6 055个，结果表明，该方法较好地提取出bunny的特征点，如前腿、耳朵、身上纹理特征等都被提取出。

图9 Armadill模型实验结果

图10 bunny模型实验结

为验证本文方法的优越性，将本文算法与文献[4]算法进行对比分析。文献[4]为提取点云特征点典型的曲率阈值检测法，且在文献[5]中也有采用此方法，首先通过移动最小二乘计算曲率，再设置阈值，将曲率绝对值较大的点标定为特征点。图11为斯坦福快乐佛模型实验结果，曲率阈值检测法提取出脊谷特征点14 130个，本文方法提取出脊谷特征点13 226个。从图11(d)可以看出，曲率阈值检测法虽然能较完整地提取出脊谷点，但是曲率在计算中存在误差，因此提出的特征点所含噪点较多。图12为龙模型，文献[4]方法提取出脊谷特征点8 270个，本文提取出脊谷特征点9 387个，从龙头和脊背部分数据可看出，本文方法能更好地提取出模型的尖锐与细节特征，而且模型的轮廓信息更完整。从整体效果来看，本文方法能够更加精确地提取出点云细节特征点，而且能传达模型的轮廓信息，特征点更完整。

(a) 模型特征点 (b) 轮廓点加强

(c) 本文整体效果 (d) 曲率阈值检测法图11 快乐佛模型实验结果

(a) 模型特征点 (b) 轮廓点加强

(c) 本文整体效果 (d) 曲率阈值检测法图12 龙模型实验结果

表1为本文方法与文献[4]的曲率阈值检测法在其他模型上提取的特征点对比。

表1 本文方法与文献[4]方法提取特征点数对比

可以看出，本文方法在前两个模型上提取出的特征点数明显多于文献[4]的曲率阈值检测法，数据差主要来自模型轮廓特征点，文献[4]方法虽然可以较好地提取出脊谷特征点，但是冗余数据较多，在对模型细节特征的提取上效果较差。

5 结 语

点云特征提取是点云处理的关键底层技术，针对现在大部分文献都采用曲率和法向作为切入点的现状，本文提出了基于FPFH的点云特征点提取方法。采用PCA估算法向向量，计算点云的FPFH值；引入模型FPFH值在各子区间的均值，根据点云FPFH各区间值与均值的欧式距离提取出初始特征点；根据凹凸点与两临近点夹角大小对脊谷特征点进行优化，再对模型轮廓特征进行加强。

实验结果表明，本文方法简单、有效，可以有效提取点云特征点，与其他方法相比，能更好地体现模型的细节特征与轮廓特征。然而，在提取初始点云特征点时，不同模型需要设置不同的阈值，如何改进对阈值的设置是下一步研究的目标。