A homological version of a result of digital topology
Keywords:
hereditarily homology-simple, acyclic space, critical kernel, P-simple, binary digital image, parallel thinning, skeletonization, Khalimsky $n$-spaceAbstract
Let $\mathcal{F}$ be any collection of subspaces of a topological space and let $\mathcal{D} \subseteq \mathcal{F}$. We say $\mathcal{D}$ is homology-simple in $\mathcal{F}$ if the inclusion map of $\cup(\mathcal{F} \backslash \mathcal{D})$ in $\cup \mathcal{F}$ induces homology group isomorphisms in all dimensions, and say $\mathcal{D}$ is hereditarily homology-simple in $\mathcal{F}$ if every subcollection of $\mathcal{D}$ is homology-simple in $\mathcal{F}$.
Thinning algorithms are used in image processing to simplify binary images. An $n \mathrm{D}$ binary image may be regarded as a representation of a finite collection of closed $n$-cubes that are grid cells of an $n \mathrm{D}$ Cartesian grid. Then the goal of thinning is to reduce such a collection of grid cells to a subcollection that is a "thin skeleton" of the collection. Thinning algorithms are commonly designed in such a way that, if $\mathcal{J}_{\text {in }}$ is the original collection of grid cells and $\mathcal{J}_{\text {skel }}$ the resulting skeleton, then $\mathcal{F}_{\text {in }} \backslash \mathcal{F}_{\text {skel }}$ is homology-simple in $\mathcal{F}_{\text {in }}$. We call this the homology preservation condition.
For $n \in\{2,3,4\}$, a theorem of Bertrand and Couprie implies a local characterization of the hereditarily homology-simple subcollections of any finite collection $\mathcal{F}$ of $n \mathrm{D}$ Cartesian grid cells. The theorem and the implied characterization of hereditary homologysimpleness can be used to design good parallel thinning algorithms that automatically satisfy the homology preservation condition, and can also be useful for verifying that a proposed parallel thinning algorithm satisfies that condition.
Bertrand and Couprie's work makes no explicit use of homology. It is based on collapsing of complexes and depends on $\mathcal{F}$ being part of a cubical complex of dimension $\leq 4$. This paper shows how their theorem can be restated using homology, and shows that the restated theorem is valid under much weaker hypotheses than were assumed in the original theorem. For example, it is valid whenever $\mathcal{F}$ is a finite collection of acyclic polyhedra in $\mathbb{R}^n$ whose nonempty intersections are acyclic, and whenever $\mathcal{F}$ is a finite collection of acyclic open sets (of any topological space) whose nonempty intersections are acyclic. We also deduce a characterization of hereditary homology-simpleness in the case where $\mathcal{F}$ is a finite collection of singleton subspaces of Khalimsky $n$-space.
References
P. S. Aleksandrov. Combinatorial Topology, Vol. 1. Graylock Press, 1956.
L. A. Ankeney and G. X. Ritter. Cellular topology and its applications in image processing. International Journal of Computer and Information Sciences, 12:433456, 1983.
M. A. Armstrong. Basic Topology. Springer, New York, 1983.
G. Bertrand. On P-simple points. Comptes Rendus de l'Académie des Sciences de Paris, Série I, 321:1077-1084, 1995.
G. Bertrand. On critical kernels. Comptes Rendus Mathématique, 345:363-367, 2007.
G. Bertrand and M. Couprie. Two-dimensional parallel thinning algorithms based on critical kernels. Journal of Mathematical Imaging and Vision, 31:35-56, 2008.
G. Bertrand and M. Couprie. On parallel thinning algorithms: minimal non-simple sets, $P$-simple points and critical kernels. Journal of Mathematical Imaging and Vision, 35:2335, 2009.
G. Bertrand and M. Couprie. Powerful parallel and symmetric SD thinning schemes based on critical kernels. Journal of Mathematical Imaging and Vision, 48:134-148, 2014.
G. Bertrand and M. Couprie. Isthmus based parallel and symmetric SD thinning algorithms. Graphical Models, 80:1-15, 2015.
G. Bertrand and M. Couprie. Parallel skeletonization algorithms in the cubic grid based on critical kernels. In: P. K. Saha, G. Borgefors, and G. Sanniti di Baja, editors, Skeletonization: Theory, Methods and Applications. Elsevier, pp. 181-210, 2017. HAL open access version: hal-01613008.
L. Comić and B. Nagy. A description of the diamond grid for topological and combinatorial analysis. Graphical Models, 100:33-50, 2018.
M. Couprie and G. Bertrand. New characterizations of simple points in 2D, 9D, and 4D discrete spaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31:637-648, 2009.
M. Couprie and G. Bertrand. Asymmetric parallel SD thinning scheme and algorithms based on isthmuses. Pattern Recognition Letters, 76:22-31, 2016.
R. Courant and H. Robbins. What is Mathematics?, 2nd ed., revised by I. Stewart. Oxford University Press, 1996.
H. Edelsbrunner and J. Harer. Computational Topology: An Introduction. American Mathematical Society, 2010.
S. Eilenberg and N. Steenrod. Foundations of Algebraic Topology. Princeton University Press, 1952.
R. Engelking. General Topology, revised and completed edition. Heldermann, 1989.
C. J. Gau and T. Y. Kong. Minimal nonsimple sets of voxels in binary images on a face-centered cubic grid. International Journal of Pattern Recognition and Artificial Intelligence, 13:485-502, 1999.
C. J. Gau and T. Y. Kong. Minimal nonsimple sets in 4D binary images. Graphical Models, 65:112-130,2003.
R. W. Hall. Fast parallel thinning algorithms: parallel speed and connectivity preservation. Communications of the ACM, 32:124-131, 1989.
R. W. Hall. Tests for connectivity preservation for parallel reduction operators. Topology and Its Applications, 46:199-217, 1992.
A. Hatcher. Algebraic Topology. Cambridge University Press, 2001.
G. T. Herman. On topology as applied to image analysis. Computer Vision, Graphics, and Image Processing, 52:409-415, 1990.
G. T. Herman. Geometry of Digital Spaces. Birkhäuser, 1998.
P. J. Hilton and S. Wylie. Homology Theory. Cambridge University Press, 1965.
P. P. Jonker. Discrete topology on $N$-dimensional square tessellated grids. Image and Vision Computing, 23:213-225, 2005.
P. P. Jonker and O. Vermeij. On skeletonization in 4D images. In P. Perner, P. Wang, and A. Rosenfeld, editors, Advances in Structural and Syntactical Pattern Recognition: 6th International Workshop (SSPR 1996, Leipzig, Germany, August 1996), Proceedings, pp. 79-89. Springer, 1996.
G. Karai and P. Kardos. Distance-based skeletonization on the BCC grid. Acta Cybernetica, 25:351-367, 2021.
P. Kardos and K. Palágyi. On topology preservation of mixed operators in triangular, square, and hexagonal grids. Discrete Applied Mathematics, 216:441-448, 2017.
E. D. Khalimsky. Pattern analysis of $n$-dimensional digital images. Proceedings of the 1986 IEEE International Conference on Systems, Man and Cybernetics (Atlanta, GA, U.S.A., October 1986), pp. 1559-1562. IEEE, 1986.
E. D. Khalimsky. Motion, deformation and homotopy in finite spaces. Proceedings of the 1987 IEEE International Conference on Systems, Man and Cybernetics (Alexandria, VA, U.S.A., October 1987), pp. 227-234. IEEE, 1987.
E. D. Khalimsky, R. D. Kopperman, and P. R. Meyer. Computer graphics and connected topologies on finite ordered sets. Topology and Its Applications, 36:117, 1990.
C. O. Kiselman. Elements Of Digital Geometry, Mathematical Morphology, and Discrete Optimization. World Scientific, 2022.
R. Klette and A. Rosenfeld. Digital Geometry. Morgan Kaufmann, 2004.
T. Y. Kong. On the problem of determining whether a parallel reduction operator for $n$-dimensional binary images always preserves topology. In R. A. Melter and A. Y. Wu, editors, Vision Geometry II (Boston, MA, U.S.A., September 1993), Proceedings, pp. 69-77. Proc. SPIE 2060, 1993.
T. Y. Kong. On topology preservation in 2D and SD thinning. International Journal of Pattern Recognition and Artificial Intelligence, 9:813-844, 1995.
T. Y. Kong. Topology-preserving deletion of 1's from 2-, 3-, and 4-dimensional binary images. In: E. Ahronovitz and C. Fiorio, editors, Discrete Geometry for Computer Imagery: 7th International Workshop (DGCI 1997, Montepellier, France, December 1997), Proceedings, pp. 3-18. Springer, 1997.
T. Y. Kong. The Khalimsky topologies are precisely those simply-connected topologies on $\mathbb{Z}^n$ whose connected sets include all $2 n$-connected sets but no ( $3^n-1$ )disconnected sets. Theoretical Computer Science, 305:221-235, 2003.
T. Y. Kong. Minimal non-simple and minimal non-cosimple sets in binary images on cell complexes. In A. Kuba, L. G. Nyúl, and K. Palágyi, editors, Discrete Geometry for Computer Imagery: 13th International Conference (DGCI 2006, Szeged, Hungary, October 2006), Proceedings, pp. 169-188. Springer, 2006.
T. Y. Kong. Minimal non-deletable sets and minimal non-codeletable sets in binary images. Theoretical Computer Science, 406:97-118, 2008.
T. Y. Kong. Critical kernels, minimal nonsimple sets, and hereditarily simple sets in binary images on n-dimensional polytopal complexes. In P. K. Saha, G. Borgefors, and G. Sanniti di Baja, editors, Skeletonization: Theory, Methods, and Applications, pp. 211-256. Academic Press, 2017.
T. Y. Kong and E. D. Khalimsky. Polyhedral analogs of locally finite topological spaces. In R. M. Shortt, editor, General Topology and Applications: Proceedings of the 1988 Northeast Conference, pp. 153-164. Marcel Dekker, 1990.
T. Y. Kong, R. D. Kopperman, and P. R. Meyer. A topological approach to digital topology. American Mathematical Monthly, 98:901-917, 1991.
T. Y. Kong and A. W. Roscoe. Characterizations of simply-connected finite polyhedra in 3-space. Bulletin of the London Mathematical Society, 17:575-578, 1985.
T. Y. Kong and A. Rosenfeld. Digital topology: Introduction and survey. Computer Vision, Graphics and Image Processing, 48:357-393, 1989.
T. Y. Kong and A. Rosenfeld, editors. Topological Algorithms for Digital Image Processing, Elsevier/North-Holland, Amsterdam, 1996.
T. Y. Kong, P. K. Saha, and A. Rosenfeld. Strongly normal sets of contractible tiles in $N$ dimensions. Pattern Recognition, 40:530-543, 2007.
R. D. Kopperman. The Khalimsky line as a foundation for digital topology. In
Y. L. O et al., editors, Shape in Picture: Mathematical Description of Shape in Grey-Level Images, pp. 3-20. Springer, 1994.
R. D. Kopperman, P. R. Meyer, and R. G. Wilson. A Jordan surface theorem for three-dimensional digital spaces. Discrete and Computational Geometry, 6:155161, 1991.
V. A. Kovalevsky. Finite topology as applied to image analysis. Computer Vision, Graphics and Image Processing, 46:141-161, 1989.
V. A. Kovalevsky. Finite topology and image analysis. In P. W. Hawkes, editor, Advances in Electronics and Electron Physics, vol. 84, pp. 197-259. Academic Press, 1992.
V. A. Kovalevsky. Topological foundations of shape analysis. In Y. L. O et al., editors, Shape in Picture: Mathematical Description of Shape in Grey-Level Images, pp. 21-36. Springer, 1994.
V. A. Kovalevsky and R. D. Kopperman. Some topology-based image processing algorithms. In S. Andima et al, editors, Papers on General Topology and Applications: Eighth Summer Conference at Queens College, pp. 174-182. Annals of the New York Academy of Sciences, vol. 728, 1994.
E. H. Kronheimer. A note on alternative digital topologies. Topology and Its Applications, 46:269-277, 1992.
E. H. Kronheimer. The topology of digital images. Topology and Its Applications, 46:279303, 1992.
C. M. Ma. On topology preservation in SD thinning. CVGIP: Image Understanding, 59:328-339, 1994.
A. Manzanera, T. M. Bernard, F. Prêteux, and B. Longuet. N-dimensional skeletonization: a unified mathematical framework. Journal of Electronic Imaging, 11:25-37, 2002.
W. S. Massey. A Basic Course in Algebraic Topology. Springer, 1991.
C. R. F. Maunder. Algebraic Topology. Cambridge University Press, 1980.
M. C. McCord. Singular homology groups and homotopy groups of finite topological spaces. Duke Mathematical Journal, 33:465-474, 1966.
J. R. Munkres. Elements of Algebraic Topology. Addison-Wesley, 1984.
M. Niethammer, W. D. Kalies, K. Mischaikow, and A. Tannenbaum. On the detection of simple points in higher dimensions using cubical homology. IEEE Transactions on Image Processing, 15:2462-2469, 2006.
N. Otter, M. A. Porter, U. Tillmann, P. Grindrod, and H. Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, 6:17, 2017.
C. Ronse. A topological characterization of thinning. Theoretical Computer Science, 43:31-41, 1986.
C. Ronse. Minimal test patterns for connectivity preservation in parallel thinning algorithms for binary digital images. Discrete Applied Mathematics, 21:67-79, 1988.
A. Rosenfeld. A characterization of parallel thinning algorithms. Information and Control, 29:286-291, 1975.
P. K. Saha, G. Borgefors, and G. Sanniti Di Baja, editors. Skeletonization: Theory, Methods, and Applications. Academic Press, 2017.
P. K. Saha, T. Y. Kong, and A. Rosenfeld. Strongly normal sets of tiles in N dimensions. Electronic Notes in Theoretical Computer Science, 46:309-320, 2001. M. A. Shtan'ko and M. I. Shtogrin. On the embedding of cubic manifolds and complexes in a cubic lattice. Russian Mathematical Surveys, 47(1):267-268, 1992.
E. H. Spanier. Algebraic Topology, 3rd ed. Springer, 1994.
J. R. Stallings. Lectures on Polyhedral Topology. Tata Institute of Fundamental Research, 1967.
R. Stefanelli and A. Rosenfeld. Some parallel thinning algorithms for digital pictures. Journal of the Association for Computing Machinery, 18:255-264, 1971.
R. Strand. Surface skeletons in grids with non-cubic voxels. Proceedings of the 17th International Conference on Pattern Recognition (ICPR 2004, Cambridge, U.K., August 2004), Vol. 1, pp. 548-551. IEEE Computer Society, 2004.
