一种改进的基于特征点求解的骨架提取算法

宫法明，陈依心，李广丽

0 引言

随着计算机图形学的迅速发展，对三维模型的研究日益深入。骨架作为形状表示的一种有效形式，在三维模型的各个研究领域中被广泛采用。Blum 1967年给出了骨架的最初定义[1]：骨架(中轴)是模型内部各个最大内切球中心的集合。它还有一个grassfire的模拟定义[2]，从模型表面开始点火，各个方向上的火的相遇点所构成的集合。因为模型的骨架很好的保留了模型的拓扑连接性及其形态，所以经常被用于碰撞检测、三维动画、模型渲染、模型表面重建、模型检索等应用中，也有研究人员采用骨架为模型的分解做校正[3]。

模型骨架的提取方法很多，有些是源于对二维图像的扩展，有些是针对三维模型提出的，大体上来说，有如下几类：(1)基于拓扑细化技术[4]。该类算法主要应用于采用体表示的模型上，通过不断地进行不改变模型拓扑特性的体元素的削减来实现骨架抽取，因为模型的体表示数据量巨大，所以整个过程比较耗时。Gong等人提出过一种并行细化算法，通过先定义模型的简单顶点、删除谓词和两个细化元操作，在抽取算法中不断迭代两个元操作进行模型细化；(2)基于距离矩阵[5]。它一般的计算对象要求也必须是体表示的模型，通过计算每个体元素的距离来求取模型的脊点。Sundar等人提出过基于该思想的一个算法思路，通过计算每个体元素到边界的最小距离来得到骨架点，Sundar采用该算法创建了一个模型检索系统；(3)亦有学者将二维图像领域中的Voronoi图技术引入到三维骨架抽取中，Dey等人提出过一种利用Voronoi图直接近似中轴的算法[6]。因为对三维模型而言只有部分Voronoi顶点能够汇聚成骨架，所以他通过定义角度和比例这两个与大小、比重都无关的筛选标准来实现它的中轴近似算法，并证明该方法能够保证收敛；(4)基于Reeb图思想[7]。该类算法首先在模型上定义一个连续函数，计算每个模型顶点的函数值，将具有相同函数值的顶点聚合成一个顶点，得到模型的骨架，其中著名的有 Hilaga等人提出的MRG，Hilaga定义的连续函数为顶点到整个模型表面所有顶点的最短距离与面积之积的和。Julien Tierny等人使用了更加合理的标量函数计算方法。(5)基于模型分解[8]。Lien等人观察到对于保存模型连接性的分解过程就是一个骨架抽取的过程，所以提出了基于模型近似凸面体分解的骨架抽取算法，通过计算模型表面的桥识别模型表面的凹地，计算每个顶点的凹陷性，并对模型按照凹陷性进行分解，不断迭代该过程创建骨架。(6)其它类。Ma等人提出过基于可见互斥力的骨架抽取算法[9]，它应用了物理学上的互斥力的概念来计算模型上的平衡点，最终得到模型的骨架。

1 特征点的提取

特征点是指三维模型中显著部分处于极端位置的顶点，它反映了模型的整体空间结构及分支情况，对3D模型的骨架提取有重要作用，每个特征点对应于一个分支，提取特征点即得到模型的分支，将分支的另一端点——骨架点与特征点连接，得到分支部分的骨架，最后，依据骨架点携带的拓扑信息，将具有拓扑相关性的骨架点连接起来，得到3D模型拓扑骨架。

1.1 计算vs1和vs2。

vs1和vs2是三角网格模型中测地线距离最远的两个顶点的索引。首先使用最短距离Floyd算法计算三角网格中所有顶点间的测地线距离，然后找到测地线距离最大的两个顶点索引即为vs1和vs2。

1.2 对每个顶点计算fg1和fg2。

基于测地线距离换算的函数fg1和fg2定义如下：

fg1(v)=δ(v,vs1) ∀v∈T，vs1∈T，fg1(v)表示T上任意一个顶点v到vs1的测地线距离。

fg2(v)=δ(v,vs2) ∀v∈T，vs2∈T，fg2(v)表示T上任意一个顶点v到vs2的测地线距离。

T为模型的三角网格。

1.3 计算fg1和fg2的局部最值集合E1和E1。

局部最值定义如下（图1）：

图1 局部最值

1)局部最大值：v为局部最大值，当且仅当所有与v相邻的结点的f值都小于f(v)。

2)局部最小值：v为局部最小值，当且仅当所有与v相邻的结点的f值都大于f(v)。

3)其它：与v相邻的结点的f值既有大于f(v)的又有小于f(v)的。

根据局部最值的概念，定义E1为fg1局部最值的集合；E2为fg2局部最值的集合。计算fg1(v)局部最值E1步骤如下：

