How far is it from everywhere to somewhere?
Channel: Kevin's Mathematical Musings
Date: 2021-08-21

Computing the Euclidean Distance Transform on a regular grid.

A fundamental operation in image processing, used as part of separating objects, finding best matches, finding sizes of objects, and so on.

The algorithm presented here is described in:

J. Wang and Ying Tan, Efficient Euclidean distance transform using perpendicular bisector segmentation. CVPR 2011, pp. 1625-1632.
http://www.cvpapers.com/papers/egpaper_final.pdf

Two good libraries for solving general Voronol and Delaunay problems are
CGAL  https://doc.cgal.org/latest/Manual/packages.html#PartVoronoiDiagrams
and qhull http://www.qhull.org/

For the Euclidean distance transformation on a grid, there are widely used implementations in the image processing application ImageJ
(https://imagej.nih.gov/ij/docs/guide/146-29.html#toc-Subsection-29.8 - search for 'Distance Map') and the computer vision library OpenCV https://docs.opencv.org/4.5.3/d2/dbd/tutorial_distance_transform.html

The algorithm presented here appears to be newer than those used in the libraries cited above.

Chapters:
00:00 Introduction
01:53 Voronoi tessellations and Delaunay triangulations
05:06 What happens on a grid row?
07:01 Data structure for Voronoi on a grid
07:55 Algorithm for grid rows
09:26 Performance
10:03 Exact arithmetic
13:01 Putting it all together
14:13 Next steps