（计算机应用技术专业论文）基于特征点求解的reeb图骨架提取.pdf

摘要 针对目前骨架提取算法普遍存在的准确性与复杂度的矛盾，本文提出一种基于特征 点求解的r e e b 图骨架提取算法，创新地将提取特征点和r e e b 图结合用于骨架提取，在 保证骨架提取准确性的同时，降低计算复杂度，加快提取骨架的速度，提高算法效率。 在j u l i e nt i e m y 提出的应用于骨架提取的特征点提取算法为基础，对多处原实现细 节进行了改进或提出了新的替代方法。提出了中心最近点算法用来提取模型的最远点 对，避免了传统算法导致的f l o y d 算法瓶颈问题，提高了整体算法的执行效率；针对三 角网格模型的特征点提取阈值，给出了两种自适应阈值取值方法：直接取值法和一阶邻 域取值法。直接取值法以多组实验数据作为取值依据，自适应地给出一个较宽泛的特征 点提取阈值，一阶邻域取值法采用特征点的一阶邻域边长作为取值依据，两种方法都能 快速有效地提取特征点，提取结果的完备性和准确性能够满足骨架提取的要求。 在提取特征点的基础上，通过对进行骨架提取的总体流程进行充分分析，给出了骨 架提取的总体实现方案。以提取的特征点为计算依据，结合映射函数对模型顶点进行分 类计算，求得模型分支，提出拓扑结构法用于聚合模型的分支顶点，提取骨架点。为避 免干扰点和骨架环路影响骨架提取效果，给出了剔除冗余点的具体方案。 实验结果表明，基于特征点求解的r e e b 图骨架提取算法在保证骨架提取精度的同 时，具有较低的计算复杂度，能够快速提取骨架，针对一般模型的骨架提取效果较好。 关键词：骨架提取，特征点，r e e b 图，3 d 模型 s k e l e t o ne x t r a c t i o nu s i n gr e e bg r a p hb a s e do nf e a t u r ep o i n t s k a n gc u l ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f z h e n gq i u m e ia n da s s o c i a t ep r o f g o n g f a m i n g a b s t r a c t a i m i n ga t t h ec u r r e n tc o n f l i c tb e t w e e nt h ea c c u r a c ya n dc o m p l e x i t yw h i c he x i s t si n c u r r e n ts k e l e t o ne x t r a c t i o na l g o r i t h m ，an e wa l g o r i t h mo fs k e l e t o ne x t r a c t i o nb a s e do nf e a t u r e p o i n t sa n dr e e bg r a p ht h e o r yi sp r o p o s e d t h ea l g o r i t h mc a ne n s u r et h ea c c u r a c y , r e d u c et h e c o m p u t i n gc o m p l e x i t y , a n di m p r o v et h es p e e da n d t h ee f f i c i e n c yo fs k e l e t o ne x t r a c t i o n t h ef l o y da l g o r i t h mi su s e di nt h ef e a t u r ep o i n t se x t r a c t i o na l g o r i t h m ，w h i c hi su s e di n s k e l e t o ne x t r a c t i o na n dp r o p o s e db yj u l i e nt i e m y f o ri t sh i g hc o m p u t i n gc o m p l e x i t y ，a n a l g o r i t h m f o r e x t r a c t i n g t h e t w o - - l o n g e s t - g e o d e s i c - p o i n t s o fm o d e l sb a s e do nt h e s h o r t e s t d i s t a n c ew i t ht h ec e n t e rp o i n ti sp r o p o s e dt ot a k ep l a c eo ft h ef l o y da l g o r i t h m i n t h ev i e wo ft h ep r o b l e mo fd e t e r m i n i n gt h ef e 舭p o i n t s e x t r a c t i o nv a l u ef o rd i f f e r e n t m o d e l s ，t w oa l g o r i t h m sf o rf e a t u r ep o i n t s e x t r a c t i o ns e l f - a c c o m m o d a t e dv a l u ei sp r o p o s e d o n ei sc a l l e dd i r e c t v a l u ea l g o r i t h m ，w h i c hs e tt h ev a l u eb a s e do ne x p e r i m e n t a lr e s u l t s ；t h e o t h e ri sc a l l e dn e i g h b o r v a l u ea l g o r i t h mt h a ts e tt h ev a l u ea st h ea v e r a g eo ft h ea d j a c e n t e d g e sl e n g t h b o t ha l g o r i t h m sw o r kw e l la n dc o u l dm e e tt h en e e d so fs k e l e t o ne x t r a c t i o n w h i c has u f f i c i e n ta n a l y z i n gw a sd o n eo nt h ef l o wo fs k e l e t o ne x t r a c t i o n ，t h i sp a p e r p r e s e n t st h ed e s i g np r e c e p ta saw h o l ea n di m p l e m e n t a t i o nt e c h n o l o g y b yu s i n gf e a t u r e p o i n t sa n dd e f m i n ga na p p r o p r i a t em a p p i n gf u n c t i o n ，w ef i n i s hm o d e lb r a c h e sc a l c u l a t i o n 。 t h i sp a p e rp r e s e n t sa na l g o r i t h m ，w h i c hc a l l e dt o p o l o g ya l g o r i t h m ，t oe x t r a c ts k e l e t o np o i n t s a na l g o r i t h mf o rd e l e t i n gr e d u n d a n tp o i n ti sa l s op r o p o s e d e x p e r i m e n tr e s u l t ss h o wt h a tt h em e t h o dc o u l di m p r o v et h ee f f i c i e n c ya n dc a r le n s u r et h e a c c u r a c y , r e d u c et h ec o m p u t i n gc o m p l e x i t ya n di m p r o v et h es p e e do fs k e l e t o ne x t r a c t i o n k e yw o r d s ：s k e l e t o ne x t r a c t i o n , f e a t u r ep o i n t ，r e e bg r a p h ，3 dm o d e l l l 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均己在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名： 鳇日期：细1 年5 月2 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门 ( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被 查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用 影印、缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：建墨 指导教师签名：竺毫丕么扯 - j 参 识狃 同期：办dc 年 日期：2 0oc 1 年 占月7 2 同 5 月2 2 同 中国石油大学( 华东) 硕士学位论文 第一章绪论 1 1 课题来源、提出背景及意义 信息技术的发展使得信息处理对象已从简单二维图像发展到更为真实丰富的三维 模型。计算机图形学的迅速发展促进了三维可视化技术的形成，使得我们能够再现三维 世界的物体，运用三维模型表示各种复杂的信息。 通过计算机处理后获取的三维模型是对三维物体原始数据更规范化的数学形式描 述，通常十分庞大，并且带有冗余信息，给三维模型的应用带来很多限制，例如三维模 型的识别，就不适合直接采用三维模型作为处理和匹配对象。考虑用更加精练的模型来 表示复杂三维物体的本质特征，这就是三维模型的特征提取。 三维模型的提取特征可分为代数特征和几何特征两大类。代数特征一般是对目标进 行数学描述后所计算出来的一些数学特性，例如通过曲面拟合描述的三维模型，可以根 据其拟合多项式的参数获得模型的各个数据特征。然而这类特征的几何特性不直观，而 且对于数学模型的理论研究要求较高。几何特征主要指的是图形的几何尺寸。相对而言， 几何特征在描述几何特性方面则更加直观一些，并且适用性更加广泛，对于一些不规则 的难以用方程表达的物体同样可行。 骨架作为图形几何形态的一种拓扑描述，是一种重要的几何特征，直观地反映了图 形的形状和拓扑特征，能够保留模型由粗到精的分层次信息，精度高的骨架甚至能保留 模型的完整信息，重建原始模型，因此其应用领域越来越广泛。骨架除了应用于对象识 别与表示、工业零件检测、印制电路板校验、医学图像分析等传统领域外，还经常应用 于其它领域，如三维数据的压缩、物体特征识别与跟踪1 ，2 1 、三维表面重建【3 1 、自动导 航及可视化4 ，尤其在医学图像应用领域，对于计算机辅助诊断与辅助手术治疗【6 7 】 等具有非常重要的意义。 国内外研究人员对骨架算法的研究已进行了三十多年，通过阅读文献和研究发现， 二维图形骨架化的研究比三维情况下要成熟许多。图形学向三维空间的拓展，使得骨架 化的研究也日趋偏向于三维空间模型。然而，三维模形数据量很大，提取的三维骨架不 仅包含点、线，还存在面，大大增加了计算复杂度。如何在保证骨架提取算法准确性的 前提下，降低计算复杂度，提高骨架提取速度己成为目前研究的热点。 第一章绪论 1 2 国内外研究现状 国内外研究人员经过三十多年的不懈努力，在骨架算法方面的研究已经取得了很大 成就。 g o n g 8 】等人提出过一种基于拓扑细化的并行细化算法，通过先定义模型的简单顶 点、删除谓词和两个细化元操作，在抽取算法中不断迭代两个元操作进行模型细化，得 到模型的骨架。车武军和杨勋年提出一种改进的细化算法【9 】，首先用传统细化法求出连 通的骨架，然后引入s n a k e 模型调整骨架的位置，从而解决了骨架位置不精确的问题。 s u n d a r y 1 0 】等人提出过基于距离矩阵的一个算法思路，通过计算每个体元素得到边 界的最小距离来得到骨架点，s u n d m y 采用该算法创建了一个模型的检索系统。n i b l a e k 和g i b b o n 引入了鞍点( s a d d l ep o n s ) 的概念【1 1 】，用于解决基于距离变换骨架算法难以保 证骨架连通性的问题，能将不连通的骨架部分连通起来。g e 和f i t z p a t r i c k 给出了离散 图形中两个离散圆包含关系的判断准则【1 2 1 ，用以求得最大圆，并给出了鞍点的寻找方法。 b i t t e 和k a u f i n a n 的方、法【1 3 】不但计算距离变换，还引入梯度变换，即距离变换的l 阶导 数变换，能明显的反映出哪些点具有距离变换的极大值，从而提高骨架点提取精确度。 该方法主要用于柱状物体提取骨架。z h o u 和t o g a 的方法【1 4 】定义了两种衍生的距离变换， 一种称作b s ( b o u n d a r ys e e d e d ) ，另一种为s s ( s i n g l ep o i n ts e e d e d ) 。b s 类似于传统的距 离变换，计算任意体素到图形轮廓的最短距离。s s 则是首先选定图形内部的一个特定 点，然后计算任意体素到该点的最短距离。c h o i 1 5 】提出了基于连续准则下由距离变换形 成的骨架，但是在引入尺度因子的条件下，连续性仍然得不到保证。g a g v a n i 采用了一 种简单方法1 1 6 】，比较每个点与其领域点的距离变换值，满足一定局部最大条件的点被选 取为骨架点。 d e y 1 。7 】等人提出过一种利用v o r o n o i 图直接近似中轴的算法。o g n i e w i c z 给出了利 用v o r o n o i 图计算二维骨架的方法【1 8 1 ，r e d d y 和t u r k i y y a h 利用v o r o n o i 图的反变换 d e l a t m a y 三角化计算三维骨架t 1 9 。v o r o n o i 图方法对于复杂的三维模型，理论上可以实 现，但是计算量十分庞大。v o r o n o i 图方法多用于生成多尺度骨架，但对于边界噪声非 常敏感，导致v o r o n o i 图过于稠密，需要额外进行剪支处理，而且规则复杂，导致该方 法适用性不广。 h i l a g a 2 u j 等人提出了基于r e e b 图思想的多分辨率r e e b 图( m r g ) ，将r e e b 图用于骨 架提取，并将映射函数定义为顶点到整个模型表面所有顶点的最短距离与面积乘积的 2 中国石油大学( 华东) 硕士学位论文 和。j u l i e nt i e m y 【2 1 】等人使用了更加合理的标量函数计算方法。l i e l l 【2 2 1 等人观察到对于 保存模型连接性分解过程就是一个骨架抽取的过程，所以提出了基于模型近似凸面体分 解的骨架抽取算法，通过计算模型表面的桥识别模型表面凹地，计算每个顶点的凹陷性， 并对模型按照凹陷性进行分解，不断迭代该过程创建骨架。 在国内，清华大学的张绍广瞄】等提出了一种基于权值的骨架提取算法，为解决骨架 提取提供了一种新的途径。台湾学者m a e 2 4 】等人提出过基于可见互斥力的骨架抽取算法， 它应用了物理学上的互斥力的概念来计算模型上的平衡点，最终得到模型的骨架。 王刚等【2 5 】提出一种基于区域增长的树状体数据的骨架提取算法，充分利用了区域生 长算法在计算速度方面的优势，能从复杂的空腔组织中提取简单骨架，算法能够自动检 测树状组织的分支和自动确定分支的结束节点，能够应用于提取三维物体的骨架和获取 虚拟内窥镜自动漫游路径方面。 南京大学的黄坤武等通过研究m r g 算法，指出m r g 算法的不足【2 6 】：m r g 算法 在计算模型聚合函数时都采用了全局计算方法，将模型表面上所有的顶点或面片作为函 数计算依据，对于顶点或面片数量较多的高分辨率模型，算法的执行效率成为瓶颈；另 外，这种全局计算方法不能消除临近顶点( 面片) 对函数值的负面影响，影响了函数值 的实际聚合效果；m r g 算法对实际应用中的模型可能包含多个连通分量的情况处理不 理想。基于此，黄坤武等提出改进算法，修改了m r g 关于映射函数的定义以及骨架点 的生成算法，从而提高算法处理效率。另外，黄坤武【2 7 】等还提出了一种基于面片采用 r e e b 图对多边形网格模型进行骨架抽取的算法，通过对模型进行一定预处理以保证面 片的规则，定义面片间距离的计算方法，创建模型的对偶图，识别连通分量，在连通分 量上应用r e e b 图的计算思想抽取原型骨架。 三维模形数据量巨大，计算机处理起来复杂度高，而且现有的大多数典型骨架提取 算法( 如细化法、距离变化法、v o r o n o i 图方法等) ，由于算法本身限制，很难推广到三 维，即使有些算法理论上可以实现，计算量也十分庞大。与此相反，r e e b 图能很好的 表达三维模型的拓扑形状，在三维模型拓扑形状描述方面应用非常广泛，因此，越来越 多的研究将r e e b 图应用于三维模型的骨架提取。 三维模型的特征点处于物体的极端位置，将特征点与r e e b 图思想结合应用于三维 模型的骨架提取，可以保证提取骨架完整性与准确性。 3 第一章绪论 1 3 研究目标和主要研究内容 本文研究目标：通过分析研究三维模型骨架提取技术，在提取三维模型特征点的基 础上，以特征点为计算依据，结合r e e b 图思想，实现一种新的三维网格模型骨架提取 算法。提取特征点的数量和准确性能够满足提取骨架的需求，在保证骨架提取准确性的 同时，降低算法的计算复杂度，减少运行时间，提高算法效率。具体研究内容包括以下 几个方面： ( 1 ) 通过分析总结骨架提取的基本需求，确定基于特征点求解的r e e b 图骨架提取算 法的算法思路和总体设计方案，并对主要问题给出相应的解决方法。 ( 2 ) 实验中要用到三维网格模型，通过研究相关理论和实现技术，实现三维网格模 读取、存储等操作。 ( 3 ) 在j u l i e nt i e r n y 提出的应用于骨架提取的特征点提取算法的基础上，针对f l o y d 算法复杂度高影响算法整体运行效率的问题，提出基于距离模型中心最近点算法以取代 f l o y d 算法提取测地线距离最远点对；针对特征点提取阈值的取值问题，提出两种具体 的取值方法( 直接取值法和一阶邻域取值法) ，分析两种方法的适用对象，并在提取速 度和提取效果方面进行比较分析，以确保有意义的特征点提取的完备性。 ( 4 ) 以三维模型的特征点为计算依据，根据特征点与待计算顶点之间的测定线距离， 确定合适的映射函数对模型顶点进行分类，实现分支计算。 ( 5 ) 针对三维模型复杂程度不同的情况，提出两种分支点合并算法用以提取骨架点， 即：平均值法和拓扑结构法，通过实验对两种方法从算法效率方面进行分析比较，指出 二者的适用对象。 ( 6 ) 提出临近骨架点合并方法用来剔除干扰点，提高提取骨架点精确度。并针对连 接骨架点时可能造成骨架环路的问题提出具体解决方法。 ( 7 ) 通过实验给出基于特征点求解的r e e b 图骨架提取算法方案的相关数据和效果 分析图表，分析算法的局限性并提出改进方案。 1 4 论文的组织结构 论文的组织结构如下： 第一章绪论 主要介绍本课题的提出背景、目的及意义，总结国内外研究现状，提出论文的研究 4 中国石油大学( 华东) 硕士学位论文 目标，以及基于特征点求解的r e e l ：) 图骨架提取算法研究的内容与思路。 第二章骨架提取技术概述 主要介绍骨架提取技术的基本原理和常用的骨架提取算法，并着重介绍r e e b 图的 相关理论以及基于r e e b 图思想的骨架提取算法。 第三章三维网格模型的特征点提取算法 研究应用于三维模型骨架提取的特征点技术的基本理论和相关提取方法，分析算法 局限性，并进行相应改进，使提取的特征点能够满足骨架提取算法的需求。通过实验数 据对算法效率进行分析验证。 第四章基于特征点求解的r e e b 图骨架提取算法 给出基于特征点求解的r e e b 图骨架提取算法的具体实现方案，并针对具体问题提 出具体解决方法。 第五章算法实现 实现特征点提取算法，通过实验确定自适应特征点提取阈值s 的取值。实现基于特 征点求解的r e e b 图骨架提取算法，通过实验数据对比分析两种骨架点提取方法，确定 二者的适用环境，并针对骨架中存在干扰点和骨架环路的问题，通过对改进前后的效果 图进行对比来验证改进算法的有效性。 第六章全文总结。 总结全文工作，列出主要的研究工作及取得的创新，指出不足，并明确进一步的研 究内容。 5 第二章骨架提取技术概述 2 1 前言 第二章骨架提取技术概述 三维模形的骨架位于图形的对称中心，类似于动物的骨骼决定动物的外形，三维模 形的骨架描述了图形的拓扑结构和重要的几何特征。利用骨架表示三维模形，可以在保 留图形重要拓扑特征的前提下，减少图形的冗余信息，降低计算的复杂度，有利于三维 模形的推广和应用。 理想的骨架提取算法应能够满足如下要求： ( 1 ) 提取的骨架保留了原始图形的拓扑特征，即：骨架是连通的，且为单像素宽。 ( 2 ) 提取的骨架带有一定的形状信息，且对边界噪声具有一定的抗干扰能力。 ( 3 ) 算法适用于离散体素模型，并且适合推广到三维领域。 由于三维模形数据量巨大，以及现有的适用于二维图像的骨架化算法自身的局限 性，使得骨架提取算法在三维领域还有很大的发展空间。 2 2 骨架 骨架又称中轴( m e d i a la x e s ) ，是一种性质优良的图形几何特征和有效的图形描述手 段。它是一种线型的几何体，居于图形的对称中心，有着与原图形相同的拓扑结构，并 能保留原图形的形状信息。骨架能够直观地反映出了图形的形状和拓扑特征，其线型结 构有利于降低后续匹配过程的设计难度，并且能抓住图形的本质特征，多尺度骨架还能 很好地保留模型由粗到精的分层次信息以实现图形匹配，因此骨架在三维模形识别领域 受到了越来越广泛的关注。 图形学中对骨架都有着明确的定义，任何图形的骨架都是唯一确定的。下面介绍三 种最为典型的定义。 定义2 1 对于图形a 内的一点p ，若以p 点为圆心的图形内切圆( 球) u p 与a 的边界有 至少两个切点，则点p 是图形a 的骨架点。 定义2 2 对于图形a 内以点p 为圆心的圆( 球) d ，若不存在图形a 内的圆( 球) d ， 使得d ，c d a ，则马是图形a 的最大圆，点p 是图形a 的骨架点。 1 9 6 7 年b l u m 最早给出定义2 1 的物理描述【2 8 】，通过模拟烧草模型( g r a s sf i r em o d e l l ， 6 中国石油大学( 华东) 硕士学位论文 假设图形边界点同时着火，火源向图形内部各个方向等速的燃烧直至熄灭，所有熄灭点 的集合就构成了该图形的骨架。后来，b l u m 在最大圆理论基础上给出了定义2 1 2 9 ，即骨 架是所有最大圆的圆心集合，最大圆是完全包含在图形内部的圆，并且不被任何其它包 含在图形内部的圆所包含。s e r r a 从数学形态学( m o r p h o l o g y ) 的角度也对骨架进行了如下 定义【3 0 1 。 定义2 3 设集合xcz ”，b 为单位闭球，则集合x 的骨架s k ( x ) 由一系列骨架子 集s k ，( x ) 组成，s k ( x ) = u s k ，( x ) 。其中s k ，( 肖) = i ( xo 培) 一( xor b ) 地 。 r ok o 上述定义经证明是完全等效的。定义的基础是连续空间，而实际应用中绝大多数情 况下处理的都是离散图形，例如以像素点集构成的二维图像、体素表达法描述的三维模 形。离散空间的骨架实际上是对连续域骨架定义的近似，定义过程本身往往与具体的骨 架算法结合在一起，如何定义离散空间的骨架是一个难点，并且直接关系着提取骨架的 优良。下文将具体介绍当前几类主要的骨架提取算法。 2 3 烧草模型法 该类算法主要应用于采用体表示的模型上，通过模拟烧草模型的物理原理，由图形 的边界开始向内演化，最终提取到模型的骨架。 2 3 1 细化法 细化法是烧草模型法的一类典型代表算法。其基本思想是：在确保不改变模型拓扑 特性的前提下，逐层均匀剥掉图形边界点，剩下最后不能再削减( 否则会影响连通性) 的 部分，使之最终成为单像素宽的先行几何体，即图像的骨架。 细化是一个迭代的过程，根据体素模型中像素及其邻域像素的分布关系，采用一定 的规则对模型进行过滤操作，去除冗余信息，保留中心像素，如此反复迭代，直至没有 冗余信息。每次细化操作依赖于上次的操作结果。 算法具体实现是通过定义一类简单点( s i m p l ep o i n t ) ，这类点即使被移除也不会影响 原始图形的连通关系，因此，某点与其邻域点的连通关系可作为该点是否简单点的判断 依据。每次细化操作去除本轮的简单点，循环执行迭代过程直至去除所有简单点，剩余 的点集就构成骨架。从所得到的骨架类型来看，细化算法又可分为中轴面( m e d i a ls u r f a c e ) 骨架化方法【3 1 3 3 】与中轴线( m e d i a ll i l l e ) 骨架化方法 3 4 - 3 6 1 。 简单点中有一类称为末梢点( e n dp o i n t ) ，该点在二维图形内的特性是只与图形内的 7 第二章骨架提取技术概述 一点相邻。末梢点在迭代过程中不能去除，否则将影响提取骨架的完整性。由于末梢点 在三维领域的定义不容易确定，影响了细化法向三维领域的推广。 细化法适用于离散空间的骨架提取，并已发展得较为成熟，常运用于图像目标形状 分析、信息压缩、特征提取与描述的模式识别等应用。细化法能够保证优良的连通性， 即提取骨架保持与原图形相同的拓扑特征，这是细化法最大的优点，但是这类方法处理 的体表示模型数据量巨大，并且需要进行迭代运算，导致计算复杂度高，计算量非常庞 大，整个过程非常耗时；经过离散处理的细化法提取的骨架结果位置不精确，这是因为 在离散域里任何点的行进方向依赖于图形局部信息，无法对全局特征进行把握，难免受 到边界噪声的干扰，从而影响到骨架位置的精确度，难以满足理想骨架化算法的稳定性 要求；对具有椭圆截面和不规则形状的物体的细化处理还需要进一步改进；对初步提取 的骨架线还没有解析处理使之成为一棵保持拓扑结构的曲线树，这些都是细化法存在的 不足之处。 2 3 2 蛇形边界法 该算法引入蛇形模型在建立了距离变换的图形内运动，从外围边界在距离变换场牵 引下向骨架位置演化。此类方法能保证较高的精确度，但是向三维空间推广有一定的难 度。 2 4 距离变换法 距离变换概念i 扫r o s e n f i e l d 和p f a l t 【3 7 】于l9 6 6 年首次提出，并被广泛应用于图像分析 和模式识别领域【3 8 , 3 9 。一个二值图像可以看作包含背景( 1 像素) 和特征( 0 像素) 两种 像素( 如图2 1 所示) ，设p 为b ( p ) = 1 的像素区域，q 为b ( q ) = o 的像素区域，从p 的任意像 素到q 像素的最小距离的过程就是距离变换。 其定义f 4 0 】表达如下： 定义2 4 离散域的二值图像i ( m ，1 1 ，o ) 的距离变换的定义： d 及：j m m 哩刃”p 呈，其中 始妇，g ) 表劫、g 间的距离。取不同的计算方 l o p 0 法，就得到不同的距离变换。 城市( c i t yb l o c k ) 距离：d i s t ( p ，g ) - | x j 口一x 9l + ly ，一y gj ； 棋盘( c h e s s b o a r d ) 距离：d i s t c h e s s ( p ，g ) = m a x ix p x gi ，i 少p y g1 ) ； 中国石油大学( 华东) 硕士学位论文 欧式( e u c l i d e a n ) 距离：d i s t 西五( p ，g ) = 圻i j i 了了石而 图2 1 二值图像 f i g2 - 1b i n a r yi m a g e 从声浪模拟的角度看，欧式距离为最优变换，城市距离和棋盘距离都是对其不同程 度的近似。但是在离散情况下，非欧式距离变换计算相对简单，在图像处理诸多领域得 以应用。 基于距离变换提取骨架算法的基本思路是计算模型内部体素到边界体素的距离，通 过以某点为圆心作的内切圆，判断此内切圆是否为最大圆( 即该圆不被其它的任何内切 圆包含) ，如果是则此点即是骨架点。算法处理对象一般为体表示模型，通过计算每个 体元素的距离求取模型的骨架点。 该算法能够很好地解决细化法提取骨架位置不准确的问题，在提取骨架的准确度方 面有明显的优势，求出的骨架可以反映物体的本质结构特征，不受模型平移、旋转、比 例变化的影响。但是这类方法很难保证骨架的连通性，这将影响骨架拓扑特性的表达， 若采用该方法提取的骨架恢复原始图形难以保证图形的连通性。此类方法也难以保证提 取骨架的单像素特性，进而影响匹配算法地进行。 2 5v o r o n o i 图近似法 2 5 1 v o r o n o i 图 v o r o n o i 匿 是计算几何领域里的一项重要工具【4 1 1 。对v o r o n o i 图研究始于1 9 7 5 年 s h a m o s 和h o e y 联合发表的论文“c l o s e s t - p o i n tp r o b l e m s ，从此计算几何诞生。在不同 领域，v o r o n o i 图有时也被称为t h i e s s e n 多边形、d i r i c h i f i t 网格、或w i n g e r s e i t z 区域等， 它是关于空间邻近关系的一种基础数据结构【4 2 ，4 3 1 。 9 第二章骨架提取技术概述 图2 - 2v o r o n o i 图 f i g2 - 2 v o r o n o id i a g r a m 图2 2 给出了一组点及其生成的v o r o n o i 图。这组点由空间里的n 个点组成，记为点集 s j 对于s 中的点p i ，v o r o n o i 多面体表示到点p i 距离小于到点集s 内其它任何点的距离的 空间区域。v o r o n o i 图即为所有这些v o r o n o i 多面体的集合。 2 5 2v o r o n o i 图与骨架 根据骨架的定义2 1 ，图形的最大圆( 球) 与图形边界是相切的，切点的距离相等且取 最小值。因此，图形边界点集的骨架点与至少两个边界图能够给出部分的骨架。不完备 之处在于图计算的是空间内到给定点集距离最小的区域，因而不区分图形内外部分，在 遇到有凹点的图形时与精确骨架有差别，可知骨架是v o r o n o i 图的子集。 该算法的基本思想是先提取线状对象的边界线，提取的边界线按照一定的规则或者 约束条件，如等距离或者等时间间隔取点对边界线进行离散化，得到近似描述这些边界 线的离散点，并存储点边的隶属关系信息，生成v o r o n o i 图，得到一系列的多边形。根 据离散时所存储的点线之间的隶属关系进行多边形的融合，得到边的近似v o r o n o i 图， 最后通过面线之间的转换，提取骨架线。 v o r o n o i 图方法只适合计算简单多面体的骨架，可以有效地提取线状地物骨架，但 此方法是生成线近1 9 v o r o n o i 图，近似程度受离散化结果影响很大，不适用于离散模型。 对于复杂的三维实体，理论上可以先用表面网格模型表达，然后计算v o r o n o i 图，但是 若原始物体表面太光滑，则表面多边形太小，v o r o n o i 图的计算量将十分庞大，因此 v o r o n o i 图方法的适用范围目前还比较狭窄。此类方法也便于生成多尺度骨架描述，但 是需要剪支的过程，而且规则很复杂。 1 0 中目石油大学( 华东) 硕士学位论文 2 6 基于模型分解技术 此类算法的基本思想是通过计算模型表面的桥识别模型表面的凹地，计算每个顶点 凹陷性，并对模型按照凹陷性进行分解，不断迭代该过程创建骨架。 这种方法可以提取模型骨架，但是需要计算每个顶点凹陷性，并且对模型进行分解， 这个步骤是非常困难的，相对使用的时间上的消耗也比较大。 2 7 基于r e e b 图的骨架化方法 27 1r e e b 图 r e e b 图b 1 是利用输入平面上的标量函数，对临界点的连通关系进行编码从而构造 出的拓扑结构图。r c e b 图能够较好地表达三维模型的拓扑形状，r e e b 图定义如下： 定义2 5 设bm r 是定义在紧流体m 上的一个m o r s e 函数。f 的r e e b 图是m r 中f 的商集，等价于关系( p l ，f ( p 1 ) ) ( p 2 ，f ( p 2 ) ) ，当且仅当： i f ( p ，) = f ( p ：) 1 p 】a n dp ib e l o n gl ot h es a m ec o n n e c t e dc o m p o n e n to f f 。( ，( 且) ) 图2 - 3 给出的例子是在双向环面上r e e b 图高度函数的计算，很好地阐明了r c v b 图 可作为骨架使用的事实。 国2 3 取向圆环上高度函数水平线的演让、其临界点及其r e e b 图 f i g2 - 3d o u b l e - t o r u $ o f i t sh e i g h t f u n c f i o aa n d t h e r e e b g r a p h w i t h t h ec r i t i c a lp o i n t s 由r e e b 图的定义可以看出，基于r e e b 圈的骨架算法首先要在模型上定义个连续 的映射函数用以对模型顶点进行分类，计算每个模型顶点的函数值，将具有相同函数值 的顶点聚合成一个顶点，得到模型的骨架点。 算法的基本思想是在三维模型上定义一个连续函数u ，首先计算三维模型每个顶点 的1 3 , 函数值，然后根据u 值将模型上的顶点进行分类，i 1 值相同且位于同一连通分量上 口鸯 第二章骨架提取技术概述 的点归为一类，最终得到原顶点集的一个商集。将商集中的点根据原有模型点间邻接关 系连接起来，就得到原有模型的一个骨架。 此类算法的关键是寻找一个好的u 函数，然后根据p 值对模型顶点进行分类聚合求 取骨架点，然而这也是此类算法的一大难点。 2 7 2 一种基于r e e b 图提取骨架的典型算法 该算法是在提取特征点的基础上，结合r e e b 图思想，最终实现模型骨架提取的一 种典型算法。通过分析该算法，从计算复杂度和运行时间方面提出具体改进方法，也是 在此算法思路的基础之上提出的改进算法。下面对该算法的基本思路作详细介绍。 s e t p l ：提取特征点。 特征点是位于三角网格突出区域端点位置的网格顶点。因为它们充分代表了三角网 格最显著形状的特征，所以将它们参与到映射函数的计算和原始测地线距离的计算。 提取特征点主要思想是：首先，得到三角网格模型中距离最远的两个顶点v s t 和7 s z ， 其次，计算三角网格每个顶点的数值函数厶。和六：，然后，计算g 和g z 的局部最值 作为e , 并i e 2 。最后，利用公式，= 互ne z 得到三角网格模型的特征点集合。 s t e p 2 ：计算映射函数。 在处理拓扑骨架的时候，定义映射函数是很有必要的，因为：它揭示了网格最有 意义的部分；它在图形简化过程中，不会产生更多的关键点。 。映射函数的定义如下： 厂( v ) ： 塑! 上堕盟五盟 咖v7 m a x 时l ( v ) 一m i n 惺r 丘( v ) 其中，厶是一个关于z 标准化的版本，丘有如下的定义( 工( 训 - 0 ，v v t ) ： 丘( v ) = 1 一万( v ，v 。) k 是距离v 最近的特征点： k f 脚，v c ) = r a i n e f5 ( v ，v 少) s t e p 3 ：映射函数的离散轮廓线。 建立离散轮廓线的目的是用于检测三角模型拓扑的变化或者是曲率的过渡，不需要 重新建模和参数输入，就可以提取更精细的拓扑骨架。 1 2 中国石自大学( 华东) 硕士学位论女 映射函数离散轮廓线的建立过程：在计算了三角网格每个顶点的映射函数之后，对 映射函数值进行区域分类，把具有相同函数值的顶点聚集到一类，用同一种颜色显示， 这样，在模型上就会形成离散的轮廓线。 s t e p 4 ：离散轮廓线的拓扑分析。 为了对离散轮廓线进行拓扑分析，定义了三种拓扑变化：分支、会合、终结，如图 2 4 所示： 属毳謦、自尸气鹊尹峨，厂、“、 氓一l 曩崩 l - _ 一 、一j ( a )( b 鱼鱼皇卜 ；氖i j oo 。 i 晤夏f ( d ) 图2 一拓扑变化 f i 9 2 - 4t o p o l o g yc h a n g e s 分支：当离散轮廓线的数量变化发生如图2 - 4 由( a ) 一( b ) 时，发生的拓扑变化为分 支，在求取骨架点的时候需要添加一个分支的骨架点，如图2 - 4 ( d ) 中的分支点。 会舍：当离散轮廓线的数量变化发生如图2 - 4 由( b ) 一( c ) 时，发生的拓扑变化为会 舍，在求取骨架点的时候，需要镓加一个会合的骨架点，如图2 2 4 ( d ) 中的会合点。 终结：当离散轮廓线的数量逐渐减少，并且不出现新的轮廓线时，发生的拓扑变 化为终结。 通过对3 d 模型做拓扑分析就可以得到3 d 模型的拓扑骨架。 s 卸5 ：离散轮廓线的几何分析。 拓扑分析得到的骨架较简单，通过离散轮廓线的几何分析收缩逼近的方法可以 第二章骨架提取技术概述 把骨架细分为更为精细的部分。 基本思想为：计算离散轮廓线的高斯曲率，确定局部最小值。遍历离散轮廓线，对 于取得最小值的离散轮廓线，都可以收缩逼近于每一个骨架点。 2 8 本章小结 本章首先介绍了骨架的定义，随后对当前几种主要的骨架提取方法进行了详细讨 论，就算法思想、解题思路、算法优缺点等多方面进行了分析，接着介绍了一种基于r e e b 图提取骨架算法的基本思路，我们将依据此算法的基本思路，进行下面的研究工作。 1 4 中目石目大学( 华东) 颈学论文 3 1 引言 第三章三维网格模型的特征点提取算法 骨架提取算法难以同时满足人们对准确性和运行速度两方面要求，如何保证骨架提 取准确性的同时，降低算法复杂度减少运行时间是目前研究的重点。 本课题提出基于特征点求解的r e e b 图骨架提取算法。通过提取的特征点来描述三 维网格模型的外轮廓特征，以特征点作为计算模型分支结构的依据。特征点也是模型的 骨架点，能准确地反映模型的整体空间结构，以特征点为基础进行骨架提取能够确保 提取骨架的完整性。图3 1 给出了模型特征点的示意图； _- 3 2 特征点提取技术 ( 劬模型 圈3 1 模型特征点 f 吨3 - 1f e a t u r e p o i n t s o f m o d e l 特征点已在骨架提取1 2 1 1 和三维模型分割1 等计算机图形学的多个研究领域起到重 要作用。s a g ik a t z 4 4 等人提出一种基于测地线距离的特征点提取算法，无需输入参数， 可应用于模型匹配、三维动画等方面。j u l i e nt i e m y 等人逐步对其算法进行了改进，提 高了算注的计算速度和准确度，并将算法应用于三维模型的骨架提取。 j u l i e nt i e r n y 将处于模型显著部分极端位置的顶点作为特征点并应用于骨架提取， 利用这些特征点描述模型的外轮廓特征和整体空间结构，以保证提取骨架的完整性和骨 架位置的准确性。由图3 - 2 可以看出，提取的特征点均处于三角网格模型的显著部分的 极端位置，能够清晰区分模型的外轮廓和整体空间结构，如h a n d 模型的五指和手掌， 【三i 及h a m m e r h e a d 模型的头部和尾鳍。 第三章三鞋目镕模型特征点提取算法 ( a ) h a n d ( b ) h a m m e r h e a d 图3 - 2 三维模型的特征点 f 蛸of c i n u 陀p o i n t o f 3 d m o d e l 3 2 1 相关定义 1 、三角网格模型：由三维空间中的三角形通过边和顶点相互连接而成的封闭或半 封闭线性曲面h 5 1 ( 如图3 3 所示) 。 圈3 3 三角网格模型 f i 9 3 - 33 、- i a a g u l a r m e s h m o d e l 其中每条边最多包含在两个三角形中。严格意义上，网格是一个二元组忙( k ，v ) 。 其中v = v ，v ，”，v 。) ，v 。月表示网格m 中的顶点在空间中的位置，k 是一个单纯复形，包 含顶点集i i ，2 ，m ) 及其非空子集，一个单纯复形包含