Fast Euclidean distance transformations by propagation using multiple neighbourhoods

We propose a new exact Euclidean distance transformation (DT) by propagation, using bucket sorting. A fast but approximate DT is first computed using a coarse neighborhood. A sequence of larger neighborhoods is then used to gradually improve this approximation. Computations are kept short by restricting the use of these large neighborhoods to the tile borders in the Voronoi diagram of the image. We assess the computational cost of this new algorithm and show that it is both smaller and less image-dependent than all other DTs recently proposed. Contrary to all other propagation DTs, it appears to remain o(n2) even in the worst-case scenario.


Published in:
Computer Vision and Image Understanding, 76, 2, 163
Year:
1999
Keywords:
Laboratories:




 Record created 2006-06-14, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)