Skip to main content
SpringerLink
Log in

Skeleton pruning as trade-off between skeleton simplicity and reconstruction error

  • Research Paper
  • Published:
Science China Information Sciences Aims and scope Submit manuscript

Abstract

Skeletons can be viewed as a compact shape representation in that each shape can be completely reconstructed from its skeleton. However, the usefulness of a skeletal representation is strongly limited by its instability. Skeletons suffer from contour noise in that small contour deformation may lead to large structural changes in the skeleton. A large number of skeleton computation and skeleton pruning approaches has been proposed to address this issue. Our approach differs fundamentally in the fact that we cast skeleton pruning as a trade-off between skeleton simplicity and shape reconstruction error. An ideal skeleton of a given shape should be the skeleton with a simplest possible structure that provides a best possible reconstruction of a given shape. To quantify this trade-off, we propose that the skeleton simplicity corresponds to model simplicity in the Bayesian framework, and the shape reconstruction accuracy is expressed as goodness of fit to the data. We also provide a simple algorithm to approximate the maximum of the Bayesian posterior probability which defines an order for iteratively removing the end branches to obtain the pruned skeleton. Presented experimental results obtained without any parameter tuning clearly demonstrate that the resulting skeletons are stable to boundary deformations and intra class shape variability.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Siddiqi K, Pizer S. Medial Representations: Mathematics, Algorithms and Applications. Berlin: Springer, 2008

    Book  MATH  Google Scholar 

  2. Blum H. Biological shape and visual science (part I). J Theor Biol, 1973, 38: 205–287

    Article  Google Scholar 

  3. August J, Siddiqi K, Zucker S. Ligature instabilities and the perceptual organization of shape. Comput Vis Image Und, 1999, 76: 231–243

    Article  Google Scholar 

  4. Dimitrov P, Phillips C, Siddiqi K. Robust and efficient skeletal graphs. In: CVPR. Hilton Head Island: IEEE, 2000. 417–423

    Google Scholar 

  5. Siddiqi K, Bouix S, Tannenbaum A, et al. Hamilton-Jacobi skeletons. Int J Comput Vision, 2002, 48: 215–231

    Article  MATH  Google Scholar 

  6. Aslan C, Tari S. An axis-based representation for recognition. In: ICCV. Beijing: IEEE, 2005. 1339–1346

    Google Scholar 

  7. Torsello A, Hancock E. Correcting curvature-density effects in the Hamilton-Jacobi skeleton. IEEE Trans Image Process, 2006, 15: 887–891

    Article  Google Scholar 

  8. Borgefors G, Ramella G, di Baja G S. Hierarchical decomposition of multiscale skeleton. IEEE Trans Pattern Anal, 2001, 13: 1296–1312

    Article  Google Scholar 

  9. Katz R, Pizer S. Untangling the blum medial axis transform. Int J Comput Vision, 2003, 55: 139–153

    Article  Google Scholar 

  10. Bai X, Latecki L, Liu W Y. Skeleton pruning by contour partitioning with discrete curve evolution. IEEE Trans Pattern Anal, 2007, 29: 449–462

    Article  Google Scholar 

  11. Bai X, Latecki L. Discrete skeleton evolution. In: EMMCVPR. Ezhou: Springer, 2007. 362–374

    Google Scholar 

  12. Eede M, Macrini D, Telea A, et al. Canonical skeletons for shape matching. In: ICPR. Hong Kong: IEEE, 2006. 64–69

    Google Scholar 

  13. Ward A, Hamarneh G. Gmat: the Groupwise Medial Axis Transform for Fuzzy Skeletonization and Intelligent Pruning. Technical Report. School of Computing Science, Simon Fraser University, 2008

    Google Scholar 

  14. Ward A, Hamarneh G. The groupwise medial axis transform for fuzzy skeletonization and pruning. IEEE Trans Pattern Anal, 2010, 32: 1084–1096

    Article  Google Scholar 

  15. Aslan C, Erdem A, Erdem E, et al. Disconnected skeleton: shape at its absolute scale. IEEE Trans Pattern Anal, 2008, 30: 2188–2203

    Article  Google Scholar 

  16. Bai X, Latecki L. Path similarity skeleton graph matching. IEEE Trans Pattern Anal, 2008, 30: 1282–1292

    Article  Google Scholar 

  17. Macrini D, Siddiqi K, Dickinson S. From skeletons to bone graphs: medial abstraction for object recognition. In: CVPR. Anchorage: IEEE, 2008. 1–8

    Google Scholar 

  18. Bai X, Wang X G, Latecki L, et al. Active skeleton for non-rigid object detection. In: ICCV. Kyoto: IEEE, 2009. 575–582

    Google Scholar 

  19. Levinshtein A, Sminchisescu C, Dickinson S. Multiscale symmetric part detection and grouping. In: ICCV. Kyoto: IEEE, 2009. 2162–2169

    Google Scholar 

  20. Adluru N, Latecki L J, Lakaemper R, et al. Contour grouping based on local symmetry. In: ICCV. Rio de Janeiro: IEEE, 2007. 1–8

    Google Scholar 

  21. Latecki L, Lakeamper R, Eckhardt U. Shape descriptors for non-rigid shapes with a single closed contour. In: CVPR. Hilton Head Island: IEEE, 2000. 424–429

    Google Scholar 

  22. Arcelli C, di Baja G S. A width-independent fast thinning algorithm. IEEE Trans Pattern Anal, 1985, 7: 463–474

    Article  Google Scholar 

  23. Pudney C. Distance-ordered homotopic thinning: a skeletonization algorithm for 3d digital images. Comput Vis Image Und, 1998, 72: 404–413

    Article  Google Scholar 

  24. Leymarie F, Levine M. Simulating the grassfire transaction form using an active contour model. IEEE Trans Pattern Anal, 1992, 14: 56–75

    Article  Google Scholar 

  25. Golland P, Grimson E. Fixed topology skeletons. In: CVPR. Hilton Head Island: IEEE, 2000. 10–17

    Google Scholar 

  26. Tang Y, You X. Skeletonization of ribbon-like shapes based on a new wavelet function. IEEE Trans Pattern Anal, 2003, 25: 1118–1133

    Article  Google Scholar 

  27. Brandt J, Algazi V. Continuous skeleton computation by voronoi diagram. CVGIP: Image Und, 1992, 55: 329–338

    Article  MATH  Google Scholar 

  28. Ogniewicz R, Kübler O. Hierarchic voronoi skeletons. Pattern Recogn, 1995, 28: 343–359

    Article  Google Scholar 

  29. Mayya N, Rajan V. Voronoi diagrams of polygons: a framework for shape representation. In: CVPR. Seattle: IEEE, 1994. 638–643

    Google Scholar 

  30. Arcelli C, di Baja G S. Euclidean skeleton via center-of-maximal-disc extraction. Image Vision Comput, 1993, 11: 163–173

    Article  Google Scholar 

  31. Malandain G, Fernandez-Vidal S. Euclidean skeletons. Image Vision Comput, 1998, 16: 317–327

    Article  Google Scholar 

  32. Choi W P, Lam K M, Siu W C. Extraction of the euclidean skeleton based on a connectivity criterion. Pattern Recogn, 2003, 36: 721–729

    Article  MATH  Google Scholar 

  33. Kimmel R, Shaked D, Kiryati N, et al. Skeletonization via distance maps and level sets. Comput Vis Image Und, 1995, 3: 382–391

    Article  Google Scholar 

  34. Ge Y, Fitzpatrick J. On the generation of skeletons from discrete euclidean distance maps. IEEE Trans Pattern Anal, 1996, 18: 1055–1066

    Article  Google Scholar 

  35. Meyer F. Skeletons and perceptual graphs. Signal Process, 1989, 16: 335–363

    Article  MathSciNet  Google Scholar 

  36. Maragos P, Schafer R W. Morphological skeleton representation and coding of binary images. IEEE Trans Acoust Speech Signal Proc, 1986, 34: 1228–1244

    Article  Google Scholar 

  37. Goutsias J, Schonfeld D. Morphological representation of discrete and binary images. IEEE Trans Pattern Anal, 1991, 39: 1369–1379

    Google Scholar 

  38. Kresch R, Malah D. Morphological reduction of skeleton redundancy. Signal Process, 1994, 38: 143–151

    Article  Google Scholar 

  39. Zhu S, Yuille A. Forms: a flexible object recognition and modeling system. Int J Comput Vision, 1996, 20: 187–212

    Article  Google Scholar 

  40. Sebastian T, Klein P, Kimia B. Recognition of shapes by editing their shock graphs. IEEE Trans Pattern Anal, 2004, 26: 550–571

    Article  Google Scholar 

  41. Liu T, Geiger D, Kohn R. Representation and self-similarity of shapes. In: ICCV. Bombay: IEEE, 1998. 1129–1135

    Google Scholar 

  42. Siddiqi K, Shokoufandeh A, Dickinson S, et al. Shock graphs and shape matching. Int J Comput Vis, 1999, 35: 13–32

    Article  Google Scholar 

  43. Shaked D, Bruckstein A. Pruning medial axes. Comput Vis Image Und, 1998, 69: 156–169

    Article  Google Scholar 

  44. Mokhtarian F, Mackworth A. A theory of multiscale, curvature-based shape representation for planar curves. IEEE Trans Pattern Anal, 1992, 14: 789–805

    Article  Google Scholar 

  45. Gold C, Thibault D, Liu Z. Map generalization by skeleton retraction. In: ICA Workshop on Map Generalization. Ottawa: ICA, 1999

    Google Scholar 

  46. Jiang H B, Liu W P, Wang D, et al. Case: connectivity-based skeleton extraction in wireless sensor network. In: INFOCOM. Rio de Janeiro: IEEE, 2009. 2916–2920

    Google Scholar 

  47. Krinidis S, Chatzis V. A skeleton family generator via physics-based deformable models. IEEE Trans Image Process, 2009, 18: 1–11

    Article  MathSciNet  Google Scholar 

  48. Choi H, Choi S, Moon H. Mathematical theory of medial axis transform. Pac J Math, 1997, 181: 57–88

    Article  MathSciNet  Google Scholar 

  49. Feldman J, Singh M. Bayesian estimation of the shape skeleton. Proc Natl Acad Sci U. S. A., 2006, 103: 18,014–18,019

    MathSciNet  Google Scholar 

  50. Belongie S, Malik J, Puzicha J. Shape matching and object recognition using shape contexts. IEEE Trans Pattern Anal, 2002, 24: 509–522

    Article  Google Scholar 

  51. Shen W, Bai X, Hu R, et al. Skeleton growing and pruning with bending potential ratio. Pattern Recogn, 2011, 44: 196–209

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electronics and Information Engineering, Huazhong University of Science and Technology, Wuhan, 430074, China

    Wei Shen & Xiang Bai

  2. Department of Computer and Information Sciences, Temple University, Philadelphia, PA, 19122, USA

    XingWei Yang & Longin Jan Latecki

Authors
  1. Wei Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiang Bai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. XingWei Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Longin Jan Latecki
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xiang Bai.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Shen, W., Bai, X., Yang, X. et al. Skeleton pruning as trade-off between skeleton simplicity and reconstruction error. Sci. China Inf. Sci. 56, 1–14 (2013). https://doi.org/10.1007/s11432-012-4715-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11432-012-4715-3

Keywords

Search

Navigation