Parallel algorithms for determining k-width connectivity in binary images

In this paper we consider a new form of connectivity in binary images, called k-width connectivity. Two pixels a and b of value "1" are in the same k-width component if and only if there exists a path of width k such that a is one of the k start pixels and b is one of the k end pixels of this path. We present characterizations of the k-width components and show how to determine the k-width components of an n × n image in O(n) and O(log2n) time on a mesh of processors and hypercube, respectively, when the image is stored with one pixel per processor. Our methods use a reduction of the k-width-connectivity problem to the 1-width-connectivity problem. A distributed, space-efficient encoding of the k-width components of small size allows us to represent the solution using O(1) registers per processor. Our hypercube algorithm also implies an algorithm for the shuffle-exchange network