（计算机应用技术专业论文）三维模型检索中关键技术的研究.pdf

浙江大学博士学位论文 摘要 随着三维数据获取技术、三维图形建模方法以及计算机硬件技术的发展，已 经产生了越来越多的三维模型数据三维模型l l - - 维图像更真实的描述了现实世 界。如何从各类模型数据库或互联网检索到所需的三维模型已成为计算机和互联 网发展过程中的一个重要课题。r 前三维模型检索研究的对象主要是网格模型。 网格模型是指由多边形网格组成的三维模型，通常包括顶点坐标、颜色、纹理、 法向量等属性。一个完整的三维模型检索系统通常包括特征提取、相似性匹配、 索引结构、查询接口等几方面。其中，特征提取是三维模型检索研究中的一个首 要解决的基本问题和关键技术，它也是本文研究的重点。 目前特征提取方法还处于对通用网格模型形状特征的研究阶段，如针对模型 顶点关系的统计特征描述、基于视觉相似的关于二维视图的特征描述等。由于网 格模型形状实质上就是由一组具有不同法向、面积和空间位置的多边形组成的多 边形集合，因此已有方法往往存在对几何形状特征描述过于弱化的问题。针对此， 本文提出了两种基于三维网格模型形状相似的特征提取方法：基于多视点深度图 的特征提取技术和复球面特征映射技术：同时本文针对蛋白质分子的三维结构， 提出了两种分维特征的计算方法，即h a u s d o r f f 维数和信息量维数，它们是对蛋 白质主链结构特征的描述。 针对网格描述的通用模型，奉文首先提出了一一种基于多视点深度图的特征提 取技术。该技术的思想是如果两个模型是相似的，那么从任意一个角度看它们都 应该相似。基于这一点文中采用了主元分析和相位傅立叶变换两种技术提取了模 型的几何统计特征。首先用主元分析方法对模型进行规范化预处理，然后通过对 模型不同视点下的一组深度图的相位傅立叶变换，获得关于模型面片的法向和面 积的二维统计特征直方图。提取的特征对模型的平移、旋转、尺度不变，对噪音 不敏感；并利用图像相关技术对特征进行了相似性度量。通过与已有的典型特征 提取方法的比较，实验结果表明该方法对模型的分类效果较好。 针对网格通用模型，文中还提出了一种复球面映射的特征提取技术。由于网 格模型实质上是一组具有不同法向、面积和空问位置的面片集合，因此通过对模 浙江大学博士学位论文 型面片的一次扫描，把面片的法向、面积、面片的空间位置映射到单位复球血上， 构造出关于模型几何特性的复球面特征直方图。由于无需进行模型配准，冈此特 征提取的计算量小，存储消耗不大。利用球面相关技术，对模型进行相似性匹配， 实验表明该方法对模型的平移、旋转、尺度不变，通过与已有的典型特征提取方 法的比较，实验结果表明该方法对模型的分类效果较理想。 在对蛋白质分子的三维结构的特征提取的研究中，首先分析了现有方法对蛋 白质分子配准要求过于严格和特征矢量维数过高带来的耗时和存储开销大等缺 点，文中针对蛋白质主链，提出了两种标量特征：h a u s d o r f f 维数和高次的信息 量维数。利用合适的尺度对蛋白质主链进行长度度量，根据尺度和长度之间的关 系确定主链的h a u s d o r f f 维数；对蛋白质分子进行某种尺度的区域划分，根据蛋 白质主链原子落在某个区域的概率确定主链的各阶信息量维数，借此表达出蛋白 质结构更为丰富的信息特征。与已有的方法相比，本文方法计算量小，存储开销 不大，对噪音不敏感，适合对蛋白质结构的预分类，分类结果较好。 关键词：三维模型检索特征提取主元分析相位傅立叶变换复球面映射 蛋白质结构分类蛋白质主链分形维数 浙江大学博七学位论文 a b s t r a c t w i t ht h e d e v e l o p m e n to f3 dd a t aa c q u i s i t i o na n dm o d e l i n gt e c h n i q u ea n d h a r d w a r e ，m o r ea n dm o r e3 dm o d e l sa r ep r o d u c e d h o wt or e t r i e v et h en e e d e d3 d m o d e l sf r o mt h ei n t e m e ta n d3 dm o d e l sd a t a b a s ei sb e c o m i n ga ni m p o r t a n ti s s u e f e a t u r ee x t r a c t i o ni st h ek e yp r o b l e mi n3 dm o d e lr e t r i e v a l m o s to ft h ep r e v i o u s m e t h o d sa r ea b o u tt h ef e a t u r ee x t r a c t i o no f t h eg e n e r a l3 dm o d e l s i nt h i sc o n t e x t ，w e f o c u so nt w oa s p e c b ：f i r s tt h ef e a t u r ee x t r a c t i o na n ds i m i l a r i t ym e a s u r e m e n to ft h e g e n e r a l3 dm o d e l si nm e s hr e p r e s e n t a t i o n ，s e c o n dt h ef e a t u r ee x t r a c t i o no ft h e3 d s t r u c t u r eo fp r o t e i nm o l e c u l e t h ee x i s t i n gm e t h o d sc a n n o tp r o v i d et h er e a l g e o m e t r i c a lf e a t u r eo f3 dm o d e l ss u c ha st h eo r i e n t a t i o na n dt h ea r e aa n dp o s i t i o no f t h ef a c e so f3 dm o d e l s i nt h i st h e s i s ，w ep r o p o s et w of e a t u r ee x t r a c t i o nm e t h o d s f o r t h eg e n e r a l3 dm o d e l si nm e s hr e p r e s e n t a t i o n ：o n ei sp h a s e e n c o d e df o u r i e r t r a n s f o r mb a s e do nm u l t iv i e w p o i n tr a n g ei m a g eo fm o d e l s ，a n o t h e ri sc o m p l e x s p h e r ef e a t u r em a p s i m u l t a n e o u s l y , w ep r o p o s et h eh a u s d o r f ff r a c t a ld i m e n s i o na n d i n f o r m a t i o nf r a c t a ld i m e n s i o na st h ef e a t u r eo f3 ds t r u c t u r eo ft h ep r o t e i nm o l e c u l e f i r s t l y , t h ef e a t u r ee x t r a c t i o nm e t h o df r o mp h a s e - e n c o d e df o t c r i e rt r a n s f o r m b a s e do nm u l t i - v i e w p o i n tr a n g ei m a g eo f3 dm o d e l si sp r o p o s e d ，w h i c hc o m e sf r o m t h es t a t e m e n t “i ft w om o d e l sa r es i m i l a r , t h e ya l s ol o o ks i m i l a rf r o ma l lv i e w i n g a n g l e s ”t w ot e c h n i q u e sa r eu s e di nt h i sm e t h o d ：p r i n c i p a lc o m p o n e n ta n a l y s i sa n d p h a s e e n c o d e df o u r i e rt r a n s f o r m , as e to ft w od i m e n s i o n a ls t a t i s t i c a lh i s t g o r a m a b o u tt h eo r i e n t a t i o na n da r e ao ft h ef a c eo f3 dm o d e la r eu s e df o rf e a t u r ev e c t o r s ， w h i c ha r ei n v a r i a n tt ot h et r a n s l a t i o n ，r o t a t i o n ，a n ds c a l i n go ft h em o d e la n d i n s e n s i t i v et ot h en o i s e s i m i l a r i t ym e a s u r e m e n tb e t w e e nt w om o d e l sa r co b t a i n e db y u s i n gt h ei m a g ec o r r e l a t i o nt e c h n i q u e s t h ee x p e r i m e n t a lr e s u l t s s h o wt h a tt h e p r o p o s e dm e t h o di ss u i t a b l ef o rt h ec l a s s i f i c a t i o no f3 dm o d e l s s e c o n d l y , af e a t u r ee x t r a c t i o nm e t h o db a s e do nc o m p l e xs p h e r ef e a t u r em a pi s s u g g e s t e d t h eo r i e n t a t i o n ，a r e aa n dp o s i t i o no f t h ef a c eo f3 dm o d e la r em a p p e do n t o 浙扛大学博士学位论文 t h ec o m p l e xp o i n to nt h eu n i ts p h e r e ，t h e nas p h e r i c a lh i s t o g r a ma b o u tt h eg e o m e t r i c a l f e a t u r eo f3 dm o d e li sc o n s t r u c t e d t h i sm e t h o do n l yn e e d st h el o wc o m p u t a t i o na n d s t o r a g ec o s t b yu s i n gs p h e r i c a lc o r r e l a t i o nt e c h n i q u e s ，t h es i m i l a r i t ym e a s u r e m e n t c a l lb eo b t a i n e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h i sm e t h o di sg o o da tt h er e c o g n i t i o n o f3 dm o d e l sa n di n v a r i a n tt ot h et r a n s l a t i o na n dr o t a t i o no f t h em o d e l s t h i r d l y , i no r d e rt 0a v o i dt h ec o m p l e x i t yo ft h ee x i s t i n gm e t h o d si nr i g i db o d y a l i g n m e n ta n dh i g hd i m e n s i o nf e a t u r ev e c t o r s ，w ep r o p o s et w of r a c t a ld i m e n s i o n sa s t h ef e a t u r eo ft h eb a c k b o n eo ft h ep r o t e i nm o l e c u l e si nt h ef e a t u r ee x t r a c t i o nf o rt h e t h r e e d i m e n s i o n a ls t r u c t u r eo fp r o t e i nm o l e c u l e s ，o n ei sh a u s d o r f fd i m e n s i o na n dt h e o t h e ri si n f o r m a t i o nd i m e n s i o n c o m p a r e dt ot h ee x i s t i n gm e t h o d s ，t h i sm e t h o dn e e d s l o w e rc o m p u t a t i o nc o s ta n dl o w e rs t o r a g e ，a n di ti ss u i t a b l ef o rt h ep r e c l a s s i f i c a t i o n o f3 ds t r u c t u r e so f p r o t e i nm o l e c u l e s k e yw o r d s 3 dm o d e lr e t r i e v a l ，f e a t u r ee x t r a c t i o n ，p r i n c i p a lc o m p o n e n ta n a l y s i s ， p h a s e e n c o d e df o u r i e rt r a n s f o r m ，c o m p l e xs p h e r ef e a t u r em a p ，p r o t e i ns t r u c t u r e c l a s s i f i c a t i o n ，b a c k b o n eo f p r o t e i n ，f r a c t a ld i m e n s i o n 浙江大学博士学位论文 第一章绪论 互联网的发展给人们提供了巨大的信息资源，计算机使用的普及使得人们畅 游于虚拟而又真实的数字信息海洋之中，面对着庞大的纷繁复杂的各类多媒体信 息，人们对信息检索工具的依赖日益增强和迫切，如何快速、准确地查找到自己 所需要的资料成为计算机和互联网发展过程中的一个重要课题。2 0 世纪9 0 年代 初为了适应对图像和视频检索的需求发展了基于内容的多媒体检索技术的研究， 该技术很快在理论研究和实际应用中得到迅速发展，在基于内容的图像检索研究 中，比较成功的例子是针对商标图像的内容检索【b a d a w y2 0 0 2 。随着兰维数据 获取技术、三维图形建模方法及图形硬件技术的发展，已经产生了越来越多的物 体的三维模型数据库，如三维游戏( 3 dg a m e ) 、工业实体c a d 数据库等，三维 模型已成为继声音、图像和视频之后的第四种多媒体数据类型，日益发达的互联 网和功能增强的计算机为人们对三维模型的共享和处理提供了条件，在不久的将 来，人们可以像使用二维图像一样任意地使用三维模型，人们的问题已经从最初 的“我们如何获得三维模型? ”，变成了如今的“我们如何查找到所需的三维模 型? ”，这些都导致对三维模型检索应用需求的增长，比如进行高逼真度的三维 建模非常费时费力，如果能对已有的三维模型进行复用的话，将节省大量开支， 同时基于内容的三维模型检索研究可以广泛应用于虚拟地理环境、计算机辅助设 计、分子生物学、军事、医学、化学、考古、工业弗4 造等领域，在电子商务和互 联网搜索引擎中也有着广阔的应用前景。因此如何迅速检索到所需的三维模型成 为继文本、图像、视频检索之后的又一1 个热门课题，它涉及了人工智能、计算机 视觉、模式识别等领域。发艘基于内容的或其它的检索技术是多媒体信息检索课 题的一个必然趋势，对三维模型及三维场景等媒体信息的标准化描述和检索已被 纳入m p e g - - 7 国际标准的发展框架中，进一步开展基于内容的三维模型检索研 究，不仅具有重要的理论意义，而且具有重大的实际应用价值。 现在的许多三维模型检索网站主要依靠文本关键词检索手段，如3 d c a 托三 维模型库( h t t p ：w w w 3 d c a f e c o m ) ，这是一个免费的三维模型下载站点，用户可 以通过输入要查找模型的文本描述进行检索，还有一些网站可以输入需要查找模 浙江：j _ = 学博士学位论文 型文件的类型( 比如3 d s ，o b j 等) 或文件名进行查找，如美国d e r e x e l 大学的c a d 数字图书馆( h t t p ：w w w d e s i g n r e p o s i t o r y o r g ) 等。虽然基于关键词的方法在些搜 索引擎中得到成功地应用，如g o o g l e ，y a h o o 等，但当用关键词技术应用于诸如 图像、视频、三维模型等多媒体数据的搜索时，基于关键词的方法存在以下问题： ( 1 ) 、关键词的描述比较片面，难以充分描述复杂的三维模型、图像、视频和场 景，甚至会遗漏重要的信息。( 2 ) 、关键词的标注常常依赖于一些主观和客观因 素，比如标注者的年龄、知识结构、语言、文化背景甚至性别等，因此关键词容 易产生歧义性。( 3 ) 、用来查找的网络上的一些三维模型或场景的提供者往往也 只提供了相应的文件名和文件类型，并没有提供具体的关键词描述。( 4 ) 、有时 用户自身对所需查询的模型也很模糊，无法提供确定的关键词。( 5 ) 、三维模型 数量与日俱增，人工标注关键字非常费时费力。因此，基于关键词的检索可靠性 和效率都不高，基于文件名和文件类型的检索也存在同样的问题，而且检索的结 果仍将是海量的，由此可见，发展基于内容的三维模型检索技术非常重要和迫切。 在基于内容的三维模型检索领域，国外的研究者较国内更早，早在上个世纪 九 | 年代末，加拿大国家研究院( n a t i o n a lr e s e a r c hc o u n c i l ) 的p a q u e t 等人就已经 对三维模型检索进行了理论和算法的研究，并开发了第一个三维模型检索实验系 统的原型 p a q u e t1 9 9 9 1 ，其他高校和研究机构如美国的普林斯顿大学( p r i n c e t o n u n i v e r s i t y ) 、华盛顿大学( w a s h i n g t o nu n i v e r s i t y ) 、布朗大学( b r o w nu n i v e r s i t y ) 、 卡耐基梅隆大学( c a r n e g i em e l l o nu n i v e r s i t y ) 、普渡大学( p u r d u eu n i v e r s i t y ) 、 n e c 美国研究院、h p 以色列海法研究院、德国的慕尼黑大学( m u n i c h u n i v e r s i t y ) 、波恩大学( b o n nu n i v e r s i t y ) 、i b m 日本东京研究院等相继开展了基 于内容的三维模型检索技术研究，并取得一定进展，国内如浙江大学 p a n2 0 0 4 ， w e n g2 0 0 2 、北京大学 l i u2 0 0 4 、南京大学 y a n g2 0 0 4 、北京微软研究院 l i u 2 0 0 3 等也于近几年开展了对三维模型检索的研究。到目前为止，所有关于三维 模型检索的研究均处于实验探索和研究阶段，研究的对象主要是通用的三三维模 型，只有少数的关于专业领域的检索系统，如德国m u n i c h 大学a n k e r s t 等人研 制的三维蛋白质分子模型检索系统以及苏格兰h e r i o t - - w a t t 大学开发的基于w e b 的c a d 模型搜索引擎等。 三维模型检索的研究目标是帮助用户到数据库或者互联嘲上查找到能反映 浙江大学博十学位论文 查询意图的三维模型或三维模型集，查询的思路是通过将查询意图和数据库中的 模型之间进行相似性匹配，从而确定查询结果，匹配建立在模型特征的相似性度 量的基础上进行的，由此引发了一些思考： 1 、什么是模型的特征? 特征是事物的某种属性或属性组合，特征既可以看作a 事物区别于b 事物的 性质有时特征又成为a 事物与b 事物是否属于同类的判断依据，因此什么样的 特征是模型的特征成为一个旨要思考的问题。比如，对一个普通的模型而言，它 具有多种属性：几何形状、纹理、拓扑、应用功能、材质等，究竟哪种属性能作 为模型的特征? 这是我们酋先要思考的问题。 2 、什么样的特征可以作为模型相似的判断依据? 人类对事物相似性判断，是带有很强的主观性的，它与人类进行相似性判断 的目的有关，与人看问题的角度相关。如图1 1 所示，a 是一只篮球，b 是一只 西瓜。人类的视觉系统首先会从它们对人类的功能来识别它们是否相似，在人看 来，这是两个完全不同的事物，篮球是人类的体育用品，两西瓜是人类的食物， 显然想让一个人类研制的检索系统模拟人类的视觉系统，从低级视觉特征得到具 有高层语义识别的功能是一个报复杂而且有难度的课题，它涉及到诸如计算机视 觉、人工智能等学科。仅从模型的视觉特征看，a 和b 是两个形状相似但纹理不 同的球状物体，这两个物体是否相似取决于系统判断它们时所用的特征，即是用 形状作为模型的特征还是用纹理作为模型的特征，或者是形状和纹理的组合作为 描述模型的特征，不同的特征将带来不同的判断结果。由此可见，模型的特征提 取对模型的相似性判断至关熏要，f i 前的研究主要集中在对模型的形状相似性的 研究上，对纹理相似的研究还没有出现相关报道。 图1 1a ：篮球 b ：西瓜 3 、用户如何向计算机提交查询意图? 对大多数用户而言，他们对所需查询的模型的概念有时是模糊的、不明确 浙江大学博士学位论文 的，他们只能用诸如“想查找一个像什么样的物体或模型”等模糊语言来描述自 己的查询意图，如何将这些模糊的刁i 明确的想法用计算机语言进行描述，是三三维 模型检索课题中极为挑战的课题，即用户查询接口的设计也是模型检索课题中需 要解决的关键技术。目前有少部分研究人员正在从事查询接口设训的研究工作， 但技术还不够成熟。 总之，一个三维摸型检索系统常常涉及到以下几个关键技术： 模型的特征提取 特征的相似性度量 索引结构 查询接口的设计 对这些技术的研究直接影响着模型检索系统的性能，本文重点研究了三维模 型捡索系统中基于模型几何形状的特征提取技术和相似性度量。 4 浙江大学博士学位论文 第二章三维模型检索系统 2 0 世纪人类最伟大的成就之一是发明了计算机，并通过i n t e m e t 使海量的信 息自由地驰骋于世界的任何角落。但是，人类现在面临的问题是如何从信息汪洋 中，快速有效地获得所需要的资料。一些著名的搜索引擎如y a h o o ，g o o g l e ， i n f o s e e k ，l y c o s ，e x c i t e 的成功之处在于为人们在纷杂的互联网中找寻信息提供 了一条途径，这些搜索引擎都是基于用户输入的关键字进行信息查询的。随着多 媒体技术的飞速发展，图像、视频、音频等不断进入人们的日常t 作和生活中， 基于内容的图像、视频、音频的检索的研究已近十年，并取得了一定的进展。近 年来，三维模型的涌现使得基于内容的三维模型的检索成为多媒体信息检索研究 者们关注的热点。三维模型比二维图像具有更为丰富和更接近真实世界的信息， 它包含的数据量也远远大于二维图像，因此对三维模型的识别和检索的难度也大 于对二维图像的检索。基于内容的三维模型检索技术的核心是通过提取模型的特 征或一组特征来表示三维模型，通过提取的特征值之间的比较，完成模型的相似 性匹配，最终实现三维模型的检索，即从数据库中或互联网上查找能反映用户查 询意图的三维模型或三维模型集。三维模型不仅具有物体的空问几何形状信息和 拓扑信息，还具有物体表面的一些诸如纹理、材质、反射系数属性的相关信息， 因此模型匹配研究内容主要包括：空间几何形状的相似性匹配、模型空间拓扑关 系的相似性匹配和模型表面属性的相似性匹配。目前对模型匹配的研究主要集中 在对三维模型的空间几何形状的相似性度量，有少数关于拓扑相似性匹配的研 究，基于纹理或材质等属性的相似性研究国内外尚未见到相关报道。 基于内容的三维模型检索主要分为两部分：一是离线处理( o f f i i n e ) ，二是在 线处理( o n l i n e ) ，如图21 所示。离线部分主要是对三维模型数据库中的数据进 行特征提取( f e a t u r ee x t r a c t i o n ) ，建立特征描述符和相应的特征数据库，并建立 合适的索引结构。在线部分主要是用户在线提交查询意图并进行特征提取、相似 性度量和索引、查询结果可视化等。 以下对三维模型检索系统中涉及到的几个关键技术作一个简单的介绍： ( 1 ) 、特征提取，建立特征描述符 浙i 上大学博七学位论文 图2 1 基于内容的三维模型检索框架 由于绝大多数的三维模型都是用于可视化，因而表达三维模型的文件中往往 只包含模型的几何属性( 顶点坐标、法向矢量、拓扑连接等) 和外观属性( 顶点 颜色、纹理等) ，很少有适合自动匹配的高级语义特征的描述。显然几何和外观 属性的数值描述无法被直接用来进行两个模型之间的相似性匹配，因此，如何合 理的描述三维模型，即对三维模型进行特征提取成为了检索课题首先要解决的问 题，它也是三维模型检索的难点。一个理想的特征描述符必须满足以下几点： 易于表达和计算的 不占用太多的存储空间 适合进行相似性匹配 具有几何不变性，即对模型的平移( t r a n s l a t i o n ) 、旋转( r o t a t i o n ) 、缩放( s c a l i n g ) 等具有不变性 具有拓扑不变性，即相同模型有多个拓扑表示时。特征描述符应是稳定的 对模型的退化( d e g e n e r a c i e s ) 鲁棒 对噪音( n o i s e ) 不敏感 该特征必须具有唯一性，即不同类型的模型对应的特征表示廊陔4 i 捅同 ( 2 ) 、相似性度量 相似性度量方法与特征提取和描述是密切相关的，不同的特征描述对应不同 的相似性度量方法。相似性度量通过计算模型特征描述之间的相似度。得到对模 型语义相似程度的评价，评价指标通常用查准率( p r e c i s i o n ) 和查全率( r e c a l l ) 浙江大学博士学位论文 来表达。当前的研究中所采用的相似性匹配方法主要借搽了基于内容榆索c b r ( c o n t e n t ，b a s e dr e t r i e v a l ) 的一些相似距离度量，比如e u c l i d e a n 距离 a n k e r s t 1 9 9 9 、m a n t a t t a n 距离 o s a d a2 0 0 1 ，s h a r i r1 9 8 6 、h a u s d o r f f 距_ 离 v r a n i c2 0 0 0 等。 ( 3 ) 、索引结构 在三维模型检索系统中，模型的检索转化成了对高维特征矢量数据库的检索 问题，因此，特征数据库中索引结构的设计对提高检索效率非常重爱，好的索引 机制可以帮助检索系统在时间和存储空间上同时得到提高。因此，在高维空间中 的查询和搜索问题己成了检索研究课题中一个重要的研究领域。 ( 4 ) 、查询接口 作为一个成熟的检索系统，应该拥有良好的交互性能，提供给用户方便的查 询手段。查询方式与用户接口主要研究用户如何准确地向系统提交一个查询请 求，并把榆索结果返回给用户测览或二次榆索。能否方便、充分地表达用户查询 意图的检索系统交互方式直接影响三维模型检索系统的可用性和查询的准确性。 目前的三维模型检索系统主要提供四种典型的交互方式：1 ) 、提交实例方式。2 ) 、 绘制二维草图方式。3 ) 、绘制三维草图方式。4 ) 、文本关键词方式。 2 1 特征提取技术 特征提取与描述研究如何从三维模型表达中提取能够反映高层语义信息的 特征表达。对于三维模型的特征提取与描述早在多年前就有学者在研究【a r b t e r 1 9 9 0 ，b a l l a r d1 9 8 1 ，d e k u b g e t t e1 9 9 3 ，r e e v e s1 9 8 8 ，w a l l a c e1 9 8 0 ，s a d i a d i1 9 8 0 ，但 由于相关应用领域发展的滞后当时并未引起更多的关注，直至二_ 世纪末，随着 计算机硬件条件的成熟、图形学的发展和应用需求的出现，关于三维模型特征提 取方法的研究开始受到了人们的重视。二维模型l ：- - - - 维图像具有更为丰寓的内容 信息和更大的数据量，不仅具有空间几何信息、拓扑信息，还具有诸如纹理、材 质、颜色、透明度、反射系数等表面属性，因此三维模型的识别和检索l l - - 维图 像更为复杂。三维模型的几何特性存在多种表示方式，如多边形9 6 | l 格包围的实体 表示、隐性函数、体素表示、参数化曲面等，由于不同的模型表示方法之间有时 不能相互转换，因此目前还没有一种统一的特征描述方法能适用所有三维模型表 示方法，很多对模型的特征提取的研究和描述只是针对某一种特定表示方法的三 浙江大学博士学位论文 维模型，如 s u n d a r2 0 0 3 等对体素表示的三维模型的特征提取进行了研究， o s a d a2 0 0 u 和 s a u p e2 0 0 h 等的研究对象是多边形网格表示的三维模型， r e g l i 2 0 0 0 ，m c w h e r t e r2 0 0 1 ，c o m e y2 0 0 2 ，m u k a i2 0 0 2 】以c a d 模型作为研究对象， k e i m1 9 9 9 ，【z h a n g2 0 0 1 b 和 o h b u c h i2 0 0 2 等采用v r m l 模型作为研究对象。 由于绝大多数对三维模型描述的文件格式( 如v r m l ，3 ds t u d i o 等) 的设汁都是 用于可视化，虽然在某些3 d 文件格式中会包括一些简单的有意义的结构和一些 语义标识，如a u m c a d 中的实体的层( e m i t yl a y e r ) ，但是在w w w 上可用的3 d 模型绝大多数都不具有这样的属性，它们只是一些没有组织的、退化的多边形集 合表示的三维模型，只包含了模型的几何属性和拓扑关系，不具备结构的相关信 息和高层语义描述，被称之为p l o y g o ns o u p ，这也给三维模型的搜索与匹配带来 了困难。尽管如此，由于三维物体的检索有着实际而广阔的应用，仍吸引着越来 越多的人加入到对它的研究行列中，同时由于三维模型表面属性的多样性和复杂 性，目前对模型特征提取的研究主要集中在对模型空间形状的特征描述和相似性 匹配的研究上，基于形状相似的物体的识别和相似匹配也是计算机视觉领域一直 研究的课题。国内外还没有对于表面属性特征提取和匹配研究的相关报道。 目前三维模型特征提取方法主要分为四类：统计特征提取方法、骨架提取方 法、基于视觉相似的提取方法、和基于几何误差的特征描述方法。下面就此作一 个简单介绍。 2 1 1 基于统计的特征提取方法 对一个三维模型进行参数化本身就是一个很复杂的问题，同时由于三维表面 有任意的拓扑，使得一些在二维图像被使用的如傅立叶分析( f o u r i e ra n a l y s i s ) 等方法无法直接应用在三维领域。很多模型虽然满足了视觉效果，但是大多数是 退化的、不完整的，最经典的如u t a ht e a p m ，是一个无底的茶壶，又如s t a n f o r d b u n n y 是一个带有几个h o l e ( 洞) 的兔子，对这些模型进行有意义的几何特征和 形状信号的计算是很困难的，因此从统计的观点出发寻找出模型的有意义的统计 特征成了研究者们所考虑的研究对象。日前已经被研究使用过的统计特征如：模 型表面随机点间的相互关系( 距离、角度等) 的概率分布、模型的主轴方位关系、 模型项点的曲率分布、模型顶点的矢量方向分布、模型的各阶统计矩、模型映射 浙江犬学博士学位论文 后的傅立叶系数和球砸调和系数等等。统计特征的计算不复杂，易于理解，日翦 统计方法都是针对多边形网格描述的三维模型。由于统计方法提取的是模型的全 局特征，因而适合进行模型的全局匹配。但是统计方法一；能良好的反映模型的本 质特征，并带有随机性，检索性能并4 i 稳定，计算出的模型特征无法进行可视化 的插述不适合对模型进行局部匹配，对原模型中丢失的特征信息也无法提取。 从实验结果看，大多数的参数化的统计特征，如 s a u p e2 0 0 1 a ，a n k e r s t1 9 9 9 等， 比较适合对模型进行粗分类，建立分类数据库。 2 1 1 1形状分布方法 形状分布方法主要用于对模型表面的随机特征进行提取，相关特征如：模型 表面点的曲率分布情况、表面的随机两点问的距离的概率分布情况等等。不同的 统计特征有着不同的特点，经过预处理之后大多数可以满足几何不变性 v r a n i c 2 0 0 0 ，z h a n g2 0 0 1 a ，s a u p e2 0 0 2 ，z a h a f i a2 0 0 1 ，但由于它用模型表面的特征替代了 模型几何体的特征，因而大多数情况下更适合用于对模型进行粗分类。下面对一 些有代表性的特征提取进行简单描述。 o s a d a2 0 0 1 ，o s a d a2 0 0 2 等人采用了一些简单的通用的三角形描述的模型作 为例子，根据不同的几何形体表面顶点间的相互关系呈现出不同的分布特征，试 图将一个任意的、可能退化的三维模型的复杂的特征提取转换成相对简单的形状 概率分森问题。如图2 2 所示，不同形状的d 2 ( 模型表面两个随机点间的欧氏 距离函数) 距离概率分布是不同的，显然将一个任意的模型转换为一个参数化的 概率分布函数，计算比较简单。 l l 兰 l i z 图2 2 直线段a 、圆b 、三角形c 、立方体d 的d 2 概率分布，弓| 自 o s a d a2 0 0 1 1 a n k e r s t1 9 9 9 a a n k e r s t1 9 9 9 b 1 等以蛋白质的分子结构为例，对模型用图2 3 所示的方法进行分割，并计算出每个区域的面积、或体积 z h a n g2 0 0 1 b 、或顶点 9 浙江大学博士学位论文 的数目等参数，描述这些特征分布的直方图，如图2 4 所示以此作为模型的特 征描述。 图2 ，3 网状模型引自【a n k e r s t1 9 9 9 a 】 图2 4n a x a ；y # q ，引自【a n k e r s t1 9 9 9 a 】 上述两种方法对模型的平移、旋转、缩放等具有不变性，对模型边界- 一些小 的扰动具有较好的鲁棒性。但由于特征提取的信息较少，不能全面正确地反映模 型的特征，因此检索性能不是十分理想。 z a h a r i a2 0 0 1 b 提出用3 d s s d ( 3 ds h a p es p e c t r u md e s c r i p t o r ) 方法对三维模 型进行描述。它避免了 m a h m o u d i2 0 0 2 中的二次特征提取。其主要思想是根据 物体表面的一些局部几何属性如某点的曲率，提供物体内在的形状索引s 1 ( s h a p ei n d e x ) 描述。s i 被定义为某点关于两个主要曲率的函数，则3 d s s d 被 定义为s i 在整个模型网格上的分冻，用直方图表示。该描述符对几何转换和比 例缩放具有不变性，对一些易见的、显著的，有突起的特征( 如： c o n v e x i t y ，e o n c a v i t y ，r u t ，r i d g e ，s a d d l e ) 描述准确。但该方法对拓扑表示 ( t o p o l o g i c a lr e p r e s e n t a t i o n s ) 很敏感，对任意网格摘述之前需进行规则化 的预处理，预处理的过程较复杂，涉及到很多方面，如拓扑表示的不唯一性 ( n o n u n i q u e n e s s ) 、网格的不规则采样( i r r e g u l a r l ys a m p i n g ) ，非定向嗍格 ( n o n o r i e n t a b l em e s h e s ) ，退化嘲格( d e g e n e r a t e dm e s h e s ) 等等均需经过处 理，因此该方法并不通用。但该方法的实验效果好，并被建议使用在未来的m p e g 一7 中。 f v r a n i c2 0 0 0 等用一个中心在模型质心的i | 二面体作为参考，由质心至f 。- 面体的顶点的方向作为特征矢量方向再，沿着该矢量方向与模型的三角丽片相 交，取该方向截交长度最长的那个矢量进行归一化后作为模型的特征矢量i ( “) 。 因此，描述一个模型仅需2 0 个特征矢量，尽管该方法比较简单，汁算量小，存 储量少，但显然对模型特征的描述不够准确，同时对一些小的扰动很敏感。冈此 实验结果并小理想。 0 浙江大学博士学位论文 2 1 1 2 基于各种数学变换和矩的统计特征提取方法 在二维图像中，常用各种数学变换如傅立叶变换( f o u r i e rt r a n s f o r m ) 、哈 夫变换( h o u g ht t r a n s f o r m ) 或各阶矩( m o m e n t ) 对图像进行描述，因而很多研究 者尝试着将这种思想应用到三维模型的特征表达上。但是这些特征表达有时是不 稳定的。为了克n f v m n i c2 0 0 0 中特征提取过于粗糙的缺点，文献 s a u p e2 0 0 1 b 对模型球面参数化后沿着经、纬两个方向均匀采样后，得到的球面傅立叶系数作 为模型的特征描述( r a y s b a s e d ) ，这种方法可以实现多分辨率的特征表达，对模 型表面小的扰动具有鲁棒性，在文献 s a u p e2 0 0 l b 中，还采用了矩( m o m e n t ) m “5 作为模型的特征： n 一- i m 玑。5 = r ( m 口) f 畅q ，v v rz 扩s i ，j = o 从实验结果看球面傅立时系数具有更好的检索性能。尽管这种基于射线的矩 ( r a y b a s e d ) 比 p a q u e t2 0 0 0 中的统计矩检索性能要强但是参数化的过程中存 在不同的点映射在同一个球面点上的问题，对模型的表示不唯一：另外，高阶矩 对模型表面小的扰动异常敏感。文献 a n t h o n y1 9 8 8 ，z h a n g2 0 0 2 ，z h a n g2 0 0 1 c s a u p e2 0 0 1 a ，c a n t e r a k i s1 9 9 9 与 s a u p e2 0 0 1 b 思想类似，采用基于傅立叶转换与 矩的思想对模型进行特征描述的，在应用时傅立叶转换对边界的变化很敏感，矩 则对物体的质量分布较为敏感，这些都影响了榆索的效果。i f t m k h o u s e r2 0 0 3 将 三维模型光栅化到一个2 r 2 r 的体素网格上，把这些体素网格看成是模型定义 在一组同心球面上的函数，( p ，们，并用球面坐标表示，对上述函数利用球面调 和分析的方法( 如公式2 1 所示) 得到函数在0 i 同频率m 下的各个振幅系数，并 以此作为模型的特征描述，该方法对模型的平移旋转和反射均不变。 肌州，者。n j ( 李2 m + i ) 蕊( m - i ，2 1 ) p 瓤_ c o s 即哪旺n 其中，r 为体素所在的球恧半径，【0 ，r 】，0 o ，石】和妒毫【0 ，2 z 】。 z h a n g2 0 0 1 b ，e p a q u e t1 9 9 7 等的思想与上述类似，提出了一埽十c o r d b a s e d 浙江大学博士学位论文 的方法，但提供了更丰富的特征描述。首先用主元分析( p c a ) 方法 v r a n i c2 0 0 1l 对模型进行规范化处理得到模型的三个主轴，c o r d 则由模型的质心与模型顶点 的连线定义。模型的特征描述则由以下三部分组成：c o r d 与模型的第一主轴之 间的角度的分布直方图；c o r d 与模型的第二个轴之间的角度的分布直方