Tests for connectivity preservation for parallel reduction operators (Q1205563)

This work arises from the need to analyze topological properties such as connectedness in applications for image processing and computer graphics. The context: A two-dimensional digital image space (call it an image space) is the set of cells, called pixels, obtained by a rectangular or hexagonal tessellation of the real plane. A two-dimensional binary digital image (call it a digital image) is a partition of the image space into two sets, where the pixels in one set are called 1's and the pixels in the other are called 0's. For a fixed image space, an image processing operator maps the set of all digital images into itself. Such operators are used in various ways -- e.g., to simplify or improve an image. A reduction operator is an operator which may change 1's to 0's, but never 0's to 1's. This paper is about an important class of reduction operators: the connectivity-preserving reduction operators, which are required to preserve the ``connected components'' of the set of 1's and the set of 0's. (One standard application of connectivity-preserving reduction operators is in thinning algorithms, which are used to reduce the set of 1's in a digital image to a skeleton that is ``digital deformation retract'' of that set.) For operators which change only a single pixel at each application (these are called sequential operators) simple necessary and sufficient conditions for the operator to preserve connectivity are well known. We come now to the parallel reduction operators of the title. Parallel operators change large numbers of pixels simultaneously, making the issue of connectivity preservation much more complex. How can one tell whether or not such operators preserve connectivity? The present paper discusses and develops tests to determine whether a given parallel reduction operator preserves the connected components of 1's and of 0's for all possible input images. It is important to note that these tests have efficient computer implementations. The notions of connectivity used here are based on graph-theoretic rather than topological definitions. For a discussion of the relation between these two approaches, see [\textit{T. Y. Kong}, \textit{R. Kopperman} and \textit{P. R. Meyer}, Am. Math. Mon. 98, No. 10, 901-917 (1991; Zbl 0761.54036)]. This paper is part of a collection of related papers; see [\textit{T. Y. Kong}, \textit{R. Kopperman} and \textit{P. R. Meyer}, Topology App. 46, No. 3, 173-179 (1992; Zbl 0762.54035)].