Title :
An EREW PRAM algorithm for image component labeling
Author :
Cypher, R. ; Sanz, J. L C ; Snyder, L.
Author_Institution :
Dept. of Comput. Sci., Washington Univ., Seattle, WA, USA
fDate :
3/1/1989 12:00:00 AM
Abstract :
An important midlevel task for computer vision is addressed. The problem consists of labeling connected components in N1/2 ×N2/2 binary images. This task can be solved with parallel computers by using a simple and novel algorithm. The parallel computing model used 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 has O(log N) complexity. The algorithm can run on parallel machines other than the EREW PRAM. In particular, it offers an optimal image component labeling algorithm for mesh-connected computers
Keywords :
computational complexity; computer vision; parallel algorithms; random-access storage; EREW PRAM algorithm; binary images; computer vision; exclusive-read exclusive-write parallel RAM; image component labeling; mesh-connected computers; parallel algorithm; parallel processing; synchronous fine-grained shared-memory model; Computer science; Computer vision; Concurrent computing; Image processing; Labeling; Parallel algorithms; Parallel processing; Phase change random access memory; Pixel; Read-write memory;
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
