《三维CAD模型公共可重用局部结构自动提取.pdf》由会员分享，可在线阅读，更多相关《三维CAD模型公共可重用局部结构自动提取.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2 3 卷第9 期计算机辅助设计与图形学学报V 0 1 2 3N o 92 0 11 年9 月J o u r n a lo fC o m p u t e r A i d e dD e s i g n C o m p u t e rG r a p h i c sS e p 2 0 1 1三维C A D 模型公共可重用局部结构自动提取张开兴，张树生，白晓亮(西北工业大学现代设计与集成制造技术教育部重点实验室西安7 1 0 0 7 2)(z h a n g k a i x i n g m a i l n w p u e d u c n)摘要：为了更好地实现C A D 模型的重用，提出一种面向C A
2、 D 模型的自动识别和提取公共可重用局部结构算法首先将C A D 模型用属性化特征邻接图来表示；将公共可重用局部结构的提取转化成频繁子图挖掘问题来解决，通过候选产生、候选剪枝、频繁度计数及后处理等步骤来实现可重用局部结构的提取实验结果表明该算法可以实现隐含在外形完全不同的C A D 模型中的、不易被发现的局部结构的提取，由于在提取的过程中运用了多种优化算法，因此算法的效率可满足工程应用中的需求关键词：可重用；局部结构；属性化特征邻接图；频繁子图挖掘中图法分类号：T P 3 9 lA u t o m a t i cE x t r a c t i o no fC o m m o nR e u s
3、a b l eP a r t i a lS t r u c t u r e si n3 DC A DM o d e l sZ h a n gK a i x i n g，Z h a n gS h u s h e n g，a n dB a iX i a o l i a n g(K e yL a b o r a t o r yo，C o n t e m p o r a r yD e s i g na n dI n t e g r a t e dM a n u f a c t u r i n gT e c h n o l o g y(N o r t h w e s t e r nP o l y t e
4、 c h n i c a lU n i v e r s i t y)，M i n i s t r yo fE d u c a t i o n，X i a n7 1 0 0 7 2)A b s t r a c t：T or e u s eC A Dm o d e l sm o r ee f f i c i e n t l y，an e wm e t h o df o rs e e k i n gt h ec o m m o nr e u s a b l ep a r t i a ls t r u c t u r e sf r o mal a r g ea m o u n to fC A Dm o
5、 d e l si sp r o p o s e d F i r s t l y，C A Dm o d e l sa r er e p r e s e n t e db yt h ea t t r i b u t e df e a t u r ea d j a c e n tg r a p h(A F A G)T h e n。t h ef r e q u e n ts u b g r a p hm i n i n ga l g o r i t h mi se m p l o y e dt od e t e c tt h ec o m m o nr e u s a b l ep a r t i
6、a ls t r u c t u r e s T h ep a r t i a ls t r u c t u r e sa r eo b t a i n e dt h r o u g hc a n d i d a t eg e n e r a t i o n，c a n d i d a t ep r u n i n g，f r e q u e n c yc o u n t i n ga n dp o s t p r o c e s s i n g E x p e r i m e n t a lr e s u l t ss h o wt h ee f f e c t i v e n e s so
7、 ft h i sa p p r o a c hf o rt h ee x t r a c t i o no ft h er e u s a b l ep a r t i a ls t r u c t u r e si nt h eC A Dm o d e l sw i t hd i f f e r e n ts h a p e s B e s i d e s，i t se f f i c i e n c ym e e t st h er e q u i r e m e n to fe n g i n e e r i n ga p p l i c a t i o nb ya p p l y i
8、 n gm u l t i p l eo p t i m i z a t i o nm e t h o d si ne x t r a c t i o np r o c e s s K e yw o r d s：r e u s a b l e；p a r t i a ls t r u c t u r e；a t t r i b u t e df e a t u r ea d j a c e n tg r a p h；f r e q u e n ts u b g r a p hm i n i n g目前，基于三维模型的产品设计与制造已成为我国制造业的主流模式，由于产品=三维模型具有可视化、数字化
9、和虚拟化等特点，使其成为产品开发各环节(C A D，C A E，C A P P，C A M 等)不可或缺的基础载体研究和统计分析表明，在新产品开发中，约4 0 是重用过去的部件设计，约4 0 是对已有设计部件的微小修改，只有约2 0 是完全新的设计u】而在企业的模型库中，存在很多形状相同、具有重用价值的局部结构，这些局部结构往往隐含在外形完全不同的C A D 模型中，设计人员很难发现不同C A D 模型中隐含的相同形状的局部结构如图1 所示的几个模型都包含一个共同的局部结构，但这些模型在外形上却存在比较大的差异，其中共同的局部结构称为可重用局部结构三维C A D 模型中可重用局部结构是指模型中
10、包含的具有重用价值的局部区域，这些局部区域一般是由若干简单的特征组成，具有一定的复杂性通过对C A D 模型公共可重用局部结构的提取可以发现C A D 模型设计过程中潜在的规律，它可以启发设计灵感、加快设计过程，对于C A D 模型的检索、重用以及基于工程定义口收稿日期：2 0 1 卜0 1 0 7；修回日期：2 0 1 l 0 5 一1 0 基金项目：国家自然科学基金(5 1 0 7 5 3 3 6)；国家“八六三”高技术研究发展计划(2 0 0 7 A A 0 4 2 1 3 7)张开兴(1 9 8 4)男博十研究生。主要研究方向为C A G D、几何造型与处理、模型检索；张树生(1 9
11、5 6 一)男。博士，教授。博士生导师主要研究方向为C I M S，先进制造技术、计算机图形学、C A G D 等；白晓亮(1 9 7 5 一)男。博十讲师主要研究方向为计算机图形学、C A G D、模型检索万方数据第9 期张开兴等：三维C A D 模型公共可重用局部结构自动提取1 S 1 3的结构化工艺信息模型的构建等具有重要的意义。是C A D 领域一个新的研究方向一图1 不同的C A D 模型包曾相同的可重用局部结构对于可重用局部结构的提取，L i 等“3 提出基于特征依赖有向无环图(f e a t u r ed e p e n d e n c yd i r e c t e da c y
12、 c l i cg r a p h，F D A G)，通过去除F D A G 中关键特征节点的形式来提取潜在的可重用匹配区域，并通过对潜在匹配区域的比较来实现C A D 模型的局部检索 B a i 等“1 提出一种面向设计重用的三维c A D模型可重用区域提取及表征方法，通过树匹配算法实现由简单查询实例到完整可重用区域的局部检索以上2 种算法都以特征为基础，因此它们非常适用于三维C A D 模型，但它们最终目的都是通过给定的局部结构检索包含该局部结构的所有模型M a 等基于A G M 算法 6 3 实现了C A D 模型公共结构的提取，该算法在以下2 个方面做了改进：将精确的子图同构算法转化为
13、二维坐标系下面形状描述子的比较；基于累进约束集的方法，通过较少的迭代来产生候选频繁子图。从而提高算法的效率正如文献 5 所指出，由于将精确的子图比较转化成面描述子的比较，因此导致不同的设计结构可能会被认为是相同的；而模型是以面邻接图的形式来表示，其更注重特征的可重用价值；虽然该算法的效率比A G M 算法有了很大的提高，但对于大型模型库来说。c A D模型所包含的面的数量将会非常的庞大，算法的执行时间会非常耗时文献 7 提出一种从模型中提取设计模板的算法，它首先基于切割环收缩算法对模型进行体分割将其分割为若干封闭体，然后将设计模板的提取转化为图的最小描述长度优化问题该算法中的体分割基于尺度函数
14、进行自动分割，分割的结果很难具有工程语义信息并且该算法与可重用局部结构的提取存在本质区别：可重用局部结构提取要求提取的局部结构是在多个模型中同时出现的，而该算法提取的设计模板不从出现的频率来考虑，而是从多模型统一表达、数据压缩角度出发，用模板库统一表达模型；模板不一定是可重用局部结构，可重用局部结构也不一定是模板，它们之间不是等同关系可重用局部结构的提取可以转化为频繁子图挖掘问题，而对于模型的图表示可以用面邻接图和特征邻接图来表示面邻接图可以直接通过提取C A D模型的B-r e p 信息获得，获取比较方便；特征邻接图则可以通过C A D 模型的特征历史树、C S G 树或从特征识别系统中获得
15、由于频繁子图挖掘算法随着图节点数目的增多其执行时间会非常耗时。因此，为了更好地发现c A D 模型中潜在的语义信息，本文以节点数目小的特征邻接图为基础，吸取频繁子图挖掘算法A p r i o r i 算法“3 的思想，设计了一种三维C A D 模型公共可重用局部结构提取算法1 基本概念及算法概述1 1 基本概念在工程上，C A D 模型真正能表达一定语义的最小单位是“特征”，“特征”由一个或多个面构成，并能实现某种特定功能因此，为了满足可重用需求的局部结构，本文以C A D 模型的属性化特征邻接图表示为基础，实现公共可重用局部结构的自动提取定义1 属性化特征邻接图它是一种用于描述C A D 模
16、型内部特征及特征关系的图结构在属性化特征邻接图中，每一个图顶点对应模型中的一个特征，特征的类型作为顶点的属性；顶点与顶点之间的关系对应模型中特征与特征之间的关系常见的关系包括相邻、贴合和相交等本文考虑的特征为具有原子性的基本特征，它们不可再分，主要包括5 大类：凸台、型腔、台阶、孔和槽由于这些特征不可再分且定义明确，因此，三维C A D 模型对应的属性化特征郐接图具有唯一性本文通过以自动识别为主、交互识别为辅获得属性化特征邻接图中的特征节点先利用一种基于图和规则相结合的算法 9 3 实现特征的自动识别，该算法对相交特征识别具有较好的效果并且识别效率较高然后对于模型中少量难以自动识别的特征，则利
17、用人机交互去实现 获得特征节点后，通过自动识别特征之间的邻接关系完成C A D 模型特征邻接万方数据1 5 1 4计算机辅助设计与图形学学报第2 3 卷图的构建图2a 所示为一个C A D 模型特征自动识别实例，对于难以识别的特征可以通过右上角特征a 特征识别交互识别窗体进行识别，图2b 所示为模型对应的的特征邻接图b 特征邻接图图2C A D 模型特征识别及其特征邻接图在逐层构造子图的过程中，基于A p r i o r i 思想的算法，需要考虑图的同构与子图同构问题例如判断候选子图是否存在于候选集中，对候选子图进行频繁度计数等阶段，都要进行图同构判定下面给出图同构及子图同构的定义定义2 图同
18、构对于2 个图G=(y，E)。G 7 一(y 7，E 7)如果存在一一映射函数f 一”：且e 一(q，q)是G 中的一条边，当且仅当e 7 一(。：，。：)是G 的一条边，则称G 和G7 是同构的定义3 子图同构对于2 个图G 一(y，E)。G 7 一(v，E)，如果G 7 有子图G”一(矿，j，矿y 7，C _ E 7，使得与G 同构，则称G 和G 是子图同构的判断2 个图是否同构，本质上就是看是否存在2 个图顶点之间的一个映射，使得2 个图的边在该映射下也保持对应图同构问题的计算复杂度目前还没有彻底解决，它既没有归人N P 完全问题，也没有归人P 问题 1 0 3；而子图同构问题已经被证明
19、为是一个N P 完全问题基于A p r i o r i 思想的算法大多将子图同构问题转化成求解图的规范化标号问题来解决规范化标号通过一些规则减少图的邻接矩阵的穷举次数和概率来提高算法的效率，但这并不能真正降低求解规范化标号的复杂度，求解规范化标号的过程和图同构判定过程是等价的由于图同构算法的复杂度比较高，所以本文将利用一种简单高效的判定方法“”来处理图的同构问题和子图同构问题，在判定的过程中通过图的顶点细分和快速剪枝搜索来提高搜索的效率，以降低算法的复杂度定义4 频繁度给定图数据库集合D 一 g。，g t，g。，对于子图g，令，、f 1，如果g 与g。子图同构 g 毋一1 0 如果g 与g i
20、 中任意子图不同构5设d 一2：g(g，g，)，g，D，则d 是图g 在D 中出现的频率，一即为频繁度定义5 频繁子图给定最小频繁度。若存在子图g 满足d d，则称g 是图数据库集合D 的频繁子图定义6 公共可重用局部结构给定一个C A D模型库，其特征邻接图集合M=G o，G”G。，若存在子图G 是特征邻接图集合M 的频繁子图，则该频繁子图G 在C A D 模型中对应的局部结构称为公共可重用局部结构三维C A D 模型公共可重用局部结构自动提取是指从C A D 模型库中查找出所有的公共可重用局部结构公共可重用局部结构的提取本质上是频繁子图的挖掘，但是与一般的频繁子图挖掘相比，公共可重用局部结
21、构提取的复杂性在于它不仅仅是子图挖掘的过程，同时也包含C A D模型形状结构的比较过程，特别是局部结构的比较1 2 算法概述A p r i o r i 算法口3 是数据挖掘中一类典型的广度优先算法，其采用“产生一测试”思想，即 一频繁子集用于产生k+l 子集，根据“向下包闭”性质进行剪枝，生成+1 候选集；通过对数据库进行扫描判断候选子集中哪些是频繁的，从而产生k+1 频繁子集，直到找不到频繁子集则算法结束目前，主要有2 类经典的基于A p r i o r i 思想的频繁子图挖掘算法，一类是以A G M 6 1 为代表的通过对顶点进行逐层构造求解的算法，一类是以F S G 1“为代表的通过对边
22、的操作进行逐层构造求解的的算法A G M 算法操作对象是顶点，F S G 算法的操作对象是边，而在一个图中边的个数远远的大于顶点的个数，因此F S G万方数据第9 期张开兴，等：三维C A D 模型公共可重用局部结构自动提取算法所产生的候选集的总数目要大于A G M 算法所产生的候选集的总数目，F S G 算法要进行更多的判定来获得频繁子图；在计算候选子图的频繁度时，A G M 算法需要全部扫描数据库，而F S G 算法利用T I D(t r a n s a c t i o ni n d e n t i t i e r)列表 对某个图的所有频繁子图的T I D 表进行求交运算，大大减少了子图同
23、构判定的次数本文将综合A G M 算法和F S G 算法的优点，以特征邻接图中的特征顶点为操作对象，运用多种优化算法来提高算法的效率，从而实现三维C A D 模型公共可重用局部结构的提取在提取公共可重用局部结构的过程中，需要定义一些参数来对算法进行描述，表1 所示为算法使用中的一些参数及其定义表1 参数定义参数定义c k 阶候选频繁子图集合F k女阶频繁子图集合F F所有的频繁子图集合，F F=F 1，F z，p M所有的特征邻接图集合对于候选频繁子图及频繁子图，通过定义一数据结构来对其属性进行描述，数据结构定义如下：S t r u c tG r a p h A t t r i b u t e
24、i n tI D；v e c t o r f e a t u r e A t t；v e c t o r(v e c t o r(i n t)m a t H x；v e c t o r(i n t)c o r e l D；v e c t o r(i n t)s u p p o r t l D；)；其中，I D 表示该子图在C 或F。中的I D 号；f e a t u r e A t t 表示该子图包含的所有特征节点的属性；m a t r i x 表示特征邻接图的邻接矩阵；c o r e l D 表示该子网的所有的核I D 列表，所谓核是指在由是阶频繁子图构造k+l 阶候选子图的过程中，要求2个
25、结合的志阶频繁子图必须包含相同的k 一1 阶频繁子图，k 一1 阶子图称为核；s u p p o r t l D 表示该子图的所有支持图I D 列表，所谓支持图I D 列表是指如果该子图与集合M 巾的某一个图具有子图同构关系，那么就将集合M 中这个图的I D 号存入s u p p o r t l D 中c o r e l D 是在生成候选子图时得到的，而s u p p o r t l D 是在生成频繁子图时得到的频繁子图集生成算法的描述如下：F r e q u e n t s G e n(M，靠，。)输入：图集M，频繁度阈值。输出：所有的频繁子图集F F，F F=F 1，F z，F”B e g
26、 i n初始化F 1，F 2女=2W h i l eP d op“一9“-C a n d i d a t e G e n(P)F o rV 矿“D“d oI fa(g“1)。t h e nP“一P“U 矿”)E n di fE n df o rk=女+1E n dw h i l eP o s t-P r o c e s s i n g(F F)R e t u r nF FE n d首先初始化F 1，和F 2，然后利用一阶和二阶频繁子图循环求解高阶频繁子图(行)，在求解高阶频繁子图的过程中主要包括候选子图产生(行)、候选剪枝和频繁度计数(行)等步骤，最后对频繁子图进行筛选剪枝实现频繁子图提取(行
27、)2 公共可重用局部结构提取2 1 候选集产生候选集产生之前需要对一阶和二阶频繁子图进行初始化一阶频繁子图对应C A D 模型特征节点，可以比较容易获得任取2 个一阶频繁子图对其进行连接，其连接是唯一的；通过遍历图库，生成二阶频繁子图，同时保存二阶频繁子图的1 D，f e a t u r e A t t，m a t r i X，c o r e l D 和s u p p o r t l D 用于生成高阶频繁子图初始化完成后，算法基于k 阶频繁子图来构造k+1 阶候选子图。通过连接2 个包含相同k 一1 阶频繁子图的k 频繁子图来获得k+1 阶候选子图在产生壶+1 阶候选子图过程中，主要有2 个过
28、程：相同k 一1 阶子图的识别和2 个k 频繁子图的连接2 个k 阶子图是否可以连接，取决于它们是否包含相问的七一1 阶子网，因此首先需要识别相同的k 一1 阶子图大多数算法都是先任取一个k 阶子图中的顶点或边进行删除来获得一个k 一1 阶子图，然后万方数据1 5 1 6计算机辅助设计与图形学学报第2 3 卷通过判断该k 一1 阶子图与另外一个k 阶子图是否子图同构以识别2 个k 子图所包含的相同k 一1 阶子图对于包含k 个顶点的子图来说，需要进行k 次子图同构判定才能识别其相同的k 一1 阶子图，其效率比较低下由于k 阶频繁子图属性中记录了其包含的所有的k 一1 阶频繁子图的I D，即c
29、o r e I D，因此可以通过对2 个k 阶频繁子图的c o r e l D 列表的交集获得相同的k 一1 阶频繁子图，从而避免了子图同构的判定其中，2 个k 阶频繁子图可以包含多个相同k 一1 阶子图，其个数等于2 个k 阶频繁子图的c o r e I D 列表交集中元素的个数2 个k 阶频繁子图包含的相同志一1 阶子图识别完成后，通过连接这2 个k 阶频繁子图产生k+1 候选子图2 个k 频繁子图连接可以看作是通过合并2 个(忌最)的邻接矩阵来产生(是+1)(志+1)邻接矩阵的过程令2 个k 阶频繁子图包含的相同k 一1阶频繁子图的邻接矩阵为s。一。，那么2 个k 阶频繁广Cr 1子图的
30、邻接矩阵可以分别表示为X。一l J k-，1”l，l，。一。I S k-，1y：，其中X l，y。为(矗-1)l 维的列向oY iU J量，连接它们产生k+1 候选子图，其邻接矩阵可以P 1甄Y 表示为Z k+1 一I 工 0z M+ll；其中，z 鼬+l 的值lj，7 z 川。o j由x，和Y，所对应的顶点之间是否存在邻接关系来确定这存在2 种情况，一种是存在边相连接，此时斛，一1；一种是不存在边相连接，此时z 鼬+。一0 图3 所示是2 个子图G。和G：的连接过程实例。其中图G。是由口，b，c 和d4 个不同属性的顶点组成，图G z 是由a，b，f 和e4 个不同属性的顶点组成，矩形虚线框
31、内是2 个子图包含的相同低阶子图(由a，b 和c3 个顶点组成)基于相同低阶子图连接这2 个子图来产生候选子图(由口，b，c，d 和e5 个顶点组成)，由于顶点d 和顶点e 之间的邻接关系存在邻接和不邻接2 种情况，因此连接会产生2 个候选子图图3 子图连接过程在子图连接时，可能存在一种特殊的情况：相同忌一1 阶频繁子图自同构，也就是说子图存在多种拓扑等价如图4 所示，当图G。和G：中的顶点f 转变成顶点a 时，由a，a 和b3 个顶点组成的子图存在自同构，会产生2 种类型的候选子图自同构问题是同构问题的一种特殊情况，即当2 个图相同时，图是否存在对自身的一种映射因此，对于相同k 一1 阶频繁
32、子图，首先利用图同构判定方法求出该子图的自同构图，然后再进行连接在志+1 候选子图产生后，将该候选子图与候选图4 自间构万方数据第9 期张开兴。等：三维C A D 模型公共可重用局部结构自动提取1 5 1 7集“中的图比较，若其不存在于候选集中，则将该女+l 阶候选子图添加到候选集p“中，并将合并的2 个女阶频繁子图j D 号添加到该k+1 阶候选子图的c o r e l D 表中；否则只需要将合并的2 个阶频繁子图I D 号添加到该候选子图的c o r e l D 表中，并删除c o r e l D 中的重复项2 2 候选剪枝为了提高算法的效率在频繁度计数前需要对候选子图进行剪枝操作，以减少
33、候选子图的数且基于A p r i o r i 思想的算法使用向下闭合性质作为剪枝策略，向下闭合性质描述如下：性质1 x 是子图，若x 是非频繁的，则任意满足x E z 的子图z 都是非频繁的性质2 x 是子图，若x 是频繁的，则任意满足y x 的子图l，都是频繁的在基于A p r i o r i 思想算法中，首先求出+1 候选子图的所有k 子图，然后利用图同构算法检测这些k 子图是否包含在k 频繁子图中，最后根据性质1 和性质2 进行剪枝操作本文算法不需要对k+1候选子图的所有 子图是否包含在k 频繁子图集中进行同构检测，由于+1 候选子图都有一个c o r e I D 表。该列表记录了候选子
34、图所包含的所有阶频繁子图，因此只需要通过比较+l 候选子图的所有k 子图的个数与c o r e I D 表中k 阶频繁子图的个数是否相等实现剪枝操作若它们的个数相等，则表示该候选子图满足向下闭合的性质；否则进行剪枝，直接删除该候选子图，通过剪枝操作可以大大减少候选子图的数目2 3 频繁度计数当女+1 阶候选子图产生后将对其进行频繁度计数，从而判定该候选子图是不是频繁子图频繁度计数实际上是一个子图同构检测的过程，最简单直接的方法是检测每一个候选子图在图集合M 中的频繁度，但其效率是非常低的由于+1 阶候选子图包含的所有 阶频繁子图都有一个5“拗o r t l D表，该表记录了该频繁子图的支持图集
35、合，因此可以通过对所有k 阶频繁子图的s u p p o r t I D 表求交集来优化频繁度计数，以避免不必要的子图同构检测当交集的个数小于频繁度阈值时，直接对该候选子图进行剪枝，不用执行子图同构检测；否则，只需要检测该候选子图与交集中的图是否同构即可，不用对集合M 中的所有图进行子图同构检测，大大减少了子图同构判定的次数2 4 后处理频繁子图挖掘是一个由低阶到高阶不断进行子图连接的过程，因此在挖掘的过程中获得的频繁子图集中会存在高阶频繁子图包含低阶频繁子图的现象，这些被包含的子图称为冗余频繁子图图5 所示为一个C A D 模型上提取的2 个公共局部结构其中图5b 中的局部结构包含了图5a
36、中的局部结构，图5a 中的局部结构是最终可重用局部结构中的一部分，是冗余的，因此需要对这些冗余的局部结构进行查找并删除莎莎-局部结构1b 局部结柯2图5 同一个模型中提取的不同局部结构查找和删除冗余频繁子图时，首先对P 中所有的k 阶频繁子图的c o r e I D 表求并运算，删除重复项，从而得到所有女阶频繁子图所包含的 一1 阶频繁子图；然后将这些子图从PH 1 中删除，从而得到最终的频繁子图集F F 频繁子图集在C A D 模型中对应的局部结构即为提取的公共可重用局部结构3 算法验证与讨论为了对本文提出的三维c A D 模型公共可重用结构自动提取算法的有效性及性能进行验证和评估，文中以M
37、 i c r o s o f tV i s u a lS t u d i o2 0 0 8 为集成开发环境，并利用1 0 0 个C A D 模型进行测试在不同的a。下。所提取的局部结构的数目如图6 所示，其中红色曲线表示未对冗余子图进行筛选和删除前提取的局部结构数目随O m。变化的情况，蓝色曲线表示冗余子图删除后的情况通过对比发现，冗余子图删除前提取的局部结构的数目要远远的大于冗余子图删除后提取的局部结构的数目，并且随着。的增加，所提取的局部结构的数目是_4l，tH频繁度值口“图6 不同阈值下提取的局部结构数目万方数据计算机辅助设计与图形学学报第2 3 巷逐渐减小的当“。较小时，两者的数目差距
38、较大，随着。的增大，两者的数目差距逐渐缩小例如，当。=2 时，两者数目的差距是1 1 9，而当口一8时，两者数目的差距是1 4 表2 所示为当“。一3 时提取的部分典型的公共可重J j 局部结构，这些典型局部结构隐含在外形完全不同的C A D 模型中，设计人员是很难发现的，而通过本文算法可以有效地对这些局部结构进行提取，C A D 模型中红色标记部分即为提取的公共局部结构表2 公共可重用局部结构提取具有公共局部结构的C A D 模型公共局部结构乡莎莎岁留乡乡绍国夕乡处兰Z j 冬唔为了验证本文算法的时间效率，将从不同。下以及不同模型数目下算法的执行时间2 个方面进行讨论图7 所示为在。不同时算
39、法的执行时间，其中，蓝色曲线表示频繁子图挖掘算法执行时间，红色曲线表示特征邻接图构建及频繁子图挖掘算法执行的总时间由于算法是基于逐层构造的思想，随着。的增大，提取的局部结构的数目是逐渐减小的，因此算法的执行时间也是逐步减少的本文算法与h夕智邑八|)丫鄢占o万方数据第9 期张开妊等：三维C A D 模型公共可重用局部结构自动提取文献E s 3 算法都是基于子图挖掘算法实现公共局部结构的提取文献 5 算法中的模型以面邻接图的形式来表示更注重特征的可重用价值，而本文算法的模型以特征邻接图的形式来表示，更注重特征组合的可重用价值由于频繁子图挖掘随着图节点数目的增多，其算法的执行时间非常的耗时，而本文算
40、法以特征节点为操作对象，相比文献E s 算法极大地减少了图节点数目当。=4，模型数目为1 0 0 时，本文算法执行的总时间(特征邻接图构建时间和频繁子图挖掘算法时间之和)为8 9 7 4s，而文献 5 算法以面节点为操作对象，节点数目较多且算法执行时间也较长图7 不同两值下算法执行时间为了验证不同C A D 模型数目下算法的执行时间，在“。一3 的情况下，将测试库中1 0 0 个C A D 模型随机分为l O 组，每组中模型的数量分别为1 0 个，2 0 个，1 0 0 个，得出算法的执行时间曲线如图8所示图8 不同模型数耳算法执行时间4 结论本文提出一种适合三维C A D 模型的公共可重用局
41、部结构的提取算法，它将公共可重用局部结构的提取转化成频繁子图挖掘问题来解决，通过候选集产生、候选剪枝、频繁度计数及后处理等步骤实现了公共可重用局部结构的提取，并在提取的过程中运用了多种优化手段来提高算法的效率例如利用c o r e l D 列表来实现频繁子图核的识别和剪枝操作利用s u p p o r t l D 列表来优化频繁度计数，利用一种高效的判定方法来实现子图同构的检测等实验结果显示，该算法可以实现隐含在外形完全不同的C A D 模型中的、不易被发现的局部结构的提取，并且算法的效率满足实际应用中的需求其对于c A D模型的检索和重用等具有重要的意义参考文献 R e f e r e n
42、c e s】1 l y e rN，J a y a n t iS。L o uKY，e ta lT h r e e d i m e n s i o n a ls h a p es e a r c h i n g s t a t e 0 1 一t h e a r tr e v i e wa n df u t u r et r e n d s J C o m p u t e r A i d e dD e s i g n 2 0 0 5 3 7(5)：5 0 9-5 3 0C z Q u i n t a n aV R i v e s tL，P e l l e r i nR，e la LW i l lm
43、o d e l b a s e dd e f i n i t i o nr e p l a c ee n g i n e e r i n gd r a w i n g st h r o u g h o u tt h ep r o d u c tl i f e c y e l e?Ag l o b a lp e r s p e c t i v ef r o ma e r o s p a c ei n d u s t r y J C o m p u t e r si nI n d u s t r y。2 0 1 0，6 1(5)：4 9 7-5 0 8 3 L iM。F u hJYH，Z h a
44、n gYF。e ta 1 G e n e r a la n dp a r t i a ls h a p em a t c h i n ga p p r o a c h e so nf e a t u r e b a s e dC A Dm o d e l st os u p p o r te f f i c i e n tp a r tr e t r i e v a l c f P r o c e e d i n g so ft h e2 8 t hC o m p u t e r sa n dI n f o r m a t i o ni nE n g i n e e r i n gC o n
45、f e r e n c e s N e wY o r k：A S M EP r e s s。2 0 0 8 i1 2 1 1 3 0 4 B a iJ，G a oSM tT a n gWH，e ta 1 D e s i g nr e u s eo r i e n t e dp a r t i a lr e t r i e v a lo fC A Dm o d e l s J C o m p u t e r A i d e dD e s i g n 2 0 1 0，4 2(1 2)：1 0 6 9 1 0 8 4 5 M aLJ，H u a n gzD W a n gYW A u t o m a
46、 t i cd i s c o v e r yo fD o m m o nd e s i g ns t r u c t u r e si nC A Dm o d e l s J C o m p u t e r s&G r a p h i c s，2 0 1 0，3 4(5)l5 4 5-5 5 5 6 I n o k u c h iA，W a s h i oT，M o t n d aH C o m p l e t em i n i n go ff r e q u e n tp a t t e m sf r o mg r a h p s：m i n i n gg r a h pd a t a J
47、 M a c h i n eL e a r n i n g，2 0 0 3 5 0(9)：3 2 1-3 5 4 7 M aLJ H u a n gZD W uQS E x t r a c t i n gc o m m o nd e s i g np a t t e r n sf r o mas e to fs o l i dm o d e l s J C o m p u t e r A i d e dD e s i g n 2 0 0 9。4 1(1 2)：9 5 2-9 7 0 8 A g r a w a lR，I m i e l i f i s k iT S w a m iA M i n
48、 i n ga s s o c i a t i o nr u l e sb e t w e e ns e t so fi t e m si nl a r g ed a t a b a s e c P r o c e e d i n g so fA C MS 1 G M O DI n t e r n a t i o n a lC o n f e r e n c eo nM a n a g e m e n to fD a t a N e wY o r k：A C MP r e s s。1 9 9 3；2 0 7-2 1 6 9 S u n i lVB，A g a r w a lR P a n d
49、eSS A na p p r o a c ht or e c o g n i z ei n t e r a c t i o ni e a t u r e sf r o mB R e pC A Dm o d e l so fp r i s m a t i cm a c h i n e dp a r t s u s i n gah y b r i d(g r a p ha n dr u l eb a s e d)t e c h n i q u e 口 C o m p u t e r si nI n d u s t r y，2 0 1 0，6 1(7)：6 8 6 7 0 1E 1 0 W a n
50、gF e i，Z h a n gS h u s h e n g B a iX i a o l i a n g，e ta 1 L o c a lm a t c h i n go f3 DC A Dm o d e lb a s e do ns u b g r a p hi s o m o r p h i s m J J o u r n a lo fC o m p u t e r A i d e dD e s i g nC o m p u t e rG r a p h i c s 2 0 0 8，2 0(8)：1 0 7 8 1 0 8 4(1 nC h i n e s e)(王飞，张树生白晓亮等基