CAD模型自动语义标注.pdf

《CAD模型自动语义标注.pdf》由会员分享，可在线阅读，更多相关《CAD模型自动语义标注.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 22 卷第 12 期2010年 12 月计算机辅助设计与图形学学报Journal of Computer?Aided Design&Computer GraphicsVol.22 No.12Dec.2010?收稿日期:2010-06-04;修回日期:2010-08-19.基金项目:国家自然科学基金(50805122);国家?八六三 高技术研 究发展计划(2007AA04Z184).张?欣(1985!),男,博士研究生,主要研究方向为模式识别、三维模型搜索;莫?蓉(1957!),女,博士,教授,博士生导师,主要研究方向为协同设计;宫中伟(1985!),男,博士研究生,主要研究方向为复杂零件的

2、三维建模;连?鑫(1984!),男,硕士研究生,主要研究方向为计算机集成制造.CAD模型自动语义标注张?欣,莫?蓉,宫中伟,连?鑫(西北工业大学现代设计与集成制造技术教育部重点实验室?西安?710072)(zhangx0325 )摘要:为了解决基于关键字检索方式难以获得符合设计意图的 CAD 模型的问题,通过对 CAD 模型自动添加语义标签来改进传统关键字方式检索 CAD 模型的准确性.首先提出一种利用属性图比较 CAD 模型形状相似性的算法,根据图的邻接矩阵及顶点属性构造图顶点集的序列,通过动态编程方法求出图的最大公共子图,得到 CAD 模型之间的形状相似度;然后根据求出的未知模型与已知模型

3、之间的形状相似度,利用概率方法实现对未知模型的自动语义标注.实验结果表明,采用文中方法可以使基于关键字的检索方法具有搜索形状相似模型的功能,在很大程度上改进了传统关键字方式检索 CAD 模型的准确性.关键词:语义标签;自动标注;CAD 模型检索;设计意图中图法分类号:T P391Automatic Semantic Tagging of CAD Models for RetrievalZhang Xin,Mo Rong,Gong Zhongwei,and Lian Xin(K ey L aboratory of Contemp orary Design and Integrated Manuf

4、 acturing Technology,Ministry of Education,N orthwestern PolytechnicalUniversity,Xi?an?710072)Abstract:T he traditional text?based search method for CAD models often obtain searched results thatmay not satisfy with user?s design intent.To solve this problem,a new method is proposed to improvethe pre

5、cision of the text?based search by automatically assigning semantic tags to CAD models.First amethod based on attributed graph for determining the shape similarity of the CAD models isintroduced.A sequence of graph nodes is created based on the adjacent matrix of graph and attributesof nodes.The max

6、imum common graph representing the shape similarity of models is calculated bydynamic programming with the sequence of the graph nodes.Then probability method is used to tagthe CAD models automatically according to the similarity between the models.T he experiments showthat the text?based search for

7、 CAD models with semantic tags could enable the users to more accuratelylocate the models with similar shapes and the user?s design intents can be satisfied.Key words:semantic tag;automatic tagging;CAD model retrieval;design intent?随着企业中 CAD?CAM 系统的普及,三维 CAD模型在工程界得到了越来越广泛的应用.据保守估计,80%以上的新产品都不是从零开始设计

8、的,而是在原有产品模型的基础上修改得到的.CAD 模型蕴含了丰富的设计知识,如何快速、准确地找到符合用户设计意图的三维 CAD 模型,帮助用户重用已有CAD 模型的设计知识,以提高产品设计质量、缩短新产品的设计周期,已成为当前国内外的热点研究课题.迄今为止,企业中 CAD 模型的检索仍然大都停留在基于关键字、编码的传统检索方式上,这种检索方式由于受到命名规则等一些主观因素以及有些复杂 CAD 模型很难用文字来充分描述的影响,使得这种检索方法虽然简单、易于实现,但是检索可靠性不高,因此一些学者提出了基于形状的 CAD 模型检索方法.基于形状的 CAD 模型检索方法可以分为两大类:模型整体形状检索

