完全欧几里德距离变换的最优算法

欧几里德距离变换（ＥＤＴ）对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离，应用于图象分析，计算机视觉，在本文之前，该问题的最好复杂度为Ｏ（ｎ＾２ｌｏｇｎ）。本文提出了一个复杂度为Ｏ（ｎ＾２）的算法，使复杂度达到最优，该算法可以并行化，在有ｒ个处理单元的ＥＲＥＷＰＲＡＭ计算模型上，若ｒｌｏｇｒ≤２２／６ｎ，则时间复杂度为Ｏ（ｎ／ｒ）否则为Ｏ（ｎｌｏｇｒ）。

OPTIMAL ALGORITHM FOR COMPLETE EUCLIDEAN DISTANCE TRANSFORM

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 applications in image analysis and computer vision. Before this paper, the best complexity for this problem is O(n2logn). This paper, presents an algorithm with complexity O(n2) which is optimal. The algorithm can also be parallelized. In an EREW PRAM model with r processors, time complexity is O (n2/r) if r log , or O(n log r) otherwise.