Computing distance transformations in convex and non-convex domains

摘要

It is shown that the well known two-pass sequential local transformation algorithm for computing a distance transformation in rectangular domains may fail in some convex integer domains, but that a four-pass algorithm is sufficient in all two-dimensional convex domains. For non-convex domains the number of passes necessary is shown to be generally greater. Two propagation algorithms for computing the distance transformation are described and shown theoretically and experimentally to be computationally more efficient than the sequential local transformation algorithm in non-convex domains of complex shape. The relationship of the distance transformation in non-convex domains to some more general transformations is explored.