（计算机软件与理论专业论文）基于内容的三维模型检索方法研究及实现.pdf

摘要 摘要 随着多媒体技术及网络的迅速发展，三维模型也逐渐成为继声音、图像和视 频之后的第四种多媒体数据类型。针对海量网络信息中搜寻需要的三维模型问 题，研究三维模型预处理、交互式检索方式以及特征提取等三维模型关键技术， 具有重要的理论意义和实际应用价值。研究的主要进展有： ( 1 ) 总结分析了基于内容的三维模型检索的研究现状、相关技术及典型的 三维模型检索系统。 ( 2 ) 实现了c p c a 与各向同性两种预处理方法，并对其性能进行了对比与 分析，为三维模型特征提取提供了基础，有效提高了检索算法的准确 性。 ( 3 ) 提出了一种新颖的“搭积木 式三维模型检索方式。与现有的检索方 式不同，用户通过“搭积木的方式构建想象中的查询模型，实现了 一种人机交互式的联机检索新方式。实验表明，这种基于模型构建的 交互式检索方法简单易用，更符合真实的检索环境，开拓了三维模型 检索方式的新思路。 ( 4 ) 改进了一种基于正视图描述符的特征提取算法。从实验结果来看，相 对于简单的形状分布特征提取算法，该方法对模型具有良好的区分能 力，并结合两种预处理方法进行了分析与比较。 ( 5 ) 设计开发了基于p p 风格的软件体系结构的3 d m o d e i r e t r i v a l 系统。该 系统结合c s 与b s 架构，实现了本文所涉及的相关检索技术，具有 简单、易用、扩展性强的特点。 关键字：三维模型，三维模型检索，特征提取，搭积木，相似性度量 a b s t r a c t r e s e a r c ha n di m p l e m e n t a t i o no fc o n t e n t - b a s e d3 d m o d e lr e t r i e v a lm e t h o d s a b s t r a c t d u et ot h ed e v e l o p m e n to fm u l t i m e d i aa n di n t e r a c tt e c h n i q u e s ，t h e3 dm o d e l s a r eg r a d u a l l yb e c o m i n gt h ef o r t hm e d i ad a t at y p ea f t e rs o u n d ，i m a g e sa n dv i d e o a i m a tt h ep r o b l e mo f s e a r c h i n gf o r3 dm o d e l si nm a s s i v en e t w o r ki n f o r m a t i o n ，w es t u d y p r o - p r o c e s s i n g ，i n t e r a c t i v er e t r i e v a lm e t h o d s ，f e a t u r ee x t r a c t i o na n do t h e r3 dm o d e l k e yt e c h n o l o g i e s t h er e s e a r c hw o r kh a sa ni m p o r t a n tt h e o r e t i c a la n dp r a c t i c a lv a l u e t h em a i np r o g r e s s ： ( 1 ) s u m m a r i z ea n da n a l y z ep r e s e n ts t a t u so fc o n t e n t - b a s e dr e t r i e v a lo f3 d m o d e l s ，r e l a t e dt e c h n o l o g ya n dt h et y p i c a l3 dm o d e lr e t r i e v a ls y s t e m ( 2 ) i m p l e m e n tt h ec p c aa n di s o t r o p i cp r e p r o c e s s i n g ，a n dw ea l s oc o m p a r ea n d a n a l y z et h ep e r f o r m a n c e i tp r o v i d e sab a s i sf o rf e a t u r ee x t r a c t i o n , a n d e f f e c t i v e l yi m p r o v e st h ea c c u r a c yo ft h es e a r c ha l g o r i t h m ( 3 ) p r o p o s ean e w3 dm o d e lr e t r i e v a lm e t h o d 、) l ，i t l lb u i l d i n gb l o c k s d i f f e r e n t f r o mt h ee x i s t i n gr e t r i e v a lw a y s ，t h eu s e rc o n s t r u c t si m a g i n a r yq u e r ym o d e l t h r o u g hb u i l d i n gb l o c k s ，a n da c h i e v ean e wh u m a n - c o m p u t e ri n t e r a c t i o n o n - l i n er e t r i e v a lw a y t h ee x p e r i m e n t ss h o wt h a tt h ec o n s t r u c t i o no fs u c ha m o d e l b a s e di n t e r a c t i v es e a r c hm e t h o di ss i m p l et ou s e ，m o r ei nl i n ew i t ht h e a c t u a lr e t r i e v a le n v i r o n m e n t ，a n do p e nu pa3 dm o d e lo ft h en e wi d e a s r e t r i e v a lm e t h o d ( 4 ) i m p r o v ea ne x t r a c t i o na l g o r i t h mb a s e do nt h ee l e v a t i o nd e s c r i p t o r f r o mt h e e x p e r i m e n t a lr e s u l t s ，c o m p a r e dt o as i m p l es h a p ed i s t r i b u t i o ne x t r a c t i o n a l g o r i t h m ，t h em e t h o do ft h em o d e lh a sag o o da b i l i t yt od i s t i n g u i s hb e t w e e n , a n dac o m b i n a t i o no ft w om e t h o d so fp r e p r o c e s s i n go ft h ea n a l y s i sa n d c o m p a r i s o n a b s t r a c t ( 5 ) d e s i g na n dd e v e l o pa3 d m o d e l r e t r i v a ls y s t e m w h i c hi sb a s e do nt h e p p - s t y l es o f t w a r ea r c h i t e c t u r e t h es y s t e mc o m b i n e sc sa n db ss 仃u c t u r e ， a n di m p l e m e n t sr e l e v a n tr e t r i e v a lt e c h n o l o g yo ft h ep a p e r i ti ss i m p l e ， e a s y - t o - u s e ，e x p a n s i o na n ds t r o n gc h a r a c t e r i s t i c s k e y w o r d s ：3 dm o d e l ，3 dm o d e lr e t r i e v a l ，f e a t u r ee x t r a c t i o n ，b u i l d i n gb l o c k s ， s i m i l a r i t ym e a s u r e m e n t i i i 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：刻嗑登 指导教师签名： 鲴! 盈金 加。孑年6 月9e t 2 嘲年多月，夕日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：到晚静 刎年乡月夕日 第一章绪论 第一章绪论 随着计算机技术的发展和网络时代的到来，图像多媒体信息来源不断扩大。 三维模型作为继声音、图像和视频之后的新一代多媒体数据类型，是最直观、最 具表现力的多媒体信息。与二维图像相比，三维模型能够给人们带来更加丰富的 感知细节。三维模型不仅在数量方面快速增长，而且其应用领域也越来越广泛。 基于内容的三维模型检索正是在这种背景下，成为近年来研究的热点。研究该项 技术既有深远的意义，也将面临着巨大的挑战。本章首先介绍课题的背景与研究 意义，然后给出了本文的主要贡献，最后给出了本文的组织结构。 1 1 课题背景与研究意义 基于内容的三维模型检索技术涉及到计算机图形学、计算机视觉、图像处理、 图像理解、人工智能、模式识别和数据库等诸多研究领域。该研究的深入必将推 动其它相关领域的发展。基于内容的三维模型检索技术的主要特点有： ( 1 ) “百闻不如一见，三维模型的空间复杂性使得三维模型难以用简单的 词语来表达。对于三维模型来说，形状是个复杂的概念，至今仍然没有统一的定 义，三维模型可以通过多边形网格、体积、点云数据等来表示。 ( 2 ) 对于从不同三维模型中获得的特征，很难自动地在它们之间建立联系， 只能通过相似性度量来完成。 ( 3 ) 具有相同拓扑结构的模型表达的语义可能不同。比如模型马与模型人 的拓扑结构也许会相同，但是语义却差别很大。 ( 4 ) 具有同样语义的模型也许会有不同的拓扑结构。例如，从外表看，椅 子有很多种形状，拓扑结构也不同，但是它们都属于椅子。而对于同一个模型， 由于它的位置与方向的不同，它所表示的特征也许有很大不同，因此，在检索过 程中应该将这些因素都考虑进去。 基于内容的三维模型检索技术的应用非常广泛，如： ( 1 ) c a d 与c 蝴领域 第一章绪论 在计算机辅助设计( c a d ) 和计算机辅助制造( c a m ) 领域，利用数字图 像来表示待加工的机械零件，只能给人们提供一个外观结构的显示，而不包含足 够的可供加工的几何信息。如果用三维模型来表示机械零件的几何结构，就可以 完全记录零件的几何信息，使得自动来料加工成为可能。 ( 2 ) 生物领域 生物分子模型检索技术很早就得到了重视与研究，特别是蛋白质分子模型的 检索具有很重要的应用价值。蛋白质分子的模型的相似性不仅取决于蛋白质分子 模型的三维几何信息，还与蛋白质分子氨基酸组成，链接结构等生物特性有关。 目前，蛋白质分子模型系统已经广泛地应用到医药设计、生物分子模型设计等领 域中，并且获得了很好的实用价值。 ( 3 ) 医学领域 通过三维成像技术构建的数字化的人体器官模型，可以帮助医生更加直观的 诊断病情。c t 和核磁共振是常用的人体疾病探测手段，并在此基础上发展了交 互式外科技术。外科医生可以在三维显示系统的引导下，进行胸内，颅内各种复 杂条件下的手术。这些应用均促进了三维几何结构的描述，可视化技术和人机交 互等三维视觉计算领域的研究。 ( 4 ) 文物保护 浙江大学与敦煌研究院合作，利用虚拟现实、图像处理与人工智能等技术解 决敦煌石窟虚拟重现、脱落壁画复原与演变模拟等问题完成了莫高窟中壁画与彩 塑的数字化摄影与保存，并开发了包括莫高窟外景在内的石窟虚拟展示与旅游参 观系统【1 】o ( 5 ) 犯罪与安全预防 当将模型的内容限制在特定领域时，基于内容的三维模型检索技术将找到更 为具体的应用。例如，安全部门可以将人脸部特征存储在数据库中，通过人脸模 型识别就有可能从大量的人脸库中自动识别出特定的目标。毫无疑问，这具有重 大的社会价值。 此外，在工业产品的模型设计、虚拟现实、3 d 游戏、多媒体教学、影视动 画、模拟仿真等各个领域被广泛使用。 综上所述，基于内容的三维模型检索技术涉及多个研究领域，有着广泛的应 2 第一章绪论 用前景。在不久的将来，人们可以像使用二维图像那样任意地使用三维模型。经 过近几年的研究，基于内容的三维模型检索技术得到了长足的发展。但是，基于 内容的三维模型检索技术仍然存在以下难点： ( 1 ) 模型本征表示 如何保证提取的形状特征在模型发生平移、旋转、缩放等情况下保持稳定性， 如何提高检索的准确性，是三维模型检索研究的一个难点。 ( 2 ) 用户查询意图的表示 用户如何向计算机提交查询意图呢? 对大多数用户而言，他们对所需查询的 模型的概念有时是不明确的，他们只能用诸如“想查找一个像什么样的物体或模 型等模糊语言来描述自己的查询意图，三维模型低层特征表示与人们对三维模 型的认知之间存在着“语义鸿沟”。如何准确的表达用户的查询意图，如何将这 些模糊的不明确的想法用计算机语言进行描述，是三维模型检索研究中极为挑战 的课题。 ( 3 ) 三维模型特征描述符 三维模型是一个高维数据，三维模型检索面临的一个重大问题仍是“维数灾 难”，如何寻找一个良好的特征描述符是模型检索过程的关键环节。对一个普通 的三维模型而言，它具有几何形状、纹理、拓扑等特征。如何找到一种三维模型 的特征描述符，来合理地描述三维模型也是三维模型检索的一个难点问题。 因此，如何表示模型的本征，如何准确地表示用户的查询意图，如何用特征 描述符合理地描述三维模型，从而在网络信息的海洋中搜寻人们需要的三维模 型，就成了一个亟待解决的课题。本论文的工作就是在这样的研究现状下开始的， 研究内容主要围绕着三维模型预处理、用户查询意图的表示、特征提取、力图解 决“语义鸿沟 问题的人机交互技术等问题展开系统、详细的研究。 1 2 本论文的主要贡献 本文总结国内外基于内容的三维模型检索技术的研究成果，以及在新的应用 环境下所面临的挑战，提出一套解决方案，旨在充分发掘该项技术的潜力，克服 局限性，拓展应用范围。主要贡献在于： 第一章绪论 ( 1 ) 总结分析了基于内容的三维模型检索的研究现状及其相关技术，给出了 当前几种较为典型的三维模型检索系统。 ( 2 ) 为了提高检索算法的准确性，在提取三维模型特征之前需要对模型进行 预处理。本文实现了c p c a 与各向同性两种预处理方法，并对其性能进行了对 比与分析。 ( 3 ) 分析总结了当前存在的三维模型检索方式，并且提出了一种新颖的“搭 积木”式三维模型检索方式。类似于儿童的搭积木游戏，用户利用计算机通过“搭 积木”的方式构建想象中的查询模型，实现了一种人机交互式的联机检索新方式。 实验表明该方法简单易用，更符合真实的检索环境，开拓了三维模型检索方式的 新思路。 ( 4 ) 改进了一种基于正视图描述符的特征提取算法。首先对模型进行预处理， 然后从六个不同的视角利用正视图描述符描述模型信息。从实验结果来看，相对 于简单的形状分布特征提取算法，该方法对模型具有良好的区分能力，并结合两 种预处理方法与s h i h 方法进行了比较与分析。 ( 5 ) 设计开发了基于p p 风格的软件体系结构的3 d m o d e l r e t r i v a l 系统，实 现了真正意义上的组件“即插即用”，在扩展功能的过程中消除了大量重新编译 链接的麻烦，从而为新版本的异地发布和维护提供极大的方便，同时也提高了系 统的可扩展性、可定制性和可维护性。该系统结合c s 与b s 架构，实现了本文 所涉及的相关检索技术，具有简单、易用、扩展性强的特点。 1 3 本论文的组织结构 全文共七章。 第一章是绪论部分。主要介绍了课题背景、主要贡献以及创新点。 第二章是三维模型检索技术概述部分。主要对三维模型的研究现状进行全面 的综述，比较详细的介绍了一些有代表性的三维模型检索技术。 第三章是三维模型预处理部分。主要实现了c p c a 与各向同性两种预处理方 法，并对其性能进行了对比与分析。 4 第一章绪论 第四章是一种新的“搭积木式三维模型检索方式部分。详细介绍了一种新 颖的“搭积木”式三维模型检索方式。 第五章是一种改进的基于正视图描述符的特征提取算法部分。详细介绍了一 种改进的基于正视图描述符的特征提取算法，并通过实验与简单的形状分布特征 提取算法，以及s h i h 方法进行了比较与分析。 第六章是三维模型检索系统设计与实现部分。详细介绍了3 d m o d e l r e t r i v a l 系统的系统结构以及各个部分的实现细节。 第七章是总结与展望部分。 1 4 本章小结 本章阐述了基于内容三维模型检索的研究背景与意义，确定了本文的研究内 容，说明了本论文的组织结构。 第二章三维模型检索技术概述 第二章三维模型检索技术概述 近年来，随着计算机图形学的发展以及数字化技术、可视化技术的提高，三 维模型的应用越来越广泛。如何在浩如烟海的三维模型数据库和网络中快速而有 效地搜寻有用的、同主题的模型，这便构成了三维模型检索的主要目标。本章将 从三维模型检索框架、特征提取技术、相似性度量以及典型的三维模型检索系统 四个方面分别介绍检索技术。这些技术是近年来提出的比较有代表性的技术，而 且大部分已经应用到了实际的三维模型检索实验系统中。 2 1 三维模型检索框架 一个典型的三维模型检索框架可以描述为图2 1 所示，包含一个有索引结构 创建的在线与离线检索机制的数据库。为了有效地在线检索一个大的模型集合， 建立一个数据结构与搜索算法是必要的。在线检索机制计算搜索描述，而后从建 立索引的数据库结构中检索与描述的模型相似的模型。两个描述的模型之间的相 似性通过不同的度量来量化。 w e b 刘三维模型 三维模型实例 模型坐标 预处理与 标准化 检 二维草图7 i 特征提取r 旧 索 文本描述 界 面 检索结果输出 特征提取 及索引 文本li 二维 关键字ii 特征 索引ii 索引 文本 相似性 匹配 二维 相似性 匹配 三维 特征 索引 三维 相似性 匹配 图2 1 一个典型的三维模型检索框架1 有三种方法来区分所提供的检索对象：( 1 ) 从获得的结果中来选择新的检索 对象，( 2 ) 通过提供的描述的检索对象直接来检索，( 3 ) 通过提供的存在的三维 6 第二章三维模型检索技术概述 模型的实例来检索或者通过创建的三维模型来检索，三维模型可以通过使用三维 工具来创建或者通过三维模型的二维投影来创建。另外，可以对检索的模型进 行可视化。 2 2 特征提取技术 三维模型的特征提取是基于内容的三维模型检索技术的研究重点，模型特征 值的优劣直接决定了能否“准确”的找到目标模型。进行特征提取的目的是提取 出能更好地区分不同三维模型的特征描述符，以便在模型匹配过程中计算两个模 型之间的相似度，从而从数据库中检索出与用户查询意图最为相似的三维模型集 合。 三维模型检索技术的关键是提取特征，在提取特征时要满足以下一些基本要 求【3 】： ( 1 ) 平移不变，在平移变换前后，3 d 模型特征要保证基本不变。 ( 2 ) 缩放不变，在缩放变换前后，3 d 模型特征要保证基本不变。 ( 3 ) 旋转不变，在旋转变换前后，3 d 模型特征要保证基本不变。 ( 4 ) 对噪音具有鲁棒性，有噪音的情况下，3 d 模型要保证其特征相似。 ( 5 ) 对重采样和简化具有鲁棒性，在重采样和简化变换前后，3 d 模型要保 证其特征相似。 以下将分别介绍一些基于内容的三维模型检索特征提取技术，这些技术是近 年来提出的比较有代表性的技术，而且大部分己应用到了实际的三维模型检索试 验系统中。按照所使用三维模型特征的不同，三维模型特征提取可以划分为：( 1 ) 基于低层特征的方法；( 2 ) 基于高层结构特征的方法；( 3 ) 基于视图特征的方法。 2 2 1 基于低层特征的方法 在三维模型检索中，基于低层特征通常用来描述三维模型的几何特征与统计 特征，三维模型之间的相似性可以通过比较它们的特征来进行度量。 2 2 1 1 基于全局几何特征的方法 基于全局几何特征的方法，主要以三维模型的表面积、中心点、最小包围盒、 7 第二章三维模型检索技术概述 主轴等全局的几何信息作为特征值。 h e a l y 【4 】提出对三维空间上的几何信号分析。与二维空间上的傅立叶变换相 比，球面傅立叶变换还可以对三维形状进行多分辨率描述。砌c 【5 1 使用傅立叶 变换方法首先对三维模型进行规范化和体素化预处理，然后对体单元进行离散的 傅立叶变换。k a z h d a n t 6 】首先采用一系列同心球对模型进行分解，接着对落入每 个球壳的点进行球面傅立叶变换，最后根据变换系数在每个频带下的旋转不变性 提取旋转不变形状特征。 f u n k h 7 】使用球面调和函数提取三维模型特征。球面调和函数源自球面上的 拉普拉斯方程，它们构成了球面上连续函数空间的一组完备单位正交基。 p a p a d a k i s 8 】提出了一种基于球面调和函数理论的三维形状检索方法。 毛棉等1 9 1 提出一种基于深度加权法向映射的三维检索算法，从归一化处理后 的物体形状出发，计算关于视点方向的深度加权表面法向统计分布，并将该分布 沿视点方向作球面调和分析得到深度加权法向映射特征方法。 l i u 1 0 1 采用d e l t a 函数对模型在频域空间进行采样，提高了同心球分解的鲁 棒性。对一些模型的检索实验表明，该采样算法可以有效地提高检索准确率。 孙晓鹏等【1 1 】将三维网格模型，投影为三维的光顺主曲线；通过对主曲线沿弧 长方向的均匀分割采样，提取主曲线的空间位置和姿态等形状特征。该方法降低 了多分辨率、噪声等因素影响对三维网格模型形状描述的干扰。庞明勇等【1 2 】提 出了一种基于特定轴向上体积分布特征的三维网格模型检索方法。 基于全局几何特征的方法计算简单，节省存储空间，而且一定的全局几何信 息具有几何不变性。然而，不同的形体可能具有同样的全局几何特征，这样对于 小的扰动非常敏感。 2 2 1 2 基于全局统计特征的方法 对一个三维模型进行参数化是一个很复杂的问题，同时由于三维表面有任意 的拓扑，这使得一些在二维图像被使用的方法无法直接应用在三维领域。因此， 从统计学的观点出发，寻找出有意义的统计特征成为研究人员首先考虑的方法。 目前的研究中主要使用了如下统计特征：模型顶点间的几何关系( 距离、角度、 法线方向关系等) ，模型顶点的曲率分布特征、各阶统计矩以及各类变换特征系 第二章三维模型检索技术概述 数等。 o s a d a 【1 3 】根据不同几何形体表面顶点间的相互关系呈现出不同的分布特征， 将一个任意的、可能退化的三维模型中复杂的特征提取转换成相对简单的形状概 率分布问题。 z a h a r i a l l 4 】提出用3 d s s d ( 3 ds h a p es p e c t r u md e s c 邱t o r ) 方法对三维模型进 行描述，其主要思想是根据物体表面的一些局部几何属性( 如某点的曲率) 提供物 体内在的形状索引( s h a p ei n d e x ，s i ) 描述。s i 被定义为某点关于两个主要曲率 的函数，则3 d s s d 被定义为s i 在整个模型网格上的分布，用直方图表示，3 d s s d 对几何转换和比例缩放具有不变性。但该方法仅对一些易见的、显著的、有突起 的特征描述准确，并且对模型的拓扑很敏感，对任意网格描述之前需进行规范化 的预处理。 为了解决3 d s s d 方法对拓扑的敏感问题，z a h a r i a 【1 5 1 提出了一种新的三维模 型的特征描述符0 3 d h t d ( o p t i m a l3 dh o u g ht r a n s f o r m d e s c r i p t o r ) 。0 3 d h t d 是基于h o u g h 变换的思想而定义的。针对三角面片描述的三维网格模型，将三 角形质心作为原始点集映射到某参数空间，通过h o u g h 变换确定参数集合，以 此作为模型的特征描述。0 3 d h t d 并没有很好地解决几何不变性。 z h a n g 1 6 1 采用基于傅里叶变换与矩的思想对模型进行特征描述，在应用时傅 里叶变换对边界的变化很敏感，矩则对物体的质量分布较为敏感，这些都影响了 检索的效果。h o u 1 7 】重建c s r b f 曲面，根据网格顶点方向夹角来提取特征，该 方法能有效提取脊线特征，但算法复杂，计算量太大。贾骥提出了一种网格 分解二维投影边界点的三维模型检索方法，可以在较短的响应时间获得较优的检 索性能。 矩( m o m e n t ) 是另外一种比较典型的变换特征。c a n t e r a k i s 1 9 】将z e r n i k e 矩从二 维推广到三维。三维z e r n i k e 多项式是三维模型函数在一组正交函数上的投影， 表达式简单，并且具有良好的检索性能。n o v o t n i 2 0 1 提出一种基于三维z e m i k e 不变矩函数的特征提取方法。该方法以球面调和函数为基础，将三维模型划分为 体元网格并对其进行规一化处理；然后计算其几何矩；最后在此基础上求出 z e m i k e 矩。三维z e r n i k e 矩具有旋转不变形，对三维模型的拓扑结构变形和几何 性质变形具有一定的鲁棒形。 9 第二章三维模型检索技术概述 统计特征的计算简单，易于理解。由于统计方法提取的是模型的全局特征， 因而适合进行模型的全局匹配。但是统计方法不能良好的反映模型的本质特征， 并且带有随机性，检索性能不稳定，这样计算出的模型特征无法进行可视化的描 述，不适合对模型进行局部匹配，对原模型中丢失的特征信息也无法提取。 2 2 1 3 基于局部特征的方法 j o h n s o n l 2 1 】应用位于曲面点周围的二维柱状图的旋转图像来识别混乱的三维 场景。此方法对于三维形状匹配非常困难，而且对于如何定义满足不同三角形的 函数是不明确的。 k o r t g e n 2 2 1 提出三维形状上下文是模型表面某一点的局部特征，以该点为中 心，将其它表面点与该点的相对位置，按照相同的方式( 壳、扇区以及混合模式) 进行分类。应用前后的三维形状上下文关系来进行三维形状检索与匹配。 y o s h i z a w a l 2 3 提出基于多项式曲面的局部拟合，对曲率张量和曲率导数逼近，不 能直接用于三维离散曲面。 基于局部特征的方法匹配效率低，效率指数并不简单，而且获得不同度量的 方法并不遵守三角形的不等性。由于表面属性的多样性和复杂性，对于模型的特 征描述还需要进行大量的研究和试验。 2 2 2 基于高层结构特征的方法 基于低层特征的检索技术只是考虑了三维模型的几何特征或者拓扑属性，而 基于高层结构的检索技术则是描述了三维模型各组成部分之间的关系，可以通过 骨架特征或者r e e b 图来表示。 2 2 2 1 基于骨架特征的方法 所谓骨架是指对三维模型主要特征的一种直观描述，它符合人类的视觉特 征。基于骨架特征的方法进行匹配时采用的是节点属性和拓扑匹配，因此它既可 以对模型进行全局匹配，也可以进行局部匹配，同时骨架描述对模型的几何变换 如旋转、缩放、平移等是鲁棒的【2 4 】。 s u n d a r 2 4 1 把三维模型骨架应用于模型检索，对经过体素化的模型通过细化方 法提取三维模型骨架。b i a s o t t i t 2 5 1 提出使用显性骨架的方法。 1 0 第二章三维模型检索技术概述 另外，在医学的虚拟内窥镜手术中，人们致力于研究如何提取管状器官的中 轴线，a m e n t a 2 6 1 首先计算出模型的v o r o n o i 图，并在此基础上计算出模型的骨架， 它描述了模型的全局特征，但是v o r o n o i 图的计算开销和存储量非常庞大，更适 合实体模型，对于有孔、洞的模型还需要进行特殊的处理；另外，v o r o n o i 图的 构造对噪声也非常敏感，边界上小的噪声常会导致密集的v o r o n o i 图，这就增加 了计算量，影响了对模型特征的精确描述。因此，这种方法的实用性有待更进一 步的研究。 基于骨架特征的提取方法更适合有关节的模型，由于匹配时采用的是节点属 性和拓扑匹配，因而对模型的几何变换如旋转、缩放、平移等是鲁棒的。由于有 着其它方法不可替代的优点，如直观，可进行全局和局部匹配等，因此在未来的 三维模型检索中是一个值得关注的研究方法，但是进行骨架提取时对原始模型的 要求比较严格，对一些退化的模型进行骨架提取则可能会导致不正确的结果。 2 2 2 2 基于r e e b 图的方法 s k l l a g a w a 【2 7 1 采用了另一种骨架的提取方法。定义在模型表面的连续标量函 数p ( v ) 为三维模型构造了一个二维的图形r g ( r e e bg r a p h ) 描述符。r e e b 图不 仅可以描述模型的特征，同时还描述了模型的空间拓扑关系。 h i l a g a t 2 8 1 采用测地距离来定义三维模型的r e e b 图用于匹配操作。该方法首 先定义一个测地半径，把曲面分割成不同的子曲面，然后根据子曲面的连通性定 义模型的多分辨率r e e b 图。 c h e n t 2 9 】采用多分辨率r e e b 图构造了一个三维模型检索系统。a u g m e n t e d r e e bg r p a h s 是多分辨率r e e b 图的一种改进【3 0 】，主要是提取更多的几何特征以便 用于模型的局部属性描述。 黄坤武洲针对m r g 方法的一些处理步骤较长，不能处理包含多个连通分量 的模型，对它进行了改进，提高了处理速度。 由于r e e b 图具有平移、旋转不变性，对模型变形引起的变化、噪音带来的 影响不敏感，具有鲁棒性。但是r e e b 图是通过量化构成的，它不能够反映三维 模型真实的拓扑连接关系。因而也就很难采用多分辨率r e e b 图去解释三维模型 的结构。另外，对于一个三维模型来说，其构造出来的节点数会很多，从而可能 第二章三维模型检索技术概述 导致匹配过程中需要耗费大量的时间。 2 2 3 基于视图特征的方法 二维视图包含了丰富的信息可以用来描述三维模型，因此很多二维形状描述 符可以直接应用于三维形状内容的理解。基于视图的检索技术是借助成熟的二维 图像检索进行三维模型检索。基于视图的检索技术是使用许多二维图像来表现三 维模型。因此，二维特征可以用作三维模型的相似性索引，每一个二维图像可以 通过从不同的视觉获得三维边界轮廓。 a b b a s i 3 2 1 提出如何选择最优视图集合用于三维模型识别，采用的二维形状特 征是曲率尺度空间。c y r 3 3 1 首先对一个三维模型从不同视点得到大量的视图，接 着定义每个视图的二维形状特征，最后对视图进行聚类分析，选择一些彼此之间 存在明显差异的视图作为代表性的视图。m i n l 3 4 】从三维模型的正视、侧视和俯视 三个固定方向提取模型轮廓图，基于视图的检索技术实现三维模型检索。c h e n ”】 提出基于视觉相似的侧面影像比较实现三维模型检索。每一个侧面轮廓由一个二 维图像来表示，使用z e m i k e 矩与傅立叶描述符来描述每一个二维图像。该方法 可以尽早排除不相关的模型，缩小检索范围，提高检索速度。m a h m o u d i 3 6 给出 了一个基于三维模型视图的三维模型特征检索机制，通过形状的分割方法使用曲 率刻度空间描述符( c s s ) 来解决刻度问题。 利用基于视图的检索技术进行三维模型检索时，通过定义更多的视图通常可 以获得更好的检索准确率，但是随着视图的增加，匹配时间会以几何数的方式增 加。因为在匹配过程中，系统需要对所定义的视图进行穷举搜索，然后对代表不 同模型的视图集合之间构造最优视图匹配。因此对于基于视图的检索技术，一个 最值得注意的问题就是如何在不增加视图数量的情况下来提高检索准确率，从而 保证检索效率。 除了以上几种特征提取方法外，还可以利用三维模型的综合特征进行检索。 k u o 3 7 】提出了一种基于主平面分析与动态规划组合的三维形状表示模式。首先将 顶点投影到主平面上将三维模型转换为一个二维图像，然后使用动态规划将二维 图像分割成许多不相交的三角形，最后对于每一个三角形，将直方图与矩作为特 第二章三维模型检索技术概述 征向量进行相似性搜索。高波涌等3 8 】将基于视图描述的形状特征和三维z e r n i k e 矩两种特征应用于三维模型检索，并且根据用户反馈在输出层进行融合。 另外，还可以利用三维模型的表面属性，包括颜色、反射系数和纹理等进行 检索。但是由于三维模型表面属性的多样性和复杂性，表面属性特征提取的研究 至今并未得到充分发展。目前在基于内容的三维模型检索领域还没有在不同的情 况下都能表现出很好效果的通用方法，对模型特征描述的精度的判断还缺乏一个 统一的评判体系。 2 3 相似性度量 三维模型特征计算通常得到一组特征向量，相似的三维模型在对应的特征向 量空间中具有相近的距离，而不相似的三维模型间的距离却足够大。三维模型相 似性度量则需要计算特征向量之间的相似距离，并按相似性度大小返回检索结 果，从而实现三维模型检索。目前，在基于内容的三维模型检索研究中，主要有 距离度量法与分类学习法的相似性度量方法。 2 3 1 距离度量法 在三维模型相似性比较算法中，常用的向量距离有e u c l i d e a n 距离、m a n h a t t a n 距离、马氏距离、m i n k o w s k i 距离、z2 距离以及h a u s d o 世距离等阻4 0 1 。 设任意两个三维模型的特征向量表示为x = ( x 1x ：，x 。) ， y = ( 乃，少2 ，儿) ，上述常用的距离公式分别为： ( 1 ) e u c l i d e a n 距离 d ( x ，n =( 2 - 1 ) 在实际情况中，需要考虑向量每一维对相似性计算具有不同的重要性，可以 对每一维定义权值，得到一种加权度量： d ( x ，y ) = 这里w 为不同特征分量的权重。 ( 2 - 2 ) 第二章三维模型检索技术概述 ( 2 ) m a n h a t t a n 距离 d ( x ，y ) = z x ，- y ，f ( 2 3 ) ( 3 ) 马氏距离( m a h a l a n o b i sd i s t a n c e ) 马氏距离首先根据已有的特征向量集合估计出协方差矩阵，然后定义如下的 对称距离： d ( x ，】，) = 4 ( x i ，) 7a ( x 一】，) ( 2 4 ) 其中，a 是根据已有的特征矢量集估计出来的n n 的相似矩阵。 ( 4 ) m i n k o w s k i 距离 d ( x ，】，) = ( 主b j ，) | ) 17 (2-5) ( 5 ) z2 距离 。e ，f 2 ) = 喜篇 ( 2 - 6 ) ( 6 ) 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 ，)( 2 7 ) 其中，d ( x ，y 。) 表示两个特征点集中任意两点之间的距离，如e u c l i d e a n 距 离等，m a x ( ) 为取最大值函数，m i n ( ) 为取最小值函数。 2 3 2 分类学习法 基于分类的相似性度量方法主要是通过预先选取一定规模的三维模型特征 作为训练样本集。然后使用神经网络、支持向量机( s v m ) 等机器学习方法对 其训练，实现对三维特征空间的理想划分，从而得到求解问题的分类器，实现相 似性度量【3 9 1 。目前，在三维模型的相似性度量问题中分类学习法正引起越来越 多研究者的兴趣。 分类学习法还可用于实现三维模型检索中的用户相关反馈机制，通过响应用 户的交互性操作，逐步精化检索结果，实现基于用户兴趣度的个性化检索。 另外，章志勇等【4 j 】提出一种基于视觉的三维模型相似性比较算法。通过计 算三维模型的带深度信息的正交平面投影图像，采用z e m i k e 描述子和r e e b 图 1 4 第二章三维模型检索技术概述 比较这些正交投影图像的形状相似性。 基于人类的感知特性，在相似性度量中有必要考虑主观性的问题，因此，进 行包含主观语义的相似性度量方法的研究是十分必要的。在基于内容的三维模型 检索研究中，这一问题也已经逐渐开始得到重视。 2 4 典型的三维模型检索系统 三维模型检索是近十年孕育出来的新的研究领域，现在还不成熟。最近几年 相继出现了一些三维模型检索的原型系统。目前，比较典型的三维模型检索系统 和搜索引擎主要有： ( 1 ) 美国普林斯顿大学 h t t p ：w w w p r i n c e t o n e d u 搜索引擎网址： h t t p ：s h a p e c s p r i n c e t o n e d u s e a r c h q u e r y c g i ? i n p u t = t e x t _ 3 d 】 提供了二维草图和三维草图的绘制界面，并且具有规模最大的三维模型数据 库，其中包括3 1 0 0 0 个通用的三维模型以及多个专业的三维模型子库，如图2 2 所示： ，一- ，r - 一r v 一 釜兰i 旷黼脚苗黼删s e a r c 烨h 簖e 一 旦哇望皇蝴旦芝弛皇鲤璺! 彦碰曼舅黠g 丝幽胜鲤堂 一! _ r t = 1 ! 一 一 _ = = = ：= = = = = = = = = = ：= = = r i 7 j _ _ ! | 啦量盈苫生啦女 o n e 叫r n o mk e w ，o r a s j n m 吖1 璧g r 魄o u # i * s k 曲 憾e 血啦量j 亟量虹蛐 o f i e 。r m o r ek e v w o r d s 口a 4 b 3 d h 女d 理m m l d o 日ov 0 啦a 帕3 d m o o e l t b f - h - h r 鲥 曲c k 怕h n k b e o w 8s e a f j _ 1 瞄晴 h h d b 日口 f f m o d e k 一3 1 0 0 0 m o 船sd 。a 批 o m f 啉w 啦 v r d d 玳酣 一2 c i 。c ) c q n 嘣c i i n o o e b d e s p o n a i m o d h 一1 f 瑚c “n n 料c m ! n k 日e b c c ，f o 瞄m 咄h 、2 c 1 0 0c a t 盹r 伽jm o c e b o m 椰d t a b o 雌 图2 2 普林斯顿大学三维模型检索系统 ( 2 ) 台湾城市大学网址 h t t p ：w w w n t u e d u t w 搜索引擎网址： h t t p ：3 d c s i e n t u e d u t w d y n a m i c c g i b i n d a t a b a s e l i _ v 1 8 i n d e x h t m l 】 该系统使用m p e g 7 标准的三维形状描述符和多视图描述符对模型特征进 行描述，基于w e b 平台进行三维模型检索，如图2 3 所示： 第二章三维模型检索技术概述 th l ，) d 川t - ，。r - l d b 邮，i8 h “ ”二。川 “ 2 * a ，_ h 4 0 1 t i o h q - m 啦 蒲- h l d 甲-气。 。 棒 - ”，i 日t p “_ “4 。“。“。一一： 0 扎q u a yo y3 lm 州e jh o e