A Fast Algorithm for Image Component Labeling with Local Operators on Mesh Connected Computers
✍ Scribed by H.C. Shi; G.X. Ritter
- Publisher
- Elsevier Science
- Year
- 1994
- Tongue
- English
- Weight
- 562 KB
- Volume
- 23
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
A new parallel algorithm for image component labeling with local operators on SIMD mesh connected computers is presented. This algorithm provides a positive answer to the open question of whether there exists an (O(n))-time and (O(\log n))-space local labeling algorithm on SIMD mesh connected computers. The algorithm uses a pipeline mechanism with stack-like data structures to achieve the lower bound of (O(n)) in time complexity and (O(\log n)) in space complexity. Additionally, the algorithm has very small multiplicative constants in its complexities by using local parallelshrink and label-propagate operations. O 1994 Academic Press, Inc.