An EREW PRAM Algorithm for Image Component Labeling

In this paper, an important mid-level task for computer vision is addressed. The problem consists of labeling connected components in N1/2 x N1/20 binary images. This task can be solved with parallel computers by using a simple and novel algorithm. The parallel computing model used in this work is a synchronous fine-grained shared-memory model where only one processor can read from or write to the same memory location at a given time. This model is known as the exclusive-read exclusive-write parallel RAM (EREW PRAM). Using this model, the algorithm presented here has O (log N) complexity. Also, the algorithm can be run on parallel machines other than the EREW PRAM. In particular, it renders a new optimal image component labeling algorithm for mesh connected computers. © 1989 IEEE