（计算机应用技术专业论文）基于形状的三维模型检索.pdf

基于形状的三维模型检索 张元祯( 计算机应用技术) 指导教师：李宗民( 教授) 中文摘要 本文的工作主要是研究一种有效可行的基于形状的三维模型检索算 法，检索的有效性是指其在检索的速度和质量等方面能够达到令人满意的 效果。 文中提出了一种基于法向投影矩的三维模型检索的新算法，详细地给 出了算法的完整实现方案，并通过实验对算法进行了验证。首先，从三维 模型库中获得三维模型的原始结构数据，对其进行预处理( 几何变换、网 格化处理) 后获得模型的有效网格点数据，然后通过计算法向投影不变矩， 获得所有模型的特征值数据，最后通过模型之间的相似性匹配来检索三维 模型。从算法和试验结果来看，法向投影矩具有很好的几何变换不变性， 计算简单快捷，选取三维模型的检索结果要优于三维z e r n i k e 矩。 另外，本文还对极半径矩在三维模型检索中的应用进行了研究，给出 了计算公式和与三维z e r n i k e 矩的比较试验结果，其检索算法的步骤与法 向投影矩的算法步骤基本相同。 关键词：形状，三维模型，相似性匹配，法向投影矩，极半径矩 s h a p e b a s e d3 dm o d e lr e t r i e v a l z h a n g y u a n - z h e n ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rl iz o n g - m i n a b s t r a c t t h i sp a p e ri st os t u d ya l le f f e c t i v ea n da p p l i c a b l ea l g o r i t h mo f s h a p e - b 船e d 3 dm o d e ir e t r i e v a lt og e tas a t i s f i e dr e s u l ti ns p e e da n dq u a l i t yo f r e t r i e v i n g i nt h i s p a p e r , an e wa l g o r i t h mo f3 dm o d e lr e t r i e v a lb a s e do nt h e n o r m a l - p r o j e c t i o n m o m e mi sp r e s e n t e da n dad e t a i l e dp r o j e c ti sp r o p o s e dt o t e s t i f yt h ea l g o r i t h i n f i r s tt h eo r i g i n a ld a t ai so b t a i n e df r o mt h el i b r a r yo f m o d e l sa n dp r e p r o c e s s e d ( g e o m e t r yt r a n s f o r m a t i o na n d 鲥dp r o c e s s i n g ) t og e t d a t ao fg r i dp o i n t s t h e nt h en o r m a l p r o j e c t i o n - m o m e n ti sc a l c u l a t e dt og e tt h e c h a r a c t e r i s t i cv a l u eo fa l lt h em o d e l s f i n a l l ym o d e l s i r es i m i l a r l ym a t c h e d t or e a l i z er e t r i e v a l f r o me x p e r i m e n t a lr e s u l t s ，i ti ss i m p l ea n dq u i c kt oc o m p u t e f o rt h e n o r m a l - p r o j e c t i o n - i n v a r i a n tm o m e n tw h i c hh a sg o o d m v a r i a n t p e r f o r m a n c ea f t e rg e o m e t r yt r a n s f o r m a t i o na n db e t t e rr e s u l to fs o m ec l a s s e so f 3 dm o d e l st h a n3 dz e m i k em o m e n t i na d d i t i o n , t h e p o l a r - r a d i u s - m o m e n ta r e d e s c r i b e di nt e r m so ft h e a p p l i c a t i o n f o r3 dm o d e lr e t r i e v a l t h e c a l c u l a t i n g f o r m u l a so fi ta n d e x p e r i m e n t a lr e s u l t sc o m p a r i n gw i t l lt h e3 dz e m i k em o m e n ta r eg i v e n b a s i c a l l yt h ea l g o r i t h mo ft h ep o l a r - r a d i u s - m o m e n ti s s a m ea st h en o r m a l - p r o j e c t i o n - m o m e n t k e yw o r d s ：s h a p e ，3 dm o d e l ，s i m i l a r i t ym a t c h i n g ，t h en o r m a l - p r o j e c t i o n - m o m e n t ，t h ep o l a r - r a d i u s m o m e n t 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得中国石油大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：年 月日 关于论文使用授权的说明 本人完全了解中国石油大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 ( 保密论文在解密后应遵守此规定) 学生签名： 导师签名： 年 缸 月 月 日 日 中国行油人学( 华东) 硕十论文第1 章前言 第1 章前言 1 1 课题的来源、提出背景及意义 该课题来源于国家自然科学基金：“三维形状内在特征描述方法”( 编 号：6 0 5 7 3 1 5 4 ) 。 计算机信息检索技术作为信息采集的重要方法和手段已有几十年的发 展历程。随着i n t e r n e t 的发展，信息处理从传统模式向新型模式转变。信 息检索的对象已经从单一的文本信息发展为二维图像等多媒体信息以及更 为真实丰富的三维模型和三维场景等虚拟媒体信息。2 0 世纪9 0 年代初， 为适应图像、视频等二维多媒体信息检索的需要，基于内容的多媒体检索 ( c o n t e n t - - b a s e dm u l t i m e d i ar e t r i e v a l ) 技术应运而生，并很快在理论 研究和实际应用中得到迅速发展“。 随着三维数据获取技术，三维图形建模方法以及图形硬件技术的发展， 已经产生了越来越多的三维模型库，如虚拟现实环境( v i r t u a lr e a l i t y ) 、 三维游戏( 3 dg a m e ) 、工业实体c a d 模型库等等，在互联网上也涌现出了越 来越多的三维模型库嘲。另一方面，高逼真度的三维模型费时费力，造价昂 贵，如果能对模型进行重复利用，将会大大节省开支，由此引发的一个重要 课题是对三维模型需要一个有效的基于内容的三维模型检索( c o n t e n t - - b a s e d3 dm o d e lr e t r i e v a l ) 方法。 三维模型具有任意的坐标方向和坐标单元大小，同时具有几何特性 ( g e o m e t r i c a lp r o p e r ti e s ) 和表面属性( a p p e a r a n c ea t t r i b u t e s ) 两方 面的数据。其中，表面属性主要包括：材质种类及其颜色、透明度、反射 系数以及纹理贴图等；而几何特性则存在多种表示方式，如参数化曲面或 中国石油大学( 华东) 硕+ 论文第1 章前言 多边形网格包围的实体表示、体元集合，隐形函数以及类似于v r m l 模型的 多边形混合模型等 4 。由于表面属性的多样性和复杂性，目前的三维模型 检索算法往往针对特定的三维模型数据表示方法，只根据其形状特征进行 相似性检索。 通过查阅文献和研究发现，现有的基于形状的三维模型检索技术存在 的局限性主要在于：三维表面拓扑关系任意，不能进行简单的参数化描述 5 ，模型的退化现象 6 ，需要进行模型坐标的标准化，模型预处理时阃 长，采用复杂的函数变换来保证提取特征的几何变换不变性等等，大大降 低了三维模型检索的效率，模型检索的时间和质量难以达到同步，影响了 三维模型检索技术的广泛应用。 为此，有必要研究一种可行的基于形状的三维模型检索新方法，以期 解决上述局限性，使其在检索速度和质量方面获得令人满意的效果。 1 2 国内外研究现状 基于形状的三维模型检索的核心是提取一组形状特征来表示三维模 型，然后通过比较其特征值来实现模型检索，其实现技术主要包括模型坐 标的标准化( n o r m a l i z a t i o n ) 与预处理( p r e p r o c e s s i n g ) 、形状特征提取 与索引、相似性匹配以及检索界面四个部分脚，其中，形状特征提取是关 键技术，它在很大程度上决定了三维模型检索的效率和优劣。 1 2 1 模型坐标标准化和预处理 实现基于形状的三维模型检索，很关键的一点就是要求所提取的三维 模型特征描述具有针对平移、旋转、尺度大小以及方位变换的不变性和鲁 棒性，对噪声、重采样和简化具有鲁捧性，在有噪声的情况下，在重采样 和简化变换前后，3 d 模型的特征均要保持相似。 2 中国石油大学( 华东) 硕十论文第l 章前言 目前，实现特征描述不变性的方法主要有三种”3 ：( 1 ) 使用主成分分 析( p r i n c i p a lc o m p o n e n ta n a l y s i s ，p c a ) 等方法对三维模型坐标进行标 准化，计算其标准化的坐标框架，然后，在此标准化坐标系内提取相应的 特征；( 2 ) 将所有待比较的三维模型两两之间进行坐标对齐，这种方法由 于极为费时而很少被采用；( 3 ) 定义并提取本身具有不变特性的特征描述。 但实际上，这些特征描述所具有的不变性往往是不全面的，例如，s u z u k i 等人提出的形状特征只对绕坐标轴9 0 。范围内的旋转变换保持不变性“， k a z h d a n 等人提出的反射对称特征描述只具有平移和尺度不变性嘲，而且， 大多数这类特征的计算有时也需要在一个归一化的坐标系内完成。因此， 为了进一步提高检索的准确性，往往也需要进行模型坐标标准化。 模型坐标的标准化又称姿态估计( p o s ee s t i m a t i o n ) 。在三维空间中， 三维模型可以具有任意大小，其位置、方位和角度各有不同。因此，为了 保证特征提取对于平移、旋转和尺度大小的不变性，在进行特征提取和相 似性匹配之前，必须先将所有待比较的三维模型变换至一个标准坐标系的 范围内。这样，即使同一三维模型具有不同尺度、不同位置、方向、旋转 角度和不同角度的细节层次( l e v e l 一0 f d e t a i l ，l o d ) 时，其表示方式 仍具有唯一性。模型坐标标准化的目的在于使得三维模型检索独立于其所 采用的具体数据表示方式。 为保证平移不变性，需要将模型的质心平移至坐标原点的位置。为保 证旋转不变性，有多种变换方法，最常用的是采用p c a 变换方法“”，在一 个标准坐标平面中对齐模型。为保证方位不变性，还需要进行翻转变换， 以保证互为镜面映象的三维模型在表示方式上的同一性“。最后，为保证 尺度大小的不变性，还要将旋转后的三维模型归一化至标准单元大小。因 此，一个完整的坐标模型标准化过程可以表示为如下的几何变换f ： f ( d = s 。f r ( j c ) “1 ，其中，s 是缩放系数，f 是一个对角阵形式的 中国石油大学( 华东) 硕十论文第l 章前言 翻转矩阵，r 为对应于p c a 变换的旋转矩阵，i 为原始模型坐标，c 为坐标 原点。 需要指出的是，使用p c a 变换进行模型坐标标准化，是以三维模型坐 标的顶点作为分析对象，没有考虑组成三维模型的三角形网格之间的大小 差异，因此，有可能对相同的三维模型产生不同的标准化坐标系，从而影 响检索的准确性m 。为了克服这一缺点，p a q u e t 等人“”计算出每个三角形 网格的质心，用其代替相应的顶点，然后再对该集合进行p c a 变换；而 h e c z k o 等人“”则通过为三角模型的各个顶点设定权值，生成一个加权的顶 点集合的方法来解决这个问题。 除了p c a 变换方法外，还有一种基于模型实体的不变矩特征的坐标标 准化方法。g o t t s c h a l k 等人“3 1 假定三维模型的单元点质量位于其各个顶点 之上，从而计算出其惯性主轴。该方法的缺陷在于其最终计算出的主轴方 向依赖于模型网格的细化程度。作为对该方法的一种改进，o h b u c h i 等人伽 则假定每个多边形表面具有均匀的密度分布，然后使用m o n t e c a r l o 方法对 每个多边形面上的点集进行模拟，点集的大小与多边形表面的面积成正比。 通过对模拟出的点集进行计算，求出其质心和惯性主轴，然后对三维网格 模型坐标的位置和方向进行归一化。基于不变矩特征的坐标标准化方法假 设三维模型中一定存在包含一个或多个实体的闭合表面，但是，在实际应 用中并不能保证这一前提。因此，该方法的适用范围较窄，往往在三维模 型库规模较小时使用m 。 针对不同三维模型表示，目前存在多种形状特征提取方法。例如：有 的方法针对多边形网格实体表示提取特征，有的方法针对曲面实体表示( 如 c a d 模型) 提取特征，有的方法直接针对几何c a d 模型提取特征，而有些 方法针对体元集合表示提取特征。这些模型表示方法的定义是完备的。但 是，常用的表示三维对象的v r m l 模型却是不完备的，其使用多边形网格、 4 中国石油大学( 华东) 硕士论文第l 章前言 独立多边形、线段和点组成的集合突出三维视觉效果，并未定义任何三维 对象“1 。因此，在对其进行特征提取之前，还需要进行一些预处理的操作， 例如各种模型数据结构之间的转换、模型单元的划分、聚类或者模型的函 数投影等“旧。具体采用的预处理步骤根据不同的形状特征提取方法而各 有不同。 1 2 2 形状特征提取 三维模型检索所提取的特征，除了传统的文本关键字特征之外，主要 包括通过变换提取的二维形状特征以及对模型进行几何运算提取的三维形 状特征。目前，还没有一种通用的形状特征描述方法。不同种类的形状特 征可能适用于不同的三维模型表示方法。除此之外，在检索中也涉及到颜 色、纹理等其它表面属性特征。 物体的形状特征具有多面性，因而导致其具有多种不同的表示方式。 迄今为止，还没有任何一种表示方式可以完全符合人类对形状的识别和理 解能力“1 。基于形状的特征描述已经在计算机视觉、计算几何、c a d 以及分 子生物等领域得到了广泛研究，但目前大部分工作都还集中在二维数据的 检索“司。如何得到既能快速简单的进行提取和比较，又能十分有效的分辨 相似和不相似三维模型的特征描述，是三维模型检索研究中的关键和难点。 现有的大多数研究工作主要针对三维模型的几何形状特征h ”“1 ，形状 特征描述应该具有如下特点：( 1 ) 对三维信息的描述和分辨能力强；( 2 ) 计算速度快；( 3 ) 易存储，特征维数足够低：( 4 ) 易索引，能方便的组织 索引结构，以加快检索过程；( 5 ) 具有几何变换无关性，并对形变和噪声 具有一定程度的鲁棒性；( 6 ) 独立于具体的三维模型表示方法、模型的细 化方式、模型的种类和拓扑关系等”“8 “。 表达三维模型的数据结构一般都较为复杂，包括每个表面、边、顶点 中国石油丈学( 华东) 硕七论文第1 章前言 以及它们之间的连接和拓扑关系。其对三维物体的描述分为两类：( 1 ) 拓 扑关系，记录表面、边、顶点之间的连接关系；( 2 ) 几何关系，描述表面、 边、顶点的具体形状和空间位置。形状特征一般着重于描述三维模型的几 何形状和表面拓扑关系，通常基于三维表面、三维体元及其顶点集合以及 结构化建模来描述三维模型的形状特征。 三维模型的形状特征主要包括基于几何结构分析的形状特征、基于拓 扑关系的形状特征、基于函数投影的形状特征、基于统计特性的形状特征。 ( 1 ) 基于几何结构分析的形状特征提取 v r a n i c 等人哪提出一种基于射线( r a y - - b a s e d ) 的形状特征描述方法。 以坐标原点为起点，沿一组等间距的空间方向矢量作射线，计算与其相交 的三角形面片与坐标原点的最大距离作为特征值。h e c z k o 等人“2 1 提出一种 基于体结构的形状特征提取方法。将每个单元网格所包围的网格面片面积 作为特征元素。s u z u k i 嘲则提出一种基于三维模型顶点等价类的特征提取 方法。首先，计算每个网格单元中的顶点( 或表面法向量) 数目，将网格 单元划分为一系列等价类。最后，以每个等价类中归一化的顶点个数为特 征向量。t a n g e l d e r 等人啪描述了一种使用加权点集合( w e i g h t e dp o i n t s e t s ) 表示多面体模型的方法，用每个网格单元中的代表点组成加权点集 合作为形状特征。b i n f o r d 乜1 1 使用一种称为广义柱( g e n e r a l i z e d c y l i n d e r s ) 的参数模型实现三维模型的特征提取，该模型由一组基于样条 曲线的空间轴及定义在该轴上的截面连接函数组成。c i c i r e l l o 等人噙1 和 m c w h e r t e r 等人1 通过提取三维图形中的几何学和工程学上的特征来进行 相似性估计。z h a n g 等人嘲蚓和v r a n i c 等人则使用球形谐函数分解 ( s p h e r i c a lh a r m o n i c sd e c o m p o s i t i o n ) ，提取对三维模型的多分辨率特 征，实现基于表面匹配的三维模型检索。此外，v r a n i c 等人基于三维离散 傅立叶变换的方法提取三维模型的特征1 。其实验结果表明，在频率域的 6 中国行油大学( 华东) 硕十论文第l 章前言 特征表示比空自j 域上的特征表示更加有效，具有较好的检索性能。 ( 2 ) 基于拓扑关系的形状特征提取 h i l a g a 等人瑚1 提出一种基于网格点的测地距离( g e o d e s i cd i s t a n c e ) 嘲，使用多分辨率r e e b 图( m u l t i r e s o l u t i o nr e e bg r a p h ，m r g ) 结构表 示三维模型的方法。r e e b 图啪3 是一种使用连续函数变换而产生的三维物体 骨架信息的描述方式。基于骨架信息能很好地进行细节层次地控制，可以 实现多层次的三维模型表示。以基于两点间测地距离的计算函数作为生成 r e e b 图的连续函数，从而构造一种r e e b 图的多分辨率扩展结构m r g ，作为 三维模型检索的特征表示。该方法能有效描述三维模型的拓扑结构，对于 模型的形变具有鲁棒性；并能实现逐步精化的检索。b a r d i n e t 等人。”则基 于二维中轴变换( m e d i a la x e s ) 的概念进行扩展，提出一种基于骨架和中 间轴的三维物体表示方法，然后基于图的节点和边结构，描述三维模型的 形状及其拓扑特征。 基于几何结构分析的形状特征由于能较好地描述模型的高层结构信息 而受到广泛关注。除了上述的特征提取方法外，还有大量类似的研究成果。 如分支点骨架( s h o c ks c a f f o l d ) 阳、超曲面( s u p e r q u a d r i c s ) 脚1 、变形 区域( d e f o r m a b l er e g i o n s ) 嘲以及三维骨架提取( 3 ds k e t c h ) m 嘲等。 但是，这类方法对大型的三维模型库进行相似性计算的时间很长，需要的 存储空间很大，提取的特征不易在大型数据库进行索引哪! ，为了有效解决 计算复杂的缺点，z h a n g 等人0 7 认为，造成几何形状特征提取效率低下的 一个原因在于这些形状特征无法直接从网络数据中有效地提取和获得，往 往需要先将三维物体从多边形网格模型变换为体元网格( v o x e lg r i d ) 模 型，变换速度很慢，而且需要大量的存储空间m “删。因此，z h a n g 等人提 出一种直接针对多边形网格模型计算三维形状特征的方法，通过计算模型 中的三角形及四边形面片等基本形状的体积、矩以及傅立叶变换系数等特 7 中国石油大学( 华东) 硕士论文第1 章前言 征，将其累加后得到特征向量。其实验表明，算法的效率得到了一定程度 的改善。 当三维模型可以被分割为一组规范化的特征集合，并且特征之间的对 应关系明确时，基于几何结构分析的形状特征方法具有很好的效果。然而， 对于广义的三维多边形模型而言，实现上述条件是非常困难的。而且，这 类特征提取方法对于模型表示中的轻微干扰和噪声十分敏感，从而使得特 征之间的匹配和相似性计算也变得困难并且不稳定。另外，提取特征之前， 必须进行一系列复杂的模型坐标标准化处理，这可能带来不稳定性“”。由 于这类方法要求解决模型的重建，参数化、坐标标准化以及特征对应等难 点问题，因此，其处理三维多边形模型时的效果还不够理想。 ( 3 ) 、基于函数投影的形状特征提取 基于函数投影的形状特征提取工作在三位设计与c a d 领域开展较早， 并已进行了较多的研究。如l i t t l e 等人3 使用扩展高斯投影( e x t e n d e d g a u s s i a ni m a g e s ) 方法匹配三位表面。该方法只对具有完整定义的数据结 构的凸面体有效。d e l i n g e t t e 等人则提出球形属性投影( s p h e r i c a l a t t r i b u t ei m a g e s ) 的方法，首先将三维模型表示为一系列由椭圆形状拟 合而成的离散网格，然后将其投影至一个标准的球形网格，使用每个表面 的曲率组成三维模型的形状特征向量。z h a n g 等人嘲1 基于谐映射( h a r m o n i c m a p ，又称调和映射) 的概念，提出一种谐形状投影( h a r m o n i cs h a p ei m a g e s ) 的特征提取方法。其基本思想在于采用基于能量最小原则的谐映射方法， 将三维表面映射为一系列二维投影。j o h n s o n 等人邮则将三维表面匹配的 问题转换为三维表面上点的匹配问题来考虑，提出一种旋转投影( s p i n i m a g e s ) 的特征提取方法，将三维点的匹配问题转化为二维投影图像矩阵 的模板匹配及模式识别问题。为减少存储空自j 的要求，j o h n s o n 等人使用 p e a 方法对二维投影图像矩阵进行压缩，在进行特征匹配时直接使用压缩 8 中国石油大学( 华东) 硕+ 论文第1 章前言 过的二维投影图像矩阵，改善其性能。上述方法都基于表面匹配来实现三 维模型的识别和检索，其假设模型具有正确的表面网格表示或明显的体积， 且依赖于模型坐标系统的预先校正，计算较为复杂。 除了上述方法外，还可以将三维模型在特定平面上进行投影，得出其 在不同角度的二维外形轮廓，据此提取相应的特征表示。m i n 等人0 1 将三维 模型从多个不同视点投影成m 个二维投影，与用户绘制的n 张二维草图进 行基于e u c l i d e a n 距离的相似性匹配( m n ) ，然后，用这些距离值与一 组同心圆的交集确定一组函数。基于这组函数，求取其傅立叶变换系数的 幅值作为三维形状特征。c y r 等人提出一种基于外表投影视图( a s p e c t g r a p h ) 的特征，每隔5 。计算出三维模型在不同角度上的二维投影视图。 按照这些视图之间的距离对其进行聚类，划分为若干个外表投影( a s p e c t ) ， 从每个外表投影选取出一个具有代表性的视图作为特征。其实验结果表明， 该方法可以较为准确的识别具有任意角度的三维模型。但该方法对特征的 索引和相似性匹配则较难实现。f u n k h o u s e r 等人“”利用球形谐函数 ( s p h e r i c a lh a r m o n i cf u n c t i o n ) 的不变特性，将三维空间分解为一系列 具有不同半径的同心圆，然后分别为这些同心圆空间定义具有旋转不变性 的频率函数，其集合构成三维模型的特征向量。这种方法的好处在于不需 进行模型坐标标准化。s a p u e 等人m 3 则同样以球形谐函数为基础，按照等 间距的不同角度方向对三维模型进行投影采样，然后对采样值进行傅立叶 变换，选取其前k ( k o ) 个系数作为最终的特征向量。s a p u e 等人还指 出，除了球形谐函数外，投影变换函数还可以采用其他形式，如s h a d i n g 函数及其复数形式等。h e c z k o 等人“2 1 将三维模型分别在x y ，y z 和z x 三个 平面上进行投影，获得不同的二维轮廓信息，然后，计算一组距离值和f v r 能量谱系数作为形状特征向量。该方法计算简单，但其将三维模型仅仅视 为不同二维投影的组合，不能很好地反映出三维模型中的空自j 结构信息， 9 中国石油大学( 华东) 硕+ 论文第1 章前言 准确率较低。为了克服这一问题，h e c z k o 等人对其加以改进，提出一种带 有深度信息的二维投影的扩展方法。在进行二维投影的过程中，将三维模 型的深度信息通过投影区域的象素灰度值加以体现，同时，对于二维投影 图像，计算其二维f f t 的频域特征，使用基于区域的形状特征表示而非基 于轮廓的形状特征表示，提高了准确性。k a z h d a n 等人m 计算所有通过三维 模型质心的平面与其映像之间的对称距离，并为这些对称距离定义二维的 球形函数，从而提出一种基于反射对称的形状描述符。实验结果表明，该 特征具有很好的稳定性。 函数投影方法的共同特点是首先将原始的三维模型表示投影至一个标 准的函数模型中，然后计算相应的特征向量，主要基于三维模型的表面或 其二维投影区域进行特征提取。这类方法的优点在于其将三维模型投影为 一系列不同视角的二维图像，大大降低了匹配的复杂度；提取的特征较为 简单，容易计算并生成索引。但由于在进行函数投影的过程中需要进行不 同的条件约束，因此容易丢失一些表示三维结构的重要信息。另外，如何 决定所需二维投影的数量，也是一个值得研究的问题1 。 ( 4 ) 、基于统计特性的形状特征提取 模型坐标标准化方法一般是不稳定的【4 为了克服这一缺点，研究者 开始尝试进行不需进行模型坐标标准化的特征提取方法。最简单的方法就 是提取由圆度( c i r c u l a r i t y ) 、离心率( e c c e n t r i c i t y ) 以及代数矩 ( a l g e b r a i cm o m e n t s ) 等全局形状属性组成的形状特征向量1 ，e l a d 等 人伽假设三维模型是由其表面包围的空心模型、基于其表面信息计算三维 几何矩特征作为描述其形状的特征向量。三维矩特征的定义如式( 1 1 ) 所 示； 脚彤2j d 工9 y * z d x d y d z ( 1 1 ) a d 为三维模型d 的表面，p ，q ，r 分别为各个坐标轴上的阶数。由于几 t 0 中国，f i 油夫学( 华东) 硕十论文第l 章前言 何矩特征与三维模型具有一一对应的关系，因此可以对三维模型进行完整 的描述，而且，其子集也可以描述三维模型的局部特征。 o h b u c h i 等人“3 则提出一种基于主轴惯性矩的特征表示方法，o h b u c h i 等人在提取惯性矩特征之前，对模型坐标的方向和尺寸进行变换，以求出 模型的主轴，再将模型沿主轴方向量化为一系列的分析窗口( a n a l y s i s w i n d o w ) ，对每个分析窗口计算其惯性矩特征。 基于矩的表示方法除了几何矩特征之外，还有l e g e n d r e 矩、f o u r i e r - - m e l l i n 矩、z e r n i k e 矩以及p s e u d o - - z e r n i k e 矩等多种形式。其中，二 维z e r n i k e 矩具有比其它矩表示法更好的抗噪性、抗冗余性和识别能力m 1 。 c a n t e r a k i s “”在理论上将其从二维推广至三维z e r n i k e 多项式。三维 z e r n i k e 多项式是三维模型函数在一组正交函数上的投影，表达形式简单， 却具有良好的检索性能。n o v o t n i 等人“7 1 提出一种基于三维z e r n i k e 不变 矩函数的特征提取方法，该方法以球形谐函数为基础，将三维模型划分为 具有一定精度的体元网格并对其尺寸进行归一化，计算其几何矩，在此基 础上再求出三维z e r n i k e 矩。其实验表明，三维z e r n i k e 矩对三维模型的 拓扑结构变形和几何性质变形具有定的鲁棒性。 另一种基于统计特性的特征提取方法是计算反映三维模型的形状统计 特性的直方图特征。直方图能很好的表达以体元为基础的三维数据的分布 特点。直方图特征对平移、旋转及尺寸放缩等变换具有不变性。p a q u e t 等 人油1 于1 9 9 7 年提出的三维模型相似性检索方法中，采用了包括颜色直方 图、法线向量直方图以及材质直方图等在内的三维形状直方图特征。 a n k e r s t 等人8 ”围绕三维模型的质心，将其空间划分为一系列的轮廓和扇 区，以此为基础计算出三维形状直方图。b e s l ”则考虑由三维模型的三角 形网格的所有边界组成的折角直方图特征。b e s l 的方法只适用于多面体模 型，对模型的裂缝和顶点的微小扰动极为敏感，并且还受到网格细化方式 中国石油大学( 华东) 硕十论文 第l 章前言 的影响。而且，这种折角直方图特征并不十分符合人类对于刚体形状的感 观认知。o s a d a 等人嘲提出一种形状分布( s h a p ed i s t r i b u t i o n ) 特征描述 方法，基于三维模型的特定形状函数值的统计分布情况提取其特征。o s a d a 等人将形状匹配问题简化为概率分布问题，这样可以避免模型坐标标准化 和模型配准的预处理步骤。计算三维模型表面上随机点之间的角度、距离、 面积以及体积等形状函数，对其函数值进行随机采样，构造形状分布模型。 该特征满足旋转、平移、尺度变化以及镜像、细化方式的不变性，且对噪 音、裂缝以及多边形的重叠、交错等错误具有一定的鲁棒性。 基于统计特性的三维特征描述方法不需进行模型坐标的标准化，因此。 因此，其计算较为简单，具有良好的不变特性。但是，这些特征描述模型 之间相似性的能力普遍不够强，对三维模型的内容描述不够充分。 1 2 3 相似性匹配 通过特征提取，相似的三维模型可以表示为在特征向量空间中相近的 组特征向量。相似的三维模型在对应的特征向量空间中具有相近的距离， 而不相似的三维模型之间的距离足够大。相似性匹配算法的任务就是在多 维特征空间中，计算用户的三维模型查询请求与三维模型库中的所有模型 之间的空间距离，或通过构建特定的分类器，得出模型之间在内容上的相 似程度，并按相似程度大小返回检索结果，从而实现基于内容的检索。目 前，在基于内容的三维模型检索研究中，主要有以下三类相似性匹配方法。 一、距离度量法 在基于内容的二维图像检索领域，已经提出了多种相似性距离度量算 法”。其中，常用于三维模型检索领域的主要有e u c l i d e a n 距离“4 “”“”、 m a n h a t t a n 距离“矧以及h a u s d o r f f 距离“等。设三维模型的特征空间为 f = r ”，任意两个三维模型的特征向量表示为x = ( ，x ：，x n ) ， 1 2 中国年i 油大学( 华东) 硕士论文第l 章前言 y = ( m ，j ，：，儿) ，则上述三种距离度量的计算公式分别为： 1 )e u c l i d e a n 距离 一 d ( 置耻1 善瓴叫1 ) 2 “卫 为了允许在检索过程中根据用户相关反馈的情况对距离计算过程进行 适当的调整，可以为每个特征赋予不同的权值，得到式( i 3 ) 中的加权 e u c li d e a n 距离公式： 一 d ( x ，y ) = 1 7 q ( 一一只) 2 ( 1 3 ) li - i 其中以为不同特征的权值。 2 )m a n h a t t a n 距离 d ( x ，聊= k y ，i ( 1 4 ) 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 m i n d ( x ，y j ) ( 1 5 ) l 旬s n i s j s n 其中d ( x ，y ，) 表示两个特征点集中任意两点之间的距离度量，如 e u c l i d e a n 距离等。 o h b u c h i 等人“1 在使用e u c l i d e a n 距离的同时，为了克服其在距离度量 时易变形失真的缺点，针对v r m l 模型中的三维多边形网格模型，计算出惯 性矩、面片与轴的平均距离以及面片与轴的距离的方差作为三维特征向量， 采用基于动态规划( d y n a m i cp r o g r a m m i n g ) 的弹性匹配距离( e l a s t i c - - m a t c h i n gd i s t a n c e ) 度量算法进行相似性匹配，也取得了较好效果，其提 中国石油大学( 华东) 硕十论文第l 章前言 出的弹性匹配距离计算公式如式( l6 ) ( 1 8 ) 所示： d ( x ，t 3 = g ( x 。，y 。) ( 1 6 ) ig ( ，j ，i ) + a g ( x ，y 。)l g ( ，儿) = m i n i g ( - l ，以一i ) + 2 g ( 矗，只) i ( 1 7 ) l g ( x - 1 ，) + g ( 矗，儿) j g ( 孙乃) = k 一乃1 2 ( 1 8 ) o s a d a 等人鲫还针对形状分布特征的概率密度函数计算m i n k o w s k i 距离 来实现相似性匹配算法。假设任意两个三维模型的形状分布概率密度函数 为厂和g ，则m i n k o w s k i 距离为： d ( g ) = ( j 1 ，一g 附“ ( 1 9 ) o s a d a 等人分别计算= 1 ，2 ，c o 时的三种m i n k o w s k i 距离进行相似 性匹配，其中，前两种m i n k o w s k i 距离分别简化为m a n h a t t a n 距离和 e c u l i d e a n 距离。 此外，t a n g e l d e r 等人嘲使用一种基于e a r t h e r m o v e r s 距离的改进 算法实现三维形状特征之间的相似性匹配，其物理意义在于计算将一个三 维模型a 变换到另一个三维模型b 所需要的最小工作量。g a i n 等人脚1 还把 基于h a a r 小波变换的二维图像的距离度量方法引入三维检索，提出一种基 于三维模型体元结构表示的相似性距离度量函数。由于三维模型要比二维 模型复杂得多，因此，g a i n 等人提出的二维距离度量方法存在一定问题。 此外，后两种方法由于丢弃了模型表面的信息，要求表面网格具有有效的 拓扑结构，这就需要预先对模型坐标进行校准和标准化，因此较难实现自 动化和相似性度量的鲁棒性。 二、分类学习法 基于分类学习的相似性匹配方法主要是通过预先选取一定规模的三维 1 4 中国石油大学( 华东) 硕+ 论文第l 章前言 模型特征作为训练样本集，然后使用神经网络、支持向量机( s ) 等机器 学习方法对其训练，实现对三维特征空自j 的理想划分，从而得到求解问题 的分类器，实现相似性匹配。目i i ，在三维模型的相似性匹配问题中，分 类学习法正引起越来越多研究者的兴趣，例如，i b a t o 等人m 1 使用s v m 学 习算法实现相似性匹配。s v m 生成并使用一个非线性超平面，使得给定的 训练集中不同类别数据之间的距离最大嘲i b a t o 等人将提取到的特征向量 直接输入s v m 分类器，将其分类结果作为模型匹配的的相似度，从而实现 基于内容的检索。p e d r o 等人嘲使用自组织映射神经网络( s e l f - - 0 r g a n i z e d m a p ，s o m ) 对提取出的三维模型的旋转投影( s p i ni m a g e ) 特征进行相似 性匹配。 另外，分类学习法还可用于实现三维检索中的用户相关反馈机制，通 过响应用户的交互性操作，逐步精化检索结果，实现基于用户兴趣度的个 性化检索。例如，e l a d 等人“”1 在相关反馈操作中，使用s v m 算法对加权 e u c l i d e a n 距离度量函数的权值进行自适应调整。e l a d 等人使用的距离度 量函数式如下： d ( x ，j ，) - 【x 一明1w x l ，】4 - b ( 1 i 0 ) 其中，z ，】，表示待比较的三维特征向量，表示权值矩阵，为一对角 矩阵，6 为预设常数。 假设用户待检索的三维模型实例的特征向量为d ，当前检索结果中“相 关”的三维模型特征向量集合为 q ) ，七= 1 , 2 ，埘。，“不相关”的三维模型 特征向量集合表示为 局 ，= 1 , 2 ，。假设权值矩阵矿的主对角线元素表 示为，不失一般性，为权值函数作如下约定： 七= l ，2 ，h g d ( 。，g i ) = 【o g i 】2 + 6 玉l ( 1 1 1 ) ，= 1 , 2 ，d ( d 目) = 【o - 目】2 + 6 2 公式( 1 1 1 ) 定义了“相关”与“不相关”的检索结果的边界。可以 中国石油大学( 华东) 硕十论文第l 章前言 证明，当0 叫1 2 最小时，“相关”与“不相关”集合具有最大边界。由此，相 似性匹配可以转化为如下问题：在满足公式( 1 1 1 ) 的前提下，求取使物8 2 最小的权值矩阵矽。这个问题可以通过s v m 学习加以解决。这样，在相似 性匹配过程中，可以根据每一轮检索中用户的相关反馈结果，计算每一步 的最优的权值组合，通过自适应调整相似性匹配函数达到模拟人类基于主 观认知进行检索的目的。 三、结合语义的相似性匹配方法 基于人类的感知特性，在相似性匹配中有必要考虑主观性的问题，因 此，进行包含主观语义的相似性匹配方法的研究是十分必要的。在基于内 容的三维模型检索研究中，这一问题已经开始得到重视。s u z u k i 等人嗍使 用一种多维综合度量( m u l t i d i m e n s i o n a ls c a l i n g ) 的方法，首先创建一 个用户兴趣度空间，然后，使用多元回归分析( m u l t i p l er e g r e s s i o n a n a l y s i s ) 方法建立从三维模型特征空间到用户兴趣度空间的函数映射， 将主观的语义关键字与三维形状特征综合起来，实现结合人类主观语义认 知的三维模型检索。s u z u k i 等人对主观语义的考虑主要体现在从三维模型 特征空间到用户兴趣度空间的函数映射这一方面，其相似性匹配方法仍然 采用传统的e u c l i d e a n 距离。而i b a t o 等人则采用通过训练得到的s v m 学习分类器来模拟人类基于主观认知的检索，其对主观语义的考虑体现在 相似性度量方法和用户的相关反馈上。z h a n g 等人呻1 则通过隐性语义标注 ( h i d d e na n n o t a t i o n ) 的方法，构建对应于三维模型库的语义树结构。该 结构具有一个概率表，每个值分别表示三维模型具有某种语义属性的概率。 对于训练集中的三维模型，其概率值根据是否具有某种语义属性而被标注 为0 或l 。对于未被标注的三维模型，使用基于核回归( k e r n e lr e g r e s s i o n ) 的主动学习( a c t i v el e a r n i n g ) 算法，计算出三维模型对应于各个语义节 1 6 中国打油大学( 华东) 硕十论文第1 章前言 点的概率值。