Monday, April 13, 2009



I needed code for the 2D and 3D distance transform (for my dendrogen toolkit), and the only thing I could find used ITK -- lovely toolkit, but that's a big dependency I didn't want to drag in. I looked up the algorithm, and it turns out it's dead simple.

Curious thing about the distance transform is that approximate algorithms have been around for a while, but so far as I can tell, an efficient (linear in the number of pixels) and exact algorithm was only devised in 2004, by Messrs. Felzenszwalb & Huttenlocher. Their solution is also beautifully simple. The paper contains pseudocode which can be directly translated into C.

The above pic is a slice through a 3d distance transform of a set of points, and the corresponding 3d voronoi diagram.

I added the ability to optionally generate voronoi regions. The code mostly tests with points, but it will work with arbitrary regions as well. It's a VC Express project, but the code is all portable. The test code uses OpenCV just to display results, but the distance transform code itself is in a single header and has no dependencies beyond the C++ standard library.

If you look at the code, you'll notice an OpenMP directive, which sped things up by about 25% on my slow-but-dual-core laptop. The tiny amount I know about OpenMP is from a Doctor Dobb's article I read years ago, so I don't know if I'm using it correctly, except to say that the results appear correct, and it did indeed make it go faster.

2 Comments:

Anonymous Anonymous said...

Hi, im really interested in your implementation. any chance that you update the link to the source? cheers!

12:19 PM  
Blogger The Method Artist said...

Hi there,

I managed to find an old version which you can download here:

http://hesdiya.org/wp-content/uploads/2011/07/dist_trans.cpp

It actually quite easy to write your own code from the pseudo code in the paper.

Cheers,

Kevin

12:40 PM  

Post a Comment

<< Home