TY - GEN

T1 - Computing the nearest neighbor transform exactly with only double precision

AU - Millman, David L.

AU - Love, Steven

AU - Chan, Timothy M.

AU - Snoeyink, Jack

PY - 2012/10/3

Y1 - 2012/10/3

N2 - The nearest neighbor transform of a binary image assigns to each pixel the index of the nearest black pixel - it is the discrete analog of the Voronoi diagram. Implementations that compute the transform use numerical calculations to perform geometric tests, so they may produce erroneous results if the calculations require more arithmetic precision than is available. Liotta, Preparata, and Tamassia, in 1999, suggested designing algorithms that not only minimize time and space resources, but also arithmetic precision. A simple algorithm using double precision can compute the nearest neighbor transform: compare the squared distances of each pixel to all black pixels, but this is inefficient when many pixels are black. We develop and implement efficient algorithms, computing the nearest neighbor transform of an image in linear time with respect to the number of pixels, while still using only double precision.

AB - The nearest neighbor transform of a binary image assigns to each pixel the index of the nearest black pixel - it is the discrete analog of the Voronoi diagram. Implementations that compute the transform use numerical calculations to perform geometric tests, so they may produce erroneous results if the calculations require more arithmetic precision than is available. Liotta, Preparata, and Tamassia, in 1999, suggested designing algorithms that not only minimize time and space resources, but also arithmetic precision. A simple algorithm using double precision can compute the nearest neighbor transform: compare the squared distances of each pixel to all black pixels, but this is inefficient when many pixels are black. We develop and implement efficient algorithms, computing the nearest neighbor transform of an image in linear time with respect to the number of pixels, while still using only double precision.

KW - Arithmetic precision

KW - Computational geometry

KW - Degree-driven analysis of algorithms

KW - Distance transform

KW - Image processing

UR - http://www.scopus.com/inward/record.url?scp=84866776689&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84866776689&partnerID=8YFLogxK

U2 - 10.1109/ISVD.2012.13

DO - 10.1109/ISVD.2012.13

M3 - Conference contribution

AN - SCOPUS:84866776689

SN - 9780769547244

T3 - Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012

SP - 66

EP - 74

BT - Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012

T2 - 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012

Y2 - 27 June 2012 through 29 June 2012

ER -