资源描述：
《CAD模型自动语义标注.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
第22卷第12期计算机辅助设计与图形学学报Vol.22No.122010年12月JournalofComputerAidedDesign&ComputerGraphicsDec.2010CAD模型自动语义标注张欣,莫蓉,宫中伟,连鑫(西北工业大学现代设计与集成制造技术教育部重点实验室西安710072)(zhangx0325@hotmail.com)摘要:为了解决基于关键字检索方式难以获得符合设计意图的CAD模型的问题,通过对CAD模型自动添加语义标签来改进传统关键字方式检索CAD模型的准确性.首先提出一种利用属性图比较CAD模型形状相似性的算法,根据图的邻接矩阵及顶点属性构造图顶点集的序列,通过动态编程方法求出图的最大公共子图,得到CAD模型之间的形状相似度;然后根据求出的未知模型与已知模型之间的形状相似度,利用概率方法实现对未知模型的自动语义标注.实验结果表明,采用文中方法可以使基于关键字的检索方法具有搜索形状相似模型的功能,在很大程度上改进了传统关键字方式检索CAD模型的准确性.关键词:语义标签;自动标注;CAD模型检索;设计意图中图法分类号:TP391AutomaticSemanticTaggingofCADModelsforRetrievalZhangXin,MoRong,GongZhongwei,andLianXin(KeyLaboratoryofContemporaryDesignandIntegratedManufacturingTechnology,MinistryofEducation,NorthwesternPolytechnicalUniversity,Xian710072)Abstract:ThetraditionaltextbasedsearchmethodforCADmodelsoftenobtainsearchedresultsthatmaynotsatisfywithusersdesignintent.Tosolvethisproblem,anewmethodisproposedtoimprovetheprecisionofthetextbasedsearchbyautomaticallyassigningsemantictagstoCADmodels.FirstamethodbasedonattributedgraphfordeterminingtheshapesimilarityoftheCADmodelsisintroduced.Asequenceofgraphnodesiscreatedbasedontheadjacentmatrixofgraphandattributesofnodes.Themaximumcommongraphrepresentingtheshapesimilarityofmodelsiscalculatedbydynamicprogrammingwiththesequenceofthegraphnodes.ThenprobabilitymethodisusedtotagtheCADmodelsautomaticallyaccordingtothesimilaritybetweenthemodels.TheexperimentsshowthatthetextbasedsearchforCADmodelswithsemantictagscouldenabletheuserstomoreaccuratelylocatethemodelswithsimilarshapesandtheusersdesignintentscanbesatisfied.Keywords:semantictag;automatictagging;CADmodelretrieval;designintent随着企业中CADCAM系统的普及,三维CAD在原有产品模型的基础上修改得到的.CAD模型蕴模型在工程界得到了越来越广泛的应用.据保守估含了丰富的设计知识,如何快速、准确地找到符合用计,80%以上的新产品都不是从零开始设计的,而是户设计意图的三维CAD模型,帮助用户重用已有收稿日期:2010-06-04;修回日期:2010-08-19.基金项目:国家自然科学基金(50805122);国家八六三高技术研究发展计划(2007AA04Z184).张欣(1985!),男,博士研究生,主要研究方向为模式识别、三维模型搜索;莫蓉(1957!),女,博士,教授,博士生导师,主要研究方向为协同设计;宫中伟(1985!),男,博士研究生,主要研究方向为复杂零件的三维建模;连鑫(1984!),男,硕士研究生,主要研究方向为计算机集成制造. 第12期张欣,等:CAD模型自动语义标注2163CAD模型的设计知识,以提高产品设计质量、缩短的局部匹配.文献[1011]针对的都是三角网格模新产品的设计周期,已成为当前国内外的热点研究型,它们都需要基于一个尺度函数对模型进行分解,课题.这样会导致分解的模型子部分并不是CAD模型的迄今为止,企业中CAD模型的检索仍然大都典型结构特征.文献[12]是一种精确的CAD模型停留在基于关键字、编码的传统检索方式上,这种检局部匹配算法,它可以检索到具有相同结构特征的索方式由于受到命名规则等一些主观因素以及有些CAD模型.但是在实际应用中,模型的局部结构特复杂CAD模型很难用文字来充分描述的影响,使征不可能完全相同,会受到一些辅助特征(如倒角、得这种检索方法虽然简单、易于实现,但是检索可靠倒边等)的影响,因此该算法应用范围非常有限.性不高,因此一些学者提出了基于形状的CAD模尽管基于形状的CAD模型检索方法可以很好型检索方法.基于形状的CAD模型检索方法可以地解决文字难以准确表达CAD模型的问题,但是分为两大类:模型整体形状检索和模型局部形状检很多CAD模型虽然形状相似,其功能、用途或者加索.模型整体形状检索要求检索模型与查询模型整工方法,也就是CAD模型包含的语义知识却相差体几何形状相似,模型局部形状检索要求检索模型甚远.例如,对于CAD模型上的孔结构来说,尽管孔的尺寸相同,但是由于孔的加工精度不同,那么孔与查询模型具有某一个或某几个相似局部结构.无的加工方法则会差别很大.利用关键字可以很好地论是模型的整体检索或者局部检索,首要问题是比区分这类包含不同语义知识的CAD模型,因此本较模型的相似性,而模型的相似性比较算法主要文希望依据模型形状相似的特性对CAD模型自动分为形状描述符的提取以及形状描述符的比较两添加语义标签,使传统基于关键字的检索方式也具部分.有基于模型形状检索的功能,以提高关键字方式检对于模型整体检索而言,目前三维模型形状描[1]索CAD模型的准确性.本文利用属性图来表示述符的提取方法有三维模型投影方法、基于球射[2][3][4]CAD模型的几何和拓扑信息,并采用图的序列化方线方法、形状分布方法和Reeb图方法等.形法比较图的相似性,以得到CAD模型之间的形状状描述符的比较方法主要是利用数学变换将形状描相似度;其次,依据CAD模型之间的相似度,利用[2]述符转换为可比较的向量,如球面调和、球面小概率方法自动标注CAD模型.[5]波等.然而上述算法处理的对象是三角网格模型,并没有充分利用CAD模型的拓扑结构知识.针对1CAD模型相似性比较算法[6]CAD模型相似性比较的算法有拓扑不变量算法、[7][8]特征向量距离算法、模型依赖图近似匹配算法属性图可以完全表示CAD模型的拓扑和几何[9]以及基于图的序列化算法等.基于图的序列化算信息,那么模型的形状相似性比较就可以转化为图法检索的结果要优于其他类算法,但是该算法在比的相似性比较.然而由于图的子图同构问题是一个较图的相似性时没有考虑模型面之间的位置关系NP完全问题,只有对顶点非常少的图才可求解,所(例如平行、垂直、共轴等),因此该算法还有待进一以文献[9]提出了利用图的序列化算法来比较属性步改进.而对于模型局部的检索,文献[10]提出了一图的相似性,但是其没有考虑图顶点对应模型面之种尺度空间分解方法来提取模型的局部特征,间的位置关系(例如平行、垂直、共轴等).本文提出文献[11]利用带有属性的Reeb图来实现模型的局了一种CAD模型形状相似性比较的新方法,其主部比较,文献[12]利用子图同构来实现CAD模型要步骤如图1所示.图1CAD模型相似性比较算法流程 2164计算机辅助设计与图形学学报第22卷1.1CAD模型的图表示大特征值对应的特征向量时,g(x)可以取得最大CAD模型包含了丰富的拓扑和几何信息,如何值.通过该方法求出图G的序列x,可以最大程度上用可比较的描述符来表示这类信息,已成为CAD使序列中的相邻点Vi,Vi+1对应的CAD模型的面模型相似度比较的首要问题.本文利用属性邻接图相邻,这样可以使序列中的顶点集包含更多的信息,(attributedadjacencygraph,AAG)来表示三维有助于图顶点的匹配.然而文献[13]只利用了图的CAD模型,其定义为G(V,E,,).其中,邻接矩阵计算图的序列,并没有考虑图顶点属性的1)V为图G的顶点集,CAD模型中的每一个影响.例如,对于表示CAD模型的AAG来说,如果面fi在图G中都有一个唯一的顶点Vi与之对应.两个图的顶点代表着不同的类型(一个为平面、一个2)E为图G的边集,对于模型中的任意2个相为圆柱面),那么这两个顶点肯定不匹配.本文根据邻面fi,fj,图G都会有唯一的一条边Ei,j与之对应.这一特性对x做出一些修改,使尽可能相同类型的顶点在序列x中聚集.如在实验中,由于CAD模型3)为图G的顶点属性集,它表示CAD模型包含的平面比较多,因此本文认为对应平面的顶点面的属性,例如面的几何类型(平面、球面、圆柱面的序列值要大于对应圆柱面的顶点序列值,其具体等),面的面积,面的边数以及面的边长等.排序过程步骤如下:4)为图G的边属性集,它表示CAD模型相Step1.定义一个链表L用来记录AAG中顶点的访问邻面的位置关系,例如平行、垂直、同轴或者平行等.序列,其中Lk为L中的第k个顶点.初始化L0=Vi,其中如图2所示,CAD模型可以用图2右边的邻Vi=max(x).接图G来表示.Step2.查找顶点L0在AAG中的邻集NL={i|(L0,0Vi)#E},那么链表L中的第二个点L1={Vi|max(x)∃V#NL}.0Step3.经过k步迭代后,链表长度为k+1.如果k+1=n,其中n为属性图的顶点数,则排序结束;否则,求顶点集的补集C={i|ViL∃Vi#V},令AAG新的顶点集V=C,并重复上述计算过程,直到AAG中的所有顶点都被访问到.图2CAD模型及其对应AAG图3所示为图2中的AAG按照上述方法的排序结果.1.2图的序列化当CAD模型用AAG表示后,CAD模型的相似性比较问题就转化为图的子图匹配问题.图的子图同构问题是一个典型的NP完全问题,这主要是因为图的顶点是无序的,而顶点在匹配的过程中需要多次反复遍历.如果能够对AAG的顶点集建立一个唯一的序列,那么图的子图同构问题就简单了很多.本文试图根据AAG的顶点、边的属性以及顶图3AAG的排序结果点之间的拓扑关系,对AAG的顶点集进行排序.1.3图的相似性比较文献[13]提出利用AAG的邻接矩阵A来确定本文计算图之间的距离公式为图顶点集的序列,它可以最大程度地保证序列中的2%|mcs(G1,G2)|d(G1,G2)=1-(1)相邻顶点在图中具有相邻的边,其定义向量x为顶|G1|+|G2|点集的序列,并且该向量x满足其值越小,表示图越相似.其中,函数||为图的顶点|V|-1|V|2个数;mcs(G1,G2)为图G1和G2的最大公共子图,gmax(x)=∀∀(A(i,k)+A(i+1,k))xk;i=1k=1它是式(1)的关键.本文通过动态编程DP方法求出其中xk为x的第k项,表示顶点集V的第k个顶点排序后的图之间的编辑距离EditDis(G1,G2),并将的序列值.文献[13]指出,当x为邻接矩阵A的最式(1)转化为 第12期张欣,等:CAD模型自动语义标注2165|G1|+|G2|-EditDis(G1,G2)标记CAD模型.d(G1,G2)=1-.|G1|+|G2|本文采用已知一些典型模型或者模型的一些动态编程DP方法比较成熟,本文不再赘述.本典型结构来对大量的、未知的CAD模型进行整体文在实验中计算AAG的编辑距离EditDis(G1,G2)和局部的自动语义标注.假设已知CAD模型的标12n1的伪代码如下:签集为={!,!,&,!},CAD模型集∀={M,初始化替换、删除和插入的代价2njM,&,M},并且模型集中的任一CAD模型M标ReplCost=1,DelCost=1,InsCost=1;记为!i的概率为p(!i,Mj),那么CAD模型的自动|G1|,|G2|为图G1,G2的顶点数标记问题即可表示如下:当遇到一个未知的CADfori=1:|G1|模型M时,系统用中的哪些标签来标记该模型,forj=1:|G2|并且该标签标记该模型的概率为多少.该标签属于s1(i),s2(j)分别表示排序后的图G1第i个和G2模型的概率越大,则模型更倾向于该标签的类型.第j个顶点ii本文以计算模型M标记为!的概率p(!,M)ifs1(i)==s2(j)为例,说明模型自动语义标记的整个过程.首先根据ifIsCompatible(s1,s2,i,j)第1节提出的CAD模型比较方法来计算模型M和IsCompatible为兼容函数jjM之间的近似概率,其定义为p(M∋M)=(1-Repl=0;j2jjD(M,M));其中D(M,M)为模型M和M的距else离函数,即D(M,Mj)=d(GjRepl=ReplCost;Repl为替换代价M,GM).既然模型M和jjendM的相似度为p(M∋M),那么本文有理由认为模ielse型M标记为!的概率为ijijRepl=ReplCost;p(!,M)=p(M∋M)%p(!,M).jiend这是根据单个模型M得出模型M标记为!的概D(i+1,j+1)=min((D(i,j)+Repl),(D(i+1,j)+率,其结果可能会具有一定的随机性.如果考虑整个DelCost),(D(i,j+1)+InsCost));模型集∀对M的影响,那么可以很大程度上提高标endni记的可靠性,因此本文定义p(!,M)=(p(M∋endj=1jijM)%p(!,M).同理,可以计算模型M标记为其那么图的编辑距离EditDis(G1,G2)=D(i+他标签的概率.1,j+1),其中函数IsCompatible为兼容函数,判断该顶点是否与已有的mcs(G1,G2)中的顶点保持兼3实验及结果分析容.例如,假设图G1,G2的最大公共子图mcs(G1,1122G2)={Vi,Vi+1}或者mcs(G1,G2)={Vi,Vi+1},其)1212我们以DesignRepository模型库中的CAD中f(Vi)=Vi,f(Vi+1)=Vi+1.当遇到一对新的顶121模型为研究对象,来验证本文提出的模型比较算法点Vi+2,Vi+2时,函数IsCompatible判断顶点Vi+2与顶点集{V112以及CAD模型自动标注结果.i,Vi+1}中的位置关系是否与Vi+2与顶点集{V223.1CAD模型形状相似度比较i,Vi+1}的位置关系相同.如果相同,则加入这对顶点到图的最大公共子图中,即mcs(G1,G2)=根据第1节提出的CAD模型相似性比较算法,11122图4列出了5类模型的比较结果.可以看出实验结{Vi,Vi+1,Vi+2}或者mcs(G1,G2)={Vi,Vi+1,2果基本上可以反映出CAD模型的相似程度.由于Vi+2}.本文在第1.3节求图的最大公共子图mcs(G1,G2)2CAD模型自动标注方法时,兼容函数IsCompatible只考虑了CAD模型面的类型以及面之间的位置关系,因此该算法目前不当CAD模型之间的距离确定后,模型的自动能区分具有相同拓扑结构而几何外形有差异的标记问题就可以简化为聚类问题:已知一些已经标CAD模型,如图4中距离为0的模型.记过的CAD模型,根据定义的模型距离将未标记模型归为其中某一类,本文采用概率的方法自动)www.designrepository.com 2166计算机辅助设计与图形学学报第22卷图4CAD模型相似性比较3.2模型自动语义标注结果动语义标记;图5b所示为一些CAD模型自动标注本文从DesignRepository模型库中的一些典的标签以及该标签属于模型的概率,可以看出,实验型类别中提取一个模型作为已知的标记模型,如结果基本上符合人的主观判断.图5a所示,并对模型库中剩余的CAD模型进行自图5CAD模型自动语义标注3.3算法的准确性比较来验证算法的准确性.图6所示为本文算法与其他本文用查全率查准率(RecallPrecision)曲线4类算法的比较,其中MDG表示模型依赖图近似 第12期张欣,等:CAD模型自动语义标注2167匹配算法,ITV表示特征不变量算法,EigenBrep[3]OsadaR,FunkhouserT,ChazelleB,etal.Shapedistributions[J].ACMTransactionsonGraphics,2002,21表示基于特征向量距离算法(MDG,ITV和Eigen(4):807832Brep算法的查全率查准率曲线来自文献[14]),ED[4]HilagaM,ShinagawaY,KohmuraT,etal.Topology表示文献[9]提出的算法.从图6中可以看到,本文matchingforfullyautomaticsimilarityestimationof3Dshapes提出的基于语义标签的CAD模型关键字检索方法[C]ComputerGraphicsProceedings,AnnualConference在准确性方面优于其他4类算法.Series,ACMSIGGRAPH.NewYork:ACMPress,2001:203212[5]SchrderP,SweldensW.Sphericalwavelets:efficientlyrepresentingfunctionsonthesphere[C]Proceedingsofthe22ndAnnualConferenceonComputerGraphicsandInteractiveTechniques.NewYork:ACMPress,1995:161172[6]McwherterD,PeabodyM,RegliWC,etal.Solidmodeldatabases:techniquesandempiricalresults[J].JournalofComputingandInformationScienceinEngineering,2001,1(4):300310[7]PeabodyM.Findinggroupsofgraphsindatabases[D].图65种算法的查准率查全率曲线比较Philadelphia:DrexelUniversity,2002[8]CicirelloVA,RegliWC.Anapproachtoafeaturebasedcomparisonofsolidmodelsofmachinedparts[J].Artificial4结语IntelligenceforEngineeringDesign,AnalysisandManufacturing,2002,16(5):385399本文通过对CAD模型自动添加语义标签,解[9]ZhangXin,MoRong,ShiYuan,etal.StringbasedCAD决了关键字方式难以准确表述CAD模型问题,使modelssimilarityassessmentalgorithm[J].ChinaMechanical基于关键字的检索方法同样也可以检索到具有整体Engineering,2009,20(20):24352439(inChinese)(张欣,莫蓉,石源,等.基于字符串度量的CAD模型或局部相似的CAD模型,在很大程度上改进了传相似性比较算法[J].中国机械工程,2009,20(20):2435统关键字方式检索CAD模型的准确性.然而,本文2439)算法仍存在一些不足的地方:在比较CAD模型时,[10]BespalovD,RegliWC,ShokoufandehA.Localfeature本文主要是通过比较模型的拓扑结构,而对模型的extractionandmatchingpartialobjects[J].ComputerAided几何信息考虑的比较少,这样会造成模型相似性比Design,2006,38(9):10201037[11]BiasottiS,MariniS,SpagnuoloM,etal.Subpart较的程度相对粗糙,算法的准确性容易受到CADcorrespondencebystructuraldescriptorsof3Dshapes[J].模型辅助特征的影响.因此,我们下一步工作的重点ComputerAidedDesign,2006,38(9):10021019就是在CAD模型比较时,更多地考虑模型几何信[12]WangFei,ZhangShusheng,BaiXiaoliang,etal.Local息对模型比较的影响,进一步完善本文算法.matchingof3DCADmodelsbasedonsubgraphisomorphism[J].JournalofComputerAidedDesign&ComputerGraphics,2008,20(8):10781084(inChinese)参考文献(References):(王飞,张树生,白晓亮,等.基于子图同构的三维CAD模型局部匹配[J].计算机辅助设计与图形学学报,2008,20[1]ChenDY,TianXP,ShenYT,etal.Onvisualsimilarity(8):10781084)based3Dmodelretrieval[J].ComputerGraphicsForum,[13]RoblesKellyA,HancockER.Grapheditdistancefrom2003,22(3):223232spectralseriation[J].IEEETransactionsonPatternAnalysis[2]VranicDV.Animprovementofrotationinvariant3DshapeandMachineIntelligence,2005,27(3):365377basedonfunctionsonconcentricspheres[C]Proceedingsof[14]BespalovD,YiulpC,RegliWC,etal.BenchmarkingCADtheIEEEInternationalConferenceonImageProcessing.searchtechniques[C]ProceedingsofACMSymposiumonWashingtonDC:IEEEComputerSocietyPress,2003,2:SolidandPhysicalModeling.NewYork:ACMPress,2005:757760275286
