CODEWITHSUNDEEP
imageimage-processinggisscikit-image
user3612505
user3612505

Reputation: 35

Minimum cost path / least cost path

I am currently using a library from skimage.graph and the function route_through_array to get the least cost path from one point to another in a cost map. The problem is that i have multiple start points and multiple end points, which leads to thousands of iterations. This i am fixing currently with two for loops. The following code is just an illustration:

img=np.random.rand(400,400)
img=img.astype(dtype=int)
indices=[]
costs=[]
start=[[1,1],[2,2],[3,3],[4,5],[6,17]]
end=[[301,201],[300,300],[305,305],[304,328],[336,317]]
for i in range(len(start)):
    for j in range(len(end)):
        index, weight = route_through_array(img, start[i],end[j])
        indices.append(index)
        costs.append(weight)

From what i understand from the documentation the function accepts many many end points but i do not know how to pass them in a function. Any ideas?

Upvotes: 2

Views: 1680

Answers (1)

JDWarner
JDWarner

Reputation: 86

This should be possible much more efficiently by directly interacting with the skimage.graph.MCP Cython class. The convenience wrapper route_through_array isn't general enough. Assuming I understand your question correctly, what you are looking for is basically the MCP.find_costs() method.

Your code will then look like (neglecting imports)

img = np.random.rand(400,400)
img = img.astype(dtype=int)
starts = [[1,1], [2,2], [3,3], [4,5], [6,17]]
ends = [[301,201], [300,300], [305,305], [304,328], [336,317]]

# Pass full set of start and end points to `MCP.find_costs`
from skimage.graph import MCP
m = MCP(img)
cost_array, tracebacks_array = m.find_costs(starts, ends)

# Transpose `ends` so can be used to index in NumPy
ends_idx = tuple(np.asarray(ends).T.tolist())
costs = cost_array[ends_idx]

# Compute exact minimum cost path to each endpoint
tracebacks = [m.traceback(end) for end in ends]

Note that the raw output cost_array is actually a fully dense array the same shape as img, which has finite values only where you asked for end points. The only possible issue with this approach is if the minimum path from more than one start point converges to the same end point. You will only get the full traceback for the lower of these convergent paths through the code above.

The traceback step still has a loop. This is likely possible to remove by using the tracebacks_array and interacting with `m.offsets, which would also remove the ambiguity noted above. However, if you only want the minimum cost(s) and best path(s), this loop can be omitted - simply find the minimum cost with argmin, and trace that single endpoint (or a few endpoints, if multiple are tied for lowest) back.

Upvotes: 3

Related Questions