Fastest available algorithm for distance transform

Question

I am looking for the fastest available algorithm for distance transform.

According to this site http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm, it describes: "The distance transform can be calculated much more efficiently using clever algorithms in only two passes (e.g. Rosenfeld and Pfaltz 1968)."

Searching around, I found: "Rosenfeld, A and Pfaltz, J L. 1968. Distance Functions on Digital Pictures. Pattern Recognition, 1, 33-61."

But I believe we should have a better and faster algorithm than the one in 1968 already? In fact, I could not find the source from 1968, so any help is highly appreciated.

Porty

Answer 1

There's tons of newer work on computing distance functions.

• Fast marching algorithms that originally came from Tsitsiklis (not Sethian like Wikipedia says). Tons of implementations are available for this.
• Fast sweeping algorithms from Zhao
• O(n) (approximate) fast marching by Yatziv

By the way, you'd really want to use these instead of the work by Rosenfeld, specifically when you want to compute distances in the presence of obstacles.

Careerism

Answer 2

This paper reviews the known exact distance transform algorithms:

"2D Euclidean distance transform algorithms: A comparative survey"
https://rfabbri.github.io/stuff/fabbri-EDT-survey-ACMCSurvFeb2008.pdf

The fastest exact distance transform is from Meijster:

"A General Algorithm for Computing Distance Transforms in Linear Time."
http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

The design of the algorithm is particularly well suited for parallel calculation.

This is implemented in my open source library which tries to emulate Photoshop's "Layer Style:"

https://github.com/vinniefalco/LayerEffects

Rotarian

Answer 3

The OpenCV library uses for its approximate cv::distanceTransform function a algorithm which passes the image from top left to bottom right and back. The algorithm is described in the paper "Distance transformations in digital images" from Gunilla Borgefors (Comput. Vision Graph. Image Process. 34 3, pp 344–371, 1986).

The algorithm calculates the distance through a combination of some basic jumps (horizontal, vertical, diagonal and the knight move). Each jump incurs costs. The following table shows the costs for the different jumps.

+------+------+------+------+------+
| 2.8  |2.1969|   2  |2.1969|  2.8 |
+------+------+------+------+------+
|2.1969|  1.4 |   1  |  1.4 |2.1969|
+------+------+------+------+------+
|   2  |   1  |   0  |   1  |   2  |
+------+------+------+------+------+
|2.1969|  1.4 |   1  |  1.4 |2.1969|
+------+------+------+------+------+
| 2.8  |2.1969|   2  |2.1969|  2.8 |
+------+------+------+------+------+

The distance from one pixel to another is the sum of the costs of the jumps necessary. The following image shows the distance from the 0-cells to each other cell. The arrows are showing the way to some cells. The colored numbers reflect the exact (euclidean) distance.

The algorithm works like this: Following mask

+------+------+------+
|   0  |   1  |   2  |
+------+------+------+
|   1  |  1.4 |2.1969|
+------+------+------+
|   2  |2.1969|  2.8 |
+------+------+------+

is moved from top left of the image to bottom right. During this pass, cells lying inside the boundaries of the mask either keep their value (if it is known and smaller) or they get the value calculated by summing the mask-value and the cell-value (if it is known) from the cell below the mask-0-cell. After that, a second pass from bottom right to top left (with a vertical and horizontal flipped mask) is performed. After the second pass the distances are calculated.

Alves

This method is considerably slower than modern techniques (the most notable being the one from A. Meijster). – Rotarian

Why the value 2.1969 instead of 2.2360 approx. sqrt(3)? – Onym

Answer 4

Felzenszwalb and Huttenlocher present an elegant algorithm that is exact and O(N) in their paper "Distance Transforms of Sampled Functions" available here. They exploit the fact that the square of the Euclidean distance transform is a parabola that can be evaluated independently in each dimension.

Source code is also available.

Alva

I made a version of this algorithm for 3D volumes that handles multiple labels and anisotropy: github.com/seung-lab/euclidean-distance-transform-3d – Obstetrics

Answer 5

I have implemented Meijster's O(N) method cited in Vinnie's answer. "A General Algorithm for Computing Distance Transforms in Linear Time." http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

The nice thing is that it can be parallelized very efficiently, computing each pixel line independently (it's a separable method). Running on 12 CPU cores, the distance field of a 1000^3 volumetric image computes in a few seconds.

The solution of Felzenszwalb and Huttenlocher "Distance Transforms of Sampled Functions" dating from 2012 (cited in bw1024's answer) is based on exactly the same idea. Interestingly, they don't cite the work of Meijster done 12 years earlier.

Eblis

For what it's worth, I found Felzenszwalb and Huttenlocher's paper much easier to read than Mejister et al. It does seem odd that they don't cite that paper, I imagine they didn't know about it? – Obstetrics

I agree, that Felzenszwalb algorithm is just a copy-paste of the Meijster algorithm, which was published more than ten years earlier. – Estival

Felzenszwalb and Huttenlocher algorithm was originally published in 2004 – Alva