TESTS FOR CONNECTIVITY PRESERVATION FOR PARALLEL REDUCTION OPERATORS

Connectivity preservation is a concern in the design of image processing algorithms for parallel reduction processes like thinning where connected components in 2-D images are reduced to medial axis approximations. Tests and proof techniques, which use local support for their computations, have been presented by Rosenfeld, Ronse and others to prove preservation of connectivity for reduction classes of thinning algorithms. In this paper the earlier Rosenfeld proof techniques are characterized as connectivity preservation tests for rectangular and hexagonal tessellations and simplified versions of these tests are developed. The later Ronse tests are characterized for rectangular and hexagonal tessellations; the Ronse test complexities are evaluated; and relevant equivalences are identified between the Rosenfeld and Ronse test forms. It is shown that forms of the Ronse tests for rectangular and hexagonal tessellations are derivable directly and simply from tests derived from the earlier Rosenfeld proof techniques. Arguments are given to establish under what operator support restrictions these tests are necessary and sufficient proofs for key connectivity preservation properties. Finally, a specific computer-based implementation of the Ronse test is described with extensions for reduction operators with larger supports and with reduction operators using subfields notions; and time performance results are given for this implementation.