9、和模型局部形状检索.模型整体形状检索要求检索模型与查询模型整体几何形状相似,模型局部形状检索要求检索模型与查询模型具有某一个或某几个相似局部结构.无论是模型的整体检索或者局部检索,首要问题是比较模型的?相似性,而模型的相似性比较算法主要分为形状描述符的提取以及形状描述符的比较两部分.对于模型整体检索而言,目前三维模型形状描述符的提取方法有三维模型投影方法 1、基于球射线方法 2、形状分布方法 3和 Reeb 图方法 4等.形状描述符的比较方法主要是利用数学变换将形状描述符转换为可比较的向量,如球面调和 2、球面小波 5等.然而上述算法处理的对象是三角网格模型,并没有充分利用 CAD 模型的拓扑

10、结构知识.针对CAD 模型相似性比较的算法有拓扑不变量算法 6、特征向量距离算法 7、模型依赖图近似匹配算法 8以及基于图的序列化算法 9等.基于图的序列化算法检索的结果要优于其他类算法,但是该算法在比较图的相似性时没有考虑模型面之间的位置关系(例如平行、垂直、共轴等),因此该算法还有待进一步改进.而对于模型局部的检索,文献 10 提出了一种尺度空间分解方法来提取模型的局部特征,文献 11 利用带有属性的 Reeb 图来实现模型的局部比较,文献 12 利用子图同构来实现 CAD 模型的局部匹配.文献 10?11 针对的都是三角网格模型,它们都需要基于一个尺度函数对模型进行分解,这样会导致分解的

11、模型子部分并不是 CAD 模型的典型结构特征.文献 12 是一种精确的 CAD 模型局部匹配算法,它可以检索到具有相同结构特征的CAD 模型.但是在实际应用中,模型的局部结构特征不可能完全相同,会受到一些辅助特征(如倒角、倒边等)的影响,因此该算法应用范围非常有限.尽管基于形状的 CAD 模型检索方法可以很好地解决文字难以准确表达 CAD 模型的问题,但是很多 CAD模型虽然形状相似,其功能、用途或者加工方法,也就是 CAD 模型包含的语义知识却相差甚远.例如,对于 CAD 模型上的孔结构来说,尽管孔的尺寸相同,但是由于孔的加工精度不同,那么孔的加工方法则会差别很大.利用关键字可以很好地区分这

12、类包含不同语义知识的 CAD 模型,因此本文希望依据模型形状相似的特性对 CAD 模型自动添加语义标签,使传统基于关键字的检索方式也具有基于模型形状检索的功能,以提高关键字方式检索 CAD 模型的准确性.本文利用属性图来表示CAD 模型的几何和拓扑信息,并采用图的序列化方法比较图的相似性,以得到 CAD 模型之间的形状相似度;其次,依据 CAD 模型之间的相似度,利用概率方法自动标注 CAD 模型.1?CAD模型相似性比较算法属性图可以完全表示 CAD 模型的拓扑和几何信息,那么模型的形状相似性比较就可以转化为图的相似性比较.然而由于图的子图同构问题是一个NP 完全问题,只有对顶点非常少的图才

13、可求解,所以文献 9 提出了利用图的序列化算法来比较属性图的相似性,但是其没有考虑图顶点对应模型面之间的位置关系(例如平行、垂直、共轴等).本文提出了一种 CAD 模型形状相似性比较的新方法,其主要步骤如图 1 所示.图 1?CAD 模型相似性比较算法流程2163第 12期张?欣,等:CAD 模型自动语义标注1.1?CAD 模型的图表示CAD 模型包含了丰富的拓扑和几何信息,如何用可比较的描述符来表示这类信息,已成为 CAD模型相似度比较的首要问题.本文利用属性邻接图(attributed adjacency graph,AAG)来表示 三维CAD 模型,其定义为 G(V,E,?,?).其中,

14、1)V 为图 G 的顶点集,CAD 模型中的每一个面 fi在图G 中都有一个唯一的顶点 Vi与之对应.2)E 为图 G 的边集,对于模型中的任意 2 个相邻面 fi,fj,图 G 都会有唯一的一条边 Ei,j与之对应.3)?为图 G 的顶点属性集,它表示 CAD 模型面的属性,例如面的几何类型(平面、球面、圆柱面等),面的面积,面的边数以及面的边长等.4)?为图 G 的边属性集,它表示 CAD 模型相邻面的位置关系,例如平行、垂直、同轴或者平行等.如图 2 所示,CAD 模型可以用图 2 右边的邻接图 G 来表示.图 2?CAD 模型及其对应 AAG1.2?图的序列化当 CAD 模型用 AAG

