Abstract
The development of digital imaging (and its subsequent applications) has led to consideration and investigation of topological notions that are well-defined in continuous spaces, but not necessarily in discrete/digital ones. In this article, we focus on the classical notion of path. We establish in particular that the standard definition of path in algebraic topology is coherent w.r.t. the ones (often empirically) used in digital imaging. From this statement, we retrieve, and actually extend, an important result related to homotopy-type preservation, namely the equivalence between the fundamental group of a digital space and the group induced by digital paths. Based on this sound definition of paths, we also (re)explore various (and sometimes equivalent) ways to reduce a digital image in a homotopy-type preserving fashion.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alexandroff, P.: Diskrete Räume. Rec. Math. [Mat. Sb.] N.S. 2, 501–519 (1937)
Arenas, F.G.: Alexandroff spaces. Acta Math. Univ. Comen. 68(1), 17–25 (1999)
Barmak, J.A., Minian, E.G.: Minimal finite models. J. Homotopy Relat. Struct. 2(1), 127–140 (2007)
Barmak, J.A., Minian, E.G.: One-point reductions of finite spaces, h-regular CW-complexes and collapsibility. Algebraic Geom. Topol. 8(3), 1763–1780 (2008)
Barmak, J.A., Minian, E.G.: Simple homotopy types and finite spaces. Adv. Math. 218(1), 87–104 (2008)
Bertrand, G.: New notions for discrete topology. In: Bertrand, G., Couprie, M., Perroton, L. (eds.) Discrete Geometry for Computer Imagery–DGCI’99, 8th International Conference, Proceedings, Marne-la-Vallee, France, 17–19 March 1999. Lecture Notes in Computer Science, vol. 1568, pp. 218–228. Springer, Berlin (1999)
Cointepas, Y.: Modélisation homotopique et segmentation tridemensionnelle du cortex cérébral à partir d’IRM pour la résolution des problèmes directs et inverses en EEG et en MEG. Ph.D. thesis, ENST (1999)
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)
Duda, O., Hart, P.E., Munson, J.H.: Graphical data processing research study and experimental investigation. Technical Report AD650926, Stanford Research Institute (1967)
Hardie, K.A., Vermeulen, J.J.C.: Homotopy theory of finite and locally finite T 0-spaces. Expo. Math. 11, 331–341 (1993)
Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)
Hilton, P.J., Wylie, S.: Homology Theory. Cambridge University Press, Cambridge (1960)
Khalimsky, E.: Topological structures in computer science. J. Appl. Math. Stoch. Anal. 1(1), 25–40 (1987)
Khalimsky, E., Kopperman, R., Meyer, P.R.: Computer graphics and connected topologies on finite ordered sets. Topol. Appl. 36(1), 1–17 (1990)
Klette, R.: Topologies on the planar orthogonal grid. In: International Conference on Pattern Recognition–ICPR’02, 16th International Conference, Proceedings, Québec, Canada, 11–15 August 2002, vol. 2, pp. 354–357. IEEE Comput. Soc., Los Alamitos (2002)
Kong, T.Y.: A digital fundamental group. Comput. Graph. 13(2), 159–166 (1989)
Kong, T.Y.: The Khalimsky topologies are precisely those simply connected topologies on Z n whose connected sets include all 2n-connected sets but no (3n−1)-disconnected sets. Theor. Comput. Sci. 305(1–3), 221–235 (2003)
Kong, T.Y., Kopperman, R., Meyer, P.R.: A topological approach to digital topology. Am. Math. Mon. 98(12), 901–917 (1991)
Kovalevsky, V.A.: Finite topology as applied to image analysis. Comput. Vis. Graph. Image Process. 46(2), 141–161 (1989)
Kukieła, M.: On homotopy types of Alexandroff spaces. Order 27(1), 9–21 (2010)
Latecki, L.J.: Multicolor well-composed pictures. Pattern Recognit. Lett. 16(4), 425–431 (1995)
Lee, C., Poston, T., Rosenfeld, A.: Holes and genus of 2D and 3D digital images. Graph. Models Image Process. 55(1), 20–47 (1993)
Lohou, C.: Contribution à l’analyse topologique des images: étude d’algorithmes de squelettisation pour images 2D et 3D selon une approche topologie digitale ou topologie discrète. Ph.D. thesis, Université de Marne-la-Vallée, France (2001)
Maunder, C.R.F.: Algebraic Topology. Dover, New York (1996)
May, A.: A Concise Course in Algebraic Topology. University of Chicago Press, Chicago (1999)
May, J.P.: Finite spaces and simplicial complexes (2008)
May, J.P.: Finite topological spaces (2008)
Mazo, L., Passat, N., Couprie, M., Ronse, C.: Digital imaging: A unified topological framework. Technical Report hal-00512270, Université Paris-Est (2010)
McCord, M.C.: Singular homology groups and homotopy groups of finite topological spaces. Duke Math. J. 33(3), 465–474 (1966)
Munkres, J.: Topology. Prentice Hall, New York (1999)
Osaki, T.: Reduction of finite topological spaces. Interdiscip. Inf. Sci. 5(2), 149–155 (1999)
Ronse, C.: An isomorphism for digital images. J. Comb. Theory, Ser. A 39(2), 132–159 (1985)
Rosenfeld, A.: Connectivity in digital pictures. J. Assoc. Comput. Mach. 17(1), 146–160 (1970)
Rosenfeld, A., Pfaltz, J.L.: Sequential operations in digital picture processing. J. Assoc. Comput. Mach. 13(4), 471–494 (1966)
Spanier, E.H.: Algebraic Topology. McGraw-Hill, New York (1966)
Stong, R.E.: Finite topological spaces. Trans. Am. Math. Soc. 123(25), 325–340 (1966)
Viro, O.Ya., Ivanov, O.A., Netsvetaev, N.Yu., Kharlamov, V.M.: Elementary Topology: Problem Textbook. AMS, Providence (2008)
Whitehead, J.H.C.: Simplicial spaces, nuclei and m-groups. Proc. Lond. Math. Soc. (2) 45(1), 243–327 (1939)
Whitehead, J.H.C.: Combinatorial homotopy. I. Bull. Am. Math. Soc. 55, 213–245 (1949)
Whitehead, J.H.C.: Combinatorial homotopy. II. Bull. Am. Math. Soc. 55, 453–496 (1949)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mazo, L., Passat, N., Couprie, M. et al. Paths, Homotopy and Reduction in Digital Images. Acta Appl Math 113, 167–193 (2011). https://doi.org/10.1007/s10440-010-9591-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10440-010-9591-5