摘要：研究了一种高效、鲁棒的三维网格模型的线状骨架化算法，包括基于距离变换的网格模型的拓扑结构标记提取、基于路径规划算法的初始骨架线构造、基于Snake模型的骨架中心化算法，以及一种全局噪声消除方法等内容；实验表明该方法对于不规则的复杂线状物体骨架提取，具有较好的效果。
   关键词：线状骨架化算法；距离变换；路径规划算法；Snake模型

 Abstract: This paper presents an efficient and robust method of extracting linear skeletons for 3D mesh models. The proposed method includes three steps. The first step is extracting the topological marks of a mesh model based on distance transform. And then initial skeleton lines are constructed using path planning algorithm. Finally the initial skeleton lines are centralized based on snake model. Experiments show that the proposed method provides good results for irregular elongated objects.
   Keywords: Linear Skeletonization; Distance Transform; Path Planning Algorithm; Snake Model
1  引  言
   基于三维激光扫描建模方法的数字几何处理技术，被称为第四代数字媒体技术 [1]，已成为图形学领域的一个新兴分支和研究热点。
   三维网格模型的骨架在数字几何处理研究的以下方面有着重要作用：①三维网格模型的拓扑结构分析[2,3]；②基于拓扑信息的网格分割[3,4,5]；③三维网格模型检索[5]；④网格模型动画与几何变形[6,7]；⑤网格模型的碰撞检测[8]；⑥网格模型运动合成[9]等。
   三维网格模型的线状骨架定义为位于模型内部的、连通的、且与模型拓扑结构一致的中心线。具有以下特性：拓扑结构同伦性、骨架表示相对简单、易于模式匹配与几何变形等。
   目前三维网格模型通常讨论的骨架是由面和线构成的中轴面[10-12]。尽管中轴面骨架有许多良好的性质如可重建性等，但在上述数字几何处理领域，线状骨架的应用更为明显，尤其对于具有分支拓扑结构的管状三维网格模型，如人体模型、植物模型、医学上的血管模型等。而目前线状骨架的研究较为罕见。
2  网格模型的分支端点提取
   线状骨架主要应用于具有分支拓扑结构的三维网格模型，对于这类网格模型，其分支端点(End Point)是模型拓扑结构的重要标记。因此，要获得拓扑结构同伦的线状骨架，首先要准确提取分支端点。这里借鉴三维图象骨架化中基于某个参考点的距离变换方法[13]，即先计算网格模型上的每个顶点到参考点(Seed Point)的距离，然后选取距离极大值的顶点作为分支端点。与文献[13]不同的是，计算三维图象中体素点之间距离时，通常得到的是近似的欧式距离，在网格模型中可精确计算两点欧式距离，因而，结果更为准确。
具体计算步骤如下：
（1）在网格模型上，选取一个参考点 Ps；
（2）将参考点的距离值定义为零，将其它顶点的距离值初始化预先定义的极大值，即：
                  (1)
（3）从参考点的邻接顶点开始，采取广度优先算法，依次计算网格上每个顶点的距离值，计算方法：
对于顶点Pi，假定Pj是其所有邻接顶点中距离值最小的顶点，则
    (2)
（4）重复步骤（3），直到所有顶点的距离值不再改变或改变量小于给定的阈值为止；
（5）根据上一步得到的网格顶点的距离值，选取所有距离值为局部极大的顶点作为求得分支端点Pe(e=1,2, …, N)。
参考点Ps的选择，对于分支端点提取有重要影响。这里采用人机交互方式选取某一明显分支顶点作为Ps。
3 初始骨架线构造
获取Ps与Pe点后，在模型表面将Ps与Pe连接起来，就可得到初始骨架线。
具体步骤：
（1）将求得的Pe(e=1,2, …, N)按距离值从大到小排序，得到Pe，(e=1,2, …, N)；
（2）令e=1，借鉴路径规划方法，在模型表面将Pe，与Ps连接起来，即：在模型表面寻找一条从Pe，到Ps的最短路径，就可得到一条初始骨架线。具体实现方法是采用基于距离值的最陡下降法；
（3）e=e+1, 重复(2)中操作，直到e>N；
（4）在步骤（2）中，除第一条初始骨架线外，其它骨架线都可能与已求得的初始骨架线相交和重叠。因此，要对相交和重叠部分的初始骨架线进行处理。

4 初始骨架线中心化

