TR-179: Parallel Algorithms for Determining K-width- Connectivity in Binary Images

Abstract

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 charac­terizations of the k-width-components and show how to determine the k-width-components of an n x n im­age in 0( n) and O(log2 n) time on a mesh of pro­cessors 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 I-width-connectivity problem. A distributed, space-efficient encoding of the k-width-components of small size allows us represent the solution using 0(1) registers per processor. Our hypercube algorithm also implies an algorithm for the shuffle-exchange network.