{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T12:40:38Z","timestamp":1753879238190,"version":"3.41.2"},"reference-count":33,"publisher":"ASME International","issue":"3","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,9,1]]},"abstract":"<jats:p>3D shape matching is widely used in engineering design for model retrieval, shape similarity assessment or collaborative development. In this paper, an enhanced graph representation and heuristic tabu search based approach is presented to enable flexible and efficient 3D shape matching. The core idea includes (1) generic shape features are recognized from boundary representation (B-rep) of 3D shape as many as possible to incorporate domain design knowledge, (2) an enhanced graph representation of 3D shape is constructed by mixing faces of B-rep and recognized features, to achieve meaningful matching results at low-level of faces or high-level of features satisfying various design intents, and (3) a tabu list of possible improper matches is built to reduce the search space so that the optimal result can be efficiently obtained. Finally, Two examples are demonstrated to show that both two levels of 3D shape matching results can be efficiently obtained for various design intents in the engineering applications, only not more than 18% computation time is required when compared with a typical shape matching method, and it takes only 20\u2009s when the number of matching nodes is more than 460.<\/jats:p>","DOI":"10.1115\/1.4027616","type":"journal-article","created":{"date-parts":[[2014,5,7]],"date-time":"2014-05-07T04:31:20Z","timestamp":1399437080000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":3,"title":["An Enhanced Graph Representation and Heuristic Tabu Search Approach for Flexible and Efficient 3D Shape Matching"],"prefix":"10.1115","volume":"14","author":[{"given":"Yuhang","family":"Sun","sequence":"first","affiliation":[{"name":"School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liping","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunbao","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sha","family":"Wan","sequence":"additional","affiliation":[{"name":"School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2014,6,2]]},"reference":[{"issue":"5","key":"2019100602445380500_B1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1016\/j.cad.2004.07.002","article-title":"Three-Dimensional Shape Searching: State-of-the-Art Review and Future Trends","volume":"37","year":"2005","journal-title":"Comput.-Aided Des."},{"issue":"13","key":"2019100602445380500_B2","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1016\/j.cad.2005.02.011","article-title":"Shape-Based Searching for Product Lifecycle Applications","volume":"37","year":"2005","journal-title":"Comput.-Aided Des."},{"issue":"12","key":"2019100602445380500_B3","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1016\/j.cad.2010.07.002","article-title":"Design Reuse Oriented Partial Retrieval of CAD Models","volume":"42","year":"2010","journal-title":"Comput.-Aided Des."},{"issue":"1","key":"2019100602445380500_B4","doi-asserted-by":"crossref","first-page":"011001","DOI":"10.1115\/1.3563055","article-title":"Similarity Assessment of Mechanical Parts Based on Integrated Product Information Model","volume":"11","year":"2011","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"key":"2019100602445380500_B5","article-title":"Synchronous Technology"},{"issue":"5","key":"2019100602445380500_B6","first-page":"355","article-title":"Framework for Integrated Mechanical Design Automation","volume":"32","year":"2000","journal-title":"Comput.-Aided Des."},{"issue":"2","key":"2019100602445380500_B7","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1115\/1.1577356","article-title":"A Survey of Shape Similarity Assessment Algorithms for Product Design and Manufacturing Applications","volume":"3","year":"2003","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"issue":"1","key":"2019100602445380500_B8","doi-asserted-by":"crossref","first-page":"15","DOI":"10.3233\/ICA-120416","article-title":"A Method for Topological Entity Matching in the Integration of Heterogeneous CAD Systems","volume":"20","year":"2013","journal-title":"Integr. Comput.-Aided Eng."},{"issue":"2","key":"2019100602445380500_B9","first-page":"29","article-title":"A 3D Shape Retrieval Framework Supporting Multi-Modal Queries","volume":"89","year":"2010","journal-title":"Int. J. Comput. Vision"},{"volume-title":"Parametric and Feature-Based CAD\/CAM: Concepts, Techniques, and Applications","year":"1995","key":"2019100602445380500_B10"},{"issue":"1","key":"2019100602445380500_B11","first-page":"440","article-title":"A Discourse on Geometric Feature Recognition From CAD Models","volume":"1","year":"2001","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"issue":"11","key":"2019100602445380500_B12","first-page":"973","article-title":"An Approach to Identify Design and Manufacturing Features From a Data Exchanged Part Model","volume":"35","year":"2003","journal-title":"Comput.-Aided Des."},{"issue":"4","key":"2019100602445380500_B13","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.compind.2007.09.001","article-title":"A Review of Automated Feature Recognition With Rule-Based Pattern Recognition","volume":"59","year":"2008","journal-title":"Comput. Ind."},{"key":"2019100602445380500_B14","doi-asserted-by":"crossref","unstructured":"Cicirello, V., and Regli, W., 2001, \u201cMachining Feature-Based Comparisons of Mechanical Parts,\u201d Proceedings of IEEE SMA, Genova, Italy, pp. 176\u2013185.","DOI":"10.1109\/SMA.2001.923388"},{"issue":"1","key":"2019100602445380500_B15","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/S0010-4485(01)00178-6","article-title":"A Database System of Mechanical Components Based on Geometric and Topological Similarity. Part II: Indexing, Retrieval, Matching, and Similarity Assessment","volume":"35","year":"2003","journal-title":"Comput.-Aided Des."},{"key":"2019100602445380500_B16","doi-asserted-by":"crossref","unstructured":"Ascher, M., Marefat, M., and Fasse, E., 2001, \u201cA Methodology for Automatic Retrieval of Similarly Shaped Machinable Components,\u201d Proceedings of IEEE ICSM, Tucson, AZ, Oct. 7\u201310, pp. 2840\u20132845.10.1109\/ICSMC.2001.971940","DOI":"10.1109\/ICSMC.2001.971940"},{"issue":"11","key":"2019100602445380500_B17","doi-asserted-by":"crossref","first-page":"2447","DOI":"10.1016\/j.patcog.2009.04.024","article-title":"3D Object Retrieval Using the 3D Shape Impact Descriptor","volume":"42","year":"2009","journal-title":"Pattern Recognit."},{"issue":"11","key":"2019100602445380500_B18","doi-asserted-by":"crossref","first-page":"1047","DOI":"10.1016\/j.cad.2004.01.005","article-title":"Shape Retrieval Using 3D Zernike Descriptors","volume":"36","year":"2004","journal-title":"Comput.-Aided Des."},{"key":"2019100602445380500_B19","doi-asserted-by":"crossref","unstructured":"Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S., 2004, \u201cSymmetry Descriptors and 3D Shape Matching,\u201d SGP '04, Eurographics\/ACM SIGGRAPH Symposium on Geometry Processing, pp. 115\u2013123.10.1145\/1057432.1057448","DOI":"10.1145\/1057432.1057448"},{"issue":"3","key":"2019100602445380500_B20","doi-asserted-by":"crossref","first-page":"1142","DOI":"10.1016\/j.patcog.2009.07.012","article-title":"3D Model Comparison Using Spatial Structure Circular Descriptor","volume":"43","year":"2010","journal-title":"Pattern Recognit."},{"key":"2019100602445380500_B21","doi-asserted-by":"crossref","unstructured":"Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, T., 2001, \u201cTopology Matching for Fully Automatic Similarity Estimation of 3D Shapes,\u201d SIGGRAPH '01, Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, Los Angeles, CA, pp. 203\u2013212.10.1145\/383259.383282","DOI":"10.1145\/383259.383282"},{"key":"2019100602445380500_B22","doi-asserted-by":"crossref","unstructured":"Bespalov, D., Regli, W., and Shokoufandeh, A., 2003, \u201cReeb Graph Based Shape Retrieval for CAD,\u201d Proceedings of ASMEIDETC\/CIE, Chicago, IL, Sept. 2\u20136, pp. 229\u2013238.10.1115\/DETC2003\/CIE-48194","DOI":"10.1115\/DETC2003\/CIE-48194"},{"key":"2019100602445380500_B23","unstructured":"Iyer, N., Jayanti, S., Lou, K., Kalyanaraman, Y., and Ramani, K., 2004, \u201cA Multi-Scale Hierarchical 3D Shape Representation for Similar Shape Retrieval,\u201d Proceedings of the TMCE, Lausanne, Switzerland, pp. 1117\u20131118."},{"issue":"1","key":"2019100602445380500_B24","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/S0010-4485(01)00177-4","article-title":"A Database System of Mechanical Components Based on Geometric and Topological Similarity. Part I: Representation","volume":"35","year":"2003","journal-title":"Comput.-Aided Des."},{"issue":"5","key":"2019100602445380500_B25","first-page":"649","article-title":"3D Solid Model Retrieval for Engineering Reuse Based on Local Feature Correspondence","volume":"46","year":"2010","journal-title":"Int. J. Adv. Manuf. Technol."},{"issue":"4","key":"2019100602445380500_B26","doi-asserted-by":"crossref","first-page":"1721","DOI":"10.1016\/j.patcog.2011.09.017","article-title":"Partial Retrieval of CAD Models Based on the Gradient Flows in Lie Group","volume":"45","year":"2012","journal-title":"Pattern Recognit."},{"issue":"18","key":"2019100602445380500_B27","doi-asserted-by":"crossref","first-page":"4655","DOI":"10.1080\/00207540050205569","article-title":"Shape Similarity Assessment of Polyhedral Parts Based on Boundary Models","volume":"38","year":"2000","journal-title":"Int. J. Prod. Res."},{"issue":"9","key":"2019100602445380500_B28","doi-asserted-by":"crossref","first-page":"1020","DOI":"10.1016\/j.cad.2006.07.005","article-title":"Local Feature Extraction and Matching Partial Objects","volume":"38","year":"2006","journal-title":"Comput.-Aided Des."},{"key":"2019100602445380500_B29","doi-asserted-by":"crossref","first-page":"124501","DOI":"10.1115\/1.4000253","article-title":"Toward Effective Mechanical Design Reuse: CAD Model Retrieval Based on General and Partial Shapes","volume":"131","year":"2009","journal-title":"ASME J. Mech. Des."},{"issue":"3","key":"2019100602445380500_B30","doi-asserted-by":"crossref","first-page":"417","DOI":"10.3722\/cadaps.2010.417-430","article-title":"Retrieving Reusable 3D CAD Models Using Knowledge-Driven Dependency Graph Partitioning","volume":"7","year":"2010","journal-title":"Comput.-Aided Des. Appl."},{"key":"2019100602445380500_B31","doi-asserted-by":"crossref","unstructured":"Wan, S., Huang, Y., Wang, Q., Chen, L., and Sun, Y., 2012, \u201cA New Approach to Generic Design Feature Recognition by Detecting the Hint of Topology Variation,\u201d Proceedings of ASME IDETC\/CIE, Chicago, IL, Aug. 12\u201315, pp. 297\u2013306.10.1115\/DETC2012-70760","DOI":"10.1115\/DETC2012-70760"},{"key":"2019100602445380500_B32","unstructured":"Petrovic, S., Kendall, G., and Yang, Y., 2002, \u201cA Tabu Search Approach for Graph-Structured Case Retrieval,\u201d Starting Artificial Intelligence Researchers Symposium, pp. 55\u201364."},{"key":"2019100602445380500_B33","doi-asserted-by":"crossref","unstructured":"Sorlin, S., and Solnon, C., 2005, \u201cReactive Tabu Search for Measuring Graph Similarity,\u201d 5th IAPR Workshop on Graph-Based Representations in Pattern Recognition, pp. 172\u2013182.","DOI":"10.1007\/978-3-540-31988-7_16"}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4027616\/6099890\/jcise_014_03_031009.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4027616\/6099890\/jcise_014_03_031009.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T20:36:29Z","timestamp":1746218189000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/doi\/10.1115\/1.4027616\/371517\/An-Enhanced-Graph-Representation-and-Heuristic"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,2]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,9,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4027616","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2014,6,2]]},"article-number":"031009"}}