Computing the nearest neighbor transform exactly with only double precision

David L. Millman; Steven Love; Timothy M. Chan; Jack Snoeyink

doi:10.1109/ISVD.2012.13

Computing the nearest neighbor transform exactly with only double precision

David L. Millman, Steven Love, Timothy M. Chan, Jack Snoeyink

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012
Pages	66-74
Number of pages	9
DOIs	https://doi.org/10.1109/ISVD.2012.13
State	Published - Oct 3 2012
Externally published	Yes
Event	2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012 - Piscataway, NJ, United States Duration: Jun 27 2012 → Jun 29 2012

Publication series

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

Other

Other	2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012
Country/Territory	United States
City	Piscataway, NJ
Period	6/27/12 → 6/29/12

Keywords

Arithmetic precision
Computational geometry
Degree-driven analysis of algorithms
Distance transform
Image processing

ASJC Scopus subject areas

Geometry and Topology

Online availability

10.1109/ISVD.2012.13

Library availability

Discover UIUC Full Text

Cite this

Millman, D. L., Love, S., Chan, T. M., & Snoeyink, J. (2012). Computing the nearest neighbor transform exactly with only double precision. In Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012 (pp. 66-74). Article 6257658 (Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012). https://doi.org/10.1109/ISVD.2012.13

Computing the nearest neighbor transform exactly with only double precision. / Millman, David L.; Love, Steven; Chan, Timothy M. et al.
Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012. 2012. p. 66-74 6257658 (Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Millman, DL, Love, S, Chan, TM & Snoeyink, J 2012, Computing the nearest neighbor transform exactly with only double precision. in Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012., 6257658, Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012, pp. 66-74, 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012, Piscataway, NJ, United States, 6/27/12. https://doi.org/10.1109/ISVD.2012.13

Millman DL, Love S, Chan TM, Snoeyink J. Computing the nearest neighbor transform exactly with only double precision. In Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012. 2012. p. 66-74. 6257658. (Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012). doi: 10.1109/ISVD.2012.13

Millman, David L. ; Love, Steven ; Chan, Timothy M. et al. / Computing the nearest neighbor transform exactly with only double precision. Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012. 2012. pp. 66-74 (Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012).

@inproceedings{02573be3713d4ea680d08488a098ef77,

title = "Computing the nearest neighbor transform exactly with only double precision",

abstract = "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.",

keywords = "Arithmetic precision, Computational geometry, Degree-driven analysis of algorithms, Distance transform, Image processing",

author = "Millman, {David L.} and Steven Love and Chan, {Timothy M.} and Jack Snoeyink",

year = "2012",

month = oct,

day = "3",

doi = "10.1109/ISVD.2012.13",

language = "English (US)",

isbn = "9780769547244",

series = "Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012",

pages = "66--74",

booktitle = "Proceedings of the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012",

note = "2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012 ; Conference date: 27-06-2012 Through 29-06-2012",

}

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 -

Computing the nearest neighbor transform exactly with only double precision

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this