基于Snake的点模型谷脊线提取与优化

张若男， 王仁芳

（1. 上海海洋大学信息学院，上海 201306；2. 浙江万里学院计算机与信息学院，浙江 宁波 315100）

基于Snake的点模型谷脊线提取与优化

张若男1,2， 王仁芳2

（1. 上海海洋大学信息学院，上海 201306；2. 浙江万里学院计算机与信息学院，浙江 宁波 315100）

基于主动轮廓模型（Snake模型），提出一种点模型的谷脊线提取与优化方法。首先构建点模型的局部隐式曲面，并求出采样点的曲率值；然后通过求解主曲率极值点得到潜在谷脊点，依据特征点的主方向连接谷脊点生成谷脊折线段；最后利用主动轮廓模型对谷脊折线段进行优化。实验结果表明，算法是鲁棒的且能够生成光滑的谷脊线。

点模型；特征提取；谷；脊；Snake模型

随着三维扫描设备和获取技术的快速发展，点模型的数字几何处理已经成为数字几何处理领域的研究热点[1-3]。特征线是三维几何模型的重要组成部分，对其外观及准确表达具有重要的作用，因此特征线的提取在几何分析、曲面重建与编辑以及数据分块等方面有着非常广泛地应用。在数字几何处理领域，网格模型特征提取的研究工作已取得一定的成果[4]，然而点模型特征提取的研究工作相对较少，主要原因是点模型缺乏拓扑连接关系，且在获取过程中易受噪声影响。因此，点模型特征线的提取仍是一项挑战性工作。

现有的特征线提取方法大致分为3类：①基于曲面拟合的方法[5-11]。文献[5]提出了一种基于鲁棒的移动最小二乘法(robust moving least square, RMLS)的特征线提取方法，该方法首先通过RMLS算子收集候选特征点并对候选点分别进行 RMLS局部拟合，然后将候选特征点投影到最近的曲面交线上，对投影点进行光顺处理，最后通过特征折线生长获得特征线。该方法对特征点的识别主要取决于尖锐边上的投影点，因此特征线的提取效果比较精确，但该方法基于RMLS拟合，时间代价较大。文献[8]将 RMLS引入到点云谷脊特征线提取的研究中，实现了点云模型谷脊线的较准确提取，但由于没有进行优化，最终效果不够光滑。针对网格模型，文献[11]提出了一种基于局部拟合的谷脊线提取方法，该方法是采用紧支撑径向函数(compactly supported radial basis functions, CS-RBFs)拟合三角网格曲面，并将网格点投影到拟合曲面上，计算曲率梯度和曲率张量，然后计算网格边端点的最大最小主曲率，跟踪检测出所有谷脊特征点。该方法在网格模型上取得了良好的效果，但仍然有谷脊线连接性较弱的问题，并且该方法效率较低。②基于主成分分析的方法[12-15]。文献[12]通过主成分分析法(principal component analysis, PCA)来计算采样点的法向，并根据采样点局部邻域内法向的变化对点模型进行分类，然后在不同分类的边界点构造最小生成树，最后生成特征线。文献[13]通过构造黎曼树建立点云的拓扑连接信息，利用局部邻域的协方差矩阵的特征值计算某一点属于特征点的可能，构造最小生成树来确定特征线。文献[14]提出了点模型的特征检测算法，该算法首先基于多尺度的协方差分析得到点模型的特征区域，然后利用最小生成树算法将特征区域连接，最后对特征线进行非真实感绘制。尽管这些方法能够提取点模型的特征线，但是对噪声较为敏感，同时对细微特征的提取效果有限。③基于统计的方法[16-18]。文献[16]提出一种基于高斯法向聚类的特征提取方法，首先在一点局部邻域内构建当前点及其邻域点组成的所有三角形集合，利用高斯法向聚类算法对三角形法向进行聚类，然后依据法向聚类的个数判别当前点是否为特征点，最后用特征折线生长算法连接得到特征线。由于该算法需要对采样点邻域进行三角网格化，从而增加了运算的复杂度，且存在跨越特征边的三角形，由此降低了特征识别的准确性。

为了能鲁棒地提取出光滑的特征线，本文提出一种基于主动轮廓模型的谷脊特征线提取方法。通过构建点模型的局部隐式曲面，求出采样点的曲率值；通过求解主曲率极值得到潜在谷脊点，并依据谷脊点的主方向连接谷脊点生成谷脊折线；利用主动轮廓模型对谷脊线进行优化。

1 算法概述