将上一步得到的每条初始骨架线作为初始Snake： ，在内力（包括拉伸力和弯曲力）和特征力的作用下，使其逐步收敛于网格模型的中心位置。
算法暂不考虑内力的作用，因此，特征力的计算是问题的关键，特征力通常由模型内部能量决定。
网格模型内部能量的计算无法直接采用图像处理中方法，为此这里采用一种弹簧模型。对于Snake上的点 ，假定与一定邻域内网格顶点 之间均用同样弹性系数的弹簧连接，则 的特征力表示为：
(3)  

5  抗噪声处理
在上述三个步骤中均要考虑噪声消除：
a. 拓扑结构标记提取过程中，为防止错误地将噪声作为分支端点提取，除考虑顶点的距离值外，还可增加的曲率、顶点附近距离值变化等参数。
b. 初始骨架线构造方面，在从EP点向RP点回缩过程中，可根据给定阈值参数，删除短的噪声分支。
c. 中心化过程中，如果只考虑较少网格顶点对骨架点的外力作用，则可能由于模型局部畸变导致局部某个方向外力较大，从而使骨架也发生畸变。为此，通过增加每个骨架点受到外力作用的网格顶点数量，可平滑局部畸变导致的某个方向外力过大现象，从而减少噪声带来的骨架畸变。

6   实验结果及结论
   采用文中提出的方法对人工合成和实际三维扫描重建的网格模型骨架提取结果如图1-3所示。图中分别给出了原始网格模型、距离变换结果及所求的骨架。其中，距离变换图示中顔色越深表示距离值越小。由图示可以看出，文中提出的骨架化方法得到了较好的实验结果。
   进一步的工作有以下几个方面：（1）分支结构中的分叉点在算法中没有考虑，因此，在分叉点处骨架有一定的变形。因此，算法改进过程中除提取分支端点外，还要将分叉点提取出来。（2）寻求一种自动确定参考点的方法。

致  谢  本文实验所采用的三维扫描重建的植物根系网格模型由北京朝日三维科技有限公司制作，在此表示感谢！
参 考 文 献
[1] Schroder P, Sweldens W. Digital geometry processing[A]. In: Computer Graphics Processings, Annual, Conference Series, ACM SIGGRAPH[C], Los Angeles, California, 2001. Couse Notes #50
[2] Li X, Woon T W, Tan T S, et al. Decomposing polygon meshes for interactive application[A]. In: Proceedings of the ACM Symposium on Interacive 3D Graphics[C], Research Triangle Park, North Carolina, 2001. 35~42
[3] Leymarie F, Kimia B. The shock scaffold for representing 3D shape[A]. In: Proceedings of the 4th International Workshop on Visual Form[C], Capri, 2001. 216~228
[4] Rossl C, Koobbelt L, Seidel H P. Extraction of feature lines on triangulated surface using morphological operators[A]. In: Proceedings of the AAAI Symposium on Smart Graphics[C], Stanford, California, 2000. 71~75
[5] Page D L, Koschan A F, Abidi M A. Perception-based 3D trangle mesh segmentation using fast marching Watersheds[A]. In: Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition[C], Madison, 2003.27~32
[6] Chaudhuri P, Kalra P, Banerjee S. A system for view-dependent animation[J]. Eurographics, 2004,23(3):411~420
[7] Blanding R L, Tuikiyyah G M, Storti D W, et al. Skeleton-based three-dimentional geometric morphing[J]. Computational Geometry, 2000, 15:129~148

[8] Kavan L, Zara J. Fast collision detection for skeletally deformable models[J]. Eurographics, 2005,24(3):364~372
[9] Urtasun R, Glardon P, Roulic R, et al. Style-based motion synthesis[J]. Computer Graphics Forum, 2004, 23(4):799~812
[10]Etzion M, Rappoport A. Computing Voronoi skeletons of a 3d-polyhedron by space subdivision[J]. Computational Geometry, 2002, 21:87~120
[11]Ramanathan M, Gurumoorthy B. Constructing medial axis transform of extruded and resolved 3D objects with free form boundaries[J]. Computer-Aided Design, 2005, 37:1370~1387
[12]Attali A, Lachand H O. Delaunay conforming iso-surface, skeleton extraction amd noise removal[J]. Computational Geometry, 2001, 19 175~189
[13]Maddah M. Soltanian-Zadeh H. and Afzali-Kusha A. Snake modeling and distance transform approach to vascular centerline extraction and quantification[J]. Computerized Medical Imaging and Graphics, 2003, 27:503~512.