{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T14:44:31Z","timestamp":1761057871044,"version":"3.30.2"},"reference-count":47,"publisher":"ASME International","issue":"4","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2003,12,1]]},"abstract":"<jats:p>This paper presents a framework for shape matching and classification through scale-space decomposition of 3D models. The algorithm is based on recent developments in efficient hierarchical decomposition of a point distribution in metric space p,d using its spectral properties. Through spectral decomposition, we reduce the problem of matching to that of computing a mapping and distance measure between vertex-labeled rooted trees. We use a dynamic programming scheme to compute distances between trees corresponding to solid models. Empirical evaluation of the algorithm on an extensive set of 3D matching trials demonstrates both robustness and efficiency of the overall approach. Lastly, a technique for comparing shape matchers and classifiers is introduced and the scale-space method is compared with six other known shape matching algorithms.<\/jats:p>","DOI":"10.1115\/1.1633576","type":"journal-article","created":{"date-parts":[[2003,12,24]],"date-time":"2003-12-24T23:00:38Z","timestamp":1072306838000},"page":"315-324","update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":13,"title":["Scale-Space Representation and Classification of 3D Models"],"prefix":"10.1115","volume":"3","author":[{"given":"Dmitriy","family":"Bespalov and","sequence":"first","affiliation":[{"name":"Department of Computer Science, College of Engineering, Drexel University, 3141 Chestnut Street, Philadelphia, PA\u200919104"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ali","family":"Shokoufandeh","sequence":"additional","affiliation":[{"name":"Department of Computer Science, College of Engineering, Drexel University, 3141 Chestnut Street, Philadelphia, PA\u200919104"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William C.","family":"Regli","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering and Mechanics and Department of Computer Science, College of Engineering, Drexel University, 3141 Chestnut Street, Philadelphia, PA\u200919104"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Sun","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engiineering and Mechancis, College of Engineering, Drexel University, 3141 Chestnut Street, Philadelphia, PA\u200919104"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2003,12,24]]},"reference":[{"key":"2019100521594093000_r1","doi-asserted-by":"crossref","unstructured":"Han, J.-H., Regli, W. C., and Pratt, M. J., 2000, \u201cAlgorithms for Feature Recognition from Solid Models: A Status Report,\u201d IEEE J. Rob. Autom., 16(6), pp. 782\u2013796.","DOI":"10.1109\/70.897789"},{"key":"2019100521594093000_r2","doi-asserted-by":"crossref","unstructured":"Shah, J., Anderson, D., Kim, Y. S., and Joshi, S., 2001, \u201cA Discourse on Geometric Feature Recognition from cad Models,\u201d ASME J. Comput. Inf. Sci. Eng., 1(1), pp. 41\u201351.","DOI":"10.1115\/1.1345522"},{"key":"2019100521594093000_r3","doi-asserted-by":"crossref","unstructured":"Elinson, A., Nau, D. S., and Regli, W. C., 1997. \u201cFeature-based Similarity Assessment of Solid Models,\u201d In Fourth Symposium on Solid Modeling and Applications, C. Hoffman and W. Bronsvoort, Eds., ACM, ACM Press, pp. 297\u2013310. Atlanta, GA.","DOI":"10.1145\/267734.267806"},{"key":"2019100521594093000_r4","doi-asserted-by":"crossref","unstructured":"Regli, W. C., and Cicirello, V., 2000, \u201cManaging Digital Libraries for Computer-aided Design,\u201d Comput.-Aided Des., 32(2), pp. 119\u2013132. Special Issue on CAD After 2000. Mohsen Rezayat, Guest Editor.","DOI":"10.1016\/S0010-4485(99)00095-0"},{"key":"2019100521594093000_r5","doi-asserted-by":"crossref","unstructured":"Cicirello, V., and Regli, W. C., 1999. \u201cResolving Non-uniqueness in Design Feature Histories,\u201d In Fifth Symposium on Solid Modeling and Applications, D. Anderson and W. Bronsvoort, Eds., ACM, ACM Press. Ann Arbor, MI.","DOI":"10.1145\/304012.304020"},{"key":"2019100521594093000_r6","unstructured":"Cicirello, V. A., 1999, \u201cIntelligent Retrieval of Solid Models,\u201d Master\u2019s thesis, Drexel University, Geometric and Intelligent Computing Laboratory, Department of Mathematics and Computer Science, Philadelphia, PA 19104, June 1999."},{"key":"2019100521594093000_r7","doi-asserted-by":"crossref","unstructured":"Cicirello, V., and Regli, W., 2001. \u201cMachining Feature-based Comparisons of Mechanical Parts,\u201d In International Conference on Shape Modeling and Applications, ACM SIGGRAPH, the Computer Graphics Society and EURO-GRAPHICS, IEEE Computer Society Press, pp. 176\u2013187.","DOI":"10.1109\/SMA.2001.923388"},{"key":"2019100521594093000_r8","doi-asserted-by":"crossref","unstructured":"Cicirello, V., and Regli, W. C., 2002, \u201cAn Approach to a Feature-based Comparison of Solid Models of Machined Parts,\u201d Artificial Intelligence for Engineering Design, Analysis, and Manufacturing (AIEDAM), 16(5) [November], pp. 385\u2013399.","DOI":"10.1017\/S0890060402165048"},{"key":"2019100521594093000_r9","doi-asserted-by":"crossref","unstructured":"Ramesh, M. M., Yip-Hoi, D., and Dutta, D., 2000, \u201cA Decomposition Methodology for Machining Feature Extraction,\u201d In ASME Design Engineering Technical Conferences, Computers in Engineering Conference, American Association of Mechanical Engineers, ASME Press. DETC2000\/CIE-14645.","DOI":"10.1115\/DETC2000\/CIE-14645"},{"key":"2019100521594093000_r10","doi-asserted-by":"crossref","unstructured":"Sun, T.-L., Su, C.-J., Mayer, R. J., and Wysk, R. A., 1995, \u201cShape Similarity Assessment of Mechanical Parts Based on Solid Models,\u201d In ASME Design for Manufacturing Conference, Symposium on Computer Integrated Concurrent Design, R. Gadh, Ed., ASME, pp. 953\u2013962.","DOI":"10.1115\/DETC1995-0234"},{"key":"2019100521594093000_r11","doi-asserted-by":"crossref","unstructured":"McWherter, D., Peabody, M., Shokoufandeh, A., and Regli, W., 2001. \u201cTransformation Invariant Similarity Assessment of Solid Models,\u201d In ASME Design Engineering Technical Conferences, ASME, ASME Press. DETC2001\/DFM-21191.","DOI":"10.1115\/DETC2001\/DFM-21191"},{"key":"2019100521594093000_r12","doi-asserted-by":"crossref","unstructured":"McWherter, D., Peabody, M., Shokoufandeh, A., and Regli, W., 2001, \u201cSolid Model Databases: Techniques and Empirical Results,\u201d ASME J. Comput. Inf. Sci. Eng. 1(4), pp. 300\u2013310.","DOI":"10.1115\/1.1430233"},{"key":"2019100521594093000_r13","doi-asserted-by":"crossref","unstructured":"McWherter, D., Peabody, M., Shokoufandeh, A., and Regli, W., 2001. \u201cDatabase Techniques for Indexing and Clustering of Solid Models,\u201d In Sixth ACM\/SIGGRAPH Symposium on Solid Modeling and Applications, D. Dutta and H.-P. Seidel, Eds., ACM, ACM Press, pp. 78\u201387.","DOI":"10.1145\/376957.376968"},{"key":"2019100521594093000_r14","unstructured":"Snead, C. S., 1989. Group Technology: Foundations for Competitive Manufacturing. Van Nostrand Reinhold, New York."},{"key":"2019100521594093000_r15","doi-asserted-by":"crossref","unstructured":"Ames, A. L., 1991, \u201cProduction Ready Feature Recognition Based Automatic Group Technology Part Coding,\u201d In Symposium on Solid Modeling Foundations and CAD\/CAM Applications, J. Rossignac and J. Turner, Eds., ACM SIGGRAPH, ACM Press, pp. 161\u2013169.","DOI":"10.1145\/112515.112540"},{"key":"2019100521594093000_r16","unstructured":"Shah, J. J., and Bhatnagar, A., 1989, \u201cGroup Technology Classification from Feature-based Geometric Models,\u201d Manufacturing Rev. 2(3), pp. 204\u2013213."},{"key":"2019100521594093000_r17","unstructured":"Bond, A., and Jain, R., 1988, \u201cThe Formal Definition and Automatic Extraction of Group Technology Codes,\u201d In ASME Design Technical Conferences, Computers in Engineering Conference, pp. 537\u2013542."},{"key":"2019100521594093000_r18","doi-asserted-by":"crossref","unstructured":"Henderson, M., and Musti, S., 1988, \u201cAutomated Group Technology Part Coding from a Three-dimensional Cad Database,\u201d J. Eng. Ind., 110(3), pp. 278\u2013287.","DOI":"10.1115\/1.3187882"},{"key":"2019100521594093000_r19","unstructured":"Ham, I., Marion, D., and Rubinovich, J., 1986, \u201cDeveloping a Group Technology Coding and Classification Scheme,\u201d Ind. Eng. (N. Y., 1922-1931), 18(7), pp. 90\u201397."},{"key":"2019100521594093000_r20","unstructured":"The Digital Michelangelo Project, http:\/\/graphics.stanford.edu\/projects\/mich\/."},{"key":"2019100521594093000_r21","unstructured":"Thompson, W. B., Riesenfeld, R. F., and Owen, J. C., 1996, \u201cDetermining the Similarity of Geometric Models,\u201d In Proceedings of the ARPA Image Understanding Workshop."},{"key":"2019100521594093000_r22","doi-asserted-by":"crossref","unstructured":"Thompson, W. B., Owen, J., de St. Germain, H., Stark, S. Jr.,, and Henderson, T., 1999, \u201cFeature-based Reverse Engineering of Mechanical Parts,\u201d IEEE J. Rob. Autom., 12(1), pp. 57\u201366.","DOI":"10.1109\/70.744602"},{"key":"2019100521594093000_r23","doi-asserted-by":"crossref","unstructured":"Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, T. L., 2001, \u201cTopology Matching for Fully Automatic Similarity Estimation of 3D Shapes,\u201d In SIGGRAPH, ACM Press, pp. 203\u2013212.","DOI":"10.1145\/383259.383282"},{"key":"2019100521594093000_r24","doi-asserted-by":"crossref","unstructured":"Osada, R., Funkhouser, T., Chazelle, B., and Dobkin, D., 2001, \u201cMatching 3D Models with Shape Distributions,\u201d In International Conference on Shape Modeling and Applications, 154\u2013166, Ed., ACM SIGGRAPH, the Computer Graphics Society and Eurographics, IEEE Computer Society Press.","DOI":"10.1109\/SMA.2001.923386"},{"key":"2019100521594093000_r25","doi-asserted-by":"crossref","unstructured":"Osada, R., Funkhouser, T., Chazelle, B., and Dobkin, D., 2002, \u201cShape Distributions,\u201d ACM Trans. Graphics, 21(4).","DOI":"10.1145\/571647.571648"},{"key":"2019100521594093000_r26","doi-asserted-by":"crossref","unstructured":"Funkhouser, T., Min, P., Kazhdan, M., Chen, J., Halderman, A., Dobkin, D., and Jacobs, D., 2003, \u201cA Search Engine for 3D Models,\u201d ACM Trans. Graphics, 22(1).","DOI":"10.1145\/588272.588279"},{"key":"2019100521594093000_r27","doi-asserted-by":"crossref","unstructured":"Kazhdan, M., Chazelle, B., Dobkin, D., Funkhouser, T., and Rusinkiewicz, S., 2003, \u201cA Reflective Symmetry Descriptor for 3D Models,\u201d Algorithmica, To appear.","DOI":"10.1007\/s00453-003-1050-5"},{"key":"2019100521594093000_r28","unstructured":"Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S., 2003, \u201cRotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors,\u201d In Symposium on Geometry Processing."},{"key":"2019100521594093000_r29","doi-asserted-by":"crossref","unstructured":"Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S., 2002, \u201cHarmonic 3D Shape Matching,\u201d In SIGGRAPH.","DOI":"10.1145\/1242073.1242204"},{"key":"2019100521594093000_r30","doi-asserted-by":"crossref","unstructured":"Elad, M., Tal, A., and Ar, S., 2001, \u201cContent Based Retrieval of VRML Objects\u2014An Iterative and Interactive Approach,\u201d In The Sixth Eurographics Workshop in Multimedia, pp. 97\u2013108.","DOI":"10.1007\/978-3-7091-6103-6_12"},{"key":"2019100521594093000_r31","doi-asserted-by":"crossref","unstructured":"Ip, C. Y., Lapadat, D., Sieger, L., and Regli, W., 2002. \u201cUsing Shape Distributions to Compare Solid Models,\u201d In Seventh ACM\/SIGGRAPH Symposium on Solid Modeling and Applications, H.-P. Seidel, Ed., ACM, ACM Press, pp. 273\u2013280.","DOI":"10.1145\/566313.566322"},{"key":"2019100521594093000_r32","doi-asserted-by":"crossref","unstructured":"Ip, C. Y., Sieger, L., Regli, W., and Shokoufandeh, A., 2003, \u201cAutomated Learning of Model Classifications,\u201d In Eighth ACM\/SIGGRAPH Symposium on Solid Modeling and Applications, G. Elber and V. Shapiro, Eds., ACM, ACM Press, pp. 322\u2013327.","DOI":"10.1145\/781650.781659"},{"key":"2019100521594093000_r33","doi-asserted-by":"crossref","unstructured":"Cyr, C. M., and Kimia, B. B., 2001, \u201c3D Object Recognition Using Shape Similarity-based Aspect Graph,\u201d In Proceedings of the Eighth International Conference On Computer Vision (ICCV-01), pp. 254\u2013261.","DOI":"10.1109\/ICCV.2001.937526"},{"key":"2019100521594093000_r34","doi-asserted-by":"crossref","unstructured":"Shapiro, L. G., and Haralick, R. M., 1981, \u201cStructural Descriptions and Inexact Matching,\u201d IEEE Trans. Pattern Anal. Mach. Intell., 3, pp. 504\u2013519.","DOI":"10.1109\/TPAMI.1981.4767144"},{"key":"2019100521594093000_r35","doi-asserted-by":"crossref","unstructured":"Kim, W., and Kak, A. C., 1991, \u201c3D Object Recognition Using Bipartite Matching Embedded in Discrete Relaxation,\u201d IEEE Trans. Pattern Anal. Mach. Intell., 13(3), pp. 224\u2013251.","DOI":"10.1109\/34.75511"},{"key":"2019100521594093000_r36","doi-asserted-by":"crossref","unstructured":"Pelillo, M., Siddiqi, K., and Zucker, S., 1999, \u201cMatching Hierarchical Structures Using Association Graphs,\u201d IEEE Trans. Pattern Anal. Mach. Intell., 21(11) [November], pp. 1105\u20131120.","DOI":"10.1109\/34.809105"},{"key":"2019100521594093000_r37","doi-asserted-by":"crossref","unstructured":"Gold, S., and Rangarajan, A., 1996, \u201cA Graduated Assignment Algorithm for Graph Matching,\u201d IEEE Trans. Pattern Anal. Mach. Intell., 18(4), pp. 377\u2013388.","DOI":"10.1109\/34.491619"},{"key":"2019100521594093000_r38","unstructured":"Siddiqi, K., Shokoufandeh, A., Dickinson, S., and Zucker, S., 1999, \u201cShock Graphs and Shape Matching,\u201d Int. J. Comput. Vis., 30, pp. 1\u201324."},{"key":"2019100521594093000_r39","doi-asserted-by":"crossref","unstructured":"Shokoufandeh, A., Dickinson, S., Jo\u00a8nsson, C., Bretzner, L., and Lindeberg, T., 2002, \u201cOn the Representation and Matching of Qualitative Shape at Multiple Scales,\u201d In Proceedings, 7th European Conference on Computer Vision, vol. 3, pp. 759\u2013775.","DOI":"10.1007\/3-540-47977-5_50"},{"key":"2019100521594093000_r40","doi-asserted-by":"crossref","unstructured":"Luo, B., and Hancock, E. R., 2001, \u201cStructural Matching Using the EM Algorithm and Singular Value Decomposition,\u201d IEEE Trans. Pattern Anal. Mach. Intell., 23, pp. 1120\u20131136.","DOI":"10.1109\/34.954602"},{"key":"2019100521594093000_r41","doi-asserted-by":"crossref","unstructured":"Veltkamp, R. C., 2001, \u201cShape Matching: Similarity Measures and Algorithms,\u201d In International Conference on Shape Modeling and Applications, 188\u2013197, Ed., ACM SIGGRAPH, the Computer Graphics Society and EUROGRAPH-ICS, IEEE Computer Society Press pp.","DOI":"10.1109\/SMA.2001.923389"},{"key":"2019100521594093000_r42","unstructured":"Tangelder, J. W., and Veltkamp, R. C., \u201cPolyhedral Model Comparison and Retrieval Using Weighted Point Sets,\u201d In The eight annual conference of the Advanced School for Computing and Imaging, pp. 223\u2013230."},{"key":"2019100521594093000_r43","unstructured":"Cormen, T. H., Leiserson, C. L., and Rivest, R. L., 2001, Introduction to Algorithms, MIT Press."},{"key":"2019100521594093000_r44","doi-asserted-by":"crossref","unstructured":"Thomasian, A., Castelli, V., and Li, C.-S., 1998, \u201cClustering and Singular Value Decomposition for Approximate Indexing in High Dimensional Spaces,\u201d In The Seventh International Conference on Information and Knowledge Management Table of Contents, pp. 201\u2013207.","DOI":"10.1145\/288627.288658"},{"key":"2019100521594093000_r45","unstructured":"Golub, G. H., and van Loan, C. F., 1989, Matrix Computations. John Hopkins Press."},{"key":"2019100521594093000_r46","doi-asserted-by":"crossref","unstructured":"Wang, J. T. L., Shapiro, B. A., Shasha, D., Zhang, K., and Currey, K. M., 1998, \u201cAn Algorithm for Finding the Largest Approximately Common Substructures of Two Trees,\u201d IEEE Trans. Pattern Anal. Mach. Intell., 20, pp. 889\u2013895.","DOI":"10.1109\/34.709622"},{"key":"2019100521594093000_r47","doi-asserted-by":"crossref","unstructured":"Novotni, M., and Klein, R., 2003. \u201c3D Zernike Descriptors for Content Based Shape Retrieval,\u201d In Proceedings of the eighth ACM symposium on Solid modeling and applications, ACM Press, pp. 216\u2013225.","DOI":"10.1145\/781606.781639"}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/3\/4\/315\/5525491\/315_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/3\/4\/315\/5525491\/315_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T18:44:09Z","timestamp":1734201849000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/3\/4\/315\/445320\/ScaleSpace-Representation-and-Classification-of-3D"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12,1]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2003,12,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.1633576","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2003,12,1]]}}}