Algorithms for image component labeling on SIMD mesh-connected computers

Two 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 S. Levialdi (1972) and have time complexities of O(N log N) bit operations, making them the fastest local algorithms for the problem. Compared to other approaches with similar or better asymptotic time complexities, this local approach greatly simplifies the algorithms and reduces the constants of proportionality by nearly two orders of magnitude, making them the first practical algorithms for the problem. The two algorithms differ in the amount of memory required per processing element; the first uses O(N) bits, while the second uses a novel compression scheme to reduce the requirement to O(log N ) bits