DocumentCode :
1309353
Title :
Euclidean distance transform for binary images on reconfigurable mesh-connected computers
Author :
Pan, Yi ; Hamdi, Mounir ; Li, Keqin
Author_Institution :
Dept. of Comput. Sci., Dayton Univ., OH, USA
Volume :
30
Issue :
1
fYear :
2000
fDate :
2/1/2000 12:00:00 AM
Firstpage :
240
Lastpage :
244
Abstract :
The distance calculation in an image is a basic operation in computer vision, pattern recognition, and robotics. Several parallel algorithms have been proposed for calculating the Euclidean distance transform (EDT). Recently, Chen and Chuang proposed a parallel algorithm for computing the EDT on mesh-connected SIMD computers (1995). For an n×n image, their algorithm runs in O(n) time on a two-dimensional (2-D) n×n mesh-connected processor array. In this paper, we propose a more efficient parallel algorithm for computing the EDT on a reconfigurable mesh model. For the same problem, our algorithm runs in O(log 2n) time on a 2-D n×n reconfigurable mesh. Since a reconfigurable mesh uses the same amount of VLSI area as a plain mesh of the same size does when implemented in VLSI, our algorithm improves the result in [3] significantly
Keywords :
computational complexity; image processing; parallel algorithms; parallel architectures; Euclidean distance transform; O(n) time; binary images; parallel algorithm; reconfigurable mesh; reconfigurable mesh-connected computers; Computer science; Computer vision; Concurrent computing; Euclidean distance; Image processing; Parallel algorithms; Pattern recognition; Pixel; Robot vision systems; Very large scale integration;
fLanguage :
English
Journal_Title :
Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on
Publisher :
ieee
ISSN :
1083-4419
Type :
jour
DOI :
10.1109/3477.826967
Filename :
826967
Link To Document :
بازگشت