Lidar点云三维模型于Morse理论下特征提取及应用

Lidar Point Cloud 3D Model for Feature Extraction and Application Based on Morse Theory

摘要: 针对传统的特征提取技术特征提取粗略，拓扑信息大量丢失，拓扑关系难以简化等问题，本文实现了基于分段线性Morse理论的特征提取算法，确定了一种新特征线度量指标。首先以三角网格顶点曲率计算为基础，构建了三维表面模型的Morse理论指标函数；采用最大(小)邻点算法连接指标函数所提取特征点，完成特征线构建；针对Morse-Smale复形在三维表面模型中冗余或错误特征过多，采用单复形拓扑模型进行特征提取；以三维表面模型Morse单复形“持续值法”思想为参照，确定了一种点线结合特征线提取度量指标，并基于该指标完成特征线额拓扑简化。实验结果表明，对棱角线完整性和存在性存在关键作用，在零件模型点云压缩率为26.02%，在苹果模型点云压缩率为39.33%，提高了拓扑特征提取效率，为点云后续处理奠定良好基础。

Abstract: In response to the problems of rough feature extraction, massive loss of topological information, and difficulty in simplifying topological relationships by traditional feature extraction techniques, this study implements a feature extraction algorithm based on segmented linear Morse theory and de-termines a new feature line metric. The Morse index function of the 3D surface model is constructed based on the calculation of the triangular mesh vertex curvature; the maximum (small) neighbor-hood algorithm is used to connect the extracted feature points of the index function to complete the construction of the feature line; in view of the excessive redundant or wrong features of the Morse-Smale complex in the 3D surface model, the single complex topological model is used for feature extraction; the 3D surface model is used as the “Morse single complex” continuous model. The Morse single complex shape “continuous value method” is used as a reference, and a point-line combination feature line extraction metric is determined. And based on this index, the topological simplification of the characteristic line is completed. The experimental results show that it has a key effect on the integrity and existence of angular lines, and the compression rate of the point cloud is 26.02% in the part model and 39.33% in the apple model, which improves the efficiency of topological feature extraction and lays a good foundation for the subsequent processing of the point cloud.

1. 引言

三维激光扫描技术为三维建模提供了丰富的三维空间信息，已成为三维建模的重要数据来源 [1]。常用于数字孪生城市，逆向工程和文物保护等模型重建中 [2] [3] [4]。三维激光扫描技术扫描点云的数量巨大、冗余程度过高，难以满足实际建模需求，因此一种能有效较少点云数量，并保证特征的精确性、完整性和拓扑信息的一致性的三维点云特征提取算法是建模前急需解决的关键问题。

对于模型拓扑特征提取技术，众多学者结合不同的数据类型和模型，在不同角度进行了研究。文献 [5] 结合图像学和数学思想，利用曲面上定义的累积热核函数提取曲面关键点，并使用曲面特征检测技术交互式选定边缘特征点，完成文物修复的片状缺块和跨区域缺块补配特征点提取，但变形剧烈模型其误差较大。文献 [6] 基于随机抽样一致算法直接进行3D点云数据分析，该算法抗噪性抗干扰性强，但提取精度有待提高，可采用更适合限制条件提高捕捉面积和形状特征的能力。文献 [7] 基于激光雷达点云数据的数字地面模型(DTM)，提出一种圆环探测法，利用堤防特殊形态特征和圆环的关联性，完成堤防中心线构造，该算法的应用广泛性和可移植性较差。文献 [8] 采用相邻点几何结构特征关系的线性截距比检测特征点，由于相邻点线性截距比的有序性，通过一次计算即可确定特征点，计算量小且速度快，但对于球面等特殊曲面会产生局部误差。文献 [9] 将数学形态学中定义的梯度值作为特征点检测指标，使用局部邻域梯度均值为阈值获取特征点，该算法计算简单，计算机资源需求小，但损失了大量的拓扑结构信息。文献 [10] 融合Lidar数据和高分影像，使用SegNet语义模型实现建筑物粗提取，并将阈值分割后高分影像光谱特征信息作为建筑物精提取的约束条件，完成模型特征提取，但高分影像的部分光谱特征信息严重制约提取精度。文献 [11] 提出了单复形模型，仅以下降Morse复形进行特征提取，提高了特征提取效率，避免了无实际意义特征的提取，但部分棱角线仍存在断裂问题。文献 [12] 实验表明三维表面模型极小点与下降线及上升Morse复形对于特征提取无实际作用，且增加了特征提取难度。文献 [13] 提取了部分拓扑特征，但存在毛刺附加特征过多。

