Skip to main content
SpringerLink
Log in

A Skeletal Measure of 2D Shape Similarity

  • Conference paper
  • First Online:
Visual Form 2001 (IWVF 2001)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2059))

Included in the following conference series:

Abstract

This paper presents a geometric measure that can be used to gauge the similarity of 2D shapes by comparing their skeletons. The measure is defined to be the rate of change of boundary length with distance along the skeleton. We demonstrate that this measure varies continuously when the shape undergoes deformations. Moreover, we show that ligatures are associated with low values of the shape-measure. The measure provides a natural way of overcoming a number of problems associated with the structural representation of skeletons. The first of these is that it allows us to distinguish between perceptually distinct shapes whose skeletons are ambiguous. Second, it allows us to distinguish between the main skeletal structure and its ligatures, which may be the result of local shape irregularities or noise.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. C. Arcelli and G. Sanniti di Baja. A width-independent fast thinning algorithm. IEEE Trans. on PAMI, 7(4):463–474, 1985.

    Google Scholar 

  2. J. August, K. Siddiqi, and S. W. Zucker. Ligature instabilities in the perceptual organization of shape. Comp. Vision and Image Und., 76(3):231–243, 1999.

    Article  Google Scholar 

  3. J. August, A. Tannenbaum, and S. W. Zucker. On the evolution of the skeleton. In ICCV, pages 315–322, 1999.

    Google Scholar 

  4. H. Blum. Biological shape and visual science (part I). Journal of theoretical Biology, 38:205–287, 1973.

    Article  MathSciNet  Google Scholar 

  5. G. Borgefors, G. Ramella, and G. Sanniti di Baja. Multi-scale skeletons via permanence ranking. In Advances in Visual Form Analysis, 31–42, 1997.

    Google Scholar 

  6. S. Bouix and Kaleem Siddiqi. Divergence-based medial surfaces. In Computer Vision ECCV 2000, 603–618. Springer, 2000. LNCS 1842.

    Chapter  Google Scholar 

  7. P. J. Giblin and B. B. Kimia. On the local form and transitions of symmetry sets, medial axes, and shocks. In ICCV, 385–391, 1999.

    Google Scholar 

  8. B. B. Kimia and K. Siddiqi. Geometric heat equation and nonlinear di usion of shapes and images. Comp. Vision and Image Understanding, 64(3):305–322, 1996.

    Article  Google Scholar 

  9. B. B. Kimia, A. R. Tannenbaum, and S. W. Zucker. Shapes, shocks, and deforamtions I. International Journal of Computer Vision, 15:189–224, 1995.

    Article  Google Scholar 

  10. P. Klein et al. A tree-edit-distance algorithm for comparing simple, closed shapes. In ACM-SIAM Symp. on Disc.e Alg., 1999.

    Google Scholar 

  11. R. L. Ogniewicz. A multiscale mat from voronoi diagrams: the skeleton-space and its application to shape description and decomposition. In Aspects of Visual Form Processing, 430–439, 1994.

    Google Scholar 

  12. R. L. Ogniewicz and O. Kübler. Hierarchic voronoi skeletons. Pattern Recognition, 28(3):343–359, 1995.

    Article  Google Scholar 

  13. S. J. Osher and J. A. Sethian. Fronts propagating with curvature dependent speed: Algorithms based on hamilton-jacobi formulations. J. of Comp. Physics, 79:12–49, 1988.

    Article  MATH  MathSciNet  Google Scholar 

  14. M. Pelillo, K. Siddiqi, and S. W. Zucker. Matching hierarchical structures using association graphs. PAMI, 21(11):1105–1120, 1999.

    Google Scholar 

  15. D. Sharvit, J. Chan, H. Tek, and B. B. Kimia. Symmetry-based indexing of image database. J. of Visual Comm. and Image Rep., 9(4):366–380, 1998.

    Article  Google Scholar 

  16. A. Shokoufandeh, S. J. Dickinson, K. Siddiqi, and S. W. Zucker. Indexing using a spectral encoding of topological structure. In CVPR, 1999.

    Google Scholar 

  17. K. Siddiqi, S. Bouix, A. Tannenbaum, and S. W. Zucker. The hamilton-jacobi skeleton. In ICCV, 828–834, 1999.

    Google Scholar 

  18. K. Siddiqi and B. B. Kimia. A shock grammar for recognition. In CVPR, 507–513, 1996.

    Google Scholar 

  19. K. Siddiqi, A. Shokoufandeh, S. J. Dickinson, and S. W. Zucker. Shock graphs and shape matching. International Journal of Computer Vision, 35(1):13–32, 1999.

    Article  Google Scholar 

  20. S. Tirthapura et al. Indexing based on edit-distance matching of shape graphs. In SPIE Int. Symp. on Voice, Video, and Data Comm., 25–36, 1998.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, University of York, Heslington, York, YO10 5DD, UK

    Andrea Torsello & Edwin R. Hancock

Authors
  1. Andrea Torsello
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Edwin R. Hancock
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Istituto di Cibernetica, Via Toiano 6, 80072, Arco Felice (Naples), Italy

    Carlo Arcelli  & Gabriella Sanniti di Baja  & 

  2. Dipartimento di Informatica e Sitemistica, Universitá di Napoli “Frederico II”, Via Claudio 21, 80125, Naples, Italy

    Luigi P. Cordella

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Torsello, A., Hancock, E.R. (2001). A Skeletal Measure of 2D Shape Similarity. In: Arcelli, C., Cordella, L.P., di Baja, G.S. (eds) Visual Form 2001. IWVF 2001. Lecture Notes in Computer Science, vol 2059. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45129-3_23

Download citation

  • DOI: https://doi.org/10.1007/3-540-45129-3_23

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42120-7

  • Online ISBN: 978-3-540-45129-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation