In the paper we present parallel solutions for performing image contour ranking on coarse-grained machines. In contour ranking, a linear representation of the edge contours is generated from the edge contours of a raw image. We describe solutions that employ different divide-and-conquer approaches and that use different communication patterns. The combining step of the divide-and-conquer solutions uses efficient sequential techniques for merging information about subimages. The proposed solutions are implemented on Intel Delta and Intel Paragon machines. We discuss performance results and present scalability analysis using different image and machine sizes. © 1997 by John Wiley & Sons, Ltd.

We present analytical and experimental results for fine-grained list ranking algorithms. We compare the scalability of two representative algorithms on random lists, then address the question of how the locality properties of image edge lists can be used to improve the performance of this highly data-dependent operation. Starting with Wyllie's algorithm and Anderson and Miller's randomized algorithm as bases, we use the spatial locality of edge links to derive scalable algorithms designed to exploit the characteristics of image edges. Tested on actual and synthetic edge data, this approach achieves significant speedup on the MasPar MP-1 and MP-2, compared to the standard list ranking algorithms. The modified algorithms exhibit good scalability and are robust across a wide variety of image types. We also show that load balancing on fine grained machines performs well only for large problem to machine size ratios.

We describe a project that integrates applications requirements, parallel algorithm design, models of parallel computing, and software tools in order to improve the ability of applications researchers in the fields of computer vision and image processing (CVIP) to realize the performance potential of high performance parallel computers. This objective is achieved by pursuing four directions of research: the development of efficient and practical scalable algorithms for fundamental CVIP problems; the implementation of realistic CVIP scenarios on high performance computers; the development of a scalable, architecture-independent parallel model and a metric for estimating the performance of an algorithm on an existing parallel machine; and the development of prototype software tools. In this paper we describe work in each of these areas.