（计算机软件与理论专业论文）三维模型检索技术研究及系统实现.pdf

摘要 数字多媒体技术、计算机视觉技术、三维图形硬件的飞速发展拓展了三维图 形的应用前景；三维扫描技术与造型工具的日益普及，扩展了可供使用的三维模 型数据库；互联网络的扩张增强了人们获取分散存储的三维模型的能力，并为有 效传播高质量模型创造了条件，因此对三维模型的检索技术的研究变得越来越必 要。 在对已有三维模型检索技术的进行系统研究的基础上，本文提出了两种基于 内容的三维模型检索技术。这两种检索技术是从三维模型的几何形状特征上来比 较三维模型。以下是本文在三维模型检索技术方面主要的工作： ( 1 ) 基于形状分布算法，提出了点对分类的形状分布算法。本算法将三维模 型上点对的连线按不同情况分为两类，然后分别构建形状分布直方图。 ( 2 ) 厚度图算法将三维模型的一个重要特征法向量作为一个因素加入到形状 特征提取当中。由于法向量的加入，对三维模型提取的特征曲线能够充分反映模 型的集合特征。 ( 3 ) 联合分布图将面的法向量相互间所成个角度作为一个新的因素考虑了进 来，从而形成了一个反映三维模型特征的密度图。 ( 4 ) 在三维模型特征匹配方面，本文研究了相似性的度量方法的数据模型， 提出了两种多特征组合的相似性度量结构，给出了本文所选用的相似性度量函数 和方法。 从实验结果看，这几种三维检索技术特征提取方法提取的特征向量都能很好 的区分不同的三维模型。本文设计实现了一个三维检索原型系统，是具有良好扩 展性的系统，实现了高速、有效的三维模型检索。 关键词：三维模型，三维模型检索，形状特征，特征提取，相似度计算 a b s t r a c t 3 dm o d e ld a t a b a s e sw i l lb e c o m eu b i q u i t o u sd u et of o l l o w i n gf a c t s f i r s t l y , i m p r o v e dd i g i t a l m u l t i m e d i at e c h n o l o g y , c o m p u t e rv i s i o nt h e o r ya n dg r a p h i c s p r o c e s s i n gu n i th a v ee x p a n d e dt h ea p p l i c a t i o n so f3 dg r a p h i c s s e c o n d l p o p u l a r i z e d m o d e l i n gt o o l sa n d3 ds c a n n i n gd e v i c e sa r em a k i n ga c q u i s i t i o no f3 dm o d e l se a s i e r a n dl e s se x p e n s i v e ，c r e a t i n gal a r g es u p p l yo fp u b l i ca v a i l a b l e3 dd a t as e t s s o r e t r i e v a li sb e c o m i n gm o r ea n dm o r en e c e s s a r y t h et w on e w3 dm o d e ls e a r c hm e t h o d sa r ep u tf o r w a r di nt h i st h e s i s t h e s et w o m e t h o d sa l lb e l o n gt os h a p e - b a s e dr e t r i e v a lt e c h n i q u e s b e f o r ee x t r a c t i n gf e a t u r ef r o m 3 dm o d e l ，w en e e dt od os o m ep r e - p r o c e s s i n g t h e nt h er e s e a r c ho fa l g o r i t h m so f3 d m o d e lr e t r i e v a li sd e v i s e df r o mt h ef o l l o w i n gt h r e ea s p e c t s ：( 1 ) t h ec l a s s i f i c a t i o no f p o i n t - p a i r si sp u tf o r w a r db a s e do ns h a p ed i s t r i b u t i o n t l l i sa p p r o a c hs e p a r a t e st h e p a i r so fp o i n t sb a s e do ng e o m e t r i cp r o p e r t i e so fl i n ec o n n e c t i n gt h e m n l ed i f f e r e n t k i n d so f1 i n e sc o n s t r u c td i f f e r e n th i s t o g r a m s ( 2 ) t h i c k n e s sh i s t o g r a ma d d st h en o r m a l o ft r i a n g l ei n t os h a p ef e a t u r e b e c a u s eo ft h i sn e wf e a t u r e ，t h i sa p p r o a c ha p p r o v e st o p e r f o r mb e n e rt h a ns h a p ed i s t r i b u t i o n ( 3 ) t h ec o m b i n e dd i s t r i b u t i o nc a l c u l a t et h e a n g l e sb e t w e e nt h en o r m a l t h ef e a m r er e p r e s e n t st h ed i s t r i b u t i o na tc e r t a i nn o r m a l a n dd i s t a n c 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 tt h ep r o p o s e dr e t r i e v a lm e t h o d sa r ee f f e c t i v ea n d e f f i c i e n t a sf o r s i m i l a r i t y m e a s l l r e m e mo f3 dm o d e l r e t r i e v a l ，t h i sp a p e r d e m o n s t r a t e st w od a t am o d e l sr e l a t e dt ot h es i m i l a r i t ym e a s l l r e m e n ta n dp r o p o s e st w o k i n d so fm u l t i f e a t u r ec o m b i n a f i o ns t r u c t u r e s s o m eo ft h ed i s t a n c ef u n c t i o n sf o r m e a s u r i n gm o d e ls i m i l a r i t yu s e di nt h i sp a p e ra r ec o m p a r e di nt h ep a p e rt o o t h i sp a p e rd e s i g n sa3 dr e t r i e v a ls y s t e m _ m e a s u r e 3 da st h et e s tb e df o r r e t r i e v a la l g o r i t h m s ，w h i c hi sa ne x p e r i m e n t a lf r a m es y s t e m t h e r e f o r e ，s o m ek e y i s s u e so f3 dm o d e lr e t r i e v a lf o rf u t u r er e s e a r c ha l ea l s od i s c u s s e da tt h ee n do ft h i s t h e s i s k e y w o r d ：3 dm o d e l ，3 dm o d e lr e t r i e v a l ，s h a p ef e a t u r e ，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 y c a l c u l a t i o n 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间论文7 - 作 的知识产权单位属于西北大学。学校有权保留并向国家有关部门或机构送交论文的复印件 和电子版。本人允许论文被查阅和借阅。学校可以将本学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时， 本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 学位论文作者签名：一闺丝彖 指导教师签名： f 司验 2 瞄年5 月，日年 月日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含 其他人已经发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：阎i 良朱 2 田了年6 月岁日 第一章绪论 1 1 研究的背景及意义 我们生活在一个三维的世界中，传统的照相技术只能获得三维物体的二维 影像，而无法精确的记录物体的三维几何特征。类似于二维数码图像可以看作利 用离散像素来逼近物体在照相机胶片上的投影，三维模型的一种最基本的表示形 式是利用大量多边形来逼近真实三维物体的几何。除此之外，三维模型还有其他 多种表示形式，如利用诸如长方体等基本体紊进行布尔运算来构造复杂三维几何 体的c s g 表示形式；用非均匀有理b 样条( m 瓜b s ) 等基于b c m s t e i n 基函数的样 条曲面表示形式：利用二值化的三维数组对模型几何特征进行描述的体素化表示 形式等等。在各种三维模型的表示形式中，多边形表示形式无疑是最直观，最简 单的一种，因此其他三维几何表示形式往往需要预先转换到这种最基本的表示形 式以获得统一的处理。本文的各个算法也均建立在三维模型的多边形表示形式， 值得指出的一点是，最常见的三维模型数据格式t m i 等，并没有给出模型表 面流形的定义。构成三维模型的大量多边形并没有紧密拼接，而是形成多边形汤 ( p o l y g o n s o u p ) 的无组织散乱分布，在很大程度上不方便利用已有的信号处理 方法对这种表示形式的三维模型进行处理。由于填充三维模型表面的大量“漏洞” 是一个开放性难题，因此，人们希望在建模过程中尽可能保证组成三维模型表面 的多边形紧致( w a t e r - t i 曲t ) 拼接，从而形成可定义流形的多边形网格结构，这 就是三维网格模型的基本概念。 计算机信息检索技术作为信息采集的重要方法和手段已有几十年的发展历 程。随着i n t e m e t 的发展，信息处理从传统模式向新型模式转变。信息检索的对象 已经从单一的文本信息发展为二维图像等多媒体信息以及更为真实丰富的三维 模型和三维场景等虚拟媒体信息。人们对信息检索工具的依赖日益迫切，并且规 模与复杂性日益加强。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 ) 技术应运 而生，并很快在理论研究和实际应用中得到迅速发展i t , 2 i 。 在计算机辅助设计( c a d ) 和计算机辅助制造( c a m ) 领域，利用数字图 像来表示待加工的机械零件，只能给人们提供一个外观结构的显示，但并不包含 足够的可供加工的几何信息。而用三维模型来表示机械零件的几何结构，就可以 完全记录零件的几何信息，使得自动来料加工成为可能。类似地，三维模型在建 筑设计，艺术设计，工业工程，家居装修等需要大量处理三维几何信息的领域， 都有着广泛的应用前景。 在科学技术领域，以分子生物学为代表的基因技术将成为2 l 世纪的领头羊， 基础研究的热点从基于p c r 技术的基因测序，利用限制性内切酶进行基因重组 等传统基因技术，逐渐转向了以结构基因组学为代表的后分子生物学时代。结构 基因组学关注的问题是，从基因序列到具有活性的蛋白质产生，往往肽链要经过 多次切割，重组，才能最终形成具有特定空间形态的蛋白质三维结构，从而具有 生物活性。一般来说，酶在同靶分子作用时的动态三维结构最终决定了它在催化 反应中的功能，一旦蛋白质由于受热或受到重金属离子影响而破坏了特定的三维 空间结构，其特定的功能也就丧失，尽管氨基酸序列并没有发生变化。因此，测 定蛋白质的三维结构，对探索生命过程最根本问题是十分有意义的。 目前常用的测定蛋白质三维结构的技术手段包括对蛋白质进行纯化、结晶基 础上利用x 射线衍射学对晶体空间结构进行测定，还包括在液相中测定空间结构 的核磁共振等方法。利用这些方法测定的数据形成了蛋白质结构数据库，如何在 数据库中进行检索，如何根据已有的知识，根据结构预测蛋白质的功能，如何根 据结构功能的关系设计新药就成了生物信息学研究的内容。从上面我们可以看 到，三维几何建模技术，特别是对大分子空间结构的描述，在生命科学基础研究 领域，同样具有良好的应用前景。 在医学方面，c t 和核磁共振是常用的人体疾病探测手段，并在此基础上发 展了交互式外科技术。外科医生可以在三维显示系统的引导下，进行胸内，颅内 各种复杂条件下的手术。颅内手术包括利用1 刀对脑体内部肿瘤进行切除，内 常见的包括冠状动脉搭桥术等高难度手术。这些应用均促进了三维几何结构的描 述，可视化技术和人机交互等三维视觉计算领域的研究。西北大学可视化研究所 在这方面作了深入的研究，如在人脑的虚拟内窥镜技术和计算机辅助颅像重合计 算的研究上取得了显著的成果。 三维建模在文物保护中也发挥着重要的作用。前面已经提到，三维模型的特 点是可完整反映真实物体的三维几何。因此，对于一些珍贵的三维模型，由于年 代久远面临着风化，碎裂，受潮变形等危险。建立它们精确的三维模型有备无患 是十分必要的。西北大学可是化研究所利用激光扫描技术，重建了兵马俑头的三 维模型，在文物保护领域做出了良好的示范性作甩。 人类的视觉感知具有立体的、三维的特性。三维模型及其组成的三维场景能 提供比二维图像更多、更丰富的视觉感知细节。随着三维数据获取技术、三维图 形建模方法及图形硬件技术的发展，已经产生了越来越多的三维物体模型库，如 虚拟现实环境( v i r t u a lr e a l i t y ) 、三维游戏( 3 d g a m e ) 等等。在互联网上，也涌现出 越来越多的三维模型库 ”。由于进行高逼真度的三维建模非常费时费力，如果能 对已有的三维模型进行复用的话，将节省大量开支。因此，如何有效地对三维模 型及其场景进行浏览和检索，开始吸引众多研究者的注意，并日益成为一个研究 热点p 。在m p e g7 国际标准中也已规定，与之相关的媒体数据除包括二维媒体 信息外，还包括三维模型及三维场景等虚拟媒体信息【4 1 。 现有的许多三维模型检索网站主要依靠文本关键字检索和目录浏览两种手 段，这些方法的不足之处在于仅使用几个关键字难以对复杂的三维模型和场景进 行充分描述。此外，关键字选取具有很大的主观性和片面性，而且可靠性和效率 都不高，面对目前三维模型数量越来越多以及互联网搜索引擎规模与复杂性日益 增强的情况，显然难以胜任。因此，迫切需要三维模型检索方法的研究。 1 2 三维形状分析 三维形状分析的研究主要集中在计算机视觉与图形学领域，并应用于机械 c a d 、化学、分子生物学和古生物学等各个方面。其主要研究内容包括： 识别：判断物体是否存在，以及其在场景数据库中的位置。 检索：寻找与查询例子形状类似的物体，并按照相似程度大小进行排列。 分类：根据物体形状将其归并到预先设定的类别中。这些类别可以由自动 分类技术产生，也可以手工指定。分类依据视具体的应用而定。对于简单的 几何形状，根据其形状可以分为球形长方形平行六面体等；对于机械c a d 模型，则需要根据功能对模型进行划分。 合并：即所谓的用例子进行建模。这时候的设计不再是一个从无到有的过程。 已有的例子就像是积木，而设计者的工作便是如何利用这些积木，搭出自己 需要的效果。形状分析则是设计者与积木之间的一座桥梁，帮助快速、准确 地找到目标。 目前，三维形状分析仍存在以下几点： 特征检测与自动标注：如何将物体分为彼此独立又相互关联的部分，并 赋予每一部分适当的标签。 配准：如何找到两个相似，但又不尽相同的三维物体间特征的一一对应。 识别：如何定义两个物体之间的几何相似性，如何找到查询物体一致的 目标。 聚类：如何对数据进行自动分类。 这些问题同时也是计算机视觉和模式识别领域所探讨和关注的。相信这些领 域的研究，必将进一步推动三维形状分析的发展。 1 3 本课题主要研究内容 本课题的主要研究目的是对三维检索算法进行研究并实现一个三维检索系 统。现有的各种算法都有自己的长处和不足，例如：基于统计的方法其优点是对 模型要求不高、计算不复杂、易理解、大多数满足几何不变性和对噪声不敏感， 但是这种方法表面特征替代了几何特征，丢失了一些特征。因此这种算法适用于 全局匹配。基于骨架提取的方法优点是其的不变性，缺点是对模型要求高，计算 量大、对边界噪声敏感，因此适合局部匹配。因此本课题算法研究应该满足以下 要求： 1 ) 对三维信息的描述和分辨能力强； 2 ) 计算速度快； 3 ) 易存储，特征维数足够低； 4 ) 易索引，能方便地组织索引结构，以加快检索过程； 5 ) 具有几何变换无关性，并对形变和噪声具有一定程度的鲁棒性； 6 ) 独立于具体的三维模型表示方法、模型的细化方式、模型的种类和拓扑 关系等。 4 通过研究各种算法，本课题确定了以下几个研究重点： 1 ) 针对三维模型自身特点，研究适用于3 d s 、c t s 和t d o 这三种文件格 式的特征提取算法( 其中后两种文件文格式是我所独有的) 。实现的算法要 具有快速、鲁棒性高、支持多种文件格式的特眭。 2 ) 选择合适的相似性度量算法，从而更好的提高检索的准确度。 3 ) 完成三维模型数据库的设计，实现一个支持多种文件格式的三维检索原 形系统。 围绕以上主题，本文主要分为六个章节： 本文第一章首先介绍研究背景，讨论三维检索的应用前景以及有待解决的问 题，并概括主要工作。 第二章回顾了现有的三维形状分析技术，对形状描述、相似度匹配、相关反 馈、界面设计、系统框架等各方面内容进行总结，并介绍现有的典型系统。 第三章三维特征提取技术的研究。在对已有的三维检索技术研究基础上，本 文提出了两种三维模型特征提取技术。这一章主要分为四个部分，第一部分讨论 了形状分布算法。第二部分讨论点对分类的形状分布算法；第三部分讨论厚度直 方图算法；第四部分讨论联合分布算法。 第四章相似性度量技术研究。在模型相似性度量方面，阐述了几何矩阵模 型和集合理论模型，给出了两种多特征组合的相似性度量模型。结合本文具体研 究的算法，比较了4 个具体的距离度量函数的效果，选择了合适的算法。并采用 排序的评价参数，对本文涉及的算法进行了评价和比较性研究。 第五章系统实现。分析了整个系统功能，讨论了系统特点和一部分实现工作。 第六章结论与展望。对本文作的总结，并对今后三维检索技术的研究方向进 行了展望。 第二章三维模型检索技术概述 2 1 二维图像检索 物体之间形状相似性的比较，可以追溯到早期基于形状的图像检索( s h a p e b a s e di m a g er e t r i e v a l ) ：提取图像中感兴趣物体的轮廓或区域，采用不同方法描 述其形状特征，将问题简化为形状特征的比较。借助于计算机视觉技术，人们可 以定义多种二维形状表示方法和相似性度量。二维形状表示大致分为三类：特征 向量法( f e a t u r ev e c t o ra p p r o a c h ) 、变换形状方法( s h a p et h r o u g ht r a n s f r o m a p p r o a c h ) 与关系方法( r e l a t i o n a la p p r o a c h ) 【5 】a 具体选择哪一种表示方法取决 于应用的要求，如目标形状的特征点，是否允许遮挡与形变的存在，噪声强弱， 以及索引难易程度等。 上述形状描述方法无法直接扩展应用在三维模型上，主要原因是他们要求而 为连续曲线( 或平面上区域的边界) 存在标准参数化表示。对于任意三维曲面， 需要根据具体应用，恢复成一致曲面或流形曲面，得到相应曲面的参数，这样才 能采取扩展的三维形状描述。在重建过程中，需要引入人工干预，以消除模型二 义性。 基于形状的图像检索系统用多维特征空间距离来衡量形状相似性。在特征维 数不是很高的前提下，用索引结构组织特征向量，将加速数据库的访问。但是， 由于人类的感知相似性并不等价于物体的拓扑相似性，单一特征无法完整描述物 体的形状。因而需要提取多种形状特征，给出尽可能详尽的表示。为了满足创建 索引结构的要求，需要将多特征进行降维处理。 2 2 三维模型检索 如何在浩如烟海的三维模型数据库和网格中快速有效的搜索有用的、同主题 的模型，构成了三维模型检索的主要目标。与二维图像相比，三维模型有其独特 的性质。首先，三维模型空间中一个简单的物体，即可以用多边形面片( p o l y g o n s o u p ) 、也可以用点( p o i n t ) 、线( l i n e ) 和体素( v o x e l ) ，还可以由基元物体的 几何操作和布尔操作表示( c o n s t r u c t i v es o l i dg e o m e 仃y ) 。任意的三维曲面不存 在类似二维上弧长公式的直接参数化方法，因此无法对物体空间定义规则的、标 准的类似二维图像的采样方式。这种内在的不规则采样和三维表面存在任意的拓 扑关系，使得经典的信号处理技术，如傅立叶变换，无法直接扩展应用到三维。 其次，空间维数大小直接影响模型特征对应、参数匹配，分类其构造，优化路径 搜索等问题，其复杂度与处理时间随之显著增加。可能的模型退化现象使得常用 的几何形状特征，如面积、体积、曲率等难以计算。 另一方面而言，三维模型检索与相机配置、光源设置和场景语义无关，且不 包含反射、阴影、遮挡、透射等效果，不需要考虑环境光照条件、相机参数、镜 头校准、自遮挡等现象，极大地简化了匹配相似物体的过程，或因为投影到地面 变为两个人，或者由于周围场景的迷惑性而凭空消失。 综上所述，三维模型特征的选取，需要考虑以下三个方面。第一，特征要能 够反映物体的内在基本特性。第二，三维模型在空间中的位置、朝向和大小是任 意的，因此，所提取的特征应该与模型的平移、旋转、放缩等刚体变换无关。第 三，即便对于退化的三维模型，特征也必须是确定的。噪声的存在和网格的细分 操作不影响其稳定性和鲁棒性。本节对当前三维模型检索领域已有的技术做一下 概述。 2 3 1 三维模型检索系统 三维模型检索首先从模型数据中自动计算并提取三维模型的特征，如形状、 空间关系、材质的颜色及纹理等，建立三维模型的多维信息索引，然后在多维特 征空间中计算待查询模型与月标模型之间的相似程度，实现对三维模型数据库的 浏览和检索 “。三维模型检索系统就是试图利用反映三维模型视觉特征的内容信 息自动建立特征索引，达到检索三维模型的目的。三维模型检索技术通过对视觉 特征的相似性匹配来查找用户所要求的三维模型，这更贴近于人们在现实生活中 靠直觉印象使用信息的方式。 因此，一个完整的模型检索系统包括如下几个方面： ( 1 ) - - 维模型的特征提取由于绝大多数的三维模型是用于可视化，因此表 达三维模型的文件中往往只包含模型的几何属性( 顶点坐标、法向矢量、拓扑连 接等) 和外观属性( 顶点颜色、纹理等) ，很少有适合自动匹配的高级语义特征的描 述。如何合理地描述三维模型( 即特征提取) 成为三维模型检索课题首先要解决的 问题，它也是三维模型检索的难点。一个理想的特征描述符s d ( s h a p c d c s c f i p t 0 0 必须满足：易于表达和计算；不占用太多的存储空间；适合进行相似性匹配；具 有几何不变性，即对模型的平移、旋转、缩放等具有不变性；具有拓扑不变性， 即当相同模型有多个拓扑表示时，s d 应是稳定的；s d 对模型的绝大多数处理， 如子分、模型简化、噪声增减、变形等是鲁棒的；s d 必须具有惟一性，即不同 类型的模型对应的特征表示应该不相同。 ( 2 ) 相似性度量检索的目的是找出与所给模型相似的模型集合，因而对提 取得到的特征如何进行相似性匹配是检索课题中要解决的第二个问题，选择的度 量方法必须适合匹配计算。 ( 3 ) 模型分类由于三维模型资源庞大，因此需要建立一个分类数据库以便 提高模型查找效率，该分类数据库必须适合用高级语义描述。当然，对这个问题 与相似性度量方法的研究有交叉的地方。 ( 4 ) 搜索方法的研究尽管有了分类作基础，但面对仍然庞大的数据库，如 何快速、有效地查找出相似的模型，在人工智能和数据库领域中仍然是一个值得 探讨的问题。 ( 5 ) 查询接口的设计作为一个成熟的检索系统，应该拥有庭好的交互性能， 提供给用户方便的查询手段。通常，查询输入可以通过文本与模型相结合的方法 【7 ，8 1 进行。对于查询模型的输入主要有两种途径：文献 7 将已知的模型作为查询 输入，通知系统检索出相似的模型，该方法的检索结果比较理想，但是要求用户 必须预先拥有某种模型的范例，因此实际使用中不够灵活，有一定的局限性；文 献 8 提供给用户一个绘图接口，允许用户绘制所需查询模型的二维视图，由系 统根据视图自动生成三维模型。对于普通用户而言，准确地绘制一个拓扑复杂、 有洞或有许多分支的模型是比较困难的。实验表明，目前该系统在这方面的性能 不是非常理想。显然，查询接口的设计也直接影响了系统的检索性能，因此设计 一个理想的查询接口在检索系统中非常重要。 ( 6 ) 检索性能的判断对于三维模型的检索性能的判断，主要从查全、查准、 时间、资源消费等几个方面来衡量。目前的研究主要是用查全率和查准率两个参 数来对检索性能进行评判。 总之，如何提取模型的特征是三维模型检索首先需要解决的关键技术，也是 目前研究比较多的一个方面。 2 3 2 三维模型预处理 要真正实现基于内容的三维模型检索，非常关键的一点就是要求所提取的三 维模型特征描述具有针对平移、旋转、尺度大小以及方位变换的不变性和鲁棒性。 目前，实现特征描述不变性的方法主要有三种【9 】： ( 1 ) 使用主成分分析n c i p a lc o m p o n e n ta n a l y s i s ，p c a ) 0 ： 1 3 】等方法对三维模 型坐标进行标准化，计算其标准化的坐标框架，然后，在此标准化坐标系内提取 相应的特征； ( 2 ) 将所有待比较的三维模型两两之间进行坐标对齐，这种方法由于极为费 时而很少被采用； ( 3 ) 定义并提取本身具有不变特性的特征描述。 但实际上，这些特征描述所具有的不变性往往是不全面的，例如，s u z u k i 等人提出的形状特征只对绕坐标轴9 0 。范围内的旋转变换保持不变性1 0 ， k a z h d a n 等人提出的反射对称特征描述只具有平移和尺度不变性 1 1 】。而且，大多 数这类特征的计算有时也需要在一个归一化的坐标系内完成。因此，为了进一步 提高检索的准确性，往往也需要进行模型坐标标准化。 2 3 。3 特征提取 从计算机图形学发展的初期开始，多边形网格就是通用的三维模型的表示方 法。尽管后来出现了更多的描述方法，但由于多边形具有形状简单、便于计算和 处理等特点，使得三维模型检索的研究者们更多的以多边形网格模型作为研究对 象。文献 1 4 ，1 5 在2 0 世纪8 0 年代初就对三维模型形状特征的描述进行了研究， 但由于相关应用领域发展的滞后，当时并未引起更多的关注，直至2 0 世纪末， 随着硬件条件的成熟和应用需求的发展，关于三维模型特征提取方法的研究开始 受到了人们的重视。目前，三维模型特征提取方法主要分为三大类：统计特征提 取方法；骨架提取方法；基于几何学的提取方法。 ( 1 ) 统计特征提取方法： 对一个三维模型进行参数化本身就是一个很复杂的问题，同时由于三维表面 有任意的拓扑，使得一些在二维图像被使用的方法( 如傅里叶变换) 无法直接应用 在三维领域。很多模型虽然满足了视觉效果，但是大多数是退化的、不完整的， 最经典的如u t a h t e a p o t ，是一个无底的茶壶；又如s t a n f o r db u n n y 是一个带有几 个洞的兔子。对这些模型进行有意义的几何特征和形状信号的计算是很困难的， 因此从统计学的观点出发，寻找出有意义的统计特征成了研究人员首先考虑的方 法。目前的研究中主要使用了如下统计特征：模型顶点间的几何关系( 距离、角 度、法线方向关系等) ，模型顶点的曲率分布特征，模型顶点的各阶统计矩以及 各类变换特征系数等。 z a h a r i a 等1 16 】提出用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 ) 方法对三维模型 进行描述，该方法避免了文献 1 7 中的二次特征提取，其主要思想是根据物体表 面的一些局部几何属性( p n 某点的曲率) 提供物体内在的形状索弓l ( s h a p ei n d e x ，s 1 ) 描述。s i 被定义为某点关于两个主要曲率的函数，则3 d s s d 被定义为s i 在整个 模型网格上的分布，用直方图表示。3 d s s d 对几何转换和比例缩放具有不变性， 对一些易见的、显著的、有突起的特征，如c o n v e x i t y ，c o n c a v i t y ，r u t ，r i d g e ， s a d d l e 描述准确。但该方法对模型的拓扑很敏感，对任意网格描述之前需进行规范 化的预处理，预处理的过程较复杂且涉及到很多方面( 如拓扑表示的不唯一性、 网格的不规则采样，非定向网格，退化网格等均需经过预处理) ，因此该方法并 不通用。 o h b u c h i 等【1 8 】在假设模型的质量分布是均匀的前提下，计算了模型相对三 个主轴的惯量矩和模型表面顶点对三个主轴的距离分布。由于模型对轴会有一些 小的变形，为了减少由此带来的影响，文献 1 8 】采用了一种叠盖分析窗口的方法， 增加算法对这种变形的鲁棒性。这种方法计算不复杂，对些退化的模型也适用， 但实验表明其对于具有旋转对称特征的模型效果更好些，而对其他特征的模型实 验结果并不理想，因此该方法局限性比较大。 文献 5 2 在假设三维模型可以用三维等高线描述的前提下，用傅里叶系数作 为特征描述符。显然，这种方法无法从理论和实验上证明等高线就是三维模型的 理想特征描述符，因此还需进一步研究。 1 0 ( 2 ) 骨架提取方法： 在医学的虚拟内窥镜手术中，人们致力于研究如何提取管状器官的中轴线， a m e n t a 等【1 9 2 0 增先计算出模型的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 图，增加了计算量，影响对 模型特征的精确描述。因此，这种方法的实用性有待进步研究。 与中轴变换的思想相似，文献 3 s3 9 采用基于参数控制的瘦化算法对模型进 行骨架提取，适合任何以体素描述的三维模型。该算法首先计算出模型的骨架节 点，然后通过各节点构造出相应的骨架图形，即一个有向的非循环图。以此作为 模型的特征描述，不仅适合全局匹配，也可进行局部匹配。该算法中骨架节点为 模型局部的中心点，通过瘦化参数控制节点的密度，因此参数直接影响了模型骨 架的提取质量。瘦化算法对噪声异常敏感，小的扰动会导致错误的骨架提取。同 时，由于需要对每个体素的距离转换值进行递归计算和比较，因此这种算法的计 算量很大。而关于如何选择瘦化参数文献 2 1 ，2 2 】中没有给出理论的描述，这也是 该算法的一个遗憾。 ( 3 ) 基于几何学的提取方法： v r a n i c 等人2 3 l 提出一种基于射线( r a yb a s e d ) 的形状特征描述方法。以坐标原 点为起点，沿一组等间距的空间方向矢量作射线，计算与其相交的三角形面片与 坐标原点的最大距离作为特征值。h e c z k o 等人2 4 1 提出一种基于体结构的形状特 征提取方法。将每个单元网格所包围的网格面片面积作为特征元素。s u z u k i 怛别 则提出一种基于三维模型顶点等价类的特征提取方法。首先，计算每个网格单元 中的顶点( 或表面法向量) 数目，将网格单元划分为一系列等价类。最后，以每个等 价类中归一化的顶点个数为特征向量。t a n g e l d e r 等人【1 9 】描述了一种使用加权点 集合( w e i g h t e dp o i m s e t s ) 表示多面体模型的方法，用每个网格单元中的代表点组 成加权点集合作为形状特征。b i n f o r d 2 0 l 使用一种称为广义柱( g e n e r a l i z e d c y l i n d e r s ) 的参数模型实现三维模型的特征提取，该模型由一组基于样条曲线的空 间轴及定义在该轴上的截面连接函数组成。c i c i r e l l o 等人和m c w h e r t e r 等人【1 8 j 通过提取三维图形中的几何学和工程学上的特征来进行相似性估计。z h a n g 等人 f 2 6 和v r a n i c 等人 2 2 】则使用球形调和函数5 潞( s p h e r i c a lh a r m o n i c sd e c o m p o s i t i o n ) ， 提取对三维模型的多分辨率特征，实现基于表面匹配的三维模型检索。此外， v r a n i c 等人基于三维离散傅立叶变换的方法提取三维模型的特征【2 7 】。由于绝大多 数的模型是不严格的，如i n t e m e t 上的模型通常是退化的、松散的多边形集合， 所以该方法的应用受到很大的限制。 ( 4 ) 其他提取方法： 除了形状特征以外，还可以利用三维模型的表面属性，包括颜色、反射系数 和纹理等进行检索。s u z u k i 等人实现了一种基于三维模型材质颜色的特征提取方 法。s u z u k i t 2 8 1 等人认为，材质颜色在很大程度上影响着三维模型的外观属性，对 于三维模型的颜色而言，其复杂之处在于要考虑光照模型的影响，如环境光 ( a m b i e n tl i g h t ) 、漫射光( d i f f u s el i g h t ) 、反光系数( s h i n i n e s sv a l u e ) 以及透明 系数( t r a n s p a r e n c yv a l u e ) 等等。随着光照模型的变化，可以为三维模型表面产 生大量的颜色种类，以此为基础，s u z u k i 等人提出一种基于用户输入的交互式三 维模型颜色检索方法，将每一种材质颜色表示为光照模型中若干个光照参数的综 合值，基于一个有用户主观评价生成的颜色训练集，使用多元回归分析方法对光 照模型进行预测。实验表明，该方法能较好的反映用户对于模型外表面颜色的主 观认知特性。但由于三维模型表面属性的多样性和复杂性，表面属性特征提取的 研究至今并未得到充分发展。 特征描述方法使用模型优点 局限性 统计特征任意网格模型( 对对模型要求不高、计算不部分特征不稳定、表面特 松散的、退化的模复杂、易理解、大多数满性替代了几何体特性，丢 型也适用1足几何不变性、大多数对失了一些特征。部分特征 边界噪声鲁棒、适合全局 对拓扑敏感，大多数特征 匹配 适合粗分类 骨架提取 体素模型、封闭的 直观( 可视化) 满足几何不 对模型要求较高、适合有 网格模型变性，适合全局和局部匹关节或分支的模型、计算 配量大、对边界噪声敏感 基于几何学刚度较大、变形较原理简单，符合人类的相对模型要求很高、不通 小、封闭的网格模似判断准则、适合全局匹用、计算量大、对预处理 型配要求非常严格 2 3 4 相似度比较 表2 - 1 各类方法分析 相对于三维检索形状算子的研究而言，相似度比较方法在图像检索领域已 有了比较成熟的研究。般的，当特征位于二维笛卡尔空间，满足三角不等式的 l ，范数是一种自然的度量方式。加权，距离考虑各个特征分量之间的相对权重 【2 9 】，弹性形变距离( e l a s t i cm a t c h i n gd i s t a n c e ) 3 0 1 允许相比较模型对应部位之间 的相对尺度存在不一致它们提供了。范数所不具备的灵活性。此外，如果特 征是用直方图形式所表示的一个分布，z 2 距离及b h a t t a c h a r y y a 距离都是较好的 选择。 2 3 5 相关反馈 相关反馈( r e l e v a n c ef e e d b a c k ) 是检索研究的热点之一。由于没有一种形 状特征能够完整地描述模型的特性，也没有一种相似性度量可以很好的模拟人的 视觉感知，已有的分类器只能在给定样本的情况下给出最佳分类结果，因此，如 何让系统在各种检索条件下都能够给出较好的结果，是一般的检索系统需要考虑 的问题。相关反馈的目标是从用户与查询系统的实际交互过程中进行学习，发现 并捕捉用户的实际查询意图，并以此修正系统的查询策略，从而得到用户实际需 求尽可能相吻合的查询结果；由于相关反馈可以实时的修改系统的查询策略，从 而为检索系统增加了自适应功能。 与相似度比较类似，相关反馈也不是三维模型检索领域所独有的。在图像检 索中，他被用于缩小高层语义与底层特征之间的差异，以及弥补人类视觉感知的 主观性 3 1 】。 2 3 6 界面设计 由于三维模型中所包含的内容信息比图像等二维媒体更加丰富，因此，基于 内容的三维模型检索系统一般具有多种检索方式 3 】，主要有： ( 1 ) 直接提供三维模型实例作为检索请求，该模型可以是用户上载至检索服 务器的新模型文件，也可以是某次检索结果集中的任一幅三维模型【3 ，q 使用文件 上载方式时，用户只需直接提交三维模型的文件名或url 地址；而使用服务器 上的三维模型实例检索时，用户可以通过缩略图浏览的方式在界面上交互选取。 乜) 使用用户交互绘制的二维形状草图，如m i n 等人设计了一个基于用户交 互的二维草图绘制界面，由用户绘制l t 个不同角度的二维草图作为查询请求【3 】， 在检索时则使用三维模型在不同视角下的二维投影分别进行相似性匹配。 ( 3 ) 使用用户交互绘制的三维草图，如i g a r a s h i 等人设计的三维草图绘制工具 t e d d y 3 2 】。但相对于二维草图绘制而言，三维草图的绘制难度较大，限制较多， 而且只能绘制相对简单的三维模型。 ( 4 ) 基于文本关键字的检索界面【3 1 。其中，文本关键字可分为两类：一类是不 具有语义属性的文本，如模型文件名称等附加信息；另一类是语义关键字，可以 通过直接输入语义文本或者目录浏览的方式提交检索请求。 此外，检索界面还负责将检索结果以可视化的方式显示给用户，以进行浏览 或下一步的检索过程。些三维检索系统中还引入了用户相关反馈的机制，为用 户提供一个交互式的评价界面，作为引入用户主观评价的手段，以提高检索精度， 并实现个性化的、结合用户主观性认知的检索。如e l a d 等人2 9 1 提出基于学习的 检索机制以自动适应不同用户的检索要求和偏好，在检索结果显示时提供了一个 4 标记相关”和“不相关两种评价的用户反馈界面。而z h a n g 等人7 1 则进一步 对用户评价界面加以细化，提供了调节“相关”和“不相关”程度的反馈界面。 2 3 7 已有系统 在基于内容的三维模型检索领域，目前已经实现并发布了一些进行理论和算 法研究的原型系统以及架构于w e b 平台上的搜索引擎等。其中，加拿大国家研 究院( 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 s t 等人开发的三维模型检索系统n e f e r t i t i 是第一个通用的三维模型检索系统6 ，3 3 】，所提取的特征主要包括形状和颜色两 种。目前，比较典型的通用三维模型检索系统和搜索引擎主要有： ( 1 ) 美国普林斯顿大学形状检索与分析( s h a p er e t r i e v a la n da n a l y s i sc r o u p ) 实 验室开发的三维模型搜索引擎，提供了二维草图和三维草图的绘制界面，并具有 规模最大的三维模型数据库，其中包括3 1 0 0 0 个通用的三维模型以及多个专业的 三维模型子库。 ( 2 ) 美国卡耐基梅隆大