python最短路径的可视化,计算python中位图中两点之间的最短路径

如评论中所述,此问题可以减少到

Dijkstra.

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

首先,观察大小为4×4的图像的天真表示：

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)和(i2,j2)在图像中相邻,则i1 * 4 j1和i2 * 4 j2在图中相邻.

此时,我们有一个图表,我们可以在其中计算最短路径.

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

import itertools

from scipy import misc

from scipy.sparse.dok import dok_matrix

from scipy.sparse.csgraph import dijkstra

# Load the image from disk as a numpy ndarray

original_img = misc.imread('path_t_image')

# Create a flat color image for graph building:

img = original_img[:, :, 0] + original_img[:, :, 1] + original_img[:, :, 2]

# Defines a translation from 2 coordinates to a single number

def to_index(y, x):

return y * img.shape[1] + x

# Defines a reversed translation from index to 2 coordinates

def to_coordinates(index):

return index / img.shape[1], index % img.shape[1]

# A sparse adjacency matrix.

# Two pixels are adjacent in the graph if both are painted.

adjacency = dok_matrix((img.shape[0] * img.shape[1],

img.shape[0] * img.shape[1]), dtype=bool)

# The following lines fills the adjacency matrix by

directions = list(itertools.product([0, 1, -1], [0, 1, -1]))

for i in range(1, img.shape[0] - 1):

for j in range(1, img.shape[1] - 1):

if not img[i, j]:

continue

for y_diff, x_diff in directions:

if img[i + y_diff, j + x_diff]:

adjacency[to_index(i, j),

to_index(i + y_diff, j + x_diff)] = True

# We chose two arbitrary points, which we know are connected

source = to_index(14, 47)

target = to_index(151, 122)

# Compute the shortest path between the source and all other points in the image

_, predecessors = dijkstra(adjacency, directed=False, indices=[source],

unweighted=True, return_predecessors=True)

# Constructs the path between source and target

pixel_index = target

pixels_path = []

while pixel_index != source:

pixels_path.append(pixel_index)

pixel_index = predecessors[0, pixel_index]

# The following code is just for debugging and it visualizes the chosen path

import matplotlib.pyplot as plt

for pixel_index in pixels_path:

i, j = to_coordinates(pixel_index)

original_img[i, j, 0] = original_img[i, j, 1] = 0

plt.imshow(original_img)

plt.show()

免责声明：

>我没有图像处理经验,所以我怀疑解决方案的每一步.>该解决方案假设一个非常天真的邻接谓词.对于这部分,计算几何中可能有一些更好的方法.