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.
… 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.
… 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.
… (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.
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.
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.
some other test-cases
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
Distance field: randomly places samples, text and user-drawing, varying distance-factors and smooth color falloff accross the screen.
Lena Voronoi: centroids are a set of choosen random samples, based on some SAT-averaging.