A Linear Time Algorithm for Computing the Euclidean Distance Transform in Arbitrary Dimensions

摘要

A sequential algorithm is presented for computing the Euclidean distance transform of a -dimensional binary image in time linear in the total number of voxels. The algorithm may be of practical value since it is relatively simple and easy to implement and it is relatively fast (not only does it run in linear time but the time constant is small).