逆向工程中点云特征提取技术研究

周建钊，颜雨吉

（陆军工程大学野战工程学院，江苏 南京210007）

逆向工程（Reverse Engineering，简称 RE）是根据现有的模型，利用数字化测试设备获取实体数据，对数据进行处理后进而重构出完整的三维模型，在此基础上，进行模型优化、创新设计、二次开发[1]。逆向工程广泛应用于机械制造、文物修复和地理信息构建等方面，如图1所示。点云数据获取、点云数据处理以及模型重构是逆向工程中三个必要环节。点云数据处理是逆向工程中最重要的环节，其精度以及效率将直接影响着三维模型的最终效果。而特征提取是点云数据处理中的一项重要内容，如何有效的提取点云数据的特征点，将对后续点云模型的分析、配准、匹配以及曲面重建产生巨大的影响。

图1 逆向工程应用

特征点是最基本的曲面几何形状的特征基元，对于几何模型的外观及其准确表达具有重要作用。点云数据的特征提取是指从点云模型中识别出几何模型的轮廓、尖锐处、凸凹处和过渡光滑处等结构特征及形状特征的过程[3]。特征提取可分为基于三维网格模型的特征提取和基于散乱点云的特征提取，本文研究内容主要基于后者。

通过三维激光扫描仪获取的散乱点云数据通常不具备网格信息，且数据点分布不均匀、数据量庞大、存在冗余和噪声、无法直观反应物体的真实信息，因此，寻找有效地提取点云数据的可靠特征信息的方法，对点云数据处理和几何模型重建的精度及效率的提高具有重要意义。

为了能清晰地表达点云几何信息，常用点云特征描述参数（法线和曲率、点特征直方图、快速点特征直方图、文理特征、视点特征直方图等）对点云进行描述。基于不同的点云几何描述参数有不同的特征提取算法，下面从不同的特征描述参数分析特征提取的关键技术。

1 基于法向量的特征提取

法向量是点云数据模型中很重要的几何属性，点云数据配准、分割、特征提取和曲面重建等处理，都依赖于法向量的准确估算[4-5]。大多数情况下三维设备获取的点云没有法向，也不具有几何拓扑结构，因此需要依靠点云空间位置信息从初始点云中进行法向量的估算。如图2所示，区域曲面内法向量变化平缓时，表征该区域较平坦，法向量变化较大时，反映该区域起伏大，根据领域k内法向量的变化，设定适当的阈值可识别出点云数据的特征点。

图2 法向量反映曲面信息

点云法向量的计算可以分为以下两种方法：

（1）三维设备获取的点云数据是物体表面的样本点，故可先对物体表面的几何进行估计，使用低阶多项式对点云数据进行局部拟合[6-7]，得到采样点对应的曲面，然后再用曲面模型计算其表面的法线，如图3所示。此方法的缺点时在特征比较尖锐的地方，法线计算容易被平滑，可以用迭代权重的方法来修正，先用平面局部拟合，然后给局部点计算权重，以点离平面的距离确定权重，然后再用带权重的点再次进行局部平面拟合，反复迭代可获得更精确的特征点。

图3 拟合计算点云数据法向量

（2）直接从点云数据中计算曲面法线[4，8，9]，把估计某个点的表面法线问题简化为从该点的k邻域计算协方差矩阵的特征向量和特征值，并进行分析，从而估计一点处的表面法线，此方法所计算出的法线精确度依赖于k邻域的选取。

式中k是指与点pi欧氏距离最近的k个点，θij是指点pi与邻近点pj的法向量夹角，将某点法向量变化程度fi与设定的合适阈值比较，即可有效提取点云数据特征点。

基于法向量的特征提取计算简单，但依赖于k邻域的选取，同时对噪声较为敏感，对于孤立的特征点因为缺乏近邻点信息所以无法提取，对于细节特征较多、较复杂的点云数据提取效果也不佳。

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

2 基于曲率的特征提取

曲线的曲率（curvature）是针对曲线上某个点的切线方向角对弧长的转动率，通过微分来定义，表明曲线偏离直线的程度。曲面的曲率可以经曲线的曲率推导而来：设在欧几里德空间中存在一个三维曲面，规定过某点的曲率为过该点的法向量和某一切向量所确定的平面与曲面的交集（是一条曲线）的曲率。由于过某点可以确定无数条曲线，即曲面上某点的曲率不唯一，所以定义曲面的主曲率、高斯曲率和平均曲率：

主曲率：过曲面上某个点上具有无穷个正交曲率，其中存在一条曲线使得该曲线的曲率为极大，这个曲率为极大值kmax，垂直于极大曲率面的曲率为极小值kmin，这两个曲率定义为主曲率。

高斯曲率：两个主曲率的乘积即为高斯曲率，又称总曲率，反映某点上总的弯曲程度。

平均曲率：是空间上曲面上某一点任意两个相互垂直的正交曲率的平均值。如果一组相互垂直的正交曲率可表示为ki，kj，则平均曲率则为：k=（ki+kj）/2，见图5所示。

图5 曲面某点法向量与主曲率[10]

点云数据中的任意一点都存在某曲面逼近该点其近邻点云，因此可以通过该点及其邻域点拟合获得局部曲面，利用拟合所得曲面的曲率近似表征该点的曲率。常用最小二乘拟合可获得某点近邻区域的曲面参数方程，根据参数方程和曲面曲率性质则可以计算出对应的主曲率、高斯曲率和平均曲率，过程概括如下[11-12]：

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

（2）根据二次曲面基本方程：

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

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

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

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

