（计算机软件与理论专业论文）关节特征约束的骨架提取算法及其应用研究.pdf

辽，j t 师范人学硕士学位论文f i i i ii iii i irl l lll ll lllj y 17 9 4 8 6 8 摘要 近十几年来，模型骨架抽取这一课题已成为国际上比较热门的研究方向，包括 s i g g r a p h 在内的很多国际、国内的科研机构、学者对骨架抽取及应用进行了深入的研究， 使得这一方向的算法得到不断改进。 三维模型的骨架保持了模型的拓扑特性，被广泛应用于三维模型库匹配检索、动画 及压缩等领域。本文根据多分辨率r e e b 图( m r g ) 的原理，提出了一种基于离散高斯 曲率约束的骨架提取优化算法。其优势之处在于通过计算网格顶点的离散高斯曲率，判 断曲面凸凹特性，获取模型表面的双曲极值点作为约束点，以约束点为基础进一步得到 视觉突起与关节，找出凹陷区域，增加关节点，优化原始骨架。实验结果表明本方法有 效地突出了模型的拓扑分支特征以及模型表面的细节，提高了骨架提取的精度和效率。 提取三维模型骨架并不是最终目的，将骨架应用到某些领域才是骨架的价值所在， 不同的骨架抽取方法所针对的应用领域也是不同的，所以文章最后展示了利用本文优化 算法抽取出的骨架在三维模型匹配检索以及骨架动画这两大领域的应用效果。 本文总体上可分为三大部分： 。 第一大部分介绍了骨架抽取算法相关工作，它的历史和现状，优缺点对比，以及骨 架的应用。 第二大部分阐述本文算法的全过程，先引入m r g ，然后引入网格顶点的离散高斯 曲率，算法具体步骤，最终提取效果以及性能对比等等。 第三大部分给出了本算法骨架的一些应用，包括骨架动画变形和三维模型检索。 关键词：骨架抽取；多分辨率r e e b 图；离散高斯曲率；三维模型检索：骨架变形 s麓瞳憎氇置呵冒留蓄， t吖d鼍隋d爵塔墨甲醒1，再0-r 5p艮瞳10鼬藩叠1国卵呵簟|=，_， 关节特征约束的骨架提取算法及其应用研究 c u r v a t u r e c o n s t r a i n e ds k e l e t o ng r a p he x t r a c t i o na n di t sa p p l i c a t i o n s a b s t r a c t i nr e c e n td e c a d e3 dm o d e ls k e l e t o ne x t r a c t i o ni saw o r l d w i d ei m p o r t a n tr e s e a r c hi s s u e m a n ys c i e n t i f i co r g a n i z a t i o n ，i n c l u d i n gs i g g r a p h ，a n ds c h o l a rh a v et a k e nad e e pr e s e a r c ho n t h i si s s u e ，m a k i n gi ti m p r o v e df a s t s k e l e t o n sr e p r e s e n t e dt h et o p o l o g i c a ls t r u c t u r eo f3 dm o d e l s ；t h e yh a v eb e e nw i d e l y u s e df o rs i m i l a r i t yc o m p a r i s o n ，a n i m a t i o na n dd a t ac o m p r e s s i o na r e a sr e c e n t l y r e e bg r a p h s a r ec o m p a c ts h a p ed e s c r i p t o r sw h i c hc o n v e yt o p o l o g i c a li n f o r m a t i o nr e l a t e dt ot h el e v e ls e t s o faf u n c t i o nd e f i n e do nt h es h a p e b u ti ti sn o tc a p a b l eo fd e a l i n gw i t l ll o c a lg e o m e t r i cd e t a i l s t h i sa r t i c l ea d d r e s s e da no p t i m i z e ds k e l e t o ne x t r a c t i o na p p r o a c hb yu s i n gd i s c r e t eg a u s s i a n c u r v a t u r eb a s e do nm r gm e t h o d i tf i r s tc a l c u l a t e dt h eg a u s s i a nc u r v a t u r eo fe a c hv e r t e x w h i c hi m p l i e dt h ec o n v e xa n dc o n c a v ef e a t u r eo ft h el o c a ls u r f a c e s a n di tt h e ns e a r c h e dt h e c u r v a t u r ee x t r e m a ( c o n c a v ep o i n t ) a sc o n s t r a i n e dp o i n t s f i n a l l y ，n e wn o d e sd e n o t i n gt h ej o i n t f e a t u r e sa r ee x t r a c t e da n du s e df o r a d a p t i v e l yu p d a t i n g t h eo r i g i n a lr e e bg r a p h t h e a d v a n t a g eo ft h ee n h a n c e df e a t u r eg r a p hi st op r o v i d ea na f f i n e i n v a r i a n ta n dv i s u a l l y m e a n i n g f u ls k e l e t o no fa r b i t r a r yt o p o l o g i c a ls h a p ei nar e a s o n a b l ee x e c u t i o nt i m e as e r i e so fe x p e r i m e n t sw i t ha p p l i c a t i o n si na n i m a t i o na n ds h a p em a t c h i n gh a v eb e e n i m p l e m e n t e da n ds h o w nt h er o b u s t n e s sa n de f f i c i e n c y t h i sa r t i c l ec o u l db es e p a r a t e di n t o3p a r t s ： t h ef i r s tp a r ti n t r o d u c e sr e l a t e dw o r k ，c o m p a r i s o na n di t sa p p l i c a t i o n t h es e c o n dp a r tw o u l db et h em a i np a r tw h i c he x p a t i a t e st h ea l g o r i t h mo ft h i sa r t i c l e t h el a s tp a r ts h o w ss o m ea p p l i c a t i o no ft h es k e l e t o ne x t r a c t e df r o mt h i sa r t i c l ei n c l u d i n g s k e l e t o nd e f o r m i n ga n d3 dm o d e l sr e t r i e v a l k e yw o r d s ：s k e l e t o ne x t r a c t i o n ；m r g ；d i s c r e t eg a u s s i a nc u r v a t u r e ；3 dm o d e l sr e t r i e v a l ； s k e l e t o nd e f o r m i n g 辽j2 师范大学硕十学位论文 目录 摘要i a b s t r a c t i i 弓i言l 1r e e b 图和多分辨率r e e b 图( m r g ) 。：3 1 1r e e b 图：l 1 2 多分辨率r e e b 图4 1 3m r g 的优点与缺限5 2 关节特征约束的骨架提取7 2 1m r g 及函数的改进7 2 2 离散高斯曲率9 2 3 约束点的提取lo 2 4 视觉关节优化的骨架11 3 实验结果与分析l5 3 1 约束骨架优点与不足1 5 3 2 时间复杂度与效率对比1 9 4 关节约束算法的骨架实际应用2 l 4 1 骨架动画变形的应用2 1 4 1 1 骨架动画变形综述2 l 4 1 2 本文算法骨架在动画变形的应用2 2 4 2 三维模型匹配检索的应用2 4 4 2 1 三维模型相似性检索综述2 4 4 2 2 本文算法骨架在相似性比较中的应用2 7 结论3 5 参考文献3 6 攻读硕士学位期间发表学术论文情况3 9 致谢4 0 辽 引言 随着计算机图形技术的发展，模型骨架已被广泛应用于虚拟导航( v i r t u a l n a v i g a t i o n ) 、动画( a n i m a t i o n ) 、三维模型匹配( m a t c h i n g ) 、分解网格模型( d e c o m p o s i n g ) c a d c a m ，碰撞检测，压缩等领域1 7 1 。 骨架( s k e l e t o n ) 是将拓扑特性可视化以后形成的类似骨骼的内嵌于模型的图形， 本质上就是由结点和边结成的图。基于不同的原理，骨架提取算法可分为以下五类：( 1 ) 细化与边界伸展法，文献 5 ，6 1 ；它具有很好的连通性，且能保持原对象的主要拓扑结构。 ( 2 ) 基于距离场的方法，文献 3 ，4 】；该方法不能保证拓扑特性，且容易受到边界噪声的干 扰，但是该方法计算非常快速。( 3 ) 基于几何学方法；如：v o r o n o i 图、s h o c k 方法，文 献【8 ，1 2 】。这两类几何方法都是以中轴面或中轴线为基础的，其缺点是对噪声点非常敏 感，与细化方法相比，计算量过大。( 4 ) 广义场函数方法；基于径向基函数场( r a d i a l b a s i sf u n c t i o n ) 方法和可见反力场( v i s i b l er e p u l s i v ef o r c ef i e l d ) 方法，文献1 1 3 ，1 4 】。由于 其考虑更大范围内的模型边界点的作用，所得到的骨架更光顺，而且对噪声不敏感，其 缺点是计算量比较大。( 5 ) 基于r e e b 图的方法。该算法在模型表面上定义一个连续标量 函数( 如：高度、测地线、曲率) ，计算三维模型每个顶点函数值，将具有相同的函数 值且连通的顶点聚合为图的结点或边，得到r g 描述符构成的骨架，文献【1 ，9 ，1 0 。通 过选择合适的连续函数( 如测地线g e o d e s i c ) 造出的r g 具有平移、旋转不变性，对由 于模型的简化、子分、网格重构引起的连通改变是鲁棒的，对模型变形引起的变化、噪 声带来的影响不敏感。多年来研究者们围绕连续函数的选择以及优化，取得了一定的进 展，文献【2 ，11 】，其中最有意义的是h i l a g a 等人【l 】提出的多分辨率r e e b 图( m r g ) 算 法。它通过创建模型的多分辨率r e e b 图来满足检索时的不同分辨率要求。( 6 ) 还有 一些属于以上几种类型之外的方法，比如s h a r f 1 5 等人从点云和多边形网格两者中提取 出骨架，但是初始提取的骨架有噪声，需要过滤与融合。 然而随着对于三维模型研究的逐步深入，对于骨架描述中局部和全局细节特性的要 求逐渐提高，目前的r g 研究成果中，虽然能够有效的描述三维模型的整体拓扑分支结 构，但是缺乏表面细节特性的保留，尤其在主体与分支的连接区域缺乏有效的判断，为 了确定细小的分支部分，必须不断的提高模型的分区，因此，大大降低了骨架提取的精 度和效率。 本文基于m r g 算法，引入了离散高斯曲率，分析模型表面的凸凹细节，获取双曲 极值点作为约束点，从而进一步得到具有凹陷特性的区域，进行局部区域细化，在视觉 分支的联接处或关节处增加特性点，提高拓扑分支骨架的精度。同时，本文进一步优化 骨架提取算法及其应用研究 的生成算法。最终，高效地生成既体现模型细节 辽宁师范大学硕士学位论文 1r e e b 图和多分辨率r e e b 图( m r g ) r e e b 图是一种l d 的结构，它由结点和边组成，其结点( n o d e s ) 是定义在模型表 面的实值函数的关键点( c r i t i c a lp o i n t s ) 1 6 】，它反映了模型的拓扑结构f 1 7 1 。r e e b 图已被 运用于计算机图象处理、建模、可视化、模型匹配检索、骨架提取等各个领域。多分辨 率r e e b 图( m u l t i r e s o l u t i o n a lr e e bg r a p h ) 是在r e e b 图上的一种改进，使得最后得出的 骨架图有着旋转、缩放不变性等优势。 1 1r e e b 图 r e e b 图的定义如下l i j = 设? m 。尺是定义在模型m 上的连续函数，当且仅当以下 两个条件成立时( 如公式1 1 ) ，函数的r e e b 图就是原模型的商空间( q u o t i e n ts p a c e ) 。 黑pp 嚣1 2 a 川炯个连通部0 ， i l 与2 属于- 1 ( ( p 1 ) ) 的同个连通部分j u “7 r e e b 图的思想是在三维模型上定义一个连续函数，首先计算每个顶点的函数值， 然后根据值将模型上的顶点进行分类，值相同且位于同一连通分量上的点归为一类， 最终得到原顶点集的一个商集。将商集中的点根据原有模型点间的邻接关系连接起来， 就得到原有模型的一个骨架。 当函数被定义在流形上，由函数得到的关键点( 极大点、极小点、鞍点) 都是 非退化的，并且所有关键点的函数值都不相等的时候，函数就会成了m o r s e 函数1 。 一一1 m o r s e 理论进一步指出，对于厅代，( 1 1 ) 连通分支的亏格只在的关键点处发生改变， 因此关键点反映了矢量场的等值部分的拓扑，刻画了它的局部微分属性。根据r e e b 图的思想，不同的函数会产生不同的r e e b 图，所以函数的选取对于不同的r e e b 图应用就至关重要。 近年来根据r e e b 图思想产生了很多函数，比如高度函数等，如图1 1 。在早期， 高度函数得到了广泛的应用，多应用于地型处理。但是众多函数普遍存在着没有旋转不 变性、抗噪性差等缺点。如图1 1 ，一旦旋转模型，那么得出的r e e b 图将完全变化，而 实际中的模型坐标是没有一个方向标准的，它们确实存在着各种旋转和噪声。 图1 2 ：基本点 f i g1 2 ：b a s ev e r t i c e s 辽宁师范大学硕士学位论文 f i g1 z ： b a s ev e r t i c e s 公式1 2 中所有基本点占据的面积总和为模型s 表面积，即a r e a ( b ，) = a r e a ( s ) 。在 ， 提取基本点的时候，阈值r 用来控制每个基本点占据的范围，r 越大，每个基本点占据 的面积越大，基本点越少。文章【l 】中将r 设置成，= 4 0 0 0 5 a r e a ( s ) 。然后将规一化后 的函数值区间进行k 等分，找出划分后每个区间内的连通点集，聚合成一个骨架的关 节点，然后按一定顺序连接这些关节点即生成骨架。如图1 3 是高度函数的m r g 图， 体现了其基本算法思想。 m r g 算法的主要步骤为： 重采样，细分网格； 根据阈值r 选择基本点 b i ) ； 根据公式( 1 2 ) 计算每个顶点v 的函数值( v ) ： 选择区段数a n r a n g e sk ，将整个模型划分成k 段； 细分被n r a n g e s 分裂的三角形，确保让每个三角形属于一个区段： 创建r e e b 图的结点和边，也就是本文的骨架关节点和连线。 t 画_ 丽药； 糍 鼬k 产八 弋产 魄嗨 图1 3 ：高度函数的m r g ，从左到右分辨率逐渐增大 f i g 1 3 ：m r gu s i n gah e i g h tf u n c t i o nw i t ht h er e s o l u t i o na u g m e n t e d 1 3m r g 的优点与缺限 传统的r e e b 图算法，包括m r g ，虽然可以很好的反映模型的拓扑结构，然而这些算 法考虑每个顶点通过函数得到的信息都是相关的，它缺少对模型局部细节特征的描 述，表面的凹陷或凸起部分无法精确识别。图1 4 中虎的尾部骨架穿出了身体，而没有 从尾巴的根部通过，右图形象地说明了m r g 不能保留模型视觉特征细节这一缺点。想产 处多是 图1 5 算每个 辽j2 师范人学硕士学位论文 2 关节特征约束的骨架提取 2 1m r g 及函数的改进 测地线距离是需要一个源点的，取哪个点为源点就成了不稳定因素，计算机需要根 据不同的模型自动计算出源点，这是很困难也是鲁棒性很弱的。为了解决这个问题， m r g 方法提出了基本点这个要素，即首先抽取均匀散布于模型表面的一些顶点作为基 本点，再用这些基本点作为测地线距离的源点，从而将原先只有一个源点变成了多个源 点。那么不管模型怎么变，这些基本点是不会有大变化的，这样就大大加强了测地线距 离的稳定性。 在本文当中，我们首先改进1 2 小节提到的m r g 方法，使我们的方法更加简易有 效。首先本文省去了重采样以及网格细分，直接在原始多边形网格上进行处理。因为 m r g 中重采样和细分的目的是让每个小三角面片都能落入某一z n 。r a n g e s 区域，省去它 的理由是我们只考虑顶点落在了哪个n r a n g e s 区域，而不是面片，所以如果某一面片 被n r a n g e s 划分丌了，那么它的顶点落入哪个z n r a n g e s 足不受影响的，如图1 6 。 图2 1 ：顶点落入哪个区域不受影响 f i g 2 1 ：t h ev e r t i c e si sn o ta f f e c t e da b o u tt h eg n - r a n g e s 为了更加有效的获得均匀散布的基本点b ，我们改进了m r g 的阈值，。，- 相当于一个 基本点占据的表面半径，越小就会得到越多的b i 基本点。m r g 中r = 、i 0 0 0 5 a r e a ( s ) ( 其中 a r e a ( s ) 为模型表面积) ，因为a r e a ( s ) 处在根号中，且有着一个o 肿5 这个很小的因子， 这使得a r e a ( s ) 变得敏感，的抗噪性降低。本文对r 进行了改进，通过计算模型的包围 盒，选取在x ，y ，z 方向上的最大欧氏距离变化d i r ，因为模型表面的噪声几乎对包围 d i r 盒没有任何影响。r2 f a c t o r ，本f a c t o , 设为2 0 ，基本点比较均匀( 可生成1 5 0 2 0 0 左右的基本点) ，如图2 2 。 看 己 采 最 短路径实现，文章中提到的测地线距离，也就等价于最短路径。 用d i j k s t r a 最短路径来计算测地线距离算法描述： s t e p l ：初始化所有表面顶点v 的g 例= ； s t e p 2 ：选择一个任意的基本点b ，设置g 俐= 仍将该基本点插入或附加到v l i s t ， 这罩v l i s t 就是一个线性链表； s t e p 3 ：在v l i s t 中找到g 例最小的那个顶点v ，把它从v l i s t 中移除，但不要销 毁它。 一8 一 辽宁师范大学硕士学位论文 s t e p 4 ：对于每个与v 有边相连的顶点昭，如果g 纠手i e n g t h 化v a ) g 砂，则 更新g ( v a ) = 纠1 ll e n g t h 亿v a ) ，然后把阳插入或附加进v l i s t 。如果髓已经存在 于v l i s t 中，则用新值履盖它。这时需要销毁顶点v ，以防内存漏露。 要注意v l i s t 可以是像二叉树或线性链表之类的数据结构，在每次迭代中都需要找 出v l i s t 中g 纠最小的顶点v 。这里的l e n g t h 化训表示两点之间的边的长度。 p n 纠是例归一化后的值。归一化公式为： ( = 丝挈墨兰 ( 2 3 ) j i i ，【功= 工_ _ 7 弋 u - j j m x p 醯l p j i n u l 胙s u ” ， 。 这样，我们就计算出了模型表面所有顶点的规一化后函数值( ，) 。图2 3 展示 了改进后的m r g 整个提取骨架过程。 蹿 ( a )( b )( c ) 4 图2 3 ： ( a ) 首先计算基本点；( b ) 计算所有顶点的( v ) ，并分为k = 4 个区段；( c ) 同一m - m n g c 内 的顶点聚合为关节点 f i g 2 3 ：( a ) f i r s tc o m p u t et h eb a s ev e r t i c e s ；( b ) b a s e do nt h ev a l u e so f ( v ) a n d4p a r t i t i o n s ，t h em e s h m o d e li sd e c o m p o s e d ；( c ) t h e 融b g r a p hi se x t r a c t e d ( i n c l u d i n g2 0n o d e s ( y e l l o wb a l l s ) ) 从图2 3 ( b ) 可以看出( 1 ，) 的特点，即越往模型的边缘该值就越大，越往模型的中 间该值就越小。由这个特点我们就能够对模型进行分层，而层数k 由用户来决定。把属 于同一层或区段的顶点聚合，就得到骨架的关节点，把关节点按顺序相连就得到最终的 r e e b 图骨架。但是这个骨架是未经约束优化的原始骨架，还不能体现模型细节，不能 识别视觉意义上的分支连接处。 2 2 离散高斯曲率 曲率估算是分析和描述曲面形状的主要方法。对于曲面上的每个顶点p 存在两个主 曲率岛、忍，那么p 点的高斯曲率膨就被定义为两个主曲率的乘积尼忱。高斯曲率 一9 ， 通过该算法可以计算出表面所有顶点的离散高斯曲率。下面就要找到双曲极值点， 即k ； 0 的极值点，只有曲率小于0 时a 。会是凹陷的区域，有了凹陷区域，就很可能识 别出分支子部分的关节所在，从而产生新的约束关节点。在下面的一节中，我们将通过 曲率的判定比较来得到一些特殊的又曲极值点，称之为“约束点”，进而用约束点产生 “约束关节点 对原始骨架进行约束。 2 3 约束点的提取 模型的主干与分支连接处( 比如马身与马腿之间的连接处，鱼的身体和鱼鳍的连接 处) 或单一分支的子部分( 比如手指的关节) 通常会出现局部凹陷，所以凹陷顶点通常 代表着拓扑结构的突出分支或者子关节部位。由高斯曲率的几何意义，可以找到曲率极 值点，并选择双曲极值点作为约束点。 模型上的双曲点有很多，必须对其进行过滤，得到体现关节信息的约束点。我们设 定曲率阈值b o u n d = ( m a x c u r v a t l t e m i n c u r v a t w e ) n洲为模型表面基本点个数) 。每一 辽宁师范大学硕士学位论文 次选取曲率小于- b o u n d 的项点，以它为中心搜索，( 基本点半径) 范围内的曲率极小值 点作为约束点。如果此范围内存在曲率大于b o u n d 的顶点，则放弃这次的搜索，并选取下 个，范围作为候选区进行检测。极小值点周围应该是向大曲率渐变过渡，若附近有突 变的大曲率点说明该处有噪声或者只是表面偶然性波动，因此不作为真正约束点处理， 这样增加了对表面噪声的鲁棒性。如此往复，直至将所有顶点都搜索一遍。 图2 5 展示了顶点的过滤，一一直到少量的约束点。由图可见分支子部分的关节基本 位于约束点的附近区域，在下一节中就将介绍如何根据约束点定义合理的区域，最终产 生约束关节点，得到关节特征约束的骨架。 ( a )( b ) 图2 5 ：( a ) 模型上的所有双曲点( 红色球所示) ：( b ) 过滤后得到的约束点 f i g 2 5 ：( a ) t h ed i s t r i b u t i o no f a l lh y p e r b o l i cp o i n t so nm e s h ( r e db a l l s ) ；( b ) af e wc o n s t r a i n tp o i n t s ( b l u e ) 一曩 瓷 2 4 视觉关节优化的骨架 约束点的作用在于体现细节，体现视觉突起分支与关节，指示出模型表面视觉凹陷 或关节处的位置。要想在模型内部形成骨架关节点，必须得到环绕突起分支部分的凹陷 区域，在凹陷区域内部进行有意义的新骨架关节点的添加。从而打断原有骨架，重新确 立新旧关节点的连接关系，增加新骨头、新关节点，优化原始骨架。 图2 6 ：间隔变化的颜色代表子连通点集 f i g 2 6 ：d i f f e r e n tc o l o r sr e p r e s e n ts u b - c o n n e c t e dp o i n ts e t s 根据上面改进的m r g 算法得到初始骨架的同时，还会得到与骨架关节点对应的子连 通点集。一个k 等分后的函数值区间可能包括若干个子连通点集，比如图2 6 中同一 种颜色表示一个j n - r a n g e ，而其中相连通的点集才是子连通点集。 关节特征约束的骨架提取算法及其应用研究 约束点计算完毕以后，一个子连通点集罩可能会落入若干或o 个约束点。生成约束 关节点，最终建立视觉优化骨架的算法步骤如下： s t e p l ：查找子连通点集的边界。一个子连通点集的边界点集设为 一。n 。 n nd 、 v 2 v l ，v z ，即不属于本子连通点集但与本子连通点集有边相连的点集。一个子 连通点集可能有多个边界，v 岛= v p ，谚，) 是矿的一个子集，代表属于第i 个边界的 点集( 如图2 7 ( a ) ) 。 s t e p 2 ：建立约束点与子连通点集边界y 之间的对应关系。在当前子连通点集中取 出一个约束点，叫做当前约束点( c u r r e n t c p ) 。一个约束点与一个边界之间的距离定义 为公式： ：媾尊囊蠕焉e n t c p , v ? ，黪囊黪 d ( c u r r e n t c e ，矿6 ，) ：每二_ 一，0 = l ，2 多：西：；筹( 2 4 ) 。 霹， 庀 匆 其中后是边界y 点的个数，我们选择使得d ( c u r r e n t c p ，矿。) 取得最小值的边界i ，那么 约束点c u r r e n t c p 和边界矿。之间的对应关系就建立了。如果两个或者多个约束点与同 一边界相对应，则只取其中高斯曲率最小的那个约束点与该边界保持对应关系，而放弃 其他约束点的对应关系。这时一个边界最多可能与一个约束点相对应，也可能不与任何 约束点相对应。约束点也可能保持对应关系，可能不保持对应关系。 s t e p 3 ：上一步中得到的与边界有对应关系的约束点正是用来产生约束关节点的。 取出一个保持着对应关系的约束点c u r r e n t c p 为例，其对应的边界为y 。假设 l # ( c u r r e n t c p ) = ，k 等分后每段函数值区间范围为厶。建立一个函数约束点集： v = v i ( v ) ( 一d f ，+ d f ) ( 2 5 ) 其中v 是当前子连通点集中的点，当彤= 厶，d 时就可以取得足够多的v 点。然后设 d ( c u r r e n t c p ，矿) = d 。 ? 一 再次构造一个距离约束的点集：”。二：， j t ? 一。 v = 矿i 矿v ，d ( 矿，v q ) 一4 9 ) s h o w st h ec u r v a t u r e c o n s t r a i n e df e a t u r eg r a p h ( r e d b a l l sa r en e wc r i t i c a lp o i n t sw h i c hr e v e a lt h ea r t i c u l a t i o nf e a t u r e si n3 dp o l y g o n a lm e s h ) 3 2 时间复杂度与效率对比 给定一个单连通的三维网格模型m ，设n 为模型表面顶点个数。在构建原始m r g 骨 架的过程中，d i j k s t r a 最短路径算法需要时间复杂度o ( n l o g n ) ，并且构建r e e b 图的时 间为d 俐，因为只是简单计算表面网格的连通子部分。在运用曲率和关节特征进行优化 的过程中，离散高斯曲率计算消耗去o ( k n ) ，k 是多边形网格的边数，多取3 或4 。约束 点与边界的对应消耗时间d f l 爿n l o g ( n ) ) ，其中旧是得出的约束关节点的个数。约束 环区域的计算更加直接，d f l 用肌) ，其中m 是子连通点集的顶点个数，它远小于n 。 最终结果表明，我们算法的全局复杂度的瓶劲在于约束点与边界对应的计算，它花去了 0 加l o g ( n ) ) 的时间复杂度。但是这个复杂度要比文献【2 】的离散轮廓环约束算法更加高 效，文献 2 】的耗费了o 向乡以得到一个视觉有意义的骨架。 我们的算法实践平台为p e n t i u m3 gc p u ，2 g 内存的i b mp c 机，并使用了c 语言、 o p e n i n v e n t o r 和o p e n g l 图形库软件开发环境。表3 1 列出了本文算法的计算时间，统 计了算法的运行特性，可见，本算法在执行速度上是高效的。 表3 1 算法的运行特性 t a b 3 1t h ep e r f o r m a n c eo fo u ra l g o r i t h m ，煮竺、吁裂分琴奎掌m r 9 掣点喜焉羹聒訾差墨熟优化 ( 项点数)( 个) ( 个) ( 个) 川”：笨；“”“：秘；“。 3 0 6 1 8 6 2 0 8 2 5 2 2 2 1 5 9 2 0 2 92 8 1 3 + 1 7 5 s 2 20 5 + o 3 4 4 l50 5 9 3 + 0 2 6 2 8 1 9 6 9 + 0 7 8 、，、， q o 6 n 纠 8 3 5 强 2 0 9 砭 ( 9 (“u r 一 一 一 q 眦 出 苦 关俐寺征约束的骨架提取算法及其应用研究 6 1 7 2 2 4 2 80 1 2 5 + 0 0 7 8 骨架在动画变形以及三维模型匹配检索领域的相关工作和科研现状，再 实验结果，来展示本文算法提取出的优化骨架在这两大领域中的实际应 辽宁师范人学硕士学位论文 4 关节约束算法的骨架实际应用 4 1 骨架动画变形的应用 4 1 1 骨架动画变形综述 三维形状的变形是几何建模、形状设计和计算机动画的一个重要工具。一个很重要 的研究课题是怎样调整物体的形状。三维变形方法主要包括基于物理的变形和空间变形 这两种，其中使用比较多的是空间变形方法。空间变形是改变物体形状的重要操作，动 画中的许多新奇效果往往是通过物体的变形来实现的。最简单、最直观的变形方法是 通过移动物体的顶点或控制顶点，但是，若我们要对物体进行某种整体变形或者需移动 的顶点非常多时，该方法就显得相当费时和繁琐。近l o 多年来，与物体表示无关的变 形方法越来越成为人们研究的课题。现在应用比较广泛的空间变形技术是s e d e r b e r g 和 p a r r y 提出的自由变形( f r e ef o r n ld e f o r m a t i o n ，简称f f d ) 技术1 2 0 l 。与物体表示无关的变形 可分为以下几类：( 1 ) 调整变换参数的变形方法。b a r r 提出的整体和局部变形是与物体 表示无关的变形中最早的工作。( 2 ) 基于嵌入空间变形的物体整体变形方法。s e d e r b e r g 和p a r r y 提出的f f d ( f r e ef r o md e f o r m a t i o n ) 自由变形方法是空间变形最有效的方法之一 1 2 0 1 。( 3 ) 基于约束的变形方法。在基于类f f d 的方法中，用户必须先在待变形区域的周 围定义控制顶点，然后操纵这些控制顶点。 f f d 方法不对物体直接进行变形，而是对物体所嵌入的空间进行变形，f f d 方法 中b 6 z i e r 参数体的形状为平行六