本文算法思想是通过三次多项式拟合点模型的局部隐式曲面，根据最大、最小主曲率标记出潜在的谷脊特征点，然后采用启发式搜索法分别对谷脊点进行连接，并采用Snake模型对谷脊线进行平滑优化。设定的点模型为P={p1, p2,…, pN}, pi∈R3。算法步骤如下（图1）：

步骤1. 计算主曲率。采用三次多项式拟合采样点的局部邻域，得到采样点的局部隐式曲面表达式，从而计算出采样点的主曲率。

步骤2. 提取谷脊特征点。根据谷脊点定义标记出谷脊特征点。

步骤3. 生成谷脊折线。根据最小主曲率对应的主方向，采用启发式搜索的方法对谷脊点进行连接，生成初始谷脊折线。

步骤4. 谷脊折线优化。对于生成的每一条折线，将其作为初始的主动轮廓线，定义能量函数并求其最小值，以优化谷脊折线得到光滑的谷脊线。

图1 谷脊线提取与优化算法流程

2 谷脊点的提取

根据拟合的采样点的局部隐式曲面，计算出采样点的主曲率值，并通过设置曲率阈值筛选出潜在的谷脊特征点。

2.1 谷脊点的定义

谷点和脊点是曲面局部邻域内主曲率沿主方向变化的极值点，能够很好地表征三维物体的几何形状。谷点为待重建曲面凹部的极值点，脊点为待重建曲面凸部的极值点。在三维曲面中，曲面上某一点处的主曲率衡量了曲面在该点的不同方向的弯曲程度。因此，待重建曲面上的离散点在不同方向有多个不同的曲率值，最大的曲率值称为最大主曲率记为kmax，取得最大主曲率的方向是最大主方向，记为 tmax；最小的曲率值称为最小主曲率记为kmin，取得最小主曲率的方向称为最小主方向，记为 tmin；数学上可以证明，最大主方向与最小主方向是相互垂直的。谷脊点的定义[19]为：谷点是在tmin方向上局部主曲率变化取得极小值且 ki<0的点，即：

脊点是在tmax方向上局部主曲率变化取得极大值且ki>0的点，即：

2.2 谷脊点提取

根据谷脊点的定义可知，要提取谷脊点需要求得采样点的主曲率，为了更准确地计算采样点主曲率ki，对采样点进行局部拟合。通过已有研究工作对点模型进行基于Mean Shift的几何特征性聚类[20]，得到多个聚类单元，然后采用三次多项式对每个聚类单元进行局部曲面拟合。设c为聚类单元中心，在c处建立局部坐标系(c; u, v, w)，c为原点，(u, v)平面是与c点处法向正交的平面，w为c点处法向的方向。局部待拟合曲面g(x)设为：

拟合曲面与原始曲面的误差度量为：

式(1)、(2)中，x=(u, v, w)为点pi在局部坐标系中的坐标表示。其中的未知系数通过对下式求最小值得出。

其中，Ps为当前聚类单元，ωi是类高斯函数，用以控制邻域点到中心点的权重。聚类单元中的点离中心点越近，对拟合精度的影响越大，其权重较大；相反，聚类单元中离中心点较远的点，对拟合精度的影响较小，其权重较小。

根据局部曲面的隐式表达式g(x)，计算曲面的第一、第二基本量进而求得pi点的高斯曲率、平均曲率、最大主曲率和最小主曲率。图 2给出了Fandisk点模型各曲率的可视化效果，最大、最小主曲率有效地识别出谷脊特征属性。设定曲率阈值ε，当kmax>ε时，将pi标记为脊点，加入脊点集 ；当kmin＜-ε时，将pi标记为谷点，加入谷点集 。如图2所示，粉色表示脊点区域，深蓝色表示谷点区域。

图2 使用平均曲率、高斯曲率、最大、最小主曲率标记Fandisk模型

3 谷脊线生成与优化

3.1 谷脊线的生成

最大主曲率对应的主方向是采样点曲率变化最大的方向，即凹凸变化最大的方向；最小主曲率对应的主方向是采样点曲率变化最小的方向，即相对平缓的方向（即现实模型中山脊或者山谷对应的方向），因此，本文通过在采样点pi的k-近邻域Nk( pi)内根据最小主曲率对应的主方向tmin将谷脊点进行连接，以避免采用最小生成树构造特征线的复杂过程。由于谷点和脊点可以通过变换z轴的方向相互转换，因此，以脊点为例描述连接方法，谷点连接不再赘述。

采用启发式搜索[21]的思想对脊点进行连接，步骤如下：

