Parallel image component labeling algorithms for mesh-connected processor arrays
Martin Brady, Whanki Yong · 1996
Image component labeling is useful for identifying individual objects in a digital image. The goal is to give the elements of each component a single label, distinct from that of the others. Image component labeling is a fundamental task in computer vision and image processing applications. In this thesis, we present new parallel algorithms for labeling 2-D and 3-D images. We use a reduced-size mesh model, consisting of 2-D or 3-D arrays of mesh-connected processors of a much smaller size than the input image. We develop algorithms that are both provably good and efficient in practice. A new 2-D efficient image component labeling algorithm for Single Instruction Multiple Data (SIMD) meshes is presented that has time complexity $O({N\over P} + N\sp{1\over 2})$ for an N = $n n$ binary image on a $P = p p$ mesh and is thus work-optimal for $P = O(N\sp{1\over 2}).$ Previous work-optimal labeling algorithms have been based on complex strategies that are impractical for reasonable image sizes. Practical local updating strategies have been devised for $n n$ meshes, but these are inefficient when $p < n.$ The algorithm described here is both local and work-optimal. It is shown to perform well over a wide variety of images on a MasPar MP-1, as compared to other local and global labeling algorithms. A new 3-D image component labeling algorithm for SIMD meshes is presented that has time complexity $O({N\over P} + N\sp{2\over 3}P\sp{1\over 3})$ for an $N = n \times n \times n$ binary image on a $P = p p p$ mesh and is thus work-optimal for $P = O(N\sp{1\over 4}).$ The algorithm extends the local labeling technique of the 2-D algorithm to three dimensions. The algorithm is also both local and work-optimal for a somewhat limited range of input sizes. Two mapping schemes are presented for mapping the 3-D algorithms to 2-D processor arrays. Implementation results on the MasPar MP-1 show that our algorithm is comparable to or better than other local and global algorithms for 3-D images.