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. In this paper, 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 nxn 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 nxn image on a g X g processor array, the time complexity is O((n(2)/g) log(n/g)).