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.