Parallel algorithms for gray-scale image component labeling on a mesh-connected computer

We present two asymptotically optimal Θ(n) time algorithms for labeling the connected components of a gray-scale image on a mesh-connected computer. We assume that the input is an n × n gray-scale image mapped one pixel per processor onto an n × n mesh-connected computer. Our algorithms label the components so that every component is connected, the maximum difference in the gray-scale values of the pixels within any component does not exceed a given value, and no component can be merged with a neighboring component. The first algorithm is based on a divide-and-conquer approach. Although it is simple, this algorithm has the potential drawback of possibly assigning two adjacent pixels with the same gray-scale value to different components. The second algorithm avoids this potential drawback, and exploits the ability of a mesh-connected computer to efficiently determine a maximal independent set of a planar graph.