Algorithms for Image Component Labeling on SIMD Mesh-Connected Computers

Abstract

Two new parallel algorithms are presented for the problem of labeling the connected components of a binary image. The machine model is an SIMD two-dimensional mesh-connected computer consisting of an N× N array of processing elements, each containing a single pixel of an N × N image. Both new algorithms use a local “shrinking” operation defined by Levialdi and have time complexities of O(N log N) bit operations, making them the fastest local algorithms for the problem. Compared to other approaches having similar or better asymptotic. © 1990 IEEE