２０１５年 ｌ０月 图学学报 ＪＯＵＲＮＡＬ ＯＦ ＧＲＡＰＨＩＣＳ Ｏｃｔｏｂｅｒ ２０１５ Ｖ０１．３６ Ｎｏ．５ 第３６卷 第５期 基于Ｓｎａｋｅ的点模型谷脊线提取与优化 张若男 ，一， 王仁芳２ （１．上海海洋大学信息学院，上海２０１３０６； ２．浙江万里学院计算机与信息学院，浙江宁波３１５１００） 摘 要：基于主动轮廓模型（Ｓｎａｋｅ模型），提出一种点模型的谷脊线提取与优化方法。首先 构建点模型的局部隐式曲面，并求出采样点的曲率值：然后通过求解主曲率极值点得到潜在谷脊 点，依据特征点的主方向连接谷脊点生成谷脊折线段；最后利用主动轮廓模型对谷脊折线段进行 优化。实验结果表明，算法是鲁棒的且能够生成光滑的谷脊线。 关键词：点模型； 特征提取；谷：脊；Ｓｎａｋｅ模型 中图分类号：ＴＰ ３９１ 文献标识码：Ａ 文章编号：２０９５—３０２Ｘ（２０１ ５）０５．０６６２—０９ Ｅｘｔｒａｃｔｉｏｎ ｏｆ Ｖａｌｌｅｙ－Ｒｉｄｇｅ Ｌｉｎｅｓ ｆｒｏｍ Ｐｏｉｎｔ—Ｓａｍｐｌｅｄ Ｇｅｏｍｅｔｒｙ ｗｉｔｈ Ｓｎａｋｅ Ｚｈａｎｇ Ｒｕｏｎａｎ ，一，Ｗａｎｇ Ｒｅｎｆａｎｇ （１．Ｃｏｌｌｅｇｅ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ，Ｓｈａｎｇｈａｉ Ｏｃｅａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０１３０６，Ｃｈｉｎａ； ２．Ｃｏｌｌｅｇｅ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ ＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，Ｚｈｅｊｉａｎｇ Ｗａｎｌｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｎｉｎｇｂｏ Ｚｈｅｊｉｎｇ ａ３１５１００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｂａｓｅｄ ｏｎ ｔｈｅ ａｃｔｉｖｅ ｃｏｎｔｏｕｒ ｍｏｄｅｌ，ａ ｒｏｂｕｓｔ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ ｆｏｒ ｅｘｔｒａｃｔｉｎｇ ａｎｄ ｏｐｔｉｍｉｚｉｎｇ ｖａｌｌｅｙ－ｒｉｄｇｅ ｌｉｎｅｓ ｆｒｏｍ ｐｏｉｎｔ－ｓａｍｐｌｅｄ ｇｅｏｍｅｔｒｙ（ＰＳＧ）．Ｆｉｒｓｔ，ｌｏｃａｌ ｉｍｐｌｉｃｉｔ ｓｕｒｆａｃｅ ｏｆ ｔｈｅ ＰＳＧ ｉｓ ｒｅｃｏｎｓｔｒｕｃｔｅｄ，ａｎｄ ｔｈｅ ｃｕｒｖａｔｒｅ ｏｆ ｕｅｖｅｒｙ ｓａｍｐｌｉｎｇ ｐｏｉｎｔ ｉｓ ｃｏｍｐｕｔｅｄ．Ｐｏｔｅｎｔｉａｌ ｖａｌｌｅｙ－ｒｉｄｇｅ ｐｏｉｎｔｓ ａｒｅ ｔｈｅｎ ｏｂｔａｉｎｅｄ ｂｙ ｓｏｌｖｉｎｇ ｔｈｅ ｅｘｔｒｅｍｅ ｏｆ ｔｈｅ ｍａｉｎ ｃｕｒｖａｔｒｅ，ａｎｄ ｕｐｏｔｅｎｔｉａｌ ｖａｌｌｅｙ—ｒｉｄｇｅ ｐｏｉｎｔｓ ｉｓ ｃｏｎｎｅｃｔｅｄ ｉｎｔｏ ｖａｌｌｅｙ—ｒｉｄｇｅ ｐｏｌｙｌｉｎｅｓ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｍａｉｎ ｄｉｒｅｃｔｉｏｎ ｏｆ ｔｈｅ ｆｅａｔｒｅ ｐｏｉｕｎｔｓ．Ｆｉｎａｌｌｙ， ｓｎａｋｅ ｍｏｄｅｌ ｉｓ ｕｓｅｄ ｔｏ ｓｍｏｏｔｈ ｔｈｅ ｖａｌｌｅｙ－ｒｉｄｇｅ ｐｏｌｙｌｉｎｅ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｒｏｂｕｓｔ ａｎｄ ｃａｎ ｇｅｎｅｒａｔｅ ｓｍｏｏｔｈ ｖａｌｌｅｙ－ｒｉｄｇｅ ｌｉｎｅｓ． Ｋｅｙｗｏｒｄｓ：ｐｏｉｎｔ—ｓａｍｐｌｅｄ ｇｅｏｍｅｔｒｙ；ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ；ｖａｌｌｅｙ；ｒｉｄｇｅ；Ｓｎａｋｅ ｍｏｄｅｌ 随着三维扫描设备和获取技术的快速发展，点 取过程中易受噪声影响。因此，点模型特征线的提 取仍是一项挑战性工作。 模型的数字几何处理已经成为数字几何处理领域 的研究热点【ｌ。Ｊ。特征线是三维几何模型的重要组成 部分，对其外观及准确表达具有重要的作用，因此 现有的特征线提取方法大致分为３类：①基于 曲面拟合的方法［５－１Ｉ］。文献［５］提出了一种基于鲁棒 的移动最小二乘法ｆｒｏｂｕｓｔ ｍｏｖｉｎｇ ｌｅａｓｔ ｓｑｕａｒｅ， ＲＭＬＳ）的特征线提取方法，该方法首先通过ＲＭＬＳ 特征线的提取在几何分析、曲面重建与编辑以及数 据分块等方面有着非常广泛地应用。在数字几何处 理领域，网格模型特征提取的研究工作已取得一定 算子收集候选特征点并对候选点分别进行ＲＭＬＳ 的成果【４］，然而点模型特征提取的研究工作相对较 少，主要原因是点模型缺乏拓扑连接关系，且在获 收稿日期：２０１５．０４．１７；定稿日期：２０１５．０５．１８ 局部拟合，然后将候选特征点投影到最近的曲面交 线上，对投影点进行光顺处理，最后通过特征折线 基金项目：浙江省科技计划资助项Ｉ￣－１（２０１２Ｃ２１００４）：浙江省大学生科技创新（新苗人才计￣ｉｊ）（２０１４Ｒ４１９０２８）；宁波市自然科学基金资助项Ｎ（２０１３Ａ６１０１１１） 作者简介：￣（１９９０一），女，山东博兴人，硕士研究生。主要研究方向为数字几何处理。Ｅ—ｍａｉｌ：ｒｕｏｎａｎｚｈ＠ｓｉｎａ．ｃｏｒｎ 通讯作者：王仁芳（１９７４一），男，河南南阳人，教授，博士。主要研究方向为数字几何处理。Ｅ—ｍａｉｌ：ｒｅｎｆａｎｇｗａｎｇ＠１２６．ｃｏｍ 第５期 张若男等：基于Ｓｎａｋｅ的点模型谷脊线提取与优化 ６６３ 生长获得特征线。该方法对特征点的识别主要取决 类，然后依据法向聚类的个数判别当前点是否为特 于尖锐边上的投影点，因此 线韵提取效果比较 征点，最后用特征折线生长算法连接得到特征线。 精确，但该方法基于ＲＭＬＳ拟合，时间代价较大。 由于该算法需要对采样点邻域进行三角网格化，从 文献［８］将ＲＭＬＳ引入到点云谷脊特征线提取的研 而增加了运算的复杂度，且存在跨越特征边的三角 究中，实现了点云模型谷脊线的较准确提取，但由 形，由此降低了特征识别的准确性。 于没有进行优化，最终效果不够光滑。针对网格模 为了能鲁棒地提取出光滑的特征线，本文提出 型，文献ｉ１ｌ１提出了一种基于局部拟合的谷脊线提 一种基于主动轮廓模型的谷脊特征线提取方法。通 取方法，该方法是采用紧支撑径向函数（ｃｏｍｐａｃｔｌｙ 过构建点模型的局部隐式曲面，求出采样点的曲率 ｓｕｐｐｏｓｅｄ ｒａｄｉａｌ ｂａｓｉｓ ｆｕｎｃｔｉｏｎｓ，ＣＳ—ＲＢＦｓ）拟合三角 值；通过求解主曲率极值得到潜在谷脊点，并依据 网格曲面，并将网格点投影到拟合曲面上，计算曲 谷脊点的主方向连接谷脊点生成谷脊折线；利用主 率梯度和曲率张量，然后计算网格边端点的最大最 动轮廓模型对谷脊线进行优化。 小主曲率，跟踪检测出所有谷脊特征点。该方法在 网格模型上取得了良好的效果，但仍然有谷脊线连 １ 算法概述 接性较弱的问题，并且该方法效率较低。②基于主 本文算法思想是通过三次多项式拟合点模型 成分分析的方法 ２’ ］。文献［１２］通过主成分分析法 的局部隐式曲面，根据最大、最小主曲率标记出潜 （ｐｒｉｎｃｉｐａｌ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ，ＰＣＡ）来计算采样点的 在的谷脊特征点，然后采用启发式搜索法分别对谷 法向，并根据采样点局部邻域内法向的变化对点模 脊点进行连接，并采用Ｓｎａｋｅ模型对谷脊线进行平 型进行分类，然后在不同分类的边界点构造最小生 滑优化。设定的点模型为Ｐ＝ １，ｐ２，…，ＰＮ｝，Ｐ ∈ 。 成树，最后生成特征线。文献［１３】通过构造黎曼树 算法步骤如下（图１）： 建立点云的拓扑连接信息，利用局部邻域的协方差 步骤１．计算主曲率。采用三次多项式拟合采 矩阵的特征值计算某一点属于特征点的可能，构造 样点的局部邻域，得到采样点的局部隐式曲面表达 最小生成树来确定特征线。文献［１４］提出了点模型 式，从而计算出采样点的主曲率。 的特征检测算法，该算法首先基于多尺度的协方差 步骤２．提取谷脊特征点。根据谷脊点定义标 分析得到点模型的特征区域，然后利用最小生成树 记出谷脊特征点。 算法将特征区域连接，最后对特征线进行非真实感 步骤３．生成谷脊折线。根据最小主曲率对应 绘制。尽管这些方法能够提取点模型的特征线，但 的主方向，采用启发式搜索的方法对谷脊点进行连 是对噪声较为敏感，同时对细微特征的提取效果有 接，生成初始谷脊折线。 限。③基于统计的方法【ｌ 】。文献【１６］提出一种基 步骤４．谷脊折线优化。对于生成的每一条折 于高斯法向聚类的特征提取方法，首先在一点局部 线，将其作为初始的主动轮廓线，定义能量函数并 邻域内构建当前点及其邻域点组成的所有三角形 求其最小值，以优化谷脊折线得到光滑的谷脊线。 集合，利用高斯法向聚类算法对三角形法向进行聚 原始点模型 计算主曲率 谷脊点提取 谷脊线提取 谷脊线优化 图１谷脊线提取与优化算法流程 ２谷脊点的提取 一点处的主曲率衡量了曲面在该点的不同方向的 弯曲程度。因此，待重建曲面上的离散点在不同方 根据拟合的采样点的局部隐式曲面，计算出采 向有多个不同的曲率值，最大的曲率值称为最大主 样点的主曲率值，并通过设置曲率阈值筛选出潜在 曲率记为‰ ，取得最大主曲率的方向是最大主方 的谷脊特征点。 向，记为ｆｍ ；最小的曲率值称为最小主曲率记为 ２．１谷脊点的定义 ｉｎ，取得最小主曲率的方向称为最小主方向，记 谷点和脊点是曲面局部邻域内主曲率沿主方 为 数学上可以证明，最大主方向与最小主方 向变化的极值点，能够很好地表征三维物体的几何 向是相互垂直的。谷脊点的定义［１ ９Ｊ为：谷点是在 形状。谷点为待重建曲面凹部的极值点，脊点为待 方向上局部主曲率变化取得极小值且ｋｉ＜Ｏ的点， 重建曲面凸部的极值点。在三维曲面中，曲面上某 即： 第５期 张若男等：基于Ｓｎａｋｅ的点模型谷脊线提取与优化 步骤２．若＾ ｒ ）内不存在脊点 那么特征线连 步骤３．遍历谷脊特征线的每个节点，如果一个 节点连接的两条短线段之间的夹角，小于某一角度， 接结束；返回步骤１重新选取兼连接过的脊点进行 连接，直到所有脊点都被连接 那么就消除这个节点，将其他两个点直接连接成线。 （ａ） ，ｆ）内只有１个新的脊点 （ｂ） ｒｆ）内有２个或２个以上的脊点 图３脊点的连接 ３．２谷脊线的优化 提取中，取得了较好的效果，本文将Ｓｎａｋｅ模型引 入到谷脊线的优化中。 在３．１节所得到的初始谷脊线是谷脊点直接首 尾连接的结果，呈现为锯齿状的折线。在三维模型 分割应用中，折线是可以满足分割要求的，但在特 根据Ｓｎａｋｅ模型的相关知识，结合本文谷脊特 征线优化的目的，对Ｓｎａｋｅ模型进行分析。Ｓｎａｋｅ 模型有许多其他优化方法无法企及的特性： 征线提取中，折线会造成后期渲染质量低劣，可视 化效果不好，因此需要一种机制来对初始谷脊特征 线进行平滑优化。常用的特征线优化方法有Ｂ样条 拟合法［２ ，然而该方法缺乏灵活性，且对于特征线 平滑度和精确度地控制不好。Ｋａｓｓ等［２３］首次提出了 主动轮廓模型（ａｃｔｉｖｅ ｃｏｎｔｏｕｒ ｍｏｄｅｌ，ＡＣＭ），又称为 Ｓｎａｋｅ模型，用于检测图像的特征。 ｆ１）将特征、初始轮廓、目标轮廓和基于知识 的约束都融合在同一过程中； （２）初始轮廓确定后，可以自主地移动直至收 敛至能量最小状态； （３）能量极小化可以极大地扩展捕获区域，降 低计算复杂度。 Ｓｎａｋｅ模型是一种目标轮廓提取模型，其本质 是一条二维可形变的弹性曲线。Ｓｎａｋｅ模型的基本 思想是在图像目标特征边界附近给出初始轮廓，该 这些好的特性在三维模型谷脊特征线优化的 应用中发挥着重要的作用，然而Ｓｎａｋｅ模型也有其 自身的缺点： 轮廓在自身内力、图像力等外力的共同作用下作变 形运动，通过能量最小化使Ｓｎａｋｅ收敛，最终逼近 图像目标特征边界。 原始的Ｓｎａｋｅ模型定义为在Ｓ∈［０，１］上的参数 曲线，即 ）＝ （ ）， ）］，其中 （ ）和 ）分别表示 （１）对初始位置要求很高，需要确保初始轮廓 线在特征区域附近； （２）由于主动轮廓线的非凸性，收敛的过程可 能会存在发散的可能。 基于以上分析，３．１节中所得初始谷脊线在特 每个控制点在图像中的坐标位置，Ｓ是以傅立叶变 换形式描述边界的自变量。与模型相关的Ｓｎａｋｅ能 量函数定义如下： 征区域附近，因此将谷脊折线作为初始轮廓线完全 符合Ｓｎａｋｅ模型对初始位置的要求。 将脊（或谷）折线作为初始轮廓线，它在内力 与外力的共同作用下存在变形能，使其偏向于能量 最小的位置移动，经过多次移动收敛得到光滑的谷 Ｉ Ｅ（ｖ（ｓ））ｄｓ＝Ｅ （Ｖ（ ））＋Ｅ （１，（ ）） 内部能量函数定义为： Ｅ加，（ｖ（ ））＝ 专 ｌｖ （ ）Ｉ ＋ＪＴｉｖ＂（ ）ｌ ｄ 外部能量函数定义为： Ｅ。ｍ（ （ ））＝ Ｉｍ （１，（ ）） Ｓｎａｋｅ模型广泛应用于二维图像的轮廓提取和 图像分割，文献［１４］将其引入到三维模型特征线的 脊线。内部能量函数由拉伸能和弯曲能组成，在Ｐ 点的内部能量可以表示为： 埘（ｐｆ）＝Ｅ，（ｐｆ）＋ ６（ｐ ） 其中， ）是在ｐ 点处的拉伸能，Ｅｂ（Ｐｉ）是在ｐ 点 处的弯曲能，分别为： Ｅ，（ ）＝÷ （ＩｐＨＰ Ｉ＋ＩＰｉＰ川Ｉ） 图形学与可视化 ２０１５住 算法如下，其中ｒｅｓａｍｐｌｅ（ｐｆ）是重采样［２４１函数，ｍ 是重采样点的个数 ０ 其中， 为向量 Ｐ，和向量 一 ＋ 之间的夹角， ｆｏｒ（ｉ＝０；ｊ＜刀；ｆ＋＋） ｛Ｅｉ， ｉｘ＝Ｅ。 ａｋｅ（ｐｆ）：ＩＥｉｎｔ（ｐｉ）＋Ｅ。ｘｃ（ｐｆ） Ｓ＝ｒｅｓａｍｐｌｅ（ｐ／１ 和 为控制参数，用于将能量分量归一化到［Ｏ，１］范 围内。 当初始轮廓线位于目标轮廓线附近时，外部能 量通常取为点云在该点处的特征能。本文中连接得 ｆｏｒ（ｊ＝Ｏ； ； ＋） ， ｉ ） ｛Ｅ ａｋｅ（￥ｊ）＝Ｅｉｎｔ（Ｓｉ）＋Ｅｅｘｔ（Ｓｊ） 到的谷脊折线显然位于目标谷脊线附近，因此，外 部能 ，（ ）为该点处的特征能Ｅ，（ｐ ），其主要相关 特征属性为曲率值，因此定义如下： ｉｆ（Ｅ￣ ｋｅ（ ｛Ｅｌ， ｉｎ＝Ｅ ａｋｅ（ Ｐｉ，ｍｉｎ ｝ ｝ Ｅ （ ）＝Ｅ，（Ｐｆ）＝ｙｅ 其中， ｐｆ）表示点ｐ 处的最大主曲率， 用于将外 部能量归一化。 ） 图４给出了脊线平滑的局部过程和局部效果 图，图４（ａ１对相邻３个脊点进行分析，将中间脊点 调整至局部重采样点中能量最小的点处，图４（ｂ）显 示了一段脊线平滑前后的效果比较。 在Ｓｎａｋｅ迭代过程中，谷脊折线的节点都会移 动到局部邻域内能量最小的位置。单次迭代的实现 ０ ０ ０ （ａ）相邻３个脊点优化示意 图４脊线的平滑 （ｂ）一小段脊线优化示意 ４实验结果与分析 在ＶＳ２０１０环境下采用Ｃ＋＋和ＯｐｅｎＧＬ实现了 曲面拟合，在处理含有大量噪声的模型时仍然可以 保持良好的稳定性。 图７为文献［９］和本文方法的Ｄｏｌｐｈｉｎ点模型和 ＲｏｃｋＡｒｍ点模型的谷脊线提取效果对比，文献［９】 中首先对点模型进行空间分割，然后对点模型进行 全局拟合，求得主曲率值进行谷脊特征的提取；本 文方法首先对点模型进行Ｍｅａｎ Ｓｈｉｔ聚类，对聚类 ｆ本文的谷脊特征线提取算法，硬件平台为１．８ ＧＨｚ 奔腾处理器、２ ＧＢ内存的ＰＣ机。 图５为本文算法得到的一系列点模型的谷脊线 效果图，可以看出，本文方法能很好地计算出点模 型上的关键谷脊特征线条，可以很好地把握模型的 主要几何形状。 单元进行局部拟合，求得主曲率值进行谷脊特征提 取。由图７中Ｄｏｌｐｈｉｎ点模型的身体部分（图７（ｃ）、 为测试本文算法的鲁棒性，本文对点模型加入 不同程度的噪声进行实验结果比较。加入噪声的方 法是使点云中的点偏离原始位置随机值，随机值分 布服从高斯分布，通过改变 的值控制加入噪声的 程度。图６中 分别取０．００、Ｏ．０１、０．０５时，本文 算法对Ｖａｓｅ点模型的谷脊线提取效果，从图６可以 （ｄ）ｑｈ放大区域１和ＲｏｃｋＡｒｍ点模型的型号烙印部分 （图７（ｇ）、（ｈ）中放大部分）可以看出，本文方法的 谷脊线提取效果更加光滑，其主要原因是本文采用 表面特征相似性的Ｍｅａｎ Ｓｈｉｔ聚类作为局部曲面拟 ｆ合域，从而提高了拟合质量，所求曲率值更加准确。 图８出示了Ｖｅｎｕｓ点模型和Ｄｒａｇｏｎ点模型的 看出，本文算法是鲁棒的，在有噪声的情况下仍然 可以较好地提取出谷脊特征线，其主要原因是本文 采用抗噪的Ｍｅａｎ Ｓｈｉｆｔ进行聚类，并进行三次隐式 文献［８］方法与本文方法的效果对比，由图８（ｂ）、（Ｃ） 中放大区域可以看出，本文算法对特征更加敏感， 谷脊线更加光滑；同时通过对比图８（ｄ）、（ｅ），很显 第５ ｊＪｆ】 张符 等：娃ｊ Ｓｎａｋｅ的点模型 脊线提取 优化 ６６７ 然本文算法得到的Ｄｒａｇｏｎ点模型头部的谷脊线更 『Ｊ【Ｊ光滑，连续性更好。其主要原因是本文对点模型 线进行优化；而文献［８］是对点模型进行局部平而拟 合后投影到曲面上，该过程会产牛较人误蒂，影响 曲率值的准确性，进而影响谷脊特征判断。 直接进行三次曲面拟合，并采用Ｓｎａｋｅ模型对谷脊 （Ｃ）Ｌａｓｓｏ （ｄ）Ｄｒａｇｏｎ 图５ Ｂｕｄｄｈａ、Ａｒｍａｄｉｌｌｏ、Ｌａｓｓｏ、Ｄｒａｇｏｎ点卞焚 的 脊线效ｌ果 （ａ） Ｆ０ （ｂ），Ｆ０．０ ｌ （ｃ） Ｆ０．０５ 图６不Ｈ噪声影响Ｆ Ｖａｓｅ点模 脊线效果 图形学与 ｝见化 ２０１５年 （ａ）Ｄｏｌｐｈｉｎ点模型文献［９］方法 最大丰曲率可视化 （ｂ）Ｄｏｌｐｈｉｎ点模型本文方法 最大 曲术町视化 （Ｃ）Ｄｏｌｐｈｉｎ点模型文献【９］方法 谷脊线提取效果 （ｄ）Ｄｏｌｐｈｉｎ点模型本文方法 谷脊线提取效果 （ｅ）ＲｏｃｋＡｒｍ点模型文献［９］方法 最大主曲率可视化 （ｆ）ＲｏｃｋＡｒｍ点模型本文方法 最大丰曲率可视化 （ｇ）ＲｏｃｋＡｒｍ点模型文献（９］方法 脊线提取效果 （ｈ）ＲｏｃｋＡｒｍ点模型本文方法 谷脊线提取效果 图７文献［９】方法与奉文方法比较 第５期 张若男等：基］ Ｓｎａｋｅ的点模型谷脊线提取与优化 ６６９ （ａ）Ｖｅｎｕｓ点模型 （ｂ）Ｖｅｎｕｓ点模型文献【８］方法 （Ｃ）Ｖｅｎｕｓ点模型本文方法 【ｄ）Ｄｒａｇｏｎ点模型文献［８］方法效果 （ｅ）Ｄｒａｇｏｎ点模型本文方法效果 图８文献［８］方法与本文方法效果比较 王 芳，张三元．数字几何处理的＿若干问题研究进展【Ｍ］． 北京：清华大学出版社，２０１２：３３—３４． ５结束语 本文提出了一种基于Ｓｎａｋｅ模型的点模型谷脊 线提取与优化方法。首先对点模型进行了表面特征 相似性的Ｍｅａｎ Ｓｈｉｆｔ聚类，并在聚类单元上进行曲 朱 建，杨龙，刘维星，等． 著性特征保持的点云 模 缩放［Ｊ］．计算机辅助设汁与 形学学报，２０１４， ２６（１０）：１６２４—１６３２． 而拟合，以求得准确的曲率值。为了使得提取的谷 脊线更加光滑，采用基于Ｓｎａｋｅ模型的迭代方法对 谷脊线进行优化处理，通过定义能量函数并求解能 量函数的最小值，使谷脊线收敛至局部能量最小 处，得到光滑谷脊线。实验结果表明，本文算法是 鲁棒的，对特征有较强的敏感性。 王爱森，刘 弘，张桂娟．基ｆ谷脊线特征的二维刚 格模型简化方法［Ｊ］＿计算机辅助发汁与图形学学报， ２０ｌ４，２６（５）：７８８—７９３． Ｄａｎｉｅｌｓ ＩＩ Ｊ，Ｈａ Ｌ ｋ Ｏｃｈｏｔｔａ ｅｔ ａ１．Ｒｏｂｕｓｔ ｓｍｏｏｔｈ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ ｆｒｏｍ ｐｏｉｎｔ ｃｌｏｕｄｓ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｈａｐｅ Ｍｏｄｅｌｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ Ｌｏｓ Ａｌａｍｉｔｏｓ．Ｌｙｏｎ，Ｆｒａｎｃｅ，２００７： ｌｌ２３一ｌ １３６． Ｋｉｍ Ｓ Ｋ．Ｅｘｔｒａｃｔｉｏｎ ｏｆ ｒｉｄｇｅ ａｎｄ ｖａｌｌｅｙ ｌｉｎｅｓ ｆｒｏｍ 从实验结果可知，本文算法能提取出较为光滑 的 脊特征线，但仍然存在谷脊线之间有裂缝的情 况。为解决这个问题，未来工作需要对 脊线的连 接进行更加深入的研究，同时Ｓｎａｋｅ模型迭代优化 较为耗时，寻求一种高效稳定的优化算法也是研究 方向之一。 ｕｎｏｒｇａｎｉｚｅｄ ｐｏｉｎｔｓ 【Ｊ］． Ｍｕｌｔｉｍｅｄｉａ Ｔｏｏｌｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２０１２，６３（１）：２６５—２７９． Ｗｅｂｅｒ Ｃ，Ｈａｈｍａｎｎ Ｓ，Ｈａｇｅｎ Ｈ，ｅｔ ａ１．Ｓｈａｒｐ ｆｅａｔｕｒｅ ｐｒｅｓｅｒｖｉｎｇ ＭＬＳ ｓｕｒｆａｃｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｌｏｃａｌ 参考文献 ［１］ 仁芳，李继芳，杨庆，等．点模型的快速高质量绘 ｆｅａｔｕｒｅ ｌｉｎｅ ａｐｐｒｏｘｉｍａｔｉｏｎｓ［Ｊ］．Ｇｒａｐｈｉｃａｌ Ｍｏｄｅｌｓ，２０ １ ２， ７４（６）：３３５—３４５． 制［Ｊ］＿计算机辅助设计与 形学学报，２０１０，２２（２）： １９１．１９７． ［８］ 庞旭芳，庞明勇，肖春霞．点云模型谷脊特征的提取与 增强算法［Ｊ］．自动化学报，２０１０，３６（８）：１０７３—１０８３． ６７０ 图形学与可视化 ２０１５焦 叫 ” Ｏｈｔａｋｅ Ｂｅｌｙａｅｖ Ａｌｅｘａ Ｍ．Ｓｐａｒｓｅ ｌｏｗ—ｄｅｇｒｅｅ ｉｍｐｌｉｃｉｔ ｓｕｒｆａｃｅｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｈｉｇｈ ｑｕａｌｉｔｙ ｒｅｎｄｅｒｉｎｇ，ｆｅａｔｒｕｅ ｅｘｔｒａｃｔｉｏｎ，ａｎｄ ｓｍｏｏｔｈｉｎｇ［ｃ］／／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｅｕｒｏｇｒａｐｈｉｃｓ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｇｅｏｍｅｔｒｙ． Ｖｉｅｎｎａ，Ａｕｓｔｒｉａ，２００５：１４８－１５８． Ｏｈｔａｋｅ Ｙ Ｂｅｌｙａｅｖ Ｓｅｉｄｅｌ Ｈ Ｒ ３Ｄ ｓｃａｔｔｅｒｅｄ ｄａｔａ ａｐｐｒｏｘｉｍａｔｉｏｎ ｗｉｔｈ ａｄａｐｔｉｖｅ ｃｏｍｐａｃｔｌｙ ｓｕｐｐｏｒｔｅｄ ｒａｄｉａｌ ｂａｓｉｓ ｆｕｎｃｔｉｏｎｓ［Ｃ］／／Ｓｈａｐｉｎｇ Ｍｏｄｅｌｉｎｇ Ｉｎｔｅｒｎａｔｉｏｎａ１． Ｒｉｋｅｎ，Ｊａｐａｎ，２００４：３ １－３９． Ｏｈｔａｋｅ Ｂｅｌｙａｅｖ Ａ，Ｓｅｉｄｅｌ Ｈ Ｅ Ｒｉｄｇｅ－ｖａｌｌｅｙ ｌｉｎｅｓ ｏｎ ｍｅｓｈｅｓ ｖｉａ ｉｍｐｌｉｃｉｔ ｓｕｒｆａｃｅ ｆｉｔｔｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭＳＩＧＧＲＡＰ Ｈ＿ＬｏｓＡｎｇｅｌｅｓ，Ｃａｌｉｆｏｎｉａ，ｕｓ＆２００４：６，８． Ｄｅｍａｒｓｉｎ ｌ（’Ｖａｎｄｅｒｓｔｒａｅｔｅｎ Ｄ，Ｖｏｌｏｄｉｎｅ Ｌ ｅｔ ａ１． Ｄｅｔｅｃｔｉｏｎ ｏｆ ｃｌｏｓｅｄ ｓｈａｒｐ ｆｅａｔｕｒｅ ｌｉｎｅｓ ｉｎ ｐｏｉｎｔ ｃｌｏｕｄｓ ｆｏｒ ｒｅｖｅｒｓｅ ｅｎｇｉｎｅｅｒｉｎｇ ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］／／Ｒｅｐｏｒｔ ＴＷ４５８ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ．Ｐｉｔｓｂｕｒｇｈ，ＰＡ，ＵＳＡ， ２００６：５７１．５７７． Ｇｕｍｈｏｌｄ Ｓ，Ｗａｎｇ Ｘｉｎｌｏｎｇ，ＭａｃＬｅｏｄ Ｒ．Ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ ｆｒｏｍ ｐｏｉｎｔ ｃｌｏｕｄ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ １ ０ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｍｅｓｈｉｎｇ Ｒｏｕｎｄｔａｂｌｅ．Ｂｅｒｌｉｎ，Ｇｅｒｍａｎｙ， ２００１：２９３．３０５． Ｐａｕｌｙ Ｍ，Ｋｅｉｓｅｒ Ｒ Ｇｒｏｓｓ Ｍ．Ｍｕｌｔｉ－ｓｃａｌｅ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ ｏｎ ｐｏｉｎｔ—ｓａｍｐｌｅｄ ｓｕｒｆａｃｅｓ［Ｊ】．Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｆｏｒｕｍ，２００３，２２（３）：２８ １－２８９． Ｐａｒｋ Ｍ Ｉ＜，Ｌｅｅ Ｓ Ｊ，Ｌｅｅ Ｋ Ｈ．Ｍｕｌｔｉ－ｓｃａｌｅ ｔｅｎｓｏｒ ｖｏｔｉｎｇ ｏｆｒ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ ｆｒｏｍ ｕｎｓｔｒｕｃｔｒｕｅｄ ｐｏｉｎｔ ｃｌｏｕｄｓ［Ｊ］Ｉ Ｇｒａｐｈｉｃａｌ Ｍｏｄｅｌｓ，２０ １２，７４（４）：１ ９７—２０８． 【１６］Ｗｅｂｅｒ Ｃ，Ｈａｈｍａｎｎ Ｓ，Ｈａｇｅｎ Ｈ．Ｓｈａｒｐ ｆｅａｔｒｕｅ ｄｅｔｅｃｔｉｏｎ ｉｎ ｐｏｉｎｔ ｃｌｏｕｄｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｓｈａｐｅ Ｍｏｄｅｌｉｎｇ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ．Ｗａｓｈｉｎｇｔｏｎ ＤＣ，ＵＳＡ，２０１０： １７５．１８６． ［１７］Ｋａｌｏｇｅｒａｋｉｓ Ｅ，Ｓｉｍａｒｉ Ｐ，Ｎｏｗｒｏｕｚｅｚａｈｒａｉ Ｄ，ｅｔ ａ１．Ｒｏｂｕｓｔ ｓｔａｔｉｓｔｉｃａｌ ｅｓｔｉｍａｔｉｏｎ ｏｆ ｃｕｒｖａｔｕｒｅ ０１１ ｄｉｓｃｒｅｔｉｚｅｄ ｓｕｒｆａｃｅｓ ｝ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｇｅｏｍｅｔｒｙ．Ｓｗｉｔｚｅｒｌａｎｄ， ２００７：１ ３．２２． ［１８］王小超，刘秀平，李宝军，等．基于局部重建的点云特 征点提取［Ｊ］＿计算机辅助设计与图形学学报，２０１３， ２５（５）：６５９—６６５． ［１９］Ｂｅｌｙａｅｖ Ａ Ｇ Ｐａｓｋｏ Ａ Ｋｎｎｉｉ Ｔ Ｌ．Ｒｉｄｇｅｓ ａｎｄ ｒａｖｉｎｅｓ ｏｎ ｉｍｐｌｉｃｉｔ ｓｕｒｆａｃｅｓ ［Ｃ］／／Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ｎＩｔｅｒｎａｔｉｏｎａ１．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ，ｕｓＡ，１９９８：５３０－５３５． ［２Ｏ】王仁芳，徐慧霞，陈仲委，等．点模型微分属性的估算 及其应用［Ｊ】．自动化学报，２０１１，３７（１２）：１４７４．１４８２． ［２１］张长东，戴宁，廖文和，等．基于启发式搜索策略的 牙齿生物特征线提取技术［Ｊ］．中国机械工程学报， ２０１２，２３（１３）：１５６７－１５８６． ［２２】徐进．带约束的Ｂ样条曲线曲面延伸技术［Ｊ］．图学 学报，２０１３，３４（３）：３６－４２． 【２３］Ｋａｓｓ Ｍ，Ｗｉｔｋｉｎ Ｔｅｒｚｏｐｏｕｌｏｓ Ｄ．Ｓｎａｋｅｓ：ａｃｔｉｖｅ ｃｏｎｔｏｕｒ ｍｏｄｅｌｓ［Ｊ］．Ｉｎｔｅｍａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，１９８７，ｌ（４）：３２１—３３１． ［２４］左军毅，张怡哲，梁 彦．自适应不完全重采样粒子 滤波器［Ｊ］．自动化学报，２０１２，３８（４）：６４７—６５２．
