A parallel image segmentation algorithm using relaxation with varying neighborhoods and its mapping to array processors

This paper presents a segmentation algorithm based on deterministic relaxation with varying neighborhood structures for the segmentation of noisy images. The image is modeled as a discrete-valued Markov random field (MRF), or equivalently a Gibbs random field, corrupted by additive, independent, Gaussian noise; although, additivity and Gaussian assumptions are not necessary for the algorithm. The algorithm seeks to determine the maximum a posteriori (MAP) estimate of the noiseless scene. Using varying neighborhoods during relaxation helps pick up certain directional features in the image which are otherwise smoothed out. The parallelism of the algorithm is underscored by providing its mapping to mesh-connected and systolic array processors suitable for VLSI implementation. Segmentation results are given for 2- and 4-level Gibbs distributed and geometric images corrupted by noise of different levels. A comparative study of this segmentation algorithm with other relaxation algorithms and a single-sweep dynamic programming algorithm, all seeking the MAP estimate, is also presented.