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

摘要 随着计算机硬件尤其是图形扫描设备和图形处理硬件性价比的提高，以及几 何造型软件的普及，越来越多的三维模型在各个领域中褥到了广泛地应用 以三维模型为代表的数字几何称为新代媒体，在互联网的背景下，三维模 型的应用提出了以模型内在特征为基础的三维模型检索问题，这是基于内容的二 维图像检索的新发展 在三维模型检索的研究中，寻找具有平移、旋转和缩放等几何变换不变量或 者不变描述是关键所在同时。由于三维世界中各种三维实体的几何特征非常复 杂，它的描述方法必须能够提供充分的信息所以作为特征描述工具的特征向量 空间应该是易于扩展的，以适应大规模检索的需要 本文在三维模型普及和应用的大背景下，在充分调研国内外相关课题组工作 的基础上，对三维模型的形状描述问题进行了研究，探索了三维模型整体形状特 征的提取，以及如何使用这些形状特征进行三维模型检索，并在进行检索方法探 索的同时，解决实际应用中的问题 基于形状的三维模型检索系统一般由预处理、特征提取、相似性匹配和检索 界面四个部分组成本文的工作集中于静态三维几何模型的整体几何特征的提取 方法和在三维模型检索中的应用论文的主要工作和创新点如下； 提出了一种基于正交多项式系统u 系统的三维矩定义和描述方法针对 传统方式定义的几何矩在计算方面存在的高阶矩计算不稳定、特征向量 空间的扩展受到限制的问题。应用正交多项式u 系统构造了三维u 系 统矩结合u 系统的性质，引入h a d a m a r d 矩阵解决了高阶u 系统函数 的快速计算问题讨论了三维u 系统矩特征的计算结构，并给出了快速 求解方法 提出了一种基于球面调和函数构造的扩展距离描述方法对基于射线的 算法进行了扩展，采用模型表面与射线交点的最远距离作为描述三维模 型的几何特征，利用球面调和变换获得旋转不变的特征向量 提出了一种以模拟的电场力作为特征的启发式方法，将提取模型几何特 征问题与物理模型结合基于物理学中静电场的基本原理，假设点电荷 在三维模型表面均匀分布，然后提取三维模型产生模拟静电场的电场力 特征描述模型该特征在物理意义上定义。适用范围比较广泛 夺提出了一种正交样条矩的定义使用正交样条函数，在三维旋转不变矩 的一般框架下，构造了正交样条矩在三维模型检索中效果优于三维小 波矩 实现了一种三维模型检索预处理方法针对目前的三维检索系统中常见 的二维草图输入方法的局限性，本文假定输3 , 篚j - 维草图是三维模型的 三视图，在对三视图采样基础上，实现了三维体素模型的重构，避免了 二维草图在检索中产生的重复比较同时这种处理方法也可以作为三维 模型检索系统的输入技术的一种解决方案 关键词：三维模型，u 系统矩，扩展距离，球面调和变换，电场力，正交样条矩， 二维草图，三维模型检索 r e s e a r c h 佃s o m e 脚t e c h n o l o g i e so f s h a p e - b a s e d3 dm o d e lr e t r i e v a l l i u y u j i e ( c o m p u t e r a p p l i c a t i o n t 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 ih u a i m p r o v e dm o d d i n gt o o l sa n ds c a n n n gd e v i c e sa r em a k i n gt h ea c q u i s i t i o no f3 d m o d e l se a s i e ra n dl o w e fe x p 簋i s i v e 3 dg r a p h i c sh a r d w a r e 锄dc p u sh a v eb e c o m e f a s tm dc h e a pm o u g ht h 越3 dd a t a 啪b ep r o c e s s e da n dd i s p l a y e dm o r eq u i c k l yo n p c s i tl e a d st ol l i g hd e m a n df o r3 dm o d e l sf r o maw i d e 加g eo f s o u r c 嚣 u n d e rt h eb a c k g r o u n do fi n t e r n e t , 3 dm o d e lr e t r i e v a lo nt h eb a s eo fi n t r i n s i c p r o p e r t i e s i s p r o p o s e d i n a p p l i c a t i o n s o f3 dm o d e l i ti sn e we x t 砌o no f c o n t e n d - b a s e di m a g er e 仃i e v a l i nt h er e s e 缸c ho f3 dm o d e lr e 缸i e v a l , t h ek e yp r o b l e l mi st og e ti n v a r i a n c eo f g e o m e t r i cu m l s g o r m a f i o n so fr i g i db ( ) d i e s 。越t h es a m et i m et h ef e a t u r ev 既t o fs p a c e s h o u l db ee a s yt ob ee x t e n d e d , w h i c hw i l lf a c i l i t a t et h em a s s i v em o d e lr e t r i e v a l d u e t ot h ec o m p l e x i l yo f3 do b j e c t s , t h ea c q u i r e df e a t u r e ss h o u l dc o n m i na d e q u a t e i n f o r m 撕o n 砸sd i s s e r t a t i o nr e s e a r c h e sm a i n l yi nt h r e ea s p e c t s , d e s c r i b i n gt h es h a p eo f3 d m o d e l ；g e t 五n gt h es h a p ep r o p e n i e so f3 dm o d e l s ；a n di n d e x i n g3 dm o d e l sb yu s i n g t h e d e s c r i p t i o n o f i 毽s h a p e p r o p 硎e s n o r m a l l y , f o u rs t e p sa r ei n c l u d e di na3 dm o d e l sr e t r i e v a ls y s t e m , i 已p o s e n o r m a l i z a t i o n , f e a t u r ee x t r a c t i o n , s i m i l a r i 哆c o m p a r i s o na n du s e ri n t e r f a c e t h i s d i s s e n m i o nf o c u s e so nt h ee x u a c u n gm e t h o do fg l o b a lg e o m e l x i cf e a t u r e so f3 d m o d e l sa n di t sa p p l i c a t i o n si n3 dm o d e lr e u i e v a l n 地m a i nc o n t r i b u t i o n so ft h i s d i s s e r t a t i o na r es u m m a r i z e da sf o l l o w s ： an o v e l3 do r t h o g o n a lp o l y n o r m a l sm o r n 吼c a l l e d3 dus y s t 既nm o m e n ti s d e f i n e 正a n di su s e df o r3 dm o d e lr e t r i e v a l a sak i n do fc o m p l e t eo r l h o g o n a l p o l y n o m i a l ss y s t e m , us y s t e mh a sm a n yg o o dp r o p e r t i e s a c c o r d i n gt ous y s t e m t h e o r y t h ef a s tc a l c u l a n o no f u ls y s t e mm o m e n t si se s t a b l i s h e d an o v e lf e a t u r ev e a o r - 既t e n d e dd i s t a n c ei sp r e s s e d i ti so b t a i n e db yf o r m i n ga s p h e r i c a lf u n c t i o no f m a x i m u m d i s t a n c eo f ft h es u r f a c eo f t h em o d e l t h e n , s p h e r i c a l h a r m o n i ct r a n s f o r mi su s e do nt h es p h 能1 1 l ee n e r g yo f t h ec o e f f i c i e n t so f s p h e r i c a l h a r m o n i c sf o r m st h ef e a t u r ev e c t o r e l e c u i cf o r c ef e a l u r ei s p r o p o s e d , w h i c hi sb a s e do ne l e c t r i c f i e l dt h e o r y m s u p p o s i n g3 dm o d e le sc h a r g e db o d y ，w eg e tl i l ee l e c t r i cf i e l df o r c ed i s t r i b u t i o nb y p l a c i n gs o m et e s t i n gc h a r g e sa r o u n d t h e3 dm o d e l t h ef o r c ed i s u i b u d o ni st h e f e a t u r eo f t h e3 dm o d e l t h i sr e p r e s e n t a t i o nh a ss e v e r a lb m e 丘t s f i e t , i ti si n v a r i a n t t os c a l ea n dr i 矛du a n s f o r mb yc a l c u l a t i n gt h es p h e r i c a lh a r m o n i ct r a n s f o r ms e c o n d , i tc a nr e p r e s e n tc o m p l e xa n di l l - d e f i n e dm o d e l sb e c a u s eo f i 乜p h y s i c a lb a c k g r o u n d 3 do r t h o g o n a ls p l i n em o m e n t sa r ed e v e l o p e da sn e g vs h a p ed e s c r i p t o r sf o r3 d m o d e l s t h e ya r er o b u s tt ou a n s l 撕o mr o t a t i o na n ds c a l e , b e c a u s et h e y a l e c o n s t r u c t e di nt h eg e n e r a l3 dr o t a t i o ni n v a r i a n tm o m e n t sd a m e e x p e r i m e n t ss h o w t h a t3 do r t h o g o n a ls p l i n em o n m n t sh a v eh i g h e rd i s c r i m i n a u n gp o w e rc o m p a r e dw i t h 3 dw a v e l e t sm o m e n t s a n o v e lp r e p r o c e s s i n gm e t h o do f a3 dm o d e lr e t r i e v a ls y s t e mi se r e a t e dt h e2 d s k e t c h e sa r cu s e da st h r e e - v i e wd r a w i n g so fa3 dm o d e l a n d0 1 1t h eb a s i so fs a m p l e o ft h r e e - v i e wd r a w i n g s ，t h e3 dv o x e lm o d e li sr e c o n s t r u c t e d i tc a na v o i dt h e m u l t i - c e m p a r i s o n so f2 ds k e t c h e s f u r t h c m n o r et h i st e c h n i q u e 锄b eas o l u t i o no f i n p u ti n t e r f a c eo f 3 dm o d e lr e t r i e v a l 脚o r d s ：3 dm o d e l ，us y s t e mm o m e n t ，e x t e n d e dd i s t a n c e ，s p h e r i c a lh a r m o n i c t r a n s f o r m ，e l e c t r i c a lf i e l dp o w e r o r t h o g o n a ls p l i n em o m e l y 【$ ，2 ds k e t c h ，3 d m o d e lr e u i e v a l 明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 作者签名：封五主 e t i 蓼i ：勐“j 一 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件， 允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采 用影印、缩印或其它复制手段保存该论文。 作者签名：茹】硅导师签名： 参p - 母 1 1 选题背景 第一章绪论 人类生活在一个三维空间中，人类视觉感知的对象是三维立体的三维模型 及其组成的三维场景具有比二维图像更多更丰富的视觉感知细节，更适用于人类 的视觉感知和思维模式【杨育彬等2 0 0 4 从上世纪九十年代中期开始。三维模型在计算机中的应用越来越广泛，工业 产品设计、建筑设计、虚拟现实、计算机仿真、数字人、分子生物学、教育、三 维游戏和影视动画中都广泛地使用了三维模型郑伯川等2 0 0 4 1 o s a d a e t a l 2 0 0 2 1 【钟世镇等2 0 0 1 三维模型之所以得到如此广泛的推广和使用，主要是由于( 1 ) 数字相机、数字摄像机以及扫描工具等获取三维信息和建立三维模型的技术手段 不断进步和成熟，三维信息获取和表达变得越来越容易；( 2 ) 三维图形处理硬件 和c p u 的速度已足够快而且价格便宜，使得三维数据能在微机上快速处理和显 示；( 3 ) 网络的普及使人们易于得到并且使用三维模型数据，也使得三维模型的 传播和应用快速发展 o s a d ae ta l 2 0 0 2 据估计，目前有数以兆计的三维模型存在，并且每天都有大量的三维模型产 生和传播【郑伯川等2 0 0 4 1 。g u n n 估计在工业设计中“只有2 0 的原创思想需要完 全新的设计，有4 0 可以通过组合已有的设计而构建出来，另外4 0 则可以通 过修改已有的设计来取得”【g r a m 1 9 8 2 1 统计发现，在c a d 领域，2 0 0 1 年三维 模型的造型已达到“，到2 0 0 5 年末，达到8 0 i y o r e ta l 2 0 0 3 1 目前，在我国。知识产权保护工作越来越受到重视。2 0 0 5 年的q q 汽车侵 权案倍受国人关注而知识产权保护的相关工作量也越来越大2 0 0 5 年国家知 识产权局共受理三种专利申请4 7 6 2 6 4 件，同比增长3 4 6 其中发明专利1 7 万 件，实用新型申请1 3 万件，外观设计申请为1 6 万件2 0 0 5 年的申请量是2 0 0 0 年的2 1 2 李镭2 0 0 6 】在各种专利尤其是外观设计的申请的核准，审查和批复 的过程中，都需要对各种三维模型进行比较 在工业设计过程中，需要快速提供产品的零件的三维模型，目前有很多三维 零件模型库。在三维影视动画作品，三维游戏制作，以及虚拟现实应用中需要大 曩的三维模型，互联网上许多网站也将三维模型作为一种数字化商品提供给使用 者 要在一个大型数据库中找到适合的三维模型，基于形状的三维模型检索是一 种必要的技术手段基于形状的三维模型检索是指直接根据描述对象的形状特征 进行检索，它能从数据库中查找到具有指定特征或含有特定内容的三维数据在 r，i，lrl-：；_-rl-r-r lr；l l-ri-：- 三维模型应用的各个领域中都能起到重要作用。 基于形状的三维模型检索方法思想起源于基于内容的图像检索，是目前比较 活跃的研究领域。但是，总体上还处于研究的初期，有许多问题有待进一步的研 究【郑伯川等2 0 0 4 1 本课题得到了国家重点基础研究计划项目，国家自然科学基金，中国科学院 计算技术研究所创新基金的支持。 1 2 本文主要内容 本文的目标是研究三维模型的特征描述，探索具有几何不变性的特征表示方 法，并且这些特征易于扩展，在三维模型检索中得到应用 本文的主要贡献和创新点包括； 提出了一种基于正交多项式系统u 系统的三维矩定义和描述方法针对传 统方式定义的几何矩在计算方面存在的高阶矩计算不稳定、特征向量空间的扩展 受到限制的问题，应用正交多项式u 系统构造了三维u 系统矩结合了u 系统 的性质，引入h a d a m a r d 矩阵解决了高阶u 系统函数的快速计算问题。讨论了三 维u 系统矩特征的计算结构，并给出了快速求解方法 提出了一种基于球面调和函数构造的扩展距离描述方法对基于射线的算法 进行了扩展，采用模型表面与射线交点的最远距离作为描述三维模型的几何特 征，利用球面调和变换获得旋转不变的特征向量 提出了一种以模拟的电场力作为特征的启发式方法，将提取模型几何特征问 题与物理模型结合基于物理学中静电场的基本原理，假设点电荷在三维模型表 面均匀分布，然后提取三维模型产生模拟静电场的电场力特征描述模型该特征 在物理意义上定义，适用范围比较广泛 提出了一种正交样条矩的定义使用正交样条函数，在三维旋转不变矩的一 般框架下，构造了正交样条矩。在三维模型检索中效果优于三维小波矩。 实现了一种三维模型检索预处理方法。针对于目前的三维检索系统中常见的 二维草图输入方法的局限性，假定输入作为三维模型的三视图，在对三视图采样 基础上，实现三维体素模型的重构。避免了二维草图在检索中产生的重复比较 同时这种处理方法也可以作为三维模型检索系统的输入技术的一种解决方案。 1 3 本文的内容组织 本文第二章分析了基于形状的三维模型检索的已有方法、研究现状及成果， 同时还详细地说明了基于形状的三维模型检索的系统框架、关键技术和存在的主 要问题 2 j；! 第三章至第七章是作者的主要工作 第三章是使用u 系统构建的u 系统矩，包括两部分内容首先介绍了u 系 统矩的构造方法，随后通过对u 系统矩计算过程进行的详细的分析，改进了计 算方法，加快了计算的速度 第四章是扩展距离的球面调和表达首先定义了表面模型上的扩展距离然 后，介绍了球面调和变换的基本原理和性质，接下来使用球面调和变换构造了扩 展距离的旋转不变的特征 第五章是电场力特征的内容先介绍了物理学静电场基本原理，然后说明如 何使用三维模型产生模拟静电场，接下来介绍使用测试点电荷获取电场力特征， 最后说明三维模型检索实验和结果分析 第六章使用t o ，1 】区间上正交样条基函数定义了一种三维正交样条矩首 先，介绍了区间上样条基函数的概念然后对其进行了正交化，获得正交样条基 函数在此基础上，定义了三维正交样条矩，应用在三维模型检索中 第七章实现了种三维模型检索系统预处理技术重构三维体素模型。首 先分析了目前三维模型检索系统是使用二维草图的不足，然后介绍了使用三个正 交方向二维草图作为平行投影的三视图来重构三维体素模型。最后介绍了这种技 术在我们的原型系统3 d m r 中的使用 第八章总结了论文的主要研舡作并提出了今后的研究方向 ；：；!；，1l，i 第二章基于形状的三维模型检索综述 基于形状的三维模型检索是近十年孕育出来的新研究领域。一般认为，关于 面片模型的基于内容检索的论文首次发表子1 9 9 7 年 v r a n i 6 2 0 0 4 近几年，许 多大学和研究机构都进行了基于形状的三维模型检索研究，比如，美国普林斯顿 大学形状检索与分析( s h a p er e t r i e v a la n da n a l y s i sg r o u p ) 实验室、美国卡耐基 一梅隆大学a m p ( a d v a n c e dm u l t i m e d i ap r o c e s s i n g ) 实验室、德国莱比锡大学 c g i p ( c o m p u t e rg r a p h i c sa n di m a g op r o c e s s i n g ) 实验室、i b m 日本东京研究院 的。三维w e b 环境”研究项目、荷兰u t r e c h t 大学的g i v e ( g e o m e u 3 , ，i m a g i l l g a n dv i r m a le n v i r o n m e n t ) 实验室等。国内的有北京大学的视觉与听觉信息处理国 家重点实验室，浙江大学c a d & c o 国家重点实验室和台湾大学通讯与多媒体实 验室 本章主要介绍目前基于形状的三维模型检索的一些特征提取方法 2 1 基于形状的三维模型检索的总体框架 基于内容检索的一种主要方法是将三维模型的形状映射到特征空间。得到一 组特征向量，然后通过比较其特征向量的值来实现模型检索其关键技术步骤有 四个，分别是模型坐标的标准化与预处理、特征提取与索引、相似性匹配以及检 索界面图2 1 给出了一个典型的基于形状的三维模型检索系统的总体框架 i 一： - - - - - - - - - _ - - - - - - - - - - - - - _ - - - - - 图2 1 三维模型检索总体框架【李宗民2 0 0 5 】 2 2 模型坐标的标准化和预处理 在三维模型获取和建模过程中，同一类模型可能是通过不同的方式得到的。 所以，模型的尺寸可能不统一。位置、方位也可能各有不同而人类的认知系统 对于具有不同缩放尺度，处于不同位置和方位的同类模型的识别是相同的所以， 为了保证三维模型检索效果。所提取的特征应该对于平移、旋转、镜像和缩放变 换是不变的。 通常在进行特征提取和相似性匹配之前，先进行预处理，即将所有待比较的 三维模型变换至一个规范坐标系内这样，即使同_ - - 维模型具有不同尺度、不 同位置、方向、旋转角度和不同的细节层次( l e v e lo f d e t a i l ，l o d ) ，其表示方 式仍旧是唯一的。模型坐标标准化的目的在于使得三维模型检索独立于其所采用 的具体数据表示方式 目前，实现特征描述不变性的预处理方法主要分为两类，一类是找到三维模 型的标准化坐标框架，然后在该坐标框架中进行特征提取；另一类是直接提取与 图像分析中使用的矩不变量作用相似的具有几何不变性的特征 h u 1 9 6 2 获得三维模型标准框架的方法一般是主成分分析( p r i n c i p a lc o m p o n e l l t a n a l y s i s ，p c a ) 方法。 定义并提取具有几何不变特性的特征是非常理想的方法。但事实是。通常这 些特征所具有的不变性往往是不完全的，例如，s u z u k i 等人提出的形状特征只对 绕坐标轴k x 9 0 范围内的旋转变换保持不变性，k a z h d a n 等人提出的反射对称特 征描述只具有平移和尺度不变性而且，这类特征中的大多数，在提取时，也需 要在个规范化的坐标系内计算因此，为了进一步提高检索的准确性往往也 需要进行模型坐标标准化 为了获得平移不变性，通常将模型进行平移变换，令模型的质心或者几何中 心与坐标原点重合为保证旋转不变性，通常使用p c a 计算出模型的标准坐标 系，然后将模型旋转到对应的坐标系中为保证方位不变性，还需要处理模型镜 像问题，需要将模型进行翻转变换，来确保互为镜面对称的三维模型在表示方式 上的同一性最后，为保证缩放变换的不变性，还要将旋转后的三维模型归一化 至标准单元大小因此。一个完整的坐标模型标准化过程可以表示为如下的几何 变换r “材) = z s r t m( 2 - 1 ) 其中，z 是缩放变换矩阵，s 是一个对角阵形式的翻转矩阵，r 为的旋转矩 阵，t 为平移变换矩阵，m 为原始模型坐标【李宗民2 0 0 5 本文是后面具体方法的讨论中均假设模型是多边形面片模型，并且是经过了 平移缩放标准化处理之后的 6 2 2 1p c a 方法 假设一个数据向量集合矿= p i l ，= “，鸭，- 匕) = 【h ，y 2 ，】r e 彤一e n ，令鸭 是集合的平均值，一。篁 矿 卉；v ，其中州表示集合的元素个数该集合的协 方差矩阵为c r - h l - e 和一帆) ( v 一帆) r ，q 是元素v i 和_ 的协方差协方差矩 阵的特征值和特征向量形成了r - 空间的一个正交基底，特征值和特征向量是方 程c 一托o l 。，) 的解 非负对称矩阵所有的特征根都是非负实数通过降序排列矩阵的特征值，对 应的特征向量就是集合v 的最大分布方向的正交基底最大分布方向通常是原 始数据的能量分布的最大方向这样，以巩为坐标原点，以降序捧列的矩阵的 特征值对应的特征向量为正交主方向，组成了该数据集合的p c a 坐标系 令a 是以有序的特征向量为行向量的矩阵那么对于h e 矿使用公式 p ( y 一“v ) ( 2 - 2 ) 就将原数据集合中的向量变换到新的坐标系，即p c a 坐标系( 框架) 中 2 2 2p c a 的改进 在三维模型检索中，使用传统的p c a 存在一个问题。对于三角面片表达的 模型，选择顶点来进行p c a 预处理，那么处理的结果跟模型三角化的结果是相 关的，不同的三角化结果得到的p c a 框架会有所差别 为了解决这个问题，v r a n m 对传统的p c a 进行了改进对于三角面片模型， 使用每个面片的面积作为权值加以调整咖6 2 0 0 4 1 m y = 刍喜踞= 凄争址号盐t 喜蚤；喜( 2 - 3 ) 其中，墨是三角面片的面积，薪是三角面片的质心，s 是模型总面积，m 是 三角面片数，n 是顶点数，4 ，日，c ：是组成第i 个三角面片的顶点索引，碍是所有 以见为顶点的面片的面积和 因此，权重m 定义为雌= 等，显然，杰雌= 一 这样，集合v 的协方差矩阵为c r - 当主叶( ，一怖) 一唧) r ，这样可以同样地 7 得到协方差矩阵的特征向量和特征值进而得到新的p c a 坐标框架 为了保证反射不变性，定义如下几个特征量，工， 正一 至i = 1 蛔( 吱即毛掩 o o ， t 三喜咖坩赡) 文业列。 ( ：4 ) o i o ， 正；昙扣( 即毛) 墨( 鼍吲4 o “l o ， 形成一个分析矩阵s = 撕忙翱旺) ，s i c ( f , ) s i m s ( ) ) 定义一个变换矩阵z ，其主对角线上元素为z ： z - 畦薯 c m ， 先使用了p c a 方法调整模型顶点集，再进行如下处理 pi=zs珙(2-6) 则得到关于平移、旋转、反射和缩放变换不变的三维模型顶点集 2 2 3 “连续 p c a 使用质心坐标( b a , y c e n u i cc o o r d i r l a l 髑) 定义模型三角面片上的一个点， ，皇铆码+ p p s , + ( 卜口一，) p c ，( 2 - 7 ) 其中，o s 口墨l ，o ，l ，o s 口+ ，1 在模型三角面片上，定义如下函数： t a r , ) = j 乙，( v ) 出；2 q j ：d 可_ ， 以+ p p z ，, + o 一口一所，c ) d 声 ( 2 8 ) 那么， t ic y ) = 量f ，( ) = 肌，o 冲( 2 - 9 ) 取，t v ，则得到， 唧- 妻姜儿；曲t i l 智 s ，丛学z 专姜( 2 - 1 0 ) 取，z ( v 一脚) p 一怖) r ，得到的协方差矩阵如下式， o = 击j l p 一脚) ( v 一怫) 7 凼( 2 - 1 1 ) 一去喜( p ) + 五( p ) + 五k ) + ”s 其中，= 厶扣) t o 一- ) p 一- ) r 然后对协方差矩阵进行分解得到p c a 坐标框架 v m n i 6 2 0 0 4 2 2 4 最大法线分布 普建涛等提出最大法线分布( m a x i m u m n o r m a ld i s t r i b u t i o n ，h 甜d ) 获取正 交轴的方法【普建涛等2 0 0 4 p ue ta l 2 0 0 5 1 首先计算三维模型每一个三角面片的法线和面积，将法线方向相同或者相反 的三角形面积累加到一起文中认为方向相同或者相反的法线具有相同的分布 然后选取具有最大面积的法线分布所在方向为第一主轴方向b - ，再从其余的法线 分布中找到第二大面积的法线分布方向，将该方向向垂直于第一主轴矿的平面投 影，就得到正交于扩的第二主轴扩最后使用矿和6 ，的叉乘得到第三主轴， 6 - ；扩x 矿 m n d 规定距离中心较远的一侧为正方向 作者在文中还比较了该方法和p c a 方法各自的优缺点，并提出综合使用两 种方法的使用规则，即根据两种方法确定的包围盒的体积来确定。选择包围盒体 积小的方法 2 2 5p c a 方法的不足 舀一曹一喜 圈2 2p e a 预处理实1 列 v r a n i e 2 0 0 4 由于计算过程中考虑了模型的整体信息，p c a 方法还不稳定如图2 2 中。 对三个茶杯模型使用p c a 求规范化坐标系的时候，茶杯的局部一茶杯把儿的 变化对于规范坐标系的影响很大而且需要检索的模型之间，通常都会存在这种 局部的变化 9 2 3 特征提取 三维模型检索所使用的特征，主要包括通过变换提取的形状特征以及对模型 进行几何运算提取的形状特征物体的形状特征具有多面性，因而导致其具有多 种不同的表示方式。迄今为止还没有任何一种表示方式可以完全符合人类对形 状的识别和理解能力如何得到既能快速简单地进行提取和比较，又能十分有效 地分辨相似的和不相似的三维模型的特征描述，是三维模型检索研究中的关键和 难点 b u s t o s 等提出了对基于形状的三维模型检索技术的分类方法 b u s t o s 融 a l 2 0 0 5 1 b u s t o se ta l 2 0 0 6 将三维模型检索的特征向量提取过程分成一系列的子 过程，在这些子过程的基础上进行分类该分类方法将模型预处理和姿态调整作 为第一个子过程然后，对模型进行几何特征的抽取，或者得到模型表面的相关 属性，比如曲率、法线等；或者得到模型体积特征，比如体元；或者得到模型的 一些投影图再进行一些数值分析，得到最后的用于描述模型的特征向量或者其 他特征 如2 2 节所描述的，三维模型通过预处理，得到一个标准的坐标框架，便于 获得旋转( r o t a l i o n ) 平移( t r a n s l a t i o n ) 缩放( s e a l i n g ) 不变的特征 要抽取的模型几何特征有三类，包括曲面、体积或者视图图像 对于抽取不同的几何特征，各种算法采用不同的数值分析方法比如对于体 素和图像，可以使用傅立叶或者小波变换来进行分析，而曲面可以使用采样方法 来进行分析，另外还有球面调和变换 最终产生的特征可分为三类，包括特征向量、统计直方图或者图( g r a p h ) 特征向量就是将模型的几何特征经过处理后，与高维空间的点对应，得到的表达 模型信息的一组值在统计方法中，是以统计直方图的方式表达三维模型的从 模型拓扑中提取的图可以方便地表达能够分解成为多个有意义部分的模型的结 构信息，比如动物模型的身体和四肢 表2 1 对三维检索算法概述了模型预处理、模型几何特征抽取、数值变换和 特征类型等几方面信息，表中的t 、r 、s 分别表示平移、旋转、缩放 表2 - 1 基于形状的三维模型检索方法概览 特征名称不变量预处理模型形教值变抉方特征类型全局局部鸵否赴理 状抽象法 特征动作变换 三雏几何矩t ，髓 表面或采样特征向量 全局否 者体积 三维z e r m k e 矩不需要表面或采样特征向量全局 舌 者体积 三雏矩不变量不需要裹面采样特征向量全局否 结构矩不需要裹面或采样特征向量全局否 者体积 三维撮半径矩不需要衰面或来样特征向量全局特征否 看体积 b 嘶矩 t ，r 腐 体积采样特征向量全局否 b 样条矩 耵r 培 体积采样 特征向量全局 否 三维妇h d i l k 矩 刖r ，s 体积采样 特征向量 全局否 形分布( d 2 )不需要衷面采样 直方圈全局 吾 射线采样方法不需要震面采样+ 球面特征向量全局否 调和变换 射线采样扩晨方法不需要表面采样+ 球面 特征向量 全局吾 调和变换 d 。h 函数射线采样不需要衰面 采样+ 球面特征向量全局否 方法 谭和变换 形状童方圈 r 体积采样直方田全局吾 旋转不变的点云特 t ，r ，s 体积无直方阳全局否 征 旋转不变的球面调佛体积采样 特征向量全局否 和特征 对称特征仍表面采样 特征向量全局否 加权点囊t ，聃衰面无 直方圈全局吾 扩展的高斯圈 r 衰面无 特征向量全局否 健曲率特征 t ，聃 表面无 特征向量全局，局部舌 方向直方圈特征不需蔓表面采样 特征向量全局否 厚度直方圈调和裹不需要裹面采样特征向量全局 否 选 径向夹角直方圈不需要裹面采样 直方腰全局 舌 三雏傅立叶特征 t ，娜体积三雏傅立叶 特征向量 全局否 变换 三维小被特征 t ，r ，s体积三雏小教变特征向量全局吾 换 轮廓特征 t ，r ，s 图像采样+ 傅立特征向量 全局吾 叶变换 深度信息特征 1 u s图像二维傅立叶特征向量全局否 变挽 光城特征不需要圉像无特征向量全局否 二雏多边彤集方j 盎w 肼圈像采样直方圉集全局否 拓扑匹配 不需要表面无圉全局局部能 基于骨架的方法不需要体积无圈全局局部能 旋转投影不需要裹面无圈全局，局部否 拓扑连接圉方法不需要表面无暖全局局部鸵 下面各节分类介绍表2 - 1 中的各类特征提取方法 2 3 1 三维统计特征 1 三维几何矩( 3 dg e o m e u i em o m e n t s ) 在三维模型中，模型几何分布函数由f ( x , y , z ) e r 3 表示，露= f + ，+ 七阶的 连续矩h j 形式为： 鲰= ( 2 - 1 2 ) f ( x , y , z ) x y j z k d r d y d z心2 j 二lj 如果对三维模型进行离散化，得到一个三维空间点集p 作为它的近似表达， 科 那么，矩计算公式为，缸= 艺y 乒；，其中，p l 是点集中点的数量 p d 理论分析证明，几何矩的完备集( 无穷集) 能唯一地确定一个模型，反之亦 然瞰u 1 9 6 2 】先对模型进行p c a 预处理，然后再计算几何矩，作为用于检索的 特征向量以欧氏距离确定相似度，这种方法直观、简单，易于实现。 对于三角面片模型。v r a n i 6 和s a u p e 使用矩作为特征来进行三维模型检索， 他们用于计算矩的点集是使用基于射线的方法在模型表面统一采样得到的 v r a n i 6 & s a u p e 2 0 0 1 a p a q u e t 等则是使用模型表面面片的质心点计算矩特征 p a q u e t 既d 2 0 0 0 1 v r a n i d 和s a u p e 比较了基于射线的矩和基于质心点的矩，结 果说明前者检索效率较高 v r a n i 6 & s a u p e 2 0 0 i a e l a d 等则是统一在模型表面进 行采样，得到点集，进行矩计算 e a r lda l 2 0 0 2 2 三维z e r n i k e 矩( 3 dz 锄r l i k em o m e n t s ) c a n t e r a k i s 在理论上将z e m i k e 矩从二维推广至三维 o m t e r a k i s 1 9 9 9 三维 z e m i k e 多项式是三维模型函数在一组正交函数上的投影，表达形式简单，并且 具有良好的检索性能n o v o m i 等提出一种基于三维z e m i k e 不变矩函数的特征 提取方法，该方法以球面调和函数为基础，将三维模型划分为具有一定精度的体 元网格并对其尺寸进行归一化，计算其几何矩，在此基础上再求出三维z e m i k e 矩 n o v o m i & k l e i n 2 0 0 4 】 n o v o m i & k l e i n 2 0 0 3 实验表明，三维z 鲫缺e 矩对三 维模型的拓扑结构变形和几何性质变形具有一定的鲁棒性 3 三维矩不变量( 3 dm o m e n ti n v a r i i m t s ) 徐东使用了一种直观的基于几何基元的方法来推导三维矩不变量，使得不变 置的阶数能任意增加i 徐东2 0 0 6 使用符号计算软件，可以求出所有矩不变量的 显式表达式各个独立的三维矩不变量可以用来描述三维物体的形状特征，并且 与旋转，平移。缩放无关三维矩不变量除了可以应用到三维模型检索上，还可 以用于识别物体 4 结构矩( s t m c u n em o m e n t s ) 李宗民等提出了一种称为结构矩的方法j 戗a l 2 0 0 5 a 1 【i j 既a l 2 0 0 5 b 1 在传 统的几何矩定义的基础上进行扩展，提出了结构矩的定义和计算其实质是对原 有几何矩定义中的密度函数经过变换得到新的密度函数在此基础上定义的不变 矩突出或者扩大了形状之间的差别，因而使得形状相似性的比较建立在更为可靠 的基础上 5 三维极半径矩( 3 dp o l a rr a d i u sm o m e n t s ) 李宗民等通过扩展二维极半径矩到三维空间，获得了三维极半径矩五既 a l 2 0 0 5 a 1 【李宗民等2 0 0 6 1 给出了三维极半径矩及三维极半径中心矩具有平移、 缩放和旋转不变性的证明，为三维模型的检索提供了形状特征不变量提取的方 法。 6 b e z i e r 矩和b 样条矩( b e , z i c rm o m e n t sa n dbs p l i n em o m e n t s ) 李宗民提出了使用b e z i e r 多项式和b 样条多项式的b e z i e r 矩和b 样条矩， 这两种矩承袭了b e z i e r 多项式和b 样条多项式的特点，可以得到递推的矩计算 公式，但是由于这两种多项式不是正交的多项式，所以得到的特征矩含有冗余信 息【李宗民2 0 0 5 】 7 三维k r a w t c h o u k 矩( 3 dk r a w t c h o u km o m e n t s ) p a n 等以离散正交k r a w t c h