Solving nonuniform problems on SIMD computers: Case study on region growing

Abstract

Nonuniform problems are characterized by a behavior that is data dependent and cannot be determined at compile time. Currently, no formal methods for implementation or evaluation exist for this class of algorithms. This paper presents an implementation of the region growing problem, which is representative of one class of nonuniform problems, on a highly parallel SIMD computer. The region growing paradigm for image segmentation groups neighboring pixels into regions depending upon a predetermined homogeneity criteria. Our algorithm is based upon a parallel merging paradigm, which involves the selection of the best of all merge possibilities for all regions concurrently. A key requirement of any parallel region growing scheme is the ability to concurrently compute functions on irregular shaped regions. A set of general primitive functions for region growing is defined and techniques for implementing these functions on an SIMD processor are developed. These techniques make use of an embedded tree data structure to represent regions. The results of implementing a parallel split-and-merge region growing algorithm on the Massively Parallel Processor are discussed. A comparison is made to an MIMD implementation of the algorithm on the Intel iPSC/2 hypercube. The SIMD approach is shown to be efficient primarily for images involving large numbers of regions.