Adaptive Signed Distance Transform for Curves with Guaranteed Error Bounds

摘要

In this paper we present an adaptive signed distance approximation for curves in two dimensions. Our transform produces an approximation of the signed distance function of a given curve. A signed distance function defines a scaler field that specifies the minimum distance to a curve for every point in the plane, with the sign distinguishing between inside and outside. Distance functions have been used in image processing for some time. Distance functions in three dimensions are also a promising shape representation with interesting applications in geometric design and surface reconstruction. Furthermore, they are well suited to representing dynamic curves and surfaces with changing topology. However, most research relies on distance transforms which sample a distance function without regard to sampling rate requirements. In addition, most transform algorithms for surfaces do not provide error bounds. Our goal is an adaptive distance transform which provides guaranteed error bounds and enables local refinement operations to increase accuracy. The algorithm should not require preset sampling rates or other constraints. We are investigating distance functions in the plane as a precursor to a full three dimensional method. In two dimensions, the error analysis is simplified, and the behavior of the algorithm and data structures can be clearly visualized.