Topology matching for fully automatic similarity estimation of 3D shapes

ABSTRACT

There is a growing need to be able to accurately and efficiently search visual data sets, and in particular, 3D shape data sets. This paper proposes a novel technique, called Topology Matching, in which similarity between polyhedral models is quickly, accurately, and automatically calculated by comparing Multiresolutional Reeb Graphs (MRGs). The MRG thus operates well as a search key for 3D shape data sets. In particular, the MRG represents the skeletal and topological structure of a 3D shape at various levels of resolution. The MRG is constructed using a continuous function on the 3D shape, which may preferably be a function of geodesic distance because this function is invariant to translation and rotation and is also robust against changes in connectivities caused by a mesh simplification or subdivision. The similarity calculation between 3D shapes is processed using a coarse-to-fine strategy while preserving the consistency of the graph structures, which results in establishing a correspondence between the parts of objects. The similarity calculation is fast and efficient because it is not necessary to determine the particular pose of a 3D shape, such as a rotation, in advance. Topology Matching is particularly useful for interactively searching for a 3D object because the results of the search fit human intuition well.

References

1. 1.M.de Berg and M.van Kreveld. Trekking in the Alps Without Freezing or Getting Tired. Algorithmica, Vol.18, pp.306-323, 1997.
2. 2.P. J. Besl and N. D. McKay. A Method for Registration of 3-D Shapes. IEEE Trans. PAMI, Vol.14, pp.239-256, 1992.
3. 3.P. J. Besl. Triangles as a Primary Representation Object Recognition in Computer Vision, LNCS 994, pp.191-206. Splinger-Verlag, 1995.
4. 4.H. Blum. A Transformation for Extracting New Descriptors of Shape. Proc. Symp. Models for the Perception of Speech and Visual Form, pp.362-380, MIT Press, 1967.
5. 5.T. A. Cass. Robust Affine Structure Matching for 3D Object Recognition IEEE Trans. PAMI, Vol.20, pp.1265-1274, 1998.
6. 6.J. Chen and Y. Han. Shortest Paths on Polyhedron. Proc. Symp. Theory of Computing, pp.360-369, 1990.
7. 7.Y. Chen and G. Medioni. Object Modelling by Registration of Multiple Range Images. Image and Vision Computing, Vol.10, No.3, pp.145-155, 1992.
8. 8.J.-H. Chuang, C.-H. Tsai and M.-C. Ko. Skeletonization of Three-Dimensional Object Using Generalized Potential Field. IEEE Trans. PAMI, Vol.22, pp.1241-1251, 2000.
9. 9.T. Culver, J. Keyser and D. Manocha. Accurate Computation of the Medial Axis of a Polyhedron. Proc. Symp. Solid Modeling, pp.179-190, 1999.
10. 10.G. Dudek and J.K. Tsotsos. Shape Representation and Recognition from Multiscale Curvature. Computer Vision and Image Understanding, Vol.68, pp.170-189, 1997.
11. 11.C. Dorai and A.K. Jain. COSMOS-A Representation Scheme for 3D Free-Form Objects. IEEE Trans. PAMI, Vol.19, pp.1115-1130, 1997.
12. 12.M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B.Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele and P. Yanker. The Query By Image and Video Content: The QBIC System. IEEE Computer, Vol.28, No.9, pp.23-32, September 1995.
13. 13.I. Fujishiro, Y. Takeshima, T. Azuma and S. Takahashi. Volume Data Mining Using 3D Field Topology Analysis. IEEE Computer Graphics and Applications, Vol.20, No.5, pp.46- 51, 2000.
14. 14.D.M. Gaines. A Tool-Centric Approach to Designing Composable Feature Recognizers. Proc. Symp. Solid Modeling, pp.97-107, 1999.
15. 15.Y. Gdalyahu and D. Weinshall. Flexible Syntactic Matching of Curves and Its Application to Automatic Hierarchical Classification of Silhouettes. IEEE Trans. PAMI, Vol.21, pp.1312-1328, 1999.
16. 16.S.K. Gupta, W.C. Regli and D.S. Nau. Manufacturing Feature Instance: Which Ones to Recognize? Proc. Symp. Solid Modeling pp.141-152, 1995.
17. 17.A. Gupta and R. Jain. Visual Information Retrieval. Comm. ACM, Vol.40, No.5, pp.69-79, 1997.
18. 18.M. Hebert, K. Ikeuchi and H. Delingette. A Spherical Representation for Recognition of Free-form Surfaces. IEEE Trans. PAMI, Vol.17, pp.681-690, 1995.
19. 19.D.P. Hottenlocher, G.A. Klanderman, and W.J. Rucklidge. Comparing Images Using the Hausdorff Distance. IEEE Trans. PAMI, Vol.15, pp.850-863, 1993.
20. 20.C.E. Jacobs, A. Finkelsten and D.H. Salesin. Fast Multiresolution Image Querying. Proc. SIGGRAPH'95, pp.277-286.
21. 21.T. Kanai and H. Suzuki. Approximate Shortest Path on Polyhedral Surface Based on Selective Refinement of the Discrete Graph and its Applications. IEEE Proc. Geometric Modeling and Processing, pp.241-250, 2000.
22. 22.S.B. Kang and K. Ikeuchi. The Complex EGI: New Representation for 3-D Pose Determination. IEEE Trans. PAMI, Vol.15, pp.707-721, July 1993.
23. 23.M.van Kreveld, R.van Ostrum, C. Bajaj, V. Pascucci and D. Schikore. Contour Trees and Small Seed Sets for Isosurface Traversal. Proc. Symp. Computational Geometry, pp.212-220, 1997.
24. 24.F. Korn, N. Sidiropoulos, C. Faloutsos, E. Siegel and Z. Protopapas. Fast nearest neighbor search in medical image databases. Proc. Int'l Conf. Very Large Data Bases, pp.215- 226, 1996.
25. 25.M. Lanthier, A. Maheshwari and J. Sack. Approximating Weighted Shortest Paths on Polyhedral Surfaces. Proc. Symp. Computational Geometry, pp.274-283, 1999.
26. 26.F. Lazarus and A. Verroust. Level Set Diagrams of Polyhedral Objects. Proc. Symp. Solid Modeling, pp.130-140, 1999.
27. 27.C. Lu and J. Dunham. Shape Matching Using Polygon Approximation and Dynamic Alignment. Pattern Recognition Letters, Vol.14, pp.945-949, 1993.
28. 28.J.S.B. Mitchell, D.M. Mount and C.H. Papadimitriou. The Discrete Geodeic Problem. SIAM J. Computing, Vol.16, pp.647-667, 1987.
29. 29.R. Osada, T. Funkhouser, B. Chazelle and D. Dobkin. Matching 3D Models with Shape Distribution. Proc. Shape Modeling Int'l, 2001.
30. 30.G. Reeb. Sur les points singuliers d'une forme de Pfaff completement integrable ou d'une fonction numerique {On the Singular Points of a Completely Integrable Pfaff Form or of a Numerical Function}. Comptes Randus Acad. Sciences Paris, Vol.222, pp.847-849, 1946.
31. 31.M. Sharir and A. Schorr. On Shortest Paths in Polyhedral Spaces. SIAM J. Computing, Vol.15, No.1, pp.193-215, February 1986.
32. 32.E.C. Sherbrooke, N.M. Patrikalakis and E. Brisson. An Algorithm for the Medial Axis Transform of 3D Polyhedral Solids. IEEE Trans. Visualization and Computer Graphics, Vol.2, No.1, pp.44-61, 1996.
33. 33.Y. Shinagawa, T.L. Kunii and Y.L. Kergosien. Surface Coding Based on Morse Theory. IEEE Computer Graphics and Applications, Vol.11, No.5, pp.66-78, September 1991.
34. 34.K. Siddiqi, A. Shokoufandeh, S. J. Dickinson, and S. W. Zucker. Shock graphs and shape matching. Int'l J. Computer Vision, pp. 222-229, 1998.
35. 35.R. Sonthi, G. Kunjur and R. Gadh. Shape Feature Determination using the Curvature Region Representation. Proc. Symp. Solid Modeling, pp.285-296, 1997.
36. 36.S. Takahashi, Y. Shinagawa and T.L. Kunii. A Featurebased Approach for Smooth Surfaces. Proc. Symp. Solid Modeling, pp.97-110, 1997.
37. 37.S.P. Tarasov and M.N. Vyalyi. Construction of Contour Trees in 3D in O(n log n) Steps. Proc. Symp. Computational Geometry, pp.68-75, 1998.
38. 38.J.H. Vandenbrande and A.A.G. Requicha. Spatial Reasoning for the Automatic Recognition of Machinable Features in Solid Models. IEEE Trans. PAMI, Vol.15, pp.1269-1285, 1993.
39. 39.W. Wang and S.S. Iyengar. Efficient Data Structures for Model-based 3-D Object Recognition and Localization from Range Images. IEEE Trans. PAMI, Vol.14, pp.1035-1045, 1992.
40. 40.I. Weiss and M .Ray. Model-Based Recognition of 3D Object from Single Vision. IEEE Trans. PAMI, Vol.23, pp.116-128, 2001.
41. 41.Y. Zhou, A. Kaufman and A.W. Toga. Three-dimensional skeleton and centerline generation based on an approximate minimum distance field. The Visual Computer, Vol.14, No.7, pp.303-314, 1998.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Image and video acquisition

        • 3D imaging

  • Computer graphics

    • Animation

  • Machine learning