时间戳

首页 > 解决方案 > 最小成本路径/最小成本路径

image - 最小成本路径/最小成本路径

问题描述

我目前正在使用来自 skimage.graph 的库和函数 route_through_array 来获取成本图中从一个点到另一个点的最低成本路径。问题是我有多个起点和多个终点，这会导致数千次迭代。我目前正在用两个 for 循环修复这个问题。以下代码只是一个说明：

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)

根据我从文档中了解到的情况，该函数接受许多端点，但我不知道如何在函数中传递它们。有任何想法吗？

标签： imageimage-processinggisscikit-image

解决方案

skimage.graph.MCP通过直接与Cython 类进行交互，这应该可以更有效地实现。便利包装器route_through_array不够通用。假设我正确理解了您的问题，那么您要寻找的基本上就是MCP.find_costs()方法。

您的代码将看起来像（忽略导入）

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]

请注意，原始输出cost_array实际上是一个完全密集的数组，其形状与 相同img，它仅在您要求端点的地方具有有限值。这种方法唯一可能出现的问题是，如果从多个起点开始的最小路径会收敛到同一个终点。您将只能通过上面的代码获得这些收敛路径中较低路径的完整回溯。

回溯步骤仍然有一个循环。这很可能通过使用tracebacks_array和与 `m.offsets 交互来消除，这也将消除上面提到的歧义。但是，如果您只想要最小成本和最佳路径，则可以省略此循环 - 只需使用 argmin 找到最小成本，并跟踪该单个端点（或几个端点，如果多个端点绑定为最低） 背部。

推荐阅读