bwdistgeodesic with Euclidean distance as metric

Hello,

bwdist allows one to use Euclidean distance as metric while for bwdistgeodesic that is not an option. Is there a specific reason for this behavior? Is there a standard workaround?

Any advice welcome! Thanks!

[rtransform]

Looking for the exact same thing. Did you find a solution?

Kind regards

[BiologicalPhysicist]

I eventually used a Python implementation of the fast marching method:

https://en.wikipedia.org/wiki/Fast_marching_method

https://github.com/scikit-fmm/scikit-fmm

Answer 1

[Adam Danz]

According to Steve Eddins's image processing blog post on this topic, the bwdistgeodesic function (since r2011b) computes the shortest path that avoids objects. One of the distance metrics options is 'quasi-euclidean' which measures the total Euclidean distance along a set of horizontal, vertical, and diagonal line segments that cicumvent the objects. A true Euclidean metric would pass through the object if it were between the two endpoints. For a visual depiction of this and other distance metrics, see this page.

A nice description of geodesic distance transform and its relationship to Euclidean distance is described in this Jupyter Notebook blog post (not Matlab code).

Lastly, a really nice depiction of the difference between the Euclidean distance and the Geodesic distance is shown in the reference below.

Garrido, S., Moreno, L., Abderrahim, M., & Martin, F. (2006, October). Path planning for mobile robot navigation using voronoi diagram and fast marching. In 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems

[rtransform]

Thank you very much, especially for the literature.

bwdistgeodesic with the quasi-euclidean option is close to, but not exactly what I am looking for. I was thinking of a way which uses the euclidean distance whenever possible (e.g. larger patch of pixels which can be traversed on), but at the same time is able to cope with obstacles:

e.g. I have a low-res "map" with large pixels (in the simplest case just binary, 1: can be traversed on).

let's assume pixels resemble 1 mile by 1 mile. start and endpoints are in the center of the pixels.

in the "map" below, if I start in pixel s and travel to pixel f, the quasi-euclidean distance whould be 1+sqrt(2) ~ 2.414. But since all the areas in this scenario are safe to walk on, I could walk the euclidean distance which is only sqrt(5) ~ 2.236.

s 1 1

1 1 f

[Adam Danz]

Would bwdist(BW,method), using the Euclinean method, be suitable for your needs?

If not, what if you computed the distance manually by using the distance formula along with the indices of s and f?

[rtransform]

Unfortunatelly not, I think.

The distance formula would not work for restricted paths, e.g. a "peninsula" :

s 1 1 0 0

1 1 1 1 0

0 0 0 1 0

0 0 0 1 f

Neither will bwdist, I think, as I cannot apply a seed region to the image. bwdist returns distances for all zero-pixels in the image to the next non-zero pixel. But I would like to enter a binary image on which i would then like to get the distances along the true values starting at a certain seed-region.

[Adam Danz]

But in those cases, the peninsula for example, what would the euclidean method look like? I think that's where the quasi-euclidean method comes in.

[rtransform]

My main concern about using quasi-euclidean distances is that for a situation like this

1 1 1 1 1

1 1 1 1 1

1 1 s 1 1

1 1 1 1 1

1 1 1 1 1

Bwdist(geodesic) with quasi-euclidean returns significantly larger distances for some pixels than the euclidean bwdist.

What I am really looling for would be a fast and general method to get the minimal travel distances from one point in 3D space to all other points along/within an arbitrary path/volume.

[BiologicalPhysicist]

I think the difference between euclidean and semi-euclidean is not whether you pass through the object or not, but how lengths are measured locally. You want to find the shortest path from A to B. That path may be different, depending on the metric.

[Adam Danz]

bwdistgeodesic is used to find shortest paths subject to constraints.

See https://blogs.mathworks.com/steve/2011/12/13/exploring-shortest-paths-part-5/

[BiologicalPhysicist]

I agree.

The problem I had was that using the quasi-euclidean distance results in significant, unintended lattice artefacts (if you use the lattice to approximate a continuum system as I did).