针对于上述算法无法完整保留拓扑结构信息且存在冗余或错误特征等局限性，本文使用曲率作为Morse函数指标获取棱线特征点和特征线，且以单复形模型为基础，重新确定了一种点线结合特征度量指标，涵盖特征点和特征线两者优势，实现拓扑特征提取的简化表达，最后对该算法进行了有效验证和分析。

2. Morse理论

20世纪初Morse H.M.基于对连续光滑流形结构研究提出了Morse理论，该理论主要是研究n维空间内的d维流形M(M属于R的n维度)的形状和定义 [14] [15]。由于该理论主要思想是将拓扑结构和Morse映射函数集合结合起来定量分析，以此定义特征点并判断其点类型，最后来构造特征线，因此又被称为关键点理论或临界点理论 [16]。该理论对于定义在二维光滑流体M上二阶可微函数f(x, y)梯度为：

$\nabla f=\left(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\right)$ (1)

$H_f=\left(\begin{array}{cc}\frac{{\partial }^{2}f}{\partial x^2}& \frac{{\partial }^{2}f}{\partial x\partial y}\\ \frac{{\partial }^{2}f}{\partial x\partial y}& \frac{{\partial }^{2}f}{\partial y^2}\end{array}\right)$ (2)

如公式(2)，根据海塞矩阵H_f在该点在某个方向上的负特征值及变化梯度作为判断依据将关键点分为极大值点，极小值点和鞍点三类，是Morse理论的基础要素。极大值点和鞍点连线为上升线，极小值点和鞍点连线为下降线。Morse理论核心是Morse-Smale复形，复形分为上升复形和下降复形，两种复形区别在于构造复形特征线变化趋势。由于二维地表模型的Morse-Smale复形能完整表达地表趋势 [17]，其先应用于地表形态。Morse理论特征提取由三维地形模型拓展迁移为三维表面模型，判定要求和标准都有对应迁移，三维模型采用表面凸凹点对应地形模型峰谷点并使用关键点曲率变化来迁移地面模型高程变化，其仍具有良好提取效果。

3. 基于Morse理论拓扑特征提取

3.1. 特征点提取

三维表面模型网格上顶点的曲率值或法方向矢量变化值为拓扑特征提取一个重要函数指标，曲率值为曲面顶点二阶微分值，法方向矢量变化值为曲面顶点一阶微分值，顶点法向量变化值计算比顶点曲率计算更简便高效，但顶点曲率能更全面反映该顶点在曲面上局部变化趋势和几何性质，因此对关键点判别更具重要积极意义。三维空间曲率理论表明顶点曲率绝对值越大，该点附近曲面变化趋势越大，反之，曲面变化趋势越小。本文以Morse理论为基础，定义Delaunay三角网格上顶点的曲率值为Morse理论指标函数，将其作为关键点检测函数。三角网格顶点曲率计算可先在顶点P处建立曲面一般通用公式 $F\left(m,n\right)=\left(m,n,H\left(m,n\right)\right)$，其中可设 $H\left(m,n\right)=a{m}^2+bmn+c{n}^2$。以顶点P为中心局部坐标系下，根据点P的t个邻点 $\left(m_t,n_t,h_t\right)$ 得到线性方程组为：

$\left[\begin{array}{ccc}{m}_1^2& m_1{n}_1& n_1^2\\ m_2^2& m_2{n}_2& n_2^2\\ ⋮& ⋮& ⋮\\ m_t^2& m_t{n}_t& n_t^2\end{array}\right]*\left[\begin{array}{c}a\\ b\\ c\end{array}\right]=\left[\begin{array}{c}{h}_1\\ h_2\\ ⋮\\ h_t\end{array}\right]$ (3)

