Search code examples
pythonnumpyscipyscikit-imagendimage

Intensity-weighted minimal path between 2 points in grayscale image

I want to determine minimum path between two specific points in an image, i.e. the path for which sum of distances between adjacent pixels weighted by pixel intensity (greyscale) will be minimized. For instance, this picture shows the input image

original image

and this is the (hand-drawn) minimal path in red, from UL to LR corner (black boundaries serve as zero-weight padding):

example minimum path

I found that matlab has the graydist function just for this; is there something similar in ndimage/scikit-image/whatever? I found scipy.ndimage.morphology.distance_transform_edt but I am not sure if and how to use it for this purpose. It is OK if the algorithm returns only one of non-unique minima.

I am not interested in implementation hints, it is a fairly straightforward task algorithmically (at least the naive implementation using e.g. dynamic programming), I am looking for (combination of) already coded routines to accomplish this.

Solution

  • This type of dynamic programming is available in scikit-image as route_through_array and shortest_path: http://scikit-image.org/docs/dev/api/skimage.graph.html