基于启发式图匹配的模板形状搜索方法

doi:10.13196/j.cims.2013.12.sunyuhang.3122.8.20131224

摘要/Abstract

摘要： 为了改进依照模板在三维CAD模型中进行形状搜索的搜索效果和效率,提出一种基于禁忌搜索启发式图匹配的模板形状搜索方法。将B-rep表达的三维形状信息转化为属性图表达;对形成的模型属性图和模板属性图进行迭代的图匹配,在匹配过程中,采用禁忌搜索启发式方法,正向地优化搜索路径,反馈式地修正搜索偏差,同时尽可能地避免重复的尝试,最终快速有效地得到较优的结果。算法分析和实验结果表明,所提方法能够得到合理的非完全图匹配,同时能够将NP复杂度的图匹配问题降低至多项式时间内解决,实现了满足工程需求的模板形状搜索。

关键词: 计算机辅助设计, 形状搜索, 图匹配, 禁忌搜索启发式方法

Abstract: To improve the effectiveness and efficiency of the shape searching in 3D Computer Aided Design (CAD) model by reference to a template,a shape searching method was proposed based on Tabu search heuristic graph matching.After the transition from the shape information in B-rep to the attributed graph representation,the matching between templates attributed graph and model attributed graph was iteratively formed.To get a reasonable matching result quickly and effectively,during the match process the Tabu search heuristic method was used to forward optimize the search path and correct the search bias based on feedback so as to avoid the repetitive trials simultaneously.Algorithm analysis and experimental results showed that the proposed method could obtain the non-complete graph matching reasonably and realize the template shape searching of meeting engineering requirements.

Key words: computer aided design, shape searching, graph matching, tabu search heuristic method

中图分类号:

TP391

孙宇航,黄运保+,陈立平. 基于启发式图匹配的模板形状搜索方法[J]. , DOI: 10.13196/j.cims.2013.12.sunyuhang.3122.8.20131224.

SUN Yu-hang,HUANG Yun-bao+,CHEN Li-ping. Template shape searching method based on heuristic graph matching[J]. , DOI: 10.13196/j.cims.2013.12.sunyuhang.3122.8.20131224.

参考文献

［1］MEHALAWI M E,MILLER R A.A database system of mechanical components based on geometric and topological similarity Part I:representation［J］.Computer-Aided Design,2003,35(1):83-94.
[2]MEHALAWI M E,MILLER R A.A database system of mechanical components based on geometric and topological similarity Part II indexing retrieval matching and similarity assessment［J］.Computer-Aided Design,2003,35(1):95-105.
[3]CONTE D,FOGGIA P,SANSONE C,et al.Thirty years of graph matching in pattern recognition［J］.International Journal of Pattern Recognition and Artificial Intelligence,2004,18(3):265-298.
[4]ULLMANN J R.An algorithm for subgraph isomorphism［J］.Journal of the Association for Computing Machinery,1976,23(1):31-42.
[5]CORDELLA L P,FOGGIA P,SANSONE C,et al.An improve algorithm for matching large graphs［C］// Proceedings of the 3rd IAPR Work-shop Graph-Based Representations in Pattern Recognition.Berlin,Germany:Springer-Verlag,2001:149-159.
[6]SORLIN S,SOLNON C.Reactive tabu search for measuring graph similarity［C］//Proceedings of the 5rd IAPR Work-shop Graph-Based Represen-tations in Pattern Recognition.Berlin,Germany:Springer-Verlag,2005:172-182.
[7]TAO S Q,HUANG Z D,ZUO B Q,et al.Partial retrieval of CAD models based on the gradient flows in Lie group［J］.Pattern Recognition,2012,45(4):1721-1738.
[8]TAO Songqiao,WANG Shuting,ZHENG Tanguang,et al.CAD model retrieval based on inexact graph matching［J］.Journal of Computer-Aided Design & Computer Graphics,2010,22(3):545-552 (in Chinese).［陶松桥,王书亭,郑坛光,等.基于非精确图匹配的 CAD模型搜索方法［J］.计算机辅助设计与图形学学报,2010,22(3):545-552.］
[9]WANG Fei,ZHANG Shusheng,BAI Xiaoliang,et al.Local matching of 3D CAD models based on subgraph isomorphism［J］.Journal of Computer- Aided Design & Computer Graphics,2008,20(8):1078-1084 (in Chinese).［王飞,张树生,白晓亮,等.基于子图同构的三维CAD模型局部匹配［J］.计算机辅助设计与图形学学报,2008,20(8):1078-1084.］
[10]TAO Songqiao,HUANG Zhengdong,ZHENG Tanguang.3D CAD model retrieval based on attributed adjacency graph matching［J］.Computer Integrated Manufacturing Systems,2011,17(4):680-687 (in Chinese).［陶松桥,黄正东,郑坛光.基于属性邻接图匹配的三维CAD模型搜索方法［J］.计算机集成制造系统,2011,17(4):680-687.］

[1]	王耀,王春香,周国勇,纪康辉,刘流,郝林文. 快速成型技术中分层算法的研究综述[J]. 计算机集成制造系统, 2021, 27(3): 828-841.
[2]	何援军. 国产CAD软件重启之路[J]. 计算机集成制造系统, 2021, 27(11): 3057-3075.
[3]	郑华栋,丛明,刘毅,董航,刘冬. 面向增材制造的机器人轨迹自动生成技术[J]. 计算机集成制造系统, 2018, 24(第4): 956-963.
[4]	徐昌鸿,张树生,黄波,李秀玲. 面向数控工艺重用的三维CAD模型局部结构检索[J]. 计算机集成制造系统, 2017, 23(第8期): 1652-1661.
[5]	刘海滨,刘国华,方巍,柴朝华,谢会芹. 以Artifact为中心的业务流程扩展二部图模型及其相似性度量方法[J]. 计算机集成制造系统, 2017, 23(第5期): 1050-1059.
[6]	张旭,张冉,张学昌. 基于辅助装置的多视点云精确配准方法[J]. 计算机集成制造系统, 2014, 20(5): 1029-.
[7]	孙长乐,宁大勇,熊伟,王海涛. 基于特征的工程领域CAD模型检索技术[J]. 计算机集成制造系统, 2014, 20(4): 747-.
[8]	朱林森. 四坐标船模曲面对称加工集成制造系统[J]. , 2013, 19(12): 0-0.
[9]	陈军. 一类带三个形状参数的三角曲面[J]. , 2013, 19 (11 ): 0-0.
[10]	刘海滨,刘国华,黄立明,宋金玲. 以业务单据为中心的业务流程模型聚类及相似性查询方法[J]. 计算机集成制造系统, 2013, 19(08 ): 1810-1821.
[11]	成彬,张树生. 基于视图模型的产品设计信息重用检索系统[J]. 计算机集成制造系统, 2013, 19(08 ): 1975-1983.
[12]	陈成军,洪军,杨国庆. 基于三维CAD模型的复杂机械设备拆装智能诱导系统[J]. 计算机集成制造系统, 2013, 19(08 ): 2026-2035.
[13]	李鹏,张旭,马孜,陈余庆,胡英,刘传龙. 加工中心在线复合式检测定位技术[J]. 计算机集成制造系统, 2013, 19(07 ): 1595-1605.
[14]	程云勇,朱真真,李维亮,张定华. 面向叶片弯扭变形分析的测量采样方法[J]. 计算机集成制造系统, 2013, 19(06 ): 1329-1335.
[15]	王延平,李原,张杰. 三维CAD模型模块划分的蚁群聚类图分割方法[J]. 计算机集成制造系统, 2013, 19(05 ): 926-934.