Timed Fast Exact Euclidean Distance (tFEED) maps

Nasser Kehtarnavaz (Editor), Theo E. Schouten, Philip A. Laplante (Editor), Harco Kuppens, Egon van den Broek

    Research output: Contribution to conferencePaperAcademicpeer-review

    6 Citations (Scopus)
    54 Downloads (Pure)


    In image and video analysis, distance maps are frequently used. They provide the (Euclidean) distance (ED) of background pixels to the nearest object pixel. In a naive implementation, each object pixel feeds its (exact) ED to each background pixel; then the minimum of these values denotes the ED to the closest object. Recently, the Fast Exact Euclidean Distance (FEED) transformation was launched, which was up to 2x faster than the fastest algorithms available. In this paper, first additional improvements to the original FEED algorithm are discussed. Next, a timed version of FEED (tFEED) is presented, which generates distance maps for video sequences by merging partial maps. For each object in a video, a partial map can be calculated for different frames, where the partial map for fixed objects is only calculated once. In a newly developed, dynamic test-environment for robot navigation purposes, tFEED proved to be up to 7x faster than using FEED on each frame separately. It is up to 4x faster than the fastest ED algorithm available for video sequences and even 40% faster than generating city-block or chamfer distance maps for frames. Hence, tFEED is the first real time algorithm for generating exact ED maps of video sequences.
    Original languageUndefined
    Number of pages12
    Publication statusPublished - 25 Feb 2005
    EventReal-Time Imaging IX - San Jose, CA, USA
    Duration: 18 Jan 200520 Jan 2005


    ConferenceReal-Time Imaging IX
    Other18-20 January 2005


    • HMI-VRG: Virtual Reality and Graphics
    • tFEED
    • distance maps/transforms
    • robot navigation
    • Video processing
    • IR-79212
    • Exact Euclidean distance
    • FEED
    • EWI-21115

    Cite this