Distance Transforms: Academics Versus Industry

Egon      L. van den Broek; Theo      E. Schouten

Abstract

In image and video analysis, distance transformations (DT) are frequently used. They provide a distance image (DI) of background pixels to the nearest object pixel. DT touches upon the core of many applications; consequently, not only science but also industry has conducted a significant body of work in this field. However, in a vast majority of the cases this has not been published in major scientific outlets but has been filed as a patent application. This article provides a brief introduction into DT, including a specification of a few of the most prominent algorithms in the field. Next, a few interesting algorithms from the last decade are discussed. A benchmark including eight DT algorithms (i.e., city block, Danielssons algorithm, chamfer 3-4, hexadecagonal region growing, a recent claimed true Euclidean DT, and three exact Euclidean DT) has been executed, which illustrates the intriguing complexity of DT in terms of precision and computational complexity. Subsequently, a selection of key patent applications are discussed that have emerged in this field, including their scientific merit and areas of application. Finally, this articles findings are summarized and discussed, with an emphasis on both the common ground of scientific articles and patent applications as well as the added value they can have to each other.

Keywords: Distance transforms (DT), distance image, euclidean distance, computational geometry, patent, chamfer, FEED, octagonal distance, tumour cells, image segmentation, collision prevention