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

We consider the problem of labeling connected components in a gray-scale image 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. We develop two asymptotically optimal θ(n) time algorithms for generating such labelings on a mesh-connected computer when the image is mapped onto the mesh with one pixel per processor. The first algorithm operates directly on the image and is based on a divide-and-conquer approach. Although it is simple, it 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. It works with a graph representation of the image and it allows larger components to be formed from smaller ones by taking into account properties and characteristics of the smaller components.