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.