（计算机软件与理论专业论文）三维地形模型检索系统设计与实现.pdf

摘要 摘要 随着多媒体技术、计算机视觉技术和三维图形硬件的飞速发展，极大的拓 展了三维模型的应用前景，因此开展对三维模型的检索技术的研究有重大意义 和应用价值。三维地形检索也是近年来新生的一个方向，并开始被人们广泛应 用在数字地球，地理勘测等领域。 本文围绕基于三维模型的地形检索展开研究，主要工作如下： ( 1 ) 综合研究了基于内容的三维模型检索关键技术，分析了国内外三维模型 检索系统的构成，在此基础上给出了基于g i s 平台的三维地形模型检索系统的 基本结构框架。 ( 2 ) 对基于形状分布的算法进行改进，应用于三维地形特征提取上，实现了 对地形模型的特征提取 ( 3 ) 在三维地形模型的特征匹配上，本文提出了对地形模型的多特征量累进 匹配。该方法对冗余烦琐的特征量进行化简，使检索效率大大提高 ( 4 ) 实现了一个三维地形检索原型系统，验证了改进的算法；具有良好的 扩展性，实现了高速、有效的三维地形模型检索。 本研究课题源自国家计委科委项目“综合风险防范关键技术研究与实现” 项目编号( 2 0 0 6 b a d 2 0 8 0 2 ) 关键词：三维模型，三维模型检索，三维地形模型检索，特征提取，相似度计 算 a b s t r a c t a b s t r a c t w i t hi m p r o v e dd i g i t a lm u l t i m e d i at e c h n o l o g y , c o m p u t e rv i s i o nt h e o r ya n d g r a p h i 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 t h e t e c l m o l o g yo f3 dm o d e lr e t r i e v a li sb e c o m i n gm o r ea n dm o r en e c e s s a r y 3 dt e r r a i n r e t r i e v a lw h i c hi sa p p f i e dt o d i g i t a lw o r l da n dg e o g r a p h yw i l lb e c o m ean e w a p p r o a c hi nt h o s ey e a r s t h ef o l l o w i n gi st h em a i nt a s ko f t h i sa r t i c l e ： ( 1 ) s t u d yt h ek e yr e t r i e v a lt e c h n i q u eb a s e do i lc o n t e n t so f3 dm o d e l ，a n a l y z et h e s t r u c t u r eo f3 dm o d e lr e t r i e v a ls y s t e mw h i c hi se x c e l l e n ta th o m ea n da b r o a d t h e nd e s i g nt h e3 dt e r r a i nm o d e lr e t r i e v a ls y s t e mb a s e do ng i s ( 2 ) a p p l et h ei m p r o v e ds h a p ed i s t r i b u t ea l g o r i t h mt o3 1 ) t e r r a i nf e a t u r ee x t r a c t i o n ( 3 ) a p p l et h el o da l g o r i t h mt o f e a t u r e se x t r a c t i o ni no r d e rt oi m p r o v et h e e f f e c t i v e n e s s ( 4 ) t h i sp a p e rd e s i g n sa3 dt e r r a i nr e t r i e v a ls y s t e m - - m e a s u r e 3 da st h et e s tb e df o r r e t r i e v a la l g o r i t h m s , w h i c hi sa ne x p e r i m e n t a lf r a m es y s t e m t h e r e f o r e , s o m ek e y i s s u e so f3 dt e r r a i nm o d e lr e t r i e v a lf o rf u t u r er e s e a r c ha l ea l s od i s c u s s e da tt h ee n d o f t h i st h e s i s t h er e s e a r c hw o r ki ss u p p o r t e db yk e yn a t i o n a ls c i e n c ea n dt e c h n o l o g yp r o j e c t o f t h e ”l l t hf i v e y e a r p l a n - k e yt e c h n o l o g yr e s e a r c ha n dd e m o n s t r a t i o no f i n t e g r a t e di b s kg u a r d i a n s ”( n o 2 0 0 6 b a d 2 0 8 0 2 ) 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 ，3 dt e r r a i nm o d e lr e t r i e v a l , f e a t u r e e x t r a c t i o n , s i m i l a r i t yc a l c u l a t i o n 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期 间论文工作的知识产权单位属于西北大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本 学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存和汇编本学位论文。同时，本人保证，毕业后结合学位论 文研究课题再撰写的文章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 学位沦文作者签名： i 堡塾指导教师签名避 孙。1 年6 月1 1 日枷年么月l 日 7 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包 含其他人已经发表或撰写过的研究成果，也不包含为获得西北大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 享步悫 孙0 1 年占月l z 日 第一章绪论 第一章绪论 1 1 研究背景 近年来，计算机信息检索技术已成为信息采集传播的重要方法和手段之一。 随着i n t e r n e t 的发展，信息处理从传统的手动模式向自动化模式转变。信息检 索的对象也已经从单一的文本信息发展为二维图像等多媒体信息以及更为真实 丰富的三维模型和三维场景等虚拟媒体信息转变。人们对信息检索工具的依赖 日益迫切，并且规模与复杂性日益加强。2 0 世纪9 0 年代初，为适应图像、视频 等二维多媒体信息检索的需要，基于内容的多媒体检索技术“。1 应运而生，并很 快在理论研究和实际应用中得到迅速发展。 在科学技术领域，测定蛋白质的三维结构，对探索生命过程最根本问题是十 分有意义的。三维几何建模技术，特别是对大分子空间结构的描述，在生命科学 基础研究领域，具有良好的应用前景在文物保护方面，三维建模也发挥着重要 的作用。对于一些珍贵的文物，三维模型的重构，可以避免由于年代久远面临着 风化，碎裂，受潮变形而造成的缺失在医学方面，人脑的虚拟内窥镜技术和计 算机辅助颅像重合计算的研究上取得了显著的成果。这些应用均促进了三维几何 结构的描述，可视化技术和人机交互等三维视觉计算领域的研究 三维地形的分类检索技术也是近年来新生的一个方向，并开始被人们广泛应 用。现在，数字地球的范畴十分广泛，数字水文也是其中十分重要的组成部分 数字地球中开发的信息获取技术，处理技术，通讯技术，存储和管理技术，网络 技术，数字成品技术，信息挖掘等为水文科学迈向新台阶创造了极有利的技术条 件。本文提出的三维地形分类检索系统，是我所综合风险项目的检索子系统，该 系统实现了对地形模型的读取，特征提取，特征匹配和准确定位显示，对专家风 险评估起到辅助性作用 三维形状分析的研究主要集中在计算机视觉与图形学领域，在互联网上， 也涌现出越来越多的三维模型库3 】c a d 、化学、分子生学和古生物学等各个 方面。其主要研究内容包括： 识别：判断物体是否存在，以及其在场景数据库中的位置。 检索：寻找与查询例子形状类似的物体，并按照相似程度大小进行排列 1 第一苹绪论 分类：根据物体形状，将其归并到预先设定的类别中。这些类别可以由自 动分类技术产生，也可以手工指定。分类依据视具体的应用而定。对于简 单的几何形状，根据其形状可以分为球形，长方形平行六面体等；对于机械 c a d 模型，则需要根据功能对模型进行划分。 合并：即所谓的用例子进行建模。这时候的设计不再是一个从无到有的过 程。已有的例子就像是积木，而设计者的工作便是如何利用这些积木，搭 出自己需要的效果。形状分析则是设计者与积木之间的一座桥梁，帮助快 速、准确地找到目标。 这些问题同时也是计算机视觉和模式识别领域所探讨和关注的相信这些 领域的研究，必将进一步推动三维形状分析的发展。因此，如何有效地对三维 模型及其场景进行浏览和检索，开始吸引众多研究者的注意，并日益成为一个 研究热点伽在m p e g7 国际标准中也已规定，与之相关的媒体数据除包括二维 媒体信息外，还包括三维模型及三维场景等虚拟媒体信息描述接口标准 m p e c , - 7 正在走向成熟和实用，而在3 d 模型检索中，基于文本的检索还有很大的 局限性，效率不高。基于内容的检索技术因直接面向模型本身，有更大的通用性 而发展较快。基于内容的检索可以进一步分成：( 1 ) 基于特征的检索( 全局，局部 特征，空间映射旧) ：( 2 ) 基于图表示的检索( 模型，骨架坼”) ：( 3 ) 其他的一些检索 技术如：鲰”，切片，分块“1 1 ，加权点集n 玎 1 2 本课题主要研究内容 本课题的主要研究目的是在对三维模型检索算法进行研究的基础上，提出 三维地形模型检索的方法由于地形模型的特殊性，现有的各种算法对三维地 形检索都有自己的长处和不足，例如：基于统计的方法其优点是对模型要求不 高、计算不复杂、易理解、大多数满足几何不变性和对噪声不敏感，但是这种 方法全局特征替代了几何特征，丢失了位置信息，这种算法适用于全局匹配。 基于骨架提取的方法优点是其的不变性，缺点是对模型要求高，计算量大、对 边界噪声敏感，因此适合局部匹配因此本课题算法研究应该满足以下要求： ( 1 ) 对三维地形信息的描述和分辨能力强； ( 2 ) 计算速度快； ( 3 ) 易存储，特征维数足够低； 2 第一苹绪论 ( 4 ) 易索引，能方便地组织索引结构，以加快检索过程； ( 5 ) 具有几何变换无关性，并对形变和噪声具有一定程度的鲁棒性； ( 6 ) 独立于具体的三维地形模型表示方法、模型的细化方式、模型的种类 和拓扑关系等。 通过研究各种算法，本课题确定了以下几个研究重点： ( 1 ) 对现有的基于形状的三维模型检索算法进行研究讨论，提出针对三维地 形模型的检索算法。实现的算法要具有快速、鲁棒性高、支持多种文件格 式的特性 ( 2 ) 选择合适的相似性度量算法，从而更好的提高检索的准确度。 ( 3 ) 实现一个支持多种文件格式的三维地形检索原型系统。 1 3 文章的组织结构 围绕以上主题，本文主要分为六个章节： 第一章首先介绍研究背景，讨论三维模型检索的应用前景，目前3 d 地形检 索的算法以及本文的主要工作 第二章综述了三维形状分析技术，对形状描述、相似度匹配、相关反馈、 界面设计、系统框架等各方面内容进行总结，并分析了典型的三维模型检索系 统的基本架构 第三章三维地形的特征提取技术，主要分为两个部分，首先对地形数据进 行分析，接着阐述了空域检索和频域检索的基本理论。 第四章三维地形的相似性度量技术。在阐述了几何矩阵模型和集合理论模 型的基础上，提出了对三维地形模型的多特征量的累进匹配。最后总结给出了 检索的评价方法。 第五章阐述了3 d 地形检索的算法流程，介绍了本系统提出的改进算法和基 于小波的检索算法 第六章介绍了整个系统功能结构，部分算法和实现工作。 第七章结论与展望。对本文进行总结，并对今后三维检索技术的研究方及 三维地形检索方面进行了展望 3 第二章相关的工作研究 第二章相关工作研究 2 1 基于内容的检索技术 基于内容的检索技术c b i r 所指的内容包括图像的颜色，形状，纹理和语意 等特征其中，图像的颜色，形状，纹理特征，具有相对直观的特点，语义内 容具有相对主观抽象的特点。虽然人们偏爱语意查询，但是这种查询方式的完 全智能化目前还不可能实现 基于内容的图像检索技术主要包括：( 1 ) 接口技术，即查询者与检索系统之 间的交互方式查询者以何种方式提出查询的内容，检索系统如何解释接受， 并给出查找结果。( 2 ) 匹配技术，即图像相似性的度量准则。( 3 ) 数据库技术， 包括图像存储的技术，图像的查找技术，快捷、有效的遍历图像库中的每一副 图像，找出所需要的图像。( 4 ) 评价技术，对不同的检索系统，评价系统性能 的标准根据检索的速度，检索的返回库，检索的精度等，来评价系统的优劣。 基于内容的图像检索从提出以来，技术上各种新的方法就层出不穷，国内 外许多机构都在进行相关的研究工作，并取得了不少的成就。现在i n t e r n e t 网 上已经有许多关于基于内容图像检索的原形系统，最为著名的系统有：i b m 的 q b i c 系统，美国哥伦比亚大学的v i s u a l s e e k 图像查询系统以及v i r a g e 公司开 发的v i r a g e 系统，并在一些领域得到了应用。除此之外还有许多优秀的原型系 统，如u i u c 开发的姒r s 系统，w i t 多媒体实验室开发的p h o t o b o o k 系统，u c b e r k e l e y 开发的c h a b o t 系统等。国内的一些研究单位，如中科院自动化所国 家模式识别实验室，清华大学，上海交通大学，复旦大学等，也进行了研究并 开发了一些实验系统。 2 2 三维模型检索 2 2 1 三维模型检索系统 3 d 模型检索技术经过近几年的发展，己经取得了一些研究成果，有些研究 人员已经开发出3 d 模型检索系统。这些系统还只是一些实验系统，到目前为止， 还没有真正投入商业运行的3 d 模型检索系统。这些实验系统的系统结构大体相 似，一般都是基于w e b 的这些检索系统的大多数都只是为了验证检索技术的 而提供比较简单的检索界面，这些检索界面还不能满足用户的要求，用户不能 4 第二章相关的工作研究 方便地通过检索界面表达检索要求。只有个别检索系统的检索界面可以让用户 比较容易地表达检索要求，比较典型的是普林斯顿大学的3 d 模型搜索引擎和台 湾大学的3 d 模型搜索引擎。总的来讲，这些实验系统的检索界面提供的检索方 式有四种：( 1 ) 关键词检索；( 2 ) 手工绘制2 d 草图检索；( 3 ) 手工绘制3 d 模 型；( 4 ) 3 d 模型示例检索。关键词检索是基于文本的检索方式，后面三种都是 基于内容的检索方式。现有的大多数检索系统都只提供3 d 模型示例检索，这种 检索方式要求用户提供一个示例3 d 模型，这个3 d 模型可以是来自系统数据库， 也可以是用户自己上载的模型文件手工绘制2 d 草图检索和手工绘制3 d 模型 检索的检索方式提供了比较友好的检索界面，用户可以通过绘制2 d 图像或3 d 模型表达检索要求。 普林斯顿大学的3 d 模型搜索引擎被认为是一个很优秀的3 d 模型检索系统， 现在共有5 2 0 0 0 个3 d 模型，3 d 模型范围非常广泛，其中包括3 1 0 0 0 个从i n t e r n e t 网上下载的免费3 d 模型，5 0 0 0 个商业3 d 模型，1 6 0 0 0 个蛋白质3 d 模型。采用 基于w e b 的搜索引擎，它的系统结构如图2 1 所示 辫啼 圄氰 u s e r ： 图2 1 系统结构图 该搜索引擎提供了很友好的检索界面，可以使用四种检索方式检索： ( 1 ) 文本和2 d 草图方式这种方式可以分别输入检索关键词和绘制1 个、 2 个或者3 个简单的平面轮廓草图进行检索，或者将两者结合起来检索。提供 的画板只能绘制线条。用户使用鼠标左键绘制线条右键擦除线条。另外可以 使用“c l e a r ”按钮清除整个画板内容，“u n d o ”按钮回退。 5 苎三兰塑差竺三堡至塞 ( 2 ) 文本和3 d 草图方式。这种方式可以分别输入检索关键词和绘制3 d 轮廓 草图进行检索，或者将两者结合起来检索绘制3 d 轮廓草图使用的是t e d d y 系 统“”，这个j a v a a p p l e t 程序可以使用鼠标在平面画板上绘制自由形状的3 d 模 型。 ( 3 ) 文件比较方式。这种方式允许用户上载一个3 d 模型示例文件进行检索。 支持的3 d 模型文件格式有v r m l2 0 ( w r l ) ，p l y ( p l y ) ，w a v e f r o n t ( o b j ) ， a u t o c a d ( d x f ) ，u n i g r a p h i c s ( u g ) ，d e c ( o 均、p e r s i s t e n c eo f v i s i o n ( p o v ) 等格式的文件。 ( 4 ) 找相似形状。这种方式可以从初步检索的结果中选择一个3 d 模型作为 示例3 d 模型，系统返回与示例3 d 模型形状相似的3 d 模型。每次搜索引擎都返 回1 0 0 个最相似的3 d 模型的图片用户可以通过点击图片以获取3 d 模型的更 详细信息。 三维模型检索首先从模型数据中自动计算并提取三维模型的特征，如形状、 空间关系、材质的颜色及纹理等，建立三维模型的多维信息索引，然后在多维特 征空间中计算待查询模型与目标模型之间的相似程度，实现对三维模型数据库 的浏览和检索 1 1 j o 三维模型检索系统就是试图利用反映三维模型视觉特征的内 容信息自动建立特征索引，达到检索三维模型的目的。三维模型检索技术通过 对视觉特征的相似性匹配来查找用户所要求的三维模型，这更贴近于人们在现 实生活中靠直觉印象使用信息的方式 2 2 2 三维模型预处理 3 d 模型检索技术包含对3 d 模型特征提取，相似度计算，数据库搜索技术实 际上在对3 d 模型提取特征之前往往需要对3 d 模型进行一些预处理算法后，才能对 3 d 模型进行特征提取要真正实现基于内容的三维模型检索，非常关键的一点就 是要求所提取的三维模型特征描述具有针对平移、旋转、尺度大小以及方位变换 的不变性和鲁棒性目前，实现特征描述不变性的方法主要有三种“”：( 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 等人提出的反射对称特征描述只具有平移和尺度不变性“”。而且，大多 6 苎三童塑茎塑三堡堡塞 数这类特征的计算有时也需要在一个归一化的坐标系内完成。因此，为了进一步 提高检索的准确性，往需要首先进行模型坐标标准化。 模型坐标归一化 三维模型的性质决定了它的特征描述需要满足平移，旋转，缩放等刚体不 变性。一般的，存在三类方法满足这个要求：一是特征本身具有刚体不变性， 因此需要设计具有良好属性的模型特征：和是在计算模型特征前，将物体规一 化至一个标准的参考系，不变性不是由特征本身满足，而是由模型校准这一步 骤保证；二是将所有待比较的三维模型两两之间进行坐标对齐。一个完整的模 型坐标规范化由平移，旋转和缩放组成： d = j r ( d d 公式( 2 1 ) 首先平移物体使其质心与坐标原点重合，接着将物体旋转至标准坐标系， 最后所放物体至标准单元大小。常用的三维模型归一化方法建立在物体惯性矩 啪2 0 的定义之上，通过特征值分解或者奇异值分解得到旋转矩阵由于分解得到 的坐标轴存在两个可能的取值方向，需要引入约束条件，保证结果的唯一性 一般地，可以取模型质量分布较为集中的部分作为正半轴如果通过限制高阶 矩的符号来确定坐标轴的朝向，则需注意约束条件的个数。 缩放系数的选取规则也是不尽相同，一般的，令变换后物体表面的点到物 体质心的最大距离或平均距离嘲为一常数。 在某些情况下，还需要进行翻转变换，以保证互为镜面映像的三维模型在 表示方式上的同一性伽。由于惯性矩的定义是建立在连续表面点的基础上，当 取三维模型的顶点作为分析对象，则需要考虑网格的细分对估算的影响 p a q u e t 啪j 等用每个三角形的质心代替相应的顶点；或者通过为三维模型的各个 顶点设定合适的权值，生成一个加权的顶点集合的方法来解决这个问题。作为 对基于顶点方法的一个改进，假设每个多边形表面具有均匀的密度分布，利用 o n t a - c a r l o 方法模拟每个多边形上的点集，并令点集的大小与多边形面积成 正比，则可以简化惯性矩的计算州 主成分分析( p 队) ： 7 第二章相关的工作研究 对三维模型规范化的目的是使所有的模型满足( 1 ) 平移不变性；( 2 ) 旋转 不变性；( 3 ) 缩放不变性。也就是对于任何三维模型不管进行了什么样的平移 变换，旋转变换，缩放变换，对称变换，只要对其进行规范化预处理后，那么 最终的大小，原点坐标，方向都一样，因此不影响特征的提取。如图2 2 为模 型规范化处理后显示 ( i ) 平移不变 为了保征平移不变，首先求出三维模型的重心，将三维模型的重，t l , 作为三 维模型的新坐标原点，将三维模型平移到新的坐标原点。计算三维模型重心的 公式如下。 b m a m 弘蔷2 午卯 馘 2 这里r 为三角形的面积，p 为点的集合，求出c 是三维模型的重心，将三 维模型的坐标原点移动到c 点，形成的点集合p = p i p = p - c , p p 。 ( 2 ) 旋转不变 为了保证旋转不变性，首先使用公式计算三维模型的相关矩阵m ，m 是个3 * 3 的矩阵。 tp p i 7 仇 肛专 2 上l _ 易卯 m j 公式( 2 3 ) 矩阵m 是实对称矩阵，因此特征根是3 个不同的正实数。求出特征根，以降 序排列3 个特征根。然后求出3 个特征根对应的特征向量，将每个特征向量变 为单位向量，最后3 个特征向量组成旋转矩阵r ，r 同样是3 * 3 的矩阵。使用旋 转矩阵r 变换三维模型，计算出新的点集p = p = ( 以，风，b ) i p = r ，p p ) 。 ( 3 ) 缩放变换 为了统一三维模型的大小，保证缩放不变，需要计算大小变换因子 8 第二章相关的工作研究 s = 止虿i 手五万万来变换三维模型。其中， i 儿i m i 如i m 文2 等2 午 o i 岛i i 办i m 0 2 2 午 m o 挂n i 如l i 如i 屯。 2 午 m o 公式( 2 4 ) 公式( 2 5 ) 公式( 2 6 ) 最后得到了平移变换响亮c 、旋转变换矩阵r 、大小变换因子s 。将这些变 换应用到原三维模型的顶点集合p 完成规范化预处理，如图2 2 图2 2 模型规范化处理 细分算法： 有的特征提取方法在提取3 d 模型特征的时候需要将3 d 模型细分，即用更 小的三角面片来表示3 d 模型。由于本文所提出的细分算法的目的是为了提取 3 d 模型的表面积分布特征，因此这里的细分算法比较简单，只是将3 d 模型的 每个三角面片细分为n y j 、1 个等面积的小三角面片具体算法是：将三角面片的每 条边等分为n 段，然后通过等分点画出平行于三条边的等分线，这些等分线将 三角面片等分为面积相等的n 】【n 个小三角面片。如图2 3 ，三角面片a b c 被细 9 第二章相关的工作研究 分为4 x 4 个面积相等的小三角面片。图2 4 是对一个三角面片的细分结果。图 2 5 是对兔子模型的实际细分结果 c 图2 3 三角面片细分算法 a 一个三角面片 b 细分结果 图2 4 一个三角面片的细分 a 兔子模型b 细分结果 图2 5 兔子模型的细分 均匀采样点算法： 在对3 d 模型提取特征的时候，有的算法需要将3 d 模型的面片模型转换成 点云模型，因此需要在3 d 模型的表面均匀采样点假设3 d 模型是三角面片模 型，对模型的每个三角面片按下面的方法进行均匀采样。 首先求出三角形的任意一条边上的高，比如a c 边上的高b d ，将高b d 等 】0 第二章相关的工作研究 份成1 1 段。一= f b d s e p l ，s t e p 是采样点之间的距离。通过高b d 的n - 2 个等 分点，做平行于a c 的等分线，可以将a b 和b c 等分为n 段。对每条等分线包含 在三角形内的部分进行等距离采样，这些等分线包括底边a c 和顶点b ( 可以认 为是长度为0 的边) 比如等分线a i d l 包含在三角形内的部分为a l c l ，所以只 对a i c i 等距离采样。对线段采样点的时候，同样是将线段的长度等分为长度 为s t e p 的线段，将每个等分点作为采样点。比如对线段a i c i 采样，将其等分 为m 段，m = f a l s t e p l ，将等分点和端点a l ，c 1 作为线段a l c l 上的采样点。 采样算法如图2 6 所示图2 7 是一个三角面片的采样结果，可以看出不同的 步长s t e p ，得到的采样点的密度不同，但采样点在三角面片上分布都很均匀。 图2 6 三角面片采样 b 翻日吨0 0 。誊誊j i 正s k p - o o l 图2 7 三角面片的均匀采样 图2 8 是对兔子模式的均匀采样情况，可以看出应用这个均匀采样点算法 酣一 角 三 十 ： 一 1 第二章相关的工作研究 能够在3 d 模型表面得到均匀的点。 免予的面片模垄 ks t e v o o j 时的点云模型 as t e p - o 0 5 时的点云援型 正s t e p = o o g 时的点云模垂 图2 8 兔子模型的均匀采样 2 2 3 特征提取 从计算机图形学发展的初期开始，多边形网格就是通用的三维模型的表示 方法。尽管后来出现了更多的描述方法，但由于多边形具有形状简单、便于计算 和处理等特点，使得三维模型检索的研究者们更多的以多边形网格模型作为研 究对象文献嘶嘲在2 0 世纪8 0 年代初就对三维模型形状特征的描述进行了研 究，但由于相关应用领域发展的滞后，当时并未引起更多的关注，直至2 0 世纪 末，随着硬件条件的成熟和应用需求的发展，关于三维模型特征提取方法的研 究开始受到了人们的重视。目前，三维模型特征提取方法主要分为三大类：统 计特征提取方法；骨架提取方法；基于几何学的提取方法。 1 2 第二章相关的工作研究 ( 1 ) 统计特征提取方法： 对一个三维模型进行参数化本身就是一个很复杂的问题，同时由于三维表 面有任意的拓扑，使得一些在二维图像被使用的方法( 如傅里叶变换) 无法直接 应用在三维领域很多模型虽然满足了视觉效果，但是大多数是退化的、不完 整的，最经典的如u t a h t e a p o t ，是一个无底的茶壶；又如s t a n f o r db u n n y 是 一个带有几个洞的兔子对这些模型进行有意义的几何特征和形状信号的计算 是很困难的，因此从统计学的观点出发，寻找出有意义的统计特征成了研究人 员首先考虑的方法。目前的研究中主要使用了如下统计特征：模型顶点间的几 何关系( 距离、角度、法线方向关系等) ，模型顶点的曲率分布特征，模型顶点 的各阶统计矩以及各类变换特征系数等。z a h a r i a 等提出用3 d s s d ( 3 d s h a p es p e c t r u md e s c r i p 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 对几何转换和比例缩放具有不变性，对一些易见的、显著的、有 突起的特征，如c o n v e x i t y ，c o n c a v i t y ，r u t ，r i d g e ，s a d d l e 描述准确。但该 方法对模型的拓扑很敏感，对任意网格描述之前需进行规范化的预处理，预处理 的过程较复杂且涉及到很多方面( 如拓扑表示的不唯一性、网格的不规则采样， 非定向网格，退化网格等均需经过预处理) ，因此该方法并不通用。 o h b u c h i 等嘲在假设模型的质量分布是均匀的前提下，计算了模型相对三 个主轴的惯量矩和模型表面顶点对三个主轴的距离分布由于模型对轴会有一 些小的变形，为了减少由此带来的影响，文献嘲采用了一种叠盖分析窗口的方 法，增加算法对这种变形的鲁棒性。这种方法计算不复杂，对一些退化的模型 也适用，但实验表明其对于具有旋转对称特征的模型效果更好些，而对其他特 征的模型实验结果并不理想，因此该方法局限性比较大文献在假设三维模 型可以用三维等高线描述的前提下，用傅里叶系数作为特征描述符显然，这 种方法无法从理论和实验上证明等高线就是三维模型的理想特征描述符，因此 还需进一步研究 1 3 第二章相关的工作研究 ( 2 ) 骨架提取方法： 在医学的虚拟内窥镜手术中，人们致力于研究如何提取管状器官的中轴线， a m e n t a 等 3 1 ，3 2 首先计算出模型的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 图，增加了计算 量，影响对模型特征的精确描述。因此，这种方法的实用性有待进一步研究。 与中轴变换的思想相似，文献如采用基于参数控制的瘦化算法对模型进行骨 架提取，适合任何以体素描述的三维模型。该算法首先计算出模型的骨架节点， 然后通过各节点构造出相应的骨架图形，即一个有向的非循环图。以此作为模 型的特征描述，不仅适合全局匹配，也可进行局部匹配该算法中骨架节点为 模型局部的中心点，通过瘦化参数控制节点的密度，因此参数直接影响了模型 骨架的提取质量。瘦化算法对噪声异常敏感，小的扰动会导致错误的骨架提取 同时，由于需要对每个体索的距离转换值进行递归计算和比较，因此这种算法 的计算量很大。而关于如何选择瘦化参数文献随删中没有给出理论的描述，这 也是该算法的一个遗憾。 ( 3 ) 基于几何学的提取方法： v r a n i c 等人口钉提出一种基于射线( r a yb a s e d ) 的形状特征描述方法以坐 标原点为起点，沿一组等间距的空间方向矢量作射线，计算与其相交的三角形面 片与坐标原点的最大距离作为特征值。h e c z k o 等人嘲提出一种基于体结构的 形状特征提取方法。将每个单元网格所包围的网格面片面积作为特征元素 s u z u k i 咖则提出一种基于三维模型顶点等价类的特征提取方法首先，计算每 个网格单元中的顶点( 或表面法向量) 数目，将网格单元划分为一系列等价类。最 后，以每个等价类中归一化的顶点个数为特征向量t a n g e l d e r 等人m 3 描述了 一种使用加权点集合( w e i g h t e dp o i n t s e t s ) 表示多面体模型的方法，用每个网 格单元中的代表点组成加权点集合作为形状特征b i n f o r d t 2 l 使用一种称为广 义柱( g e n e r a l i z e dc y l i n d e r s ) 的参数模型实现三维模型的特征提取，该模型由 一组基于样条曲线的空间轴及定义在该轴上的截面连接函数组成。c i c i r e l l o 1 4 第二章相关的工作研究 等人和m c w h e r t e r 等人嗍通过提取三维图形中的几何学和工程学上的特征 来进行相似性估计z h a n g 等人1 和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 等人基于三维离散傅立叶变换 的方法提取三维模型的特征由于绝大多数的模型是不严格的，如i n t e r n e t 上的模型通常是退化的、松散的多边形集合，所以该方法的应用受到很大的限 制。 ( 4 ) 其他提取方法： 除了形状特征以外，还可以利用三维模型的表面属性，包括颜色、反射系 数和纹理等进行检索。s u z u k i 等人实现了一种基于三维模型材质颜色的特征提 取方法s u z u k i m j 等人认为，材质颜色在很大程度上影响着三维模型的外观属 性，对于三维模型的颜色而言，其复杂之处在于要考虑光照模型的影响，如环 境光( a m b i e n tl i g h t ) 、漫射光( d i f f u s el i g h t ) 、反光系数( s h i n i n e s sv a l u e ) 以及透明系数( t r a n s p a r e n c yv a l u e ) 等等随着光照模型的变化，可以为三 维模型表面产生大量的颜色种类，以此为基础，s u z u k i 等人提出一种基于用户 输入的交互式三维模型颜色检索方法，将每一种材质颜色表示为光照模型中若 干个光照参数的综合值，基于一个有用户主观评价生成的颜色训练集，使用多 元回归分析方法对光照模型进行预测。实验表明，该方法能较好的反映用户对 于模型外表面颜色的主观认知特性但由于三维模型表面属性的多样性和复杂 性，表面属性特征提取的研究至今并未得到充分发展。 2 2 4 相似度比较 相对于三维检索形状算子的研究而言，相似度比较方法在图像检索领域已 有了比较成熟的研究一般的，当特征位于二维笛卡尔空间，满足三角不等式 的范数是一种自然的度量方式。加权距离考虑各个特征分量之间的相对 权重，弹性形变距离( e l a s t i cm a t c h i n gd i s t a n c e ) 嘲允许相比较模型对应 部位之间的相对尺度存在不一致，它们提供了。范数所不具备的灵活性j 此外； 如果特征是用直方图形式所表示的一个分布，距离及b h a t t a c h a r y y a 距离都 1 5 第二苹相关的工作研冗 是较好的选择。 2 2 5 相关反馈 相关反馈( r e l e v a n c ef e e d b a c k ) 是检索研究的热点之一。由于没有一种 形状特征能够完整地描述模型的特性，也没有一种相似性度量可以很好的模拟 人的视觉感知，已有的分类器只能在给定样本的情况下给出最佳分类结果，因 此，如何让系统在各种检索条件下都能够给出较好的结果，是一般的检索系统 需要考虑的问题。相关反馈的目标是从用户与查询系统的实际交互过程中进行 学习，发现并捕捉用户的实际查询意图，并以此修正系统的查询策略，从而得 到用户实际需求尽可能相吻合的查询结果；由于相关反馈可以实时的修改系统 的查询策略，从而为检索系统增加了自适应功能。 2 3 本章小结 一个完整的模型检索系统主要包括如下几个方面： ( 1 ) 模型的预处理技术。其中包括坐标的归一化，规范化算法，细分化算法， 均匀采样点算法，都是常用的模型预处理算法。 ( 2 ) 三维模型的特征提取是三维模型检索技术中的重点难点对于基于内 容的模型检索来说，一个理想的特征描述符s i ) ( s h a p ed e s c r i p t o r ) 必须满足： 易于表达和计算；不占用太多的存储空间；适合进行相似性匹配；具有几何不 变性，即对模型的平移、旋转、缩放等具有不变性；具有拓扑不变性，即当相同 模型有多个拓扑表示时，s d 应是稳定的；s d 对模型的绝大多数处理，如子分、 模型简化、噪声增减、变形等是鲁棒的；s d 必须具有唯一性，即不同类型的模 型对应的特征表示应该不相同 ( 3 ) 相似性度量技术检索的目的是找出与所给模型相似的模型集合，因而 对提取得到的特征如何进行相似性匹配是检索课题中要解决的第二个问题，选 择的度量方法必须适合匹配计算。 ( 4 ) 搜索策略。尽管有了分类作基础，但面对仍然庞大的数据库，如何快速、 有效地查找出相似的模型也是一个关键部分。 ( 5 ) 查询接口。作为一个成熟的检索系统，应该拥有良好的交互性能，提供 给用户方便的查询手段。 1 6 第二章相关的工作研究 ( 6 ) 检索性能的评价。对于三维模型的检索性能的判断，主要从查全、查准、 查全率一查准率曲线，时间、资源消费等几个方面来衡量目前的研究主要是用 查全率和查准率两个参数来对检索性能进行评判。 1 7 第三章三维地形的特征提取 第三章三维地形的特征提取 对3 d 地形模型进行预处理后，我们对已经三角网格化的模型的每个三角面 片做特征提取。本章重点介绍高程地形模型数据存储和对3 0 模型特征提取的方 法。 3 1 三维地形模型的存储方法 3 1 1 高程地形模型( d t m ) 数据分析 数字地面模型包括平面和地形起伏两种数据，并且从其本身导出的数据如坡 度、坡向、可视性等也包含在其中m i l l e r 和l a f l a m e 在1 9 5 8 年给出d t m 如 下的定义： 数字地面模型是利用一个任意坐标场中大量选择的己知x ，y ，z 的坐标点 对连续地面的一个简单的统计表示，或者说，i ) t m 就是地形表面简单的数字表 示 从数学的角度，可以用下述二维函数系列取值的有序集合来概括地表示数 字地面模型的丰富内容和多样形式： 。 k ，= 厂i 盯，y ，) = 1 ，2 ，3 ，m ；p = 1 ，2 3 ，h ) 式中，k 为第p 号地面点( 可以是单一的点，但般是某点及其微小领域所划定 的一个地表面元) 上的第k 类地面特性信息的取值。u ，y ，为第p 号地面点的 二维坐标，可以是采用任一地图投影的平面坐标，或者是经纬度和矩阵的行列 号等；m ( m 大于等于1 ) 为地面特性信息类型的数目：n 为地面点的个数 当上述函数的定义域为二维地理空间上的面域、线段、或网络时，n 趋向正无 穷大：当定义域为离散点集时，1 1 一般为有限正整数。 总之，数字高程模型d 酬是表示区域d 上的三维向量有限序列，用函数的 形式描述为：v = ( x ，】，z ) ( f = l ，2 ，3 ，一) 式中，x ，y ，是平面坐标，历是( 石；，y ，) 对应的高程。当该序列中各平面向量 的平面位置呈规格网排列时。起平面坐标可省略，此时d e m 就简化为一维向量 1 8 第三章三维地形的特征提取 序列切p i = i ，2 ，3 ，j l 3 1 23 d s 文件格式介绍 3 d s 文件由许多块组成，每个块首先描述其信息类别，即块是如何组成的。 块的信息类别用i d 来标识，块还包含了下一块的相对位置信息。3 d s 二进制文 件中的数据是按低位在前、高位在后的方式组织的。如，3 a5 c 组成的整型数， 表明5 c 是高位字节，3 a 是低位字节；对于长整型数。如：3 a 5 c 4 8 8 f 表明5 c 3 a 是高位字节，4 8 8 f 是低位字节。下面描述块的具体定义块的前面两项信息分 别是：块的i d 和块的长度( 也即下一块相对于该块的字节偏移量) ，块的i d 是 一个整型数，而块的长度是一个长整型数每个块实际上是一个层次结构，不 同类型的块，其层次结构也不相同。3 d s 文件有一个基本块，其i d 是4 d 4 d ，每 一个3 d s 文件开头都是有这样一个块构成的。 3 1 3 地形模型文件的存储 由于三维地形模型与其他模型比较包含更多的空间信息，所以要使不同格 式的三维地形模型能够进行统一的检索，就需要建立统一的类进行封装对于 规则d e m 模型，不规则网格t i n 模型，和3 d s 模型文件，我们用3 d t o b j 类对其 进行操作。在3 d t o b j 类中我们加入了高程环节点，来更准确对地形进行描述定