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.


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:

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



12:40 PM  

Post a Comment

<< Home