Parallel algorithms for gray-scale image component labeling on a mesh-connected computer
Susanne E. Hambrusch, Xin He, Russ Miller · 1992
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 x n gray-scale image mapped one pixel per processor onto an n x 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.