NPAC Technical Report SCCS-397
Solving the Region Growing Problem on the Connection Machine
N Copty, S Ranka, G Fox, R Shankar
Submitted December 11 1992
Abstract
Region growing is a general technique for image segmentation, where
image characteristics are used to group adjacent pixels together to
form regions. The region growing problem is a representative of one
type of loosely synchronous problems, known as adaptive irregular
problems, whose data objects evolve during the computation in a time
synchronized manner.
This paper presents a parallel algorithm for solving the region
growing problem based on the split and merge approach. The algorithm
was implemented on the Connection Machine, models CM-2 and CM-5, in
the data parallel and message passing programming models. The
performance of these implementations is examined and compared.
Although the region growing problem belongs to a class of irregular
problems, no new, sophisticated data structures were required to solve
the problem. Only one and two-dimensional arrays of data were used.
The algorithm is therefore highly portable on a wide variety of SIMD
and MIMD architectures.