最小二乘线性方程组解法主要有QR分解法和奇异值分解法，QR分解法更适用于矩阵行数m远远大于列数n线性方程组，依据实际情况采用奇异值分解法更为合适。分解如公式(4)所示：

$A\stackrel{\rightharpoonup }{x}=U\Sigma V^{\text{T}}•\stackrel{\rightharpoonup }{x}=\stackrel{\rightharpoonup }{h}$ (4)

主曲率 $k_1,k_2$ 计算公式分别为：

$k_1=a+c-\sqrt{{\left(a-c\right)}^2+b^2}$ (5)

$k_2=a+c+\sqrt{{\left(a-c\right)}^2+b^2}$ (6)

Morse理论将三角网格顶点分为关键点和正则点，而关键点分为极小值点、鞍点和极大值点。以关键点检测函数为基础，使用邻点比较法选取关键点，定义比较点P与其邻点Pi特征属性值之差为Di，按序排列邻点的差值符号变化数为SV，理论分析可知，SV必为偶数或者0。若比较点P特征属性值均大于其邻点Pi特征属性值，即特征属性差值Di > 0，且符号变化数SV = 0，比较点P为极大值点；若比较点P特征属性值均小于其邻点Pi特征属性值，即特征属性差值Di < 0，且符号变化数SV = 0，比较点P为极小值点；若比较点P特征属性值仅大于其部分邻点Pi，即特征属性差值Di有正有负，符号变化数SV = 2时，比较点P为正则点，如果符号变化数SV为4及其以上偶数，比较点P为鞍点。通过此种方法，即可提取网格中关键点和正则点。

3.2. 特征线和复形提取

三维表面模型特征线提取是Morse复形构建和模型特征提取关键步骤，将Morse理论指标函数获取关键点按算法顺序连接可构建完成特征线。基于边界的复形提取算法沿上升特征线和下降特征线连接构成Morse复形，奠定复形拓扑简化基础。

基于三角网格常用的特征线提取算法有三种：最大(小)邻点法、最大角度法和梯度法。三维空间角度计算参考平面选择不固定，最大角度法计算较为复杂，耗费时间多；梯度法理论上最理想，选择三角形内上升或下降最优线，但会分割三角形，计算量过大；最大(小)邻点法通过比较顶点P各邻点Pi特征属性值，选择其中属性值最大(小)邻点作为特征线下一个构成点，算法简便，计算效率高。充分利用Morse理论指标函数，以提取特征点的特征属性值为基础，采用最大(小)邻点法构建特征线，可最大限度节约提取时间，提高构建效率，因此本文采用了该方法提取特征线。上升特征线和下降特征线提取都以鞍点为起始点，使用最大(小)邻点法，比较鞍点各邻点属性值，选取邻点中特征属性值极大(极小)的点为上升线(下降线)下一构成点，不断以特征线末端构成点为中心点，选取其符合要求邻点加入特征线末端，当特征线末端点为三角网格极大点(极小点)时，算法终止。构成Morse复形特征线区别将Morse复形分为上升复形和下降复形，上升复形由下降特征线组成，下降复形由上升特征线组成。理论分析发现，三维表面模型上升复形对模型拓扑特征提取无实际作用，因此本文仅构建下降Morse复形用于拓扑特征提取。

3.3. 拓扑特征简化

基于Morse理论单复形特征提取算法敏感性较高，导致可能提取部分错误特征或冗余无意义特征，产生噪声影响特征提取精确度，因此利用拓扑特征简化降低噪声，提高模型特征提取精确度。目前主流的特征重要性度量算法分为基于特征点和基于特征线两类。经典“关键线持续值”法应用广泛，以特征线为基础对于复形拓扑特征简化更具意义，其特征重要性为：

