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

摘要

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