We present a parallel component labelling algorithm that is based on a "divide-and-conquer" strategy and is suited for coarse-grained MIMD parallel machines. The complexity of the algorithm is analyzed and timings on an Intel iPSC/2® hypercube are given. Furthermore, we measure the load imbalance for a number of images and establish general theoretical upper bounds for it. We also indicate how a good static load balance can be achieved.
Embrechts H., Roose D., Wambacq P., "Component labelling on a MIMD multiprocessor", Journal of image understanding (CVGIP), vol. 57, no. 2, pp. 155-165, March 1993, Academic Press Inc.