（计算机软件与理论专业论文）三维网格模型的骨架提取.pdf

辽宁师范大学硕士学位论文 摘要 三维网格模型在计算机图形学、可视化等领域的广泛应用，使得人们开始关注三维 网格模型的骨架提取和细分的研究。骨架提取和网格细分是三维网格模型的基本问题。 骨架提取主要包括三类方法：距离变换、细化、分解。在基于细化的骨架提取方法 中，目前仍然有很多问题没有很好地解决，例如：当骨架受噪声影响时，它很容易包含 一些无效的分支或者发生骨架不连续的情况。基于距离变换的骨架提取方法能够较好地 保证骨架点的中心性，不过在保持原有拓扑信息的连通性方面则存在不足。为了解决上 述两个问题，本文提出了一种基于显著性分支分割及其测地路径的骨架提取方法，主要 方法描述如下：首先进行m d s 变换，将三维网格模型弯曲的局部分支向各个方向的显著 性伸展开，提取显著性特征点，进而对三维网格模型进行分割；然后根据网格表面离散 测地路径的计算定义各分割块的结点环，并提取各显著性分割块的骨架；最后利用k s 主曲线方法对非显著的核心分割块部分骨架进行拟合。由于对三维网格模型进行了与姿 态无关的m d s 变换，所以该算法对骨架的计算同样与模型姿态无关。 关键字：m d s 变换；三维骨架；三维分割；三角网格； 三维网格模型的骨架提取及细分 s k e l e t o ne x t r a c t i o nf o r3 dm e s h a b s t r a c t w i t ht h e3 dm e s hb e i n ge x t e n s i v e l ya p p l i e dt om a n yf i e l d ss u c ha sc o m p u t e rg r a p h i c s a n dv i s u a l i z a t i o n ，p e o p l ea r eb e g i n n i n gt op a ya t t e n t i o nt os k e l e t o ne x t r a c t i o na n ds u b d i v i s i o n s k e l e t o ne x t r a c t i o na n dm e s hs u b d i v i s i o na r et w of u n d a m e n t a lp r o b l e m si n3 dm e s h s k e l e t o ne x t r a c t i o nc o n t a i n st h r e ek i n d so fm e t h o d s ，s u c ha sd i s t a n c ec o n v e r s i o n ，t h i n m e l ta n dd e c o m p o s e s n o w , t h e r ea r em a n yp r o b l e m sw h i c hp e o p l ew a n tt os o l v ei ns k e l e t o n e x t r a c t i o nm e t h o db a s e do nt h i n n i n g f o re x a m p l e ，w h e nt h e r ei sn o i s e t h es k e l e t o ni se a s yt o i n c l u d es o m ei n v a l i db r a n c h e se v e ne m e r g ed i s c o n t i n u o u s t h es k e l e t o ne x t r a c t i o nm e t h o d b a s e do nd i s t a n c et r a n s f o r mc a ne n s u r et h ec e n t r a l i t yo fs k e l e t o np o i n t s ，b u tc a nn o tm a i n t a i n t h ec o n n e c t i v i t yo ft h eo r i g i n a lt o p o l o g yi n f o r m a t i o nw e l l t os o l v et h e s et w op r o b l e m s ，t h i s p a p e rp r e s e n t sam e t h o db a s e do nt h es i g n i f i c a n tb r a n c hs e g m e n t a t i o na n dg e o d e s i cp a t h t h e m a i ni d e ai sd e s c r i b e da sf o l l o w s ：f i r s t l y , a l lc u r v e d1 0 c a lb r a n c h e so fa3 dm e s hm o d e la r e e x t e n d e di na l ld i r e c t i o n sa n da l ls i g n i f i c a n tf e a t u r ep o i n t sa r ee x t r a c t e d a n dt h e nt h e3 d m e s hm o d e i i ss e g m e n t e d s e c o n d l y , t h i sm e t h o dd e f i n e sn o d er i n g so fe a c hb l o c ka c c o r d i n g t oc o m p u t i n gd i s c r e t eg e o d e s i cp a t ho nt h es u r f a c eo ft h i sm e s ha n de x t r a c t st h es k e l e t o no f e a c hs i g n i f i c a n tb l o c k f i n a l l y , t h es k e l e t o n so fa l ln o n - s i g n i f i c a n tp a r t sa r ef i t t e db yu s i n g k sm a s t e rc u r v em e t h o d b e c a u s et h em d sh a sn o t h i n gt od ow i t ht h ep o s t u r eo fm o d e l s e l e c t e d ，c o m p u t i n go ft h i sm e t h o da l s oh a sn o t h i n gt od ow i t ht h ep o s t u r eo fm o d e ls e l e c t e d k e y w o r d s ：m d st r a n s f o r m a t i o n ；3 ds k e l e t o n ；3 ds e g m e n t a t i o n ；t r i a n g u l a rm e s h ； i i 辽j2 师范大学硕七学位论文 目录 摘要i a b s t r a c t i i 引言1 1 1 研究背景和意义1 1 2 本文的研究工作l 1 3 本文的结构安排2 2 三维网格骨架提取算法3 2 1 三维网格骨架提取概述3 2 2 典型的网格模型骨架提取算法。3 2 2 1 体积法3 2 2 2 几何法4 2 2 3 拉酱拉斯编辑和平滑法4 2 3 三维网格模型的数据结构5 2 3 1 三角网格模型5 2 3 2 三角网格数据结构5 3 显著性分割的三维网格模型骨架抽取8 3 1 显著分支的分割8 3 1 1 模型的归一化8 3 1 2 网格模型上的离散测地距离8 3 1 3 多维标度法m d $ 9 3 1 4 显著性特征点的提取1 0 3 1 5 模型s 的k + 1 分割1 2 3 2 计算最短路径提取骨架线1 3 3 2 1 分割块之间的连接环13 3 2 2 分割块s 上的结点环定义和骨架计算1 3 3 2 3 核心分割块瓯的骨架计算1 4 3 3 实验结果分析1 6 4 工作总结与展望1 9 4 1 本文的上作总结1 9 4 2 进一步的研究与展望1 9 参考文献2 0 致 谢2 1 攻读硕士学位期间所发表的学术论文2 2 i l l 辽j 。师范人学硕十学位论文 引言 1 1 研究背景和意义 三维模型的骨架能够很好地描述其拓扑连接信息和几何形状信息，因此近年来被广 泛地应用于三维变形【1 捌、三维形状识别和检索3 圳、模型编辑【5 1 、简化6 1 、以及运动控制 和碰撞检测【7 】、三维分割【8 】等问题的研究。骨架的最初定义是模型内部各个最大内切球 中心的集合【9 j ，面向三维的网格模型或者三维的体素模型的骨架提取方法主要包括：距 离变换、细化、分解等三类。 提取三维体素模型骨架的细化方法的基本思想是：由外向内，层层剥离，其中判断 一个体素是否需要剥离的检测工作较为耗时，目前仍然有很多问题没有很好地解决，比 如骨架受噪声影响较大，往往包含一些无效的分支；骨架不连续；提取的骨架虽然具有 较高的拓扑性，但是中心性难以保证等。 基于距离变换的骨架提取方法能较好地保证骨架点的中心性，不过在维护原有拓扑 信息的连通性方面较弱。基于l e v e ls e t 的骨架提取方法i lo 】稳定性较好，也具有较高的 拓扑无关性【l ，能够有效地消除尖点、骨架断裂等问题，但是即便采用了f a s tm a r c h i n g m e t h o d 策略，其计算复杂度依然很高。文献1 1 2 】引入s n a k e 模型调整骨架点的位置，改 善了骨架点的中心性，但复杂度也同时增大。 相对于基于距离变换和细化两种方法而言，基于形状分类或者分割的三维骨架提取 方法【1 3 4 】将骨架提取和形状分割结合起来，优势较为显著。基于拓扑连接信息，先行 对三维模型进行分割：基于分割结果可以降低骨架提取的复杂度、提高骨架的精确度。 同样，已有三维的骨架可以用来指导三维模型分割，使分割结果更加有意义、更加遵循 m i n i m a lr u l el i e n 等人基于模型的近似凸面体分解，通过计算三维模型顶点的凹凸性展 开分割，并通过迭代生成骨架，不过所得到的骨架中心性较差，也难以建立层次关系i l 引。 面向分割的骨架提取工作中，多数分割算法对模型的姿势比较敏感，例如，双手合拢的 人体模型和双手伸展开来的人体模型，其分割结果会有较大的差异，其主要原因是曲率 的作用。 1 2 本文的研究工作 本文受文献1 1 6 】的启发，提出了一种基于显著性分支分割及其测地路径的骨架提取方 法。首先基于m d s 变换，将三维网格模型弯曲的局部分支向各个方向的显著性伸展开， 进而提取显著性特征点，对三维网格模型进行了分割：基于网格表面离散测地路径的计 算定义了各分割块的结点环，提取了各显著性分割块的骨架，较好地解决了噪声和弯曲 姿态等问题对骨架计算的影响；最后以k s 主曲线拟合和中心环方法，较好地逼近了非 显著的核心分割块部分骨架。因为我们对三维网格模型进行了与姿态无关的m d s 变换， 三维网格模型的骨架提取及细分 所以本文算法求其的骨架与模型姿态无关。 1 3 本文的结构安排 第一章序言。介绍了本文的研究背景，意义，工作内容，文章的结构安排。 第二章三维网格骨架提取算法。首先，论述了三维模型骨架提取和的相关概念。 然后，介绍了典型的三维模型骨架提取算法，并对这些算法所采用的标准和优缺点等进 行了总结。 第三章显著性分割的三维网格模型骨架抽取。首先介绍了显著分支的分割，这部 分主要是进行模型的预处理，角距离和测地距离的计算，m d s 处理，显著性特征点的提 取和最后的k + 1 分割，也是本文骨架提取算法中比较关键的步骤，为后续的骨架线提取 奠定了基础。其次，通过计算最短路径提取骨架线，最短路径的计算是在分割后的模型 上进行的，通过计算路径上的结点环中心，来得到骨架线上的点，模型的核心部分的骨 架是通过各个分支到模型中心环的骨架线通过k 均值聚类拟合而成。然后，把各个分支 的骨架线连接到核心骨架线的相对最近点，整个模型的骨架线就形成了。最后，对多个 模型的实验结果进行了分析研究，并统计了各个模型所需要的计算时间。 第四章工作总结与展望。总结了本文算法的优缺点，并展望了以后的科研工作。 辽宁师范大学硕士学位论文 2 三维网格骨架提取算法 2 1 三维网格骨架提取概述 骨架线是简化三维物体的几何和拓扑的一维结构。在动画，分析，变形，形状检索 等方面被广泛的应用。骨架线并没有严格的定义，各种应用可能对某些性质有不同的要 求，例如，医学上的虚拟现实情况比动画中的中心要求要严格。骨架线与中轴紧密相关， 一个三维物体的中轴的定义为所有半径最大的内切球中心的轨迹，而且通常包含一些表 面因素。这个定义意味着中轴本质上是对物体的边界很敏感，因此需要一个处理边界噪 音的过程。 图2 1 骨架提取 f i g 2 1s k e l e t o ne x t r a c t i o n 2 2 典型的网格模型骨架提取算法 2 2 1 体积法 大部分现有的骨架提取方法是利用体积离散描绘，无论是用均匀分区的三维体素化 描绘还是用离散域函数在三维空间中定义。这些方法都存在着细节的隐性丢失和不合适 离散化方法导致的数值不稳定这些缺点。 从三维体素化描绘法，体素稀释方法都是通过在保持拓扑结构的同时迭代消除边界 体素来提取骨架线n 引。这些方法的主要区别是边界体素和移除的优先性的选择方式不 同。最近，w a n g 等人提出了一种在实施细化算法之前先缩小模型体积，生产更光滑的骨 架，但是仍需要改进。一般来说，细化方法并不健壮，而且需要额外考虑，防止表面或 三维网格模型的骨架提取及细分 曲线的端点过渡移除。 距离场方法为3 d 模型上的每个内在点确定一个距离变换并检测场的边界来获得一 个候选体素集。连接这些候选体素给出了近似内侧表面，因此，基于内侧轴的方法并不 健壮。其他领域方法是选择排斥力和径向基函数的距离转换。一般场方法确定内在点的 潜在价值对噪音不太敏感，因为边界样本的数目很多。然后，用跟踪算法来连接本地的 端点从而形成骨架线。这些方法属于计算密集型的，由于较大边界区域的使用，一阶和 二阶导数的计算造成了数值的不稳定。 2 2 2 几何法 几何法是直接在多边形网格和点集上进行。佛罗诺依图是比较常用的几何方法，此 方法通过提取佛罗诺依图的内侧边和面来获得近似的近中面，并通过修剪内侧面来获得 骨架线。 基于r e e b 图的方法近年来备受关注，r e e b 图是一维结构，其节点是定义在模型表 面上实值函数的临界点，对模型的拓扑进行编码。对于不同的应用采用不同的实值函数， 例如地线函数或调和函数，用来表示骨架线，r e e b 图需要进行模型表面重建来获得更多 的骨架点，然后嵌入到几何。a u j a y 等人提出了一种谐波r e e b 图，通过拉普拉斯方程 式得到调和函数。此类方法要求用户指定明确的边界条件。o s c a r 等人提出了一种几何 收缩方法，用拉普拉斯方法像压缩边界点一样来压缩模型上所有的点，每个点的权重都 是自动定义的。 还有一些方法不属于上述一般类，s h a r f 等人提取骨架是在模型变形演变到点云和 多边形网格。最初的提取图有噪音，需要进行过滤和合并。c h u a n g 等人提取骨架线的 方法是在面片的凸角上使用f o r c e f o l l o w i n g 算法，这是基于广义势场，计算量很大。 k a t za n dt a l 提取骨架是先分割再连接各个组成部分。李等人提出了通过消除较短边而 把面片简化成线并连接这些线段。后面的两种方法生成比较粗糙的骨架线，而且并不能 很好维持拓扑性。 2 2 3 拉普拉斯编辑和平滑法 我们每一步的迭代收缩过程是一次对所有顶点以不同的权值做的拉普拉斯光顺。以 前的方法是利用拉普拉斯系统来改变或近似面片几何，对所有或部分边界进行压缩。他 原始输入的是最d 、- - - 乘网，这是与使用了统一的边界约束的顶点精心挑选的一个子集加 权离散拉普拉斯方程的解( 称为锚) 。 最近，n e a l e n 等人提出了网格优化技术，推广了几何光顺和参数光顺的压缩拉普拉 斯系统的概念。他们的方法解决了拉普拉斯系统很难用不同权重的控制参数光顺和不同 右手边线性系统控制几何光顺的问题。一般的系统，所有点被压缩到全局光渭并且容量 不变。o s c a r 等人几何收缩法解决了拉普拉斯方程约束，位置限制相对较弱，允许几何 4 辽宁师范大学硕士学位论文 被压缩成接近零体积的网格。 2 3 三维网格模型的数据结构 由于一个三维网格模型是由顶点( v e r t e x ) 、边( e d g e ) 和面( f a c e ) 组成，每个面由三个 顶点组成，每条边由两个顶点组成，因此用来存储三维网格模型的数据结构要存储这些 几何以及拓扑信息。可以通过数据结构获取几何基元之间的索引信息和邻域信息。在三 角网格数据结构中，通常有两大类：一类是基于边的( e d g e b a s e d ) 数据结构，一类是基 于面的( f a c e b a s e d ) 数据结构。基于边的数据结构存储了构成边的顶点和相邻边的信息。 基于面的数据结构存储每一个面的信息，包括构成该面的顶点信息、边信息以及相邻面 的信息。这种数据结构可以通过访问相邻面的信息来遍历一个顶点的邻域信息。 2 3 1 三角网格模型 三角形网格的表示方式有以下两种：一种是点( v e r t e x ) 和边( e d g e ) 的方式来描述三角 形网格，一种是点( v e r t e x ) 和三角形( t r i a n g l e ) 的方式来描述三角形网格。本文所介绍的 o b j 、o f f 格式的文件采用的是后一种表示方式。 蝴。峨_ 给定一个三角形网格m ( v ，r ) ，其中： v = v 小= o ，1 ，n - 1 ) ，t = tlf - 0 ，1 ，n - 1 ) ( 2 1 ) y 是三角形网格m 的顶点集合，r 是三角形网格m 的三角形集合。其中三角形集 合r 中的每个元素t 又可表示为一个由顶点集合y 中的元素组成的三元组： t = ( v f ，v ，) 一2 2 ) ( v ，v ，v 。) 称为相应三角形的顶点集，此三角形的边由顶点集中任意两个顶点组成i 设v 、e 和f 分别为三角形网格m 上的单个顶点、边和三角形，我们可以得到如下 关系： ( 1 )如果1 ，是f 的一个顶点，那么称v 和r 是相邻的，f 为顶点，一环上的面片。建 立顶点v 的一环内的三角形的集合。 ( 2 )如果1 ，是e 的一个顶点，那么称e 是v 共用边。建立顶点v 所有共用边的集合。 ( 3 )e 的两个顶点全部都在，的上，那么称，和e 是包含的。建立边e 的被包含的三 角形的集合。 ( 4 )设v 是三角形网格m 上的另外一个顶点。如果v 和1 ，为同一条边所共用，那么 称，顶点是v 的相邻点。建立项点v 的相邻顶点的集合。 ( 5 )设t 是三角形网格m 上的另外一个三角形。如果f 和f 有一条公共边，那么称这 两个三角形是边相邻的。建立三角形，的边相邻三角形的集合。 2 3 2 三角网格数据结构 定义顶点、边、三角形和网格模型的结构，建立三角网格模型的数据结构，存储模 5 三维网格模型的骨架提取及细分 型的几何和拓扑信息。具体结构的定义与说明如下： 模型的三角形列表： t y p e d e fs t r u c t _ g l m t r i a n g l e g l u i n tv i n d i c e s 3 ；三个顶点在顶点数组中的下标 g l u i n tn i n d i c e s 3 ；顶点法向量在法向量数组中的下标 g l u i mt i n d i c e s 3 ；顶点纹理坐标在纹理坐标数组中的下标 g l u i n tf i n d e x ；三角形小面片的法向量数据 g l u i n tf l a g ； ) g l m t r i a n g l e ； 模型的组结构： t y p e d e fs t r u c t _ g l m g r o u p c h a r +n a m e ； g l u i n t n u m t r i a n g l e s ； g l u i n t 奉t r i a n g l e s ； g l u i n t m a t e r i a l ； s t r e e t _ g l m g r o u p 牛n e x t ； ) g l m g r o u p ； 模型本身的数据结构： t y p e d e fs t r u c t g l m m o d e l c h a r p a t h n a m e ； c h a r *m t l l i b n a m e ； g l u i n t n u m v e r t i c e s ； g l f l o a t 木v e r t i c e s ； g l u i n tn u m n o r m a l s ： g l f l o a t * n o r m a l s ； g l u i n t n u m t e x c o o r d s ； g l f l o a t * t e x c o o r d s ； g l u i n t n u m f a c e t n o r m s ； g l f l o a t f a c e t n o r m s ； g l m i n t n u m t r i a n g l e s ； g l m t r i a n g l e + t r i a n g l e s ； g - l u i n tn u m m a t e r i a l s ； g l m m a t e r i a l * m a t e r i a l s ； g l f l o a t p o s i t i o n 3 ； g l u i n t n u m g r o u p s ； 组的名称 组中包含三角形的数目 三角形列表( 下标) 组的材质下标 指向下一个组的指针 模型所在的路径和文件名 材质库的文件名 模型中的顶点数 顶点数组 模型中法向量的数目 法向量数组 模型中纹理坐标的数目 纹理坐标数组 模型中面片法向量的数目 面片法向量数组 模型中三角形的数目 三角形数组 模型中材质的数目 材质数组 6 模型中组的数目 望! 堕蔓查堂堡主堂垡堡銮 一一一 g l m g r o u p g r o u p s ； c h a r m _ f i l e t i t l e n a m e 2 5 6 ； g l f l o a tm 【3 】【3 】； g l m m o d e l ； 所有组构成的链表 设二维数组m 【3 】【3 】来表示三维模型变换的合成 在网格模型结构中，将顶点、边、三角形结构实例化，每一个实例对象都可以访问 相应类中的每个数据成员，从而得到模型的几何和拓扑信息。 三维网格模型的骨架提取及细分 3 显著性分割的三维网格模型骨架抽取 3 1 显著分支的分割 3 1 1 模型的归一化 我们希望对同一物体处于不同的空间位置，大小，旋转角度时的测试结果是不变的， 所以需要对所有物体的特征向量做一下归一化处型17 1 。 用m ，。，m 。l 。和m 删来表示模型的重心，模型上所有点的坐标减去重心的坐标，使整 个模型移动到了以原点( 0 ，0 ，0 ) 为重心的位置。 v ，= l ，2 ，k ，y ，z ，】7 卜b 。一疡。o o ，y ，一疡，z ，- t h 0 0 i 】7 1 ( 3 1 ) 用m 2 0 0 ，m 0 2 0 ，m 0 0 2 ，m l l o ，聊l o l 和m o o l 来标示模型的旋转和缩放。这一步是在第 一步的基础上完成的。 _ m 2 0 0 m li o m l o i m = im l i o m 0 2 0 m 0 1 1 ( 3 2 ) l m l o l m o ii m 0 0 2j 我们采用奇异值分解的方法，公式如下： u a u7 = s v d ( m ) ( 3 3 ) 酉( 矩) 阵u 表示旋转，对角矩阵表示在每个轴上的大小，并按降序排列。 通过s v d 分解后，我们通过u 把模型旋转到规则位置，我们同样通过( 1 ，1 ) 把模型 的最大长度缩放到1 h j z j 卜志肌一r ( 3 4 ) 最后我们的算法应该决定每个模型的朝向问题，相对于每个轴。计算出相对于中心 任何一方向的顶点数目。把顶点数目最多的方向放在x 轴的正方向。 3 1 2 网格模型上的离散测地距离 设任意三维网格模型s 的对偶模型为s 删，在s 删定义a n g d i s t ( a 。) 为任意两个 边棚邻三角面片z ，六之间的两面角距离；对应的测地距离g e o d ( f , ，厂，) 定义为它们的公 共边够n 可，的中点到两个三角面片重心的距离之和；由此得到在三维网格模型s 上， 与三角面片，对应的两个相邻顶点v ，v ，之间的加权测地距离g e o d d i s t ( v ，v ，) 为： g p d 扣括f ( v ，_ ) = 耽动f ( 幽甜( m 幽口，( z ) ) = 黜+ ( 1 一脚 a n g o i s t ( c t ) a v g c a n g d i s t ) ( 3 5 ) 其中d v g ( g e o d ) s p i a v g ( a n g d 研) 分别为 g e o d f ，乃) 和臼馏一d i s t ( a 驴) 的均值， 8 辽宁师范人学硕十学位论文 为加权系数，基于f a s tm a r c h i n g 方法，可以得到三维网格模型s 上任意顶点对 ， ，j 间的离散测地距离瓯= g e o d d i s t ( v f ， ，j ) 和最短路径砌d ，几历( v ，y j ) 。 3 1 3 多维标度法m d s 本节使用多维标度法( m u l t i - d i m e n s i o n a ls c a l i n g ，m d s ) ，将欧式空间的任意三 维网格模型s 转换为m d s 空间的模型s 脚。 图3 1 测地距离和欧氏距离 f i g 3 1g e o d e s i cd i s t a n c ea n de u c l i d e a nd i s t a n c e 设欧式空间的任意三维网格模型s ，其顶点集合为 ，j1 f ，z ，定义 万，= g e o d d i s t ( v 。，v ，) 为s 上任意两点v ，之间的离散测地距离，定义吒为s 脚上相应 两点之间的欧几里德距离；由此可以计算其距离矩阵。定义压力公式【1 7 1 为： r ：奎罂娑垡 ( 3 6 ) 。 乞t g e o d d i s t ( v ，v ，) 就可以顺利进行了。 3 1 5 模型s 的k + 1 分割 在s 脚上定义包围球( 图3 62 c 红色球) ，球心为s 删的重心c s 脚，半径为 r = m a x ，l l v c 9 。以该包围球为对称轴面，对乳删上每个顶点v 按如下公式做镜像 2 3 1 ： ，m - , - o , = v + 2 ( r - 忡鼢舾f v - - c 习s m d s ( 3 7 ) 将镜像后位于凸包上的所有点的集合，定义为模型s 脚的核，记为。显然模 型s 删的显著性分支以及特征点均位于该凸包的内部。 假设模型s 删的特征点魍数目为k ，其相应的显著性特征分支数目也七，在镜像 变换之后，以凸包上的点为分割边界点，即可以将位于凸包内的其他显著性分支切割开， 从而得到了模型s 的一个k + 1 分割& ，s 。，s ：，瓯，其中& 表示核妃脚所对应的核心分 割块( 如图3 61 e 中绿色部分) ，s ，f _ 1 ，2 ，k 则表示k 个显著性特征分支构成的分割 块( 如图3 61 e 中白色粉色、红色和黄色部分) 。 ( 1 b ) s m 弧模型 ( 1 c ) 镜像球面( 1 d ) 核心提取 图3 6 镜像球分割 f i g 3 6s e g m e n to fm i r r o rb a l l 辽宁师范大学硕士学位论文 3 2 计算最短路径提取骨架线 3 2 1 分割块之间的连接环 图3 7 迕接环 f i g 3 7c o n n e c t i n gr i n g 设模型s 的一个k + 1 分割为瓯，s 。，s ：，s k ，则，记分割块s ，b1 , 2 ，k 与氐的公 共边界上的顶点集合为l o o p , = o s 。n o s ，( 如图3 7 红色点列所示) ，称该顶点集合为 各分割块墨与核心分割快& 的连接环。 考查每个显著性特征点即到对应连接环l o o p , 上各个点的最短路径，显然这样的 最短路径不只一条，其数量为l ，= l i l o o e , i ，这些最短路径的空间结构可以用以特征点 胆为根的树表示。 图3 8 计算最短路径 f i g 3 8c o m p u t es h o r t e s tp a t h 3 2 2 分割块s 。上的结点环定义和骨架计算 考查分割块s ，上以特征点魍为根的最短路径树，显然从根节点尸f 到对应连接环 l o o p , 上的各叶子结点的深度不同，对应的测地距离长度也有所差异。 记s h o r t e a t h ( p f ，v ) 为分割块墨上的特征点p f , 到达其连接环l o o p , 上任意顶点 三维网格模型的骨架提取及细分 v ，的最短路径的集合，对应的最短路径的测地长度为印( v ，) = i i s h d ，炉口砌( 魍，v ，) l l ，则， 记在该最短路径集合上，所有路径测地长度的最大和最小值分别为 印麟= m a x 钏舶d 胁砌( 印，v ) 恰 ( 3 8 ) s p t | i i 。= m i n s h o ，砌砌( p 只，v ) 盼 ( 3 9 ) 令卸：堕，却：s p r a i n ，于是定义分割块s ，的m 个结点环为其顶点集合的肌个 子集： h ，( ，) = u v s ji 卤咿t s p ( v ) a s p ，) ( 3 1 0 ) 其中m 为非负的常整数，t = 1 , 2 ，朋，记c = 0 日，( v ) 0 ，于是结点环日，( v ) 的中心坐 标可以定义为： c e n t e r ( h ，( 1 ，) ) ：c c o o r d _ i n a t - e ( h 一, ( v ) ) ( 3 1 1 ) f 2 l 。 顺次连接某分割块s ，上结点环的中心c e n t e r ( h ，( v ) ) ，直到t o o e , 的中心，即可得到 由聊+ 1 个点连接而成的一条骨架折线，即为分割块s ，的骨架线。、 对于模型s 的一个k + 1 分割s os l ，s 2 ，s 女，除了与核心分割块对应的瓯外，分别 对其他分割块s 。，s ：，s 。做同样的处理，即可得到与各显著分支的骨架线。 lr t 竹仙7 一工u n 故卅盯j ；，i 外、i ，竹仙，j 3 - u r j o 卅“j 轧，i 卅、 图3 9 结点环和中心环 f i g 3 9n o d er i n ga n dc e n t e rr i n g ， 3 2 3 核心分割块鼠的骨架计算 由于模型p 的核心分割块& 上没有特征点，故其骨架提取问题需要特别的考虑。 对于重心位于核心分割块s o 内部的模型，可以使用k s 主曲线算法，对连接t o o e 的 中心点与& 的中心的k 条直线段进行拟合，从而得到以主曲线表示的核心分割块& 新的 骨架s ，依次连接l o o p , 的中心点与s o 两个端点中的较近端，可以得到模型s 的完整 1 4 辽宁师范人学硕士学位论文 骨架。 l 钳址，_ l _ il 叫、i f j 臼粜l ，竹【i j 血j u 垃缢；1 【r j 打泉 图3 1 0 骨架 f i g 3 1 0s k e l e t o n 对于重心位于核心分割块瓯外部的模型，则按照下述方法进行处理。 设任意三维网格模型s ，其顶点和，l1 f 刀) 的坐标集合为扛，y ，z ，匕，则其 ( p ，q ，) 一砌矩的离散定义可以表示为： 朋阿= 圭x ，y ? z j ( 3 1 2 ) i z m 阿r2 = z x ；y ：z i o 根据矩的定义，所得各阶矩的集合切用，j 具有唯一性和确定性，且s 的一阶矩和二 阶矩分别表示其重心和三个p c a 主轴u 7 】。 据此，首先基于核心分割块& 一阶矩和二阶矩，计算核心分割块瓯的重心、p c a 主 轴和三个轴平面。设瓯的重心为d ，三个主轴按轴长降序排列为a ，b ，c ，则令基面为两 个短轴所在的平面o b c ，沿最长轴伽方向适当地选择常数，可将氐的顶点集合水平 地切割为m 个厚度为h 。的子集合日? ( v ) ，t = 1 , 2 ，m ，称顶点子集合1 4 0 ( v ) 为核心分割块 s 。的中心环，其中心坐标为： c e n t e r ( 日? ( 1 ，) ) ：c c o o r d i 7 n a t 广e ( h o ( v ) ) ( 3 13 ) 其中c o = 8 日? ( v ) l l 。顺次连接c e n t e r ( h o , ( v ) ) ，即可得到由m 个中心点连接而成的一 条骨架折线，即为核心分割块& 的骨架线。 本节要求核心分割块s 。具有较好的凸性，此时c e n t e r ( h o ( v ) ) 应该位于顶点子集合 n o c v ) 在基平面o b c 上投影多边形的内部；否则c e n t e r ( h o , ( v ) ) n - i 能将位于日? ( v ) 在基平 面o b c 上投影多边形的外部，此时骨架将穿出核心分割块瓯，而不是完全位于模型s 的 内部，本节算法失效。 三维网格模型的骨架提取及细分 3 3 实验结果分析 本骨架提取实验环境为个人计算机，基本硬件环境为i n t e lc o r e ( t m ) 2d u oc p u e 4 5 0 0 ，主频2 2 0 g h z ，内存2 g ，显存1 2 8 m 。在w i n d o wx p 操作系统下，用m i c r o s o f tv i s u a l s t u d i oc + + 和m a t l a b 编程，在普林斯顿大学的s h a p eb e n c h m a r k 数据库上完成实验( 图 3 11g 例外) 。 ( d ) m 0 0 7 1 ( b ) m 0 3 3 6( c ) m 0 3 2 4 ( e ) m 0 0 9 5 ( g ) m 0 0 5 0 0 ( i ) m 0 1 0 4 图3 1 1 部分实验结果 f i g 3 11r e s u l t s 1 6 淑 一 、l - _f1j 一 厂 一 避7 一。箧 陵飞w臻蓄。 心q绷。一 (= | ) ll l 、j ，r ，l 辽宁师范人学硕+ 学位论文 图3 1 l 中模型上绿色圆点为显著性特征点，黄色点核心分割块瓯骨架的两个端点， 红色为所求的骨架及其分支。在3 2 节中，显著性分支的骨架不是从特征点艘出发， 而是顺次连接分割块墨上结点环的中心c e n t e r ( h ，( v ) ) 、直到l o o p , 的中心而得到，所以 在图3 1 1 b 和图3 1 1 c 中，腕部的骨架远离了手腕底部的绿色特征点；图3 1 1 的其他 实验结果中，绿色特征点与显著性分支骨架的红色端点也是分离的。 需要说明的是，依据尽s 。优化过程，在各向伸展拉后直得到新模型s 心上计算 显著性特征点，虽然能够避免噪声带来的干扰，但是另外外一方面，也使得细微的局部 特征被屏蔽，如图3 11 f 中猫头鹰的喙、以及图3 1 1 e 中的耳朵等处，较小的局部极值 点被临近的其他更为显著的局部极值点屏蔽掉。另外，在计算没有显著性分支的模型时， 所得骨架没有明确的意义，例如图3 1 1 9 中的椭球部分。 总体上，实验表明，本文方法在提取单连通的、具有复杂拓扑结构的三维网格模型 骨架时效果较好，连接显著性特征点麒和l o o p , 上各点的锥状最短路径集合确保了生 成的骨架位于分割块s ，的内部，提高了骨架的中心性；定义在核心分割块氐上的层次中 心环、以及瓯骨架的主曲线拟合法所得骨架的中心性较强、能够保持骨架的拓扑连续性。 对于任意给定的三维网格模型s ，设其三角面片数目为，则m d s 变换的复杂度为 o ( n 2 ) ；显著性特征点的提取复杂度为o ( n l o g n ) ；生成模型s 的一个k + 1 分割 s 。，s ，s 2 ，s 。的复杂度为o ( n l o g n ) ；计算连接环、结点环及中心环的复杂度为 o ( 1 0 9 n + n ) ；骨架线计算的复杂度为d ( ) ；因此，总体上，本文算法的复杂度为 o ( n l o g n + l o g n + n 2 + n ) = o ( n 2 ) 。 表1 为各模型显著性特征点数目、本文算法v c + + 编程的骨架计算时间。 表1 计算时间 一 ! 璺b ：! 堡旦婴巳些生旦璺t i 塑皇 模型顶点数面片数特征点数骨架计算( s ) 三维网格模型的骨架提取及细分 o u r 厂 i 、l 匕 m e t h o d ，0 。 7 i 。 ；。；7 一kk 。7 雌， f 飞。冬 。j r e e b g r a p h f 吣 一，一， ： 1f p o t e n o a i g￥ f l e l d 冬j 飞 、 j 7 “、h 、 f 炒 f 笤 - 3 - d i s t a n c e f i o l d 莓一一再 、矗瓠? 乏& f 。 心黟 t h i n n i n g 乏i i ，誊。 、 f 够 _ e d i a l _ + 钌 s u r f a c e 压一矿： 图3 1 2 实验结果对比 f i g 3 1 2c o n t r a s t 1 8 辽宁师范人学硕士学位论文 4 工作总结与展望 4 1 本文的工作总结 本文骨架提取算法的优势在于如下几个方面：算法没有涉及到复杂的数学工具，相 对于s n a k e 和l e v e ls e t 等骨架计算方法 1 1 , 1 2 , 1 5 1 而言，算法复杂度较低；使用m d s 预处 理提取特征点，使骨架计算在特征点的指导下进行，同时基于分割的策略进行局部骨架 计算，提高了算法的效率，并降低了噪声对骨架计算的影响，所得骨架的拓扑结构与模 型姿态是否有局部弯曲无关；最短路径的搜索在分割的基础上进行，解决了难以判断模 型分支、难以选择特征点等不足；不需要预先知道特征点的数目，也不需要用户交瓦输 入任何参数；所提取骨架与模型的姿态无关。 本文骨架提取