Fast image labeling using local operators on mesh-connected computers Conference Paper uri icon


  • A parallel algorithm is proposed for fast image labeling on mesh-connected computers using only local operators on image pixels. The algorithm requires O(kn1/k) bits of memory per processor and takes O(kn) time, for any integer k in the range [1, log n]. Bit-serial communication can be used among processors without affecting the asymptotic time complexity of the algorithm. The algorithm has a very small constant factor for the computation time, which makes it superior to previous mesh-computer labeling algorithms for most practical image sizes (e.g., up to 4096 4096 images). The algorithm is based on the use of stacks, which can be easily realized by using very fast shift registers within each PE. When k is a constant, the algorithm takes O(n) time and uses (n1/k) bits of memory per processor, which is quite small for most practical applications.

published proceedings

  • Proceedings of the International Conference on Parallel Processing

author list (cited authors)

  • Alnuweiri, H. M., & Prasanna Kumar, V. K.

complete list of authors

  • Alnuweiri, HM||Prasanna Kumar, VK

publication date

  • December 1989