Shape representation using a generalized potential field model

Abstract

This paper is concerned with efficient derivation of the medial axis transform of a two-dimensional polygonal region. Instead of using the shortest distance to the region border, a potential field model is used for computational efficiency. The region border is assumed to be charged and the valleys of the resulting potential field are used to estimate the axes for the medial axis transform. The potential valleys are found by following force field, thus, avoiding two-dimensional search. The potential field is computed in closed form using the equations of the border segments. The simple Newtonian potential is shown to be inadequate for this purpose. A higher order potential is defined which decays faster with distance than as inverse of distance. It is shown that as the potential order becomes arbitrarily large, the axes approach those computed using the shortest distance to the border. Algorithms are given for the computation of axes, which can run in linear parallel time for part of the axes having initial guesses. Experimental results are presented for a number of examples.