15、 表示后,CAD 模型的相似性比较问题就转化为图的子图匹配问题.图的子图同构问题是一个典型的 NP 完全问题,这主要是因为图的顶点是无序的,而顶点在匹配的过程中需要多次反复遍历.如果能够对 AAG 的顶点集建立一个唯一的序列,那么图的子图同构问题就简单了很多.本文试图根据 AAG 的顶点、边的属性以及顶点之间的拓扑关系,对 AAG 的顶点集进行排序.文献 13 提出利用 AAG 的邻接矩阵 A来确定图顶点集的序列,它可以最大程度地保证序列中的相邻顶点在图中具有相邻的边,其定义向量 x 为顶点集的序列,并且该向量 x 满足gmax(x)=|V|-1i=1|V|k=1(A(i,k)+A(i+1,k

16、)x2k;其中 xk为x 的第k 项,表示顶点集 V 的第k 个顶点的序列值.文献 13 指出,当 x 为邻接矩阵 A 的最大特征值对应的特征向量时,g(x)可以取得最大值.通过该方法求出图 G 的序列x,可以最大程度上使序列中的相邻点 Vi,Vi+1对应的 CAD 模型的面相邻,这样可以使序列中的顶点集包含更多的信息,有助于图顶点的匹配.然而文献 13 只利用了图的邻接矩阵计算图的序列,并没有考虑图顶点属性的影响.例如,对于表示 CAD 模型的 AAG 来说,如果两个图的顶点代表着不同的类型(一个为平面、一个为圆柱面),那么这两个顶点肯定不匹配.本文根据这一特性对 x 做出一些修改,使尽可能

17、相同类型的顶点在序列 x 中聚集.如在实验中,由于 CAD 模型包含的平面比较多,因此本文认为对应平面的顶点的序列值要大于对应圆柱面的顶点序列值,其具体排序过程步骤如下:Step1.定义一个链表 L 用来记录 AAG 中顶点的访问序列,其中 Lk为 L 中的第 k 个顶点.初始化 L0=Vi,其中Vi=max(x).Step2.查找顶点 L0在 AAG 中的邻集 NL0=i|(L0,Vi)#E,那么链表 L 中的第二个点 L1=Vi|max(x)V#NL0.Step3.经 过 k 步 迭 代后,链表 长 度为 k+1.如 果k+1=n,其中 n 为属性图的顶点数,则排序结束;否则,求顶点集的补

18、集 C=i|Vi?L Vi#V,令 AAG 新的顶点集V=C,并重复上述计算过程,直到 AAG 中的所有顶点都被访问到.图 3 所示为图 2中的 AAG 按照上述方法的排序结果.图 3?AAG 的排序结果1.3?图的相似性比较本文计算图之间的距离公式为d(G1,G2)=1-2%|mcs(G1,G2)|G1|+|G2|(1)其值越小,表示图越相似.其中,函数|为图的顶点个数;mcs(G1,G2)为图 G1和 G2的最大公共子图,它是式(1)的关键.本文通过动态编程 DP 方法求出排序后的图之间的编辑距离 EditDis(G1,G2),并将式(1)转化为2164计算机辅助设计与图形学学报?第 22

19、 卷d(G1,G2)=1-|G1|+|G2|-EditDis(G1,G2)|G1|+|G2|.?动态编程 DP 方法比较成熟,本文不再赘述.本文在实验中计算 AAG 的编辑距离 EditDis(G1,G2)的伪代码如下:?初始化替换、删除和插入的代价Rep lCost=1,DelCost=1,InsCost=1;?|G1|,|G2|为图 G1,G2的顶点数for i=1:|G1|?for j=1:|G2|?s1(i),s2(j)分别表示排序后的图 G1第 i 个和 G2第 j 个顶点?if s1(i)=s2(j)?if IsCompatible(s1,s2,i,j)?IsCompatible为

20、兼容函数?Repl=0;?else?Repl=ReplCost;?Repl 为替换代价?end?else?Repl=ReplCost;?end?D(i+1,j+1)=min(D(i,j)+Repl),(D(i+1,j)+DelCost),(D(i,j+1)+I nsCost);?endend那么图的编辑距离 EditDis(G1,G2)=D(i+1,j+1),其中函数 IsCompatible 为兼容函数,判断该顶点是否与已有的 mcs(G1,G2)中的顶点保持兼容.例如,假设图 G1,G2的最大公共子图 mcs(G1,G2)=V1i,V1i+1或者 mcs(G1,G2)=V2i,V2i+1,

21、其中f(V1i)=V2i,f(V1i+1)=V2i+1.当遇到一对新的顶点 V1i+2,V2i+2时,函数 IsCompatible 判断顶点 V1i+2与顶点集V1i,V1i+1中的位置关系是否与 V2i+2与顶点集V2i,V2i+1 的位置关系相同.如果相同,则加入这对顶点到图的最大公共子图中,即mcs(G1,G2)=V1i,V1i+1,V1i+2 或者 mcs(G1,G2)=V2i,V2i+1,V2i+2.2?CAD 模型自动标注方法当 CAD 模型之间的距离确定后,模型的自动标记问题就可以简化为聚类问题:已知一些已经标记过的 CAD 模型,根据定义的模型?距离 将未标记模型归为其中某一

22、类,本文采用概率的方法自动标记 CAD模型.本文采用已知一些典型模型或者模型的一些典型结构来对大量的、未知的 CAD 模型进行整体和局部的自动语义标注.假设已知 CAD 模型的标签集为 =!1,!2,&,!n,CAD 模型集=M1,M2,&,Mn,并且模型集中的任一 CAD 模型 Mj标记为!i的概率为p(!i,Mj),那么 CAD 模型的自动标记问题即可表示如下:当遇到一个未知的 CAD模型 M 时,系统用 中的哪些标签来标记该模型,并且该标签标记该模型的概率为多少.该标签属于模型的概率越大,则模型更倾向于该标签的类型.本文以计算模型 M 标记为!i的概率 p(!i,M)为例,说明模型自动语

23、义标记的整个过程.首先根据第 1 节提出的 CAD 模型比较方法来计算模型 M 和Mj之间的近似概率,其定义为 p(M Mj)=(1-D(M,Mj)2;其中 D(M,Mj)为模型 M 和Mj的距离函数,即 D(M,Mj)=d(GM,GMj).既然模型 M 和Mj的相似度为p(M Mj),那么本文有理由认为模型 M 标记为!i的概率为p(!i,M)=p(M Mj)%p(!i,Mj).这是根据单个模型 Mj得出模型 M 标记为!i的概率,其结果可能会具有一定的随机性.如果考虑整个模型集 对M 的影响,那么可以很大程度上提高标记的可靠性,因此本文定义 p(!i,M)=(nj=1p(M Mj)%p(!

24、i,Mj).同理,可以计算模型 M 标记为其他标签的概率.3?实验及结果分析我们以 Design Repository 模型库)中的 CAD模型为研究对象,来验证本文提出的模型比较算法以及 CAD模型自动标注结果.3.1?CAD 模型形状相似度比较根据第 1节提出的CAD 模型相似性比较算法,图 4 列出了 5 类模型的比较结果.可以看出实验结果基本上可以反映出 CAD 模型的相似程度.由于本文在第 1.3 节求图的最大公共子图 mcs(G1,G2)时,兼容函数 IsCompatible 只考虑了 CAD 模型面的类型以及面之间的位置关系,因此该算法目前不能区分具有相同拓扑结构而几何外形有差异

25、的CAD 模型,如图 4中距离为 0 的模型.2165第 12期张?欣,等:CAD 模型自动语义标注)图 4?CAD 模型相似性比较3.2?模型自动语义标注结果本文从 Design Repository 模型库中的一些典型类别中提取一个模型作为已知的标记模型,如图 5a 所示,并对模型库中剩余的 CAD 模型进行自动语义标记;图 5b 所示为一些 CAD 模型自动标注的标签以及该标签属于模型的概率,可以看出,实验结果基本上符合人的主观判断.图 5?CAD 模型自动语义标注3.3?算法的准确性比较本文用查全率?查准率(Recall?Precision)曲线来验证算法的准确性.图 6 所示为本文算

26、法与其他4 类算法的比较,其中 MDG 表示模型依赖图近似2166计算机辅助设计与图形学学报?第 22 卷匹配算法,ITV 表示特征不变量算法,Eigen?Brep表示基于特征向量距离算法(MDG,ITV 和 Eigen?Brep 算法的查全率?查准率曲线来自文献 14),ED表示文献 9 提出的算法.从图 6 中可以看到,本文提出的基于语义标签的 CAD 模型关键字检索方法在准确性方面优于其他 4 类算法.图 6?5 种算法的查准率?查全率曲线比较4?结?语本文通过对 CAD 模型自动添加语义标签,解决了关键字方式难以准确表述 CAD 模型问题,使基于关键字的检索方法同样也可以检索到具有整体

27、或局部相似的 CAD 模型,在很大程度上改进了传统关键字方式检索 CAD 模型的准确性.然而,本文算法仍存在一些不足的地方:在比较 CAD 模型时,本文主要是通过比较模型的拓扑结构,而对模型的几何信息考虑的比较少,这样会造成模型相似性比较的程度相对粗糙,算法的准确性容易受到 CAD模型辅助特征的影响.因此,我们下一步工作的重点就是在 CAD 模型比较时,更多地考虑模型几何信息对模型比较的影响,进一步完善本文算法.参考文献(References):1 Chen D Y,Tian X P,Shen Y T,et al.On visual similaritybased 3D model retri

28、eval J.Computer Graphics Forum,2003,22(3):223?232 2 V ranic D V.An improvement of rotation invariant 3D?shapebased on functions on concentric spheres C?Proceedings ofthe IEEEInternational Conferenceon Image Processing.Washington D C:IEEE Computer Society Press,2003,2:757?760 3 OsadaR,FunkhouserT,Cha

29、zelleB,etal.Shapedistributions J.ACM Transactions on Graphics,2002,21(4):807?832 4 Hilaga M,Shinagawa Y,Kohmura T,et al.T opologymatching for fully automatic similarity estimation of 3D shapes C?Computer Graphics Proceedings,Annual ConferenceSeries,ACM SIGGRAPH.New York:ACM Press,2001:203?212 5 Schr

30、?der P,Sweldens W.Spherical wavelets:efficientlyrepresenting functions on the sphere C?Proceedings of the22ndAnnualConferenceonComputerGraphicsandInteractive T echniques.New York:ACM Press,1995:161?172 6 Mcwherter D,Peabody M,Regli W C,et al.Solid modeldatabases:techniques and empirical results J.Jo

31、urnal ofComputing and Information Science in Engineering,2001,1(4):300?310 7 Peabody M.Finding groups of graphs in databases D.Philadelphia:Drexel University,2002 8 Cicirello V A,Regli W C.An approach to a feature?basedcomparison of solid models of machined parts J.ArtificialIntelligenceforEngineeri

32、ngDesign,AnalysisandManufacturing,2002,16(5):385?399 9 Zhang Xin,Mo Rong,Shi Yuan,et al.String?based CADmodels similarity assessment algorithm J.China MechanicalEngineering,2009,20(20):2435?2439(in Chinese)(张?欣,莫?蓉,石?源,等.基于字符串度量的CAD 模型相似性比较算法 J.中国机械工程,2009,20(20):2435?2439)10 Bespalov D,Regli W C,Sh

33、okoufandeh A.Local featureex traction and matching partial objects J .Computer?AidedDesign,2006,38(9):1020?1037 11 Biasotti S,MariniS,SpagnuoloM,etal.Sub?partcorrespondence by structural descriptors of 3D shapes J.Computer?Aided Design,2006,38(9):1002?1019 12 Wang Fei,Zhang Shusheng,Bai Xiaoliang,et

34、 al.Localmatching of 3D CAD models based on subgraph isomorphism J.JournalofComputer?AidedDesign&ComputerGraphics,2008,20(8):1078?1084(in Chinese)(王?飞,张树生,白晓亮,等.基于子图同构的三维CAD 模型局部匹配 J.计算机辅助设计与图形学学报,2008,20(8):1078?1084)13 Robles?Kelly A,Hancock E R.Graph edit distance fromspectral seriation J.IEEE T ransactions on Pattern Analysisand Machine Intelligence,2005,27(3):365?377 14 Bespalov D,Yiulp C,Regli W C,et al.Benchmarking CADsearch techniques C?Proceedings of ACM Symposium onSolid and Physical M odeling.New York:ACM Press,2005:275?2862167第 12期张?欣,等:CAD 模型自动语义标注