Skip to main content
SpringerLink
Log in

On Parallel Thinning Algorithms: Minimal Non-simple Sets, P-simple Points and Critical Kernels

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

Critical kernels constitute a general framework in the category of abstract complexes for the study of parallel homotopic thinning in any dimension. In this article, we present new results linking critical kernels to minimal non-simple sets (MNS) and P-simple points, which are notions conceived to study parallel thinning in discrete grids. We show that these two previously introduced notions can be retrieved, better understood and enriched in the framework of critical kernels. In particular, we propose new characterizations which hold in dimensions 2, 3 and 4, and which lead to efficient algorithms for detecting P-simple points and minimal non-simple sets.

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. Alexandroff, P.S.: Diskrete Räume. Math. Sb. 2(3), 501–518 (1937)

    MATH  Google Scholar 

  2. Bertrand, G.: On P-simple points. C. R. Acad. Sci., Sér. Math. I(321), 1077–1084 (1995)

    MathSciNet  Google Scholar 

  3. Bertrand, G.: Sufficient conditions for 3D parallel thinning algorithms. In: SPIE Vision Geometry IV, vol. 2573, pp. 52–60 (1995)

  4. Bertrand, G.: On critical kernels. C. R. Acad. Sci., Sér. Math. I(345), 363–367 (2007)

    MathSciNet  Google Scholar 

  5. Bertrand, G., Couprie, M.: A new 3D parallel thinning scheme based on critical kernels. In: Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science, vol. 4245, pp. 580–591. Springer, Berlin (2006)

    Chapter  Google Scholar 

  6. Bertrand, G., Couprie, M.: Two-dimensional parallel thinning algorithms based on critical kernels. J. Math. Imaging Vis. 31(1), 35–56 (2008)

    Article  MathSciNet  Google Scholar 

  7. Bing, R.H.: Some aspects of the topology of 3-manifolds related to the Poincaré conjecture. Lect. Mod. Math. II, 93–128 (1964)

    MathSciNet  Google Scholar 

  8. Burguet, J., Malgouyres, R.: Strong thinning and polyhedric approximation of the surface of a voxel object. Discrete Appl. Math. 125, 93–114 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  9. Cohen, M.M.: A Course in Simple Homotopy Theory. Springer, Berlin (1973)

    MATH  Google Scholar 

  10. Couprie, M.: Note on fifteen 2d parallel thinning algorithms. Internal Report, Université de Marne-la-Vallée, IGM2006-01 (2006)

  11. Couprie, M., Bertrand, G.: New characterizations of simple points in 2D, 3D and 4D discrete spaces. IEEE Trans. Pattern Anal. Mach. Intell. 31(4), 637–648 (2009)

    Article  Google Scholar 

  12. Gau, C.-J., Kong, T.Y.: Minimal non-simple sets in 4D binary images. Graph. Models 65, 112–130 (2003)

    Article  MATH  Google Scholar 

  13. Giblin, P.: Graphs, Surfaces and Homology. Chapman and Hall, London (1981)

    MATH  Google Scholar 

  14. Hall, R.W.: Tests for connectivity preservation for parallel reduction operators. Topol. Appl. 46(3), 199–217 (1992)

    Article  MATH  Google Scholar 

  15. Kaczynski, T., Mischaikow, K., Mrozek, M.: Computational Homology. Springer, Berlin (2004)

    MATH  Google Scholar 

  16. Khalimsky, E., Kopperman, R., Meyer, P.R.: Computer graphics and connected topologies on finite ordered sets. Topol. Appl. 36, 1–17 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  17. Kong, T.Y.: On topology preservation in 2-D and 3-D thinning. Int. J. Pattern Recognit. Artif. Intell. 9, 813–844 (1995)

    Article  Google Scholar 

  18. Kong, T.Y.: Topology-preserving deletion of 1’s from 2-, 3- and 4-dimensional binary images. In: Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science, vol. 1347, pp. 3–18. Springer, Berlin (1997)

    Google Scholar 

  19. Kong, T.Y.: Minimal non-simple and minimal non-cosimple sets in binary images on cell complexes. In: Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science, vol. 4245, pp. 169–188. Springer, Berlin (2006)

    Chapter  Google Scholar 

  20. Kong, T.Y.: Minimal non-deletable and minimal non-codeletable sets in binary images. Theor. Comput. Sci. 406(1–2), 97–118 (2008)

    Article  MATH  Google Scholar 

  21. Kong, T.Y., Gau, C.-J.: Minimal non-simple sets in 4-dimensional binary images with (8–80)-adjacency. In: International Workshop on Combinatorial Image Analysis, pp. 318–333 (2004)

  22. Kong, T.Y., Rosenfeld, A.: Digital topology: introduction and survey. Comput. Vis. Graph. Image Process. 48, 357–393 (1989)

    Article  Google Scholar 

  23. Kong, T.Y.: On the problem of determining whether a parallel reduction operator for N-dimensional binary images always preserves topology. In: Proc. SPIE Vision Geometry II, vol. 2060, pp. 69–77 (1993)

  24. Kong, T.Y., Litherland, R., Rosenfeld, A.: Problems in the topology of binary digital images. In: Open Problems in Topology, pp. 376–385. Elsevier, Amsterdam (1990)

    Google Scholar 

  25. Kovalevsky, V.A.: Finite topology as applied to image analysis. Comput. Vis. Graph. Image Process. 46, 141–161 (1989)

    Article  Google Scholar 

  26. Lohou, C., Bertrand, G.: A 3D 12-subiteration thinning algorithm based on P-simple points. Discrete Appl. Math. 139, 171–195 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  27. Lohou, C., Bertrand, G.: A 3D 6-subiteration curve thinning algorithm based on P-simple points. Discrete Appl. Math. 151, 198–228 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  28. Ma, C.M.: On topology preservation in 3d thinning. Comput. Vis. Graph. Image Process. 59(3), 328–339 (1994)

    Article  Google Scholar 

  29. Manzanera, A., Bernard, T.M., Prêteux, F., Longuet, B.: N-dimensional skeletonization: a unified mathematical framework. J. Electron. Imaging 11(1), 25–37 (2002)

    Article  Google Scholar 

  30. Maunder, C.R.F.: Algebraic Topology. Dover, New York (1996)

    Google Scholar 

  31. Ronse, C.: Minimal test patterns for connectivity preservation in parallel thinning algorithms for binary digital images. Discrete Appl. Math. 21(1), 67–79 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  32. Rosenfeld, A.: A characterization of parallel thinning algorithms. Inf. Control 29, 286–291 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  33. Whitehead, J.H.C.: Simplicial spaces, nuclei and m-groups. Proc. Lond. Math. Soc. 45(2), 243–327 (1939)

    Article  MATH  MathSciNet  Google Scholar 

  34. Zeeman, E.C.: On the dunce hat. Topology 2, 341–358 (1964)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Université Paris-Est, Laboratoire d’Informatique Gaspard-Monge, Équipe A3SI, ESIEE-Paris, Marne-la-Vallée, France

    Gilles Bertrand & Michel Couprie

Authors
  1. Gilles Bertrand
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michel Couprie
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michel Couprie.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bertrand, G., Couprie, M. On Parallel Thinning Algorithms: Minimal Non-simple Sets, P-simple Points and Critical Kernels. J Math Imaging Vis 35, 23–35 (2009). https://doi.org/10.1007/s10851-009-0152-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-009-0152-3

Keywords

Search

Navigation