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)).
Keywords for this software
References in zbMATH (referenced in 3 articles , 1 standard article )
Showing results 1 to 3 of 3.
- Hirata, Tomio: 3-D Voronoi tessellation algorithms (2005)
- Shen, Hong: Finding the $k$ most vital edges with respect to minimum spanning tree (1999)
- Chen, Ling; Chuang, Henry Y.H.: An efficient algorithm for complete Euclidean distance transform on mesh-connected SIMD (1995)