第16卷第7期2004年7月
计算机辅助设计与图形学学报
JOURNAL OF COMPU TER 2AIDED DESIGN &COMPU TER GRAPHICS
Vol 116,No 17J uly ,2004
原稿收到日期:2003206205；修改稿收到日期:20032122011本课题得到国家自然科学基金重点项目(60033010)和国家创新体科学基金
(20021201)资助1崔晨 ，女,1970年生，博士研究生，主要研究方向为计算机视觉、模式识别、科学计算可视化1石教英，男,1937年生，教授,
博士生导师，主要研究方向为分布图形计算、科学计算可视化、虚拟现实、多媒体等1
崔晨 石教英
(浙江大学CAD &CG 国家重点实验室 杭州 310027)
摘要 介绍了三维模型检索的主要研究内容，综述了三维模型检索中的关键技术———特征提取的研究现状，通过对基于统计特征、骨架几何学的特征提取方法的综合比较与分析，对各种特征提取技术进行了评价1关键词 三维模型；检索；特征提取中图法分类号 TP391
Analysis of Feature Extraction in 3D Model R etrieval
Cui Chenyang Shi Jiaoying
(S tate Key L aboratory of CA D &CG ,Zhejiang U niversity ,Hangz hou 310027)
Abstract The main contents of 3D model retrieval are analysed and a survey on the key technology of feature extraction in 3D model retrieval based on statistic characteristics ,skeleton ,and geometry of object images is presented with a comparative evaluation of various approaches 1K ey w ords 3D model ;retrieval ;feature extraction
1 引 言
随着三维扫描技术和计算机图形学的发展以及计算机性能的提高，三维模型已成为继声音、图像和视频之后的第4种多媒体数据类型1对三维模型的使用与研究在娱乐、医学、机械工程、工业应用等领域得到了认同，日益发达的互联网技术为人们对三维模型的共享和处理提供了条件，使创建一个三维模型数据
库变为可能，这些都导致对三维模型应用需求的增长1面对庞大的三维模型数据库，如何迅速查到所需的模型正在成为继图像、视频检索之后的又一个热门课题，它涉及了人工智能、计算机视觉、模式识别等领域1对三维模型的标准化描述和检索已被纳入MPEG 7的发展框架中1目前，虽然已经有针对专用模型(如蛋白质分子结构的分类和查
询问题)的研究，但绝大多数三维模型检索的研究都是针对通用模型进行的1同时三维模型的描述方法多样，如体素表示法、多边形网格表示、点集合表示等，这也使得对三维模型特征提取的研究更加复杂1通常，一个完整的模型检索系统包括如下几个方面:
(1)三维模型的特征提取1由于绝大多数的三维模型是用于可视化，因此表达三维模型的文件中往往只包含模型的几何属性(顶点坐标、法向矢量、拓扑连接等)和外观属性(顶点颜、纹理等)，很少有适合自动匹配的高级语义特征的描述1如何合理地描述三维模型(即特征提取)成为三维模型检索课题首先要解决的问题，它也是三维模型检索的难点1一个理想的特征描述符SD (Shape Descriptor )必须满足：易于表达和计算；不占用太多的存储空间；适合进行相似性匹配；具有几何不变性，即对模型的平移、旋转、缩放等具有不变性；具有拓扑不变性，即当
相同模型有多个拓扑表示时,SD应是稳定的;SD对模型的绝大多数处理，如子分、模型简化、噪声增减、变形等是鲁棒的;SD必须具有惟一性，即不同类型的模型对应的特征表示应该不相同1
(2)相似性度量1检索的目的是出与所给模型相似的模型集合，因而对提取得到的特征如何进行相似性匹配是检索课题中要解决的第二个问题，选择的度量方法必须适合匹配计算1
(3)模型分类1由于三维模型资源庞大，因此需要建立一个分类数据库以便提高模型查效率，该分类数据库必须适合用高级语义描述1当然，对这个问题与相似性度量方法的研究有交叉的地方1
(4)搜索方法的研究1尽管有了分类作基础，但面对仍然庞大的数据库，如何快速、有效地查出相似的模型，在人工智能和数据库领域中仍然是一个值得探讨的问题1
(5)查询接口的设计1作为一个成熟的检索系统，应该拥有良好的交互性能，提供给用户方便的查询手段1通常，查询输入可以通过文本与模型相结合的方法[122]进行1对于查询模型的输入主要有两种途径：文献[1]将已知的模型作为查询输入，通知系统检索出相似的模型，该方法的检索结果比较理想，但是要求用户必须预先拥有某种模型的范例，因此实际使用中不够灵活，有一定的局限性；文献[2]提供给用户一个绘图接口，允许用户绘制所需查询模型的二维视图，由系统根据视图自动生成三维模型1对于普通用户而言，准确地绘制一个拓扑复杂、有洞或有许多分支的模型是比较困难的1实验表明，目前该系统在这方面的性能不是非常理想1显然，查询接口的设计也直接影响了系统的检索性能，因此设计一个理想的查询接口在检索系统中非常重要1
(6)检索性能的判断1对于三维模型的检索性能的判断，主要从查全、查准、时间、资源消费等几个方面
来衡量1目前的研究主要是用查全率和查准率两个参数来对检索性能进行评判1
总之，如何提取模型的特征是三维模型检索首先需要解决的关键技术，也是目前研究比较多的一个方面1
2 特征提取方法描述
从计算机图形学发展的初期开始，多边形网格就是通用的三维模型的表示方法1尽管后来出现了更多的描述方法，但由于多边形具有形状简单、便于计算和处理等特点，使得三维模型检索的研究者们更多的以多边形网格模型作为研究对象1文献[325]在20世纪80年代初就对三维模型形状特征的描述进行了研究，但由于相关应用领域发展的滞后，当时并未引起更多的关注，直至20世纪末，随着硬件条件的成熟和应用需求的发展，关于三维模型特征提取方法的研究开始受到了人们的重视1目前，三维模型特征提取方法主要分为三大类：统计特征提取方法；骨架提取方法；基于几何学的提取方法1
211 统计特征提取方法
对一个三维模型进行参数化本身就是一个很复杂的问题，同时由于三维表面有任意的拓扑，使得一些在二维图像被使用的方法(如傅里叶变换)无法直接应用在三维领域1很多模型虽然满足了视觉效果，但是大多数是退化的、不完整的，最经典的如U2 tah teapot，是一个无底的茶壶；又如Stanford Bunny 是一个
带有几个洞的兔子1对这些模型进行有意义的几何特征和形状信号的计算是很困难的，因此从统计学的观点出发，寻出有意义的统计特征成了研究人员首先考虑的方法1目前的研究中主要使用了如下统计特征：模型顶点间的几何关系(距离、角度、法线方向关系等)，模型顶点的曲率分布特征，模型顶点的各阶统计矩以及各类变换特征系数等1
21111 形状分布方法
形状分布方法主要描述了模型表面随机顶点间的特征关系，相关特征如模型表面顶点的曲率分布、两个随机顶点间距离的概率分布等1不同的统计特征有着不同的特点，但经过预处理之后大多数可以满足几何不变性[6213]，由于形状分布方法用模型表面的特征替代了模型几何体的特征，因此大多数情况下更适合用于对模型进行粗分类1下面对一些有代表性的特征提取进行简单描述1Osada等[6]根据不同几何形体表面顶点间的相互关系呈现出不同的分布特征，试图将一个任意的、可能退化的三维模型中复杂的特征提取转换成相对简单的形状概率分布问题1图1a～1d分别表示直线、圆、三角形、立方体上任意两点间的欧氏距离D2的概率分布曲线1显然，不同的形状呈现出不同的关于D2的曲线特性，以此作为模型的特征描述1文献[6]中还建议了其他特征，如A3(模型表面三个随机顶点间的角度)、D1(模型质心至表面任意顶点间的距离)等1该方法计算简单，对模型的平移、旋转、缩放等具有不变性，对模型边界一些小的扰动具有较好的鲁棒性1
388
7期崔晨 等：三维模型检索中的特征提取技术综述
图1 欧氏距离D 2的概率分布曲线
文献[729]首先对模型进行规则分割(图2所示
为对蛋白质分子进行的网状分割)，将不同模型在相同的分割下可能呈现出关于某种特征的不同的分布特性(图3所示为蛋白质在各个区域中的顶点密度的直方图)作为模型的特征描述符1该方法没有对模型进行预处理，因此提取的特征仅具有平移、缩放不变性，但对模型边界小的扰动有较好的鲁棒性
1
图2
网状模型
图3 形状直方图
文献[10212]将模型的一些几何参数(如面积、
体积以及构造一些特殊的矢量)作为特征向量1文献[12]用一个中心在模型质心的规则多面体(如十二面体)作为参考系，由质心至十二面体的顶点的方向作为特征矢量方向，沿着该矢量方向与模型的三角面片相交，取该方向截交长度最长的那个矢量进行归一化后作为模型的特征矢量；因此，描述一个模型仅需20个特征矢量1尽管该方法比较简单，计算量小，存储量少，但显然对模型特征的描述不够准确，同时对一些小的扰动很敏感，因此实验结果并不理想1
Epaquet 等[13]的思想与上述方法类似，将模型顶点与模型的某些特征轴间的关系作为特征描述，提出了一种cord 2based 的方法1该方法首先用主元分析方法(Principle Component Analysis ,PCA )[14]对
模型进行规范化得到模型的三个主轴,cord 则由模型的质心与模型顶点的连线定义1模型的特征描述由三部分组成:cord 与模型的第一主轴之间的角度的分布直方图;cord 与模型的第二主轴之间的角度的分布直方图;cord 的长度分布直方图1显然，该方法的计算量比文献[7212]大，但对模型描述的信息更丰富1
文献[15217]将顶点的曲率作为特征提取研究的对象1Mahmoudi 等[16]尝试将三维模型的特征提取转换到二维平面上进行，提取二维视图上的边界点的曲率分布特征1为了减少由于模型在坐标系统中的方向、位置、尺寸给模型的特征提取带来的影响，对模型用PCA 进行规范化的预处理1Mahmoudi 等[16]计算了模型的7个二维投影特征视图上顶点的曲率空间分布，其中3个为主要视图，另外4个视图为从属于三个主要视图的次要特征视图1视图投影的方向和数目直接影响了模型特征描述的精确程度，虽然原文中选择7个视图对比较规则的模型特征描述效果不错，但对拓扑复杂的模型效果并不理想1由于模型最终的特征表达是经过两次特征提取得到的，因此特征描述的精确度受到一定的影响；同时，该方法对模型噪声比较敏感1尽管该方法存在诸多需要解决的问题，但仍不失为一个好的思路1
Z aharia 等[17]提出用3D SSD (3D Shape Spectrum Descriptor )方法对三维模型进行描述，该方法避免了文献[16]中的二次特征提取，其主要思想是根据物体表面的一些局部几何属性(如某点的曲率)提供物体
内在的形状索引(Shape Index ,SI )描述1SI 被定义为某点关于两个主要曲率的函数，则3D SSD 被定义为SI 在整个模型网格上的分布，用直方图表示13D SSD 对几何转换和比例缩放具有不变性，对一些易见的、显著的、有突起的特征，如convexity ,concavity ,rut ,ridge ,saddle 描述准确1但该方法对模型的拓扑很敏感，对任意网格描述之前需进行规范化的预处理，预处理的过程较复杂且涉及到很多方面(如拓扑表示的不惟一性、网格的不规则采样，非定向网格，退化网格等均需经过预处理)，因此该方法并不通用1但该方法的实验效果好，并被建议使用在未来的MPEG 7中121112 基于各种数学变换和矩的统计特征提取方法
在二维图像中，常用各种数学变换(如傅里叶变换、Hough 变换)或各阶矩对图像进行描述，因而很多研究人员尝试着将这种思想应用到三维模型的特征描述上1
4
88计算机辅助设计与图形学学报2004年
为了克服文献[12]中特征提取过于粗糙的缺点，文献[18219]对模型首先进行球面参数化；然后沿着经、纬两个方向均匀采样，得到的球面傅里叶系数作为模型的特征描述符1这种方法可以实现多分辨率的特征表达，对模型表面小的扰动具有鲁棒性1在文献[18]中，还采用了矩作为模型的特征1从实验结果可以看出，球面傅里叶系数具有更好的检索性能1尽管这种基于射线的矩(ray2based)[18]比文献[20]中的统计
矩检索性能要强，但是参数化的过程中，存在不同的点映射在同一个球面点上的问题，对模型的表示不惟一1另外，高阶矩对模型表面小的扰动异常敏感1文献[21229]与文献[18]思想类似，采用基于傅里叶变换与矩的思想对模型进行特征描述，在应用时傅里叶变换对边界的变化很敏感，矩则对物体的质量分布较为敏感，这些都影响了检索的效果1
文献[30]在假设三维模型可以用三维等高线描述的前提下，用傅里叶系数作为特征描述符1显然，这种方法无法从理论和实验上证明等高线就是三维模型的理想特征描述符，因此还需进一步研究1 Ohbuchi等[31]在假设模型的质量分布是均匀的前提下，计算了模型相对三个主轴的惯量矩和模型表面顶点对三个主轴的距离分布1由于模型对轴会有一些小的变形，为了减少由此带来的影响，文献[31]采用了一种叠盖分析窗口的方法，增加算法对这种变形的鲁棒性1这种方法计算不复杂，对一些退化的模型也适用，但实验表明其对于具有旋转对称特征的模型效果更好些，而对其他特征的模型实验结果并不理想，因此该方法局限性比较大1为了解决文献[17]中的3DSSD对拓扑敏感的问题，文献[32233]给出了一种新的三维模型的特征描述符———O3DHTD(Optimal3D Hough Transform Descriptor)1O3DHTD是基于Hough变换的思想而定义的，该思想在二维图像中已得到应用1文献[33]针对三角面片描述的三维网格模型，将三角形质心作为原始点集映射到某参数空间，通过Hough 变换确定参数集合，以此作为模型的特征描述3DHTD(Hough Transform Descriptor)13DHTD从本质上满足了拓扑不变性的要求，但并没有很好地解决几何不变性1为此，文献[33]采用了PCA方法对模型进行规范化处理，并对由于PCA方法所引起的新坐标
系统出现的48种可能情况都做了计算，保证了特征O3DHTD的几何不变性，获得最终的优化后的O3DHTD1由于文献[33]采用了一些优化处理，导致特征提取的计算量较大；同时，该方法是对模型全局特征的描述，适合做全局匹配1图4a所示为基于O3DHTD对飞机模型的检索结果，图4b所示为基于3DSSD对飞机模型的检索结果1可以看出, O3DHTD比3DSSD检索性能好
1
212 骨架提取方法
由于用统计方法提取的特征无法对模型进行直观形象的可视化描述，因此骨架提取成为研究人员关注的第二类方法1骨架是对模型的主要特征的一种可视化描述，它符合人类的视觉特征1
在医学的虚拟内窥镜手术中，人们致力于研究如何提取管状器官的中轴线，并以此作为手术的导航1Amenta等[34235]首先计算出模型的Voronoi图，在此基础上计算出模型的骨架，它描述了模型的全局特征，但是Voronoi图的计算开销和存储量非常庞大，更适合实体模型，对于有孔、洞的模型还需特殊处理；同时,Voronoi图的构造对噪声非常敏感，边界上小的噪声常会导致密集的Voronoi图，增加了计算量，影响对模型特征的精确描述1因此，这种方法的实用性有待进一步研究1
与中轴变换[36237]的思想相似，文献[38239]采用基于参数控制的瘦化算法对模型进行骨架提取，适合任何以体素描述的三维模型1该算法首先计算出模型的骨架节点，然后通过各节点构造出相应的骨架图形，即一个有向的非循环图1以此作为模型的特征描述，不仅适合全局匹配，也可进行局部匹配，如图5所示1该算法中骨架节点为模型局部的中心点，通过瘦化参数控制节点的密度，因此参数直接影响了模型骨架的提取质量1瘦化算法对噪声异常敏感，小的扰动会导致错误的骨架提取1同时，由于需要对每个体素的距离转换值进行递归计算和比较，因此这种算法的计算量很大1而关于如何选择瘦化参数文献[38239]中没有给出理论的描述，这也是该算法的一个遗憾1
588
7期崔晨 等：三维模型检索中的特征提取技术综述
文献[40242]采用了建立网格模型多分辨率R G (Reeb Graph )的骨架提取方法1一个定义在模型表面的连续标量函数为三维模型构造了一个二维的R G 描述符,R G 不仅可以描述模型的特征，同时还描述了模型的空间拓扑关系，如图6所示1
不同分辨率节点图之间的节点具有父子关系，直线表示了节点间的拓扑1匹配策略由粗到精，当父节点匹配时，再进行子节点的匹配1这种方法无论对模型的全局匹配和局部匹配都适用，而且通过选择合适的连续函数构造出的R G 具有平移、旋转不变性，对由于模型简化、子分、网格重构等引起的连通改变是鲁棒的，对模型变形引起的变化、噪声带来的影响不敏感1该方法不仅能识别拓扑不同的模型(如一个面包圈和球)，而且对于几何不同而拓扑相似的模型也能识别，如弯曲的手指或伸直的手指1
由于R G 的构造是基于连续标量函数进行的，因此当模型存在两个分离的部分时(如模型中包括两个分离的球)，该方法无法正确识别，并且对边界敏感1不同类型的模型必须采用适合的连续函数才能得到正确的R G ，如文献[42]中所用的geodesic 距离函数并不适合于体素模型,
可能密度函数更适合1
图6 多分辨率R G 的构造
213 基于几何学的特征提取方法
人类的相似判断是基于对物体在整体几何形体buchi
上的一种比较,Novotni 等[43244]据此对三维模型直接进行几何相似判断1其基本思想是将一物体A (如图7a 中的香蕉)与另一物体B (如图7a 中的苹果)重叠放置，计算出物体B 位于物体A 之外的点到物体A 的边界的距离分布特征，构造出包含这些距离的直方图，最后基于这些直方图计算一个量化的相似度量1该方法适用于严格定义的封闭的多边形网格模型，对刚度较大或变形较小的物体效果较好1进行相似判断之前，对模型需进行精确的重新定位和对准的预处理，然后对模型进行边界提取1如图7所示，图7a 中的香蕉和苹果质心重合，图7b 中香蕉和香蕉虽然质心重合，但应如图7c 所示，两者的方向也需一致1该方法适合进行模型的全局匹配，如文献[44]中对客户的脚进行三维扫描后进行模型重构，然后将重构后的模型与鞋楦模型进行相似比较，为客户制造更为符合个人的鞋子1由于绝大多数的模型是不严格的，如Internet 上的模型通
常是退化的、
松散的多边形集合，所以该方法的应用受到很大的限制1
图7 两个模型的预处理
3 各类方法比较与分析
无论是基于统计特征的方法还是骨架提取，或
基于几何学的方法，都无法从理论上验证它们对模型特征描述的精确度，更多的是从实验的结果来判断其优劣1图8所示为对同一飞机模型用同一种度量方法在不同的统计特征描述下得到的查准率2查全率图1三种特征描述符分别为:ray 2based 的用球面调和函数提取的特征矢量(rays 2sh )[18],ray 2based
6
88计算机辅助设计与图形学学报2004年
发布评论