×

Partial retrieval of CAD models based on the gradient flows in Lie group. (English) Zbl 1231.65037

Summary: Based on gradient flows in Lie group, a partial retrieval approach for CAD models is presented in this paper. First, a representation of the face attributed relational graph (ARG) for a CAD model is created from its B-rep model and thus partial retrieval is converted to a subgraph matching problem. Then, an optimization method is adopted to solve the matching problem, where the optimization variable is the vertex mapping and the objective function is the measurement of compatibility between the mapped vertices and between the mapped edges. Different from most previously proposed methods, a homogeneous transformation matrix is introduced to represent the vertex mapping in subgraph matching, whose translational sub-matrix gives the vertex selection in the larger graph and whose orthogonal sub-matrix presents the vertex permutation for the same-sized mapping from the selected vertices to the smaller graph’s vertices. Finally, a gradient flow method is developed to search for optimal matching matrix in the special Euclidean group \(\operatorname{SE}(n)\). Here, a penalty approach is used to handle the constraints on the elements of the matching matrix, which leads its orthogonal part to be a permutation matrix and its translational part to have different integer elements. Experimental results show that it is a promising method to support the partial retrieval of CAD models.

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

References:

[1] Osada, R.; Funkhouser, T.; Chazelle, B.; Dobkin, D., Shape distributions, ACM Transactions on Graphics, 21, 4, 807-832 (2002) · Zbl 1331.68256
[2] Mademlis, A.; Daras, P.; Tzovaras, D.; Strintzis, M. G., 3D object retrieval using the 3D shape impact descriptor, Pattern Recognition, 42, 11, 2447-2459 (2009) · Zbl 1176.68185
[3] M. Kazhdan, T. Funkhouser, S. Rusinkiewicz, Rotation invariant spherical harmonic representation of 3D shape descriptors, in: Proceedings of the Eurographics Symposium on Geometry Processing, 2003.; M. Kazhdan, T. Funkhouser, S. Rusinkiewicz, Rotation invariant spherical harmonic representation of 3D shape descriptors, in: Proceedings of the Eurographics Symposium on Geometry Processing, 2003.
[4] Novotni, M.; Klein, R., Shape retrieval using 3D Zernike descriptors, Computer-Aided Design, 36, 11, 1047-1062 (2004)
[5] Kazhdan, M.; Chazelle, B.; Dobkin, D.; Funkhouser, T.; Rusinkiewicz, S., A reflective symmetry descriptor for 3D models, Algorithmica, 38, 1, 201-225 (2004) · Zbl 1072.68095
[6] M. Kazhdan, T. Funkhouser, S. Rusinkiewicz, Symmetry descriptors and 3D shape matching, in: Proceedings of the Eurographics Symposium on Geometry Processing, 2004.; M. Kazhdan, T. Funkhouser, S. Rusinkiewicz, Symmetry descriptors and 3D shape matching, in: Proceedings of the Eurographics Symposium on Geometry Processing, 2004. · Zbl 1072.68095
[7] Daras, P.; Axenopoulos, A., A 3D shape retrieval framework supporting multimodal queries, International Journal of Computer Vision, 89, 229-247 (2010)
[8] Gao, Y.; Dai, Q.; Zhang, N., 3D model comparison using spatial structure circular descriptor, Pattern Recognition, 43, 3, 1142-1151 (2010) · Zbl 1187.68453
[9] Biasotti, S.; Giorgi, D.; Spagnuolo, M.; Falcidieno, B., Size functions for comparing 3Dmodels, Pattern Recognition, 41, 9, 2855-2873 (2008) · Zbl 1154.68479
[10] H. Sundar, D. Silver, N. Gagvani, S. Dickenson, Skeleton based shape matching and retrieval, in: Proceedings of the shape modeling international, 2004, pp. 130-139.; H. Sundar, D. Silver, N. Gagvani, S. Dickenson, Skeleton based shape matching and retrieval, in: Proceedings of the shape modeling international, 2004, pp. 130-139.
[11] D. Bespalov, W.C. Regli, A. Shokoufandeh, Reeb graph based shape retrieval for CAD, in: Proceedings of DETC03 2003 ASME Design Engineering Technical Conferences, 2003.; D. Bespalov, W.C. Regli, A. Shokoufandeh, Reeb graph based shape retrieval for CAD, in: Proceedings of DETC03 2003 ASME Design Engineering Technical Conferences, 2003.
[12] Biasotti, S.; Marini, S.; Spagnuolo, M., Sub-part correspondence by structural descriptors of 3D shapes, Computer-Aided Design, 38, 9, 1002-1019 (2006)
[13] A. Agathos, I. Pratikakis, P. Papadakis, S. Perantonis, P. Azariadis, N. Sapidis, Retrieval of 3D articulated objects using a graph-based representation, in: Proceedings of the Eurographics Workshop on 3D Object Retrieval, 2009, pp. 29-36.; A. Agathos, I. Pratikakis, P. Papadakis, S. Perantonis, P. Azariadis, N. Sapidis, Retrieval of 3D articulated objects using a graph-based representation, in: Proceedings of the Eurographics Workshop on 3D Object Retrieval, 2009, pp. 29-36.
[14] D. Bespalov, A. Shokoufandeh, W.C. Regli, W. Sun. Scale-space representation of 3D models and topological matching, in: SM ’03: Proceedings of the eighth ACM symposium on Solid modeling and applications, New York, USA, 2003, pp. 208-215.; D. Bespalov, A. Shokoufandeh, W.C. Regli, W. Sun. Scale-space representation of 3D models and topological matching, in: SM ’03: Proceedings of the eighth ACM symposium on Solid modeling and applications, New York, USA, 2003, pp. 208-215.
[15] Bespalov, D.; Regli, W. C.; Shokoufandeha, A., Local feature extraction and matching partial objects, Computer-Aided Design, 38, 9, 1020-1037 (2006) · Zbl 1206.68265
[16] El-Mehalawi, M.; Miller, R. A., A database system of mechanical components based on geometric and topological similarity, part II: indexing, retrieval, matching and similarity assessment, Computer-Aided Design, 35, 1, 95-105 (2003)
[17] Funkhouser, T.; Min, P.; Kazhdan, M.; Chen, J.; Halderman, A.; Dobkin, D.; Jacobs, D., A search engine for 3D models, ACM Transactions on Graphics, 22, 1, 83-105 (2003)
[18] Shilane, P.; Min, P.; Kazhdan, M.; Funkhouser, T., The princeton shape benchmark, Shape modeling applications (2004), IEEE Computer Society Press, pp. 167-180
[19] Jayanti, S.; Kalyanaraman, Y.; Iyer, N.; Ramani, K., Developing an engineering shape benchmark for CAD models, Computer-Aided Design, 38, 9, 939-953 (2006)
[20] D. Bespalov, Ch. Y. Ip, W.C. Regli, Joshua Shaffer. Benchmarking CAD search techniques, in: Proceedings of the 2005 ACM symposium on Solid and physical modeling (SPM ’05), New York, USA, 2005, pp. 275-286.; D. Bespalov, Ch. Y. Ip, W.C. Regli, Joshua Shaffer. Benchmarking CAD search techniques, in: Proceedings of the 2005 ACM symposium on Solid and physical modeling (SPM ’05), New York, USA, 2005, pp. 275-286.
[21] Tangelder, J. W.H.; Veltkamp, R. C., A survey of content based 3D shape retrieval methods, Multimedia Tools and Applications, 39, 3, 441-471 (2008)
[22] Funkhouser, T.; Kazhdan, M.; Shilane, P.; Min, P.; Kiefer, W.; Tal, A.; Rusinkiewicz, S.; Dobkin, D., Modeling by example, ACM Transactions on Graphics, 23, 3, 649-660 (2004)
[23] Fisher, M.; Hanrahan, P., Context-based search for 3D models, ACM Transactions on Graphics, 29, 6, 182.1-182.10 (2010)
[24] Gal, R.; Cohen-Or, D., Salient geometric features for partial shape matching and similarity, ACM Transactions on Graphics, 25, 1, 130-150 (2006)
[25] T. Schreck, B. Bustos, M. Walter, A query-by-example concept and user interface for global and partial 3D object retrieval, in: Proceedings o f the Eurographics Workshop on 3D Object Retrieval, 2009.; T. Schreck, B. Bustos, M. Walter, A query-by-example concept and user interface for global and partial 3D object retrieval, in: Proceedings o f the Eurographics Workshop on 3D Object Retrieval, 2009.
[26] Ferreira, A.; Marini, S.; Attene, M.; Fonseca, M. J.; Spagnuolo, M.; Jorge, J. A.; Falcidieno, B., Thesaurus-based 3D object retrieval with part-in-whole matching, International Journal of Computer Vision, 89, 327-347 (2010)
[27] Philipp-Foliguet, S.; Jordan, M.; Najman, L.; Cousty, J., Artwork 3D model database indexing and classification, Pattern Recognition, 44, 3, 588-597 (2011) · Zbl 1209.68479
[28] Chen, X.; Golovinskiy, A.; Funkhouser, T., A benchmark for 3D mesh segmentation, ACM Transactions on Graphics, 28, 3, 73.1-73.12 (2009)
[29] T. Funkhouser, P. Shilane, Partial matching of 3D shapes with priority-driven search, in: Proceedings of the Eurographics Symposium on Geometry Processing, 2006, pp 131-142.; T. Funkhouser, P. Shilane, Partial matching of 3D shapes with priority-driven search, in: Proceedings of the Eurographics Symposium on Geometry Processing, 2006, pp 131-142.
[30] Bronstein, A. M.; Bronstein, M. M.; Guibas, L. J.; Ovsjanikov, M., Shape Google: geometric words and expressions for invariant shape retrieval, ACM Transactions on Graphics, 30, 1, 1.1-1.22 (2011)
[31] Cardone, A.; Gupta, S. K.; Karnik, M., A survey of shape similarity assessment algorithms for product design and manufacturing applications, ASME Journal of Computing and Information Science in Engineering, 3, 2, 109-118 (2003)
[32] Cardone, A.; Gupta, S. K.; Deshmukh, A.; Karnik, M., Machining feature-based similarity assessment algorithms for prismatic machined parts, Computer-Aided Design, 38, 9, 954-972 (2006)
[33] Li, M.; Zhang, Y. F.; Fuh, J. Y.H.; Qiu, Z. M., Toward effective mechanical design reuse: CAD model retrieval based on general and partial shapes, ASME Journal of Mechanical Design, 131, 12, 121501.1-121501.8 (2009)
[34] Saber, E.; Xu, Y.; Tekalp, A. M., Partial shape recognition by sub-matrix matching for partial matching guided image labeling, Pattern Recognition, 38, 10, 1560-1573 (2005)
[35] Ullmann, J. R., An algorithm for subgraph isomorphism, Journal of the Association for Computing Machinery, 23, 1, 31-42 (1976) · Zbl 0323.05138
[36] Haralick, R. M.; Elliot, G. L., Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence, 14, 263-313 (1980)
[37] Kim, W. Y.; Kak, A. C., 3-D Object recognition using bipartite matching embedded in discrete relaxation, IEEE Transactions on PAMI, 13, 3, 224-251 (1991)
[38] Gold, S.; Rangarajan, A., A graduated assignment for graph matching, IEEE Transactions on PAMI, 18, 4, 377-388 (1996)
[39] Christmas, W. J.; Kittler, J.; Petrou, M., Structural matching in computer vision using probabilistic relaxation, IEEE Transactions on PAMI, 17, 8, 749-764 (1995)
[40] Suganthan, P. N.; Teoh, E. K.; Mital, D. P., Pattern recognition by graph matching using the Potts MFT neural networks, Pattern Recognition, 28, 7, 997-1009 (1995)
[41] Lee, Y. L.; Park, R. H., A surface-based approach to 3-D object recognition using a mean field annealing neural network, Pattern Recognition, 35, 2, 299-316 (2002) · Zbl 0993.68097
[42] Cross, A. D.J.; Wilson, R. C.; Hancock, E. R., Inexact graph matching using genetic search, Pattern Recognition, 30, 6, 953-970 (1997)
[43] Auwatanamongkol, S., Inexact graph matching using a genetic algorithm for image recognition, Pattern Recognition Letters, 28, 12, 1428-1437 (2007)
[44] Zavlanos, M. M.; Pappas, G. J., A dynamical systems approach to weighted graph matching, Automatica, 44, 11, 2817-2824 (2008) · Zbl 1204.05084
[45] El-Mehalawi, M.; Allen, M. R., A database system of mechanical components based on geometric and topological similarity, part I: representation, Computer-Aided Design, 35, 1, 95-105 (2003)
[46] Munthe, K. H., Runge-Kutta methods on lie group, BIT, 38, 92-111 (1998) · Zbl 0904.65077
[47] Gallier, J.; Xu, D., Computing exponentials of skew-symmetric matrices and logarithms of orthogonal matrices, International Journal of Robotics and Automation, 18, 1, 10-20 (2003)
[48] Buono, N. D.; Lopez, L.; Peluso, R., Computation of the exponential of large sparse skew-symmetric matrices, SIAM Journal of Scientific Computing, 27, 1, 278-293 (2005) · Zbl 1108.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.