| Objects in three dimensions, and their two-dimensional images, are approximated digitally by sets of voxels ("volume elements") or pixels ("picture elements"), respectively. Digital geometry is the study of geometric properties of digitized objects (or digitized images of objects); it deals both with the definitions of such properties and with algorithms for their computation. In particular, digital topology deals with properties of a "topological" nature (particularly, properties that involve the concepts of connectedness or adjacency, but do not depend on size or shape), and with algorithms that compute or preserve such properties. Topological properties and algorithms play a fundamental role in the analysis of two- and three-dimensional digital images. This book deals with basic topological algorithms; it presents their underlying theory and also discusses their applications.
An object is always understood to be (arcwise) connected, and the same is therefore true for images of the object obtained from any viewpoint. Thus if a three- (or two-) dimensional digital image can be segmented into "object" and "background" voxels (or pixels), the connected components of the object voxels or pixels are the individual objects (or their images). Connected component labeling is the process of assigning a distinct label to the voxels (pixels) that belong to each distinct object. The first chapter, by Shapiro, defines the problem of connected component labeling and gives sequential and parallel solutions, including efficient sequential algorithms (due to Lumia et al.) for labeling connected components in both two- and three-dimensional digital images. An algorithm for constructing the graph representing the pairwise adjacencies of the components is also presented. An appendix to this chapter, coauthored by the editors, provides a simple proof of the correctness of Lumia's algorithms.
The second chapter, coauthored by Hall and the editors, discusses shrinking algorithms, which reduce the sizes of the components in an image. Shrinking to a topological equivalent reduces the number of object pixels while preserving the topology of the image (i.e., not changing the connectivity properties of the objects or the background). In shrinking to a residue, holes in objects are not preserved, but each object is shrunk to a single isolated pixel (called a residue) which may then be deleted. The chapter discusses parallel algorithms for both kinds of shrinking, but focuses on shrinking to a residue. |
