用python计算位图中两点间的最短路径

Question

我有一个黑白位图图像显示在这里：

图像大小为200158。在

我想选取两个落在白色路径上的点，然后计算出这两个点之间的最短距离。我不知道如何处理这个问题。我想创建一个函数，用两组x，y坐标来调用，它只返回沿着白色像素最短路径的像素数。在

如有任何建议，我们将不胜感激。在

Answer 1

skimage.graph有一个专门针对图像的Dijkstra实现，它只需几行代码就可以解决您的问题：

import numpy as np
import skimage.graph

T,F = True,False
array = np.asarray(
    [[T, F, F, T],
     [T, T, F, T],
     [F, T, T, F],
     [T, T, T, T]])
costs = np.where(array, 1, 1000)
path, cost = skimage.graph.route_through_array(
    costs, start=(0,0), end=(3,3), fully_connected=True)

在这个例子中，path将等于[（0，0），（1，1），（2，2），（3，3）]，这确实是最短的路径。在

Answer 2

如注释中所述，这个问题可以简化为Dijkstra。在

解决方案背后的关键概念是将图像表示为图形，然后使用预先制定的最短路径算法实现。在

首先，观察4x4大小图像的原始表示：

T F F T
T T F T
F T T F
T T T T

其中T是白点，F是黑点。在这种情况下，路径是相邻白点之间的一组移动。在

假设一个图是一组节点{1, 2, ..., 16}，我们可以将每个点(i, j)映射到数字i * 4 + j。在图中，边是相邻点的反映，这意味着如果(i1, j1)和{}在图像中相邻，那么{}和{}在图中是相邻的。在

在这一点上，我们有一个可以计算最短路径的图。在

幸运的是，python为图像加载和最短路径实现提供了简单的实现。以下代码处理路径计算，并将结果可视化：

^{pr2}$

免责声明：

• 我没有图像处理方面的经验，所以我怀疑解决方案的每一步。在
• 该解决方案假设一个非常朴素的邻接谓词。对于这一部分，可能有更好的计算几何方法。在

Answer 3

你好，米尔顿布拉德利

我不是这种算法的专家，但至少我可以给你一些线索来帮助你。 我去年在学校也做过类似的项目。当时，我们正在考虑两种算法：蚁群优化算法和遗传算法。在

蚁群优化

这些算法是基于蚂蚁的行为，当他们试图找到最简单和最短的路线到食物。{a1}更多信息。在

遗传算法

它们更通用，可以解决很多问题。 根据您的情况，您可能对this paper感兴趣。在

很抱歉，我不能为你提供更详细的帮助。我让别人回答，给你你你需要的宝贵建议。祝你的项目好运！在

祝你今天愉快

马蒂斯。在