The "dead reckoning" signed distance transform

Consider a binary image containing one or more objects. A signed distance transform assigns to each pixel (voxel, etc.), both inside and outside of any objects, the minimum distance from that pixel to the nearest pixel on the border of an object. By convention, the sign of the assigned distance value indicates whether or not the point is within some object (positive) or outside of all objects (negative). Over the years, many different algorithms have been proposed to calculate the distance transform of an image. These algorithms often trade accuracy for efficiency, exhibit varying degrees of conceptual complexity, and some require parallel processors. One algorithm in particular, the Chamfer distance [J. ACM 15 (1968) 600, Comput. Vis. Graph. Image Process. 34 (1986) 344], has been analyzed for accuracy, is relatively efficient, requires no special computing hardware, and is conceptually straightforward. It is understandably, therefore, quite popular and widely used. We present a straightforward modification to the Chamfer distance transform algorithm that allows it to produce more accurate results without increasing the window size. We call this new algorithm Dead Reckoning as it is loosely based on the concept of continual measurements and course correction that was employed by ocean going vessel navigation in the past. We compare Dead Reckoning with a wide variety of other distance transform algorithms based on the Chamfer distance algorithm for both accuracy and speed, and demonstrate that Dead Reckoning produces more accurate results with comparable efficiency. (C) 2004 Elsevier Inc. All rights reserved.