基于子图同构的三维CAD模型局部匹配  

Local Matching of 3D CAD Models Based on Subgraph Isomorphism

作　　者：王飞[1] 张树生[1] 白晓亮[1] 陈书琼[1] 

机构地区：[1]西北工业大学现代设计与集成制造技术教育部重点实验室,西安710072

出　　处：《计算机辅助设计与图形学学报》2008年第8期1078-1084,共7页Journal of Computer-Aided Design & Computer Graphics

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

摘　　要：针对整体相似性检索算法无法实施精确的局部结构匹配的问题,提出一种基于子图同构的三维CAD模型局部结构匹配算法.该算法通过提取CAD模型的B-Rep信息,将其表示为以面作为节点的属性邻接图.在局部匹配过程中,用户输入的局部结构被表示成"子图",待匹配的整体CAD模型被表示成"大图";则在整体CAD模型中,检索局部结构的问题就被转换成在"大图"中寻找同构"子图"的问题.子图同构是NP完全问题,通过利用CAD模型的面特征将图顶点有效细分,并利用已匹配顶点之间的邻接关系动态裁剪搜索空间,实现了快速的同构匹配.实验结果表明,该算法能实现精确的局部结构匹配,并且检索效率能满足实际应用要求.The 3D model retrieval methods considering only global shape features cannot compare models accurately at a local level of detail. A new approach to local matching of CAD models based on subgraph isomorphism is presented. First, an attribute adjacent graph （AAG） for the representation of CAD models is constructed. Then, by taking the local features provided by users as portions of the AAG, and the whole CAD model as the whole AAG, the problem of local feature matching is transformed into that of subgraph isomorphism. Subgraph isomorphism is a NP-complete problem.Rapid isomorphism matching can be realized through the effective classification of the vertices of the graph by using the face features of the CAD model and the dynamic pruning of the search space byusing the adjacent relationship of the matched vertices. Experimental results show that this method supports the precise local matching and the matching efficiency can meet the requirement of the practical retrieval.

关 键 词：CAD模型检索 局部特征 子图同构 

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