Concepts of digital topology (Q1205564)

In computer graphics and image processing one sometimes wants to apply the concept of connectedness in binary images. Here a binary image can be viewed as a partition of a set of image points \(V\) into two subsets; points in one subset are called black points, and points in the other subset are called white points. The usual way to define connectedness in a binary image is to first choose two symmetric irreflexive binary ``adjacency'' relations \(\rho_ B\) and \(\rho_ W\) on the set of all image points, and then to say that a set \(S\) of black (white) points is connected iff the graph of the restriction of \(\rho_ B\) (of \(\rho_ W)\) to \(S\) is connected. In the important practical cases \(V=\mathbb{Z}^ 2\) and \(V=\mathbb{Z}^ 3\), the adjacency relations \(\rho_ B\) and \(\rho_ W\) chosen for this purpose have almost always satisfied the following conditions: 1. If \(p,q\in V\) differ in only one coordinate and differ by just 1 in that coordinate then \((p,q)\in\rho_ B\cap\rho_ W\). 2. If \((p,q)\in\rho_ B\cup\rho_ W\) then no coordinate of \(p\) differs from the same coordinate of \(q\) by more than 1. However, it is well known that some pairs of irreflexive symmetric relations \((\rho_ B,\rho_ W)\) that satisfy these two conditions yield definitions of connectedness in a binary image that are ``paradoxical''. In these cases the derived notions of connectedness are not at all analogous to the notion of connectedness in Euclidean space -- for example, the discrete analog of the Jordan Curve Theorem may fail in the case \(V=\mathbb{Z}^ 2\). This raises the following question. Question: Among those pairs of irreflexive, symmetric relations \((\rho_ B,\rho_ W)\) on \(\mathbb{Z}^ 2\) and \(\mathbb{Z}^ 3\) that satisfy conditions 1 and 2 above, which pairs yield good notions of connectedness in binary images? This paper gives an answer. The concept of a strongly normal digital picture space (DPS) is defined. It is shown that if a pair of adjacency relations corresponds to a strongly normal DPS then that pair of adjacency relations will yield a rather well-behaved concept of connectedness for binary images. On the other hand, it follows from simple arguments given in this paper that pairs of adjacency relations for which conditions 1 and 2 hold but which do not correspond to a strongly normal DPS are unsatisfactory in certain respects. The digital fundamental group is a ``fundamental group'' for binary images. The main theorem shows that in a strongly normal DPS the connectedness properties and digital fundamental groups of binary images are analogous to the connectedness properties and fundamental groups of connected polyhedra and their complements in the plane or 3-space. Here the meaning of ``are analogous to'' is made precise by the concept of a continuous analog. Two definitions of the digital fundamental group, one discrete and one involving continuous deformation, are shown to be equivalent up to a natural isomorphism.