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.


PostScript version of the paper