Shih Frank Y, Wu Yi-Ta
Computer Vision Laboratory, College of Computing Sciences, New Jersey Institute of Technology, Newark, NJ 07102, USA.
IEEE Trans Image Process. 2004 Aug;13(8):1078-91. doi: 10.1109/tip.2004.826098.
Euclidean distance transformation (EDT) is used to convert a digital binary image consisting of object (foreground) and nonobject (background) pixels into another image where each pixel has a value of the minimum Euclidean distance from nonobject pixels. In this paper, the improved iterative erosion algorithm is proposed to avoid the redundant calculations in the iterative erosion algorithm. Furthermore, to avoid the iterative operations, the two-scan-based algorithm by a deriving approach is developed for achieving EDT correctly and efficiently in a constant time. Besides, we discover when obstacles appear in the image, many algorithms cannot achieve the correct EDT except our two-scan-based algorithm. Moreover, the two-scan-based algorithm does not require the additional cost of preprocessing or relative-coordinates recording.
欧几里得距离变换（EDT）用于将由对象（前景）像素和非对象（背景）像素组成的数字二值图像转换为另一幅图像，其中每个像素的值是到非对象像素的最小欧几里得距离。本文提出了改进的迭代腐蚀算法，以避免迭代腐蚀算法中的冗余计算。此外，为了避免迭代操作，通过一种推导方法开发了基于两次扫描的算法，以便在固定时间内正确且高效地实现EDT。此外，我们发现当图像中出现障碍物时，除了我们的基于两次扫描的算法外，许多算法都无法实现正确的EDT。而且，基于两次扫描的算法不需要额外的预处理成本或记录相对坐标。
