Skip to main content
SpringerLink
Log in

Retrieving articulated 3-D models using medial surfaces

  • Original Paper
  • Published:
Machine Vision and Applications Aims and scope Submit manuscript

Abstract

We consider the use of medial surfaces to represent symmetries of 3-D objects. This allows for a qualitative abstraction based on a directed acyclic graph of components and also a degree of invariance to a variety of transformations including the articulation of parts. We demonstrate the use of this representation for 3-D object model retrieval. Our formulation uses the geometric information associated with each node along with an eigenvalue labeling of the adjacency matrix of the subgraph rooted at that node. We present comparative retrieval results against the techniques of shape distributions (Osada et al.) and harmonic spheres (Kazhdan et al.) on 425 models from the McGill Shape Benchmark, representing 19 object classes. For objects with articulating parts, the precision vs recall curves using our method are consistently above and to the right of those of the other two techniques, demonstrating superior retrieval performance. For objects that are rigid, our method gives results that compare favorably with these methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alt, H., Aichholzer, O., Rote, G.: Matching Shapes With a Reference Point. In: Proceedings of the Tenth Annual Symposiusm On Computational Geometry, pp. 85–92 (1994)

  2. Amenta N., Choi S. and Kolluri R. (2001). The power crust, unions of balls, and the medial axis transform. Comput. Geometry. Theory Appl. 19(2): 127–153

    Article  MATH  MathSciNet  Google Scholar 

  3. Ankerst, M., Kastenmüller, G., Kriegel, H., Seidl, T.: 3D Shape Histograms for Similarity Search and Classification in Spatial Databases. In: Advances in Spatial Databases, 6th International Symposium, vol. 18, pp. 700–711 (1999)

  4. Besl P. and Jain R. (1985). Three-dimensional object recognition. ACM Comput. Surv. 17(1): 75–145

    Article  Google Scholar 

  5. Biederman I. (1987). Recognition–By–Components: a theory of human image understanding. Psychol. Rev. 94(2): 115–147

    Article  Google Scholar 

  6. Binford, T.O.: Visual Perception by Computer. In: IEEE Conference on Systems and Control (1971)

  7. Blum H. (1973). Biological Shape and Visual Science. J. Theor. Biol. 38: 205–287

    Article  MathSciNet  Google Scholar 

  8. Borgefors G. (1984). Distance Transformations in Arbitrary Dimensions. Comput. Vis. Graph. Image Process. 27: 321–345

    Article  Google Scholar 

  9. Borgefors G., Nyström I. and Sanniti di Baja G. (1999). Computing Skeletons in Three Dimensions. Pattern Recogn. 32(7): 1225–1236

    Article  Google Scholar 

  10. Campbell R.J. and Flynn P.J. (2001). A Survey of Free-Form Object Representation and Recognition Techniques. Comput. Vis. Image Understanding 81: 166–210

    Article  MATH  Google Scholar 

  11. Chin R. and Dyer C. (1986). Model-Based Recognition in Robot Vision. ACM Comput. Surv. 18(1): 67–108

    Article  Google Scholar 

  12. Cornea, N., Demirci, M., Silver, D., Shokoufandeh, A., Dickinson, S., Kantor, P.: 3D Object Retrieval using Many-to-many Matching of Curve Skeletons. In: Proceedings, IEEE International Conference on Shape Modeling and Applications, pp 368–373. Boston (2005)

  13. Culver T., Keyser J. and Manocha D. (2004). Exact Computation of the Medial Axis of a Polyhedron. Comput. Aided Geometric Des. 21(1): 65–98

    Article  MATH  MathSciNet  Google Scholar 

  14. Damon, J.N.: Geometry and medial structure. In: Siddiqi, K., Pizer, S.M. (eds.) Medial Representations: Mathematics, Algorithms and Applications. Springer, Heidelberg (2007) (to appear)

  15. Dimitrov P. (2003). Flux Invariants For Shape. McGill University, School of Computer Science, M.Sc. thesis

    Google Scholar 

  16. Dimitrov, P., Damon, J.N., Siddiqi, K.: Flux Invariants for Shape. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Madison (2003)

  17. van Eede, M., Macrini, D., Telea, A., Sminchisescu, C., S.: Canonical Skeletons for Shape Matching. In: Proceedings, International Conference on Pattern Recognition, Hong Kong (2006)

  18. Elad, M., Tal, A., Ar, S.: Content Based Retrieval of VRML Objects- An Iterative and Interactive Approach. In: 6th Europgraphics Workshop on Multimedia, pp. 107–118. Manchester (2001)

  19. Giblin P.J. and Kimia B.B. (2004). A formal Classification of 3D Medial Axis Points and Their Local Geometry. IEEE Trans. Pattern Anal. Mach. Intell. 26(2): 238–251

    Article  Google Scholar 

  20. Hamza, A.B., Krim, H.: Geodesic Object Representation and Recognition. In: Proceedings of DGCI, vol. LNCS 2886, pp. 378–387 (2003)

  21. Hilaga, M., Shinagawa, Y., Kohmura, T., Kunii, T.L.: Topology Matching for Fully Automatic Similarity Estimation of 3D Shapes. In: Proceedings of ACM SIGGRAPH, pp. 203–212 (2001)

  22. Ikeuchi K. and Kanade T. (1988). Automatic Generation of Object Recognition Programs. Proc. IEEE 76: 1016–1035

    Article  Google Scholar 

  23. Katayama, N., Satoh, S.: The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries. In: ACM SIGMOD International Conference on Management of Data, pp. 369–380 (1997)

  24. Kazhdan M., Chazelle B., Dobkin D., Funkhouser T. and Rusinkiewicz S. (2003). A Reflective Symmetry Descriptor for 3D Models. Algorithmica 38(1): 201–225

    Article  MathSciNet  Google Scholar 

  25. Kazhdan, M., Funkhouser, T., Rusinkiewicz, S.: Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors. In: Symposium on Geometry Processing (2003)

  26. Keselman Y. and Dickinson S.J. (2005). Generic Model Abstraction from Examples. IEEE Trans. Pattern Anal. Machine Intell. 27(7): 1141–1156

    Article  Google Scholar 

  27. Levinshtein A., Sminchisescu C. and Dickinson S.J. (2005). Learning Hierarchical Shape Models from Examples. In: Rangarajan, A., Vemuri, B.C., and Yuille, A.L. (eds) EMMCVPR, Lecture Notes in Computer Science, vol. 3757, pp 251–267. Springer, Heidelberg

    Google Scholar 

  28. Leymarie, F.F., Kimia, B.B.: Computation of the Shock Scaffold for Unorganized Point Clouds in 3D. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 821–827. Madison (2003)

  29. Lowe D.G. (2004). Distinctive Image Features from Scale-Invariant Keypoints. Int. J. Comput. Vis. 60(2): 91–110

    Article  Google Scholar 

  30. Malandain G., Bertrand G. and Ayache N. (1993). Topological Segmentation of Discrete Surfaces. Int. J. Comput. Vis. 10(2): 183–197

    Article  Google Scholar 

  31. Marr D. and Nishihara K.H. (1978). Representation and Recognition of the Spatial Organization of Three Dimensional Shapes. Proc. R. Soc. Lond. B 200: 269–294

    Google Scholar 

  32. Messmer, B., Bunke, H.: Subgraph Isomorphism in Polynomial Time. Tech. Rep. 95-003, IAM (1995). citeseer.nj.nec.com/messmer95subgraph.html

  33. Murase H. and Nayar S. (1995). Visual Learning and Recognition of 3D Objects from Appearance. Int. J. Comput. Vis. 14: 5–24

    Article  Google Scholar 

  34. Näf, M., Kübler, O., Kikinis, R., Shenton, M.E., Székely, G.: Characterization and Recognition of 3D Organ Shape in Medical Image Analysis Using Skeletonization. In: IEEE Workshop on Mathematical Methods in Biomedical Image Analysis (1996)

  35. Osada R., Funkhouser T., Chazelle B. and Dobkin D. (2002). Shape Distributions. ACM Trans. Graphics 21(4): 807–832

    Article  Google Scholar 

  36. Pellilo M., Siddiqi K. and Zucker S.W. (1999). Matching Hierarchical Structures Using Association Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 21(11): 1105–1120

    Article  Google Scholar 

  37. Pentland A. (1986). Perceptual Organization and the Representation of Natural Form. Artif. Intell. 28: 293–331

    Article  MathSciNet  Google Scholar 

  38. Pizer, S.M., Siddiqi, K., Székeley, G., Damon, J.N., Zucker, S.W.: Multiscale Medial Axes and Their Properties. Int. J. Comput. Vis. 55(3), (2003)

  39. Pudney C. (1998). Distance-Ordered Homotopic Thinning: A Skeletonization Algorithm for 3D Digital Images. Comput. Vis. Image Understanding 72(3): 404–413

    Article  Google Scholar 

  40. Reyner S.W. (1977). An Analysis of a Good Algorithm for the Subtree Problem. SIAM J. Comput. 6: 730–732

    Article  MATH  MathSciNet  Google Scholar 

  41. Rosch, E.: Principles of Categorization. In: Cognition and Categorization. L. Erlbaum Associates (1978)

  42. Sclaroff S. and Pentland A. (1995). Modal Matching for Correspondence and Recognition. IEEE Trans. Pattern Anal. Mach. Intell. 17(6): 545–561

    Article  Google Scholar 

  43. Sebastian T., Klein P. and Kimia B. (2004). Recognition of Shapes by Editing their Shock Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26: 551–571

    Article  Google Scholar 

  44. Sengupta K. and Boyer K. (1995). Organizing Large Structural Modelbases. IEEE Trans. Pattern Anal. Mach. Intell. 17(4): 321–332

    Article  Google Scholar 

  45. Sengupta K. and Boyer K. (1998). Modelbase Partitioning Using Property Matrix Spectra. Comput. Vis. Image Understanding 70(2): 177–196

    Article  MATH  Google Scholar 

  46. Shapiro L.G. and Haralick R.M. (1982). Organization of Relational Models for Scene Analysis. IEEE Trans. Pattern Anal. Mach. Intell. 4(6): 595–602

    Article  MATH  Google Scholar 

  47. Shilane, P., Min, P., Kazhdan, M., Funkhouser, T.: The Princeton Shape Benchmark. In: Shape Modeling International. Genova, Italy (2004)

  48. Shinagawa Y., Kunii T.L. and Kergosien Y.L. (1991). Surface Coding Based on Morse Theory. IEEE Trans. Comput. Graphics Appl. 11(5): 66–78

    Article  Google Scholar 

  49. Shokoufandeh, A., Dickinson, S.J., Jonsson, C., Bretzner, L., Lindeberg, T.: The Representation and Matching of Qualitative Shape at Multiple Scales. In: Proceedings, ECCV, pp. 759–775, Copenhagen (2002)

  50. Shokoufandeh, A., Dickinson, S.J., Siddiqi, K., Zucker, S.W.: Indexing Using a Spectral Encoding of Topological Structure. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 491–497. Fort Collins, (1999)

  51. Shokoufandeh A., Macrini D., Dickinson S., Siddiqi K. and Zucker S. (2005). Indexing Hierarchical Structures Using Graph Spectra. IEEE Trans. Pattern Anal. Mach. Intell. 27(7): 1125–1140

    Article  Google Scholar 

  52. Siddiqi K., Bouix S., Tannenbaum A. and Zucker S.W. (2002). Hamilton-Jacobi Skeletons. Int. J. Comput. Vis. 48(3): 215–231

    Article  MATH  Google Scholar 

  53. Siddiqi, K., Pizer, S.M.: Medial Representations: Mathematics, Algorithms and Applications. Springer, Heidelberg (2007) (to appear)

  54. Siddiqi K., Shokoufandeh A., Dickinson S.J. and Zucker S.W. (1999). Shock Graphs and Shape Matching. Int. J. Comput. Vis. 35(1): 13–32

    Article  Google Scholar 

  55. Sossa, H., Horaud, R.: Model Indexing: The Graph-Hashing Approach. In: Proceedings, IEEE CVPR, pp. 811–814 (1992)

  56. Stolpner, S., Siddiqi, K.: Revealing Significant Medial Structure in Polyhedral Meshes. In: Third International Symposium on 3D Data Processing, Visualization and Transmission. Chapel Hill (2006)

  57. Sundar, H., Silver, D., Gagvani, N., Dickinson, S.: Skeleton Based Shape Matching and Retrieval. In: International Conference On Shape Modeling International and Applications, pp. 130–142. Seoul (2003)

  58. Turk M. and Pentland A. (1991). Eigenfaces for Recognition. J. Cogn. Neurosci. 3(1): 71–86

    Article  Google Scholar 

  59. Vranic, D., Saupe, D.: 3D Model Retrieval With Spherical Harmonics and Moments. In: Proceedings of the DAGM, pp. 392–397 (2001)

  60. Zhang, J., Kaplow, R., Chen, R., Siddiqi, K.: The McGill Shape Benchmark (2005). http://www.cim.mcgill.ca/~shape/benchMark/

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Centre for Intelligent Machines, McGill University, Montreal, QC, H3A 2A7, Canada

    Kaleem Siddiqi & Juan Zhang

  2. Department of Computer Science, University of Toronto, Toronto, ON, M5S 3G4, Canada

    Diego Macrini & Sven Dickinson

  3. Department of Computer Science, Drexel University, Philadelphia, PA, 19104, USA

    Ali Shokoufandeh

  4. Psychiatry Neuroimaging Laboratory, Harvard University Medical School, Boston, MA, 02115, USA

    Sylvain Bouix

Authors
  1. Kaleem Siddiqi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Diego Macrini
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ali Shokoufandeh
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Sylvain Bouix
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Sven Dickinson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kaleem Siddiqi.

Additional information

A preliminary version of this article was published in EMMCVPR 2005. In this extended version we have included results on the significantly larger McGill Shape Benchmark, making a stronger case for the advantages of our method for models with articulating parts. We have also included expanded introduction, medial surface computation, matching, indexing, experimental results, and discussion sections, along with several new figures.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Siddiqi, K., Zhang, J., Macrini, D. et al. Retrieving articulated 3-D models using medial surfaces. Machine Vision and Applications 19, 261–275 (2008). https://doi.org/10.1007/s00138-007-0097-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00138-007-0097-8

Keywords

Search

Navigation