A Study of Connected Component Labeling Algorithms on the MPP
Susanne E. Hambrusch, Lynn TeWinkel · Purdue e-Pubs (Purdue University System) · 1988
In this paper we consider the problem of labeling the connected components of a binary image.We descnbe three different algorithms and variations thereof which we implemented on NASA's MPP.These algoritluns include a simple label propagation algorithm.a version of Levialdi's algorithm, and an asymptotically optimal divide-and-eonquer algorithm.We discuss the perfonnance of these algorithms on the MPP and provide insight into how special hardware features of the lvIPP influence the design of parallel algorithms.We also address the issue of how to handle images that are larger than the processor array of the MPP (Le.; images larger !ban 128xl28).