Connected Component Labeling on Coarse Grain Parallel Computers: An Experimental Study
✍ Scribed by A. Choudhary; R. Thakur
- Publisher
- Elsevier Science
- Year
- 1994
- Tongue
- English
- Weight
- 499 KB
- Volume
- 20
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
Connected component labeling is a fundamental task in computer vision. This paper presents parallel implementations of connected component labeling for grey level images on the iPSC/2 and iPSC (/ 860) hypercubes, the CM-5, and on the shared memory Encore Multimax multiprocessor. Several partitioning and mapping strategies, including multidimensional divide and conquer, block decomposition, and scatter decomposition, for different multiprocessor sizes, are used. Implementation results, performance evaluation and comparison for all the mapping strategies are reported. The block and scatter decomposition methods are simple to implement given the sequential algorithm, but their performance is sensitive to the distribution of intensity values in the image. The multidimensional divide and conquer method is more difficult to implement, but it performs the best irrespective of the intensity value distribution. O 1994 Academic Press, Inc.