（计算机应用技术专业论文）三维模型分割及检索的方法研究.pdf

、 、 、 v 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加以标注和 致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同志的研究成果对本人的 启示和所提供的帮助，均已在论文中做了明确的声明并表示谢意。 学位论文作者签名：垄赳 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 一，一 ，一j 一 学位论文作者签名：勉蓝虹叁 指导教师签名： 签名日期： yf 1 年6 月9 日 厂 辽宁师范大学硕士学位论文 摘要 在计算机图形学的研究领域，三维网格模型分割技术和检索技术已经成为近年研究 的热门课题。随着三维扫描技术的发展和三维造型技术的成熟，三维网格模型被越来越 多的应用于3 d 数字动画、虚拟现实、真实感造型等各几何处理研究领域，并逐步代替 了传统的曲面模型，成为数字几何建模的主流模型。由此，对网格模型的研究也开始细 化到离散网格处理的各方面，其中网格分割和检索便是极具代表性的研究方向。 三维网格的分割可以有助于参数化、形状匹配、纹理映射、多分辨率建模、网格编 辑、变形、压缩、动画等。近年来，涌现出许多优秀的网格模型分割算法，如：s h a p e d i a m e t e r 方法、n o r m a l i z e dc u t s 方法、c o r ee x t r a c t i o n 方法、r a n d o m i z e dc u t s 方法等等。 每种方法都有其适用的模型，所以没有一个通用的分割算法适用于各种三维模型。三维 网格检索作为网格分割的应用之一，主要研究如何根据设计目标从大规模模型库中得到 形状特性相似的模型，从而更有效的重用和管理现有网格。 本文提出一种基于网格边界几何信息的快速分割算法，首先按照原始网格模型面片 的拓扑关系建立对偶图，并根据网格面片的几何信息设定权值，使用k - w a y 多级分割方 法对对偶图进行分割得到预分割区域以及各区域的初始边界，然后对模型进行特征轮廓 提取得到特征边界；定义边界强度函数来表示各预分割区域边界处的形变模型，通过最 小化形变模型的能量函数推动初始边界向特征边界运动，最终得到符合最小值法则的有 意义的子网格。实验结果表明该算法快速有效，适用于各种局部边缘特点较明显的三角 网格模型。 针对大规模三维模型库的模型检索效率不高的问题，本文提出一种基于增量式聚类 的三维模型检索方法。首先为模型库中的模型建立搜索关键词词典，然后根据目标模型 的特征直方图提取特征点得到特征向量，对特征点进行增量聚类，并根据增量聚类的结 果更新检索关键词词典；最后使用特征向量匹配的方法来判断出模型库中是否含有与目 标模型相关的模型。实验结果表明，该方法能够快速、准确的检索到与目标模型相关的 模型。 关键词：三维网格分割；边界强度；特征边界；三维模型检索；增量聚类 三维模型分割及检索的方法研究 3 dm e s hs e g m e n t a t i o nb a s e do nt h es t r e n g t ho f b o u n d a r y a b s t r a c t i nt h ec o m p u t e rg r a p h i c sr e s e a r c ha r e a s ，t h r e e d i m e n s i o n a lm e s hs e g m e n t a t i o na n d r e t r i e v a lt e c h n o l o g yh a sb e c o m eah o t p o t r e c e n t l y w i t l l t h ed e v e l o p m e n to ft h r e e - d i m e n s i o n a ls c a n n i n gt e c h n o l o g ya n dt h r e e - d i m e n s i o n a lm o d e l i n gt e c h n o l o g y ，3 dm e s h m o d e li si n c r e a s i n g l yu s e di n3 dd i g i t a la n i m a t i o n , v i r t i a 1r e a l i t y ，r e a l i s t i cm o d e l i n go ft h e g e o m e t r yp r o c e s s i n ga n do t h e rr e s e a r c ha r e a s g r a d u a l l y ，i tr e p l a c e st h et r a d i t i o n a ls u r f a c e m o d e l ，b e c o m et h em a i n s t r e a mm o d e lo f t h ed i g i t a lg e o m e t r i cm o d e l i n g t h u s ，t h er e s e a r c ht o t h eg r i dm o d e lb e g a nt or e f m ea l la s p e c t so ft r e a t m e n t m e s hs e g m e n t a t i o na n dr e t r i e v a l w h i c hi st h eh i g h l yr e p r e s e n t a t i v eo ft h er e s e a r c h 3 dm e s hs e g m e n t a t i o nc a nh e l pi nm a n ya s p e c t s ，s u c ha sp a r a m e t e r i z a t i o n , s h a p e m a t c h i n g ，t e x t u r em a p p i n g ，m u l t i r e s o l u t i o nm o d e l i n g ，m e s he d i t i n g ，d e f o r m a t i o n , c o m p r e s s i o n ，a n i m a t i o na n ds oo n i nr e c e n ty e a r s ，m a n ye x c e l l e n tm e s hs e g m e n t a t i o n a l g o r i t h m sa p p e a r e d t h e r ea r es h a p ed i a m e t e r ，n o r m a l i z e dc u t s ，c o r ee ) m a c t i o 玛 r a n d o m i z e dc u t sm e t h o d s ，a n ds oo n e a c hm e t h o dh a si t so w n a p p l i c a b l em o d e l ，s ot h e r e a r en os i n g l es e g m e n t a t i o ne v a l u a t i o nc r i t e r i at od e t e r m i n et h em e r i t so fv a r i o u sa l g o r i t h m s 硼m s ，3 dm e s hm o d e ls e g m e n t a t i o ne v a l u a t i o nt e c h n i q u e sw i l l a l s od e v e l o p 3 dm e s h r e t r i e v a li so l l eo ft h ea p p l i c a t i o n so fm e s hs e g m e n t a t i o n , t h em a i nd e s i g ng o a l so fw h i c ha r e h o wt og e ts i m i l a rs h a p ec h a r a c t e r i s t i c sm o d e lf r o ml a r g em o d e lb a s e t h u sr e u s ea n dm a n a g e o ft h ee 虹s t i n gg r i dm o r ee f f e c t i v e m s p a p e rp r e s e n t saf a s ts e g m e n t a t i o na l g o r i t h mb a s e do nt h e 鲥db o u n d a r yg e o m e t r y i n f o r m a t i o no ft r i a n g u l a rm e s h e s a tf i r s t , a c c o r d i n gt ot h et o p o l o g i c a lr e l a t i o no fo r i g i n a l m e s hf a c e s ，t h ea l g o r i t h ms e t sd u a lg r a p ha n dd e f a u l tw e i g h t sf o rt h em e s hf a c e sw i t h g e o m e t r yi n f o r m a t i o n u s et h ek - w a ym u l t i l e v e lp a r t i t i o n i n gm e t h o d st od i v i d et h ed u a lg r a p h o b t a i n i n gp r e s e g m e n t a t i o na r e a s a n di n i t i a l b o u n d a r yf o re a c ha r e a ，t h e ns e a r c ht h e c h a r a c t e r i s t i cc o n t o u ro ft h em o d u l et od e t e r m i n e 坊ec h a r a c t e r i s t i cb o u n d a r y 。乃eb o u n d a r y s t r e n g t hi sd e f i n e da sad e f o r m a t i o nm o d e lo ft h ed i v i d e da r e a s b o u n d a r y b ym i n i m i z i n gt h e e n e r g yf u n c t i o no ft h ed e f o r m a t i o nm o d e lt op r o m o t et h ei n i t i a lb o u n d a r ya p p r o a c ht ot h e c h a r a c t e r i s t i c b o u n d a r y e v e n t u a l l y , s p l i tt h eo r i g i n a lm o d e li n t os e v e r a lm e a n i n g f u l s u b d i v i d e dp a r t si na c c o r d a n c ew i t l lt h em i n i n l ar u l e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a to b r a l g o r i t h mi se f f i c i e n ta n de f f e c t i v e ，e s p e c i a l l yf o rav a r i e t yo ft r i a n g u l a rm e s hm o d e l sw i t h s h a r pf e a t u r e 一i i 辽宁师范大学硕士学位论文 f o rt h em o & lr e t r i e v eo fl a r g e s c a l et h r e e d i m e n s i o n a li n e 伍c i e n c y ，t h i sp a p e rp r e s e n t sa t h r e e - d i m e n s i o n a lm o d e lr e t r i e v a lm e t h o db a s e do nt h ei d e ao fi n c r e m e n t a lc l u s t e r i n g f i r s t l y ， f o rt h em o d e l sa m o n gt h em o & lb a s e ，c o n s t r u c tar e t r i e v a lw o r d sc o d e b o o k t h e ne x t r a c tt h e f e a t u r ep o i n t st oa t t a i nt h ef e a t u r ev e c t o ro fm o d e l sa c c o r d i n gt o 也ef e a t u r eh i s t o g r a m , a f t e r t h a t , f o l l o w e db ya l li n c r e m e n t a lc l u s t e r i n gm e t h o da n du l m t e r e t r i e v a lw o r d sc o d e b o o k f i n a l l y , af e a t u r ev e c t o rm a t c h i n gm e t h o di su s e dt od e t e r m i n ew h e t h e rt h em o d e lb a s e c o n t a i n 也em o d e l sw h i c hi sr e l a t i o nt ot h et a r g e tm o d e l e x p e r i m e n t a lr e s u l t ss h o w t h a to u r i m p l e m e n t a t i o nc a l lg e tm e r e t r i e v a lr e s u l tr a p i d l ya n dp r e c i s e l y k e yw o r d s ：3 dm e s hs e g m e n t a t i o n ：b o u n d a r ys t r e n g t h ：f e a t u r ee d g e ：3 dm e s h m o d e l r e t r i e v a l ：i n c r e m e n t a lc l u s t e r i n g 三维模型分割及检索的方法研究 目录 摘要i a b s t r a c t i i 1 绪论1 1 1 三维网格模型及数据形式2 1 2 本文的研究目标。5 1 2 1 三维网格分割。5 1 2 2 三维网格检索6 1 3 本文主要内容8 1 3 1 基于边界信息的分割算法8 1 3 2 增量式三维检索。8 1 4 本文章节安排。9 2 三维网格分割算法介绍及评价标准一1 0 2 1 三维网格分割算法分类l o 2 2 典型的三维网格分割算法1 0 2 2 1 基于曲率信息的分割1 0 2 2 2 二维推广到三维的分割算法11 2 2 3 基于拓扑结构图的分割算法1 2 2 3 三维网格分割算法的评价标准1 2 3 基于边界强度的三维分割1 4 3 1 预分割1 4 3 1 1 权值定义1 5 3 1 2 预分割1 6 3 2 提取特征边界1 7 3 3 后分割1 9 3 4 实验结果及分析2 0 4 基于增量式聚类的三维网格模型检索2 3 4 1 相关工作。：2 3 4 2 检索评价标准2 4 4 2 1 标准三维模型库2 4 4 2 2 三维模型检索评价准则2 5 4 3 本文检索方法2 6 辽宁师范大学硕士学位论文 4 3 1 特征提取2 6 4 3 2 增量聚类方法2 9 4 3 3 相似性匹配方法3 0 4 4 检索结果评价3 l 5 总结与展望3 5 5 1 工作总结3 5 5 2 后续研究及展望3 5 参考文献3 6 攻读硕士学位期间发表学术论文情况：4 0 致谢4 l v 一 辽宁师范大学硕士学位论文 1 绪论 随着数字时代的来临、计算机技术的高速发展，人们的生活不再停留在单纯的现实 世界，数字化、媒体化的出现满足了人们对视觉更高、更立体的追求，对数字化图形的 研究也相应而生。计算机图形学( c o m p u t e rg r a p h i c s ，c g ) 便专门对此领域进行探索， 主要研究如何利用计算机显示、生成、表示和处理图形，是一门科学严谨，却又不乏生 动形象的学科。 当前世界获取信息最直观、最丰富的手段之一便是图形，在各个主流媒体中，无论 是平面图像、还是流体视频，图形时刻出现在人们的视野中，描绘着生活中的点点滴滴。 图形通常由点、线、面、体等几何元素以及线型、线宽、颜色、纹理等非几何属性描述。 作为图形学中的基本元素，不同的研究领域需要不同特性的图形。从生成技术的角度来 看，图形主要有两类：一类是单纯基于线条信息表示的，例如曲面的线框图、工程图、 等高线地图等；另一类则是复杂的真实感图形。生成真实感图形的首要任务，必须要建 立画面场景的几何表达方式，再使用各种光照模型，并计算场景在假想光源、材质、纹 理属性下的光照效果【l 】。 三维模型是真实感图形中的实体模型，各种类的模型经过光照、材质、纹理等属性 的加载后，创建并构成了人们视觉所见的物体以及基本场景。三维建模的方式多种多样， 目前主流的三维建模方式是从大规模的点云模型重建为离散三维网格，之后再对模型进 行细节的加工处理。伴随着计算机视觉技术和三维数据采集技术的发展，三维点云模型 可以通过激光扫描仪等采集设备从手工模型直接获得。经过处理变成由多边形面片组成 的三维模型，这些模型在快速模型制造、图形显示、有限元分析、图形变换等方面优势 显著，并且在表示对复杂的曲面模型的逼近效果突出，常被用于计算机辅助设计、几何 造型、图形学三维动画、网络游戏、影视制作、计算机仿真等工作中，用途广泛。 由于给人们提供了一种直观的信息交流的工具，计算机图形学已被广泛的应用于各 个不同的领域，无论是引人入胜的广告，电影特技的制作，生产过程及科研的模拟，还 是游戏的开发、计算机辅助教育等，都让应用程序更加形象生动，增添了多媒体的感官 效果。三维立体电影便是计算机图形学的重要应用之一，红极一时的3 d 巨制阿凡达 中生动的亚美人的形象便是通过三维建模而成，首先利用三维激光扫描仪对真人进行采 样，然后利用计算机对采样的模型进行细节加工，最后绘制出的动画便是人们在影片中 观赏到的。惟妙惟肖的3 d 技术将好莱坞导演丰富的想象力淋漓尽致地呈现在观众眼前 ( 如图1 1 ) 。 三维模型分割及检索的方法研究 图1 1电影“阿凡达”中人物模型的建模 f i g 1 1 c h a r a c t e rm o d e l i n gi nt h em o v i e a v a t a r 为了满足各种不同的应用需求，对三维模型的研究处理也得到了飞速的发展，其重 点研究问题主要包括：数据获取、参数化、曲面拟合、几何属性估计、光顺去噪、几何 修复、网格简化、形状插值、数字水印、压缩、动画、纹理合成、分割、绘制等。其中， 如何对大规模模型进行快速有效的分割以及如何从大规模模型数据库中检索到目标模 型，即三维模型的分割和检索，一直是研究人员关注的一个热点研究内容【1 1 。 1 1 三维网格模型及数据形式 三维网格模型是三维建模中较常使用的一类模型，通过描述对象边界的点、线、面 来创建模型，是信息完整并且二义性较小的模型类别。三维网格模型是由众多点云组 成的，点云所含信息包括三维坐标( x ，y ，z ) 、颜色信息( r g b ) ，材质，光反射 强度等，所有信息叠加，最终绘成网格。通常，网格模型由三角形、普通四边形或 者简单的凸多边形组成，网格越简单，越有利于简化渲染过程。另外，网格模型不 一定是闭合的，也可以由带有空洞的普通多边形构成，这样可以使网格模型更接近 真实物体。当然，虽然网格模型模拟的是物理自然界的东西，但模拟的物体既可以 是现实世界的实体，也可以是虚构的物体，既可以小到分子或原子，也可以是很庞 大的尺寸。模拟得到的物体一般通过计算机或者具有视频显示功能的设备显示。 与传统曲面模型相比，网格模型具有以下优点：( 1 ) 多边形网格的形状表达 简单，便于整体计算和全局处理；( 2 ) 多边型网格能够任意精度地逼近任何曲面 物体，并且可以表示拓扑结构十分复杂的物体；( 3 ) 要表达相关物体的几何信息， 只需要存储每个多边形的顶点及其属性即可；( 4 ) 在计算多边形网格内的任一可 见点信息时，可以由所包含顶点的信息插值得到，这种处理方式使得对多边形网格 的绘制能够采用硬件加速技术来实现。以h a n d 模型为例，网格模型如图1 2 所示。 一2 一 辽宁师范大学硕士学位论文 图1 2h a n d 的点云模型、网格模型、面片渲染模型 f i g 1 2 k i n d so f h a n dm o d e l ：p o i mc l o u dm o d e l ，m e s hm o d e la n dr e n d e r i n gm o d e l 网格模型有多种表达格式，不同的文件格式的模型所包含的信息内容各异，为了方 便操作，本文主要使用的网格模型格式是o b j 和o f f 模型。这两种模型格式都是由顶 点和三角面片组成的，具体文件格式如下： o f f 文件格式：o f f 文件是表示模型的最简单的a s c i i 文件，它包含最少但足够传 达模型绘制所必需的几何信息量。不需要任何文件头( f i l eh e a d e r ) ，每个文件第一行都 以o f f 关键字作为起始，第二行包含模型的顶点数a 、面片数b 、边数c ，边数c 一般 可以忽略。接下来的a 行为顶点的坐标信息，每个顶点占据一行，含有三个数据：x 、y 、 z 分别表示顶点相对于x 、y 、z 轴的坐标。最后的b 行，包含组成各面片的顶点索引， 若为三角面片，则以3 打头，其后为顶点索引。最小的顶点索引值从0 开始计算，依次 递加。 o b j 文件格式：o b j 文件同样不需要文件头，只使用几行文件信息的注释作为 开头，通常以符号“群 作为注释行的开头，接下来的文本格式用以下形式表示： 信息关键字参数1 、参数2 、参数3 其中，关键字标识该行所存储的信息类型，参数表示具体的信息值。与o f f 文件 相似，o b j 文件包含了顶点信息和面片所含的顶点索引，但是比之增加了法线、纹理坐 标和材质等信息。其主要的关键字如下表： 三维模型分割及检索的方法研究 表1 1o b j 文件的主要关键字及信息 t a b 1 1 k e y w o r da n di n f o r m a t i o n o fo b jf i l e 关键字 具体参数及含义 顶点( g e o m e t r i cv e r t i c e s ) ，含有三个单精度浮点数x 、y 、z ，分别表示 v 本行指定顶点的坐标信息。 顶点法线( v e r t i c e sn o r m a l s ) ，含有三个单精度浮点数x 、y 、z ，分别表 v n 示指定该行顶点的法线向量。 顶点纹理( v e r t i c e st e x t u r e ) ，含有两个单精度浮点数u 、v ，分别表示该 ” 行顶点指示的纹理坐标值。 面片( f a c c ) ，由n 边形组成的面片则每行包含n 个顶点索引值。索引值 f 从l 开始计算。 材质库( m a t e r i a ll i b r a r y ) ，表示该o b j 文件所使用的材料库文件( m n ) m t l h b 的文件路径。 材质名称( m a t e r i a ln a m e ) ，表示该行到下一个u s e m t l 起始的行之间的 璐即m所有面片使用的材质名称。具体的材质信息存储在该o b j 文件所附属的 m t l 文件中。 以模型d i n o p e t 为例，网格模型以及o f f 和o b j 文件格式( 如图1 3 所示) i m j e n 扣哺缔忏 v0 9 5 0 9 8 一口5 6 5 9 8 s - 0 5 7 7 0 0 2 ， v0 9 5 5 4 2 b - 0 5 6 1 6 3 7 0 5 7 7 2 i 9 v0 9 6 9 0 7 4 0 5 竹8 h _ o s s 5 2 8 3 v a 0 8 5 研一0 9 5 3 1 2 争1 e e 5 l ，川0 9 6 s ，4 - 0 9 5 3 9 0 i b 8 0 4 9 1 ” _ ，0 0 e 1 7 6 2 - 4 ) 9 6 5 5 5 61 5 0 埘 ，一0 s ( m ；6 1 40 5 2 9 2 0 4 0 0 4 0 c o l v 0 3 0 3 11 口，- 0 3 8 0 0 8 4 v 一0 e 卯l - 0 戢f 1 5 9 6 - 0 1 挪 5 v e r t t c t e z，21 f 65 fz z 1 1l o 霉1 5 1 网格模型o f f 文件格式 o b j 文件格式 图1 3d i n o p e t 的网格模型以及o f f 、o b j 文件表示 f i g 1 3 o f fa n do b jf i l eo ft h em o d e ld i n o p e t 一4 一 辽宁师范大学硕士学位论文 三维模型除以上两种格式的文件表示以外，还有s t l 格式，v r m l 格式、w 3 d 格 式等，不同的格式还可以通过软件进行转化，转化后的模型同样具有很强的可操作性。 1 2 本文的研究目标 本文主要围绕三维模型的分割和检索技术展开研究，三维模型的分割和检索都是计 算机图形学领域的热点问题，但现有分割方法对普遍模型的适用度较差，本文对三维模 型的顶点属性特征进行探讨，并根据模型的属性特征，提出了可以适应更多种类模型的 新的分割方法。并且，现有的模型检索工作中，对大规模三维模型库的检索存在耗时较 长、检索效率不高的问题，本文也就此问题提出增量式聚类的方法，可以提高模型检索 的效率和准确率。 1 2 1 三维网格分割 三维网格分割，是指根据一定的规则及模型自身的结构特征，将封闭的多面体网格， 依据其网格表面的几何或拓扑特性，分解为一系列数目有限、各自具有连通性的子网格 片的工作，分割后得到的各个部分再合并仍然是整个模型，并且各个分割部分的面片交 集为空，另外，每个子部分各自具有其简单的意义。若离散的表示，则对于原始三维网 格模型m 的分割定义如下： 设模型s 是含有拧个顶点的三维多边形网格模型，两，& ，& 是s 的聊个子分割 部分，则要满足如下条件： ( 1 ) v f ，1 f k ，cs ； ( 2 ) v i ，- 混连通的； ( 3 ) u ：。& = s ； ( v i , j ，f j ，1 f ，j k ，& 和s 的交集只含有顶点或边，不含面片； 得到的满足以上几何意义的分割结果( 如图1 4 所示) ，各个分割部分连通性良好， 并且符合人类视觉中有意义的分割： 旁 图1 4h a n d 网格模型的分割结果 f 噜1 4s e g m e n t a t i o no f m o d e lh a n d 一5 一 三维模型分割及检索的方法研究 三维网格分割在许多应用领域起着至关重要的作用，网格分割己成为计算机图形学 一个重要且具有挑战性的问题。目前现有的具有较高影响的算法概述如下： 三维网格模型的分割方法最早从二维图像分割方法演变而来。1 9 9 1 年，v i n c e n t 等 人将图像处理中的分水岭方法推广到三维模型的分割问题上，二维图像分割方法向三维 网格分割工作的过渡由此展开，但分割边界含有较多的锯齿团；1 9 9 5 年，h e b e r t 等人将 图像分割中经典的区域增长算法应用到三维空间，为三维网格分割工作拓展了新的思路 3 1 。由于自动分割算法存在分割边缘不精确，过分割等问题，因此，1 9 9 6 年，k r i s h n a m u r t h y 等人在研究三维网格动画的变形过程中，提出了交互式分割的方法。交互式分割的方法 由于人为的参与，可以使分割的边缘更光滑，分割结果更接近人眼视觉的判断标准 4 1 。 2 0 0 0 年，r o s s l 等提出通过分割骨架达到分割模型的目的，研究过程先获得没有噪声区 域骨架，然后对骨架进行分割操作，最终映射回原模型，得到模型的各分割部分【习。2 0 0 2 年，l e v y 等结合了法向量、区域增长和d i j k s t r a 最短距离算法，在实现纹理生成工作中 同时，完成了三维网格模型的分割。三维网格分割算法针对不同的模型，有不同的适用 范围，通常没有一种分割算法对于所有的模型都适用 0 3 。2 0 0 4 年，gl a v o u 6 等提出了专 门针对c a d 模型的方法，该方法基于对曲率张量的分析，可以得到几个连续的区域分 割片【7 】。三维网格分割工作中，分割边缘的属性判断是难点，t s u z u k i 等人于2 0 0 5 年提 出一种通过比较两相邻三角面片法向量的夹角的方法，完成了三维网格模型的自动分割 【引。同年，s a g ik a t z 等提出一种使用模糊聚类的分层网格分割方法，该方法较好的解决 了过分割和锯齿边界的问题，并将分割成功应用到骨架提取工作中【9 1 。2 0 0 8 年，y u - k u n l a i 等结合图像分割中随机游走的方法，得到一种高效快速的分割方法，对噪声有较好 的鲁棒性，并提供了交互分割和自动分割两种方式，以满足不同的工程需要【l o 】。 1 2 2 三维网格检索 随着三维建模技术的日新月异，三维网格模型的逼真度越来越高，应用也越来越广 泛，为了充分发挥已有模型资源的优势，降低重新设计模型带来的繁冗的工作量，模型 检索的想法相应而出。如何根据从庞大的模型库中检索出相应的模型，以及如何根据已 有模型搜寻到与之相似或匹配的模型，成为检索工作的首要目标。 最早的检索相关工作要追溯至1 j 1 9 9 8 年，p a q u e t 1 1 】等首先提出基于内容的三维模型特 征描述算子，之后，国内外大量科研工作者继续在此领域进行探索，先后涌现出许多三 维模型特征描述算法，并且开发出一系列的三维模型检索系统。同时，检索也不单针对 单一模型进行，2 0 0 2 年，z u c k e r b e r g e 1 2 】等研究出根据模型局部几何拓扑性进行形状检 索的思路，发表了基于分割的检索结果( 如图1 5 ) 。 辽宁师范大学硕士学位论文 麓44趣 斑 一一 1 由 0 5 5 3n 5旬? | 7 7俄j 2 1母，2 氨 l 祭静砖带蜉 一 j 由 嘣a ，矗5a 饥，l ，o 2 9 5 遭秽 盛碧譬 l 羽 ；n 螂让粥l i j 孙l j i j0 3 熊l 妖吱 菱 凳黔 l 砌0 7 5o 掰q 0 ，n 2 ，诧2 0 6 誓i j，。， 踟 渺留 j 脚u 7 5a 舅5 3 5l l 5 i住弭 图1 5 基于分割的模型检索结果 f i g 1 5 r e t r i e v e dr e s u l t so f m o d e lb a s e do ns e g m e n t a t i o n s h l a f m a n 等人于2 0 0 2 年将检索、变形、简化应用于3 8 8 个三维网格模型的数据库 上，首先将三维网格模型分割成几个有意义的分割区域，然后对每一个分割区域的形状 进行评价，并确定他们之间的关系，之后建立各个模型分割区域的属性图，以得到与原 模型之间的相关性【1 3 1 。该方法在进行相似性度量的时候，只需要比较属性图的相似度即 可。三维模型检测的难点在于特征的提取，如何得到具有唯一标识行的特征属性成为特 征提取中最首要解决的问题，针对此问题，k o b b e l t 等人尝试从椭球集合中得到统计特 征提取的方法，采用椭球半径的标准方差或者平均方差以及这两种方差之比作为椭球的 统计特征【1 4 1 。这种统计特征在不同的形状修改中保持不变，虽然可以作为检索的特征描 述，但没有严格的理论或者实验证明此方法的正确性。2 0 0 3 年，d e y 等利用基于网格模 型的拓扑信息，提出了动力学系统的形状特征描述，并采用离散网格特征来模拟连续形 状。该方法可以十分有效地分割二维和三维形状特征，并且可以得到基于该特征分割方 法的形状匹配方法【l 纠。2 0 0 5 年，y e hj 等人通过匹配可视化相似度，开发了有关三维蛋 白质结构的检索系统【1 6 】。2 0 0 7 年，w o n g 等人提出了针对三维头颅模型的三维检索方法， 该方法根据可视化面片的不同来进行检索【l 刀。 三维模型分割及检索的方法研究 1 3 本文主要内容 1 3 1 基于边界信息的分割算法 基于区域特性的分割方法如聚类分割方法等容易造成区域的过分割问题，而基于边 界分割线的分割方法，会产生不完整的边界，需要对边界进行修补后再进行分割，并且 往往具有较大的运算量，不适宜用于大规模网格模型的分割。本文将聚类分割法和基于 边界分割线的方法相结合，首先应用聚类法预分割得到闭合的区域边界，之后提取模型 的特征边界，并且在区域边界上构建形变轮廓，令其在边界强度函数的推动下向特征边 界运动，当边界强度函数最小时到达特征边界，得到区域分割的结果。具体内容如下： ( 1 ) 根据三角面片上的顶点曲率以及相邻面片之间的二面角信息为三角面片定义权 值，使用基于超大规模网格的k w a y 多级分割法【1 8 】对网格模型进行预分割。预分割得到 的区域边界不理想，在后分割中将进行边界调整。 ( 2 ) 对于需要调整边界的模型，得到其平均曲率的直方图，之后使用直方图凹凸性 分析的方法确定曲率阈值，通过阈值对模型顶点进行分类，分类后得到由顶点构造成的 特征边界。 ( 3 ) 为初始边界定义边界强度函数表示各预分割区域边界处的形变模型。边界强度 函数包括内部轮廓推动力函数和特征轮廓约束力函数两部分，具体定义将在后分割部分 进行详细描述。 ( 4 ) 通过最小化形变模型的能量函数推动区域初始边界向特征边界运动，当能量函 数达到最小时，轮廓运动停止，得到最终的网格分割结果。 1 3 2 增量式三维检索 基于内容的三维模型检索主要分为三个步骤：提取特征、特征匹配和相似性度量。 其中，特征提取是检索工作的关键。在对模型平均曲率分布直方图的研究中，提出使用 直方图分析方法确定特征向量的方法，对曲率分布呈现单峰和双峰的模型设定统一维数 的特征向量。对于模型库中的模型和目标模型以同样的方式提取特征向量，然后应用增 量聚类的方法建立模型库的检索关键字词典，根据目标模型的关键字进行相似性匹配， 相似度越大的模型即为与目标模型的相关的模型。详细的方法步骤如下： ( 1 ) 对数据库模型进行平均曲率分布的直方图判断，以得到各模型的特征向量。通 过特征向量聚类生成检索关键字词典。 一8 一 辽宁师范大学硕士学位论文 ( 2 ) 对于要匹配的目标模型，同样使用曲率直方图方法获得该模型的特征向量。然 后判断该特征向量是否符合某个类的关键词，若符合则归属到该类，若都不符合，则修 改关键字词典，将模型加入到新的类。 ( 3 ) 在目标模型所属的关键字类中，根据其特征向量，依次对该类中其他模型进行 相似性匹配，匹配度较高的模型则属于与该模型相关的模型。 1 4 本文章节安排 本文具体的内容结构安排如下： 第一章绪论，阐述了本文的研究目标三维网格模型分割以及三维模型检索，探 讨研究方法的背景与意义，并介绍了相关的研究工作和文章的结构安排。 第二章三维网格分割算法的介绍及评价标准，论述了三维网格模型分割的发展历 程，并介绍了目前具有代表意义的三维分割算法，以及这些算法的优缺点。并且介绍了 分割算法的评价准则，其中，较为公认的是人类视觉准则中的m i n i m a lr u l e ，该章对这一 准则进行了较完整的描述。 第三章基于边界强度的分割算法。本文提出的基于边界强度的分割算法，概念来源 于二维图像分割，该章节具体详尽的描述了如何构造边界强度函数，以及如何判断函数 运动边缘线，并使用多组对比实验结果论证了本文算法的可行性和有效性。 第四章三维网格模型检索介绍以及本文的检索方法。模型检索作为模型分割的应用 之一，许多检索算法都是由部分分割结果转化而来。但是本文的检索方法，为了达到较 快的检索速度和较好的检索结果，从模型整体进行定位，对模型进行整体的特征描述， 提取能表达模型整体特点的特征向量，并结合增量聚类的思想进行检索，大大提高了检 索效率。 第五章总结与展望。对论文工作的总结归纳，并提出进一步研究的前景以及方向。 一9 一 三维模型分割及检索的方法研究 2 三维网格分割算法介绍及评价标准 2 1 三维网格分割算法分类 最早期的分割算法大多是手工或是半自动的分割，近几年的研究多倾向为自动分 割，并取得了较理想的分割结果。另外，根据不同的着眼点分割算法有不同的分类方式， 首先，根据构造模型的网格的规则与否，可将三维网格模型分割算法划分为规则的网格 分割、半规则的网格分割和任意结构的网格分割三类；根据模型的分割结果，可以将分 割分为有意义的分割和无意义的分割两类( 如图2 1 所示) ；不同的分割目标和不同的应 用领域决定其分为：基于p a t c h - t y p e ( 各特征部分) 的分割算法和基于p a r t - t y p e ( 部分 面片) 的分割算法( 如图2 2 所示) 。 缈秒蚤矽 图2 1 有意义的分割 f i g 2 1m e a m g r u ls e g m e n t a t i o n 图2 2 基于p a t c h - t y p e 的分割和p a r t - t y p e 的分割 f i g 2 2s e g m e n t a t i o nb a s e do np a t c h - t y p ea n dp a r t - t y p e 2 2 典型的三维网格分割算法 2 2 1 基于曲率信息的分割 曲率是最早被用作判断网格分割边界的信息，1 9 9 2 年，f a l c i d i e n o 等对曲率进行研究 辽宁师范