（计算机应用技术专业论文）基于蔓延骨架的三维cad模型相似性评价研究.pdf

摘曼 摘要 三维c a d 模型的检索和重用技术作为c a d 技术和检索技术的结合，可以 有效地缩短产品开发周期，充分利用已有的设计资源，降低产品设计成本，近年 来这一方向逐渐成为c a d 研究领域的一个新的热点。同时，由于三维c a d 模 型从拓扑结构到几何形状e 的复杂性和多样性，提出和生成面向该领域的三维 c a d 模型的表示受到研究人员越来越多的重视。本文即是在这一背景下对该领 域中三维c a d 模型的表示方法和其在相似性评价中的应用展开研究。 论文工作主要包括以下几个方面： 提出一种基于蔓延生成三维c a d 模型骨架图的方法。生成的蔓延骨架图能 在正确表示c a d 模型的整体拓扑和几何属性的同时具有良好的稳定性，有效地 支持三维c a d 模型的相似性评价。该方法首先通过蔓延生成初始蔓延骨架，之 后对初始蔓延骨架进行必要的修正，最后基于蔓延骨架生成对应的蔓延骨架图。 提出了多层次蔓延骨架和骨架图生成方法，实现了对三维c a d 模型的层次 化表示。该方法通过对蔓延单元进行合理的层次化生成多层次的蔓延骨架，再通 过多层次蔓延单元结构图将不同层次的蔓延骨架有机组织起来形成多层次蔓延 骨架图。相应地，文中还给出了多层次的蔓延骨架图匹配方法以保证多层次蔓延 骨架图正确、高效的匹配。最终通过每一层蔓延骨架的稳定性结合细节层次对细 部特征的表示能力较好地实现了三维c a d 模型相似形评价中稳定性和敏感性要 求的和谐统一。 基于以e 研究成果，论文实现了一个基于蔓延骨架的三维c a d 模型相似性 评价原型系统，并利用一些三维c a d 模型实例对该系统进行了测试，初步验证 了基于蔓延的三维c a d 模型蔓延骨架图和多层次蔓延骨架图生成和匹配方法的 有效性。 关键词：实体模型，相似性评价，蔓延骨架，蔓延骨架图，多层次蔓延骨架， 多层次蔓延骨架图。 + 牟主得到国家n 然科学基台( 蝙号6 0 4 0 3 0 4 9 ) ；1 1 救育部跨世纪优秀人才培养向j 阻及浙江省重点碘目基畚( 编号2 0 0 5 c 2 1 0 9 6 和2 0 0 5 c 2 1 0 0 乃的资助 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc a dt e c h n o l o g y , 3 dc a dm o d e ls i m i l a r i t y e s t i m a t i o na n dr e t r i e v a lb e c o m em o r ea n dm o r ei m p o r t a n tf o ri n d u s t r i e st or e d u c et h e c o s ta n di m p r o v et h ee f f i c i e n c yo fd e s i g n p r o c e s s d u et o t h e c o m p l e x i t ya n d d i v e r s i t yo ft h ec a dm o d e l s ，t h eg e n e r a t i o no fp r o p e rs h a p ed e s c r i p t o ro fc a d m o d e l si sab i gc h a l l e n g e i nt h i st h e s i s ，t h er e s e a r c h e sa r em a i n l yf o c u s e do nt h e a p p r o a c ht oc o n s t r u c t i n gp r o p e rs h a p ed e s c r i p t o mf o r3 dc a dm o d e ls i m i l a r i t y a s s e s s m e n t t h em a i nc o n t e n t so ft h et h e s i sa r ea sf o l l o w s ： an e w a p p r o a c ht og e n e r a t i n gd i l a t i o nb a s e ds k e l e t o n ( d b s ) i sp r e s e n t e d i nt h i s a p p r o a c h ，ai n i t i a ld b si sg e n e r a t e db a s e do nt h ed i l a t i o nu n i t sf i r s t ，t h e nt h ed b si s r e f i n e da sn e e d e d ，a n dg r a p hm a t c h i n ga l g o r i t h mi s a d o p t e dt oe s t i m a t et h er a t i oo f s i m i l a r i t ya c c o r d i n gt ot h ed b sg r a p hw h i c hi sc o n s t r u c t e df r o mt h ed b sd i r e c t l y a s as h a p ed e s c r i p t o r , t h ed b s g r a p hc o n t a i n st h eg r o s st o p o l o g ya n dg e o m e t r i cf e a t u r e s o fa3 dc a d m o d e l ，a n dt h u si ti ss t a b l ee n o u g ha n dc a ne f f e c t i v e l ys u p p o r t3 dc a d m o d e ls i m i l a r i t ya s s e s s m e n t t h ed b si sf u r t h e re x t e n d e dt oam u l t i s c a l es h a p ed e s c r i p t o rc a l l e dd i l a t i o n b a s e dm u l t i r e s o h i t i o n a ls k e l e t o nr d b m s ) i no r d e rt og e n e r a t et h ed b m so fac a d m o d e l ，w eg e tt h ed b so fe a c hl a y e rf i r s ta c c o r d i n gt ot h em u l t i - l a y e rd i l a t i o nu n i t s ， t h e nt h e s ed b s sa r ew e l lo r g a n i z e dt of o r mt h ew h o l ed b m sa n dt h ed b m sg r a p h ， f i n a l l yam u l t i l a y e rm a t c h i n gm e t h o di sa l s og i v e nt os u p p o r tt h ee f f i c i e n tm a t c h i n g a m o n gd i f f e r e n td b m sg r a p h s u t i l i z i n gt h i sn e ws h a p ed e s c r i p t o r , d e t a i l so ft h e m o d e lc a nb ee a s i l yc a u g h tu s i n gh i g h l e v e ll a y e ro ft h ed b m sa n dt h es t a b i l i t yo f t h ew h o l e d e s c r i p t o ri sg u a r a n t e e db ye a c hl a y e r ss t a b i l i t ya tt h es a l n et i m e b a s e do nt h ea b o v er e s u l t s ，ap r o t o t y p es y s t e mz d - 3 d s e si sd e v e l o p e d m e a n w h i l e ，s o m et e s t so nt h i sp r o t o t y p ew i t hs o m ec a dm o d e l sa r ec o n d u c t e d ， w h i c h s h o w st h ev a l i d i t yo ft h ep r o p o s e da p p r o a c h e s k e y w o r d ：s o l i dm o d e l ，s i m i l a r i t ye s t i m a t i o n ，d i l a t i o nb a s e ds k e l e t o n ，d i l a t i o n b a s e ds k e l e t o ng r a p h ，d i l a t i o nb a s e dm u l t i r e s o l u t i o n a ls k e l e t o n ， d i l a t i o nb a s e dm u l t i r e s o l u t i o n a ls k e l e t o ng r a p h 。* t 。h 。i 。st r 。”，s l 。si s 。盏嚣蔼兰黑，n 。a 。t 。i o n a 。ln 。a 。t u r ，a l ，s 咧o 鬣嚣畿甓：! ：i ：宅器竺筹黧孟 舞盏墨毒等蠹襞：瑟“ i i 笫一章绪沦 1 1c a d 技术 第一章 1 i ic a d 技术发展简史 绪论 c a d ( c o m p u t e ra i d e dd e s i g n ) 技术最早起步于5 0 年代后期。2 0 世纪6 0 年代， 美国的i v a ne s u t h e r l a n d 博士在其论文“s k e t c h p a d ：一种人机对话系统”中首 s u t h e r i a a d i 3 次提出了c a d 的概念 ，。此后四十多年中，c a d 技术迅速发展，为全世界 工业的发展起到了较大的促进作用，并在许多重要工程领域取得了巨大的成功。 目前，c a d 技术的发展和应用水平已成为衡量一个国家科技现代化水平和工业现 代化水平的重要标志之一。 在四十多年的发展历程中，c a d 技术经历了h 个重要阶段：2 0 世纪5 0 年代初 到6 0 年代末为第一阶段，这一阶段的c a d 软件基本上都是二维交互绘图系统，功 能和应用都受到很大的限制。第二阶段为7 0 年代仞f q 7 0 年代未，这一阶段的c a d 主要研究三维造型技术，特别是曲面造型技术。7 0 年代正值飞机和汽车工业的蓬 勃发展时期，传统的多截面视图、特征纬线和油泥模型等方法已经不再能够满足 设计者设计自由曲面的需要。b e z i e r 算法使得人们用计算机处理曲线及曲面问题 变成可能，与此同时一些大公司在国家的支持下也相继丌发i 出c a 2 i a ，u g 等一批 商用c a d 软件。8 0 年代初期，人们开始了对c a d c a e 一体化技术的探索。传统的表 面模型技术只能表达形体的表面信息，难以准确表达零件的其它特性，如质量、 第一章绪论 重心、惯性矩等，虽然基本可以解决c a m 的问题，但因为模型分析的前处理特别 困难而r 十c a e 十分不利。期间，为解决一体化问题，s d r c 公司于1 9 7 9 年发布了世 界上第一个完全基于实体造型技术的大型c a d c a e 软件i d e a s ，并在以后的 1 0 年里逐渐为众多c a d 系统所模仿。到了8 0 年代中期，p r o e 系统的 h 现充分体现 出参数化技术在许多通用件、零部件设计上简便易行的优势，因此c a d 软件中也 逐渐加入了参数化设计支持。在9 0 年代中期，人们提出了面向智能化、集成化、 网络化的新一代c a d 技术。c a d 软件通过产品数据管理( p d m ) 、统一的产品信息模 型和数据交换规范s t e p ( s t a n d a r df o rt h ee x c h a n g eo fp r o d u c tm o d e ld a t a ) “j 0 2 支持分布式工作环境下的协i 司设计 。 传统的c a d 3 技术已经历了许多年的发展历程，被工业界普遍接受并取得了显 著的经济效益。但随着c a d 应用软件的迅猛发展，已有设计不断的增加，伴随 着设计公司和设计人员对重用已有设计的需求，人们对传统的c a d 技术提出了 新的要求。“u m 8 n 9 7 “m 9 一9 0 ”。用户希望c a d 系统能对已有设计模型的快速检索提 供支持，从而使设计人员和公司在设计过程中节约大量的人力、物力，提高设计 效率，降低设计成本。因此，可以预见，三维模型的检索和重用技术将成为今后 c a d 技术发展的一个热点。 1 1 2c a d 技术发展趋势 随着c a d 系统实际使用范围的不断扩大，人们对c a d 系统提出了更高的要求。 从设计需求的角度来看，传统的c a d 系统存在着以下不足： ( 1 ) 难以支持产品设计的全过程：产品的设计包括功能设计、概念设计、详 细设计、测试分析等阶段。传统的c a d 系统主要支持详细设计阶段，而对产 品的初始和后续阶段支持不足。 ( 2 ，不能有效地支持毖同设计：随着计算机网络技术的发展，为了缩短设计 周期，一个产品的设计往往需要不同应用领域的多个设计人员在异地、异构 的环境下协同完成，而传统的c a d 系统主要支持基于个体的设计或顺序串行 的设计方法，难以支持分布式环境下的协同设计。 第一章绪论 【3 ) 不能有效的支持对原有设计的高效检索：有调查显示完全从无到有的设 计l 分少见，绝大多数设计人员在进行新产品的设计时花费7 0 甚至更多的 时间去寻找一个合适的已有设计，再在这个设计的基础上通过修改完成新的 设计【9 “山g o “。而目前这一搜寻过程基本上通过人工完成，费时费力，传统 的c a d 系统在这一点上都难以提供有力的支持。 针对传统c a d 技术的不足，近年来国内外的研究人员对c a d 的有关技术进行了 大量研究，并做出了大量有益的工作。提出了c a d 技术发展的一些方向： 集成化 c a d 系统的集成化主要包括三个方面：产品数据模型的集成化、产品设计 过程的集成化以及产品设计功能的集成化。产品数据模型的集成化要求系统 支持产品从功能设计到详细设计整个生命周期的产品信息，它既要包括产品 的几何形状信息，也要包括大量的q f - j l 何信息。产品设计过程的集成化要求 系统支持产品整个设计生命周期，使不同的设计阶段能在一个集成化的环境 下进行。设计功能的集成化要求系统将众多的单独设计功能组合成一个统 的设计环境，为设计人员提供设计过程中各种设计活动的支持。 网络化 设计活动一股由不同的设计人员或团体协同完成，分布式的网络环境是 实现这一目标的有效手段。为提高效率，今后的c a d 系统的发展趋势是产品 设计能够通过网络在异地异构的设计环境下同步协同地进行。 智能化 c a d 系统的目的就在于使人们尽可能从繁重的设计活动中解放出来并提 高设计效率。随着人工智能技术的飞速发展，知识工程、专家系统逐渐引进 到c a d 系统。通过c a d 系统、设计知识的有机结合使得c a d 系统具备启发 设计灵感，激发创造力、想象力的功能，具有学习能力以及应用专家的知识和 经验机制，已经成为众所瞩目的发展方向。 三维c a d 模型的检索技术为设计人员快速和准确地获得所需要的已有 设计提供了有力支持，从而大大减少设计人员在这一方面时阳j 和精力的投 第一章绪论 入。 1 2 三维模型检索 近来，检索技术成为计算机科学领域的一个重要的研究方向，尤其是伴随着 信息量的快速增长，如何快速、高效、准确的找到需要的信息越来越受到人们的 重视。 目前，相对成熟的信息检索技术都是基于文本的( t e x t b a s e d ) ，如著名的搜 索引擎g o o g l e ，百度等。但伴随着计算机图形学、计算机辅助设计( c a n ) 、三 维动厕等技术的迅猛发展，基于文本检索技术的局限性也突显出来，于是基于内 容的检索逐渐成为研究的热点，包括二维图像检索、视频检索、三维模型检索等。 其中三维模型检索因三维模型的广泛应用和现有三维模型数量的快速增长受到 很多研究人员的关注。 1 2 1 三维模型分类 目前，主流的三维模型的表示方法有面片表示( m e s h ) 、边界表示( b r e p ) 和 点云表示( p o i n t sc l o u d ) 。面片表示是用无数小面片( 多为三角面片) 的组合去表示 一个三维模型的表面。其优点是数据量小，便于储存和计算机显示，多用于三维 动画等计算机图形学领域，缺点是不精确，很难用于工程领域。边界表示是通过 点、线、面、体等不同层次的拓扑和几何元素以及它们之间的关系来表示三维模 型的边界。其优点是表示精确，拓扑、几何关系清晰，适用于工程等对数据精确 性要求较高的领域，缺点是数据量庞大。现有的c a d 设计软件如u g 、p r o e 、 s o l i d w o r k s 、a c i s 等都采用边界表示作为其模型的表示方法。点云表示是用密集 的点来表示三维模型，其优点是获取容易，通过对实物的扫描即可获得，缺点后 期处理困难，很多情况下点云表示都转化为面片表示或边界表示后进行后期处 王早。 1 2 2 面向相似性评价的三维模型表示方法的衡量标准 三维模型大多基于面片表示或边界表示，自身十分复杂，直接基于这样的表 鹅一章绪论 入。 1 2 三维模型检索 近来，检索技术成为计算机科学领域的一个重要的研究方向，尤其是伴随着 信息量的快速增长，如何快速、高效、准确的找到需要的信息越来越受到人们的 重视。 h 前，相对成熟的信息检索技术都是基于文本的( t e x t b a s e d ) ，如著名的搜 索引擎g o o g l e ，百度等。但伴随着计算机图形学、计算机辅助设计( c a d ) 、三 维动画等技术的迅猛发展，基于文本检索技术的局限性也突显出来，于是基于内 容的检索逐渐成为研究的热点，包括二维图像检索、视频检索、三维模型检索等。 其中三维模型检索冈三维模型的广泛应用和现有二维模型数量的快速增长受到 很多研究人员的关注。 1 2 1 三维模型分类 目前，主流的三维模型的表示方法有面片表示( m e s h ) 、边界表示( b - r 印) 和 点云表示( p o i n t sc l o u d ) 。而片表示是用无数小面片( 多为二角面片) 的组台去表示 一个三维模型的表面。其优点是数据量小，便于储存和计算机显示，多用于三维 动画等计算机图形学领域，缺点是不精确，很难用于工程领域。边界表示是通过 点、线、面、体等不同层次的拓扑和几何元素以及它们之划的关系来表示三维模 型的边界。其优点是表示精确，拓扑、几何关系清晰，适用于工程等对数据精确 性要求较高的领域，缺点是数据量庞大。现有的c a d 设计软件如u g 、p r o e 、 s o l i d w o r k s 、a c i s 等都采用边界表示作为其模型的表示方法。点云表示是用密集 的点来表示三维模型，其优点是获取容易，通过对实物的扫描即可获得，缺点届 期处理困难，很多情况下点云表示都转化为面片表示或边界表示后进行后期处 理。 1 2 2 面向相似性评价的三维模型表示方法的衡量标准 三维模型大多基于面片表示或边界表示， 三维模型大多基于面片表示或边界表示， 自身r 分复杂，直接基于这样的表 自身r 分复杂，直接基于这样的表 第一睾绪沦 示不可能进行相似性评价。合理，高效的三维模型表示是进行准确的i 维模型相 似性评价和检索的前提条件。以下是一组衡量标准，用于衡量面向相似性评价的 三维模型表示方法的合理性【”8 “】 w o o “8 。8 7 】 b i n f o r d 8 2 】 b m “3 l h a 。a l i c k 8 9 l m o k h t a r i a n 9 2 j ： a 。完整性：能表示各种拓扑和儿何结构的二维模型。 三维模型十分复杂，用于表示三维模型的几何元素中除了简单的点，线 段，平面和常规的二次曲面以外还有不规则的二次曲面，自由曲面，t r i m e d 曲面等复杂形式。因此好的三维模型表示方法必须要有很宽的描述范围以应 对不同情况下复杂的c a d 模型。 b 唯一性：三维模型和其表示之间一一对应。 这一点十分重要，因为如果这一点无法保证，基于该表示方法的三维模 型相似性评价结果的准确性将受到很大的影响。 c 稳定性：三维模型表面小的扰动不应对其表示产生剧烈影响。 也即是随小的细节和扰动不能对模型的表示有很大的干扰，只有这样才 能确保相似性评价的准确定和检索的质量。这一点也往往是三维模型表示方 法的设计难点。 d 敏感性：三维模型的细节信息应在其表示中得以体现。 这一点在进行高精度三维模型相似性评价时十分重要，表示方法只有具 备这一特性才能支持对细节的匹配。 e 高效性：三维模型的表示应易于生成。 如果生成表示的代价过大，对于海量的三维模型库来说是不可容忍的。 f 层次性：描述符支持对三维模型多层次的表示。 “细节将被抑制，直到需要它们的时候为止”，这就是多层次表示方法 希望达到的目标。好的表示方法具有在不同层次体现模型不同细度特征的能 力，从而可以有效的支持层次式的三维模型相似性评价。 球局部性：描述符支持对三维模型局部特征信息的表示。 局部性存在于两个方面，一是表示本身是否具有局部性，只有拥有这一 局部性的表示才能支持局部相似性评价。另一方面是表示的生成是否有局部 性，即是否能根据相似性评价的需要局部生成三维模型的表示。 第一章绪论 1 3 现有的三维模型相似性评价方法 通过对现有的一些三维模型相似性评价方法的分析和总结，我们将它们分为 以卜i 几类： ( 1 ) 基于全局特征的方法；( 2 ) 基于加工特征识别的方法；( 3 ) 基于图的方法； ( 4 ) 基于直方图的方法；( 5 ) 基于产品信息的方法。 1 3 i 基于全局特征的方法 这类方法运用三维c a d 模型全局的特性作为其描述符，例如矩、球面调 和函数、一些几何不变量等等。f u n k h o u s e r 提出过一种以球面调和函数作为三维 模型的描述符的方法【“曲“”邮】。n o v o t a i 针对球面调和函数的一些不足提出了用 z e m i k e 矩作为描述符的三维模型相似性评价方法 n o ”a i 0 3 1 。 这一类方法的一卜共同不足就是它们都只看重模型的几何特征，因此相似性 评价的准确性上存在不足，尤其是对于拓扑结构更为重要的c a d 模型，该类方 法的这一特性就成了致命的弱点。例如，用该方法对两个拓扑同构，只是有几何 差别的三维c a d 模型进行相似性评价，结果很可能是完全不相似，而这显然是 不合理的。 1 - 3 2 基于加工特征识别的方法 这是一类基于三维c a d 模型加工特征的相似性评价方法，因此在进行相似 性评价之前首先要对所有的c a d 模型进行加工特征识别。然后再通过某种方式 将这些识别出的特征组织起来用于进行彼此直接的匹配和相似性评价。e l i n s o n 等提出利用识别出来的三维c a d 模型的加工特征生成一个对应的模型相关图 ( m o d e ld e p e n d e n c yg m p h ) ，并且用它对不同的机械零件进行比较【e 1 。m 3 “”ji 。试讪。 0 1 】。在r a m e s h 的方法中，通过特征识别，三维c a d 模型首先被分割成为一系 列简单形状的块，然后再通过三维模型以及特征之间的空间和连接关系生成对应 的块结构图，最后基于该结构图进行三维c a d 模型的比较和相似性评价 【。姗”。k i m 则提出了一种基于加工特征识别的凸分割方法，该方法运用加工 特征识别的结果完成对给定三维c a d 模型的凸分割，最后再通过引入可视锥 第一章纬论 ( a c c e s s i b i l i t yc o n e l 对凸分割进行匹配和比较【踟吲。 这类方法的一个很大局限就是要基于加工特征识别技术，而现有的加工特征 无法处理自由曲面特征，因此浚方法能处理的模型类型受到很大限制。 1 3 3 基于图的方法 这一类方法用图作为三维c a d 模型的表示，通常情况下图中包含了对应模 型的相关拓扑和几何信息。对用图作为表示的方法，最终的相似性评价需要通过 图匹配算法来完成。普渡大学的l y e r ，l o u 和h o u 提出了一种基于三维c a d 模 型的骨架图进行匹配的方法l i y 锄3 a 】i l o u 0 3 l 【l y 。m 6 1i h o ”0 4 1 ，其中三维c a d 模型的骨架 通过细化( t h i n n i n g ) 的方法获得，最终生成的骨架图保持对应的三维c a d 模型的 亏格不变。m c w h e r t e r 在它的方法中将给定的三维c a d 模型转化为一个模型标 记 ( m o d e ls i g n a t u r eg r a p h ) ，再计算这个模型标记圈的特征值谱空间，以此作 为模型的描述符并用于不同模型之间的比较i m c w h “啪”。三维c a d 模型的b r e p 表示也被直接用于相似性评价，e 1 e h a l a w i 和m i l l e r 提出了直接基于c a d 模型 的边界表示图用予图同构进行三维c a d 模型相似性评价的方法【e 1 m 酬”0 3 8 】 e i - m e h a l “3 b i 。s u n d a r 提出了另一种基于模型骨架的特征图提取方法，该疗法利用 最小蔓延树( m i n i m u ms p a n n i n g t r e e ) 算法，将体素空问下细化和聚类算法后得到 关键骨架点组织成对应的无向图，之后通过图匹配实现模型的相似性评价 s u ”4 3 1 。h i l a g a 在2 0 0 1 年的s i g g r a p h 提出了利用r e e b 图进行三维模型相似 性评价的方澍m 1 a g a o ”，b e s p a l o v 对该方法进行了改进使其能使用在三维c a d 模 型的相似性评价中【“s p a l o ”0 3 。 基于图方法的主要问题是很难在表示能力和匹配效率上获得平衡。表示方法 的表示能力和图结点的数量上获得平衡。因为过少的结点很难完整的表示对应三 维c a d 模型的信息，而结点过多对于本身是n p 问题的图匹配算法又会带来过 大的负担。 1 3 4 基于直方图的方法 基于直方图的方法是通过采样三维模型表面上的点，再从这些采样点中提取 相应特征的方法。b e s p a l o v 提出过一个基于谱分解( s p e c 打u md e c o m p o s i t i o n ) 的 一7 第一章绪论 法【& “p ”0 3 b 1 通过对给定模型对应谱的分解，= 维模型的相似性比较问题就转化 成对应标记结点的树集( v e r t e x 1 a b e l e dr o o t e dt r e e s ) 的映射和距离计算问题。y i u 等提出了基于形状分布的三维实体比较的方法t 伽0 2 】。r e a 等人提出了基于表丽分 解谱( s u r f a c ep a r t i t i o n i n gs p e c t m m ) 的三维c a d 模型索引化和检索算法i 鼬8 0 “。 基于直方图的算法中存在计算时间消耗和采样点数量平衡的问题。采样点多 可以更准确、完整的表示三维模型但是计算的时间和空问消耗会非常的大。而控 制了计算的时间和空间复杂度可能会造成采样点过少从而影响采样的准确性和 完整性。 1 3 5 基于产品信息的方法 近年来，研究人员越来越重视产品信息，工程语义在三维c a d 模型相似性 评价中的作用。工程语义是指三维c a d 模型的设计和加工特性，例如功能，加 工要求，质量，材料等，也正是因为其特殊性，如果能成功将它引入到三维c a d 模型的相似性评价中便可以大大提高三维c a d 模型相似性评价的准确性和专业 性。l y e r 和n a g i 提出了基于成组技术( g r o u p t e c h n o l o g y ) 的：维c a d 模型相似性 评价方法i “y 一7 1 ，该方法用g t 码作为三维c a d 模型的描述符。s r i n i v a s 提出了 类型抽象层级回p ea b s t r a c t i o nh i e r a r c h y ) 的方法【蟹豳勰9 7 1 ，该方法在进行三维 c a d 模型相似性评价时，不仅考虑产品自身的特点，同时将它们彼此之间的联 系和关系也考虑进去。t s a i 等提出的基于模糊集的两阶段c a d 模型相似性评价 方法将加工要求，质量，材料，硬度，表面粗糙程度等工程语义用作c a d 模型 相似性评价时的属性并利用模糊数学的相关内容，将工程语义中相关的模糊表达 数字化i t s a “。 该类方法往往需要人工输入模型以外的其它信息，并且稳定性大多不高。不 过，虽然这类方法存在很大的局限性和不足，但其为工程语义在c a d 模型相似 性评价中的应用提供了一种可能的研究和发展方向。 1 4 工程领域对实体模型检索技术的需求 早在1 9 9 4 年，l e i z e r o w i c z 的报告中就指出设计人员花费他们6 0 的时间用 于找到合适的已有设计耻h 。训圆6 1 。在美国科学中的一篇文章中，g u n n 经过计算 第一章绪论 估计“只有不到2 0 的设计需要从头做起，有4 0 以上的设计可以在一个已有 设计的基础上完成，另外有超过4 0 0 的设计只需在已有的设汁上通过小的修改 便可以得到” 6 u ”82 1 。1 9 9 7 年，u u m a n 估讣7 5 的新设计是在原有的设计上通 过改进和修改完成的m 3 棚】。 但在实际设计和生产过程中，由于没有有效的工具对已有设计进行检索，设 计人员往往花费大量的时间在寻找合适的已有殴计上，有时即使花费了大量时间 也找不到最合适的已有设计。因此，要想有效的提高新产品的开发效率，缩短设 计时间，已有设计知识的检索和重用至关重要。 从上世纪9 0 年代起，伴随着c p u 、三维图形加速卡等计算机硬件技术的发展， 三维模型得到越束越广泛的应用。根据c h r i s t m a n 的调查，在2 0 0 1 年设计的c a d 模型中，大约6 6 的c a d 模型使用三维设计“”“1 ，这一数字在2 0 0 3 年达到了8 0 。同时由于三维c a d 设计软件的大量普及，三维c a d 模型无论从数量和复杂度卜 都飞速增长。同时对于三维c a d 模型( 实体模型) 而言，由于其设计时间更长，设 计成本更高，因此它的检索和重用有着更大的价值和意义。 正是在这样的背景之下，本文将研究立足在对实体模型( 边界表示模型) 的表 示和相似性评价方法的研究。 1 5 实体模型相似性评价研究存在的问题 现阶段的实体相似性评价和检索技术n t j 冈t j 兴起，很多至关重要的问题都还没 有得到很好的解决，这些问题成为当前制约实体模型相似性评价和检索技术研究 的瓶颈。 1 5 1 实体模型表示方法稳定性不足 现有的实体模型的表示方法缺乏足够的稳定性，容易受到模型表面微小细节 瓤扰动的影响。两我们在1 2 3 小节中强调，表示方法的稳定性对于实体模型相 似性评价十分重要，基于缺乏稳定性的表示进行实体模型的相似性评价，其效率 和质量都会很低。 当然单纯提高描述符的稳定性而减弱了表示方法对实体模型的区分能力，甚 第一章绪论 至破坏了唯一性的要求，也是不可取的。 1 5 2 实体模型表示方法层次性不足 研究人员都认识到层次性对于一个实体模型表示方法的重要性，只有通过层 次性才能有效调和稳定性要求和敏感性要求之间的矛盾，同时提高相似性评价的 效率和质量。 l i5 3 实体模型表示方法抽象程度不足 实体模型最终要实现高效、商业化的检索功能，其描述符必须高度抽象，至 少要能被数据库保存和使用。相对于这要求现阶段的实体模型表示方法往往只 是对模型低层次的抽象。 1 5 4 实体模型表示方法完整性不足 复杂的实体模型往往拥有儿于甚至几万的面，对于这样程度的复杂性，现有 的许多实体模型描述符提取方法无法提取有效的表示。 1 6 本文的研究目标和主要研究内容 本文主要针对1 5 1 小节和1 5 2 小节中提及的问题展开研究。也即重点研究 如何使实体模型表示方法更加稳定以及如何生成高质量的实体模型多层次表示。 本文的研究目标是： 1 ) 提出种具有较强稳定性的实体模型表示方法。该表示方法在保持唯一 性的同时对于实体模型表面的小细节和小扰动具有相当的抗干扰能力。 2 1 提出种具有层次性的实体模型表示方法。该表示方法通过对1 ) 中表示 方法的改进，将模型不同细节程度的特征通过多层次表现出来，从而大大提高表 示方法的敏感性。而在每一个层次内部保持1 1 中表示方法的稳定性。 3 ) 基于上述表示方法，提出对应的实体模型相似性评价算法。特别对应多 层次的表示方法，提出对应的多层次相似性评价算法，在提高匹配准确性的同时 提高匹配效率。 第章绪论 本文的丰要内容和文章组织结构为： 第一章：绪论。着重介绍本文的研究背景，包括c a d 技术，三维模型相似 性评价技术等。 第二章：基于蔓延的三维c a d 模型骨架生成方法。通过分析已有的实体模 型表示方法在稳定性上的不足提出了一种基于蔓延的通用实体模型表示的生成 方法。 第三章：基于蔓延算法的三维c a d 模型相似性评价。基于实体模型相似性 评价的要求，对第二章中提出的通用实体模型描述符进行改进。并且应用此具有 良好稳定性的描述符进行实体模型的相似性评价。 第四章：基于蔓延算法的三维c a d 模型多层次相似性评价。提出一种基于 蔓延技术的多层次的实体模型表示方法并给出了具体的生成过程。进而在此基础 卜针对该多层次表示提出了对应的多层次匹配方法，两者结合有效的进行实体模 型的多层次相似性评价。 第五章：系统实现。基于第二、第三、第四章中提出的方法，开发了原型系 统z d 一3 d s e s ( z h e d a 一3 ds i m il a r it ye s t i m a t i o ns y s t e m ) ，并通过些测试初步 验证了研究成果和原型系统正确性。 第六章：总结与展望。针对第二、第三、第四章中介绍的方法和原型系统中 一些不足的地方进行分析，并提出进步改进的可能方向。同时，根据已有的资 料和认识，展望三维c a d 模型相似性评价和检索领域未来的发展方向和趋势。 筹二二章皋于蓝延的实体模壁骨槊生成方法 第二章 基于蔓延的实体模型骨架生成方法 2 1 引言 在本章中，我们将介绍一种基于蔓延的实体模型骨架的生成方法。一直以来 人们都希望能找到简单而有效的表示方法来表示实体模型，因为现有的三维模型 尤其是边界表示模型的表示方法十分复杂、数掘量大，无法直接应用于相似性评 价领域，只有基于相对简单的表示，才可能真正实现实体模型的相似性评价和检 索。我们将c o s t a 在二维图像领域应用的基于蔓延的骨架生成方法【c 0 “删推广到三 维领域，提出了基于蔓延的实体模型骨架生成方法。相对实体模型采用的边界表 示，它是一种十分简单的实体模型表示方法，同时它又具有很好的表示能力，能 提供丰富的信息用于实体模型的相似性评价。 下面我们先给出一些基本概念，再简要介绍一f 基于蔓延的二维图像骨架 生成方法，最后详细给出基于蔓延的三维c a d 模型骨架生成方法。 2 2 基本概念 定义1 中轴( m e d i a l a x i s ) 中轴是到模型边界上两个或两个以上的点的距离等于该点到模型边界的距 离的模型内部的点的集合。其中点到模型边界的距离是该点到模型边界卜所有点 中距离最短的一个。 定义2 蔓延窄间( d i l a t i o ns p a c e ) 蔓延空间指参与整个蔓延过程的点的集合。如图2 - 1 所示，在图中整个二维 第章肇十蔓延的宴体摸型骨柴生成方 ： 模型构成蔓延空间，即图中各色阴影部分共同组成的区域。 定义3 蔓延单元( d i l a t i o nu n i t ) 蔓延单元是指模型边界上一组点的集合，这组点在蔓延过程中充当种了的角 色。在图2 - 1 中二维模型的四条不同颇色的边界代表了四个不同的蔓延单元。 定义4 蔓延区域( d i l a t i o nr e g i o n ) 蔓延区域是蔓延空间中一系列的点的组合，这些点具有同一个特性，即在所 有的蔓延单元罩，它们距离同一个蔓延单元的距离最近。这个蔓延单元也就是浚 蔓延区域对应的蔓延单元。在图2 - 1 中，四个不l j 颜色阴影的区域就是四个不同 的蔓延区域，阴影的颜色与其对应的蔓延单元的颜色相| 一j 。 定义5 蔓延骨架面( d i l a t e ds k e l e t a lf a c e ) 蔓延骨架面是到某两个蔓延单元距离相等的点的集合。在图2 - 1 中五条双色 的线段就是蔓延骨架面( 二维中是线段) ，两种颜色分别代表了构成该骨架面的两 个对应的蔓延区域( 亦即蔓延单元) 。 定义6 基于蔓延的骨架( d i l a t i o nb a s e ds k e l e t o n ) 蔓延骨架面的集合构成了模型的基于蔓延的骨架。在图2 - 1 中模型中部五个 蔓延骨架而组成的框架就是蔓延骨架。 蔓延单元1 蔓延区域i 图2 - i 蔓延方法相关概念的图示( 二维) 蔓延单元2 蔓延区域2 第一常基于蔓延的实体模型骨架生成方法 性质1 ：每个蔓延骨架面就是两个蔓延区域相交的部分。 这一点由定义4 和定又5 就可以得到直接的证明。 性质2 ：当一个模型边界上的每一个点都被作为。个单独的盟延单元时，所得的 蔓延骨架即是该模型对应的中轴。 证明：当模型边界上的每个点都成为单独的蔓延单元时，由定义5 可以得 到任意一个蔓延骨架面上的点都是到模型边界上两点距离相等的点。再由定义6 可得所有这样的点构成蔓延骨架，也即此时的蔓延骨架是到模型边界上两个或以 上的点的集台，而这诈是中轴的定义，结论成立。 性质3 ：蔓延骨架上的点是中轴上点的予集。 证明：由定义4 可知，蔓延骨架上的点都是距离两个或两个以上的蔓延单元 的距离最小的点的集合。那么这些点一定是距离这两个蔓延单元上某两个或两个 以上的点距离最小的点的集合。又因为属于不同蔓延单元的点彼此之间是没有交 集的且是模型边界上的点，所以蔓延骨架上的点是距离模型边界上两个或两个以 上点的距离最小的点的集合，再由中轴的定义可以知道，这些点是中轴上点的集 合的一个子集。 推论1 ：任何蔓延区域的内部都不存在蔓延骨架面上的点。 这一点由性质1 很容易直接得到。 推论2 ：蔓延骨架并不唯一，每一个蔓延单元的划分都对应一个蔓延骨架。 因为蔓延骨架由蔓延骨架面构成，蔓延骨架面由相应的蔓延区域的相交部分 构成，而蔓延区域又和蔓延单元一对应，所以相对于不同的蔓延单元划分方法 有不同的蔓延骨架与之一一对应。 2 3 基于蔓延的二维图像骨架生成方法 为了解决中轴易受小的扰动影响的问题，2 0 0 0 年，l u c i a n od af o n t o u r ac o s t a 提出了一种基于蔓延的二维图像骨架图生成方法i c o n 羽q 。通过该方法生成的二维 图像的骨架图能抑制中轴生成中由于小的扰动产生的部分，从而使得生成的骨架 图具有很高的稳定性。如图2 2 中所示，图2 2 ( a ) 中是一个带有小缺口的矩形的二 维图像，图2 2 ( b ) 中是它对应的中轴，图2 2 ( c ) 中是通过c o s t a 基于蔓延的方法得 到的蔓延骨架，其中矩形外部生成的骨架是由该矩形和整个图像的边界通过蔓延 第二章甚于蔓延的实体模型骨架生成方法 获得的。 图2 2 中轴与蔓延骨架举例 我们取出整个蔓延骨架中属丁该矩形内部的部分，可以发现它就和一个没有 缺口的矩形对应的中轴近似，而图2 2 ( b 1 中多出的两个分支就是由原矩形e 的细 小缺口引起的。 二维图像的蔓延骨架是通过蔓延方法提取的二维图像骨架，该骨架具有很好 的稳定性，只反应二维图像的主要结构特征，能很好的抑制图像边界上的小扰动 对骨架的影响。 在二维图像蔓延骨架生成过程中，蔓延单元的选取是至关重要的环节。理想 的蔓延骨架应该在具有相当重构性的同时尽量抑制由小扰动引起的骨架中不稳 定的部分。 考虑到是在二维图像领域的应用，c o s t a 采用了基于多层次曲率的方法对图 像的边界部分进行分割，即整体曲率变化不大的部分归入一个蔓延单元。 所谓蔓延就是基于一个起始位置( 蔓延单元) 按照距离近先到达、距离远后 到达的原则的一个扩展的过程。就如同向水平地面的某一点不停的倒水一样，理 论上水应该从倒下的这一点开始向外成同心圆的形状向外不断扩延。文中的蔓延 也基本上就是这么一个过程，只不过蔓延的起点( 蔓延单元) 可能是一个点，也 可能是一条线段或者曲线甚至一个无规律的点的集合。 蔓延过程在两种情况下停止： ( 1 )蔓延过程中如果从不同起始点出发的蔓延相遇时，在相遇的点上的 蔓延停止。 ( 2 )蔓延过程不能超越蔓延空间，也即是说蔓延在遇到蔓延空间的边界 时停止。 | 挚二章基十蔓延的实体模型骨妊生战方法 如图2 一l 所示，四边