Distance transforms: Academics versus industry

Egon van den Broek, Th.E. Schouten

    Research output: Contribution to journalArticleAcademicpeer-review

    3 Citations (Scopus)
    184 Downloads (Pure)


    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, Danielsson’s 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 article’s 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.
    Original languageUndefined
    Pages (from-to)1-15
    Number of pages15
    JournalRecent patents on computer science
    Issue number1
    Publication statusPublished - Feb 2011


    • HMI-VRG: Virtual Reality and Graphics
    • patent
    • chamfer
    • computational geometry
    • distance image
    • IR-76450
    • HMI-CI: Computational Intelligence
    • Euclidean distance
    • Distance transforms (DT)
    • FEED
    • METIS-278700
    • EWI-19534

    Cite this