Chamfer distance on gpu?

Hi all,

have you already heard about a chamfer distance implemented on gpu (cuda or other)?

(chamfer distance = discrete approximation of eulerian distance)

Classical, cpu algorithms are not easy to translate to CUDA (they are based on the execution order).
I found a few descriptions of parallel chamfer mask algos but they seem all based on an execution order anyway…

At least if someone has information about an algo that could be translated in CUDA.

Thanks.

– pium, frustrated to have a big, complex chain of image processings with only one algo executed on cpu that takes more than 50% of the execution time…

EDIT: I just found that :wacko: http://forums.nvidia.com/index.php?showtopic=101461

I can’t see better than a O(n2) regarding the #pixels/voxels, but I can hardly see how it will be faster than the 0(n) algo on cpu.

The only optimization I see is to store independently the border voxels (the ones == 0) and to compare distance only with them…

I found something relatively similar based on 2 buffers, maybe it is a good approach when enough memory is available.
http://wwwcg.in.tum.de/research/research/publications/2009/gpu-based-real-time-discrete-euclidean-distance-transforms-with-precise-error-bounds.html