步骤2. 若Nk(ri)内不存在脊点，那么特征线连接结束；返回步骤1重新选取未连接过的脊点进行连接，直到所有脊点都被连接。

步骤3. 遍历谷脊特征线的每个节点，如果一个节点连接的两条短线段之间的夹角，小于某一角度，那么就消除这个节点，将其他两个点直接连接成线。

图3 脊点的连接

3.2 谷脊线的优化

在3.1节所得到的初始谷脊线是谷脊点直接首尾连接的结果，呈现为锯齿状的折线。在三维模型分割应用中，折线是可以满足分割要求的，但在特征线提取中，折线会造成后期渲染质量低劣，可视化效果不好，因此需要一种机制来对初始谷脊特征线进行平滑优化。常用的特征线优化方法有B样条拟合法[22]，然而该方法缺乏灵活性，且对于特征线平滑度和精确度地控制不好。Kass等[23]首次提出了主动轮廓模型(active contour model, ACM)，又称为Snake模型，用于检测图像的特征。

Snake模型是一种目标轮廓提取模型，其本质是一条二维可形变的弹性曲线。Snake模型的基本思想是在图像目标特征边界附近给出初始轮廓，该轮廓在自身内力、图像力等外力的共同作用下作变形运动，通过能量最小化使Snake收敛，最终逼近图像目标特征边界。

原始的Snake模型定义为在s∈[0, 1]上的参数曲线，即v(s)=[x(s), y(s)]，其中x(s)和y(s)分别表示每个控制点在图像中的坐标位置，s是以傅立叶变换形式描述边界的自变量。与模型相关的Snake能量函数定义如下：

内部能量函数定义为：

外部能量函数定义为：

Snake模型广泛应用于二维图像的轮廓提取和图像分割，文献[14]将其引入到三维模型特征线的提取中，取得了较好的效果，本文将Snake模型引入到谷脊线的优化中。

根据Snake模型的相关知识，结合本文谷脊特征线优化的目的，对 Snake模型进行分析。Snake模型有许多其他优化方法无法企及的特性：

(1) 将特征、初始轮廓、目标轮廓和基于知识的约束都融合在同一过程中；

(2) 初始轮廓确定后，可以自主地移动直至收敛至能量最小状态；

(3) 能量极小化可以极大地扩展捕获区域，降低计算复杂度。

这些好的特性在三维模型谷脊特征线优化的应用中发挥着重要的作用，然而Snake模型也有其自身的缺点：

(1) 对初始位置要求很高，需要确保初始轮廓线在特征区域附近；

(2) 由于主动轮廓线的非凸性，收敛的过程可能会存在发散的可能。

基于以上分析，3.1节中所得初始谷脊线在特征区域附近，因此将谷脊折线作为初始轮廓线完全符合Snake模型对初始位置的要求。

将脊（或谷）折线作为初始轮廓线，它在内力与外力的共同作用下存在变形能，使其偏向于能量最小的位置移动，经过多次移动收敛得到光滑的谷脊线。内部能量函数由拉伸能和弯曲能组成，在pi点的内部能量可以表示为：

其中，Et(pi)是在pi点处的拉伸能，Eb(pi)是在pi点处的弯曲能，分别为：

其中，θi为向量 pi-1pi和向量pipi+1之间的夹角，α和β为控制参数，用于将能量分量归一化到[0,1]范围内。

当初始轮廓线位于目标轮廓线附近时，外部能量通常取为点云在该点处的特征能。本文中连接得到的谷脊折线显然位于目标谷脊线附近，因此，外部能Eext(pi)为该点处的特征能 Ef(pi)，其主要相关特征属性为曲率值，因此定义如下：

其中，k( pi)表示点pi处的最大主曲率，γ用于将外部能量归一化。

在Snake迭代过程中，谷脊折线的节点都会移动到局部邻域内能量最小的位置。单次迭代的实现算法如下，其中 resample( pi)是重采样[24]函数，m是重采样点的个数。

图 4给出了脊线平滑的局部过程和局部效果图，图4(a)对相邻3个脊点进行分析，将中间脊点调整至局部重采样点中能量最小的点处，图4(b)显示了一段脊线平滑前后的效果比较。

图4 脊线的平滑

4 实验结果与分析

在VS2010环境下采用C++和OpenGL实现了本文的谷脊特征线提取算法，硬件平台为1.8 GHz奔腾处理器、2 GB内存的PC机。

图5为本文算法得到的一系列点模型的谷脊线效果图，可以看出，本文方法能很好地计算出点模型上的关键谷脊特征线条，可以很好地把握模型的主要几何形状。

