A duality in two connectivity-preserving parallel shrinking algorithms for binary images

Recognition and labeling binary images are important problems in image processing and machine vision. In this paper, we study two classical connectivity- preserving parallel shrinking algorithms proposed for recognition and labeling two-dimensional connected components of binary images. The algorithms we consider were developed by W. T. Beyer[3] and S. Levialdi[7] independently for the purpose of shrinking 4-connected and 8-connected components of binary images in linear time. We develop a duality property between those two algorithms. It is shown that those two independently developed algorithms are closely related and in a sense they are in a dual relation such that, for any initially given binary image and its inverted one, one algorithm produces, simultaneously, a dual image of the other step by step.