Distance Transform

This post is about a short comparison of 3 similar distance transform algorithms.

CDT – Chamfer Distance Transform
DRA – Dead Reckoning Algorithm
DDT – developved by myself
All 3 have quite a lot in common and are based on the Chamfer Distance Transform. The CDT is a 2-pass algorithm, propagating distances and the corresponding nearest-neighbors (NN) in a small window (3×3) across the image. The first pass starts at the upper-left corner, the second pass in the opposite corner. Thats all.

0) initialization:
find all foreground pixels and set their distance to 0.

1) pass 1:
move window from left -> right, top -> bottom
at each pixel, check neighbors 0, 1, 2, 3 and save the smallest distance and NN
1 2 3
0 x .
. . .

2) pass 2:
move window from right -> left, bottom -> top
at each pixel, check neighbors 4, 5, 6, 7 and save the smallest distance and NN
. . .
. x 4
7 6 5

3) … finished …

… what differs among the 3 versions is, how the smallest distance is update/calculated.

Chamfer Distance Transform (CDT)

… looks-up the direct neighbors distance, and adds the pixel-distance (either 1=orthogonally or sqrt(2)=diagonally, depending on the neighbor) to it. The smallets of this 4 new distances is then stored. In the 2nd pass (backwards) the currently saved distance is also taken into account. Also, the actuall nearest neighbor is stored too.

Dead Reckong Algorithm (DRA)

… looks-up the 4 direct neighbors distances, and same as in CDT, adds the pixel-distance (1, or sqrt(2) ). If that distance is smaller then the one currently saved at X, then the euclidean distance from X to the direct neighbor’ NN is calculated and stored. The new found NN is also stored.

This is definitely a great improvement to CDT because the distance are not summed up anymore, but updated each time. Although there still can be introduced a small error, which happens during comparing the distances (before actually computing them). Another drawback of this comparison is, that the distance cant be squared, which would allow to avoid using floating-point precission and the sqrt() call. Besides that, the results in generall look as they are supposed to.

(DDT) My own algorithm

… (i couldn’t think of a name, so its just DiewaldDT, or whatever) was inspired by DRA. Mainly i was looking for a way, to only used squared distances and avoid introducing errors as much as possible. Which means, i need to compute, before comparing is done, the distances to the 4 direct-neighbors’ NN, and then compare the currents’ NN-distance to these. Not as in DRA, comparing the currents’ NN-distance to the neighbors-NN-distance (including the estimated correction of the pixel-distance).

Since it’s now possible to only work with squared distances, there is no more call for square-root, and the squared-distances can be saved as Integral-values.

Performance

While, in my tests, DRA was about 20-30% slower than CDT, my version (DDT) runs at almost the same speed as CDT, with, at least in in theory, better (but not really visible, see images) results. This timings were taken for computing the distance field, … not including the render-pass.

EDIT: for DRA and DDT it is useful to create a lookup-tabe for the distances. Since there is only a limited possible number of distances, this distances can be pre-computed once and saved into a matrix (w,h). For DRA this is most advantageous, because squareroot-calls can be completely avoided during the distance transform, which makes it almost equally fast as CDT.

Problems

Besides the above result look correct for DRA and DDT, there is still another source for errors. During comparison we only can decide for one NN to keep, which gets further propagated then to the other pixels. But there are cases, where one or more neighbors are at equal distance. While for the current pixel this it is fine to just keep one of them, for later pixels one of the other NN have been might be closer. The resulting artifacts are quite obvious in the following images. CDT seems to be a better choice here.

diewald_CDT_error_compare
diewald_DRA_error_compare
diewald_DDT_error_compare

some other test-cases

diewald_circle_CDT
diewald_circle_DRA
diewald_circle_DDT

diewald_ellipse_CDT
diewald_ellipse_DRA
diewald_ellipse_DDT

diewald_rect_CDT
diewald_rect_DRA
diewald_rect_DDT

diewald_rect_rot_CDT
diewald_rect_rot_DRA
diewald_rect_rot_DDT

diewald_grid_CDT
diewald_grid_DRA
diewald_grid_DDT

Demos (Java Applets)

comparing/debugging http://www.openprocessing.org/sketch/107671
random samples http://www.openprocessing.org/sketch/107674
lena voronoi http://www.openprocessing.org/sketch/107673

Results

Distance field: randomly places samples, text and user-drawing, varying distance-factors and smooth color falloff accross the screen.

diewald_1377882255140_distance_transform_drawing
diewald_1377882264765_distance_transform_drawing
diewald_1377882268187_distance_transform_drawing

Lena Voronoi: centroids are a set of choosen random samples, based on some SAT-averaging.

diewald_1377882680687_distance_transform_lena
diewald_1377882676937_distance_transform_lena
diewald_1377882663734_distance_transform_lena

diewald_1377882658890_distance_transform_lena
diewald_1377882619984_distance_transform_lena
diewald_1377882616000_distance_transform_lena