为测试本文算法的鲁棒性，本文对点模型加入不同程度的噪声进行实验结果比较。加入噪声的方法是使点云中的点偏离原始位置随机值，随机值分布服从高斯分布，通过改变µ的值控制加入噪声的程度。图6中µ分别取0.00、0.01、0.05时，本文算法对Vase点模型的谷脊线提取效果，从图6可以看出，本文算法是鲁棒的，在有噪声的情况下仍然可以较好地提取出谷脊特征线，其主要原因是本文采用抗噪的Mean Shift进行聚类，并进行三次隐式曲面拟合，在处理含有大量噪声的模型时仍然可以保持良好的稳定性。

图7为文献[9]和本文方法的Dolphin点模型和RockArm点模型的谷脊线提取效果对比，文献[9]中首先对点模型进行空间分割，然后对点模型进行全局拟合，求得主曲率值进行谷脊特征的提取；本文方法首先对点模型进行Mean Shift聚类，对聚类单元进行局部拟合，求得主曲率值进行谷脊特征提取。由图7中Dolphin点模型的身体部分(图7(c)、(d)中放大区域)和RockArm点模型的型号烙印部分（图7(g)、(h)中放大部分）可以看出，本文方法的谷脊线提取效果更加光滑，其主要原因是本文采用表面特征相似性的Mean Shift聚类作为局部曲面拟合域，从而提高了拟合质量，所求曲率值更加准确。

图8出示了Venus点模型和Dragon点模型的文献[8]方法与本文方法的效果对比，由图8(b)、(c)中放大区域可以看出，本文算法对特征更加敏感，谷脊线更加光滑；同时通过对比图8(d)、(e)，很显然本文算法得到的 Dragon点模型头部的谷脊线更加光滑，连续性更好。其主要原因是本文对点模型直接进行三次曲面拟合，并采用Snake模型对谷脊线进行优化；而文献[8]是对点模型进行局部平面拟合后投影到曲面上，该过程会产生较大误差，影响曲率值的准确性，进而影响谷脊特征判断。

图5 Buddha、Armadillo、Lasso、Dragon点模型的谷脊线效果

图6 不同噪声影响下Vase点模型谷脊线效果

图7 文献[9]方法与本文方法比较

图8 文献[8]方法与本文方法效果比较

5 结 束 语

本文提出了一种基于Snake模型的点模型谷脊线提取与优化方法。首先对点模型进行了表面特征相似性的Mean Shift聚类，并在聚类单元上进行曲面拟合，以求得准确的曲率值。为了使得提取的谷脊线更加光滑，采用基于Snake模型的迭代方法对谷脊线进行优化处理，通过定义能量函数并求解能量函数的最小值，使谷脊线收敛至局部能量最小处，得到光滑谷脊线。实验结果表明，本文算法是鲁棒的，对特征有较强的敏感性。

从实验结果可知，本文算法能提取出较为光滑的谷脊特征线，但仍然存在谷脊线之间有裂缝的情况。为解决这个问题，未来工作需要对谷脊线的连接进行更加深入的研究，同时Snake模型迭代优化较为耗时，寻求一种高效稳定的优化算法也是研究方向之一。

[1] 王仁芳, 李继芳, 杨 庆, 等. 点模型的快速高质量绘制[J]. 计算机辅助设计与图形学学报, 2010, 22(2): 191-197.

[2] 王仁芳, 张三元. 数字几何处理的若干问题研究进展[M].北京: 清华大学出版社, 2012: 33-34.

[3] 朱 建, 杨 龙, 刘维星, 等. 显著性特征保持的点云模型缩放[J]. 计算机辅助设计与图形学学报, 2014, 26(10): 1624-1632.

[4] 王爱霖, 刘 弘, 张桂娟. 基于谷脊线特征的三维网格模型简化方法[J]. 计算机辅助设计与图形学学报, 2014, 26(5): 788-793.

[5] Daniels II J, Ha L K, Ochotta T, et al. Robust smooth feature extraction from point clouds [C]//Proceedings of IEEE International Conference on Shape Modeling and Applications Los Alamitos. Lyon, France, 2007: 1123-1136.

[6] Kim S K. Extraction of ridge and valley lines from unorganized points [J]. Multimedia Tools and Applications, 2012, 63(1): 265-279.

[7] Weber C, Hahmann S, Hagen H, et al. Sharp feature preserving MLS surface reconstruction based on local feature line approximations [J]. Graphical Models, 2012, 74(6): 335-345.

