（计算机应用技术专业论文）基于内容的三维模型检索(1).pdf

摘要 随着三维模型扫描设备和交互式建模工具的快速发展和广泛使 用，近年来三维模型的数量快速增长。三维模型在众多领域发挥了重 要的作用，很多大型三维模型数据库相继出现，如何从数据库中获取 所需的三维模型成为一个迫切需要解决的问题。本文以基于球面调和 变换的特征提取算法为研究对象，对三维模型检索的关键技术进行了 详细的研究，主要工作包括以下几个方面： 从三维模型空间分布的基本特征出发，系统地定义了4 种球面函 数，从不同角度描述了三维模型。对这4 种球面函数进行球面调和变 换，在此基础上构建了4 种基于单个球面函数的特征描述符。实验结 果表明，这4 种特征描述符具有良好的检索性能和对模型噪声、缩放、 旋转和简化的鲁棒性。 针对单个球面函数特征表达能力有限的问题，提出了基于多球面 函数的扩展特征描述符，综合使用多个球面函数来构建特征向量。针 对单个球面函数没有考虑三维模型在球面方向上离质心不同距离处 的特征，提出了基于同心球壳划分的扩展特征描述符，将单个球面函 数分解为描述三维模型在各个球壳中空间分布特征的球面函数序列， 利用这个球面函数序列来构建特征描述符。实验结果表明，综合考虑 多个球面函数能更全面地描述三维模型的空间分布特征，将球面函数 分解为一个球面函数序列能更有效地描述三维模型在不同球壳内的 空间分布特征，提高了特征描述符的检索性能。 结合以上两种扩展方法，提出了基于多球面函数序列的特征描述 符，综合考虑多个球面函数序列来构建特征向量。实验结果表明，基 于多球面函数序列的特征描述符综合了两种扩展方法的长处，具有最 好检索性能，其中基于全部4 种球面函数序列的特征描述符的检索性 能要优于已有的基于球面调和变换的特征描述符。 关键词三维模型检索，球面函数，球面调和变换，特征描述符，同 心球壳划分 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n de x t e n s i v eu s eo fn e ws c a n n e r sa n d i n t e r a c t i v em o d e l i n gt o o l s ，t h en u m b e ro f3 dm o d e l si n c r e a s e sq u i c k l y r e c e n ty e a r s 3 dm o d e lp l a y sam o r ea n dm o r ei m p o r t a n tp a r ti nm a n y f i e l d sa n dm a n yl a r g e3 dm o d e lr e p o s i t o r i e sc o m ef o r t h t h en e e df o r r e t r i e v a lo fm o d e l sf r o ml a r g er e p o s i t o r i e so f3 ds h a p e sh a sg a i n e d p r o m i n e n c ei nt h eg r a p h i ca n dv i s i o nc o m m u n i t i e s 1 1 1 i sp a p e rf o c u s do n f e a t u r ee x t r a c t i o na l g o r i t h mb a s e do ns p h e r i c a lh a r m o n i c s ，a n a l y z e da n d i n v e s t i g a t e dt h ek e yt e c h n o l o g i e si n3 dm o d e l r e t r i e v a l t h em o s ti m p o r t a n tp a r to ff e a t u r ee x t r a c t i o na l g o r i t h mb a s e do n s p h e r i c a lh a r m o n i c sw a st od e f i n es p h e r i c a lf u n c t i o nw h i c hd e s c r i b e s c e n t a i nf e a t u r eo f3 dm o d e l s i nt h i sp a p e r , f o u rs p h e r i c a lf u n c t i o n sb a s e d o n3 dm o d e lg e o m e t r yf e a t u r ew a sd e f i n e d ，e a c hs p h e r i c a lf u n c t i o n d e s c r i b e3 dm o d e lf r o mac e r t a i np o i n to fv i e w t h e n ，s p h e r i c a lh a r m o n i c t r a n s f o r i l lw a su s e do nt h e s ef u n c t i o n sa n dt h ee n e r g yo ft h ec o e f i i c i e n t s o fs p h e r i c a lh a r m o n i c sw a su s e dt of o r mf o u r3 df e a t u r ed e s c r i p t o r s ：t h e e x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h o s ef o u rf e a t u r ed e s c r i p t o r s h a v e p r e t t yg o o dr e t r i e v a lp e r f o r m a n c ea n dr o b u s t n e s s t or o t a t e ，s i m p l i f i c a t i o n ， s c a l ea n dn o i s e b e c a u s et h ed i s c r i m i n a t i o np o w e ro ff e a t u r ed e s c r i p t o r sb a s e do n s i n g l es p h e r i c a lf u n c t i o nw a sl i m i t e d ，t w ot y p e s o fe x t e n d e df e a t u r e d e s c r i p t o r sw a sp r o p o s e d ：f e a t u r ed e s c r i p t o r sb a s e do nm u l t i p l es p h e r i c a l f u n c t i o na n df e a t u r ed e s c r i p t o r sb a s e do nc o n c e n t r i cs p h e r ep a r t i t i o n t h e s et w ot y p e so f e x t e n d e df e a t u r ed e s c r i o t o ri m p r o v e d f e a t u r e d e s c r i p t o r sb a s e d o ns i n g l es p h e r i c a lf u n c t i o nf r o mt w oa s p e c t sa n dt h o s e t w om e t h o d sc o u l db ei n t e g r a t e dt oc o n s t r u c tf e a t u r ed e s c r i p t o r sb a s e do n m u l t i p l es p h e r i c a lf u n c t i o ns e q u e n c e t h i sp a p e rp r e s e n t e dt h e b a s i c f l a m eo ff e a t u r ee x t r a c t i o na l g o r i t mo ft h o s et y p e so ff e a t u r ed e s c r i p t o r t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h o s et w om e t h o d sc o u l di m p r o v e r e t r i e v a lp e r f o r m a n c eo ff e a t u r ed e s c r i p t o r , a n dt h ef e a t u r ed e s c r i p t o r b a s e do nm u l t i p l es p h e r i c a lf u n c t i o ns e q u e n c eh a dt h eb e s tr e t r i e v a l p e r f o r m a n c e k e yw o r d s3 dm o d e lr e t r i e v a l ，s p h e r i c a lh a r m o n i c s ，s p h e r i c a l f u n c t i o n ，f e a t u r ed e s c r i p t o r , c o n c e n t r i cs p h e r ep a r t i t i o n 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：盔烈日期：世年羔月堑日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 日期：2 翌量一年上月型，- 日 硕士学位论文 第一章绪论 第一章绪论 随着三维模型扫描设备和交互式建模工具的快速发展和广泛使用，近年来三 维模型的数量快速增长。三维模型在众多领域内发挥了重要的作用，而互联网的 发展使得三维模型被广泛传播，很多大型三维模型数据库相继出现，如何从这些 数据库中获取所需的三维模型成为一个迫切需要解决的问题。本文以基于球面调 和变换的特征提取算法为研究对象，对三维模型检索的关键技术进行了详细的研 究。在本章中，主要阐述了基于内容的三维模型检索的课题背景和研究现状，并 简单地介绍了本文的主要工作及章节安排。 1 1 课题背景 互连网的发展给人们提供了巨大的信息资源，信息处理从传统模式向新型 模式转变，信息检索的对象已经从单一的文本信息发展为二维图象等多媒体信 息以及更为真实丰富的三维模型和三维场景等虚拟媒体信息，如何快速、准确 地查找自己所需要的资料成为计算机和互连网发展过程中的一个重要课题。2 0 世纪9 0 年代以来，为检索图象、音频、视频等多媒体信息，出现了基于内容的 多媒体检索( c o n t e n t b a s e dm u l t i m e d i ar e t r i e v a l ) 技术，并且很快在理论研究和实 际应用中得到迅速的发展1 1 ，2 一。虽然针对文本、图象、音频等多媒体信息的检 索在互连网上已经很平常了，但是对三维模型数据的检索还处在萌芽阶段。 然而以下的几条趋势将使得三维模型数据在未来几年问大量增加，象文本、 图象、音频、视频等其他多媒体数据一样无处不在【4 5 6 1 ：、 ( 1 ) 新的3 d 模型扫描设备和大量的交互式建模工具使得创建3 d 模型变得 可行、简单和高效。 ( 2 ) 用户级图形硬件的发展速度越来越快( 达到摩尔定律的3 倍速度) ，每 秒可处理的多边形数量大大增加，使得三维模型被越来越多的人们所需求。 ( 3 ) 互连网技术的发展使得三维模型被广泛传播，很多大型三维模型数据 库相继出现。 ( 4 ) 三维模型在现实中的应用越来越广，如计算机辅助设计( c a d ) 、计算机 辅助制造( c a m ) 、虚拟显示( v i r t u a lr e a l i t y ) 、3 d 游戏、动画制作、影视特效制 作、分子生物学、医学等领域。， ( 5 ) 人的视觉感知具有立体的、三维的特性，三维模型及其组成的三维场 景能提供比二维图象更多、更丰富的视觉感知细节。 硕士学位论文 第一章绪论 这些发展趋势改变了我们对三维数据的看法。多年前，如何去创建有趣的三 维模型是计算机图形学界面临的首要问题。然而在现在和不久的将来，关键问题 将从“我们如何去创造三维模型 转化为“我 f i n n 何去找到所需要的三维模型 【7 l 。例如一个人想对城市的某个场景建立一个三维虚拟世界，那么他将需要整个 场景中所有物体的三维模型，如汽车、房屋、路灯、各种交通路牌等等。一种方 法是购买一个三维模型建模工具然后自己去创建这些模型，另一种方法是通过互 联网从一个三维模型数据库中获取所需要的模型。显然第二种方法要省时省力， 如果能对已有的三维模型进行复用的话，将节省大量开支。据统计，在c a d 领 域，2 0 0 1 年已有三维模型的造型已达到6 6 ，虱j 2 0 0 5 年末，达到8 0 【引。 。 因此，如何快速、准确地从三维模型数据库中检索所需的三维模型，如何 有效地描述三维模型的特征，吸引了众多研究机构和研究者的注意，并成为了 计算机图形学界的一个研究热点。同时，m p e g 7 国际标准中规定：多媒体数据 除包括二维媒体信息外，还包括三维模型及三维场景等虚拟媒体信息 9 1 。 要在一个大型数据库中找到适合的三维模型，基于内容的三维模型检索是一 种必要的技术手段。基于内容的三维模型检索是指根据三维模型的某些特征进行 检索，它能从数据库中查找到具有指定特征或含有特定内容的三维数据，在三维 模型应用的各个领域中都能起重要作用。 研究现状 三维模型检索的关键问题是如何描述三维模型的特征。当然，最简单的方 法是通过关键字，使用文件名、标题、或者是背景来描述三维模型。现有的许 多三维模型检索网站主要依靠文本关键字检索和目录浏览两种手段，如3 dc a f e 三维模型库( h t t p ：w w w 3 d c a f e t o m ) 以及m e s h n o s e 三维模型搜索引擎 ( h t t p ：w w w d e e p f x c o m m e s h n o s e ) 。基于关键字方法的不足之处在于仅用几个关 键字难以对复杂的三维模型进行充分描述，关键字的录入需要人手工进行，依 赖于输入者的年龄、知识结构、性别等因素，具有很大的主观性和片面性，可 靠性和效率都不高，无法适应当前三维模型数量爆炸式增长和互连网搜索引擎 规模与复杂性日益增强的情况1 4 ，姗。因此遵循图象、音视频检索技术的发展历 程，基于内容的三维模型检索技术成为目前三维模型检索研究的热点。 近年来，基于内容的三维模型检索一直是国内外图形学界的一个热点和难 点。1 9 9 7 1 9 9 8 年，加拿大国家研究院( n a t i o n a lr e s e a r c hc o u n c i l ) l 均p a q u e t t l l ，1 2 1 首次提出了在大型通用三维模型数据库中进行基于内容的三维模型检索，对基于 内容的三维模型检索进行了理论和算法上的研究，并开发了第一个三维模型检索 的原型系统。随后美国的普林斯顿大学( p r i n c e t o nu n i v e r s i t y ) 、卡耐基梅隆大学 2 硕士学位论文 第一章绪论 ( c a r n e g i em e l l o nu n i v e r s i t y ) 、华盛顿大学( w a s h i n g t o n gu n i v e r s i t y ) 、布朗大学 ( b r o w 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 ) 、德国的慕尼黑大学( m u n i c h u n i v e r s i t y l 、波恩大学( b o n nu n i v e r s i t y ) 、n e c 美国研究院、h p 以色列海法研究 院、i b m 日本东京研究院以及国立台湾大学等著名高校和研究机构都相继对基于 内容的三维模型检索技术进行了研究，提出了一系列的三维模型相似度匹配算 法，发表了大量基于内容的三维模型检索技术的论文，同时还开发了数个采用不 同相似度匹配算法的三维模型搜索引擎。国内的如浙江大学、北京大学、南京大 学、北京微软研究院等也于这几年对三维模型检索进行了研究。 基于内容的三维模型检索首先从三维模型数据中自动计算并提取出三维模 型的特征，如形状、空间关系、材质的颜色及纹理等，建立三维模型的多维信息 索引，然后在多维特征空间中计算待查询模型与目标模型之间的相似程度，实现 对三维模型数据库的浏览和检索【4 1 0 l 。基于内容的含义就是试图利用反映三维模 型视觉特征的内容信息自动建立特征索引，达到检索三维模型的目的。 美国普林斯顿大学是国际上最早对通用领域的三维模型检索系统进行研究 的机构之一，他们经过了多年的研究，提供了一个比较完整的三维模型检索系统。 该检索系统共有3 6 0 0 0 个模型，其中包括从互联网上下载的免费三维模型3 1 0 0 0 个和5 0 0 0 个商业三维模型。普林斯顿大学提供的三维模型检索系统的体系结构大 致如图1 1 所示【7 , 1 0 ，主要包括了爬虫系统、三维模型数据库、索引数据库、三维 模型相似性比较模块和用户查询界面。 一 一 离线 一_ - 一一一- 在线 用户= = 图1 1 普林斯顿大学三维模型检索系统框架 爬虫系统从网络上自动搜索并下载三维模型文件，扩充三维模型数据库的容 量；三维模型数据库存储各种三维模型文件，普林斯顿大学三维模型检索系统的 三维模型数据库有3 6 0 0 0 个三维模型；三维模型索引数据库存储三维模型的文本 索引、图像索引和三维模型索引，文本索引是三维模型的文本描述信息，图像索 引是三维模型的二维平面轮廓特征信息，三维模型索引是三维模型的几何特征信 3 硕士学位论文第一章绪论 息；三维模型相似性比较模块包含了这三种索引的相似性比较方法，分别是文本 相似性比较、图像相似性比较和三维模型相似性比较。 用户界面是三维模型检索系统的用户接口，直接影响检索系统的使用效果和 检索性能。三维模型中所包含的内容信息比图像等二维媒体更加丰富，因此，基 于内容的三维模型检索系统一般具有多种检索方式。如图1 2 所示，普林斯顿大 学的三维模型检索系统提供了4 种的三维模型检索方式，分别是： ( 1 ) 基于关键字的三维模型检索。输入关键字便可以查找相关模型。 ( 2 ) 基于用户交互式绘制的二维草图的三维模型检索。用户绘制想要查询模 型的1 3 个平面草图，检索系统根据用户提供的草图进行检索。 ( 3 ) 基于用户交互式绘制的三维草图的三维模型检索。用户绘制想要查询模 型的三维草图，检索系统根据用户提供的草图进行检索。 ( 4 ) 直接提供三维模型实例作为检索请求，该模型可以是用户上传到检索服 务器的新模型文件，也可以是某次检索结果集中的任个三维模型。 同时用户还可以采用多方式结合起来检索三维模型，例如用户可以同时提供 关键字和二维草图进行三维模型检索，然后在检索结果中选择适当的三维模型进 行精化检索，以此来检索自己最感兴趣的三维模型。 ( a ) 文本查询( b ) 2 d 轮廓查询 ( c ) 3 d 轮廓查询( d ) 3 d 模型查询 图l 一2 普林斯顿大学三维模型检索系统的用户查询界面 4 硕士学位论文 第一章绪论 1 3 本文的主要工作及意义 基于内容的三维模型检索涉及计算机视觉、模式识别、人机交互、信号处 理、人工智能和认知科学等诸多研究领域，它的研究内容主要包括预处理、特 征提取、相似性度量、查询接口的设计等，其中特征提取是研究的关键和基础。 本文主要对基于球面调和变换的三维模型特征提取算法进行了研究，主要工作 包括如下三个方面： ( 1 ) 基于球面调和变换的三维模型特征提取算法的关键是定义反映三维模 型某些特征的球面函数。本文从三维模型空间分布的基本特征出发，定义了4 种球面函数，从不同角度描述了三维模型。对这4 种球面函数进行球面调和变 换，在此基础上构建了4 种基于单球面函数的特征描述符。 ( 2 ) 基于单球面函数特征描述符均只考虑了三维模型某一方面的特征，获 得的检索性能有限。针对此问题，本文提出了两类扩展的特征描述符：基于多 球面函数的特征描述符和基于同心球壳划分的特征描述符。这两类特征描述符 从两个方向对基于单球面函数的特征描述符进行了扩展：基于多球面函数的特 征描述符利用多个球面函数的球面调和系数来构建特征向量，基于同心球壳划 分的特征描述符将单个球面函数分解为一系列分布在各个球壳内的球面函数， 利用这个球面函数序列的球面调和系数来构建特征向量。同时这两种扩展方法 还可以结合起来构建基于多球面函数序列的特征描述符。本文提出了这三类特 征描述符的提取框架和具有多分辨率特性的特征向量的构建方法，并在第三章 定义的4 种球面函数的基础上构建了大量的复合特征描述符。 ( 3 ) 构建了三维模型检索实验原型系统，该实验原型系统能评估三维模型 检索算法的检索性能。使用该系统对本文提出的特征描述符进行了三维模型检 索实验，考察了这些特征描述符的检索性能和鲁棒性。最后本文还比较基于 c p c a 构建的特征描述符与基于球面调和变换旋转不变量的特征描述符的检索 性能。 1 4 论文组织结构 本文的组织结构如下： 第一章，绪论。阐述课题背景、研究现状、本文的主要工作及意义和文章 组织结构。 第二章，三维模型检索算法的研究。对三维模型检索三个步骤进行了综述， 首先描述了模型坐标标准化和预处理；然后分析和总结了目前已有的三维模型特 硕士学位论文第一章绪论 征提取算法，根据算法所使用的特征信息，我们将这些算法所构建的特征描述符 分成四类：基于统计特性的特征描述符、基于视觉投影的特征描述符、基于拓扑 结构的特征描述符和基于几何结构分析的特征描述符；对相似性匹配进行了综 述，给出了一些常见距离度量函数；最后描述了本文所使用的三维模型检索测试 数据库和性能评价指标。 第三章，基于球面调和变换的特征提取算法。首先描述了球面调和变换及其 在三维模型检索中的应用，给出了基于球面调和变换的特征提取算法的框架。然 后利用三维模型网格的空间几何特征定义了4 种球面函数，从不同角度描述了三 维模型。对这4 种球面函数进行球面调和变换，在此基础上构建t 4 种基于单个球 面函数的特征描述符。 第四章，基于多球面函数和同心球壳划分的特征提取算法。针对基于单个球 面的函数特征描述符只考虑了三维模型某一方面的特征，获得的检索性能有限的 问题，提出了两类扩展的特征描述符：基于多球面函数的特征描述符和基于同心 球壳划分的特征描述符。这两类特征描述符从两个方向对第三章的特征描述符进 行了扩展，然后结合这两种方法构建了基于多球面函数序列的特征描述符。 第五章，三维模型检索实验。考察了本文提出的特征描述符的检索性能和 鲁棒性，还比较了基于c p c a 构建的特征描述符与基于球面调和变换旋转不变 量的特征描述符的检索性能。 第六章，总结及展望。总结本文工作，并指出未来进一步的研究的方向。 6 硕士学位论文第二章三维模型检索算法的研究 第二章三维模型检索算法的研究 三维模型检索过程可分为三个步骤1 1 3 j ：标准化( n o 册a l i z a t i o n ) 和预处理 ( p r e p r o c e s s i n g ) ；特征提取( 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 ) rs e a r c h ) 。本 章从这三个方面对三维模型检索算法进行综述，最后还描述了评价三维模型检索 算法性能的方法和指标。 2 1 模型坐标标准化和预处理 三维模型检索算法有一个很重要的特性：对于三维模型检索系统来说，同样 的三维模型在不同的坐标系下应该具有相同的相似度，这就要求提取出的特征描 述对平移、旋转、缩放和翻转变换具有不变性。 。目前，实现特征描述不变性的方法主要有二种【1 4 1 j ( 1 ) 对三维模型坐标进行标准化，计算三维模型的标准化坐标框架，然后在 该坐标框架中进行特征提取。此方法的基本思想是依据模型的质心和主轴来对齐 三维模型。首先计算出模型的质心和主轴，然后三维模型被平移，使得模型的质 心移动到标准坐标系的原点以获得平移不变性( t r a n s l a t i o ni n v a r i a n c e ) ，然后将模 型绕原点旋转，使得模型的主轴与标准坐标系魄y 、y 、z 轴对齐以获得旋转不变 性( r o t a t i o ni n v a r i a n c e ) 。翻转不变性( f l i p p i n gi n v a r i a n c e ) 可以通过基于矩测试的方 法翻转模型来获得，最后还可以通过将旋转后的三维模型归一化至标准单元大小 以获得缩放不变性( s c a l i n gi n v a r i a n c e ) 。一个完整的三维模型坐标标准化过程可以 表示为如下的几何变换f ：f ( ，) = s - 1 f r o ( 1 一c ) 【1 4 1 ，其中s 是放缩系数，腥一 个对角阵形式的翻转矩阵，r 为旋转矩阵，伪原始模型坐标，c 为模型的质心。 坐标系旋转归一化预处理是三维模型坐标标准化中最难解决的问题。为获得 旋转不变性，需要计算出三维模型的主轴。当前最常用的计算主轴的方法是主元 分析法p c a ( p r i c i p a lc o m p e n ta n a l y s i s ) i i s , 1 6 1 ，也叫做离散k a r h u n e n l o e v e 变换或 h o t e l l i n g 变换。然而传统p c a 变换以三维模型的顶点作为分析对象，没有考虑组 成三维模型的三角形网格之间的大小差异，因此，有可能对相同的三维模型产生 不同的标准化坐标，从而影响检索的准确性【1 4 1 。p a q u e t i l 等人计算出每个三角形 网格的质心，用其代替相应的顶点，然后再对该集合进行p c a 变换：而h e c z k o i l 列 等人则通过为三维模型的各个顶点设定权值，生成一个加权的顶点集合的方法来 解决这个问题。v r a n i c 等人i l3 l 则将三维模型表面看作一个无限点集，提出了在三 7 硕士学位论文 第二章三维模型检索算法的研究 维模型网格表面进行积分来获得三维模型空间分布协方差矩阵的连续主元分析 法c p c a ( c o n t i n u o u sp c a ) ，求取的主轴具有较好的鲁棒性，被很多特征提取算法 所采用。本文提出的特征描述符也采用连续主元分析法来获取旋转不变性。 ( 2 ) 定义并提取本身具有不变特性的特征描述。f u n k h o u s e r 等人提出基于球 形调和函数( s p h e r i c a lh a r m o n i cf u n c t i o n ) 的特征描述符具有对坐标旋转的不变性 研，k a z h d a n u 9 , 2 0 等人提出的反射对称特征描述符具有对平移和缩放的不变性， s u z u k i 【2 1 】等人提出的特征描述符对绕坐标轴9 0 度整数倍的旋转变换保持不变性。 但是这些特征描述符所具有的空间变换不变性大都是不全面的，而且，大多数这 类特征描述符的计算也需要在一个标准化的坐标系内完成。因此为了迸一步提高 检索的准确性，往往也需要进行模型坐标标准化。 k a z h d a n 等在文献中提出了对三维模型进行各向同性预处理的观剧2 2 l 。在 物理学中，各向异性表示物体在各个方向的性质不一样，例如纯净的水晶在各个 方向的导热率不一致，各向同性表示物体在各个方向的性质一样，例如普通玻璃 在各个方向的导热率一致。k a z h d a n 把各向同性和各向异性的观点应用于三维模 型几何相似性比较中，在特征提取之前，对三维模型进行各向同性预处理，使得 三维模型的几何特征在各个方向上大小一致，提高了三维模型检索算法的性能。 2 2 三维模型的特征提取算法综述 三维模型的基本属性有形状、材质和颜色，形状属性是比较稳定的，而形状 相同的物体可以有不同的材质，物体的颜色又受到材质和光照的影响，因此目前 大部分三维模型相似性比较算法以形状属性作为特征，基于形状的三维模型检索 是目前三维模型检索领域的研究热点。 当前大多数的研究工作主要针对三维模型的几何形状特征。一个理想的形状 特征描述符( s h a p ef e a t u r ed e s c r i p t o r ) 应该具有如下的特点【17 2 1 , 2 4 , 2 5 , 2 6 1 ：( 1 ) 对三维 模型的朝向和封闭性没有限制。( 2 ) 不受异常网格的影响( 如重叠点、重叠三角 形、退化三角形等。( 3 ) 对平移、旋转、缩放、反射对称等空间变换具有不变性。 ( 4 ) 对各种细节层次( l e v e lo f d e t a i l ) 和不同细分方式的三维模型来说足够健壮。( 5 ) 对三维模型表面的噪声、形变和任意的拓扑退化具有较强的鲁棒性。( 6 ) 多分辨 率特征描述。( 7 ) 快速特征提取。( 8 ) 特征维数低，易存储。( 9 ) 易索引，能方便地 组织索引结构，以加快检索过程。( 1 0 ) 对三维形状信息的描述和分辨能里强。 一个完整的三维模型通常包含数千个顶点，如果逐个顶点就进行比较，将 花费大量的时间，因此必须对三维模型进行抽象，提取并存储三维模型的特征， 建立特征描述符，然后通过比较三维模型的特征描述符来描述三维模型的相似 程度，通常使用一个多维特征向量来描述三维模型的特征。 8 硕士学位论文第二章三维模型检索算法的研究 根据提取的特征信息，特征描述符可以分为如下几类： ( 1 ) 基于统计特征的特征描述符。基于统计特征的特征提取算法首先对三维 模型的某个特征信息进行统计，获得统计直方图，然后量化统计直方图来构建特 征描述符，通过计算特征描述符之间的相似距离来比较三维模型的几何相似性。 常用的统计信息有三维模型的表面积分布、体积分布、几何矩分布以及顶点数分 布等。 ， p a q u e t 等人【1 2 l 提取包含颜色直方图、法线向量直方图以及材质直方图的三维 形状直方图特征。a n k e r s t 等人 2 6 1 将三维模型的包围空间分割成不同的区域，然 后对三维模型表面进行均匀重采样，统计落入各个区域的采样点的数量，形成统 计直方图，然后构建特征描述符。s u z u k i 等人【2 l 】首先运用主元分析法将三维模型 旋转至规范坐标系，然后把三维模型的包围盒均匀划分为n x n x n 个单元格，将 围绕x 、】，z 轴旋转9 0 度后能重合的单元格作为一类，通过统计每类单元格中顶 点个数得到三维模型的统计直方图。o s a d a 等人在文献中提出形状分布( s h a p e d i s t r i b u t i o n ) 特征描述符【2 7 1 ，基于三维模型的特定形状函数值的分布情况提取形状 特征。v a n d e b o r r e 将三维模型网格面和坐标系原点组成的锥体体积、网格面的主 曲率和网格面之间的表面距离分别作为直方图的统计量【2 8 1 。t a n g e l d e r l 2 9 1 使用三 维模型的高斯曲率和法向量变化率等特征作为直方图的统计量。p a n 等提出一种 径向夹角直方图【3 0 】，通过对三维模型表面进行随机采样获得采样点集合，计算采 样点的径向与表面法向夹角来构造旋转不变的统计直方图。 矩做为一种特征描述在图象检索和分类中得到了广泛的应用，因此很多研究 人员也提出了大量基于矩的三维模型特征提取算法。如e l a d t 3 l 】假设三维模型是由 其表面包围的空心模型，基于其表面信息计算三维几何矩特征作为特征描述符。 c a n t e r a k i s 在理论上将z e m i k e 矩从二维推广至三维1 3 2 1 ，三维z e m i k e 矩是三维模型 函数在一组正交函数上的投影，表达形式简单，具有良好的检索性能。李宗民等 【3 3 】在传统的几何矩定义的基础上进行扩展，提出了结构矩的定义和计算，其实质 是对原有几何矩定义中的密度函数经过变换得到新的密度函数。在此基础上定义 的不变矩突出或者扩大了形状之间的差别，提高了特征描述符的检索性能。李宗 民掣3 4 l 通过扩展二维极半径矩到三维的情况，提出了三维极半径矩，证明了三维 极半径矩具有平移、缩放和旋转不变性，可用于三维模型的比较和识别。 基于统计特征的三维模型特征描述符计算较为简单，具有良好的空间变换 不变性，但是这些特征描述符的特征描述能力普遍不强，检索性能相对较差。 ( 2 ) 基于视觉投影的特征描述符。基于视觉投影的特征描述符首先将三维模 型投影到二维平面，再对二维投影信息提取特征向量。 h e c z k o 等人【l8 】先用p c a 变换对三维模型进行坐标标准化预处理，然后在规范 9 硕士学位论文 第二章三维模型检索算法的研究 坐标系中将三维模型栅、勉币 i y z = 个平面进行投影，获得3 个二维轮廓信息， 对每个轮廓进行采样，从轮廓图的中心向轮廓等角距发射射线，计算中心到轮廓 的距离作为采样值，然后对采样值进行傅立叶变换，利用获得的傅立叶系数构建 特征描述符。该方法计算简单，但其将三维模型仅仅视为3 个规范二维投影的组 合，不能很好地反映出三维模型的空问结构信息，检索性能不高。为此，h e c z k o 等人对其加以改进，提出了一种基于深度图的特征描述符，在进行二维投影的过 程中，将三维模型的深度信息通过投影区域的灰度值加以体现，然后，对二维深 度图进行二维傅立叶变换，利用获得的傅立叶系数构建特征描述符，提高了三维 模型检索效率。 f u n k h o u s e r 等人1 7 , 1 0 】用1 3 个从特定角度投影获得的二维轮廓图表示三维模型 ( 如图2 1 所示) ，对这些二维轮廓图用d t ( d i s t a n c et r a n s f o r m ) 转换成二进制的灰度 图象并将离散到一组同心圆上，重构一组同心圆上的函数序列，对该函数序列进 行傅立叶变换得到最终的特征描述，特征提取过程如图2 2 所示。用户向查询系 统提交一个或多个二维轮廓草图，模型的匹配在草图与1 3 个二维草图之间进行。 图2 1 牛在1 3 个特定视角下的二维投影轮廓图 图2 2 三维模型二维轮廓图的特征提取 o h b u c h i l 3 5 1 将三维模型在4 2 个视点方向上做f 交深度投影，计算每个正交深 度图的通用傅立叶描述子g f d ( g e n e r i cf o u r i e rd e s c r i p t o r s ) ，然后使用计算得到的 g f d 来构建特征描述符。c h e n 等人提出的基于视觉相似性的特征提取算法【3 6 1 的 基本思想是如果两个三维模型是相似的，那么从他们的各个角度看，必定都是相 l o 硕士学位论文第二章三维模型检索算法的研究 似的。该算法使用定义在三维模型包围球上的正十二面体2 0 个顶点上的照相机获 得2 0 个视图。由于相对于坐标原点对称的视图具有相同的投影，所以使用1 0 个视 图组成一个光场描述子。使用二维z e m i k e 矩特征和二维f o 证e r 特征来比较视图的 相似性，为了消除匹配错误，文中对光场描述子进行全排列对应，分别计算距离， 取最小距离来作为相似度。 普建涛等提出了一种基于二维多边形集相似性的特征提取算法 3 7 1 ，使用一个 平面沿着切割方向逐步与模型进行相交求解，得到一系列交点，组织成二维多边 形集。为了度量二维多边形集的相似性，采用了形分布的思想，对二维多边形集 进行均匀采样，归一化后使用广义的欧氏距离计算相似性。 基于视觉投影的三维模型特征描述符较好地符合了人对三维模型的外观感 觉，对三维模型噪声、简化、细分具有较好的鲁棒性，在三维模型检索中得到了 较为广泛的应用。 ( 3 ) 基于拓扑结构的特征描述符。拓扑结构相同的2 个三维模型在几何形态 上可能有较大的差别，但是它们却表示同一个物体在不同时间、地点所具有的不 同形态。如图2 3 右边的2 只青蛙，如采用基于几何结构、统计和视觉投影的特征 提取算法进行检索，会将他们视为不同的三维模型。当需要检索系统将这2 个模 型看做是同一个模型时，就需要采用基于拓扑结构的特征提取算法。基于拓扑结 构的三维模型特征描述符通过比较三维模型的拓扑结构来获得三维模型几何相 似性，通常使用的拓扑结构信息包括三维模型的分支、连通性等。 图2 3 两只形态不同的青蛙及多分辨率r e e b 图的构建过程 目前，描述三维模型拓扑结构的方法主要有r e e b 图方法和中轴线方法。r e e b 图从连通区域的角度来计算三维模型拓扑结构，而中轴线方法则从分支的角度来 计算三维模型的拓扑结构。 h i l a g a l ：强】等人基于网格点的测地距离( g e o d e s i cd i s t a n c e s ) ，使用多尺度r e e b 图( m u l t i r e s o l u t i o nr e e bg r a r h ) 来表示三维模型拓扑结构。表面测地距离是三维模 型两个顶点在模型表面的最短距离，它不仅可以有效的克服三维模型噪声的干 扰，而且与三维模型的坐标系方向无关。r e e b l 蛩 3 9 1 是一种使用连续函数变换而 产生的三维物体骨架信息的描述方式。h i l a g a 对三维模型的表面测地距离进行不 硕士学位论文 第二章三维模型检索算法的研究 同密度的划分，得到三维模型的多尺度r e e b 图，通过多尺度r e e b 图来比较三维模 型的几何相似性。图2 3 左边所示是一个多分尺度r e e b 图的构造过程，该方法能 有效描述三维模型的拓扑结构，对于模型的形变具有较强的鲁棒性，并能逐步精 化检索。 ， 中轴线图又称骨架图，在计算机图形学、计算机视觉等领域得到了广泛的应 用，用来表达三维模型的拓扑结构。s u n d a r 等人提出的基于骨架图的特征描述符 删，采用基于参数控制的细化算法对模型进行骨架提取，计算出模型的骨架节点， 根据得到的节点来构造骨架图。 “ 潘翔等提出了一种基于分割技术的拓扑连接图构造算法，并用于三维模型检 索【4 。首先构造多层邻域计算用于度量每个三角片平坦度的信号值，根据信号值 采用一种改进的分水岭方法把模型分割成不同的曲面片，利用这些曲面片之间的 连接关系构造拓扑连接图。通过比较拓扑连接图的相似性进行三维模型检索。 目前，已有的基于拓扑结构的三维模型特征提取算法具有较大的局限性：对 三维模型有比较苛刻的要求，可计算性较差；对于模型表示中的轻微干扰和噪声 十分敏感；计算复杂度高；不能有效的比较三维模型的轮廓相似性。 ( 4 ) 基于几何结构分析的特征描述符。此类特征描述符描述了三维模型在几 何空间中的分布特征。 、。 v r a n i c 等人在文献中提出了一种基于射线( r a y b a s e d ) 的形状特征描述符1 1 4 1 ， 以三维模型表面在给定空间方向上与坐标原点的最远距离作为特征值。k a z h d a n 等人提出一种三维模型对称特征1 1 9 , 2 0 ，用于描述三维模型反射和旋转对称的球函 数集合。反射对称和旋转对称都是关于过质心任意轴的对称，文中同时说明通过 使用球面调和变换可以提高对称特征的计算速度，并给出了对称特征的快速计算 方法。在实验中，可以看到对称特征不仅可以单独作为三维模型检索的特征，还 可以与其他特征结合来提高检索性能。 可以直接使用空间域的采样信息来构建特征描述符，也可以将空间域的采样 信息变换到频率域中，利用频域系数来构建特征向量。v r a n i c 等人基于三维傅立 叶变换的方法提取三维模型的特征i 4 2 1 ，首先对三维模型进行规范化和体素化处 理，得到三维模型的包围立方体( b o u n d i n gc u b e ) ，然后把包围立方体均匀划分为 n x n x 份，统计每个格子里的三维模型表面积与模型总表面体的比例，这些比例 值就是进行傅立叶变换的采样值。使用得到的傅立叶频谱系数来构建特征向量， 计算特征向量之间的绝对值距离和欧氏距离作为相似度。v r a n i c 的测试表明，傅 立叶变换检索技术具有较好检索效率，但是计算速度较慢。另外，除了直接使用 傅立叶变换外，还可以利用各种傅立叶描述子( f o u r i e rd e s c r i p t o r ) 作为三维模型的 特征描述符。傅立叶算子具有旋转不变性、缩放不变形，有些学者把傅立叶描述 1 2 硕士学位论文第二章三维模型检索算法的研究 子用于三位模型检索领域，取得了一定的效果。z h a n g 在其文献把短时傅立叶描 述子( s t f t s