（计算机应用技术专业论文）三维网格模型分割及其在检索中的应用.pdf

三维阐格模型分割及其红检索中的应用 摘要 随着三维扫描技术和计算机图形学的发展以及三维模型数量的快速增加，三维网格 模型分割技术已经成为近年来的一个热门的研究课题，并被广泛地应用于计算机图形学 的许多领域中，如：计算机动画、三维变形、网格压缩、纹理映射等。但目前该技术仍 然存在很大的挑战：( 1 ) 没有统一的三维网格分割技术的评价标准。近年来，为了模仿 人类视觉感知，多数研究者追求有意义的分割。然而，人类的视觉感知又是错综复杂的； 此外，没有统一的分割模型，不同的分割算法选用各自的分割模型，不能直观的比较分 割结果；这些都使得有意义的分割具有很大的主观性。符合人类视觉感知的有意义的三 维网格分割算法仍是一个难题。 ( 2 ) 基于语义的分割算法。得到基于语义的分割结果， 而不仅仅得到模型的某个部分( 例如；腿、胳膊等) 。( 3 ) 三维网格分割技术的应用领域。 寻找网格分割技术的应用领域，解决具体的应用问题。不同的分割算法适合不同的应用， 根据现有的算法，寻找相应的应用领域也是一个挑战性的问题。 本文围绕三维网格分割技术展开研究，主要针对三维网格分割算法的应用领域，结 合三维网格模型的检索技术所存在的问题，提出一种新的基于交互式分割的部分模型检 索方法。现有的检索技术还主要是针对于单个模型之间的比较，而在模型设计、形状修 复等应用领域中通常只需要模型的某个部分。如何从相似或不同种类的模型中检索出模 型的某个特殊的组成部分，仍然是一个难题。基于特征统计的方法虽然得到较好的检索 结果，但是不满足局部匹配，因而无法实现局部的检索；基于骨架提取和基于图的方法， 虽然满足局部的匹配，但是对三维模型的结构要求比较严格。由此，本文提出了基于交 互式分割的部分模型检索方法。首先采用交互式的分割方法，得到满足用户需求的部分 模型，将这些部分模型组织成一个小型的部分模型库；然后利用改进的形状分布方法提 取部分模型的形状特征，得到模型的局部匹配：最后，利用p d f 一厶标准得到部分模型之 间的匹配度，从而实现部分模型的检索。实验结果表明，我们得到较好的检索结果。 关键字：三维网格分割、特征提取、相似性度量、部分模型检索 三维网格模型分割及其在检索中的应用 a b s t r a c t i nr e c e n t y e a r s ，w i t ht h er a p i dd e v e l o p m e n to ft h et h r e e d i m e n s i o n a l s c a n n i n g t e c h n o l o g ya n dc o m p u t e rg r a p h i c s ，a u sw e l la st h ei n c r e a s i n go ft h r e e d i m e n s i o n a lm o d e l 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 nt e c h n o l o g yh a sb e c o m ea na c t i v ef i e l do fr e s e a r c ha n d w a sw i d e l yu s e di nm a n ya r e a so fc o m p u t e rg r a p h i c s h o w e v e r , t h et e c h n o l o g ys t i l lh a sal o t o fc h a l l e n g e s ：( 1 ) t h e r ei sn ou n i f o r mc r i t e r i o no ft 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 n t e c h n o l o g y i nr e c e n ty e a r s ，i no r d e rt oi m i t a t et h eh u m a nv i s u a lp e r c e p t i o n ，m o s tr e s e a r c h e r s p u r s u eam e a n i n g f u ls e g m e n t a t i o nr e s u l t h o w e v e r , h u m a nv i s u a lp e r c e p t i o ni sc o m p l e x ；i n a d d i t i o n ，t h e r ea r en ou n i f o r ms e g m e n t a t i o nm o d e l s ，d i f f e r e n ts e g m e n t a t i o na l g o r i t h r n ss e l e c t t h er e s p e c t i v em o d e l s ，w h i c hc a nn o td i r e c t l yc o m p a r et h es e g m e n t a t i o nr e s u l t s ，m a k i n ga m e a n i n g f u ls e g m e n t a t i o nr e s u l ti sv e r ys u b je c t i v e t h ea t t e m p tt oi m i t a t eh u m a nv i s u a l p e r c e p t i o n t o g e tm e a n i n g f u ls e g m e n t a t i o ni ss t i l lap r o b l e m ( 2 ) s e m a n t i c - b a s e d s e g m e n t a t i o na l g o r i t h m g e tt h es e g m e n t a t i o nr e s u l t sb a s e ds e m a n t i c ，r a t h e rt h a nb eap a r to f am o d e l ( s u c ha s ：l e g s ，a r m s ，e t c ) ( 3 ) f i n dt 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 nt e c h n o l o g y a p p l i c a t i o n s ，t os o l v es p e c i f i ca p p l i c a t i o np r o b l e m s d i f f e r e n ts e g m e n t a t i o na l g o r i t h m sa r e s u i t a b l ef o rd i f f e r e n ta p p l i c a t i o n s ，i na c c o r d a n c ew i t ht h ee x i s t i n ga l g o r i t h m s ，t of i n dt h e a p p r o p r i a t ea p p l i c a t i o ni sa l s oac h a l l e n g e i nt h i sp a p e r ，w es t u d ya r o u n dt h et 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 n ，p r i m a r i l ya b o u t t h ea p p l i c a t i o na r e a so ft h et h r e e - d i m e n s i o n a ls e g m e n t a t i o na l g o r i t h m ，an e ws u b - p a r t s r e t r i e v a lm e t h o db a s e da ni n t e r a c t i v es e g m e n t a t i o na l g o r i t h mi s p r o p o s e d e x i s t i n gr e t r i e v a l t e c h n o l o g ya l s oi sa i m e da tac o m p a r i s o nb e t w e e ns i n l g l em o d e l s w h i l ei nm o d e ld e s i g n , s h a p er e s t o r a t i o na p p l i c a t i o n so f t e nn e e dt oo n l yap a r t i c u l a rp a r to fm o d e l s m o r e o v e r ， s e a r c h i n gf o ras p e c i f i cp a r ti n s i d ea3 dm o d e li se v e nm o r ec h a l l e n g i n g n l em e t h o db a s e d s t a t i s t i e sc a l lg e tb e t t e rs e a r c hr e s u l t s ，b u td o e sn o ts u p p o r tp a r t i n w h o l eq u e r i e sa n d p a r t i a l m a t c h e s ；s k e l e t o ne x t r a c t i o na n dg r a p h b a s e dm e t h o d s ，a l t h o u g ht os u p p o r tp a r t i a lm a t c h e s ， h a v em o r es t r i n g e n tr e q u i r e m e n t sa b o u tt h es t r u c t u r eo ft h r e e d i m e n s i o n a lm o d e l s 砀u s 。w e p r e s e n tam e t h o dt h a t f i n d s a n a l o 百e sa m o n gp a r t so ft h r e e d i m e n s i o n a lm o d e l sb y s e g m e n t i n gt h e ma n dc r e a t i n gas i g n a t u r ef o re a c hp a r t t of i n da n a l o g i e sw ef i r s tp a r t i t i o na l l o b j e c t smad a t a b a s ei n t op a r t sb ya l li n t e r a c t i v es e g m e n t a t i o nm e t h o d t h e s ep a r t so ft h e m o d e l sw i l lb eo r g a n i z e di n t oas m a l ld a t a b a s e ；n e x t w ec a nr e t r i e v et h em o s ts i m i l a rp a r t s f r o ma 1 1m o d e l si nt h ed a t a b a s eb a s e do ns h a p ed i s t r i b u t i o nm e t h o da n dt h ep d f - l ，c r i t e r i o n 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 tw eg e tb e t t e rs e a r c hr e s u l t s k e y w o r d s ：3 dm e s hs e g m e n t a t i o n ；f e a t u r ee x t r a c t i o n ；s i m i l a r i t ym e a s u r e s ；s u b p a r t sr e t r i e v a l i l 三维网格模型分割及其在检索中的应用 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特 别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其 他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做了明确的声明并表示 谢意。 学位论文作者签名： 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名： 宝亟塑：一 指导教师签名 签名日期：2 0 0 9 年5 月1 2 三维网格模型分割及其在检索中的应用 1 序言 1 1 研究背景和意义 人眼对物体的感知是立体的，三维的模型和场景能够给人们带来更加形象逼真的感 知细节。近年来，三维模型越来越吸引众多研究者的注意，主要原因：( 1 ) 互联网技术 的发展使三维模型被广泛的传播。( 2 ) 日益更新的三维建模软件使得三维模型的设计变 得快速、简单。( 3 ) 三维扫描设备使得三维模型的获取变得可行、容易。( 4 ) 设计思路 发生了变化，以前设计时考虑如何构造三维模型；现在则考虑如何利用现有模型构造出 新的模型。这种基于模型的设计使模型的设计变得容易、快速。( 5 ) 三维模型的应用越 来越广泛，虚拟现实、三维游戏、工业产品设计、游戏教育、影视动画等应用领域中都 在越来越多的使用三维模型。 目前有数以兆计的三维模型存在，而且每天都有大量的三维模型产生和传播，存在 着快速寻找并应用现有模型的迫切需求。三维模型的分割问题也由此被提出。1 9 9 1 年， v i c e n t 等人 1 较早地提出三维网格模型的分割，他们将图像处理中的分水岭方法推广到 三维网格模型的分割问题上。三维网格模型分割技术逐渐成为一个热门研究课题，并且 在很多领域都得到了广泛的应用：三维建模、几何变形、几何压缩与传输、网格简化、 碰撞检测、纹理映射、骨骼提取等等。另外，三维网格模型所拥有的局部几何拓扑显著 性也是对三维网格模型进行检索的一种有效的索引。 三维网格分割在许多应用领域起着至关重要的作用，网格分割己成为计算机图形学 一个重要且具有挑战性的问题。许多网格分割算法被纷纷提出，典型的分割算法有：区 域增长算法、分水岭算法、聚类算法、基于关键点的分割算法等。但由于没有统一的评 价标准，很难评价不同分割算法性能的好坏。近年来，多数分割算法都追求产生有意义 的分割结果，为了得到符合人类感知的有意义的分割，提出交互式的分割算法。l i u 等 人 2 和w u 等人 3 】分别提出基于s k e t c h 的交互式分割算法，h u 等人【4 提出基于关键点 的交互式分割算法。而z u k e r b e r g e r 等人 5 n s a 为分割算法性能的好坏与其应用有着直 接的联系。目前尚没有满足所有应用的分割算法，大多数算法都是针对具体问题而提出 的。寻找网格分割的具体应用领域，并验证分割算法的好坏，仍然是一个比较困难的问 题。 在三维模型数据库中检索具有某种局部形状特征的三维模型，成为一个新的需求， 如在形状修复、模型设计等应用中，而现有的检索技术还主要是单个模型之间的检索。 三维模型的局部几何拓扑显著性，是一种有效的形状索引。有效的三维模型分割，不仅 可以满足上述的需求，而且极大地促进三维模型的检索和处理效果。 三维网格模型分割及其在检索中的应用 1 2 本文的研究工作 本文围绕三维模型分割技术展开研究，主要针对三维模型分割算法的应用领域。目 前现有的检索技术主要还是针对单个模型之间的比较，而在模型设计、形状修复等应用 中通常只需要模型的某个部分。如何从相似或不同种类的模型中检索出模型的某个特殊 的组成部分，仍然是一个难题。本文利用交互式分割框架，得到部分模型并建立部分模 型库，最终得到部分模型之间的检索。主要工作如下： ( 1 )三维网格模型的读写以及数据结构的提取： 为了便于对三维数据的处理，本文总结了常见的三维数据的文件格式以及对这些文 件的读写操作，并提取出三维模型数据的存储结构。为对三维模型的后续操作奠定了基 础。 ( 2 )利用交互式分割框架分割，得到独立的部分模型； 为了得到部分模型，本文采用交互式的分割算法将模型进行分割。首先交互的得到 分割结果，然后重新建立部分模型的索引信息( 三角片的顶点索引) ，最后以o f f 文件 格式将部分模型输出，形成独立的部分模型文件。 ( 3 )建立部分模型库； 将得到的部分模型，组织成一个小型的部分模型库，以便于在这个小型的模型库中 进行部分模型的检索。并且本文以原模型名加部分模型名的形式命名部分模型，建立原 模型与部分模型之间的联系。 ( 4 )对部分模型进行形状特征提取； 本文采用d 2 形分布方法，对部分模型特征提取。并对d 2 形分布方法做了改进，为 了快速准确的找到三角片的索引，本文直接在零到三角片总数之间生成随机数，得到三 角片的索引。然后，在该三角形内部生成随即点，形成随机点云模型。再计算随机点对 之间的欧式距离。最后统计落在每个单元内的距离个数，得到离散的概率分布，即为部 分模型的形状特征。 ( 5 )对提取的特征进行相似性度量； 为了比较模型之间的相似度，对提取的形状特征进行相似性度量。首先对得到的形 状分布曲线进行归一化处理，本文采用最大距离归一化处理，然后利用助卜，标准，对 形状特征曲线进行相似性比较，得到模型之间的相似度。 ( 6 )检索结果与分析。 得到本文的实验结果，并对其进行分析。本文对于模型的结构没有特殊的要求，对 于非封闭的部分模型，仍可以得到很好的检索结果。 1 3 本文的结构安排 本文各章节的内容安排如下： 2 三维网格模型分割及其在检索中的应用 第一章绪论。论述了本文的研究背景与意义。介绍了本文的主要工作及结构安排。 第二章三维网格分割算法。首先，论述了三维模型分割的相关概念、评价标准以 及其发展和三维网格分割的分类。然后，介绍了典型的三维网格分割算法，并对这些算 法所采用的标准和特征进行了总结。最后，介绍三维网格分割的应用。 第三章三维网格模型。首先，介绍了常用的三维网格数据的文件格式，以及文件 格式之间的转化。其次，介绍三维网格的数据结构，如何存储网格模型的几何和拓扑信 息。最后，实现三维网格文件的读取以及数据结构的建立。为后续对三维模型的操作奠 定了基础。 第四章交互式三维网格分割算法。本文实现了交互式网格分割算法，首先，大致 画出两条分割曲线( s k e t c h ) 的位置，其中一条曲线表示想要分割的部分( 鼠标左键拖动) ， 另一条表示选择分割的背景区域( 鼠标右键拖动) 。然后，采用改进的区域增长法分割 得到部分模型。我们在p s b 模型库中选取了7 0 个模型，分割成6 6 8 个部分模型。 第五章分割在检索中的应用。首先，建立部分模型库，并采用命名的原则建立部 分模型与原模型之间的索引。然后，采用改进的形分布方法对部分模型进行形状特征提 取，对提取的特征曲线进行相似性度量。最后，得到部分模型的检索结果，并对结果进 行分析。 第六章工作总结与展望。对整个论文主要工作和成果的进行了总结，并对进一步 的研究进行了展望。 3 三维月格模型分割凰其在檎索中的应用 2 1 三维同格分割概述 2 三维网格分割算法 2 i 1 三堆嘲格分割的相关概忿 三维网格模型分割( 简称网格分割) ，是指根据一定的几何及拓扑特征，将封闭的掰 格多面体或者可定向的二维流形，依据其表面几何、拓扑特征，分解为一组数目有限、各 自具有简单形状意义的、且各自连通的子网格片的工作 6 ，如图2 1 。 誉_ f 圈21 三维网格模型分割 令s 为网格的顶点集、边集、或面片集。对于网格模型盯的分割定义：将s 分成的 k 个不相交的子集。即： ( 1 ) u s , = 卫s c s ； ( 2 ) s n s ，= ，l ，= l k ， i ，。 网格模型对偶图，是指用图的结点表示网格模型中的多边形面片( 我们只考虑三角 形面片) 若面片之间存在公共边，则连接图中相应的结点，如图2 2 所示。 图2 2 红色线表示同格对偶图 4 三维月格模型分割及其在检索中舶应用 2 1 2 三堆网格分割的评价标准 目| ，三维网格分割没有统一的评价标准。分割质量的好坏与相应的应用有直接的 关系。但是还没有一种适合所有应用的分割算法，绝大多数算法还都是针对具体问题提 出的。常见的标准有：( 1 ) 是否存在过分割；( 2 ) 分割边界是否光滑；( 3 ) 是否产生有 意义的分割。近年来多数分割算法都追求产生有意义的分割结果。而对于过分割的处理 方法目前主要有忽略、合并、删除等方式。 研究表明 7 ，人类对形状的识别基于有意义的分割，复杂的物体通常被看做几个 部分的组合。大多数分割算法，采用各种不同的标准得到有意义的分割。其中，最常见 的标准是h o f f r i l a n 等人 8 提出的最小负曲率法则以及显著性分割理论。最小负曲率法 则认为人类在认识物体的过程中，把最小的负曲率线作为物体的分割边界，从而将物体 分成几个组成部分，如图23 。显著性分割理论则是对物体显著性特征进行提取，得到 显著性的分割结果。然而，人类对事物的感知又是错综复杂的，有意义的分割具有很大 的主观性，很难自动的得有意义的分割结果。 黪 图23 最小负曲率法则分割边界 2 1 3 三堆网格分割的发展 v i n c e n t 等人f 1 在1 9 9 1 年较早的提出了三维网格模型的分割，他们把图像处理中的 分水岭方法推广到三维模型的分割问题上，实现的三维模型的分割。1 9 9 9 年m m a g a n 等 1 2 】利用分水岭算法实现了三维网格的分割，并且较好地解决了过分割问题；2 0 0 1 年， p u l l a 等 1 3 、1 4 改进了m a n g a n 等人的曲率估计的工作。 1 9 9 2 年，f a l e i d i e n o 等人 9 】按照曲率相近的原则，把网格模型分割为凹面片、凸面 片、马鞍面片和平面片。2 0 0 3 年，s r i a r k 等人 1 田利用高斯曲率和平均曲率将顶点所在 面片分成四类：凸面、凹面、平面、最小面片，得到分割结果。这种方法在分割边界处 容易产生分割小洞，容易产生过分割。2 0 0 6 年，c h e l a 等人 1 1 】采用与f a l e i d i e n o 和s d n a r k 相似的方法，他们利用顶点的n 层领域来计算曲率，并增加了面片的凸凹估计，从而得 到分割边界光滑的有意义的分割： 1 9 9 5 年，v e d e 雠 n 1 5 和1 9 9 6 年k r i s h n a m u r t h y 等人【1 6 在他们的动画变形的制作过程 5 三维网格模型分割及其在检索中的应用 中，给出了用户交互式的分割方法；1 9 9 9 年，g r e g o r y 等人 1 7 提出在动画设计过程中的 交互应用，根据用户选择的特征点将网格曲面分割成用于变形的相应的面片；2 0 0 6 年， l i u 等人 2 提出基于两条s k e t c h e s 的交互式网格分割方法，得到有意义的分割结果；2 0 0 7 年，w u 等人【3 】提出了基于多条s k e t c h e s 的交互式网格分割方法：2 0 0 8 年，h u 等人 4 提 出基于关键点的交互式和自动的网格分割方法。 2 0 0 2 年，z u c k e r b e r g e r 等人 5 利用相邻面片的二面角来确定凸的面片，得到网格分 割结果；s h l a f m a n 等人【1 8 n 用测地距离与二面角的加权值，得到分割结果；2 0 0 3 年， k a t z 等人 1 9 】对s h l a f m a n 的方法进行了改进，得到了分割边界光滑的有意义的分割结果。 1 9 9 7 年，w u 等人 2 0 n 用穿过曲面的电荷分布得到分割结果，给出了基于物理的 分割方法。该算法利用电荷的密度判断曲面的凸凹性，分割边界在电荷密度最小的区域； 2 0 0 0 年，r o s s l 等人 2 1 在逆向工程应用中，定义了网格曲面上的面向曲率信号的数学 形态学的开闭操作，从而得到去噪后的特征区域骨架，并实现了网格分割；2 0 0 1 年， l i 等人 2 2 利用边收缩的方法简化面片，得到描述几何和拓扑特征的骨骼树，然后进行 空间扫描自动分割，由此实现了碰撞检测；y u 等人 2 3 】在视觉系统中，自动将几何场景 点云分割为特别的、用于纹理映射和绘制的网格曲面片二叉树。上述的这些方法都是为 了使得分割的结果便于参数化，故只能产生凸的分割结果，产生的分割边界并不连续。 2 1 4 三维网格分割的分类 根据网格模型的规则性，可以将三维网格分割算法分为规则网格分割、半规则网格 分割和任意结构的网格分割算法；根据分割结果，可以分为有意义的网格分割和无意义 的网格分割；另外，三维网格分割的目标和应用领域也决定了网格分割算法的类型，根 据分割目的可以将三维网格分割算法分为两类：将网格分割为如特征等模型各组成部分 的p a r t t y p e 的分割算法，以及将网格模型分割为具有某种几何性质( 如平面、圆柱面、 球面等) 区域的p a t c h t y p e 的分割算法。 p a r t t y p e 分割则是接近于基于组成部分的分割，得到的分割区域通常对应模型的物 理组成部分。该算法可以应用在形状匹配、几何变形、形状重建、碰撞检测、计算机动 画等领域。而p a t c h t y p e 分割算法是基于面的分割，这种算法得到的分割区域类似于构 成原模型的各个面，如平面、圆柱面、球面等，各个分割区域具有一定的几何意义，因 此，对于同一模型p a t c h t y p e 分割结果区域数目通常比p a r t t y p e 要多。这种算法普遍使 用于纹理映射、模型简化和编辑以及几何图像生成等工作中。， 图2 4 说明这两种方法的分割结果，左侧为p a t c h - t y p e 的分割结果，右侧为p a r t t y p e 的分割结果。 6 三维罔格模型分割其在检索中的应用 闹韩 2 2 典型的网格分割算法 2 2 1 区域增长法 图2 4 三维两格分割的两种方式 此类算法首先要选定代表不同区域的种子元素( 如顶点、三角形等) ，然后按照一 定的增长标准在种子的周围进行区域的增长，直至覆盖整个区域。该算法的优点是算法 思想简单、易于实现、通常速度较快，但还有许多需要思考的问题，如种子的选取机制， 增长的终止条件，过分割问题等。 b e s l 和j a i n 2 4 在深度图像中实现区域增长算法。他们利用高斯曲率和平均曲率得 到最初的种子元素。利用种子元素建立种子区域，从而实现区域增长。在增长区域上拟 合可变阶的二变量多项式，将满足这个多项式的邻接顶点添加到增长区域内。当满足终 止条件时，停止增长。他们的算法被v i e n 和s h i m a a a 2 5 1 应用到了三维网格模型中。 z h a n g 等人【2 6 利用高斯曲率标记顶点。根据最小负曲率法则，将负高斯曲率小于 域值的顶点标记为边界点。然后在非边界点中随机的选取种子点，进行区域增长。增长 过程中，始终添加的是非边界点。分割结果如图2 5 。该方法的优点是实现简单，但分 割结果过分地依赖于用户所定义的阀值。 霪蚤气茹目r 图2 5 对机械模型的分割结果 z u c k e r b e r g e r 5 等人利用网格的对偶图提取分割区域。尤其是他们从圈的一个节点 二维n 格模型分割及其在检索中的应用 开始深度或广度优先搜索遍历这个图。若遍历的结点所对应的三角形面片能够形成一个 凸的分割区域，遍历继续进行，否则停止遍历。然后，从未遍历的节点中建立新的分割 区域，遍历重新开始。这种方法的主要问题是产生过分割，因而作者将较小的分割区域 进行了合并。 2 22 聚类算法 通常有两种聚类方法：迭代聚类和层次聚娄。聚类和区域增长方法在本质上是非常 相似的。主要的区别在于，迭代聚类方法利用最小值函数得到聚类代表，而区域增长法 则是在算法开始时选取种子元素而且不再改变。另外选代聚类根据三角形面片与聚类 代表之间的距离将三角形面片分配到相应的分割区域中而区域增长法的分割标准与种 子元素无关。层次聚类方法中。层次结构的第一层所有元素都为种子元素，然后在下一 层进行合并，而在区域增长法中，标记出种子元素。然后将其他非种子元素添加到种子 元煮中。 s b l a f i n a n 等人【1 8 】利用女- m e 锄 i s 聚类算法来分割。( 1 ) 计算每两个三角形之间的距 离；( 2 ) 计算三角形聚类的代表：( 3 ) 将其他所有三角形分配到最近的代表中；( 4 ) 根据 聚类中的三角形与代表之间距离和的最小值更新代表。相邻两个三角形之间的距离函数 定义为三角形重心之间的禊4 地距离和三角形面片夹角的加权和。 k a t z 和t a l 1 9 1 提出层次模糊k - m e a n s 算法。他们采用与s h a f i n a n 相同的距离函数 得到三角形面片的聚类。将模型分成两个分割区域和一个模糊区域模糊区域将被分配 到其中的一个分割区域中。根据最小值原则，在摄凹处将模糊区域分成两部分。分割结 果如图2 6 。该方法的的优点是得到有意义的分割结果，并且符舍最小值法则。但当分 割边界不在凹度区域内最小值分割不能总找到最佳的分割边界。 缈， 幽2 6 层欢聚类的分割结果 2 2 3 分水岭算法 分水蛉算法展主要的一个缺点是过分割问题。一些算法采用不用的标准合并分割区 三维月措模型讣割担其在检索中的应用 域。 z u c k e r b e r g e r 等人【5 利用相邻三角形面片的二面角定义分水岭函数。该方法当输入 网格的顶点比较稀疏时，同样得到较好的分割结果。主要缺点是容易受到噪声的影响而 产生过分割。 p a g e 等人f 2 7 提出处理过分割的方法。在最小负曲率处，利用阐值和三维形态学操 作定义一个中心点，当到达中心点时，停止填充盆地。将法曲率作为分水岭函数，利用 溢出法继续填充盆地。如图27 ，从图中可以看出分割边界不光滑。 留擘 削27 刚格分制实例 2 2 4 基于关键点的算法 利用定义在网格上的关键点进行分割。关键点作为网格模型的显著性特征，区别网 格上不同的凸度区域，从而得到分割处理。 k a t z 等人【2 8 提出基于网格上的关键点的分割方法。首先，利用多维空间缩放的方 法将网格模型变换成一个固定姿势的模型。在变换后的模型上得到关键点。这些关键点 为变换模型的凸函数的局部最大值在模型的凹度区域内进行分割。 “等人【2 9 】也在网格上定义了关键点。他们称其为显著性代表。这些代表是定义在 网格对偶圈上的凸函数的局部最大值。每个代表建立的测地带称为现场，利用现场定义 边界函数。然后利用k a t z 和t a l l l 9 的最小值分割算法分割模型的显著性部分。该方 土 只有当网格模型具有显著性凸部分的时候，才能得到较好的分割结果。 2 2 s 分割算法小结 本文根据基本的方法概念、不同的标准以及在分割过程中所使用的特性，将三维网 格分割算法进行分类。另外，我们对作者采用的标准和特征进行了总结，如表2 1 ，希 望对以后的研究者有所帮助。 三维网格模型分割及其存检索中的应用 表2 1 分割算法总结 方法作者特征标准 可变近似多 项式，高斯 b e s l 和1 a i n 多边形曲面上点之间的距离，顶点的斜率估计 区域曲率和平均 增长曲率 法 z h a n g 等人 高斯曲率大于用户定义的域值的高斯曲率 z u c k e r b e r g e r 等 相邻三角形 根据二面角来确定凸面 人 的二面角 分水 p a g e 等人 最小值曲 如果顶点的最小曲率值大于一个域值，那 分水么该顶点就属于集水域，另外根据顶点的 率，法曲率 岭方岭函法曲率将其添加到分割区域内 数f法 z u c k e r b e r g e r 等 二面角根据建立的函数f 确定属于集水域的边 人 测地距离和 根据测地距离和二面角的加权和所定义的距离函 s h l a f m a n 等人 二面角数，对三角形聚类。这里的权值手动设定 聚类 测地距离和根据测地距离和二面角的加权和所定义的距离函 k a t z 和t a l 二面角数，对三角形聚类。这里的权值手动设定 k a t z 等人 关键点，二 网格模型所有顶点的中心 基于面角 关键关键点，测 点l i 等人地距离，突 根据与网格关键点的测地距离和角距离，定义分割 边界 出函数 2 3 三维网格分割的应用 2 3 1 三维检索中的应用 随着三维扫描技术和计算机图形学的发展以及计算机硬件的提高，三维模型的数量 已经有了飞跃性地增加。充分利用已有的三维模型资源，可以大大减少设计新模型的工 作量。如何从三维模型数据库中检索出相似的模型，已经成为一个重要的应用需求。形 状描述与匹配是三维检索中两个最首要解决的问题。而相似的物体有着相似的分割，基 于分割的结构形状描述子可以用于形状匹配。另外，随着互联网的广泛使用，在数据库 中检索具有某种局部形状特征的三维模型，成了一个新的需求，如图2 8 。 1 0 = 维格模型分割& j t 和检索中的成用 0 ：0鬣 氨 静囊藤r 堞 遭漕01 1 l i 婶昧瘴雕囊，盼 ，j ，瓷 图28 基于分割的三维模型检索 2 0 0 2 年，s h l a f m a n 等人【1 8 】在拥有3 8 8 个的三维网格模型的小规模数据库上，进行 丁检索、变形、简化三个应用。他们首先将三维网格模型分割成几个的有意义的分割区 域。然后评价每一个分割区域的形状，并确定它们之间的关系。建立模型每个分割区域 的属性图，从而得到与原模型之间关联性，在进行相似性度量时，只需比较树形图的相 似度。k o b b e l t 等人 30 】尝试从椭球集台中得到统计特征提取方法，如采用椭球半径的平 均方差或标准方差以及它们的比率作为椭球的统计特征。在不同的形状修改中，这种统 计特征可以保持不变，可以作为一种检索的特征描述。但是这个想法没有得到严格的理 论或者实验的证明。 2 0 0 3 年，d e y 等人口1 利用基于网格模型的拓扑信息，提出动力学系统的形状特征 描述方法，并采用离散 c 9 格形状特征模拟连续形状。实验表明，该方法十分有效地分割 二维及三维形状特征。同时，他们还提出了基于该特征分割方法的形状匹配方法。 2 0 0 4 年，f u n k h o u s e r 等人【3 2 】利用三维模型检索系统，检索所需的模型的某个特殊 的部分。在得到的检索结果中，从模型中裁剪下所需要的部分，拼接成一个新的目标模 型，完成了三维模型的重建技术。利用现有的模型构造出新的模型，在设计思路上发生 了转变。该工作可趴产生具有较高细节的几何模型。 2 0 0 5 年，s u z u k i 等人 3 3 采用自动的分割算法将模型分割，对分割得到的部分模型 进行了检索。该算法利用相邻面片之间的二面角将模型分割成几个部分，然后通过部分 模型之间的相似性比较，完成原模型之间的检索。但是该分割算法主要是通过二面角束 完成网格模型的分割，并不是有意义的分割而且容易产生过分割，并且得到的部分模 型的检索结果并不理想。 三维网格模型分割及其在检索中的应用 2 3 2 动画与几何变形中的应用 1 9 9 9 年，g r e g o r y 等人 3 4 1 在利用插值实现两个模型之间的变形。首先，在两个输 入的模型上交互的选择顶点( 记为标记点) ，建立两个模型之间的对应关系。通过计算 标记点对间的最短路径，确定在此路径上的网格上其他的顶点，从而在模型的表面得到 一个子连通图。然后，将每一个三维模型分割成相同数目的分割区域，每个分割区域都 与圆盘是同胚的。最后，在分割区域之间建立映射、重构、局部加细完成对应关系的建 立，实现两个模型之间的变形。 2 0 0 2 年，s h l a f m a n 1 8 采用与图像分割k - m e a n s 聚类相似的方法，迭代得到分割结果。 分割区域的数目可以由用户预先指定，从而避免了过分割，且适用于动画制作的需求。 并且该方法不再限制输入网格必须是零亏格、或者是二维流形的。s h l a f i n a n 提出新的网 格模型分割方法和新的柱状分割区域投影算法，降低了工作量、提高了效率。 显然，基于分割的变形对于保持模型的特征有着重要的意义。局部投影算法能够产 生精细的对应区域，且能自动产生有意义的分割区域。 2 3 3 几何压缩传输中的应用 1 9 9 6 年，t a u b i n 3 5 首先将傅立叶变换应用在三维网格模型几何压缩处理中。由任 意拓扑结构的网络顶点邻接矩阵及其顶点价数，得到网格模型的l a p l a c i a n 矩阵及由其特 征向量构成的r n 空间的正交基底，对应的特征值即为频率。三维网格顶点的坐标向量在 该空间的投影即为该网格模型的几何光谱。 2 0 0 0 年，k a m i 等人 3 6 首先将三维模型分割成具有几何性质的分割区域( 属于基 于p a t c h 的分割) ，然后将分割区域的光谱信息应用到压缩问题上。利用光谱定义三维模 型的几何拓扑信息，容易产生伪频率信息。而且对于大规模的网格，由于在网格顶点数 目多于l ，0 0 0 时，l a p l a c i a n 矩阵特征向量的计算几乎难以进行。k a m i 先将模型分割成数 目有限的、各个区域顶点数目接近的分割区域，然后利用t u r e 投影，将各个分割区域因 拓扑信息不同而产生的不同的分割区域的基函数，统一为6 r e g u l a r g 习格分割片基函数， 从而很好的解决了上述的问题，提高了计算效率。但由于分割方法的限制，该方法只适 用于没有尖锐边缘特征的光滑网格模型。 2 0 0 3 年，a l f a c e 3 7 提出了光谱表示重叠的方法。扩张分割片，使分割片之间产生 重叠。该工作很好地改进了k a m i 等人的分割边界的处理问题。 总而言之，良好的三维网格分割保证了高质量的网格压缩的传送。 1 2 三维网格模型分割及其在检索中的应用 3 三维网格模型 3 1 三维网格模型的格式 网格模型是最常用地几何表示方法之一。首先，是因为这种表示方法非常灵活，可 以采用任意精度来逼近任意形状的物体。其次，是因为当今的图形硬件可以非常快速的 处理多边形网格模型，即使是普通地个人计算机也不例外。大多数以三维网格模型作为 处理对象，目前，有o b j 、o f f 、s t l 、v r m l 等多种常用的开放数据格式。 3 1 1o b j 文件格式 o b j 文件以文本的形式存储了模型的顶点、面片、法线、纹理坐标和材质使用等信 息。注释行以一个常为开头。o b j 文件的每一行，都有极其相似的格式。在o b j 文件 中，每行的格式如下： 其中，关键字标识了这一行所存储的信息类型，参数则是具体的数据。o b j 文件的 关键字主要有如表3 1 ： 表3 1o b j 文件中的关键字说明 关键字说明 v 表示本行指定一个顶点。 关键字后面的3 个单精度浮点数，分别表示该定点的x 、y 、z 坐标值。 v t 表示本行指定一个纹理坐标。 关键字后面的两个单精度浮点数；分别表示此纹理坐标的u 、v 值。 v n 表示本行指定一个顶点法线向量。 关键字后面的3 个单精度浮点数，分别表示该法向量的x 、y 、z 坐标值。 f 表示本行指定一个表面( f a c e ) 。 一个表面实际上就是一个多边形图元。关键字行的参数格式后面将详细介绍。 u s e r n t l 关键字后只有一个参数。该参数指定了从此行之后到下一个以u s e m t l 开头的行之 间的所有表面所使用的材质名称。该材质可以在此o b j 文件所附属的m t l 文件 中找到具体信息。 m t l l i b 关键字后只有一个参数。该参数指定了此o b j 文件所使用的材质库文件( 宰m t l ) 的文件路径 处理模型的顶点和面片数据。 利用u l t r a e d i t 软件打开一个o b j 文件。可以看到如下内容： 1 3 是 三维网格模型分割及其在检索中的应用 群 撑w a v e f i o n t0 b jf i l e j c o n v e r t e db yt h e3 de x p l o r a t i o n1 5 5 0 撑x d i m e n s i o ns o f t w a r e l l c h t t p ：w w w x d s o f t c o r n e x p l o r e r 撑 m t l l i bb u n n y3 4 k m t l f o b j e c to b j e c t f 0 撑g o b j e c