New algorithms for euclidean distance transformation of an n-dimensional digitized picture with applications

摘要

In this paper, we propose a new method to obtain the Euclidean distance transformation and the Voronoi diagram based on the exact Euclidean metric for an n-dimensional picture. We present four algorithms to perform the transformation which are constructed by the serial composition of n-dimensional filters. When performed by a general purpose computer, they are faster than the method by H. Yamada for a two-dimensional picture. Those algorithms require only one n-dimensional array for storing input/output pictures and a single one-dimensional array for a work area, if an input picture needs not be preserved.