Connected Component Labeling in Image Processing with MIMD (Multiple Instruction, Multiple Data) Architectures

摘要

Many higher level image processing algorithms suggest dynamic allocation of multiple processors to image processing subtasks. However, most parallel algorithms in image processing assume an SIMD (Single Instruction Multiple Data) architecture with processors statically assigned to one or a group of image pixels. For many vision tasks, fixed assignments of processors will inevitably lead to low parallelism. Instead, it seems natural to have an intermediate number of more powerful independent processors, each with access to the shared data, to perform tasks that tend to be more global in nature. In converting SIMD algorithms into efficient code for MIMD (Multiple Instruction Multiple Data) machines with relatively fewer processors, it can frequently be determined when processors are active and when they are dormant. By analyzing the dynamic flow of subtasks, we can attempt to assign processors to the portions of the image where non-null tasks would be accomplished in a more processor-rich environment. The authors study, as an example, the Shiloach/Vishkin connected component algorithm, which is an O(logN) SIMD algorithm which requires roughly 4N processors, where N is the number of pixels.