三维模型检索中几种特征提取方法实现研究.pdf

西北大学 硕士学位论文 三维模型检索中几种特征提取方法实现研究 姓名：邓军国 申请学位级别：硕士 专业：计算机系统结构 指导教师：周明全 20090616 摘要 随着三维模型获取技术、计算机图形学以及计算机网络技术的发展，三维模型在很 多领域得到了广泛应用，并且形成了越来越庞大的三维模型数据库。如何从模型库的海量 数据中迅速查找出我们所需要的模型已经成为当前迫切需要解决的问题。 通常，完整的三维模型检索系统应包括特征提取、索引结构、相似性度量、查询接口 等几方面。其中，三维模型的特征提取对三维模型的相似性检索至关重要，针对三维模 型特征提取这个三维模型检索研究中的亟待解决的基础问题，本文通过对三维模型特征 提取方法的研究，设计实现了以下三种特征提取方法： 一、2 d 投影点集的特征提取方法。研究实现了通过比较2 d 投影点集的统计特征 比较三维模型相似性的特征提取方法，通过与基于传统2 d 投影点集的特征提 取方法的分析对比，验证了该方法具有较好三维特征描述效果，较低计算复杂 度。 二、基于球面调和变换方法。本文研究实现了快速球面调和变换、表面体素调和变 换：通过将最小包围盒计算引入到表面体素模型填充，改进实现了实体体素调 和变换方法，与传统的实体体素方法相比，具有提高计算效率的优势。 三、基于骨架特征提取方法。本文设计改进了一种线性骨架提取方法，在保证骨架 良好的连通性前提下，一定程度上解决了骨架提取算法中关键骨架点难以确定 的问题。 开发了一个三维模型特征提取原形系统，上述三种特征提取方法都在该系统上进行 了检索实验，确定了方法参数优化取值，以及合适的相似性度量方法。实验表明，这几 种三维检索技术特征提取方法提取的特征向量都能较好的描述三维模型特征。其中，实 体体素调和变换方法在提高查准率、查全率等方面效果更为突出。 关键词：三维模型，特征提取，骨架特征，2 d 投影点集 a b s t r a c t w i t ht h ed e v e l o p m e n to f3 dm o d e l sa c q u i s i t i o n , c o m p u t e rg r a p h i c s ，a n dc o m p u t e r n e t w o r kt e c h n o l o g y , 3 dm o d e l sa r em o r ea n dm o r ew i d e l yu s e di nm a n yf i e l d s t a k i n gi n t o a c c o u n tt h a tb u i l d i n gt h e3 dm o d e l si sav e r yc o m p l e xw o r k , i ti sv e r yi m p o r t a n tt or e u s e3 d m o d e l s h o wt or e t r i e v e3 dm o d e l sn e e d e db yc u s t o m e r sq u i c k l yf r o mt h eh u g ed a t a b a s ei s b e c o m i n gm o r ea n dm o r en e c e s s a r y g e n e r a l l ys p e a k i n g ，ac o m p l e t e3 dm o d e lr e t r i e v a ls y s t e mt y p i c a l l y i n c l u d e sf e a t u r e e x t r a c t i o n ，s i m i l a r i t ym a t c h i n g ，i n d e xs t r u c t u r e ，a n dq u e r yi n t e r f a c e a n df e a t u r ee x t r a c t i o ni s t h em o s ti m p o r t a n tf a c t o rf o rt h e3 dm o d e lr e t r i e v a l s o3 dm o d e lf e a t u r ee x t r a c t i o ni st h e k e yt e c h n o l o g yi n3 dm o d e lr e t r i e v a l ，a n di ti sa l s ot h em a i np o i n to f t h i sp a p e r t h em a i nj o bo ft h i sp a p e ri st od e s i g na n di m p l e m e n tt h r e en e wm e t h o d so ff e a t u r ee x t r a c t i o n t h r o u g hr e s e a r c h i n gt h et e c h n o l o g yo f3 d m o d e lf e a t u r ee x t r a c t i o n 1 2 dp r o j e c t i v ep o i n ts e t s i ti sd i f f e r e n tf r o mt h et r a d i t i o n a lm e t h o d s ，w h i c hc o m p a r e st h e 3 ds h a p e sb a s e do n2 dc o n t o u rm a p ，a n dc o m p a r e st h e3 ds h a p e sb ym e a s u r i n gt h e s t a t i s t i c a lc h a r a c t e r i s t i co f2 dp r o j e c t i v ep o i n ts e t s i nf a c t , t h i sm e t h o du s e s t h e t e c h n o l o g yo f2 di m a g er e t r i e v a l ，a n di th a sl o wc o m p l e x i t y 2 a c h i e v ea n di m p r o v eo nt h et h e a r i t h m e t i co ft h et r a n s f o r mo fs p h e r ec o n g r u i t y ，a n dw i t h t h et r a d i t i o n a lm e t h o d sc o m p a r e d ，i th a sl e s sc o m p u t a t i o n 3 t h ef e a t u r ee x t r a c t i o no fs k e l e t o n d e s i g na n di m p l e m e n tab e t t e ra l g o r i t h mo ft h ef e a t u r e e x t r a c t i o no fs k e l e t o n ：b s et h em e t h o di sd i s t a n c e sc h a n g e ，a n dg e tt h ei n f o r m a t i o n c o m b i n i n gt ot h ea r i t h m e t i co fc o n n e c t i v i t yj u d g e m e n t ，a c h i e v et h ef e a t u r ee x t r a c t i o no f s k e l e t o n t h ep a p e rh a v ed e v e l o p e da3 dm o d e lr e t r i e v a ls y s t e ma n dd o n eal o to fe x p e r i m e n t s b a s e do na l lt h et h r e ea r i t h m e t i c 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 df e a t u r e e x t r a c t i o na l g o r i t h m sa r ee f f e c t i v ea n de f f i c i e n t t h e yc a nd i s t i n g u i s hd i f f e r e n t3 dm o d e l f r o me a c ho t h e r k e y w o r d s ：3 dm o d e l ，f e a t u r ee x t r a c t i o n , s k e l e t o nf e a t u r e ，2 dp r o j e c t i v ep o i n ts e t s 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位诊文作者签名：垦 墅丑指导教师签名：f 缉全二一 一年月f 日 1 年石玛f 后日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：a p 晕融 狐，年月，日 西北大学硕士学位论文 1 1 研究的背景及意义 第一章绪论 我们生活在一个三维的世界中，人眼对物体的感知通常都是立体的。相比二维图像， 三维模型具有更丰富真实的表现形式和更多的感知细节，因此更适用于我们的视觉感 知。随着计算机图形学和空间可视化技术的发展，三维模型已经应用于社会生活的各个 方面，如虚拟现实、三维动画及游戏、c a d 、军事、分子生物学等。三维模型已经成为 了继声音、图像、视频之后的第四种多媒体数据类型。 借助于计算机的高仿真能力，我们可以将现实世界的物体转化为虚拟的三维模型。 虽然随着三维图形处理硬件的高速发展，使得模型重建变得相对容易，但是三维模型数 量成指数增加，如果每次都需要建立高逼真度的三维模型，显示工作量异常庞大。因此， 必须需要充分复用已有的模型资源。i n t e r n e t 的迅速发展为三维模型资源的共享奠定了 良好的基础，因此如何从模型库中的海量数据中迅速查找出我们所需要的模型已经成为 当前迫切需要解决的问题。与声音、图像、视频这三类多媒体数据检索技术相似，三维 模型检索主要分为两大类【2 】：基于文本的检索、基于内容的检索。由于实现算法简单， 且经过多年发展，基于文本的检索技术已经相当成熟，因而目前的商业网站大多采取的 是基于关键字的检索。但是，基于文本的检索技术存在固有的缺陷，首先文本信息本身 就无法全面表述三维模型的几何形状、拓扑结构、材质的颜色及纹理等丰富信息，而且 需要耗费大量的时间和精力；其次要为三维模型建立相对应的注释信息，不仅需要相关 领域经验丰富的专业人员参与，而且受文化、语言等多种因素的制约，注释信息会有一 定的主观性和片面性，从而会影响检索结果的准确性。因此，需要利用三维模型本身所 携带的信息进行检索，推动了基于内容的三维模型检索技术研究的迅速发展。 基于内容的检索的基本原理为：利用机器自动提取并计算三维模型的内在特征，如 形状、拓扑关系、模型表面信息等，通过对待查询模型和目标模型特征之间的相似性匹 配来自动建立特征检索索引，实现对三维模型数据库的浏览和检索。相比基于文本的检 索，它具备人工干预少、贴近现实生活中直觉的视觉印象、检索准备率高的特征。当然， 要实现准确检索，需要解决以下几个关键问题：模型的特征提取，特征的相似性度量， 索引结构，查询接口的设计【6 】。其中模型特征的提取是整个工作开展的基础，因此展开 对模型特征提取方法的研究是十分必要的。一个理想的特征描述符需要满足以下几个条 第一章绪论 件：( 1 ) 易于表达和计算；( 2 ) 尽量不受边界噪声、变形、模型简化等影响，应具有良好 的鲁棒性；( 3 ) 具有不被模型的平移、旋转、缩放等几何不变性以及不受模型多种格式 的变化的拓扑不变性，即具有良好的稳定性。( 4 ) 不同模型的特征表示应该不尽相同， 即具有唯一性。 迄今为止，国内外已经有多家著名院校和研究机构开展了特征提取相关技术的研 究，并相继提出了多种特征提取方法，主要分为以下几类：基于轮廓形状的特征提取， 基于拓扑形状的特征提取，基于视觉形状的特征提取。另外，近年来也发布了一些最新 的研究成果，如混合多特征的方法，引入相关反馈方法等。现有的各种特征提取方法都 有不同的优点和缺陷，因此本文对相关的几种典型的特征提取方法进行了分析和研究， 并提出了改进思路。综上所述，本文工作主要具有以下两方面意义： 1 、三维形状特征的提取的效果还远没有达到人们的期望，需要更深入的研究，本 文在运算速度、描述效果等方面改进实现了几种有代表性的特征提取方法，为今后做进 一步研究打下基础。 2 、在上述研究的基础上，为实验室开发的三维模型特征提取原形系统提供三维模 型特征提取模块，是一个迫切需要解决的问题。三维模型形状特征提取是三维模型检索 研究中的一个关键技术。本文希望通过对三维模型特征提取的研究，寻找三维模型特征 提取的有效方法，为三维模型检索技术提供新思路和新方法。 1 2 三维检索系统简介 随着三维模型在社会生活的多个领域得到越来越广泛的应用，由此衍生的三维模型 检索领域也越来越受到国内外学者的关注和重视。近年来，研究人员已经陆续的开发并 发布了一些进行理论和算法研究的检索系统，其中典型的代表有普林斯顿大学的3 d 模 型搜索引擎和台湾大学的3 d 模型搜索引擎等。目前，三维模型系统主要采用的模型检 索方式有以下四种【8 】： 1 关键词检索：利用用户数据的关键词与描述三维模型的文本信息进行匹配，通 过匹配度来检索出相关模型。 2 2 d 草图检索：通过提取手绘草图对象的连续外边缘轮廓信息，也就是通过机器 提取出草图的形状特征，然后依据与三维模型的投影图像的形状特征形相似性进行匹 配，并依照相似程度输出检索结果。 3 3 d 草图检索：其实现的核心思想与2 d 草图检索基本致，两者主要区别在于 2 北 mi ? r 论文 3 d 草图检索是按照三二维空司的形状特征而不是某个投影平= f j i 的形状特钶进行检索。 实例查询：用户提供个3 r ) 模型文件，井利嗣形状信息、蕊色信息、纹理信息 等多个特征实现检索。 通过卜迹分析可知，戈键词检索是一种传统的文木检索方式，而后t 种归属于基于 内容的一维模型检索。r 面以普林斯顿大学的3 d 模型搜索引擎和台湾大学的3 d 模型 搜索引擘为例对通用的三维检索系统进行简e 弘的说明 12 1 普林斯顿大学3 d 模型搜索引擎 美国普林斯顿大学形状检索与分析实驰审开发的3 d 横型搜索日擎( p r i n c e t o n3 d m o d e ls e a r c he n g i n e ) h 1 被公认为是目村世界上应用最产、效果最好的三维撞堡系统， 该系统提供了门常生活r p 各种常见三维格式的二维模型，如3 u 轧o f f 等迄今为止 其模刑数据障门n ep f i n c e t o n s h a p cb e n c h m a r k ，简称p s b ) 。中的二维模型总数量已势 到达了( 5 0 0 0 ( ) 多个。该挫第引擎提供了友好的检索界而，并且支持上述介绍的全渐4 种 检景方式，如图11 、12 、l _ 3 所，j 1 用户可以通过实例、绘制2 d 草图、绘制3 d 草 巨等方式进行检索。 篁暑妻芦鼍鼍一一 崔 一f o _ - o o o 。 ! 善簧：审1 苗销茹荫筹茹晶二。 赫：= ：”：”一_ ” ” - - - 。 o ：i 一 = o t ：一 - ：? o 盈曩蟊誓 玲 - q - 一 o- 一“一 蠢t 峨 图l i 3 d 模型示例椅索界口( 0 自文献1 0 1 二f = 一l ，j 。口 守”。劣”m o d e l s e a f c t l 罱i 。 ：二o ：。= ：_ 。二一：j 1 ：。j ，一 图1 2 手工绘制2 d 草图检索界面( 引自文献1 1 1 鼍尹“一3 ”d m o d e s e 口i c h 。e n 。g 。i n e 盐三盖五：菡= ：! 二上 _ - - - 一j _ _ 一 一 一 嚣：= i # t ：怒五?端：搿o i 中 - 霄 豁= 薷蟊j 三：= ：夏量曩忑 图1 3手工绘制3 d 草图检索界面( 日i 自文献“ ! 二台湾大学3 d 模型搜索引擎 基于视觉形状的3 u 樘型搜索引擎近十年柬孕行岜柬的新研究领域，近年柬，匿内 外学者对此进行，、量的研究和探索+ 先后r 发出多个基 二视觉形状的三维模型检索系 统，出台湾大学通讯与多媒件史验事7 r 发的检索系统就是其 的典型代表。它提供了 。 富的检索 式如文本关键词查询、维目像检索以及反馈多次查询。如目4 ，图5 所 j 、用户可以通过输入个值匡悔柬进行检索，f 且可以在初次检索的结果上再利甩 上述二种查询方式的q 、的任何种或者多种进行二敞检索如此反复直至检索到满意的 柑似横犁。 温一盈一屠一如一 曝翼一薰翼醢一盏一泣一是 e一盈一&一日一 w j 匕j 、# 十t i 蛳毋 酶帚。岛 一。严备| l 震夸 图1 - 4 二维图像检索界面( 引自文献【1 2 1 ) 3 本课题主要研究内容 ，詈罩裹篡：= = = ：= ：二= 二一：亏 岛6 口 神。吩啷舟 一薜备琶r ， 图1 - 5 检索结果再检索界面f 引自文献1 1 2 ) 本支主要改进实现了= 种有代表性的j 维模型特征提取方法，内容且rf ： 基j 。2 d 投影点集三维模型特征提取方法的实现研究 本文先将三维模型投影到2 d 平面，通过比较2 d 投影点集的统计特征来比较三雏 模型的几何相似性； 二、基于球而调和变换特征提取方法的虫艘研究 由球面调和函数牟身性质可知，球面调和变拽方法提取的特征向星具有旋转不变 性：本文通过移植s 2 k i t 软件包实现丁快速球面调和变换。在将王角网格转化为表面件 素模型后，利用种子算法，灌水式二 i 充思想对体紊模型进行了填充的同时， 入最小包 m 盘算法，得到二维实体体素模型，实现实体体素调和变换。 三、基r 骨架提取方法的实现研究 基于拓扑结构的骨架特征提取算泣能在很大程度上保留三维模型的拓扑结构，并且 陔方法提取的特征具有良好的稳定性；本文把距离变换看做一个札、量场，! - 7 其相苁联的 具有重要信息的矢量场是距离娈换的梯度再根扰距离场及其梯度得到物体内部的一些 关键点再山连通性判断算法得到这衅戈键与z 口j 丰目戈连的信息，实现线性胃架特征提 取疗法： 四、系统实现和练合检索结果 在工作小维共同完成的三维模型特征提取原形系统上对上迹乏种特征提取算法逆 行幢删，比较其检测效果。 第一章绪论 本文实验方面采用普林斯顿大学的三维模型检索标准库( t h ep r i n c e t o ns h a p e b e n c h m a r k 以下简称p s b ) 1 1 3 1 以及国际上通用的评价指标；研究的对象包括三维模型的 网格表示和三维模型的体素表示。 1 4 论文的组织结构 本文共分为七大部分，与所作的工作相对应，具体如下： 第一章：绪论。阐述了本文的研究意义与背景，简单介绍了三维模型检索系统的发 展与应用，分析了目前常用的几种特征提取方法的发展现状，并概括性介绍了本文完成 的主要工作。 第二章：三维模型特征提取相关概述。本章主要介绍了基于轮廓、基于拓扑、基于 视觉形状的特征提取算法，并对其优缺点进行了分析和比对。在此基础上，介绍了三维 模型与处理的基本原理和过程。 第三章：基于2 d 投影点集方法特征提取。本章首先介绍了三维模型的三种切分方 式，接着研究实现了基于2 d 投影点集三维模型特征提取算法，最后对该算法进行实验， 并与传统的方法进行对比分析。 第四章：基于球面调和变换方法特征提取。本章首先介绍了球面调和变换的数学原 理，利用s k i t 2 软件包实现快速球面调和变换；接着研究实现了表面体素球面调和变换 和实体体素球面调和变换，在对这两种算法进行实验和分析后，将本文实现的实体体素 球面调和变换方法与传统方法进行对比分析。 第五章：基于骨架特征提取方法特征提取。本章首先介绍了骨架特征提取方法原理， 采用距离变换的方法，保留代表骨架的关键点，这些骨架点通过连通性判断算法可以取 得相互关联的信息，最后对该算法进行实验和分析。 第六章：系统实现和综合检索结果。首先介绍了开发完成的三维模型特征提取原形 系统：再对本文研究的三种算法的检索效果做了综合比较，最后对实验结果进行分析和 总结。 总结与展望：对本文完成的工作进行了总结，并提出了本课题今后继续研究和改进 的方向。 6 西北大学硕士学位论文 第二章三维模型特征提取相关概述 2 1三维模型特征提取方法总结 2 1 1 基于轮廓形状的特征提取 计算并比较三维模型的轮廓特征从而获得三维模型的几何相似性是基于轮廓形状 的几何特征提取算法实现的思想。其中，三维模型轮廓特征主要包括了顶点以及网格的 分布特征。 o s a d a 1 4 1 提出了通过随机采样来获得三维模型的几何特征的形状分布方法。对于从 三维模型表面上随即采样到的的两个点，可得到它们之间的欧氏距离( d 2 距离) ，更进 一步地，统计通过以上方法而得到的大量的欧氏距离，可获得三维模型的形状分布曲线。 形状分布直方图算法【1 5 1 可以简要概述为：首先使用几何函数来计算三维模型顶点的 形状特征，从而获得形状特征分布直方图，然后比较直方图的相似距离以获得三维模型 的几何相似性。针对该算法中应用的几何函数，o s a d a 主要分析其中的五种，如图2 1 所示。 d 1 距离：三维模型中心到三维模型表面任意点之间的距离； d 2 距离：三维模型任意的两点之间的距离； d 3 距离：三维模型表面上任意的三点所构成的三角形的面积； d 4 距离：三维模型表面上任意的四点所构成的子模型的体积； a 3 距离：三维模型表面上任意的三点所构成的角度值。 d 1d 2d 3d 4 图2 - 1五种距离示例【9 】 在以上的几何函数中，d 2 距离的效果是最好的。不同的形状可以通过利用其d 2 距离的概率分布不同这一特征而较好地加以区别，而且对于将一个任意的三维模型转换 为一个参数化的概率分布函数，这一计算相对较为简单。如图2 2 所示，分别表示了直 线段、圆、三角形、立方体等形状的d 2 概率分布状况。 第二章三维模型特征提取相关概述 c jt r i a n g l e e jc 3 - 1 m d e r ( w i t h o u tc 娜，s ) b ) c i v i c d l s p 】b 挑 g ，了h o 确a c 既臻l 团匪h ，了讪l o 柚血tq 出曙i 髓铽：p 孤1 把d 蛳滞姆1 工3 “4u 豳 图2 - 2多种形状的d 2 概率分布1 1 o 】 具有相似外形特征但细节不相同的模型也可能有大体相似的形状分布曲线，因此， 仅仅利用一条曲线来表示三维模型的形状，在实际的应用中这通常是不够理想的【1 6 1 ， 这就是o s a d a 算法的主要缺点所在。因此需要提出增加一些新的信息来反映模型的几何 特征，从而提高算法对不同形状的区分能力。在对d 2 函数进行的改进【16 】中，两随机点 之间连线的情况包括两种：第一类为连线没有穿过模型，设其记为u 类；第二类为连线 穿过模型，设其记为w 类。对于两随机点之间的线段，可以依次判定其属于哪一类型。 如图2 3 所示，由于a 、b 两条线段中不存在任何与曲线相交的点，因此a 、b 均属于 u 类，而线段c 中至少有一个与曲线相交点，则c 属于w 类。最后，构建模型相应的 形状分布直方图，计算相似性距离。 图2 - 3随机点之间连线分类示意图【l l 】 由s u z u k i 提出的点密度方法【1 7 】，即旋转不变描述法。该方法与形状直方图方法的 基本思想具有一致性，它们都需要求出点的分布情况，但各自的实现方法并不相同。点 密度法是将包围三维模型的立方体分割为幸 个单元，并对所有的单元进行分类， 8 西北大学硕士学位论文 分类方法为：将满足围绕工轴、】，轴、z 轴旋转9 0 度后能够彼此重叠在一起这样 一种性质的所有单元划分成一类，若不相同，则类的个数也不一样。接下来计算每一 类单元中包含的三维模型的顶点数，并将其除以三维模型总的顶点数，以此构造出三维 模型的特征向量。 在由k a z h d a n 【1 8 】提出的体素化方法中，将球心的最小包围球作为三维模型重心，并 将这个模型按照该球半径为1 n 单位投射到2 幸2 n 幸2 n 的网格中，该网格的中心与三维 模型的中心重合。网格中每个格子的数值为0 或者1 ，对于任何一个格子，如果其中不 包含了三维模型表面上的点，就应将此格子的数值设置为o ，反之，应将格子的数值设 置为l 。循环地判断每一个格子的值，由此可得到了该三维模型的体素化表示。相应于 每个球壳都有一个二值化的球坐标方程，将每个方程展开可以形成球面调和函数的和， 组合函数就可以得到一组具有旋转不变性质的特征向量，组合这一系列的特征向量可形 成一个相应于此三维模型的特征矩阵，该矩阵就是该三维模型体素化方法的输出结果， 利用这一矩阵就可以比较不同模型之间的形状差异。 在基于射线方法【1 9 】中，三维模型特征提取算法可简要描述为：在模型被以原点为球 心的球包围后进行球面参数化操作，由原点分别向球面经、纬线方向均投射出一系列采 样射线，计算每条射线与模型表面的交点，从每条这样的射线与模型表面交点中选取距 原点的最大值作为该方向的采样值。从原点出发以这种方式在所有方向的进行采样，所 有的采样值构成了三维模型的特征向量。 图2 - 4 基于射线方法示例【1 4 】 针对目前大多数检索技术都只使用一个特征，而单一特征检索方法具有一定局限性 的问题，文献引中采用了这样一种方法：首先提取出两个不同的形状特征面积分布 和纬度方向平均半径，然后结合这两个特征进行模型的检索。在该方法中提出的特征提 取方式是，将模型表面点到z 轴的距离作为该模型特征，提取过程中利用距离直方图分 9 第一 = 维棱特 t 提取“ * 喊# 布特征l q 量和分块平均距离特征刚量这两种不同的特征自量表示这、距离特征。进行模 型的相似性匹配操作时，采用了从数扼库首先按第一种形状特征检索出k ，个最为相似的 模型，然后再从已选择的这k 个模型中检索出k ，个更相似的模型，其中k 远远大于 k 、，通常可以敬k ，= 2 k ，k ，= 1 0 0 212 基于拓扑形状的特征提取 通过比较三维模型的拓扑结构来莸得三维模型相似性，这是基于拓扑形状的二维模 型相似性比较算法的核心思想；其r r 】，最常使用的拓扑结构信息包括三维模型的分支与 连通性等删。如图2 - 5 所示的r e e b 图是从连通i 五域的角度柬计算二维模型的拓扑结 构。在该方法中首先将一维模型投影纠二二值图像从而作出二值图像的r e e b 图，然后 算r e e b 目的基本元素，包括圆环的个数n u m ( r ) 、刚j ：分土个数n u m ( d b ) 、川下分 支个数n u m ( u b l 、每个分支的枝权数量s u m 。最后根抓r e e b 图的这些基奉元素，计 算出r e e b 图的特征，相应的公式如下： c t t = ( d b i fs u m ( d b c h ，= n u m ( u b l ys u m ( u b 叫，= 、w f r ) - r 1 1 一 图2 - 5 坷环的r e e b 图 n ! n 一 采用基十多分辨率r e e b 圈的骨架提取方法，小仅兀丁以描述三维横型的特征同州 还县备了拙述模型的空巾拓扑关系的能力。对于局晋伫匹配乃至垒埘匹d 0 该打法都是较为 适用的。 存揣进二维模型拓扑结构的方法中除了r e e b 圈以外，述有中轴线万法。从二三维 模型骨架的角度柬计算二维模型的拓扑结构是中轴线方法的思路。如幽2 - 6 所示手骨 骼三维模型的分支结构可以通过它的骨架图较好地表选出来。 旁，爹 图2 - 6于骨骼模掣骨架图 2l3 基于视觉形状的特征提取 在基于视觉的二维模型相似性比较算法巾，通过比较= 维模型存各个万向的州赏陌 像的形状相似性u r 以获得三维模型的十日似性， 基于视觉相似的特征提取力幢的提出是基f 这样个事实：从任意视角米观察两个 相似的物体它们都应l 具有 _ | j 似性。通过比较二维模型r - ：多个方向的视觉图像的形状 相似性柬获得= 维模型的相似肚足基小丰! - ! 堂彤状的特征提取方法的基本删想。在渡方法 中，首先将三维模型投影到_ 二维观慝上，再从不同模型对应的维视幽提取特征逆行相 似性匹配| 十算。在这种算法中，m i n 的基于二维轮啊图的比较和c h e n 的牡于视觉相 似的检索技术i ”l 较为典型的例子， l o f t i e r 在预处理阶段，采用以组二迸靓表达的一维图像来对三维稹型的特征进行 描述的方法，然后仨对应的一维幽像z 唰进行后续的相似性匹配计算，并且应用了图像 橙索中戈于特征提取的方法。 在章忠勇提出的基于透视投影的三维模世几 r ! 相似盹比较尊范i “中，先将三维模型 用f 二十面件包雕，而后选取若干个祝点对三维模型进忙投影，山此可以画出二值冈像 的r e e b 隋再通过计算r e e b 图的特扯从而求h 1 投影璺像的拓扑相似距离最后叫得到 三维模型的相似距离。 图27 视点位置布置 鸡一目= 镕横! # f 取* * t m i n 提出了基于3 d 模型的2 d 轮廓罔的比较方法。在该万法中从二维模型正视、 俯视和侧视三个崮定方向提取出模型| ：! j 轮廓目，首先找到这样一个圆，该圆恰好包括了 轮廓图，将该圆等分成固定数量的圆环，构成圆环函数，然后对每个圆席进一步分解 使其由一系列三角峨数的和构成：根据旋转不变频率的振幅，u i 计算出每个圊环的特征 同量，最后，利片j 所有的圆环特征向量构成模型轮奔幽的= 维特征向量。 图2 - 8 三个方向的轮廓图 ：o 】 t2 图2 - 92 d 轮廓图特征提取叫 k ? t | i - 二一 l ：、： 在c h e n 的光场描述方法中，面过将照相机放到币1 二面体的二十六个顶点拍照，并 选择1 0 个光场下的1 0 0 张陶( h 巾每个光场下1 0 张图) ，将每个光场f 的1 0 张罔称作一 十光场拙迎。在进仔比较过程中连续自动旋转被比较的模型使两个模型的方同始终 具有一致性，两个模型的相似度等于此时光场下对应的1 0 张幽的相似度的和。 e 0 9 0 9 0 图2 - 1 0 模型的1 0 个光场描述符| 二：j 2 2 三维模型特征提取方法的评价 形状特 _ = ：捕进符足使用一定的形状特征提取方泣提取出模型在特征空川的特征阳 量。理想的形状特征问量必须满足以下条件1 ：具有几何不变性，e f g , l 模型的平移、缩 西北大学硕士学位论文 放和旋转等操作能保持几何方面的特征；特征向量须具有惟一性，即不同类型的模型对 应的特征表示应该是不相同的；易于计算以及表达；适合于相似性匹配计算的进行；不 必占用过多的存储空间；具有拓扑不变性，即当相同模型有多个拓扑表示时，同时它也应 当是稳定的，对模型的绝大多数处理，比如模型简化、噪声增减、子分、变形等处理应 当具有鲁棒性。特征空间的一组距离相近的特征向量代表两个形状相似的模型。在基于 内容的二维图像检索领域，已经提出了多种相似性距离度量方法。常用的方法包括：l 2 距离( e u c l i d e a n 距离) 2 3 1 2 4 1 、l 1 距离( m a n h a t t a n 距离) 2 5 】【2 6 1 和h a u s d o r f f 距离【2 7 】等。 设特征向量空间可表示为f = r n ，且任意的两个特征向量表示为x = ( x 1 ，x 2 ，& ，x n ) ， y = ( y l ，y 2 ，& ，y n ) ，以下给出了它们的三种距离表示的公式： i ) l 2 距离： 一 d ( x ，y ) = ( t - y ，) 2 ( 2 2 ) y t = l 2 ) l 1 距离： d ( x ，y ) = ( 薯一只) ( 2 3 ) 3 ) h a u s d o r f f 距离： h a u s d o r f f 距离通常用来对大小不同的两个点集之间的相似性进行比较，其定义为： d ( x ，y ) = m a x l 9 州m i n 埘纠d ( x ，y ，) ( 2 4 ) 在公式2 4 中，d ( x i ，y j ) 表示了两个特征点集中任意两点之间的距离度量。本文第 三、四、五章将主要采用l ：距离对特征向量进行相似性度量，而在第六章的综合实验部 分中，将分别采用l ：距离和l ，距离进行距离度量，以对它们的应用效果作出比较。由 于h a u s d o r f f 距离主要应用于不同大小的点集之间的比较，所以该度量方法并不适合于 本文。 理想形状特征向量的描述并不是一个量化的标准，因为它只能是对一种形状特征提 取方法进行研究所需考虑的方面，并不能够对方法的好坏进行评价。目前，在特征提取 算法的检索性能方面的评价方面，我们普遍采用了以下几种指标： 1 ) 查准率( p r i c i s i o n ) 查准率：黑警掣些 ( 2 5 ) 检索出的所有模型 第二章三维模型特征提取相关概述 查准率是用来衡量检索返回结果的精确性的指标。公式( 2 5 ) 为查准率的公式，它 表示正确检索的三维模型在所有检索返回结果中的比例。 2 ) 查全率( r e c a l l ) 查全率；婴警婴凳坚 ( 2 6 ) 所有相关模型 “7 查全率用来衡量检索系统返回正确结果的能力的指标。公式( 2 6 ) 为查全率的公式， 它用于衡量检索系统具备的返回正确结果的能力。 3 ) p r e c i s i o n r e c a l l 曲线 查全率与查准率均与通过该检索系统所检索出模型的数目具有很强的相关性 在一定范围内，查全率与检索出的所有模型具有正比关系，而查准率和系统检索到的所 有模型数目具有反比关系。对检索效果进行全面的评价不能仅仅通过考察查全率和查准 率而获得。一般地，我们需要通过精度一返回曲线( p r e c i s i o n - r e c a l l 曲线) 来评价检索 效果，该曲线描述了查全率和查准率之间存在的比率关系。当该曲线在整体上越靠近上 方时表示检索结果越理想，其中，过纵轴上1 0 点与横轴平行的直线是一个完美的检索 结果。 4 、第一等级匹配( f i r s t - t i e r ) 和第二等级匹配( s e c o n d - t i e r ) 假设对类型c 模型进行检索，所以相关模型的总数量为l c i ，而正确返回的模型数为 k ，则第一等级匹配( 以下简称为f t ) 和第二等级匹配( 以下简称为s t ) 的定义分别 为公式2 7 和公式2 8 ： k 丌2 陌 7 ) k s t 2 i 可丁i ( 2 8 ) 2 ( h 一1 ) “ 从以上f t 和s t 的定义可知，它们的值越大表示检索的效果越好。 在三维模型特征提取方法的评价指标中，除了以上三种以外，还存在其它的一些在 本文没有提及的评价指标。在本文的检索实验中，主要采用了上述评价指标对实现的特 征提取方法相应的效果进行评价。 2 3 三维模型预处理 通常地，我们在进行特征提取之前需要进行一系列的预处理，预处理操作的目的是 1 4 西北大学硕士学位论文 通过将三维模型变换到统一的坐标尺度下，从而使它们具有相同的位置、比例和方向， 由此来保证三维模型的特征具有几何不变性。使所有的模型具有旋转不变性、缩放不变 性以及平移不变性是三维模型规范化的目的所在，这也就是说，对于任意的三维模型， 无论对其进行了平移变换、旋转变换和缩放变换中的单一类型的变换或者多种类型组合 变换，只要我们对其进行规范化预处理，模型最终的原点、大小和方向都变成一样，这 样三维模型的特征提取就不会受到任何影响。由于三维模型检索系统的准确性不但取决 于三维模型相似性比较算法，它也同时受预处理操作的影响，因此，我们应当选择鲁棒 性较强的预处理算法。 ， 本文的三维模型规范化预处理包括三个部分，它们分别是平移、缩放以及旋转。为 了保证模型具有平移不变性，在对模型进行平移变换时，应当使模型的重心与坐标系原 点重合；为保证模型具有缩放不变性，在对模型进行缩放变换之后，应将三维模型归一 化到标准单元大小；为保证模型具有旋转不变性，应当构造旋转矩阵，对模型进行旋转 变换。公式2 9 是对这个完整的模型规范化预处理过程的表示： m = s x r x ( m 一聊p )( 2 9 ) 其中，m7 表示规范化预处理之后得到的模型，s 为缩放系数，r 为旋转矩阵，m 为原模型，m d 表示模型重心。 1 ) 平移变换 对模型进行平移变换的目的是使它的重心与坐标系的原点重合，对于满足模型的平 移变换不变性方面来说，这种平移重心的方法具有较好的鲁棒性 7 1 。公式2 10 表示了平 移变换的过程： p l = p - m p = u l u = v - m p , v p ) ( 2 1 0 ) 其中，p l 表示平移变换之后的模型，p 表示进行平移变换操作之前的原模型，m o 表示模型的重心。由上式我们可以看出，重心肌能直接影响到平移变换的效果，因此， 对它的计算是十分关键的一步。 三维网格模型通常可以被看成是密度均匀的模型，因此可以采用公式2 1 1 来计算模 型的重一已, t 6 1 ： i v d v 册p2 (211) 然而，在实际应用是对积分的计算相对较麻烦，因此可以采用仅仅计算模型的三角 第二章三维模型特征提取相关概述 网格 页点的方法，表不为公式2 1 2 如f ： n 只 = 苛 q 1 2 但是该方法并没有对三维模型顶点在模型网格表面的分布情况加以考虑。为了能在 准确性和效率之间获得一个较为满意的平衡，本文采用面积加权【3 3 l 的方法来提高重心平 移的鲁棒性，在该方法中将每个顶点的表面积作为影响因子。 三维模型中每个顶点的表面积是本文首先需要计算的值。在文献【2 9 】中对三维模型顶 点的表面积的作了这样的描述：图2 1 0 表示了三维模型中的某一个顶点，设为p ，以及 经过顶点p 的所有网格，相应的编号为0 ，1 ，2 ，3 ，4 ，n ，相应的网格面积分别是s o ，s 1 ， s 2 ，s 3 ，s 4 ，s 。，若顶点p 的表面积用s p 表示，则s p 可用公式来表示： 肇= 肋蝇悄崦蝎蝎+ 蝴 ( 2 1 3 ) 图2 1 0 三维模型顶点面积计算示意图 其中，m 表示多边形网格的边数，m 的值在模型是由三角形网格构成时为3 。从公 式2 1 1 可以看出，经过顶点p 的每个三角网格的面积s i ( 其中i = 0 ，1 ，n ) 是我们 应当首先计算出来的。三维模型大多是由三角网格构成的，因此可以采用三角形面积的 计算方法来计算网格的面积。 有多种可以计算三角形的面积方法，由于本文是针对三维模型网格的顶点的采样， 而模型三角网格各边的长度是可以通过采样点的三维坐标值得到，在获得了三角网格各 边的长度的情况下，我们就可以很方面地应用海伦公式来计算出三角网格的面积了。应 用海伦公式计算三角网格的面积，相应的公式如下： s = x p ( p - a ) ( p - b ) ( p - - c ) ，其中p = ( a + b + c ) 2 ( 2 1 4 ) 其中，a 、b 、c 分别表示三角网格各边的边长，s 为三角网格的面积。在应用海伦 1 6 西北大学硕士学位论文 公式求得每个三角网格的面积s i ( i = 0 ，1 ，n ) 之后，再根据公式2 1 2 就可以以求出经过 顶点p 的表面积s p 。重复上述过程可以依次求出模型网格中的每个顶点p 的表面积p j ( j = 0 ，1 ，m ) 。然后，将求出的模型网格每个顶点的表面积作为影响因子，应用面积 加权法可求出三维模型的重心，相应的计算公式如下： m ，= p oxs o + 异s l + + s j + + 已xs 册 ( 2 1 5 ) 在三维模型的重心i n p 被以计算出后，将该模型的重心作为新的坐标原点，并且对 将模型进行平移变换，将其平移到新的坐标原点，如公式2 1 5 所示。 二) 旋转变换 模型在经过平移变换以后，虽然它在坐标系中的位置被统一了，但是在方向上却并 不相同。不同的旋转角度会导致特征提取结果上的偏差，为了达到特征提取具有旋转不 变性这一目的，我们需要对模型作进一步