Connected component labeling on coarse grain parallel computers: An experimental study

Connected component labeling is a fundamental task in computer vision. This paper presents parallel implementations of connected component labeling for grey level images on the iPSC/2 and iPSC/86O hypercubes, the CM-5, and on the shared memory Encore Multimax multiprocessor. Several partitioning and mapping strategies, including multidimensional divide and conquer, block decomposition, and scatter decomposition, for different multiprocessor sizes, are used. Implementation results, performance evaluation and comparison for all the mapping strategies are reported. The block and scatter decomposition methods are simple to implement given the sequential algorithm, but their performance is sensitive to the distribution of intensity values in the image. The multidimensional divide and conquer method is more difficult to implement, but it performs the best irrespective of the intensity value distribution.