Step1：判断三角网格T所有顶点是否都处理，是则结束，否则取一个没有处理的顶点v，转到Step2。

Step2：找到v的所有邻居点，比较它们对应的fg1值，如果fg1(v)都大于或都小于v的所有邻接点vi的fg1(vi)的值，则将顶点v加入到E1的集合，否则，转到Step1。

两步迭代就可以得到集合E1，E2计算方法相同。

1.4 计算特征点的集合F。

特征点集合即E1与E2的交集F=E1∩E2。由于两个映射函数的特征点对于同一个显著部分并不是准确地定位在同一个点上，应用以下规则进行交集的模糊运算：

2 骨架的提取

骨架提取包括两个步骤，①骨架点的提取；②骨架点和骨架点、骨架点与特征点之间的连接。

在满足拓扑不变和几何约束条件下，通过重复剥离3D模型边界点直至得到一个连通点集，该连通点集中的点即为骨架点。本文采用了一种基于拓扑方法提取骨架点的方法，首先提取模型的分支点，将分支点聚合得到骨架点。算法步骤如下：

Step1：取T的一个顶点v，设置v的堆栈stack，v进栈。如果所有顶点都已处理，则结束，否则转Step2。

Step2：如果stack不为空，转Step3。否则，转Step1。

Step3：把栈最底端的顶点Vsi出栈，同时对顶点Vsi的所有邻接点Vi进行特征点的比较，如果Vsi与所有的邻接点Vi的特征点相同，则Vsi不是分支点，转Step1继续处理，如果不同，转Step4。

Step4：把Vsi添加到v的分支点的数组，然后，对v的所有邻接点进行遍历，查找所有与Vsi的特征点的索引相同的邻接点，加入到stack中，转Step2。

将骨架点和特征点进行连接得到分支的骨架；根据骨架点之间的拓扑关系连接各骨架点得到拓扑骨架。

3 算法分析与改进

特征点提取是整个骨架提取算法的基础。对于一个有n个顶点三角网格T，Floyd算法时间复杂度为O(n3)，成为影响特征点提取算法效率的瓶颈。本文提出了基于距离模型中心最近（远）点提取 VS的策略，得到了时间复杂度为O(n×log(n))改进算法。其基本思想为：计算三角网格的中心点Vo，找到距离该顶点最近（最远）的顶点V′，使用oDijkstra算法计算V′到T上任一点测地线距离，取测地线距o离最大的顶点Vtemp，用相同的方法迭代计算Vtemp，直到两次得到的测地线距离相差不大，即可确定VS。

4 结论

本文基于特征点求解和Reeb图思想实现了一种新的骨架提取算法。首先求取模型特征点集，以特征点为计算依据，根据三角网格中每个顶点与特征点的不同对应关系得到网格分支点，聚合成一系列骨架点，依据骨架点携带的拓扑信息，连接拓扑相邻的骨架点得到模型骨架。采用了改进的特征点提取算法，其时间复杂度由O（n3）提高到了O（n2log（n）），使用Moore-Dijkstra算法计算映射函数fg1和fg2，时间复杂度为O（nlog（n）），采用栈结构实现骨架点的搜索，实验表明算法能够快速提取骨架，针对一般模型的骨架提取效果令人满意。对于极少数特殊模型，提取特征点存在不足或者过多的问题。

图2 实验效果图

[1]Attene M, Biasotti S , and Spagnuolo M . Shape understanding by contour-driven retiling. The Visual Computer,19:127–138, 2003.

[2]Biasotti S, Marini S, Mortara M, and Patan`e G. An overview on properties and efficacy of topological skeletons in shape modelling. In Shape Modeling International, pages 245–254, 2003.

[3]Blum H and Nagel R N. Shape description using weighted symmetric axis features. Pattern Recognition, 10:167–180,1978.

[4]Bremer P T, Edelsbrunner H, Hamann B, and Pascucci V.Topological hierarchy for functions on triangulated surfaces.IEEE Transactions on Visualization and Computer Graphics, 10:385–396, 2004.

[5]Carr H, Snoeyink J, and M V. de Panne. Simplifying flexible isosurfaces using local geometric measures. In IEEE Visualization, pages 497–504, 2004.

[6]Cole K -McLaughlin, Edelsbrunner H, Harer J, Natarajan V,and Pascucci V. Loops in Reeb graphs of 2-manifolds.In Symposium on Computational Geometry,pages 344–350,2003.

[7]Edelsbrunner H and M¨ucke E P.Simulation of simplicity:a technique to cope with degenerate cases in geometric algorithms.ACM Transactions on Graphics, 9:66–104,1990.

[8]H´etroy F. Constriction computation using surface curvature.In Eurographics, pages 1–4, 2005.

[9]H´etroy F and Attali D. From a closed piecewise geodesic to a constriction on a closed triangulated surface.In Pacific Graphics, pages 394–398, 2003.