About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE Transactions on Pattern Analysis and Machine Intelligence
Paper
An EREW PRAM Algorithm for Image Component Labeling
Abstract
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