（计算机应用技术专业论文）基于二维投影的三维模型检索方法研究.pdf

摘要 3 d 数据获取技术 图形硬件 三维数据模型和可视化技术的发展 致使3 d 模型的增多 三维扫描技术与造型工具的日益普及 扩展了可供使用的三维模型 数据库 互联网络的扩张增强了人们获取分散存储的三维模型的能力 并为有效 传播高质量模型创造了条件 因此研究一种自动的 对用户友好的三维模型的检 索技术成为一个重要的课题 对于基于内容的3 d 模型检索系统 最根本的问题是选取恰当的特征来区别 不同的形状 以用来有效的索引相似的文件数据 3 d 模型检索方法可大致的分 为3 类 基于外形的低层方法 基于结构的高层方法 基于视角的方法 基于外形的低层方法尝试通过几何和拓扑的属性描述3 d 模型的形状 外形 可以是由单独向量组成的一些外形参数的固定数值或一系列外形参数的分布范 围 基于结构的高层方法尝试把3 d 模型分解成一系列关键部分 并提炼出这些 部分的几何关系 基于视角的方法通过一系列从不同角度的二维投影来得出三维 模型的外观 在对已有三维模型检索技术的进行系统研究的基础上 本篇论文提出了一种 基于二维投影的三维模型检索方法 用以3 d 模型检索 此方法是以常量去转化 并评价3 d 模型 并且它对于旋转是稳定的 实验数据显示 对于一些类型的三维模型 提出的基于二维投影的方法有着 良好的查全率和查准率 是行之有效的方法之一 关键词 三维模型检索 基于二维投影 特征提取 相似度计算 a b s t r a c t w i t l l 吐l ep r o l i f e r a t i o no fc o m p u t e rg r a p h i c sa j l d c o m p u t e ra n i m a t i o n s 3 d m o d e l sa r eb e c o m i n ga su b i q u i t o u sa si m a g e sa n dv i d e o f i r s t l y 伊a p m c sp r o c e s s i n gu n i th a v ee x p a n d e dt h ea p p l i c a t i o n so f3 dg r a p h i c s s e c o n d l y p o p u l a r i z e dm o d e l i n gt o o l sa n d3 ds c 甜m i n gd e v i c e sa r em a k i n ga c q u i s i t i o no f3 dm o d e l se a s i e r 甜l dl e s se x p e n s i v e c r e a t i n gal a r g es u p p l yo fp u b l i ca v a j l a b i e3 d d a l as e t s t h u t h en e e df o ra na u t o m a t i ca n du s e r f r i e n d l vc o n t e n tb a s e dm u l t i m e d i ar e t r i e v a ls y s t e mh a sc o n s e q u e n t l yb e c o m eu r g e n t t h e 研m a r yc h a l l e n g ef o rac o n t e n t b a s e d3 dm o d e lr e t r i e v a ls y s t e mi st o e x t r a c tt h ep r o p e rf e a t u r e sf o rr e p r e s e n t i n gt h ed i v e r s es h a p eo f3dm o d e l sf o r e 简c i e n ti n d e x i n go fs i i n i l a r3 dm o d e l s t e c m q u e sf o re f f e c t i v ea 1 1 de 笳c i e mc o n t e n t b a s e dr e t r i e v a lo f3 dm o d e l s l l a v et h e r e f o r eb e c o m ea ne s s e n t i a jr e s e a c ht o p i c h lt t l i sp a p e r an o v e lf e a t l l r e c a l l e d b a s e di sp r o p o s e df o r3 dm o d e l 曲i e v a l t h ed e s c r i p t o ri sh 撕a n t t o 仃a n s l a t i o na n ds c a l i n go f3 dm o d e l s 锄di ti sr o b u s tf o rr o 切t i o n a ne m c i e n ts i m i l a r i 锣m a t c l l i n gm e t h o di su s e dt 0j f i n dt h eb e s tm a t c hf o ra ni n p u tm o d e l t h ee x p e m e n t a lr c s u l t ss h o wm a tn l ep r o p o s e dr e t r i e v a lm e t h o d sa r ee f f e c t i v ea n de f j e i c i e n t k e yw o r d s 3 dm o d e lr e t r i e v a l p r o j e c t i o n b a s e d f e a t u r ee x 仃a c t i o n s i m i l a d 够 c a l c u l a t i o n i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果 据我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经 发表或撰写过的研究成果 也不包含为获得东北师范大学或其他教育机构的学位或证 书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意 学位论文作者签名 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留 使用学位论文的规定 即 东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘 允许论 文被查阅和借阅 本人授权东北师范大学可以将学位论文的全部或部分内容编入有关 数据库进行检索 可以采用影印 缩印或其它复制手段保存 汇编学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 邀 日 期 学位论文作者毕业后去向 工作单位 通讯地址 指导教师签名 缝 日 期 墨 竺 1 幅壁盈够 邮编 z 耋里2 苎乡 东北师范大学硕士学位论文 第一章绪论 1 1 研究的背景及意义 我们处在一个三维世界里 一切被我们感知的物体都以三维的形式存在 人 类的视觉不仅能够感知二维平面的信息 且具有立体三维的特性 与二维图像相 比 三维的模型所提供的视觉感知细节更多 更丰富 能够给人们带来更加详细 的信息 三维模型的研究成为了一个热点话题 是因为 1 随着三维数据获取 如数字摄像机 扫描仪 核磁共振 m a g n e t i c r e s o n a n c ei m a g i n g m r i 和3 d 激光扫描仪设备的功能越来越强 使用越来越方 便 技术手段不断进步和成熟 使三维信息获取和表达变得越来越容易 2 众多三维建模软件和工具 如3 d m a x a u t o c a d p o s e r c o r e 3 d 等 使得三维模型的设计变得简单 3 三维模型建模的专业需求越来越强 分子工程 地貌气象分析 工业 产品设计 医学建模 虚拟军事行动等 都广泛使用了三维技术 构建数字化模 型 可帮助科研人员更加直观 精确地处理各自领域问题 4 在娱乐领域 游戏 电影产业的发展 使人们已经不满足于二维画面 传统的制作方法已经成为历史 精美绚丽的三维动画随处可见 而三维建模本身 也成为了一门艺术门派 5 计算机图形学技术发展迅速 三维图形处理硬件和c p u 的速度已足够 快 而且价格便宜 使得三维数据能在微机上快速处理和显示 6 蓬勃发展的互联网技术也使人们对信息共享和处理的方式发生了根本 性的改变 网络已经成为人们获取信息的重要途径 互联网的普及 使三维模型 被更广泛地转播和共享 7 各软件 各版本的三维数据兼容化 共享化趋势 加速了模型的标准 化进程 如图1 1 所示 曼伽 潮 a 三维扫描仪 b 图形显卡 c 网络 图1 1 三维数据的普及 总之 三维模型已成为继声音 图像和视频之后的第四种多媒体数据类型 目前有数以兆计的三维模型存在 而且每天都有大量的三维模型产生和传播 可 东北师范大学硕士学位论文 以预见 在不久的将来 人们可以像使用二维图像一样使用三维模型 因此 为了从浩如烟海的信息中快速准确地找到需要的内容 人们存在着 对三维模型进行检索的迫切需求 1 2 三维模型检索系统的发展 作为新兴的领域 三维检索有重要的学术意义及应用价值 如 目前在我国 知识产权保护工作越来越受到重视 而知识产权保护的 相关工作量也越来越大 在各种专利尤其是外观设计的申请的核准 审查和批复 的过程中 都需要对各种三维模型进行比较 在工业设计过程中 三维数据可以完全提供产品的几何信息 为了实现给 料 加工 质检的自动化 需要反复快速地检索 匹配标准零件模型库 在一个 大型数据库中找到适合的三维模型 数字化地球 d i g it a le a r t h 战略的推行 数字农业 生态环境保护 风险 预警 路径规划应用中需要检索海量的三维模型标本 分子生物学基因技术中 蛋白质三维结构与功能的关系 是当前的重大科 学问题 蛋变质三维结构相似性比较则是探索生命科学奥秘的重要手段 从计算 机图形和视觉的角度来审视蛋白质三维空间结构的相似性检索 有着广阔的应用 前景 n 1 嘲 互联网上也出现了大量的三维模型库 许多网站也将三维模型作为一种数 字化商品提供给使用者 相对于二维多媒体信息的获取 三维模型的建模更加复杂 显然 搜索 共享大量的三维模型数据 在现有的模型基础上进行分类 比较 改进 把互联 网 数据库技术与三维模型建模技术相结合显然更加节约成本 如图1 2 所示 如今 人们的问题已经由 如何建造模型 转换为 如何检索所需要的现 有模型 要在一个大型数据库中找到适合的多媒体信息 检索是一种必要的技 术手段 三维模型检索的思想起源于三维模型识别 三维模型匹配以及基于内容 的模型检索 图1 2 利用已有模型创建模型 在基于内容的三维模型检索领域 国外开展得比较早1 9 9 7 1 9 9 8 年 加拿 大国家研究院 n a t i o n a lr e s e a r c hc o u n c i l 的p a q u e t 等最早对基于内容的三维 2 东北师范大学硕士学位论文 模型检索技术进行了理论和算法的研究h 1 自1 9 9 9 年以后 美国 德国 日本 等国的研究人员相继投身于这个研究 如美国的普林斯顿大学 p r i n c e t o n u n i v e r s i t y 华盛顿大学 w a s h i n g t o nu n i v e r s i t y 布朗大学 b r o w n u n i v e r s i t y 卡耐基 梅隆大学 c a r b e g i em e l l o nu n i v e r s i t y 德国的慕尼 黑大学 m u n i c hu n i v e r s i t y 波恩大学 b o n nu n i v e r s i t y 日本的i b m 东京研 究所 陆续提出了一些基于内容的领域三维模型检索系统 使三维模型检索成为 比较活跃的研究领域 但是 总的来说 目前对三维模型检索同其他的多媒体数 据检索系统一样 可以分为基于文本的检索和基于内容的检索 大多数的商用多媒体检索系统使用基于文本的关键词搜索来帮助用户寻找 想得到的多媒体文件信息 为了促进搜索的准确性 多媒体数据库的管理人员需 主要凭经验给多媒体数据注释易挑选的关键词 如果数据库非常庞大 则费时费 力却难以完成任务 此外 恰当的关键词因人而异 通常最普遍的方法是从文件 名 标题 上下文中提取关键词 如w w w g o 0 9 1 e c o m w w w b a i d u c o m 检索系 统 然而 当文件名不知所云 如a b c d b m p n i 0 0 0 1 a v i 或毫无特点 如 b a c k g r o l d w a v 掣e e n 二j p g 时 这种方法显然无效 因此 开发基于多媒体数据 内容自动而有效的检索系统已经成为一个重要的需求 上世纪末为了满足图像 视频等二维多媒体信息检索的需要 基于内容的 检索技术应运而生 很快在理论研究领域得到迅速发展 并应用于实际 基于内 容的三维模型检索方法思想起源于基于内容的图像检索 是目前比较活跃的研究 领域 但是 总体上还处于研究的初期 有许多问题有待进一步的研究 基于形状的三维模型检索是指直接根据描述对象的形状特征进行检索 它 能从数据库中查找到具有指定特征或含有特定内容的三维数据 面对日渐迫切的 需要 已经有一些网站提供对三维模型的检索与下载服务 但由于主要应用的是 文本关键字检索和目录浏览等手段 难以对复杂的模型进行充分描述 在这种情 况下 对于三维模型进行有效检索方面的研究越来越受到人们的重视 很多研究 机构开始对基于内容的三维模型检索系统进行研究 并取得了一定的进展 目前 已经开发出一些实验性的三维模型检索系统 1 3 论文组成部分介绍 在下面章节 本文在第二章对三维模型检索技术的形成与发展做了概述 在 第三章讨论了目前较常用的一些三维模型特征提取技术 在第四章 介绍了提出 的一种三维模型特征提取方法 此方法称为基于二维投影的三维模型检索方法 并对实验结果做出了分析比较 东北师范大学硕士学位论文 第二章三维模型检索技术概述 2 1 二维图像检索 物体之间形状相似性的比较 可以追溯到早期基于形状的图像检索 s h a p e b a s e di m a g er e t r i e v a l 提取图像中感兴趣物体的轮廓或区域 采用不同方法 描述其形状特征 将问题简化为形状特征的比较 借助于计算机视觉技术 人们 可以定义多种二维形状表示方法和相似性度量 二维形状表示大致分为三类 特 征向量法 f e a t u r ev e c t o ra p p r o a c h 变换形状方法 s h a p et h r o u 曲t r a n s f r o m a p p r o a c h 与关系方法 r e l a t i o n a la p p r o a c h 哺1 具体选择哪一种表示方法取 决于应用的要求 如目标形状的特征点 是否允许遮挡与形变的存在 噪声强弱 以及索引难易程度等 上述形状描述方法无法直接扩展应用在三维模型上 主要原因是他们要求为 连续曲线 或平面上区域的边界 存在标准参数化表示 对于任意三维曲面 需要 根据具体应用 恢复成一致曲面或流形曲面 得到相应曲面的参数 这样才能采 取扩展的三维形状描述 在重建过程中 需要引入人工干预 以消除模型二义性 基于形状的图像检索系统用多维特征空间距离来衡量形状相似性 在特征维 数不是很高的前提下 用索引结构组织特征向量 将加速数据库的访问 但是 由于人类的感知相似性并不等价于物体的拓扑相似性 单一特征无法完整描述物 体的形状 因而需要提取多种形状特征 给出尽可能详尽的表示 为了满足创建 索引结构的要求 需要将多特征进行降维处理 2 2 三维模型检索 如何在浩如烟海的三维模型数据库和网格中快速有效的搜索有用的 同主题 的模型 构成了三维模型检索的主要目标 与二维图像相比 三维模型有其独特 的性质 首先 三维模型空间中一个简单的物体 即可以用多边形面片 p o l y g o n s o u p 也可以用点 p o i n t 线 l i n e 和体素 v o x e l 还可以由基元物体的几 何操作和布尔操作表示 c o n s t r u c t i v es 0 1 i dg e o m e t r y 任意的三维曲面不存 在类似二维空间上弧长公式的直接参数化方法 因此无法对物体空间定义规则 的 标准的类似二维图像的采样方式 这种内在的不规则采样和三维表面存在任 意的拓扑关系 使得经典的信号处理技术 如傅立叶变换 无法直接扩展应用到 三维 其次 空间维数大小直接影响模型特征对应 参数匹配 分类其构造 优化 路径搜索等问题 其复杂度与处理时间随之显著增加 可能的模型退化现象使得 常用的几何形状特征 如面积 体积 曲率等难以计算 另一方面 三维模型检索与相机配置 光源设置和场景语义无关 且不包含 反射 阴影 遮挡 透射等效果 不需要考虑环境光照条件 相机参数 镜头校 准 自遮挡等现象 极大地简化了匹配相似物体的过程 或因为投影到地面变为 两个人 或者由于周围场景的迷惑性而凭空消失 综上所述 三维模型特征的选取 需要考虑以下三个方面 第一 特征要能 够反映物体的内在基本特性 第二 三维模型在空间中的位置 朝向和大小是任 4 东北师范大学硕士学位论文 意的 因此 所提取的特征应该与模型的平移 旋转 放缩等刚体变换无关 第 三 即便对于退化的三维模型 特征也必须是确定的 噪声的存在和网格的细分 操作不影响其稳定性和鲁棒性 2 2 1 三维模型检索系统 基于内容的三维模型目前对模型匹配的研究主要集中在对三维模型的空间 几何形状的相似性度量 有少数关于拓扑相似性匹配的研究 基于纹理或材质等 属性的相似性研究国内外尚比较少见 基于内容的三维模型检索主要分为两部分 一是离线处理 o f f l i n e 二是在线处理 o n l i n e 如图2 1 所示 离线部分 主要是对三维模型数据库中的数据进行特征提取 f e a t u r ee x t r a c t i o n 建立特 征描述符和相应的特征数据库 并建立合适的索引结构 在线部分主要是用户在 线提交查询意图并进行特征提取 相似性度量和索引 查询结果可视化等 图2 1 基于内容的三维模型检索系统框架 以下对三维模型检索系统中涉及到的几个关键技术作简单的介绍 三维模型 检索首先从模型数据中自动计算并提取三维模型的特征 如形状空间关系 材质 的颜色及纹理等 建立三维模型的多维信息索引 然后在多维特征空间中计算待 查询模型与目标模型之间的相似程度 实现对三维模型数据库的浏览和检索畸 三维模型检索系统就是试图利用反映三维模型视觉特征的内容信息自动建立特 征索引 达到检索三维模型的目的 三维模型检索技术通过对视觉特征的相似性 匹配来查找用户所要求的三维模型 这更贴近于人们在现实生活中靠直觉印象使 用信息的方式 因此 一个完整的模型检索系统包括如下几个方面 1 三维模型的特征提取由于绝大多数的三维模型是用于可视化 因此表达 三维模型的文件中往往只包含模型的几何属性 顶点坐标 法向矢量 拓扑连接 等 和外观属性 顶点颜色 纹理等 很少有适合自动匹配的高级语义特征的描 述 如何合理地描述三维模型 即特征提取 成为三维模型检索课题首先要解决的 问题 它也是三维模型检索的难点 一个理想的特征描述符s d s h a p ed e s c r i p t o r 必须满足以下几点 东北师范大学硕士学位论文 易于表达和计算 不占用太多的存储空间 适合进行相似性匹配 具有几何不变性 即对模型的平移 t r a n s l a t i o n 旋转 r o t a t i o n 缩放 s c a li n g 等具有不变性 具有拓扑不变性 即相同模型有多个拓扑表示时 特征描述符应是稳定 对模型的退化 d e g e n e r a c i e s 鲁棒 对噪音 n o i s e 不敏感 该特征必须具有唯一性 即不同类型的模型对应的特征表示应该不相同 2 相似性度量检索的目的是找出与所给模型相似的模型集合 因而对提取 得到的特征如何进行相似性匹配是检索课题中要解决的第二个问题 选择的度量 方法必须适合匹配计算 当前的研究中所采用的相似性匹配方法主要借鉴了基于 内容检索c b r c o n t e n t b a s e dr e t r i e v a l 的一些相似距离度量 3 模型分类由于三维模型资源庞大 因此需要建立一个分类数据库以便提 高模型查找效率 该分类数据库必须适合用高级语义描述 当然 对这个问题与 相似性度量方法的研究有交叉的地方 4 搜索方法的研究尽管有了分类作基础 在三维模型检索系统中 模型的 检索转化成了对高维特征矢量数据库的检索问题 因此 特征数据库中索引结构 的设计对提高检索效率非常重要 好的索引机制可以帮助检索系统在时间和存储 空间上同时得到提高 面对仍然庞大的数据库 如何快速 有效地查找出相似的 模型 在人工智能和数据库领域中仍然是一个值得探讨的问题 5 查询接口的设计 作为一个成熟的检索系统 应该拥有良好的交互性能 提供给用户方便的查询手段 通常 查询输入可以通过文本与模型相结合的方法 口3 进行 对于查询模型的输入主要有两种途径 将已知的模型作为查询输入 通 知系统检索出相似的模型 该方法的检索结果比较理想 但是要求用户必须预先 拥有某种模型的范例 因此实际使用中不够灵活 有一定的局限性 提供给用户 一个绘图接口 1 允许用户绘制所需查询模型的二维视图 由系统根据视图自动生 成三维模型 对于普通用户而言 准确地绘制一个拓扑复杂 有洞或有许多分支 的模型是比较困难的 实验表明 目前该系统在这方面的性能不是非常理想 显 然 查询接口的设计也直接影响了系统的检索性能 因此设计一个理想的查询接 口在检索系统中非常重要 6 检索性能的判断对于三维模型的检索性能的判断 主要从查全 查准 时间 资源消费等几个方面来衡量 目前的研究主要是用查全率和查准率两个参 数来对检索性能进行评判 总之 如何提取模型的特征是三维模型检索首先需要解决的关键技术 也是 目前研究比较多的一个方面 2 2 2 三维模型预处理 要真正实现基于内容的三维模型检索 非常关键的一点就是要求所提取的三 维模型特征描述具有针对平移 旋转 尺度大小以及方位变换的不变性和鲁棒性 目前 实现特征描述不变性的方法主要有三种阳 1 使用主成分分析印 p r i n c i p a lc o m p o n e n ta n a l y s i sp c a n 2 舯1 等方法对 三维模型坐标进行标准化 计算其标准化的坐标框架 然后 在此标准化坐标系 内提取相应的特征 2 将所有待比较的三维模型两两之间进行坐标对齐 这种方法由于极为费 6 东北师范大学硕士学位论文 时而很少被采用 3 定义并提取本身具有不变特性的特征描述 但实际上 这些特征描述所具有的不变性往往是不全面的 例如 s u z u k i 等人提出的形状特征只对绕坐标轴9 0 度的变换保持不变性 0 1 提出的反射对称 特征描述只具有平移和尺度不变性 1 而且 大多数这类特征的计算有时也需要 在一个归一化的坐标系内完成 因此 为了进一步提高检索的准确性 往往也需 要进行模型坐标标准化 2 2 3 三维模型特征提取 3 d 模型检索技术的关键是提取特征 在提取特征时有如下一些基本要求 1 平移不变在平移变换前后 3 d 模型的特征要保证不变 2 旋转不变在旋转变换前后 3 d 模型的特征要保证不变 3 缩放不变在缩放变换前后 3 d 模型的特征要保证不变 4 对噪声具有鲁棒性 噪声包括模型裂缝 插入三角面片 移去三角面片等 在有噪声的情况下 3 d 模型的特征要保证相似 5 对重采样和简化具有鲁棒性 在重采样和简化变换前后 3 d 模型的特征 要保证相似 从计算机图形学发展的初期开始 多边形网格就是通用的三维模型的表示方 法 尽管后来出现了更多的描述方法 但由于多边形具有形状简单 便于计算和 处理等特点 使得三维模型检索的研究者们更多以多边形网格模型作为研究对 象 一些学者在2 0 世纪8 0 年代初就对三维模型形状特征的描述进行了研究n 钔 n 鲥 但由于相关应用领域发展的滞后 当时并未引起更多关注 直至2 0 世纪末 随着硬件条件的成熟和应用需求的发展 关于三维模型特征提取方法的研究开始 受到了人们的重视 目前 三维模型特征提取方法主要分为三大类 基于外形的 低层方法 基于结构的高层方法 基于视角的方法 在下章中 将详细讨论特征提取方面的研究 2 2 4 相似性度量 模式识别 分类 聚类 检索等常常被应用在计算机视觉 机械工程 分子 生物学等领域 特征提取和相似性度量是完成这些任务的关键技术保证 如前所 述 好的特征提取方法可以保证得到精确的形状描述符 它是模型检索的关键前 提 相似性度量则是使得精确的形状描述得到正确应用的进一步保证 相似性度量的任务就是在多维特征空间中 计算用户的三维模型查询请求与 三维模型库中的模型之问的相似性距离 距离越小 说明两个模型的相似性程度 越高 反之 距离越大 说明匹配或度量的两个模型之间的相似程度越小 最终 系统根据相似性度量的距离大小返回查询结果 从而实现基于内容的模型检索 或者通过构建特定的分类器 得出模型之间的相似程度 因此 选择合适的相似 性度量方法是对进行精确匹配的进一步保证 相对于三维检索形状算子的研究而言 相似度比较方法在图像检索领域已有 了比较成熟的研究 在基于内容的三维模型检索系统中 针对不同形式的特征空间 有时需要采 用不同的适合的度量函数 目前在基于内容的三维模型检索中 主要借鉴了基于 内容的二维图像检索中所采用的一些距离度量算法 以下作一个简单的介绍 设u 为特征空间 z 少为特征向量 并且有z u y u 度量函数为 x 力 理想的度量函数必须易于计算 符合人类的形状感知 并满足以下特征n 8 1 东北师范大学硕士学位论文 正定性 p o s s e s s i v e n e s s v c y u d x o 对称性 s y 咖e t r y v x y u d x j d 少 x 自反性 r e f l e x i v i t y v 叠 u d 石 x o 严格的正定 s t r i c tp o s s e s s i v e n e s s v x 少 u x y d x y 0 三角不等式 坛 y z u d x y 口 d x z 卢 d z y 万 常用于三维模型检索领域的主要有e u c l i d e a n 距离 m a n h a t t a n 距离 马氏 距离以及h a u s d o r f f 距离等 设三维模型的特征空间为u r 任意两个三维模型的特征向量x 分别 表示为 x 扛 x z 洳 厂 弘 y z 弘 上述常用的经典的距离公式分别为 1 欧几里德距离 e u c l i d e a nd i s t a n c e d 2 鼬 歹 舻弘 2 l 该距离适用于任何维数的特征空间 而且计算简单 在很多文献中都被使用 但是这个距离的计算有一个前提 它假设了在同一特征空间的两个特征分量知 翦 彼此是独立的 这就可能导致错误的或者不够准确的匹配 为了弥补传统的欧几 里德距离的缺陷 a n k e r s t 提出了一种经过改进的度量方法 用一个相似矩阵彳 表示特征空间各个分量的相关性 如下述公式所示 谚 x y x 一 彳 x y r 口 一p 乃一弦 2 7 2 m a n h a t t a n 距离 d x y i 薯一只i f l 3 h a u s d o r f f 距离 h a u s d o r f f 距离通常用来比较不同大小的两个点集之间的相似性 其定义 为 d x y 2 恶蝥器璺d 薯 只 8 东北师范大学硕士学位论文 其中 表示两个特征点集中任意两点之间的距离 如e u c l i d e a n 距离等 m a x 为取最大值函数 m i n 为取最小值函数 4 马氏距离 m a h a l a n o b i sd i s t a n c e 马氏距离首先根据已有的特征向量集合估计出协方差矩阵 然后定义如下的 对称距离 d w 庀f 矛而 其中 a 是根据已有的特征矢量集估计出来的n n 的相似矩阵 2 2 5 相关反馈 相关反馈 r e l e v a n c ef e e d b a c k 是检索研究中的热点之一 由于没有一种形 状特征能够完整地描述模型的特性 也没有一种相似度量可以很好地模拟人的视 觉感知 已有的分类器只能在给定样本的情况下给出最佳分类结果 因此 如何 让系统在各种检索条件下都能够给出较好的结果 是一般的检索系统需要考虑的 问题 相关反馈利用机器学习理论 在系统与用户的交互过程中 主动学习用户 的判断 使系统逐步走向稳定与准确 c h e n 等人u 刀用主动学习 a c t i v el e a r n i n g 与隐藏标注 h i d d e na n n o t a t i o n s 相结合的技术 由用户对系统选择的具有最 大知识获取的模型进行标注 经过一段时间的学习 系统展现了良好的可扩展性 文献1 8 n 础允许用户对检索结果做出评价 用类似支持向量 s u p p o r tv e c t o r 的 思想 将问题归结为一个具有线性约束的最小二次优化 q u a d r a t i c o p t i m i z a t i o np r o b l e m 缩短用户指定为相关的模型之间的距离 同时增加不 相关模型的空间距离 与相似度比较类似 相关反馈也不是三维模型检索领域所独有的 在图像检 索中 它被用于缩小高层语义与底层特征之间的差异 以及弥补人类视觉感知的 主观性 呻3 2 2 6 界面设计 由于三维模型中所包含的内容信息比图像等二维媒体更加丰富 因此 基于 内容的三维模型检索系统一般具有多种检索方式啪1 主要有 1 直接提供三维模型实例作为检索请求 该模型可以是用户上载至检索服 务器的新模型文件 也可以是某次检索结果集中的任一幅三维模型使用文件上载 方式时 用户只需直接提交三维模型的文件名或u r l 地址 而使用服务器上的三 维模型实例检索时 用户可以通过缩略图浏览的方式在界面上交互选取 2 使用用户交互绘制的二维形状草图 如m i n 等人设计了一个基于用户交 互的二维草图绘制界面 由用户绘制n 个不同角度的二维草图作为查询请求在检 索时则使用三维模型在不同视角下的二维投影分别进行相似性匹配 3 使用用户交互绘制的三维草图 如i g a r a s h i 等人设计的三维草图绘制工 具t e d d y 口 但相对于二维草图绘制而言 三维草图的绘制难度较大 限制较 多 而且只能绘制相对简单的三维模型 4 基于文本关键字的检索界面 其中 文本关键字可分为两类 一类是不具 有语义属性的文本 如模型文件名称等附加信息 另一类是语义关键字 可以通 过直接输入语义文本或者目录浏览的方式提交检索请求 此外 检索界面还负责将检索结果以可视化的方式显示给用户 以进行浏览 或下一步的检索过程 一些三维检索系统中还引入了用户相关反馈的机制 为用 户提供一个交互式的评价界面 作为引入用户主观评价的手段 以提高检索精度 并实现个性化的 结合用户主观性认知的检索 如e l a d 等人n 砌提出基于学习的 9 东北师范大学硕士学位论文 检索机制以自动适应不同用户的检索要求和偏好 在检索结果显示时提供了一个 标记 相关 和 不相关 两种评价的用户反馈界面 而z h a n g 等人憎2 则进一 步对用户评价界面加以细化 提供了调节 相关 和 不相关 程度的反馈界面 2 2 7 已有系统 在基于内容的三维模型检索领域 目前己经实现并发布了一些进行理论和算 法研究的原型系统以及架构于w e b 平台上的搜索引擎等 其中 加拿大国家研究 院 c a n a d an a t i o n a lr e s e a r c hc o u n c i1 的p a q u e t 等人开发的三维模型检索系 统n e f e r t i t i 是第一个通用的三维模型检索系统 所提取的特征主要包括形状和 颜色两种 目前 比较典型的通用三维模型检索系统和搜索引擎主要有 1 美国普林斯顿大学形状检索与分析 s h a p er e t r i e v a la n da n a l y s i s g r o u p 实验室开发的三维模型搜索引擎 提供了二维草图和三维草图的绘制界 面 并具有规模最大的三维模型数据库 其中包括3 1 0 0 0 个通用的三维模型以及 多个专业的三维模型子库 如图2 2 所示 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 h t m l 嘲 i 舒 囊嗜 簟葛城0 蜘姊 0 端露to j社靳 罐鼍4l 霹 0 毋 0 茹 懈 猫黼茹茹焉篙蒜蕊蕊茹 一 匦匿誓耍受 女 i 一 一 y 一i 一 t 3 dm o d e is e a r c h n g i n e r 1 fo h 一甜c t 0 俐u d t h e d n u d i c r f 卅wc t 4 枷 iu 口跏h 一舢 j 兰 撼 警t 气4 j 葺芝黧 羔 一jj t r 茹 o i 吃 图2 2 普林斯顿大学的三维模型系统 2 美国卡耐基 梅隆大学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 实验室 开发的三维模型检索系统 同时结合了底层形状特征和语义特征进行检索 并提 供了用户相关反馈的功能 h t t p a m p e c e c m u e d u p r o j e c t s 3 d m o d e l r e t r i e v a l 3 德国莱比锡大学c g i p c o m p u t e rg r a p h i c sa n di m a g ep r o c e s s i n g 实 验室的s a u p e 和v r a n i c 等人开发的基于v r m l 模型库的在线三维模型检索系统 c c c c c o n t e n tb a s e dc 1 a s s i f i c a t i o no f3 dm o d e l sb yc a p t u r i n gs p a t i a l c h a r a c t e r i s t i c s 允许用户任意选择三维坐标轴x y 或z 进行模型坐标的标准 化 这样能使检索结果更符合用户的要求 该系统基于w e b 平台设计 用户界面 友好 如图2 3 所示 h t t d m e r k u r 0 1 i n f u n i k o n s t a n z d e c c c c 1 0 东北师范大学硕士学位论文 霪引 持一争一制淞j l 主 j jj jj i l 裂 一一t 黑w k 一一竺 j mt 罩m 曼醴j 图2 3 莱比锡大学的三维模型检索系统 4 i b m 日本东京研究院的 三维w e b 环境 研究项目中的三维几何形状 检索和分析系统 该系统的开发目的是对三维模型库进行知识管理 h t t p w w w t r l i b m c o m p r o j e c t s 3 d w e b s i m s e a r c h e h t m 5 希腊i t i 学院信息处理实验室开发的基于v r m l 模型数据库的三维模型 检索系统 除了可以在三维模型库中进行检索外 还提供了对三维模型进行两两 比较的用户界面和功能 h t t p 3 d s e a r c h i t i g r d e f a u l t p h p p a g e 3 d s e a r c h 6 荷兰u t r e c h t 大学的g i v e g e o m e t r yi m a g i n e dv i r t u a le n v i r o n m e n t 实验室研制开发的三维形状搜索引擎 主要基于高斯曲率等形状特征实现基于模 型形状的检索 h t t p w w w c s u u n l c e n t e r s g i v e i m a g i n g 3 d r e c o g 3 d m a t c h i n g h t m l 7 日本多媒体教育学院的s u z u k i 等人开发的基于w e b 的多边形模型检索系 统0 9 d e ni v 该系统同时使用模型的形状和颜色特征对v r m l 模型数据库实现检 索 以建立三维的网络教学环境 h t t p w w w n i m e a c j p m o t o f u m i o g d e n 8 美国布朗大学的l e m s l a b o r a t o r yf o re n g i n e e r i n gm a n m a c h i n e s y s t e m 实验室开发的三维模型检索系统 以二维图像为输入方式 在三维模型 库中检索出相似的三维物体模型 h t t p w w w 1 e m s b r o w n e d u v i s i o n r e s e a r c h a r e a s 3 d r e c o g o v e r v i e w h t m l 9 德国波恩大学k l e i n 和n o v o t n i 等人开发的数字图书馆系统r o d a 该系 统不对模型进行特征提取 而是通过计算不同模型之间的体积测定误差 东北师范大学硕士学位论文 v 0 1 u m e t r i ce r r o r 以及补偿轮廓 o f f s e th u l l 进行检索 h t t p w w w 1 e m s b r o w n e d u v i s i o n r e s e a r c h a r e a s 3 d r e c o g o v e r v i e w h t m l 1 0 台湾大学通讯与多媒体实验室研制的三维模型检索系统 该系统使用 m p e g 一7 标准的三维形状描述符和多视图描述符对模型特征进行描述 基于w e b 平台进行三维模型检索 如图2 4 所示 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 此外 还有一些用于专业领域的检索系统 如德国慕尼黑大学a n k e r s t 等人 研制的三维蛋白质分子模型检索系统 h t t p w w w d b s i n f o r m a t i k u n i m u e n c h e n d e f o r s c h u n g s i m i l a r i t y d e m o s p r o t e i n 以及苏格兰h e r i o t w a t t 大学开发的于w e b 的c a d 模型搜索引擎 s h a p e s i f t e r 等 h t t p w w w s h a p e s e a r c h n e t e c m i n d e x h t m l l 岫w t 量睁蝴 啦 一l 蝴蝻 潮强删nj 5 f 山 f 庸 h 十t p t dp 僦 洲r r 慵 擎1 巍锡 吟 冷 霜牝靛 警瓤 图2 4 中国台湾大学的三维模型检索系统 2 3 本章小结 三维模型检索被广泛应用于数字化图书馆 数字机和处理 分子生物学 机 械工程 医学图像和图形编辑等各个领域 以构建面向三维模型的专业化搜索引 擎为目标 有三维模型的获取 特征分析 查询处理和匹配以及用户界面四个部 分组成 由于种种原因 这个领域直到近两年才引起足够的重视 并得到了飞速发展 本章就是对三维模型检索研究领域的历史和现状作一个的概述 通过概述 指出 1 2 东北师范大学硕士学位论文 了目前存在的主要问题以及进一步研究的重点和必要性 在模型数据库中 强壮的模型特征表达和识别是最根本的问题 此外 我们 还需要很好的相似性距离度量方法 接下来的章节就是对这两个问题进行深入的 研究 东北师范大学硕士学位论文 第三章三维模型特征提取的研究 3 1 三维模型预处理 3 1 1 模型规范化处理 对三维模型规范化的目的是使所有的模型满足 1 平移不变性 2 旋转不变 性 3 缩放不变性 也就是对于任何三维模型不管进行了什么样的平移变换 旋 转变换 缩放变换 只要对其进行规范化预处理后 那么最终的大小 原点坐标 方向都一样 因此不影响特征的提取 本文使用了主成分分析法p c a p r i n c i p l e c o m p o n e n ta n a l y s i s 对三维模型进行规范化处理 1 平移不变 为了保证平移不变 首先求出三维模型的重心 将三维模型的重心作为三维 模型的新坐标原点 将三维模型平移到新的坐标原点 计算三维模型重心的公式 如下 p w p w c2f 2 仍酣 w 6 这里w 为三角形的面积 p 为点的集合 求出c 是三维模型的重心 将三维 模型的坐标原点移动到c 点 形成的点集合如下 尸 pp p c p 尸 2 旋转不变 为了保证旋转不变性 首先使用公式计算三维模型的相关矩阵m m 是个3 木3 的矩阵 b 仍 m 2 专一2 午 只卯 嵋 矩阵m 是实对称矩阵 因此特征根是3 个不同的正实数 求出特征根 以降 序排列3 个特征根 然后求出3 个特征根对应的特征向量 将每个特征向量变为 单位向量 最后3 个特征向量组成旋转矩阵r r 同样是3 牢3 的矩阵 使用旋转 矩阵r 变换三维模型 计算出新的点集 p p n 以 见 ip r p 尸 3 缩放变换 1 4 东北师范大学硕士学位论文 为了统一三维模型的大小 保证缩放不变 需要计算大小变换因子 s 板i i i 百万来变换三维模型 其中 l 仇1w j 以1w f 2 5 午 彬 o i 乃1w f 慨1w 旷等2 午 w 3 i 耽l 心 慨1w 已2 2 午 嵋 6 最后得到了平移变换响亮c 旋转变换矩阵r 大小变换因子s 将这些变 换应用到原三维模型的顶点集合p 完成规范化预处理 v 一 喾 t 肛 髯磐 善 奠拶 图3 1 模型规范化处理 3 1 2 三维模型的存储方法 1 三维文件格式介绍 a 3 d s 数据结构 3 d s 文件由许多块组成 每个块首先描述其信息类别 即块是如何组成的 块的信息类别用d