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

Anything in here will be replaced on browsers that support the canvas element