• Publication
  • PrePrints
  • Abstract - Fast Exact Euclidean Distance (FEED): A New Class of Adaptable Distance Transforms
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Theo E. Schouten, Radboud University, Nijmegen
Egon L. Van den Broek, Utrecht University, Utrecht, University of Twente, Karakter University Center, and Radboud University Medical Center, Nijmegen, The Netherlands
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 \emph{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.
Index Terms:
Feeds,Search problems,Euclidean distance,Transforms,Approximation algorithms,Algorithm design and analysis,distance transform,Feeds,Search problems,Euclidean distance,Transforms,Approximation algorithms,Algorithm design and analysis,benchmark,Geometric algorithms,languages,and systems,Computational Geometry and Object Modeling,Computer Graphics,Region growing,partitioning,Segmentation,Computing Methodologies,Morphological,Image Representation,Image Processing and Computer Vision,distance transformation
Citation:
Theo E. Schouten, Egon L. Van den Broek, "Fast Exact Euclidean Distance (FEED): A New Class of Adaptable Distance Transforms," IEEE Transactions on Pattern Analysis and Machine Intelligence, 02 July 2014. IEEE computer Society Digital Library. IEEE Computer Society, <http://doi.ieeecomputersociety.org/10.1109/TPAMI.2014.25>
Usage of this product signifies your acceptance of the Terms of Use.