[8] 庞旭芳, 庞明勇, 肖春霞. 点云模型谷脊特征的提取与增强算法[J]. 自动化学报, 2010, 36(8): 1073-1083.

[9] Ohtake Y, Belyaev A, Alexa M. Sparse low-degree implicit surfaces with application to high quality rendering, feature extraction, and smoothing [C]// Proceedings of Eurographics Symposium on Geometry. Vienna, Austria, 2005: 148-158.

[10] Ohtake Y, Belyaev A, Seidel H P. 3D scattered data approximation with adaptive compactly supported radial basis functions [C]//Shaping Modeling International. Riken, Japan, 2004: 31-39.

[11] Ohtake Y, Belyaev A, Seidel H P. Ridge-valley lines on meshes via implicit surface fitting [C]//Proceedings of ACM SIGGRAPH. Los Angeles, Califonia, USA, 2004: 6, 8. [12] Demarsin K, Vanderstraeten D, Volodine T, et al. Detection of closed sharp feature lines in point clouds for reverse engineering applications [C]//Report TW458 Department of Computer Science. Pittsburgh, PA, USA, 2006: 571-577.

[13] Gumhold S, Wang Xinlong, MacLeod R. Feature extraction from point cloud [C]//Proceedings of 10th International Meshing Roundtable. Berlin, Germany, 2001: 293-305.

[14] Pauly M, Keiser R, Gross M. Multi-scale feature extraction on point-sampled surfaces [J]. Computer Graphics Forum, 2003, 22(3): 281-289.

[15] Park M K, Lee S J, Lee K H. Multi-scale tensor voting for feature extraction from unstructured point clouds [J]. Graphical Models, 2012, 74(4): 197-208.

[16] Weber C, Hahmann S, Hagen H. Sharp feature detection in point clouds [C]//Proceedings of the Shape Modeling International Conference. Washington DC, USA, 2010: 175-186.

[17] Kalogerakis E, Simari P, Nowrouzezahrai D, et al. Robust statistical estimation of curvature on discretized surfaces [C]// Proceedings of Symposium on Geometry. Switzerland, 2007: 13-22.

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

[19] Belyaev A G, Pasko A A, Kunii T L. Ridges and ravines on implicit surfaces [C]//Computer Graphics International. Washington, DC, USA, 1998: 530-535.

[20] 王仁芳, 徐慧霞, 陈仲委, 等. 点模型微分属性的估算及其应用[J]. 自动化学报, 2011, 37 (12): 1474-1482.

[21] 张长东, 戴 宁, 廖文和, 等. 基于启发式搜索策略的牙齿生物特征线提取技术[J]. 中国机械工程学报, 2012, 23(13): 1567-1586.

[22] 徐 进. 带约束的 B样条曲线曲面延伸技术[J]. 图学学报, 2013, 34(3): 36-42.

[23] Kass M, Witkin A, Terzopoulos D. Snakes: active contour models [J]. International Journal of Computer Vision, 1987, 1(4): 321-331.

[24] 左军毅, 张怡哲, 梁 彦. 自适应不完全重采样粒子滤波器[J]. 自动化学报, 2012, 38(4): 647-652.

Extraction of Valley-Ridge Lines from Point-Sampled Geometry with Snake

Zhang Ruonan1,2, Wang Renfang2
(1. College of Information Science, Shanghai Ocean University, Shanghai 201306, China; 2. College of Computer Science and Information Technology, Zhejiang Wanli University, Ningbo Zhejiang 315100, China)

Based on the active contour model, a robust algorithm is proposed for extracting and optimizing valley-ridge lines from point-sampled geometry (PSG). First, local implicit surface of the PSG is reconstructed, and the curvature of every sampling point is computed. Potential valley-ridge points are then obtained by solving the extreme of the main curvature, and potential valley-ridge points is connected into valley-ridge polylines according to the main direction of the feature points. Finally, snake model is used to smooth the valley-ridge polyline. Experimental results show that the algorithm is robust and can generate smooth valley-ridge lines.

point-sampled geometry; feature extraction; valley; ridge; Snake model

TP 391

A

2095-302X(2015)05-0662-09

2015-04-17；定稿日期：2015-05-18

浙江省科技计划资助项目(2012C21004)；浙江省大学生科技创新(新苗人才计划)(2014R419028)；宁波市自然科学基金资助项目(2013A610111)

张若男(1990-)，女，山东博兴人，硕士研究生。主要研究方向为数字几何处理。E-mail：ruonanzh@sina.com

王仁芳(1974-)，男，河南南阳人，教授，博士。主要研究方向为数字几何处理。E-mail：renfang_wang@126.com