Parallel thinning algorithms on multicomputers: experimental study on loadbalancing

In this work, a practical implementation of two parallel thinning algorithm s on a multicomputer system are described. The solution has been conceived for a multiprocessor using the SPMD (single program multiple data) programm ing model. Our main goal is intended to describe our experiences on data pa rtition/distribution among processors for parallel thinning algorithms as a representative type of algorithm where communications take place between n eighbor processors and the work load for each processor depends on the inpu t data. It will be shown how the efficiency of the parallel implementation can be improved through the application of a preprocess. This preprocess is based on the analysis of the work load balance. An analysis of the communi cation cost is also made. Although the results shown here are concerned wit h the implementations of two parallel thinning algorithms we think that our proposal about data distribution is general and useful for a wide set of a lgorithms in the field of image processing. Copyright (C) 2000 John Wiley & Sons, Ltd.