基于属性邻接图匹配的三维cad模型搜索方法

基于属性邻接图匹配的三维cad模型搜索方法

0基于图与子图匹配的三维cad模型搜索方法三维辅助设计（commerciad设计，3d），软件pro-e，catia，solid维度等的推广应用，三维图形模型的主要表现形式是三维图形模型，而现存的三维图形模型超过300亿。在CAD领域,用户在产品设计时,需要在整体形状、局部特征和具体型面等不同层次下对三维CAD模型进行相似度比较,以满足不同实际需求下的客户需求。整体形状只能在整体级别上对三维模型进行较为“粗糙”的比较,可用于零件基本类型和主要功能的鉴别;局部特征包含较为详细的局部几何和拓扑信息,可用于部分功能与制造工艺及成本的比较;具体型面可用于详细设计方案的搜索。三维CAD模型搜索的实质是模型匹配,然而三维CAD模型直接匹配并不方便,于是一些三维CAD模型形状描述方法被提出,并被用于三维CAD模型匹配。属性邻接图是描述三维CAD模型最有力的工具之一,与其他形状描述方法相比,该图容易应用三维CAD模型的边界表示(Boundaryrepresentative,B-rep)信息生成,且现有的图与子图匹配方法可用于模型匹配。图与子图匹配方法在人工智能领域有较为广泛的研究。基于图与子图匹配的优化方法,是将图与子图匹配问题转化为约束优化问题求解,用优化目标函数表示搜索目标图和待搜索图之间的顶点和边属性相似程度。常用的优化求解方法包括树搜索方法本文提出一种用拉格朗日乘子法求解属性邻接图匹配的三维CAD模型搜索方法,该方法用拉格朗日乘子法求解属性邻接图匹配,能够对三维CAD模型的相似程度进行排序。该方法的优点是不用搜索整个匹配空间,具有较低的计算复杂度。实验结果表明,采用该方法能够搜索到相似的三维CAD模型。1属性邻接图和属性代码1.1零件中b-rep格式目前大部分CAD系统使用B-rep作为实体的内部结构描述,其优点在于含有较多的面、边、顶点及其相互关系信息,实体与模型之间是一对一的关系。实际应用中,CAD系统零件的模型文件中都保存有B-rep信息,且国际标准的产品模型数据交换标准(STandardfortheExchangeofProductmodeldata,STEP)文件格式也支持B-rep,不同CAD系统的零件模型都可方便地转换为STEP中的B-rep格式。本文中三维CAD模型用属性邻接图G=(V,E)来描述,其中V为图中顶点的集合,模型中每一个面f1.2计算相关系数以确定值来度量本文中搜索目标模型属性邻接图和待搜索模型属性邻接图之间面的相似程度,用它们的面属性编码值来度量。面属性编码由码头和外环边编码组成。码头用来描述面的几何类型和面的凸性,外环边编码描述外环边几何类型、外环边凸性、外环边开始角和终点角等属性。码头Header的具体计算方法如下:式中fType为面的几何类型,con表示面的凸性。外环边编码的具体计算方法如下:1.3属性化邻接图间的相似性本文中搜索目标模型属性化邻接图和待搜索模型属性化邻接图之间边的相似程度,用它们的边属性编码值来度量。边属性编码H(e)描述面邻接关系,即邻接面的几何类型和边的凸性。2面属性匹配矩阵假定两个图P定义1顶点映射匹配矩阵M(M为m×n阶矩阵)是描述搜索目标三维CAD模型和待搜索三维CAD模型的面属性匹配矩阵。图P定义2顶点映射相似程度矩阵Cc(a式中k为外环边数量,定义3边映射相似程度矩阵C3配置目标函数和求解方法3.1建立目标函数为评估搜索目标三维CAD模型与待搜索三维CAD模型的相似程度,通过定义1~定义3建立如方程(1)所示的目标函数该目标函数用搜索目标三维CAD模型和待搜索三维CAD模型的面相似程度和边相似程度描述它们总的映射相似程度,总的相似程度计算方法为3.2基于拉格朗日乘子法的目标函数首先,引入障碍函数xlogx,将其转化为如方程(2)所示的连续优化问题。障碍函数xlogx能保证匹配矩阵M的元素为正。其次,式(2)中匹配矩阵M是不等式约束,为了能运用拉格朗日乘子法求解目标函数,必须将不等式约束转化为等式约束。可通过在搜索目标三维CAD模型属性邻接图P最后,用经典的拉格朗日乘子法求解方程(3)。先将其转化为以下新的无约束条件目标函数。式中μ和v是拉格朗日乘子。令L(M,μ,v)=0,可得方程组定义将式(8)代入式(5)得式中有两个拉格朗日乘子μ和v,初始时设拉格朗日参数为μ拉格朗日乘子μ和v用以下方法更新。如果保持μ不变,则用v更新M,式(9)可变为将式(10)代入式(7)得如果保持v不变,则用μ更新M,式(9)可变为将式(15)代入式(6)得由以上推导可知,方程(1)的约束最优解为式(9),两个拉格朗日参数和的更新实质上可通过式(14)和式(19)来实现。4算法基本步骤及其收敛性4.1提取匹配矩阵及释放内存空间设搜索目标三维CAD模型的属性化邻接图为P步骤1初始化和分配内存空间。(1)参数初始化。(2)边映射相似程度矩阵C1)分配k×l阶矩阵空间,k=|P2)计算C(3)顶点映射相似程度矩阵C2)计算C(4)顶点映射匹配矩阵M分配内存空间和初始化。1)分配(m+1)×(n+1)阶矩阵空间,m=|P2)初始化顶点映射匹配矩阵M。对P(5)分配(m+1)×(n+1)阶临时矩阵M步骤2循环,直到β>β(1)循环,直到步骤3将M转化为0-1正交化矩阵。步骤4释放内存空间。步骤5输出M。4.2可变换一般性下面讨论拉格朗日乘子v和μ的上边界。式(21)可变为不失一般性,假设式(25)可写作由于式(27)可变为:由式(29)和式(28)得:用同样的方法可以得到4.3能量函数及其收敛性分析算法的精确收敛性是很难满足的,下面仅讨论算法的近似收敛性。构建如下的能量函数:边相似程度矩阵C以下是收敛性的证明过程:如果ΔM=M由于由式(9)可得将式(36)代入式(37)得由于ΔM=M如果ΔF>0,则能量函数收敛。由于边相似程度矩阵C因为5面的凸性匹配矩阵初始编码本文在确定面属性编码时,引入了码头Header。在确定顶点映射匹配矩阵M时,只要码头不相等,即两模型面的几何类型和面的凸性两者中有一个不相同,就将它们的顶点映射匹配矩阵元素置为0,从而使初始时顶点映射匹配矩阵的元素尽可能多地为0,在初始时就尽可能多地排除掉不可能匹配的顶点对应关系。在计算边映射相似程度矩阵C每更新一次匹配矩阵M,就要重新计算一次矩阵Q。为降低内存和计算的复杂度,本文计算矩阵Q时,将边相似程度矩阵C6模型搜索效果分析为验证本文提出的搜索方法的有效性,笔者开发了一个基于ACIS(AndyCharleslanue78dssystem)和MicrosoftVisualStudio.NET2003的原型系统。实验用数据库中存放了300个三维CAD模型,这些模型大部分来自NIST公开的设计模型库。用于实验用的微机配置为Intel3.0GHz的CPU,1.0GB内存。在搜索效果方面,从模型库中随机选择了两个三维CAD模型,分别进行整体结构搜索和局部结构搜索的实验,表1所示为实验的搜索结果。从表中可以看出,对于整体结构搜索和局部结构搜索,本文方法不仅能搜索出输入模型本身,还能搜索到许多不同相似程度的CAD模型,并且根据模型的相似程度进行了排序,以满足不同客户的实际需求。在搜索速度方面,本文方法与文献[11]方法进行了搜索速度对比试验。随机选择了11个三维CAD模型,模型的面数量分别为17,25,31,46,56,63,71,85,97,113和155个,将它们放在模型库中搜索输入模型本身。图1所示为试验结果,文献[11]由于采用了顶点细分的方法,面数量较多的模型搜索在速度上有一定优势,但是稳定性要差一些,而顶点细分效果不好的模型的搜索速度明显降低。本文方法的搜索速度总的来说与文献[11]差异不大,但稳定性更好。随着模型面数量的增多,搜索速度有所降低,但不是很明显,从而弥补了一般图与子图匹配精确匹配方法随着模型面数量的增多,搜索时间呈几何级增长的缺陷。7优化求解算法本文提出一种利用拉格朗日乘子法求解属性邻接图匹配的三维CAD模型搜索方法,该方法利用属性邻接图描述搜索目标三维CAD模型和待搜索三维CAD模型,将模型匹配问题转化为属性邻接图匹配问题,用拉格朗日乘子法求解属性化邻接图匹配。本文的优化求解算法与文献[10]有些类似,但在求解方法和具体处理上有所不同或改进,它避免了属性邻接图精确匹配过程的NP复杂性。实验结果表明,该方法能搜索到不同相似程度的模型,并能对相似程度进行排序,搜索效率也能满足实际检索的要求。Header=