Fast Exact Euclidean Distance (FEED): A new class of adaptable distance transforms

Theo E. Schouten, Egon van den Broek

    Research output: Contribution to journalArticleAcademicpeer-review

    20 Citations (Scopus)
    59 Downloads (Pure)


    A new unique class of foldable distance transforms of digital images (DT) is introduced, baptized: Fast Exact Euclidean Distance (FEED) transforms. FEED class algorithms calculate the DT starting directly from the definition or rather its inverse. The principle of FEED class algorithms is introduced, followed by strategies for their efficient implementation. It is shown that FEED class algorithms unite properties of ordered propagation, raster scanning, and independent scanning DT. Moreover, FEED class algorithms shown to have a unique property: they can be tailored to the images under investigation. Benchmarks are conducted on both the Fabbri et al. data set and on a newly developed data set. Three baseline, three approximate, and three state-of-the-art DT algorithms were included, in addition to two implementations of FEED class algorithms. It illustrates that FEED class algorithms i) provide truly exact Euclidean DT; ii) do no suffer from disconnected Voronoi tiles, which is a unique feature for non-parallel but fast DT; iii) outperform any other approximate and exact Euclidean DT with its time complexity O(N), even after their optimization; and iv) are unequaled in that they can be adapted to the characteristics of the image class at hand. The source code of all algorithms included as well as the data sets used for both benchmarks are provided as supplementary material to this article.
    Original languageUndefined
    Pages (from-to)2159-2172
    Number of pages14
    JournalIEEE transactions on pattern analysis and machine intelligence
    Issue number11
    Publication statusPublished - 2014


    • HMI-CI: Computational Intelligence
    • HMI-VRG: Virtual Reality and Graphics
    • HMI-IE: Information Engineering
    • distance transformation
    • EWI-24444
    • IR-89583
    • METIS-304004
    • Adaptive
    • Computational Complexity
    • Distance transform
    • Fast Exact Euclidean Distance (FEED)
    • Voronoi
    • Benchmark

    Cite this