（计算机科学与技术专业论文）三维模型的形状特征提取方法研究.pdf

中国石油大学( 华东) 硕士学位论文 1 1 课题的提出与背景 第一章引言 2 0 世纪9 0 年代以来，网络的发展给人们提供了巨大的信息资源，如文本，图像， 音频，视频等。在信息社会中，人们对于信息的需求和渴望，促进了信息检索技术的诞 生和发展。而传统的文本检索模式已经不能满足人们获取知识的需求。如何快速有效的 检索到用户需要的多媒体信息已经成为一个重要问题。基于内容的多媒体信息检索应运 而生。 9 0 年代中后期以来，三维硬件技术得到较快的发展，新的三维扫描设备和交互式的 建模工具使得三维建模变得简单、高效、快捷；显卡技术的发展使得三维模型的显示和 处理速度得到大幅的提高，三维模型的实时处理变得容易；随着网络技术的发展，推动 了三维模型的传播和应用。目前三维模型被广泛用于建筑c a d 、机械制造、虚拟现实、 游戏、分子生物学和电子商务等【l l ，其数量也越来越巨大。继图像、声音和视频之后， 三维模型被称为第四代多媒体数据。 三维模型的数量剧增，给三维模型的管理和搜索带来了新的问题。面对如此巨大的 三维模型，如何快速准确的查找到用户需要的三维模型，成为一个新的研究热点 2 1 。虽 然现在的建模技术已经相当成熟，但是进行高精度的三维建模，仍然是个费时费力的过 程，而且对于一般用户而言也难以掌握。因此，如果能够通过模型检索技术，找到用户 需要的模型，或者对已有模型复用，就可以节省开支，提高效率。 早期的三维模型检索主要是通过文本检索。该方法优点是速度快，精度高。但是人 工标注存在着一定的缺陷，随着模型检索的发展，逐渐暴露出来。首先，模型库中的所 有模型需要人工标注关键字。由于模型库中的模型数以万计，因此利用关键字作为模型 的索引进行检索中，用户对所有模型标注费时费力；另外，用户对模型标注的关键字具 有很强的主观性，不同的人对同一个模型的标注可能会有所不同，因此会降低检索的精 度。 为了解决文本检索带来的问题，基于内容的三维模型检索从2 0 0 0 年开始逐步成为 研究热点。如何合理地描述三维模型成为基于内容的三维模型检索课题首先要解决的问 题，这也是本文的主要研究内容。 第一章引言 1 2 课题主要研究内容 基于内容的三维模型检索的主要研究内容包括特征提取、相似性度量、反馈机制、 性能评价等。三维模型的特征描述子的提取是关键内容，其他几个方面研究都建立在特 征提取之上。三维模型的主要属性主要有形状、颜色、纹理等。但是颜色、纹理特征是 可变的和易变的，当前基于内容的三维模型检索主要提取三维模型的形状特征。形状是 所有三维模型的共有属性。如何有效的对三维模型的形状进行描述是本课题的主要研究 内容。 三维模型特征分为全局特征和局部特征。三维模型全局特征主要是通过对三维模型 的整体形状进行分析研究，获取其形状表达；局部特征将着眼点定位于三维模型的局部 形状，利用局部网格来获取三维模型的显著局部特征。局部特征提取和局部检索是近些 年来的研究热点。 本课题从这两方面入手，完成三维模型的形状特征提取。主要研究内容如下： l 、对三维模型的整体形状进行分析，提取具有较强鲁棒性的三维模型特征描述子。 基于视图的三维模型特征提取方法是利用三维模型的一个或多个投影图像来获取特征。 该类方法利用降维的思想将三维模型投影n - 维平面上进行特征提取，不仅降低了算法 复杂度，而且具有较好的鲁棒性。本文对三维模型进行分析，研究合理的三维模型投影 平面，进而利用投影视图提取三维模型全局特征，完成检索试验。 2 、通过对三维模型的局部形状分析，计算三维模型的局部特征。局部形状分析的 一个难点是如何获取三维模型的局部区域。本文中采用距离模型顶点的测地距离小于某 个阈值的模型局部作为模型局部区域。然后在此局部区域上，提取三维模型的局部锥曲 率特征。 3 、利用三维模型锥曲率特征获取三维模型的显著性局部特征。三维模型的显著性 局部特征，是指三维模型中比较突出或者尖锐的局部网格特征。根据三维模型的局部特 征，研究分析其分布特征和几何特征，提出有效的算法获取三维模型的显著性局部特征。 4 、三维模型特征的匹配方法研究。由于不同三维模型上的显著性局部特征数目不 尽相同，而仅仅利用欧式距离来进行特征匹配已经难以满足要求。因此如何有效的组合 使用三维模型表面的显著性特征是一个重要研究内容。 2 中国石油大学( 华东) 硕士学位论文 1 3 论文的组织结构 本文结构组织如下： 第二章简要介绍三维模型检索系统的主要发展历程，并通过普林斯顿大学的三维模 型检索系统分析了三维模型检索系统的主要组成部分。主要从三维模型库和特征库，用 户接口，特征提取，特征匹配，用户反馈5 个方面讲述，描述了一个三维模型检索系统 的基本框架。最后，根据当前三维模型检索的研究热点，介绍了三维模型检索系统的发 展前景。 第三章从三维模型全局特征入手，首先分析当前三维模型全局特征提取方法研究现 状，主要分为三种类型，基于几何属性的方法，基于图的方法和基于视图的方法。本文 提出了一种基于主平面投影的特征提取方法。首先介绍了主平面的定义和计算方法，然 后给出了投影平面的特征提取方法。最后给出试验结果并进行分析。 第四章主要着眼于局部特征提取，分析了三维模型局部特征提取和局部检索的现 状。锥曲率是三维模型表面几何属性。利用锥曲率对三维模型进行分析，提出了计算三 维模型显著性局部特征的算法。然后，将三维模型显著性特征应用于三维模型检索并给 出试验结果和分析。 最后为全文总结和展望。 3 第二章三维模型检索系统 第二章三维模型检索系统 近年来，三维模型的应用已经深入到各个领域。这也带来了的三维模型的数量和数 据的剧增。因此基于内容的三维模型检索系统也得到了研究人员的关注，并取得了较大 的进展。目前已经出现了一些专业领域的三维模型检索系统和通用三维模型检索系统。 三维模型检索系统的目的是从三维模型库中有效快速的检索到用户期望的三维模型。研 究人员对于三维模型检索技术的研究早期主要集中在特征提取和匹配两个问题上。而近 些年来，随着对三维模型检索研究的不断深入，三维模型的用户交互技术，反馈技术等 都得到了关注，这也促进了三维模型检索系统的完善和发展。 2 1 三维模型检索系统发展 早期的多媒体检索系统采用基于关键字的检索方法，如三维模型检索网站：3 dc a f 6 三维模型库网和m e s h n o s e 三维模型搜索引擎【4 】；基于关键字的三维模型检索系统主要利 用三维模型的关键字作为特征来实现检索。利用关键字进行检索的优点是速度快，精度 高。但是模型关键字的标注限制了该方法的发展和应用。主要有两个方面的原因，首先 是三维模型标注的工作量，三维模型现在使用越来越广泛，模型的数量巨大，单纯依靠 人工对海量模型进行标注，将是一个费时费力的工程；另外，关键字的给出受人的主观 影响太大。对于同一个模型，不同的人给出的关键字可能也不同。而三维模型检索的精 度也会随之下降。 由于基于关键字的三维模型检索方法的固有缺陷，研究人员将目光转向了基于内容 的三维模型检索。三维模型的形状是人们对于三维模型的直观认识。对三维模型的形状 分析是提取三维模型特征的一个主要途径。自2 0 实际9 0 年代以来，基于形状的三维模 型检索方法得到了广泛的关注和深入的研究。加拿大国家研究院p a q u e t 较早的开展了 三维模型检索领域的理论研究，并开发了第一个三维模型检索系统【5 l ；美国普林斯顿大 学对此也有深入的研究，提出了一系列的三维模型特征提取方法，并建立了三维模型检 索的模型标准库；另外斯坦福大学、布朗大学、慕尼黑大学等学校也开展了相关研究工 作。国内对于三维模型检索的研究起步相对较晚，北京大学、清华大学、浙大c a d & c g 国家重点实验室以及中国科学院计算所等都进行了该领域的研究工作，并取得了一定的 进展。 4 中国石油大学( 华东) 硕士学位论文 2 2 三维模型检索系统组成 目前，已经出现了多个三维模型检索系统，其中有基于关键字的三维模型检索系统， 也有基于内容的三维模型检索系统。其中最为典型的是普林斯顿大学开发的三维模型检 索系统p s b ( p r i n c e t o ns h a p eb e n c h m a r k ) 1 6 】。该系统的整体结构如图2 1 。一个完整 的三维模型检索系统主要包括：( 1 ) 三维模型库和索引库。p s b 系统中的三维模型是通过 网络爬虫系统从网络中收集，利用特征提取模块对三维模型库进行处理，提取索引特征， 形成模型特征索引库；( 2 ) 用户接口。主要提供系统与用户的交互接口，用户根据需求 输入查询内容；( 3 ) 特征提取模块。当用户输入查询内容后，系统自动提取模型的特征， 如关键字信息、形状信息等。( 4 ) 模型匹配。提取到三维模型的特征信息以后，通过与 特征库中的特征进行对比匹配，计算相似度，并返回给用户。 拿啼国糸 离线高= = 主盔= 釜翱二 - - - - - - - - - - - 在i 线 图2 - 1 普林斯顿大学三维模型检索系统框架 7 f i g u r e 2 - 1a r c h i t e c t u r ef i g u r eo fr e t r i e v a ls y s t e m 2 1 1 三维模型库和特征库 目前根据不同的应用背景，三维模型的表达方式也多种多样。点云模型是通过三维 扫描仪直接获取的三维数据集合，点云模型由于点个数比较密集，数据量一般比较大， 而且通常会含有较多的噪声点、漏洞等，因此一般需要对其进行平滑等处理才能使用。 多边形网格模型是通过多边形集合来逼近三维模型的表示方式，由于仅仅利用了较少的 多边形，因此多边形网格模型的数据量比较小，满足实时的对其进行显示和处理，因此 应用较为广泛。其中三角形网格模型是较常用的网格结构。 普林斯顿大学提供了一个三维模型标准库，该库已经成为三维模型检索领域中默认 的标准库。该模型库1 6 1 共含模型1 8 1 4 个，分为训练集和测试集两个集合，每个集合包含 5 第= 章三维模型检索系统 9 0 7 个模型。法库分类的依据足模型的功能和形式而每个类别是分层分类，即首先考 虑模型的功能和语义，然后考虑模型的形状，另外还有对象类型完成分类。该库中所有 模型均为o f f 格式，其模型大多采用三角网格表示( 部分采用四边形表示) 。部分模型 如图2 - 2 所示 f 瓣鋈 i 。吣i 到 多鍪翌浏臻孽翼黧羹鬟鳖潮 一- -测潮浏 鬻毯藿囊j 一 隧鞫 黪浏 强翳臻毖戮鞠星鲤鳕划露羹溪鞠露臻甏潮 圈2 - 2 普林斯顿大学三维模型库部分模型 f 唔u r 吐2 3 d m o d e l s o f p s b b e n c h m a r k 三维模型特征库是模型库中所有模型的特征索引集合。对于模型库中的每个模型需 要离线计算其形状特征，并保存在特征文件中，以便方便系统查询。 212 用户接口 用户接口是三维模型检索系统的f q p ，负责用户与系统的交互。一个好的三维模型 捡索系统应该提供友好的用户界面方便的输入接口。三维模型检索的查询内容包括形 状信息和关键字信息。以何种有效的方式实现查询输入是用户接口的主要研究内容。 目前，三维模型检索系统中常采用的是多通道用户界面设计，即采用多种用户输入 方式。较常见的有三种。第一，关键字输入方式。该方式与文件检索方式相同，通过输 入模型关键字与模型库中的模型关键字进行匹配，实现检索目的。该方式用户的输入比 较简单，仅需输入文字即可完成检索。但是，模型库中的三维模型需求提前进行人工标 注，工作量比较大。另外关键字受人的主观影响较大，难以形成统一的模型标注。第 二，用例输入。该方式主要是以三维模型用例作为输入，系统自动提取输入模型的特征。 该方式虽然比较简单，并且效果也比较理想，但是用户必须预先拥有某种模型的范例。 6 中国右汕= 学( 华尔) 硕l 学拉论文 所以该方式有一定韵局限性使用不够灵活。第三是草图输入。系统提供一个绘图接口， 用户通过该接口绘制模型的二维草图，或者是三视图。系统可以提取二维视图的特征， 也可以根据三视图束重构模型，再提取特征。该方式可以实现较好的人机交互，但是对 于一般用户绘制复杂模型的草图却比较困难。所以在实际的使用过程中，往往是通过 这几种方式相结合，从而避免了单一方式的局限。如图2 - 3 为普林斯顿大学的用户输入 接口，该接口提供上述的三种输入方式。 输入接口的好坏直接决定了三维模型检索系统的检索性能和使用复杂度。因此，设 计一个理想的用户接口也十分重要。 m 文本查懈 ( m3 d 援盟查询 忙) 2 d 轮席古淘( d ) 3 d 轮廓盎珊 图2 - 3 普林斯顿大学三维模型检索系统用户接口 7 f i g u r e23u s e ri n t e r f a c eo fp r i n c e t o n3 d 肿d e lr e t r i e v a ls y s t e m 2 13 三维模型特征提取 三维模型特征提取是整个系统的关键，决定了检索系统的检索效果。目前，基于形 状的三维模型特征提取尾国内外的一个研究热点。 一个理想的三维模型特征描述符应该满足的条件为：首先是计算简单，易于进行相 似性匹配。三维模型检索系统的最终目标是通过网络达到实时检索，而这就要求特征提 第二章三维模型检索系统 取的方法不能过于复杂，否则难以达到实时的要求；第二，特征表示简洁，占用存储少。 三维模型特征维数与占用的存储成正比，维数越低，占用存储空间越小。但是，随着特 征维数的降低，特征对于三维模型的描述能力也随之降低。因此要求，在保证三维模型 特征描述能力前提下，降低特征维数，降低占用的存储空间；第三，特征具有不变性和 较强的鲁棒性。特征对三维模型的平移、旋转和缩放具有不变性，而且对于模型的简化、 细化、变形以及噪声都具有较好的鲁棒性【8 】。 目前，三维模型特征提取方法的研究已经比较深入，但是还没有一种通用的三维模 型特征提取方法，各个方法都有一定的适用范围。因此，提取一种既易于计算，又能够 有效识别同类模型的特征是该领域的一个关键和难点。除此之外，如何有效的对三维模 型特征进行融合也是现在的一个研究方向。 三维模型特征根据范围分为全局特征和局部特征。三维模型全局特征前些年的研究 较为深入，出现了一些优秀的特征提取算法，有效的提高了三维模型检索效率。全局特 征着眼于三维模型的整体形状，如对三维模型表面点、面、方向、曲率信息进行统计处 理，获取整体形状的直方图；将三维模型进行投影，从而将三维模型形状特征转化为投 影图像的形状特征；提取三维模型的骨架等拓扑结构，利用图来完成模型匹配。这些都 是全局特征提取方法，详见3 1 节。而近年来，对三维模型的局部特征的研究逐渐成为 一个热点。该类方法着眼于三维模型局部形状，利用局部的形状来区分其他类模型。另 外，局部特征能够实现三维模型的局部检索，这是三维模型全局特征难以达到的。该类 方法的研究现状详见4 1 节。 2 1 4 三维模型相似性度量 三维模型相似性度量用来衡量两个模型直接的相似程度。三维模型经过特征提取 后，可以表示为特征空间中的一个点。如果特征空间中的两个点距离越近，则说明这两 个点代表的模型越相似；反之，两个模型越不相似。因此，合适的距离度量函数可以用 来反映模型的相似程度。这样在检索过程中，通过距离度量函数来计算输入模型特征与 模型库中所有模型特征向量之间的距离，并根据距离从小到大进行排序返回给用户。排 序结果中，排在前面的模型具有较小的距离，因此与用户的输入模型越相似。这是三维 模型相似度计算过程中最常用的度量方法。 空间向量的距离计算中，最常用的就是欧式距离。假设任意两个模型的特征表示为 x = ( 而，t ，) 和y = ( 乃，y 2 ，虼) ，其中1 1 为特征向量的维数。则两个特征之间的欧 8 中国石油大学( 华东) 硕士学位论文 式距离表示为公式( 2 1 ) 。 舭肛蜃鬲 ( 2 1 ) 另外，其他常用的距离公式还有m a n h a t t a n 距离，h a u s d o r f f 距离等，其公式表示如( 2 2 ) 、 ( 2 3 ) 。 开 d ( x ，y ) = x l x ，- y i d ( x ，功= m l g a 如xl 魄d ( 毛，y j )l g ! 浙i s ，如 其中，d ( x ，y ) 表示两个特征点集中任意两点之间的距离度量 ( 2 2 ) ( 2 3 ) 除了距离度量法外，较常用的还有分类学习法。该类方法将学习的思想引入到三维 模型检索中来。分类学习方法首先预先选取一定数量的三维模型特征通过机器学习的方 法进行训练，得到相应的分类器以完成相似度匹配。常用的学习方法有神经网络、s v m 等。i b a t o 等人使用s v m 学习算法实现相似性匹配【9 】。 2 1 5 用户反馈 通常仅仅使用三维模型形状特征进行检索的结果并不理想。这主要是因为三维模型 的底层特征与高层语义有较大的差距。而反馈技术则正是为了减小两者之间的语义鸿 沟，提高检索效率。这也是三维模型检索系统的一个重要研究内容。早期的反馈技术主 要是通过用户对检索结果进行评价反馈，然后根据用户的反馈信息调整距离计算中的权 重。这种方法的优点是速度快，计算简便。另外一种方式是基于学习的反馈技术【l o l ，该 方法类似与相似性度量中的分类学习方法。这类方法不需要用户进行评价和分类，因此 减轻了用户的负担，提高效率。 9 第三章三维模型全局特征提取 第三章三维模型全局特征提取 3 1 三维模型全局特征提取方法综述 三维模型特征提取是三维模型检索中的关键，因此近年来对于三维模型特征提取研 究较多，而且大部分集中在三维模型全局特征提取。三维模型全局特征提取方法主要分 为三类：基于几何属性的特征提取方法，基于拓扑图的特征提取方法和基于投影的特征 提取方法。 3 ”基于几何属性的特征提取方法 该类方法主要是通过模型表面的点、线、面之间的几何关系，利用统计方法获取三 维模型形状描述子。 扩展高斯图( e x t e n d e d g a u s s i a n i m a g e ) 是通过三维模型面片法向进行统计来获取 形状特征【i l l 。该方法由h o r n 在1 9 8 4 年提出。该方法首先将三维模型面片法线映射到模 型的高斯球面上，如图3 1 所示。映射过程中，法线的法向不变，法线的长度为法线所 在面片的面积。这样形成的高斯球面被称为扩展高斯图像。三维模型的扩展高斯图像包 含了模型的所有法线信息，对与三维模型的几何特征具有一定的描述能力。 爨) 立方体( b ) 立方体 图3 - 1 立方体扩展高斯图像1 f i g u r e 3 1t h ee g io fc u b e 得到模型的扩展高斯图像后，将高斯球面进行划分，然后对每个区域的法线信息进 行统计，即可得到该模型的扩展高斯图特征。文献 1 2 1 中将模型的高斯球面沿着经度划 分为r 个单元，然后沿着维度划分为c 个单元，这样统计r * c 个单元的法线信息，即 可得到一个r * c 维的特征向量。 c o r d - b a s e d 方法【1 3 】是统计三维模型表面顶点与模型主轴之间的几何关系。三维模型 的主轴通过主成份分析获得。首先利用三维模型的所有顶点来生成一个协方差矩阵，然 后计算该矩阵的特征值和特征向量，并将其按照特征值从大到小的顺序排序。这样最大 1 0 中国石油大学( 华东) 硕士学位论文 特征对应的特征向量即为模型的第一主轴，次之为第二主轴。c o r d 定义为三维模型顶点 与模型质心的联系，得到三维模型主轴之后，统计c o r d 与第一主轴的角度分布，c o r d 与第二主轴的角度分布，以及c o r d 的长度分布。这样每个模型得到三个特征向量，利用 三个特征向量来计算三维模型的相似度。 形状直方图方法的思想则是统计三维模型表面顶点的分布特征【1 4 】。该方法需要对对 模型空间进行划分，以便对点的分布进行统计。如图3 2 所示，作者提出了三种划分方 案，同心球划分，扇形划分和混合划分。这三种划分方法中，同心球划分的划分比较粗 糙，对与模型的形状表达不够精细，描述能力有限。但是该中划分方案却对于模型的旋 转具有不变特性，因此计算简单，无需对模型预处理；而扇形划分则对模型的划分比较 精细，描述能力较强，但是该划分对与模型旋转不具有不变性，需要对模型进行标准化 处理。完成模型区域划分之后，对模型的每个区域的点进行统计，得到模型的形状直方 图。 惩珍 钇p 藤毓 j 蜡耖 4s h e nb i n s 1 2s e c t o rb i n s4 8c o m b i n e db i n s 图3 - 2 模型的三种划分方案 1 4 f i g u r e3 - 2t h r e em e t h o d so fm o d e lp a r t i t i o n 由普林斯顿大学r o b e r to s a d a 提出的形分布方法主要是统计三维模型表面随机点的 几何关系【1 5 】【1 6 1 。随机点的几何关系由5 个形状函数给出。模型质，c , n 模型表面随机点的 距离( d 1 ) ，两个随机点的欧式距离( d 2 ) ，三个随机点形成的三角形面积的平方根( d 3 ) ， 四个随机点组成的四面体体积的立方根( d 4 ) ，三个随机点组成的两个向量夹角角度 ( a 3 ) 。根据这些形状函数，计算模型表面随机点组合的函数值，统计值的分布形成特 征向量。根据试验结果发现，d 2 函数的描述能力最强，检索结果较好。d 2 形分布特征 计算过程简单，鲁棒性强，尤其对模型的旋转、平移和放缩都具有不变性，是一种较好 的三维模型特征描述符。 第二章二维模犁伞局特 t 提取 图3 - 3 形状函数示意图 15 f i g u r e 3 3s h a p ef u n c t i o nf i g u r e o h b u c h i 根据重叠窗口内的模型顶点的分布，提取三维模型特征。如图3 f 4 所示， 沿着模型的主轴进行等间距分割，每个分析窗口由两个间距组成，并且相邻的两个分析 窗口是重叠的。三维模型的主轴也是通过对模型进行主成份分析得到。得到模型的分析 窗口以后，计算每个窗口中包含的模型顶点的惯性矩、顶点到主轴的期望和标准差，计 算公式如( 3 - 1 ) 所示。该方法采用重叠的分析窗口对模型顶点分布特性进行分析，利 用了较多的信息，检索效果较好。 咿喜蚌，2 芬 2 击姜旷叫2 n 表示分析窗口内的点个数，p 是主轴索引，是模型顶 ( 3 1 ) 点与主轴的距离 鑫 l 蔗 擎“ ： 尸m 图3 q 分析窗口示意图 1 7 f i g u r e 3 - 4t h ea n a l y s isw i n d o w 31 2 基于拓扑固的特征提取方法 三维模型骨架能够有效的表示三维模型的拓扑结构，因此可以用于三维模型的相似 性匹配。a m e n t a 利用三维模型的v o r o n o i 图米提取三维模型骨架( 】q ，从而利用骨架图 的匹配实现三维模型相似性匹配。但是，该方法中v o r o n o i 图的计算量比较大，对模型 的要求较高，对噪声具有较差的鲁棒性差，不能直接处理带有孔、洞的模型。 中凼l 】油人学( 华东) 硕士学位论文 h l i a 9 8 利用多分辨率r e e b 图作为三维模型特征进行模型匹配i ”】。r e e b 图计算的= ) 毛 键是m o r s e 函数的选取。利用m o r s e 函数对三维模型进行形状分析中常用的函数是高度 函数f ( x ，y ，：) = ：。利用高度函数来计算三维模型的r e e b 图，计算较为简单，但是该r e e b 图却不满足旋转不变性。当模型旋转后，三维模型的r e e b 图则会发生变化。因此，h i l a g a 采用了积分测地距离函数。三维模型顶点的积分钡4 地距离是该点到三维模型其他顶点的 测地距离之和。该距离对三维模型的旋转具有不变性。这样，以积分测地距离函数作为 m o r s e 函数来生成三维模型的多分辨率r e e b 固如图3 5 所示。这样三维模型的匹配即 转化为r e e b 图的匹配。该方法对于模型的变形、简化、子分等都具有不变性，但是汁 算r e e b 图的过程汁算量比较大而且r e e b 图的匹配也比较复杂。 厕两蓊 。鹞建i 圉35 多分辨事r e e b 图的构造 1 9 f i g u r e3 - 5n _ ec o n s t r u c t i o no f 碓 g a r ykl t a m 针对于模型的变形问题提出了基于拓扑点和拓扑环的方法。三维 模型骨架对于三维模型的变形具有不变性，但是骨架提取过程比较复杂，计算量较太。 作者通过拓扑分析提取三维模型表面的拓扑点( 关键点、鞍点) ，井根据拓扑点来计算 模型表面的拓扑环。除了利用拓扑特征，作者还提取了每个拓扑环的几何特征( 面积、 曲率等信息) 。最后利用e m d 算法计算三维模型的相似度。该方法对于三维模型的变形 具有较好的识别能力。 k 耐 图3 - 6 三维模型拓扑环 2 0 2 f i g u r e3 6t o p o l o g i c a lr i n go f3 dm o d e l 1 3 第三靠二维模型全局特征提取 王飞等人口i 采用了势场方法提取三维骨架，然后对模型进行分解。即利用骨架箝点， 在节点处将骨架拆开，每个骨架段代表一个子部分。提取每个子部分的球谐描述子特征 作为几何特征，模型的相似度计算分为两部分。一是模型的整体相似性计算，主要是用 e m d 算法计算两个模型的骨架相似性：二是计算模型对应子部分的相似性，模型对应子 部分在计算骨架相似性步骤中标出，距离采用欧式距离。模型的总相似性为两部分的加 权和。 二维模型的拓扑特征可毗有效的解决三维模型的变形问题对于模型的整体结构有 较好的描述。但是该类方法对于模型的要求比较苛刻，对于模型的噪声鲁棒性较差：另 外，该类方法的计算复杂度比较高，如何有效的减少计算量也是一个重要的研究内容。 31 3 基于视图的特征提取方法 基于视图的特征提取方法也是一类较为常用的三维模型特征提取方法。该方法通过 是利用三维模型的一个或多个投影视图来提取特征。由于模型视图较好的符合人的视觉 感受，而且模型视图对于模型的噪声、简化等的鲁捧性较好，该类方法得到了广泛的应 用， o h b u c h i 利用了4 2 幅模型视图进行相似性的匹配【划。作者将位于模型包围球上的 二十面体通过循环细分算法产生一个8 0 面多面体。这个多面体的4 2 个视点上分别作为 视点进行投影得到4 2 幅深度视图，如图3 7 所示。然后，利用通用傅立叶描述子计算 4 2 幅深度视图特征。这样三维模型的匹配转化为视图的匹配。在匹配中，两个视图的距 离定义为一个视图与其他模型4 2 幅视图的最小距离。但是，该计算过程的计算量比较 大。 徊i 鏖 图3 74 2 个视点以投影后的深度图像 2 2 f i g u r e3 - 7t h ed e p t hb u f f e ri m a g e 与上述获取视图的方法类似，c h e n 提出了三维模型的光场描述子特征鲫。该方法 中利用位于三维模型包围球面上的正十二面体的二十个视点作为视点对来获取视图。由 于正二十面的对称性，二十个视点可以得到十幅视图，从而模型的相似性转化为十幅视 1 4 中国石油大学( 华东) 硕士学位论文 图的相似性。如图3 8 所示。 每盯雩 嘧1 沁念沁 图3 8 椅子模型的十幅投影图像 2 3 】 f i s u r e 3 - 8t e np r o j e c t i o ni m a g e so fac h a i rm o d e l 对于得到的投影图像，c h e n 计算了两种特征：基于区域的z e m i k e 矩特征【2 4 1 和基于 轮廓的傅立叶描述子【2 5 1 。这样通过计算投影图像的相似度来计算模型的几何相似性。为 了提高方法的鲁棒性，c h c n 通过旋转正十二面体的空间位置来获得多个光场描述子， 利用了较多的空间信息，检索效果优于许多传统方法。 刘伟等提出了基于正交投影的三维模型特征提取方法【2 6 】。由于三维模型在空间中具 有任意的位置、方向和大小，为了获取统一的投影方向，需要对模型进行预处理，将模 型放入统一的坐标系中。预处理结束后，以模型的a a b b 包围盒的六个面作为投影平面， 从而获得六幅灰度图像，如图3 - 9 ，文中作者用了两种二维图像特征：h u 矩和傅立叶描 述子。 图3 9 模型a a b b 包围盒投影c 2 6 f i g u r e 3 - 9t h ep r o j e c t i o no nt h em o d e l sa a b bb o u n d i n gc u b e 由于投影之后得到的图像并不能全部反应模型的形状。所以对于不同投影平面的相 似度距离给予不同的权值。作者给出公式( 3 - 2 ) 进行相似度计算： d = 乒觋，+ 乒币磁。+ 4 e v , e v , d 曩 ( 3 - 2 ) e v x 、e v y 和e v z 分别表示p c a 过程中的三个特征值，d x y ，d y z 和d z x 表示投 影图像的距离。这样，对于包含信息越多的图像，在相似度计算中作用越大。从检索试 1 5 第三章三维模型全局特征提取 验看，i _ 爰方法的p r 曲线略低于光场描述子的曲线，但是采用了较少的视图，计算效率 得到了较大的提高。 c h e n t s u n gk u o a 将主平面应用到三维模型捡索中i “i 。三维模型主平面满足模型表 面的所有点到该平面的距离和最小，如图3 1 0 。该平面是模型的形状参考平面，因此可 以利用该平面计算特征。该方法思想与视图方法类似，将模型所有顶点投影至主平喵上 并计算投影点集的凸包并完成凸包的三角化，如图所示，然后提取每一个三角形内点集 的统计特征将所有三角形的特征集合作为该模型的特征。在模型相似性度量时利用 动态舰划算法进行计算，并取得较好的检索效果。 图卜1 0 模型主平面及其凸包的三角剖分 2 7 f i g a r e3 - 1 0t h ep r i n c i p l ep l a n eo f3 dm o d e l o h b u c h i 根据模型特点提出了两种特征提取方法【捌。一种是有关节模型特征的 b f - s i f t 特征提取方法，另一种是提取刚性模型特征的i m - s i f t 特征提取方法。两种方 法都是利用投影方法提取投影视图的s i f t 特征。b f - s i f t 是将全部视图的s i f t 特征利 用包特征( b a g s - o f - f e a t u r e s ) 的方法映射为一个字符表，然后统计整个模型的字符频率 直方图，从而将大量的s i f t 特征转换为一个直方图，无论在存储量上还是在计算量上 都有了大幅的降低。而i m s i f t 则在预处理中通过p c a 将模型归一化，然后利用同一 角度的视图的s i f t 特征计算距离，最后累加所有的距离即为模型的相似度。通过检索 结果的p r 曲线表明，对于关节模型检索b f s i f t 检索效果要优于光场描述子方法；而 对于剐性物体，则基本与光场描述子方法持平。 ，蓄“沁鸯 呻 。 坩 中国石油大学( 华东) 硕士学位论文 3 2 三维模型主平面 三维模型的主平面是三维模型的形状参考面。该平面满足三维模型表面所有顶点到 其距离和最小。为了表达的方便，首先对模型进行位置归一化操作，由公式( 3 3 ) 计 算模型质心，对模型其进行平移操作，将模型质心平移到坐标系的坐标原点。 c ，- ，) = c 专姜，专喜咒，专喜z ， c 3 引 设( a ，b ，c ) 为过模型质心任一平面的单位法向量，则该平面可以表示为( 3 - 4 ) ： 见= a x 。+ b y + q ( 3 4 ) 根据图3 1 1 可知，点c 为模型质心即坐标原点，c l 为模型上顶点，c l 为模型点 到主平面上的投影，而c i c l 即为模型点到主平面的深度值，由公式( 3 5 ) 可得深度值： 见= 出+ 砂+ q ( 3 5 ) 图3 - 11 模型主平面以及点到主平面深度示意图 f i g u r e3 。1 1t h ep r i n c i p l ep l a n e 模型的主平面为满足所有点到的深度值平方和最小的平面，假设s 3 模型的所有点， h 为过模型质心的所有平面，则主平面h 满足条件( 3 6 ) - 北m i n 万( s 3 , 耻m i n 猪一孑1 1 2 = 血n y z 。，磊矿( a x + 砂+ c z ) 2 ( 3 石) 上式对a 、b 、c 分别求导，并令各式等于零，可得： 1 7 第三章三维模型全局特征提取 2 x ( a x + b y + c z ) = 0 ( x , y 。：) e 2 y ( a x + b y + c z ) = o ( 3 7 ) 2 z ( a x + b y + c z ) = o ( x , y z ) e s j 展开后得： 鸭o o a + 确，l 。o 曰+ 铂，o 。i c = 0 码，l 。o 彳+ ，2 ，o b + 确，l ，l c = 0 ( 3 8 ) 嬲。o ，l 彳+ ，l ，t b + 刀l l o o ，2 c = 0 其中，j j 为模型的几何矩， 啦舢= x s y ， ( 3 9 ) ( j ，y ，z ) e f 另外已知条件，b ，c ) 为单位向量，则a 2 + b 2 + c 2 = 1 ，根据公式( 3 8 ) ，可以 求解出a ，b ，c ，从而得到模型的主平面。 3 3 主平面特征提取 3 3 1 主平面投影 主平面可以作为三维模型的形状参考平面。将三维模型向该平面进行投影后的视图 能够用于三维模型的特征提取。而在实际投影过程中，仅仅利用三维模型表面顶点来计 算主平面，其对于模型的细化、简化的鲁棒性不强，而且视图图像也会受到影响。为了 得到一个稳定的主平面，本文采用了蒙特卡罗方法f 1 卅对三维模型进行表面采样，利用采 用点计算主平面。主平面的稳定性得到了较大的提高。 蒙特卡罗方法，是一种基于“随机数 的计算方法，又被称为计算机随机模拟方法。 它的思想就是利用事件发生的频率来决定概率。而在三维模型随机点采样中，利用三维 模型面片的面积大小来决定随机点在该面片出现的概率。基本方法如下。首先生成一个 与面片个数一致的数组，用来存储当前访问到的面片的面积和。然后遍历三维模型的所 有面片，每次访问到一个三角形时，将当前访问到的所有面片的面积和存入数组中对应 的位置。然后随机生成一个大于零小于模型面片和的随机数，并采用折半查找算法在面 积数组中查找随机数的位置，该位置即当前随机点所在的三角面片索引，该三角形被找 到的概率正比与它的面积。找到三角形后，在三角形内部通过公式3 - 1 0 来生成一个随 机点。图3 - 1 2 为蒙特卡罗方法的流程图。 1 8 中国石油大学( 华东) 硕士学位论文 p = ( 1 一和彳+ ，( 1 一r d b + 扁c a ，b ，c 为面片三个顶点，r l ，眩为0 - 1 之间的随机数，p 为生成的随机点 图3 - 1 2 蒙特卡罗方法流程图 f ig u r e3 1 2f l o wc h a r t so ft h em o n t e - c a r l om e t h o d 1 9 ( 3 1 0 ) 第二章三维模型全局特征提取 三维模型的采样效果如31 3 所示。通过此采样点求敬主平面，对于相似的同类模 型在主平面t 的投影具有较大的相似性，可以利用该平面进行投影，提取投影图像的特 征进行相似度计算。 图3 一1 3 三维模型表面采样效果 f i g u r e 31 3t h es a m p l eo fah u m a nm o d e l 332 投影视凰轮廓追踪 为了获取统一大小的投影图像，我们首先对模型进行尺度归一化操作即利用模型 的最大半径进行归一化。然后以主平面的单位法向量处作为视点，利用o p e n g l 绘制模 型，获取深度信息( z b u f f e r ) 得到一幅深度图像并对模型提取轮廓。本文采用p a v l i d i s 的边界追踪算法2 9 1 。 该边界追踪算法适用于灰度图像的边界追踪。进行边界追踪时，关键是追踪方向的 确定。因此，该算法规定了边界追踪的方向。假设初始的图像如图3 一1 4 ：图像中在追踪 的起点放置一只昆虫。每次追踪下一个像素时，昆虫的前进方向为前方的三个像素之一。 乳 蓼7 # 二： p 1mt 嘻 图3 - 1 4 追踪算法的起点像素 f i g u r e3 - 1 4b e g i n n i n gp i x e lo fc o n t o u rt r a c i n g 规定昆虫进行p 1 ，p 2 和p 3 的三种情况如下： 2 0 基黼嚣鞭 中国打油大学( 华东) 硕十学位论文 如果p 1 像素为黑色，则p l 为下一个边界像素。昆虫的前进路线为先从p l 向前移 动到p 2 ，然后由p 2 向左移动到p 1 。如图3 一l5 ( a ) 。 如果p 1 像素为白色时，检查p 2 像素。如果p 2 为黑色，则将p 2 定义为下一个边界 像素。则昆虫直接向前运动至p 2 位置。如图3 1 5 ( b ) 。 如果p 1 、p 2 都为白色。则捡查p 3 ，如果p 3 为黑色，则定义p 3 为下一个边界像素。 则昆虫首先向右移动到右侧像素，然后在向上移动到p 3 。如图3 - 1 5 ( c ) 。 如果p l 、p 2 、p 3 都为白色时，则将昆虫的方向沿着顺时针旋转9 0 。如果三个点 仍为白色，则继续旋转。如果旋转三次后，三个点都为白色，则说明该点为独立的前景 点。循环结束。如果当前昆虫的位置回去起点时说明边界追踪结束，退出程序。 剁隧 i 獠 黎& 鼹i 隧 ( a ) ( b )( c ) 图3 一1 5 边界追踪方向 f i 曲r e3 一1 5d i r e c t i o no f t 。u rt r a c i n g 利用该算法能够对图像的轮廓有效的提取。图3 1 6 显示了利用边界追踪算法对三 维模型主平面投影图像进行轮廓提取的轮廓效果。这样在灰度图像和轮廓图像上就可以 提取形状描述子了。 图3 _ 1 6 模型主平面投影及其轮廓提取 f i g 叮e 3 1 6t b ep r o j e c t i o ni a g e o np r i n c i l ep l fh d e l 332 投影视图特征提取 由于三维模型通过投影至主平面后得到了一幅代表模型形状的二值图像，因此这样 可以将三维模型相似性比较转化到二维图像的相似性计算。本文选取了两种图像特征进 2 1 日 中国石油大学( 华东) 顶l 学位论文 因此可以利用曲率作为信号函数其曲率函数定义公式( 3 1 4 ) ( 3 一1 5 ) 为 ( ，) = 烈，) 一口0 1 xt = 0 ，1 h( 3 4 ) 一m 爱誊舄，岫点的隅t = o ，l ，一 n m 实验结果显示采用中心距离作为边界信号检索效果最好，因而本文采用该信号函 数。对形状信号s ( k ) 的傅立叶变换为式( 3 1 6 ) ： “= 专知e x 烈二等如砒， n m 傅立叶描述子与形边界的尺度方向和曲线的起始点位置有关。因此一般对傅立叶拙 述子归一化后再进行识别，这样就具有了旋转、平移和尺度不变性的特性。归一化后的 傅立叶描述子为公式( 3 ”) ： 34 实验结果分析 纠高，劂俐， 本试验采用普林斯顿三维模型数据库测试集，共包括9 0 7 个模型，分为9 2 类。为了 获取较为统一的主平面，对所有模型均采样3 0 0 0 0 个点，然后计算主平面并投影。图3 1 8 为h 啪a 1 1 类的5 个模型的主平面投影图像，以及图像的轮廓提取。 工舯工孽=w 剁卫翟 中国打油学( 华东) 硕士学位论文 图3 一1 9 检索结果。其中红色标记为待检索模型 f i g u r e 3 1 9t h er e t r i e v a lr e s u l t s 本文采用p r 曲线对实验结果进行评价。p r 曲线是最常用的一种衡量检索性能的定 量分析指标，表现了查准率( p r e c i s i o n ) 和查全率( r e c a l l ) 之间的函数关系其中横轴为查全 率，级轴为查准率。计算公式( 3 1 8 ) ，其中n 为正确检索的相关模型，c 为所有相关的 模型，a 为检索返回的模型总数： p v e c i s i o n ：一n ，r e c a l l ：旦( 3 - 1 8 ) ac 查全率表示返回的正确检索模型占整个相关模型的比例，这个指标衡量捡索系统返 回正确结果的能力，查准率表示在所有检索返回结果中，正确检索的三维模型的比例， 这个指标衡量检索返回结果的精确性。整体上位置靠上的曲线代表较好的检索结果。本 实验与形分布方法进行比较，形分布方法采用对采样点对的距离进行统计，最后得到的 特征向量维数为1 0 0 ，得到的p r 曲线如图3 2 0 。从p r 曲线可以看出，主平面投影方法 检索结果要好于形分布方法。 35 小结 本章提出了一种基于主平面投影的特征提取方法。利用主平面作为三维模型的形状 参考面，然后计算整个模型在该平面的投影的轮廓特征。该方法的优点是计算速度快、 效率高。从检索的试验结果看主平丽描述子要由于形分布方法。但是仅采用一个平面 对三维模型投影，因此三维模型的形状信息会有部分缺失，影响了整个检索效率。因此， 下一步的研究方向是将计算其他的投影平面。利用多个投影平面的形状特征进行检索， 提高检索效率。 ；鼻蠹一黛；|测墒 骂寰 圉再鬲爹譬掣 型剿期嘞 因磊习 第四章= 维模型局部特征提取 p h i l 咕s 描j a i l e ，t h o m