title: Euclidean distance transform for binary images on reconfigurable mesh-connected computers.
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 nxn image, their algorithm runs in O(n) time on a two-dimensional (2-D) nxn 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(2)n) time on a 2-D nxn 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.
authors.affiliation: Dept. of Comput. Sci., Dayton Univ., OH.
authors.forename: Y
authors.initials: Y
authors.lastname: Pan
authors.forename: M
authors.initials: M
authors.lastname: Hamdi
authors.forename: K
authors.initials: K
authors.lastname: Li