swMATH ID: 3445
Software Authors: Chen, Ling; Chuang, Henry Y.H.
Description: An efficient algorithm for complete Euclidean distance transform on mesh-connected SIMD The Euclidean distance transform (EDT) converts a binary image into one where each pixel has a value equal to its Euclidean distance to the nearest foreground pixel. It has important uses in image analysis, computer vision, and robotics where high speed computation is essential. A sequential algorithm which does not require global operations is first presented. We then apply a sequence of algorithm transformations to convert it into a parallel algorithm for mesh-connected SIMD computers. For an n× n image on an equal-sized processor array, the time complexity is O(n). An algorithm for computing large EDT problems on smaller processor arrays is also given. For an n× n image on a g× g processor array, the time complexity is O((n 2 /g) log(n/g)).
Homepage: http://www.sciencedirect.com/science/article/pii/016781919400103H
Keywords: Euclidean distance transform; Image analysis; Mesh-connected SIMD computer; Complexity analysis
Related Software:
Referenced in: 3 Publications

Referencing Publications by Year