How to avoid multiplications when generating Euclidean distance maps

Oleg G. Okun

doi:10.1117/12.323261

2 October 1998 How to avoid multiplications when generating Euclidean distance maps

Oleg G. Okun

Proceedings Volume 3454, Vision Geometry VII; (1998) https://doi.org/10.1117/12.323261
Event: SPIE's International Symposium on Optical Science, Engineering, and Instrumentation, 1998, San Diego, CA, United States

Abstract

A new implementation of the Euclidean, ordered propagation distance transform is developed. Unlike traditional approaches, where multiplication operations contribute a significant cost to computation, we suggest to apply the city lock and chessboard distance transform to approximate the Euclidean distances.In fact, the city block transform is just performed, while the chessboard one is simulated based on the iteration number value. Though multiplications are not totally excluded, their amount is greatly reduced because a few pixel values are only corrected at each iteration of the algorithm by using the Euclidean distances as compared to other similar methods, where those distances are determined for each pixel. As a result, we obtain a faster method for generating the Euclidean distance maps, which is still accurate.

Citation Download Citation

Oleg G. Okun "How to avoid multiplications when generating Euclidean distance maps", Proc. SPIE 3454, Vision Geometry VII, (2 October 1998); https://doi.org/10.1117/12.323261

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