Отправлено: 18.09.13 12:03. Заголовок: Concepts of digital topology

Topology and its Applications 46 (1992) 219-262
North-Holland

Concepts of digital topology
T.Y. Kong
A.W. Roscoe
A. Rosenfeld

Abstract
Kong, T.Y., A.W. Roscoe and A. Rosenfeld, Concepts of digital topology, Topology and its
Applications 46 (1992) 219-262.
In an earlier paper written for a different readership [Computers and Graphics 13(2) (1989)
159-1661 the first author defined a digitalfundamentalgroup-an analog, for binary digital pictures,
of the fundamental group. In general the definition of the digital fundamental group involves
continuous deformation. But an alternative, discrete, definition of the digital fundamental group
was proposed for the strongly normal digital picture spaces defined in the same paper. The
above-mentioned paper also defined a “continuous analog” C(p) for each binary digital picture
B on such a DPS (DPS = digital picture space). C(p) is a polyhedron constructed by “filling in
the gaps” between black points (l’s) of the binary digital picture B in a specific way. Other kinds
of continuous analog had previously been used by the first two authors.
In seeking the simplest and most efficient algorithms for performing image processing operations,
researchers have considered many different combinations of grids and adjacency relations. Almost
all of those combinations are isomorphic to special cases of the concept of a strongly normal DPS.
The main contribution of the present paper is a proof that the digital fundamental groups of
binary digital pictures on a strongly normal DPS are naturally isomorphic to the fundamental
groups of the digital pictures’ continuous analogs. We use this result to establish that on a strongly
normal DPS the discrete and continuous definitions of the digital fundamental group are
equivalent, up to a natural group isomorphism. We also show that many topological results which
hold in the Euclidean plane or Euclidean 3-space have analogs that hold in every strongly normal
DPS. Our results suggest that a strongly normal DPS is a suitable domain for studying topology-
related image processing operations such as thinning, border tracking and contour filling.
The definitions of digital fundamental group, strongly normal DPS and continuous analog are
included in this paper so as to make it self-contained.
Keywords: Strongly normal digital picture space, digital fundamental group, continuous analog,
polyhedral analog, digital topology, binary digital picture, binary digital image, border, adjacency
tree, connectedness, component, hole, tunnel, Euler characteristic, Jordan curve.