摘要
在CAD领域,三维CAD模型的相似评价技术可以有效地支持对三维CAD模型的检索,达到重用已有设计,大幅缩短产品开发周期,降低产品开发成本的目的,近年来成为了大家关注的热点。同时,由于三维CAD模型具有拓扑结构、几何形状、高层语意等方面具有丰富的信息,因此往往选用能携带大量结构信息和属性信息的属性图作为三维CAD模型在计算机里的表征。然而,传统图匹配是NP完全问题,其复杂度为指数级,无法达到人们的实际应用要求,因此以高效图匹配为基础的三维CAD模型相似评价受到研究人员的关注,本文正是在这一背景下对基于高效图匹配的三维CAD模型相似评价展开研究。
本文的主要工作包括以下几个方面:
提出一种基于改进的随机漫步图匹配的三维零件模型相似评价。该相似评价在保持传统随机漫步图匹配高效性的基础上将其推广到三维零件模型的特征依赖图,有效地支持三维零件模型的快速检索。该方法通过图转换函数消除特征依赖图的末端节点;通过概率归一化函数消除特征间的不合理干扰;通过对节点进行分类缩小匹配空间,提升效率。
提出一种基于树图匹配的三维装配体模型相似评价。该相似评价综合考虑了装配体模型装配构成关系、装配约束关系和零件本身属性三方面的信息,以树匹配和小规模的图匹配代替大规模的图匹配实现了对三维装配体模型的高效相似评价。该方法通过装配构成树表征装配体的装配构造关系;通过装配约束图表征装配体的装配约束关系;通过零件节点的属性表征零件本身的属性;通过装配构成树的匹配结果指导装配约束图的匹配,提高匹配效率。
基于以上研究成果,本文在本研究小组的面向设计重用的三维CAD模型检索原型系统ZD-DRCMRS(ZheDa Design Reuse Oriented 3D CAD Model RetrievalSystem)中以功能模块的形式实现了上述算法,并通过实验初步证实了其合理性和可行性。
The similarity assessment of three-dimensional CAD models can effectively support the retrieval of three-dimensional CAD model and thus reuse existing designs significantly, shorten product development cycles and reduce product development costs. Because of the topology, geometry and high-level semantics information contained by three-dimensional CAD models, attributed graphs are often used as the representation of three-dimensional CAD models. However, the traditional graph matching is NP-complete problem and their complexity is exponential, can not meet the practical application requirements. Therefore how to evaluate the similarity between three-dimensional CAD models efficiently based on graph matching is an imperative task for design knowledge reuse. In this thesis, the approach to assessing the similarity between two three-dimensional CAD models based on efficient graph matching is discussed.
The main contents are presented as follows:
A new similarity assessment method for three-dimensional models based on enhanced random-walks graph matching is proposed. In this approach, the traditional random-walk graph matching is extended to the feature dependency graph whereas its efficiency is maintained. Graph translation function is used to eliminate the sink nodes in feature dependency graph. Probability normalization function is used to eliminate the unreasonable disturbance among features. Classification of nodes is used to reduce the matching space and improve the efficiency.
A new three-dimensional assembly model similarity assessment based on tree-graph matching is proposed. In this approach assembly construct relationship, assembly constraint relationship and parts attribute are all considered. A tree and a smaller graph are provided to instead the large graph of traditional JNC representation. Assembly construct tree is used to represent assembly construct relationship. Assembly constraint graph is used to represent assembly constraint relationship. The nodes attributes are used to represent the parts attribute. Assembly constraint graph matching efficiency is improved by the guidance provided by assembly construct tree matching results.
Based on above results, a similarity assessment function module is implemented and embedded into the design reuse-oriented three-dimensional CAD model retrieval prototype system ZD-DRCMRS (ZheDa Design Reuse Oriented 3D CAD Model Retrieval System) developed by our research team. Some tests on this function module with some CAD models are conducted, and the results show the validity and the efficiency of the proposed approaches.
引文
[1] William Leizerowicz, Taner Bilgic, Jinxin Lin, and Mark S. Fox. Collaborative Design using WWW. Proceedings of WET-ICE, 1996, University of West Virginia.
[2] T.G. Gunn. The mechanization of design and manufacturing. Scientific American, 1982, 247(3): 114-130.
[3] A.S. Deshmukh, A.G. Banerjee, S.K. Gupta, and R.D. Sriram. Content-based assembly search: A step towards assembly reuse. Computer-Aided Design, 2008,40(2):244-261.
[4] B.T. Messmer and H Bunke. Subgraph isomorphism in polynomial time. Technical Report IAM-95-003, 1995, University of Bern.
[5] E.T. Copson. Metric spaces. Cambridge University Press, 1968, United Kingdom.
[6] Y. Rubner, C. Tomasi, and L. J. Guibas. A metric for distributions with applications to image databases. IEEE International Conference on Computer Vision, 1998, Bombay, India: 59-66.
[7] J. W. H. Tangelder and R. C. Veltkamp. Polyhedral model retrieval using weighted point sets. International Journal of Image and Graphics, 2003, 3(1): 1-21.
[8] James Gain and James Scott. Fast polygon mesh querying by example. ACM SIGGRAPH 99 Conference abstracts and applications, 1999, Los Angeles.
[9] Nilesh V. Patel and Ishwar K. Sethi. Video shot detection and Characterization for video databases. Pattern Recognition, 1997, 30(4): 583-592.
[10] R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin. Matching 3D models with shape distributions. Proceedings of the International Conference on Shape Modeling & Applications, 2001,Genova, Italy: 154-166.
[11] R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin. Shape distributions. ACM Transactions on Graphics, 2002, 21(4): 807-832.
[12] Hou Xin, Z Xutang, and Liu Wenjian. Using enhanced shape distributions to compare CAD models. Proceedings of Paeific-Rim Conference on Multimedia, 2007, Hong Kong: 358-362.
[13] Wang Hongshen, Zhang Shusheng, Zhang Kaixing, and Bai Xiaoliang. A shape distributions retrieval algorithm of 3D CAD models based on normal direction. The 9th International Conference for Young Computer Scientists, 2008, Hunan, China: 891-896.
[14] Xiang Pan, Yin Zhang, Sanyuan Zhang, and Xiuzi Ye. Radius-Normal Histogram and Hybrid Strategy for 3D Shape Retrieval. Proceedings of the International Conference on Shape Modeling and Application 2005, 2005, Washington DC: 374-379,
[15] D.V. Vranic and D Saupe. 3D shape descriptor based on 3D Fourier transform. Proc. of the EURASIP Conference on Digital Signal Processing for Multimedia Communications and Services (ECMCS '01), 2001, Budapest, Hungary: 271-274.
[16] H. Dutagaci, B. Sankur, and Y. Yemez. Transform-based Methods for Indexing and Retrievalof 3D Objects. Proceedings of the 5th Int'l Conf. on 3-D Digital Imaging and Modeling (3DIM 2005), 2005 Cambridge: 188-195.
[17]D Bespalov, WC Regli, and A Shokoufandeh. Reeb graph based shape retrieval for CAD. Proc. of ASME DETC 2003 Computers and Information in Engineering (CIE), 2003, Chicago, Illinois, United States.
[18] J. Bai, Y. S. Liu, and S. M. Gao. Multi-mode Solid Model Retrieval Based on Partial Matching. The 10th IEEE International Conference on Computer-Aided Design and Computer Graphics, 2007, Beijing, China.
[19] Mohamed El-Mehalawi and R. Allen Miller. A database system of mechanical components based on geometric and topological similarity. Part I: representation. Computer-Aided Design, 2001, 35(1): 83-94.
[20] VA Cicirello and WC Regli. Resolving non-uniqueness in design feature histories. Proceedings of the fifth ACM symposium on Solid modeling and applications 1999. New York, USA: 76-84.
[21] V. Cicirello and W. C. Regli. Machining feature-based comparisons of mechanical parts. International Conference on Shape Modeling & Applications, 2001, Genova, Italy: 176-185.
[22] Madhumati Ramesh, Derek Yip-Hoi, and Debasish Dutta. Feature Based Shape Similarity Measurement for Retrieval of Mechanical Parts. Journal of Computing and Information Science in Engineering, 2001, 1(3): 245-256.
[23] See Kim Yong, Hee Jung Yong, Gu kang Byung, and Min Rho Hyung. Feature-based part similarity assessment method using convex decomposition. Proc. of ASME DETC 2003 Computers and Information in Engineering (CIE), 2003, Chicago, Illinois, United States.
[24] Min Li, J. Y. H. Fuh, Y. F. Zhang, and Z. M. Qiu. General and Partial Shape Matching Approaches on Feature-Based CAD Models to Support Efficient Part Retrieval. ASME Conference Proceedings, 2008, New York: 121-130.
[25] Shekhar Iyer and Rakesh Nagi. Automated retrieval and ranking of similar parts in agile manufacturing. HE Transactions, 1997,29: 859-876.
[26] G. Srinivas, E. D. Fasse, and M. M. Marefat. Retrieval of similarly shaped parts from a CAD database. Systems, Man, and Cybernetics, 1998. 1998 IEEE International Conference, 1998, Annapolis: 2809-2814.
[27] A. V. Aho, J. E. Hopcroft and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison Wesley, 1974.
[28] J. E. Hopcroft and J. Wong. Linear time algorithm for isomorphism of planar graphs. Proc. 6th Annual ACM Symp, Theory of Computing, 1974.
[29] E. M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computation System Science, 1982, 25: 42-65.
[30] J. R. Ullman. An algorithm for subgraph isomorphism. J. Assoc. Comput., 1976, 23: 31-42.
[31] D. E. Ghahraman, A. K. C. Wong and T. Au. Graph monomorphism algorithms. Trans. Syst. Man Cybern, 1980,10: 189-197.
[32] L. P. Cordelia, P. Foggia, C. Sansone and M. Vento. Fast graph matching for detecting CAD image components. Proc. 15th Int. Conf. Pattern Recognition, 2000, Atlantic: 1034-1037.
[33] L. P. Cordelia, P. Foggia, C. Sansone, F. Tortorella and M. Vento. Graph matching: a fast algorithm and its evaluation. Proc. 14th Int. Conf. Pattern Recognition, 1998, Brisbane: 1582-1584.
[34] L. P. Cordelia, P. Foggia, C. Sansone and M. Vento. An improved algorithm for matching large graphs. Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition, 2001, Ischia: 149-159.
[35] B. D. McKay. Practical graph isomorphism. Congressus Numerantium, 1981, 30: 45-87.
[36] J. McGregor. Backtrack search algorithm and the maximal common subgraph problem. Software-Practice and Experience, 1982,12: 23-34.
[37] J. Larrosa and G. Valiente. Constraint satisfaction algorithms for graph pattern matching. Math. Struct. Comput. Sci, 2002, 12:403-422.
[38] H. Bunke and B. T. Messmer. Recent advances in graph matching. Int. J. Patt. Recogn. Artif. Intell, 1997, 11:169-203.
[39] W. H. Tsai and K. S. Fu. Error-correcting isomorphisms of attributed relational graphs for pattern analysis. IEEE Trans. Syst. Man Cybern, 1975, 9: 757-768.
[40] W. H. Tsai and K. S. Fu. Subgraph error-correcting isomorphisms for syntactic pattern recognition. IEEE Trans. Syst. Man Cybern, 1983, 13: 48-61.
[41] A. K. C. Wong, M. You and S. C. Chan. An algorithm for graph optimal mono- Morphism. IEEE Trans. Syst. Man Cybern, 1990, 20: 628-638.
[42] A. Sanfeliu and K. S. Fu. A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern, 1983,13: 353-363.
[43] D. E. Ghahraman, A. K. C. Wong and T. Au. Graph optimal monomorphism algorithms. IEEE Trans. Syst. Man Cybern, 1980,10:181-188.
[44] L. G. Shapiro and R. M. Haralick. Structural descriptions and inexact matching. IEEE Trans. Patt. Anal. Mach. Intell, 1981, 3: 504-519.
[45] A. C. M. Dumay, R. J. van der Geest, J. J. Gerbrands, E. Jansen and J. H. C. Reiber. Consistent inexact graph matching applied to labelling coronary segments in arteriograms. Proc. Int. Conf. Pattern Recognition, 1992, Kyoto: 439-442.
[46] J D Conte, P Foggia, C Sansone and M Vento. Thirty years of graph matching in pattern recognition. International Conference of Pattern Recognition, 2004, Artif.
[47] Gori, M. Maggini and L.Sarti. Exact and approximate graph matching using random walks. Pattern Analysis and Machine Intelligence, IEEE Transactions, 2005,27: 1100-1 111.
[48] K. Pearson. The problem of the random walk. Nature, 1905, 72:294.
[49] M. Diligenti, M. Gori, and M. Maggini. A Unified Probabilistic Framework for Web Page Scoring Systems. IEEE Trans. Knowledge and Data Eng., 2004,16(1): 4-16.
[50] H.W. Kuhn. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 1955, 2:83-97.
[51] Ibrahim Zeid. Mastering CAD/CAM, 2005, 影印版,北京,清华大学出版社.
[52] Nielsen J, Mack RL. Usability inspection methods. John Wiley & Sons, 1994, New York.
[53] Tsai LW. Mechanism design: Enumeration of kinematic structures according to function., 2001, Boca Raton (FL), CRC Press.
[54] Nobuhiro Sugimura, and Akihiko Ohtaka. ISO TC 184/SC4/WG12 N597. JNC Proposal of STEP Assembly Model for Products, 2000, Genev.
[55] P. Kilpelainen. Tree matching problems with applications to structured text databases. Ph.D. Thesis, 1992, Department of Computer Science, University of Helsinki.
