Constant-Time Algorithm for the Euclidean Distance Transform on Reconfigurable Meshes

✍ Scribed by Amitava Datta; Subbiah Soundaralakshmi

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 288 KB
• Volume: 61
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2000.1684

✦ Synopsis

The Euclidean distance transform (EDT) is an operation to convert a binary image consisting of black and white pixels to a representation where each pixel has the Euclidean distance of the nearest black pixel. The EDT has many applications in computer vision and image processing. In this paper, we present a constant-time algorithm for computing the EDT of an N_N image on a reconfigurable mesh. Our algorithm has two variants. (i) If the image is initially given in an N_N mesh, one pixel per processor, our algorithm requires an N_N_N mesh for computing the EDT. (ii) If the image is given in an N_N 2 mesh, each row of the image in the first row of a separate N_N mesh, we can compute the EDT in the same N_N 2 mesh. The AT 2 bounds for these two variants are O(N 4 ) and O(N 3 ) respectively. The best previously known algorithm (Y. Pan and K. Li, Inform. Sci. 120 (1999), 209 221) for this problem assumes input similar to the second variant of our algorithm and runs in constant-time on an N 2 _N 2 reconfigurable mesh with an AT 2 bound of O(N 4 ). Hence both variants of our algorithm improve upon the processor complexity of the algorithm in Pan and Li (1999) by a factor of N and the second variant improves upon the AT 2 complexity by a factor of N.