|
Published Articles >> Table of Contents >> Abstract
February 1991 (Vol. 13, No. 2)
pp. 202-207
Fast Image Labeling Using Local Operators on Mesh-Connected Computers
H.M. Alnuweiri
V.K. Prasanna Kumar
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/34.67649
Send link to a friend
| Abstract |
|
A new parallel algorithm is proposed for fat image labeling using local operators on image pixels. The algorithm can be implemented on an n*n mesh-connected computer such that, for any integer k in the range (1, log (2n)), the algorithm requires Theta (kn/sup 1/k/) bits of local memory per processor and takes Theta (kn) time. Bit-serial processors and communication links can be used without affecting the asymptotic time complexity of the algorithm. The time complexity of the algorithm has very small leading constant factors, which makes it superior to previous mesh computer labeling algorithms for most practical image sizes (e.g. up to 4096*4096 images). Furthermore, the algorithm is based on using stacks that can be realized using very fast shift registers within each processing element.
|
 References
|
[1] H. M. Alnuweiri and V. K. Prasanna Kumar, "Optimal geometric algorithms for fixed-size linear arrays and scan line arrays," inProc. IEEE Conf. Comput. Vision Pattern Recognition, 1988.
[2] H. M. Alnuweiri and V. K. Prasanna Kumar, "Optimal image computations on reduced VLSI architectures,"IEEE Trans. Circuits Syst., Oct. 1989.
[3] H. M. Alnuweiri and V. K. Prasanna Kumar, "Parallel architectures and algorithms for image component labeling," to be published.
[4] K. E. Batcher, "Design of a massively parallel processor,"IEEE Trans. Comput., vol. C-29, Sept. 1980.
[5] R. Cypher, J. L. C. Sanz, and L. Snyder, "Algorithms for image component labeling on SIMD mesh connected computers,"IEEE Trans. Comput., vol. 39, no. 2, Feb. 1990.
[6] C.R. Dyer and A. Rosenfeld, "Parallel image processing by memory augmented cellular automata,"IEEE Trans. Pattern Anal Machine Intell., vol. PAMI-3, Jan. 1981.
[7] T. J. Fountain, Processor Arrays:Architectures and Applications. London: Academic, 1987.
[8] S. B. Gray, "Local properties of binary images in two dimensions,"IEEE Trans. Comput., vol. C-20, May 1971.
[9] S. Levialdi, "On shrinking binary picture patterns,"Commun. ACM, Jan. 1972.
[10] D. Nassimi and S. Sahni, "Finding connected components and connected ones on a mesh-connected parallel computer,"SIAM J. Comput., vol. 9, no. 4, 1980.
[11] A. Rosenfeld, "Connectivity in digital pictures,"J. ACM, Jan. 1970.
[12] A. Rosenfeld and J. Pfaltz, "Sequential operations in digital picture processing,"J. ACM, vol. 4, 1966.
|
 Additional Information
|
Index Terms- computerised picture processing; parallel architectures; computational complexity; bit-serial processors; image labeling; local operators; mesh-connected computers; parallel algorithm; communication links; asymptotic time complexity; stacks; very fast shift registers; computational complexity; computerised picture processing; parallel algorithms; parallel architectures
Citation:
H.M. Alnuweiri, V.K. Prasanna Kumar,
"Fast Image Labeling Using Local Operators on Mesh-Connected Computers,"
IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 13,
no. 2,
pp. 202-207,
Feb.,
1991
|
|
RSS Feed