PARALLEL SIMULATED ANNEALING FOR SHAPE DETECTION

In this paper, we describe two parallel implementations of the simulat ed annealing method applied to the shape detection problem. The first is a massively parallel implementation on an SIMD mesh-connected archi tecture; the second uses an MIMD model of computation. The main focus of the paper is on restructuring the basic simulated annealing algorit hm to execute on a multiprocessor. We show how to select appropriate s ets of perturbations to be attempted at different temperatures to obta in good speed-ups. We give experimental results for the serial version of the algorithm applied to the detection of ellipses and parallelogr ams; we also present results obtained on an MIMD computer, the ENCORE MULTIMAX. (C) 1995 Academic Press, Inc.