基于非精确图匹配的CAD模型搜索方法  

CAD Model Retrieval Based on Inexact Graph Matching

作　　者：陶松桥[1,2] 王书亭[1] 郑坛光[1] 黄正东[1] 

机构地区：[1]华中科技大学国家CAD支撑软件工程技术研究中心,武汉430074 [2]武汉交通职业学院机电工程系,武汉430065

出　　处：《计算机辅助设计与图形学学报》2010年第3期545-552,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60573178;50875092);国家"八六三"高技术研究发展计划(2007AA04Z136)

摘　　要：为了弥补现有的三维CAD模型搜索方法难以搜索到不同近似程度的相似模型的缺陷,提出一种基于面属性化邻接图非精确匹配的CAD模型搜索方法.首先提取CAD模型中的B-rep信息将CAD模型转化为面属性化邻接图;然后计算目标模型与被搜索模型的面属性化邻接图之间的顶点相容程度矩阵和边相容程度矩阵,并由此建立2个模型相似程度的度量作为选择不同顶点匹配矩阵M的优化目标函数;在对匹配矩阵M进行连续化松弛后,运用Sinkhorn行列交替规范化方法求解匹配优化问题.实验结果表明,采用该方法能够搜索到不同近似程度的相似模型;并且由于避免了具有NP复杂性的精确图匹配过程,检索效率也能满足实际要求.In this paper, a CAD model retrieval method based on inexact graph matching is presented in order to resolve the problem that the exact graph matching is unable to support the similar model retrieval. First, a representation of face attributed relational graph （ARG） for each CAD model is extracted from its B-rep model. Then, the vertex compatibility matrix and edge compatibility matrix between the ARGs of the target and searched model are calculated, and the measure of the similarity between the two models is created from the compatibility matrices, which serves as the objective function for optimally selecting vertex mapping matrix M between the two models. Finally, the optimal vertex mapping matrix M is found using Sinkhorn＇s alternative normalization method for M＇s rows and columns after relaxing M＇s elements to be continuous. Experimental results show that this method is able to support the inexact model retrieval and its efficiency meets the requirement of practical applications.

关 键 词：模型搜索 非精确图匹配 属性化邻接图 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]