3 基于PFH和F PFH特征提取

3.1 点特征直方图（PFH）

法向量和曲率估计是某个点周围的几何特征基本表示法，计算快速容易，但是仅使用几个参数值来近似表示一个点的k邻域的几何特征，所包含的信息有限，对点云全局的特征信息反映较少。点特征直方图（Point Feature Histograms，PFH）三维特征描述子[13-14]，能够较好的反映点云全局特征。PFH通过计算点云中某一个查询点与该点k邻域点之间的空间差异并将其参数化表达，合成一个高维直方图，借此描述点及邻域点的几何属性。

基于点云法线和构建的局部坐标系可以计算出点云数据中点的特征直方图PFH，具体过程概括如下[15-16]：

（1）以点pi为圆心，r为领域半径，确定邻域计算范围，再将邻域范围内的所有点两两相连构建点对，如图6所示。

图6 P F H计算原理

（2）基于邻域内的任意点对pk1，pk2，对应的法线为 nk1，nk2构建局部坐标系（u，v，w），如图 7 所示。

图7 局部坐标系

（3）利用点的法向量和构建的局部坐标系计算出点的四个参数值 α、β、γ、d：

d是点pk1，pk2的距离，实践证明忽略d这一参数对点云PFH特征提取影响很小，且大大降低算法的时间复杂程度，因此忽略d的计算。其余三个参数分别将上述三个特征参数按值划分为n个子区间进行统计，进而会有n3种组合情况，直方图则产生n3个区间，分别统计落在这些区间的点云数目，最后合成点的特征直方图。提取获得的桌面上书本和杯子的点特征直方图（Point Feature Histograms，PFH）情况。

3.2 快速点特征直方图（FPFH）

PFH的计算依赖于每个点与周围邻域点的局部坐标系（u，v，w）的建立、法向量的求解、法向量与坐标轴之间的几何特征值的计算，并由此计算特征值合成直方图。如果点云P中有n个点，那么它的PFH的理论计算复杂度是O（n*k2），其中k是点云P中每个点pi计算特征向量时考虑的邻域点数量。实际应用中，计算密集点云的PFH，会导致计算过于复杂，时间效率不高。于是学者们又提出了快速点云特征直方图（Fast Point Feature Histograms，FPFH）特征提取算法[17]。

FPFH特征提取算法过程如下[15-16]：

（1）计算点pi与其k邻域内的点所构成的点对的PFH特征参数，称其为简化的点特征直方图（Simple Point Feature Histograms，SPFH）

（2）对点 pi邻域内的各点（pk1，pk2，pk3，pk4，pk5）分别计算其邻域内点的SPFH，如图8所示。

（3）计算pi的FPFH特征，计算公式如式（11）。

式中ωj是pi到点邻域内任意点pj的距离，作为计算权重。

图8 F P F H计算原理

由于减少了点pi的k邻域内的各点两两组成点对的运算，仅计算pi与邻域点的PFH，大大减少了运算量，计算复杂度由原来的O（n*k2）降低至O（n*k），提高了算法时间效率。

4 其他特征提取方法

点云特征提取技术涉及逆向工程、地理空间信息、计算机视觉等学科领域，是一项应用十分广泛的数据处理技术，因而除了上述特征提取方法，不少专家学者提出了许多的基于不同理论，应用于不同类型点云的提取算法，下面对其中的部分算法进行简单的分析总结：

（1）多特征判别参数提取点云特征[11]。通过对法向量、曲率、点到邻域重心距离等多个几何参数的计算比较，设定合适阈值，当计算所得点云的多个参数都大于阈值时，判定为特征点。

（2）基于离散Morse理论提取点云特征[18]。先利用局部邻域的协方差，计算出每个数据点的特征度量，标定为潜在特征点。然后将潜在特征点与其邻域点在主方向上所形成的夹角平均值作为局部特征检测算子，利用该算子计算该点的离散梯度。最后，利用线性插值法计算离散梯度并构建离散梯度向量域，离散梯度向量域中的梯度极值点判定为特征点。

（3）基于DBSCAN聚类提取点云特征[19]。该算法首先定义散乱点云上点的反k近邻作为特征描述子，初步判定其是否具有局部突变性；其次，将点的反k近邻尺度作为点的密度值，基于密度聚类分析的方法，将具有相似局部几何特征的点聚为一类，然后根据局部曲率突变点是否同时为潜在曲面上的曲率突变点来对聚类边界点进行判定，若同时为局部及全局曲率突变点，则判定为特征点。

（4）凹凸特性提取点云特征[20]。曲面凹凸性质在点云数据中可以直观的表现出来，因此可以根据邻域点的凹凸特性提取特征点。定义邻域重心q，通过判断查询点到q的连线构成的向量与查询点的法向量的内积的正负性判断凹凸性质（正为凸点，负为凹点），计算凸点到邻域重心的距离d，设定d的阈值，大于阈值的为特征点。

5 结束语

本文通过对三维点云特征特征提取技术的学习研究，总结了基于法向量、曲率、PFH和FPFH等不同特征提取参数的点云特征提取方法，介绍了基于多判别参数及其他特征提取的方法，为现有的点云特征提取算法的精度和时间复杂度的提高和改进理清思路，找到出发点。

点云特征提取技术在装备制造、文物修复、地理信息识别、计算机视觉等诸多学科领域都有广泛的应用，因而精确高效的点云特征识别与提取算法对装备逆向制造精度、地理信息准确反映以及视觉识别技术的提高起重要的作用，本文通过较为深入的总结分析，为后续的探索研究提供重要参考。