A Parallel Algorithm for Quasi Euclidean Distance Transform

doi:10.11834/jig.200406130

Views : 0 下载量: 228 CSCD: 0

PDF
Export
Share
Collection
Album

A Parallel Algorithm for Quasi Euclidean Distance Transform
Vol. 9, Issue 6, Pages: 693(2004)
Published：2004
DOI： 10.11834/jig.200406130
稿件说明：

移动端阅览

DOI：

A Parallel Algorithm for Quasi Euclidean Distance Transform[J]. Journal of Image and Graphics, 2004, 9(6): 693. DOI： 10.11834/jig.200406130.

摘要

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

Abstract

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.