Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fastest available algorithm for distance transform

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.

like image 429
Karl Avatar asked Sep 15 '11 05:09

Karl


People also ask

What is Euclidean distance transform?

The distance transform (DT) is a general operator forming the basis of many methods in computer vision and geometry, with great potential for practical applications. However, all the optimal algorithms for the computation of the exact Euclidean DT (EDT) were proposed only since the 1990s.

What is distance transform used for?

The distance transform provides a metric or measure of the separation of points in the image. The bwdist function calculates the distance between each pixel that is set to off ( 0 ) and the nearest nonzero pixel for binary images.

What is distance metric in digital image processing?

It is often useful in image processing to be able to calculate the distance between two pixels in an image, but this is not as straightforward as it seems.

What is distance mapping?

A distance transform, also known as distance map or distance field, is a derived representation of a digital image.


2 Answers

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.

enter image description here

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.

like image 138
Christian Ammer Avatar answered Nov 14 '22 03:11

Christian Ammer


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

like image 15
Vinnie Falco Avatar answered Nov 14 '22 03:11

Vinnie Falco