基于围线扫描的快速完全欧氏距离变换算法

A Fast Algorithm for Complete Euclidean Distance Transformation Based on Contour Scanning

欧几里德距离变换(EDT)是为由黑白像素构成的二值图像中所有像素找到距离其最近的黑色像素,并计算它们之间的欧几里德距离,目前广泛地应用于图像分析和计算机视觉等领域。本文采用基于围线扫描的思想,提出了一个在二值图像中进行完全欧氏距离变换的算法。算法首先将二值图像中的像素进行分类,对那些本身既不是特征像素且其4-邻域内也没有特征像素的点作上标记,然后对这些标记的像素自内向外进行围线扫描,搜索与它最近的黑点并计算它们的欧氏距离。算法能够计算精确的欧氏距离。同时对算法的时间复杂度进行了简单的分析,并给出了程序实现中得到的一些实验数据,结果表明该算法运算速度快,时空需求在当前的硬件环境下令人满意,是一种有效的和有着巨大实际应用价值的距离变换算法。

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. It has important applications in image analysis and computer vision. This paper gives an algorithm for complete Euclidean distance transformation on the binary image on the basis of the contour scanning. In the suggested algorithm all the pixels are classified and the ones which neither are characteristic pixel nor have characteristic pixels in 4-neighbors are marked. For the marked pixel, scan its contour form inner to outer, find its nearest characteristic pixel and compute their Euclidean distance. The exact distances are obtained. The requirement of time are analyzed briefly, some testing data produced in running the implementation are illustrated. The result shows that the algorithm runs fast, the requirements of space and time are satisfying in the present hardware condition, and it is an effective and enormous applied distance transformation algorithm.