Timed fast exact Euclidean distance (tFEED) maps

Theo E. Schouten; Harco C. Kuppens; Egon L. van den Broek

doi:10.1117/12.587784

25 February 2005 Timed fast exact Euclidean distance (tFEED) maps

Theo E. Schouten, Harco C. Kuppens, Egon L. van den Broek

Proceedings Volume 5671, Real-Time Imaging IX; (2005) https://doi.org/10.1117/12.587784
Event: Electronic Imaging 2005, 2005, San Jose, California, United States

Abstract

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.

Citation Download Citation

Theo E. Schouten, Harco C. Kuppens, and Egon L. van den Broek "Timed fast exact Euclidean distance (tFEED) maps", Proc. SPIE 5671, Real-Time Imaging IX, (25 February 2005); https://doi.org/10.1117/12.587784

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available