$D\left(p_i\right)=\{\begin{array}{l}F\left(p_i\right)-\max \left(F\left(p_i\right)\right)\\ \min \left(F\left(p_i\right)\right)-F\left(p_i\right)\end{array}$ (7)

公式(7)中， $D\left(p_i\right)$ 为关键线上点 $p_i$ 的特征重要性值； $\max \left(F\left(p_i\right)\right)$ 为与点 $p_i$ 相连的鞍点连接的极小点中较大点； $\min \left(F\left(p_i\right)\right)$ 为与点 $p_i$ 相连的鞍点连接的极大点中较小点。其计算Morse复形特征重要性度量指标为：

$I_i={\displaystyle \underset{1}{\overset{n}{\sum }}Di}/n$ (8)

经典算法仅适用于Morse-Smale复形，文献 [11] 推导出适应于单复形模型的“持续值”法，其特征重要性为：

$D\left(p_i\right)=F\left(p_i\right)-\max \left(F\left(p_i\right)\right)\approx F\left(p_i\right)$ (9)

本文参照单复形模型“持续值”法，从二维平面模型特征线重点为斜率值引申到三维立体模型线长和曲率，使用了一种特征点和特征线相结合的Morse复形特征重要性度量指标，定义为：

$I_l=\left(D_1{L}_1+D_2{L}_2+\cdots +D_n{L}_n\right)/n$ (10)

点线结合特征重要性度量指标中线段长度值L和线段两端点曲率值D都很大，表示在该线段区域特征性很强，与三维表面模型拓扑特征相符合；反之，两者都小同样符合拓扑特征。该度量指标可有效判别特征重要性，有效增加提取精度。

4. 实验与分析

本文实现硬件基础为AMD R7 4800U处理器和16G内存电脑，软件基础使用C++语言于Visual Studio 2019进行算法验证，实验所使用点云网片模型如图1(a)和图1(b)。对两种模型分别进行本文方法和文献 [13] 方法提取特征，图2(a)和图3(a)为文献 [13] 方法提取，图2(b)和图3(b)为本文方法提取。

(a) (b)

Figure 1. Model point cloud network diagram. (a) Part model; (b) Apple model

图1. 模型点云网片图。(a) 零件模型；(b) 苹果模型

(a) (b)

Figure 2. Feature extraction of part model. (a) Reference [13]; (b) This paper method

图2. 零件模型特征提取图。(a) 文献 [13]；(b) 本文方法

(a) (b)

Figure 3. Feature extraction of apple model. (a) Reference [13]; (b) This paper method

图3. 苹果模型特征提取图。(a) 文献 [13]；(b) 本文方法

由图2和图3可知，文献 [13] 所实现算法对于特征提取存在关键棱角线毛刺过多，关键线断裂和丢失关键特征等问题。图2(a)显示，红色椭圆形标记位置出现毛刺过多，绿色框处可看到关键线断裂及拓扑特征丢失，图2(b)红色椭圆框对应位置无棱角毛刺的出现，绿色框处拓扑特征线未出现断裂和丢失情形。图3(a)和图3(b)绿色椭圆形框处的关键特征缺失、断裂更具对比性，红色标记处也更能体现冗余和特征毛刺去除功能。

对于零件模型，Morse函数指标敏感性过高导致拓扑特征提取过程中曲面上产生了过多和冗余，于图2(b)的右侧部分和左上部分体现；对于苹果模型，由于苹果本身不是规则的圆柱体，所提取拓扑关键特征线即为图3(b)所示。本文算法将经典持续值变式为采用新度量指标持续值法，对零件模型和苹果棱角关键拓扑特征提取有更具积极重要性，对棱角线完整性和存在性存在关键作用，在零件模型点云压缩率为26.02%，在苹果模型点云压缩率为39.33%。

5. 结论

三维模型特征提取对三维建模的多个领域方向有重要影响，本文采用一种新Morse函数指标，使用基于新度量指标的变种持续值方法，实现了Morse理论下三维模型拓扑特征提取和简化。根据拓扑特征提取结果可知，本文算法在三维模型棱角线提取精度和抗干扰性有良好作用，本文算法克服了三维模型Morse过度剖分问题，加深了模型表达程度，减少了点云模型数据量，提高了拓扑特征提取效率，但对特殊三维表面去除毛刺冗余效果有待进一步优化。

基金项目

国家自然科学基金项目(41701464)、贵州大学培育项目(贵大培育[2019]26号)、中国科学院战略性先导科技专项子课题(XDA2806020101)。

NOTES

^*通讯作者。