近似欧氏距离变换的一种并行算法

A Parallel Algorithm for Quasi Euclidean Distance Transform

提出了一种基于超大规模集成电路 (VL SI)硬件结构的新型距离变换并行处理算法。距离变换是一种基于二值图像的全局操作 ,在骨架抽取、形状匹配、目标重建、机器人避障等图像分析与模式识别算法中有着广泛的应用。欧氏距离是精确的 L2 范数距离 ,但是由于欧氏距离的非线性 ,不利于各种并行算法和加速算法的设计与实现 ,因此在应用中各种变形的加权距离作为欧氏距离的近似得到了实际推广。本文算法是有别于传统近似欧氏距离的并行计算方法 ,可应用于传统 IC硬件或数字信号处理芯片 (DSP)。理论分析和实验结果表明 ,该方法具有算法简单、快速、误差小等特点 ,可以更好地近似欧氏距离 ,并同时得到图像的 Voronoi图 ,是一种实际可行的升级算法。

A novel parallel algorithm for distance transformation based on VLSI hardware structure is proposed in this paper. Distance transformation is a global operation on binary image which is widely used in skeletonization, shape matching, object reconstructing, obstacles elusion, etc. Because of the nonlinearity of euclidean distance, it is not convenient to design parallel and fast algorithm for it. Many deformed weighed distance transformation is adopted in practice. In this paper, we propose a parallel algorithm deferent from the traditional Quasi-Euclidean distance transformation. It can be used in traditional IC hardware and DSP. Theoretical analysis and experiments show that the algorithm is simple, fast and the results can approximate the Euclidean distance more exactly. The Voronoi diagram can be got synchronously. Simulation results on PC are also listed in this paper.