© 1996, Topology Atlas

Computer scientists concerned with problems in pattern recognition, image analysis, and related areas have found that fundamental concepts of topology are useful tools. Although the usual definitions of topology are generally not suited to the analysis of digital pictures, they are easily modified so that notions such as connected component, continuous function, homotopy type, fundamental group, the Hausdorff metric, and others, can be efficiently and profitably employed. Examples of image analysis and pattern recognition problems that benefit from the use of topological considerations include:

• Thinning, an important operation in image analysis, one of whose goals is to reduce data without altering crucial topological properties such as connectivity and homotopy type.
• Use of the Hausdorff metric as a measure of how well one image approximates another. This is particularly useful when one of the images is subjected to rigid motion so as to minimize the Hausdorff metric.
• Use of homotopy invariants such as the fundamental group to compare the forms of objects.

The mathematical challenge of digital topology lies in the fact that a digital image is a lattice-point approximation of a Euclidean space. Since a Euclidean metric imposes a discrete topology on a set of lattice points, it is necessary to use a non-Euclidean foundation as the basis of a theory that allows us to use topological properties in this setting. The usual approach to digital topology, then, starts with a notion of connectedness based on adjacent pixels. From this notion of connectedness, we can build analogs of topology's classical notions of continuous function, fundamental group, etc., that yield invariants and properties that capture the geometric feel of their Euclidean analogs.

Azriel Rosenfeld is generally considered to be the founder of digital topology as an area of research. His paper, (Rosenfeld 1979), is one of the pioneering publications in the field, and he and his collaborators have authored many of the important papers in the area. The references given below are perhaps representative, but are only a small sampling, of the literature of digital topology.

Boxer, L. (1994). Digitally continuous functions, Pattern Recognition Letters 15, 833-839.

Kong, T.Y. (1989). A digital fundamental group, Computers and Graphics 13, 159-166.

Kong, T.Y., A.W. Roscoe, and A. Rosenfeld (1992). Concepts of digital topology, Topology and its Applications 46, 219-262.

Latecki, L. and F. Prokop (1995). Semi-proximity continuous functions in digital images, Pattern Recognition Letters 16, 1175-1187.

Rosenfeld, A. (1979). Digital topology, American Mathematical Monthly 86, 621-630.

Rosenfeld, A. (1986). `Continuous' functions on digital pictures, Pattern Recognition Letters 4, 177-184.

Shonkwiler, R. (1989). An image algorithm for computing the Hausdorff distance efficiently in linear time, Information Processing Letters 30, 87-89.

Stout, Q.F. (1983). Topological matching, Proc. 15th Annual Symp. on Theory of Computing, 24-31.