基于最优搜索理论的三维模型检索技术研究

1、电子科技大学硕士学位论文基于最优搜索理论的三维模型检索技术研究姓名:彭博申请学位级别:硕士专业:计算机系统结构指导教师:朱清新20060510 电子科技大学硕士学位论文裂或表面重叠的现象(见图1-1。比如一些经典的模型:Utah茶壶模型(见图l一2就是没有底的模型,Stanford大学的bunny模型在底部也有几个空洞。这些都给特征提取带来一定难度。 图1.1具有噪声、空洞和重叠的多边形表示图1.2没有底座Utha茶壶一个典型的三维检索系统框架如图1.3。系统分为联机处理和脱机处理两部分。为了提高在线检索的效率,需要采用索引结构来组织模型数据库,并选取有效的检索算法。用户可选择模型的ID、待检

2、索的三维模型或模型素描作为系统的输入部分。特征描述器计算每个三维模型的特征值。在线检索计算模型的相似度,然后提取符合检索要求的模型,最后将结果显示出来。现有的检索系统能提供比较友好的检索界面,可以用多种方式检索: 图1-3三维检索系统框架(1文本和二维或三维草图方式,即用几个关键词或用户手绘制的草图进行检索: 电子科技大学硕士学位论文图片。用户也可通过双击图片来检索与之最相似的模型。 图1.5三维模型检索引擎的用户界面1.3本文的工作与创新点本文从一个全新的角度考虑三维模型的检索问题。我们假设用于检索的时向是有限的,并且检索工作不一定能够完成。在这种情况下,考虑以最大概率或者用最短的平均时间完

3、成检索工作的方法就十分重要。结合最优搜索理论的思想,本文研究了三维模型检索的最优搜索策略:首先研究了时间资源有限条件下,使发现目标概率最大的最优搜索策略;其次研究了当检索过程中存在假目标时,采用泛搜索和深度搜索的两步搜索方法,并且使平均检索时间最短的非适应性搜索策略。本文的内容组织如下:第二章首先介绍三维模型检索的主要技术,包括特征提取算法、距离度量方法。第三章介绍最优搜索理论的基本研究内容和常用的几种优化方法。在第四章中,研究了在搜索时间资源一定时,满足最大探测概率的最优搜索策略。在第五章中提出存在假目标情况下,采用两中搜索方法时,使平 电子科技大学硕士学位论文2.2.1基于空间全局特征的特

4、征提取算法三维模型的全局特征是对三维模型形状的全局性描述,比如体积、表面积、边界轮廓等等。Zhang和Chen16】提出了用三维模型体积、表面积和傅立叶变换后得到的系数来表示网格模型特征的方法。首先需要对模型进行三角形化的预处理,然后将三角形各顶点与坐标原点相连,组成一个四面体。所有这些四面体的体积求和得到模型的体积。文献针对使用积分求和的一类问题给出了通用的算法,所以同样的方法可以运来求模型的距和傅立叶变换。由于算法复杂度取决于网格中边和点的个数,因此计算量大。 图2-2汽车、立方体和椅子三维模型反射对称特征描述将傅立叶变换在二维球面空间进行扩展产生了球面调和分析方法(Spherical H

5、armonicAnalysis。文献18J中提出了获得模型特征旋转不变性的另一种方法:基于球面调和分析反射对称特征。Kazhdan等【19l提出了计算三维模型反射对称轴的方法。二维和三维物体的反射对称轴计算是计算机视觉中的一个经典问题,它可以作为模型的一个全局特征表示。该特征对于反射变换具有不变性。计算通过模型质心且垂直于单位向量的平面的反射对称值,该值用来对球面上的单位向量进行伸缩,以此构成模型的形状特征值。这些值的特征在对称轴处取得极值。图2-2描述了三维模型对应单位球体变换得到的反射对称特征。反射对称值的计算以工维平面上的圆周为基础。在圆周上,两点关于过圆心的对称轴的距离很容易计算。而任意的二维图形都可以用一系列同心圆进行分割