Distance transform: learn more

[tischi]

@dlegland Do you know a good article where the Chamfer distances are explained?

[dlegland]

Hi @tischi ,

I usually refer to these ones:

• Borgefors, G. (1984). Distance transformation in arbitrary dimensions. Comp. Vis. Graph. Im. Proc., 27, 321–145.
• Borgefors, G. (1986). Distance transformations in digital images. Comp. Vis. Graph. Im. Proc., 34, 344–371.

Somewhat old, but well illustrated!

Some illustrations in MorphoLibJ user manual as well.

[tischi]

Thanks @dlegland would it be OK for you if I copy below text and figure into the training material?

It would end up somewhere on this website: https://neubias.github.io/training-resources/distance_transform/index.html

[dlegland]

yes, this is fine for me!

[tischi]

Thanks!

In fact, I don't get it, @dlegland. In above figure, how would you compute the actual distances? I guess you have to still do something, like divide by something? Is this the "normalize" option?

It would be great to have beneath another panel with the actual distances that are computed using those weights.

[dlegland]

Yes, the "normalize" option consists in dividing all values (well, all values within the foreground) by the weight associated to orthogonal neighbors (the first value in the parens for each sub-panel).

Adding another panel could be nice, I agree, but one should also manage integer vs floating pint outputs (the resulting precision would not be the same...). This may lead to too many figures in the user manual... But maybe as additional material (appendices, or companion slides about chamfer distance transform?).

[tischi]

Thanks!

And how does the algorithm work if you have more than one background pixel? Does it resolve conflicts by taking the minimum distance?

And, is it correct to say that the point of the Chamfer distances is that you can compute them by building up the distances and only have to inspect nearest neighbors O(N)? Whereas for true Euclidian distances you may have to loop for each foreground pixel through the whole image to find the closest background pixel O(N^2)?

[dlegland]

And how does the algorithm work if you have more than one background pixel? Does it resolve conflicts by taking the minimum distance?

Not sure to correctly understand, but the principle is to compute to minimum distance, so yes, in case of multiple possibilities one keep the minimum distance / closest pixel.

And, is it correct to say that the point of the Chamfer distances is that you can compute them by building up the distances and only have to inspect nearest neighbors O(N)? Whereas for true Euclidian distances you may have to loop for each foreground pixel through the whole image to find the closest background pixel O(N^2)?

In principle, yes! But there are recent algorithms that can compute exact Euclidean distance transform in linear (hmm.. need to check...) time! So as of today, the Chamfer-based approach is outperformed by other more recent methods, by I have less feedback on these.