基于形状特征的三维模型检索技术综述

基于形状特征的三维模型检索技术综述1徐士彪，车武军，张晓鹏+(中国科学院自动化研究所模式识别国家重点实验室-中法联合实验室-数字内容技术研究中心,北京100190)摘要:在CAD产品设计、3D产品展示、影视动漫制作等应用中经常使用成千上万共享的3D模型，但现有的搜索引擎还不提供有效的3D模型检索服务。基于内容的检索技术能有效地根据3D模型的实际内容，如几何形状，拓扑结构等，查找到用户的期望的模型，因而可以用于自动智能检索。本文综述了目前基于形状特征的三维模型检索的主要关键技术，对常用的特征类型进行总结，并重点对特征提取方法进行分类总结。其中基于统计特性的特征提取方法比较简捷，计算简单，但对三维模型的内容描述不够充分；基于扩展特征的方法适用于结构变化较小的网格模型，但计算量较大；基于体素化的特征利用了模型的体积特征，加速了检索过程，效率较高，但不支持多分辨率检索；基于射线采样的特征适合较为简单的模型形状,但容易出现二义性；基于视图的特征主要是在三维模型的二维投影视图上提取的，计算复杂度较低，但容易丢失一些表示三维结构的重要信息。本文同时列举分析了当前实现并发布的典型检索系统。此外，对未来的研究方向进行了展望性描述。关键词:三维模型；几何形状；拓扑结构；三维模型检索；通用特征中图分类号：TP391Asurveyof3DmodelretrievalbasedonshapefeaturesXUShibiao,CHEWujun,ZHANGXiaopeng+（NLPR-LIAMA-DigitalContentTechnologyResearchCenter,InstituteofAutomation,CAS,Beijing100190,China）Abstract:Alargenumberof3Dmodelsaresharedin3Dapplications,suchasCADproductdesign,3Dproductexhibition,movieandanimationproduction.Buttheexistingsearchenginescannotprovideaneffective3Dmodelretrievalserviceforthoseapplicationsyet.Thecontent-based3Dmodelretrievaltechniqueismainlybasedontheintrinsicshapeofa3Dmodel,suchasgeometryandtopology,soitcanbeusedtosearch3Dmodelsautomatically.Thispapersummarizesthekeytechniquesof3Dmodelretrievalbasedshapefeatures,andcollectsthecommonlyusedfeaturesforretrieval,especiallytheirextractionmethods.Methodsbasedonstatisticalfeaturesareeasytoimplement,butthesefeaturescannotdescribethemeshshapeadequately.Methodsbasedonextendedfeaturesaregoodforamodelwithgentlestructurechange,butcomputationalcostishigh.Voxelizationbasedmethodsuse1收稿日期：2010-xx-xx基金项目：国家自然科学基金（No.60970093,No.60902078，No.60872120）；863计划项目（No.2008AA01Z301）；上海市科技重点攻关项目(No.08511501000）作者简介：徐士彪（1986.1－），男，汉族，硕博生，主要研究方向为计算机图形学，中国科学院自动化研究所模式识别国家重点实验室-中法联合实验室-数字内容技术研究中心。通讯作者：张晓鹏，研究员，博士生导师。E-mail:[e-mail]22volumecharacteristicsofthemodeltospeeduptheretrievalprocess,butfailtosupportmulti-resolutionsearch.Methodsbasedonraysamplingaresuitableforasimplemodel,butitispronetoambiguity.Viewbasedmethodsmainlyextractfeaturesfromtwo-dimensionalprojectionviewofamodelandhaslowcomputationalcomplexity,butmaylosesomeimportant3Dstructureinformation.Thispaperalsoenumeratesandanalyzestypical3Dmodelretrievalsystemshavingbeenachievedandpublisheduptonow.Finally,weconcludethispaperwithanoutlookforthefuturedevelopmentof3Dmodelretrieval.Keywords:3Dmodel;geometrytopology;3Dmodelretrieval;generalcharacter引言三维几何模型从几何角度再现了真实世界中物体的形状信息。随着3D模型建模、数字化、可视化技术的进步，三维几何模型的研究得到了越来越多的关注，在工业产品设计、影视娱乐、电子商务、文物保护、城市规划等各方面应用需求的驱动下，得到前所未有的关注。数字几何信息被认为是继数字音频、图像与视频之后的第四类数字媒体[1]。随着数字化生产与消费的发展，生成了越来越多的数字几何信息，迫切需要对这些信息加以处理、分析和识别，以便有效地理解，利用，甚至再利用这些信息，进一步提高生产力。在网络上，大量的3D模型可供使用，充分利用已有的3D模型数据资源，可以大大减轻设计新模型的工作量，同时也可以促进3D数据的流通和在各领域的应用，因此迫切需求对3D模型进行有效的检索。同其它多媒体数据检索技术相似，3D模型检索分为基于文本和基于内容的检索。基于文本的3D模型检索实现简单，但不具有鲁棒性，主要体现在以下几个方面：（1）并不是所有的模型都能够通过文本得到很好的定义；（2）用户可能不熟知某些模型关键字；（3）文本描述对被检索的模型可能范围过窄或过宽；（4）文本描述会随时间变化，如设计者的改变或命名原则的改变；（5）对海量的模型加注信息需要大量的人力和物力。基于内容的检索主要根据3D模型的实际内容(几何形状、拓扑结构等)来自动检索，与文字描述相比，更能客观地表达模型自身的特征，因此比基于文本的检索方法更有效。基于内容的三维模型检索技术总体分为三类：(1)基于形状的技术，通过提取3D模型形状特征进行检索，如球面调和，形状分布检索技术；(2)基于拓扑结构的技术，通过提取3D模型的拓扑结构特征进行检索，3D骨架的提取；(3)基于图像比较的技术，对3D模型提取特征量，反过来通过对比特征量进行检索。基于形状特征的三维模型检索是一种实现3D模型有效检索的重要技术手段。它是指直接根据描述对象的形状特征为依据进行检索，能从数据库中查找到具有指定特征或含有特定内容的三维数据，在三维模型应用的各个领域中都能起到重要作用。目前，基于内容的三维模型形状检索技术的发展备受关注，随着对3D形状匹配技术深入研究，提出很多新颖的形状检索和查询方法，从而使模型匹配与检索更有高效、精确。多数具有真实生命的对象的3D模型可以通过颜色、纹理和形状信息进行区分。但是，颜色和纹理在某些模型中可能会失效，例如3D蛋白质模型。因此，形状是描述3D数据最基本的特征。本文以基于形状特征的三维模型检索技术为研究对象,首先详细介绍基于形状的三维模型检索系统，从系统框架等方面予以充分的说明；继而详述三维模型形状特征提取方法，对各种算法的优劣进行分析对比；与此同时分析对比了三维模型形状相似性匹配的常用方法；最后，在总结前述内容的基础上，从局部特征检索和通用特征描述两方面对未来的研究徐士彪等:基于形状特征的三维模型检索技术综述33方向进行了展望。此外，列举并分析了在三维模型检索领域中已经实现并发布的一些典型检索系统。1基于形状的三维模型检索系统基于形状的三维模型检索技术是近十几年孕育出来的新研究领域，其检索方法的思想起源于基于内容的图像检索，是目前比较活跃的研究领域，但是总体上还处于研究的初期，有许多问题有待进一步的研究。大多数学者认为关于面片模型的基于内容检索的论文首次发表于1997年[1]。近几年，许多大学和研究机构都进行了基于形状的三维模型检索的研究，并推出相应的检索系统，如普林斯顿大学、台湾大学、莱比锡大学等（见第4节），其总体架构大同小异。因此我们首先对一般的3D形状检索系统作总体介绍。1.1三维形状检索系统总体框架图1是一个典型的3D形状检索系统框架，系统包括带有索引结构的数据库和在线查询引擎，其中的数据库是在离线的情况下创建的。从图中可知，模型检索包括模型的标准化、特征提取与构造索引、相似性匹配及检索界面。为了在大型数据库中更有效的查询3D模型，索引数据结构和查询算法也是必不可少的。3D模型库模型标准化及特征提取特征描述符索引数据结构构造索引提取出模型ID相似性匹配查询结果查询特征描述符特征描述符提取模型样本可视化检索界面OfflineOnline图1三维模型检索总体框架[2]一般来说，针对于三维模型的检索，在检索界面有三种方法可供选择：（1）从已获得的模型中选择新的对象进行检索，（2）直接通过特征描述符进行检索，（3）通过提供现有三维模型样本进行检索。最后，查询到的模型，通过可视化过程显示在检索界面。1.2三维模型检索算法基本过程基于形状检索的主要思想是将三维模型的形状信息映射到特征空间，得到一组特征向量，然后通过比较其特征向量值来实现模型检索。三维模型检索算法通常分三步：（1）模型标准化；（2）形状特征提取；（3）相似性度量。如何提取模型的特征是模型检索的核心问题。1.2.1模型标准化由于获取和建模方式的不同，各三维模型的尺寸可能不统一，位置、方向也可能各不相同，但人类的认知系统对于具有不同缩放尺度，处于不同位置和方位的同类模型的识别是相同的，所以，为了保证三维模型44检索效果，提取的特征应具有平移、旋转、镜像和缩放变换不变性，这就需要对模型进行标准化处理。模型的平移、缩放等几何变换比较常见，这里不做过多的说明，本节主要介绍两个比较典型的保证旋转不变性的变换方法：（1）主成分分析(principalcomponentanalysis,PCA)[1]是一种常用的基于变量协方差矩阵对信息进行处理、压缩和抽提的有效方法。目的是将许多相关性很高的变量转化成个数较少、能解释大部分原始数据方差且彼此互相独立的几个新变量，也就是所谓的主成分。（2）球面调和表达[3,4,5]球面调和函数是球坐标下拉普拉斯方程的角度部分的解，球面调和表达即用调和函数来表示球函数。调和函数的每个频率的能量是旋转不变量，即对应每个固定频率的展开系数的模的平方和是旋转不变量，因此,可以根据模型特点构造球函数,并利用球面调和函数对球函数进行分解,用各频率的展开系数来构造模型检索的特征。通常情况下，提取模型的特征前都需要对模型进行标准化，主成分分析法比较普遍，也比较简单，可以通过构造原始数据的协方差矩阵，利用特征分解[8]的方法来确定主成分，如果能够根据模型构造相应的球函数，也可以利用球面调和表达的方法来对模型进行标准化处理。1.2.2形状特征提取特征提取是提取最能反映不同3D模型差别的因素。3D模型匹配方法一般都将模型特征表述为特征描述符，以方便检索。因此，要根