在Python中计算位图中两点之间的最短路径 [英] Calculating the shortest path between two points in a bitmap in python
问题描述
我有一个黑白位图图像,显示在这里:
I have a black and white bitmap image shown here:
图片大小为200,158.
The image size is 200,158.
我想选择落在白色路径上的两个点,并计算仅跟随白色像素的两点之间的最短距离.我不确定如何解决这个问题.我想创建一个使用两组x,y坐标调用的函数,它只返回沿着白色像素的最短路径的像素数.
I want to pick two points that fall on the white path and calculate the shortest distance between those two points following only the white pixels. I am not sure how to approach this problem. I want to create a function that I call with 2 sets of x,y coordinates and it returns the number of pixels following the shortest route along the white pixels only.
任何指针将不胜感激.
推荐答案
如评论中所述,此问题可以减少为 Dijkstra .
As stated in the comments, this problem can be reduced to Dijkstra.
解决方案背后的关键概念是将图像表示为图形,然后使用最短路径算法的预制实现.
The key concept behind the solution is to represent the image as a graph and then use a pre-made implementation of the shortest-path algorithm.
首先,观察4x4大小的图像的幼稚表现形式:
Firstly, observe a naive representation of an image of size 4x4:
T F F T
T T F T
F T T F
T T T T
其中T
是一个白色的点,而F
是一个黑色的点.在这种情况下,路径是相邻白点之间的一组移动.
Where T
is a white dot and F
is a black one. In this case, a path is a set of moves between adjacent white points.
假设一个图是一组节点{1, 2, ..., 16}
,我们可以将每个点(i, j)
映射到数字i * 4 + j
.在图中,边缘是相邻点的反射,这意味着如果(i1, j1)
和(i2, j2)
在图像中相邻,则i1 * 4 + j1
和i2 * 4 + j2
在图中是相邻的.
Assuming a graph would be a set of nodes {1, 2, ..., 16}
, we can map every point (i, j)
to the number i * 4 + j
. In the graph, the edges are a reflection of neighboring points, meaning that if (i1, j1)
and (i2, j2)
are adjacent in the image, then i1 * 4 + j1
and i2 * 4 + j2
are adjacent in the graph.
这时,我们有了一个可以计算最短路径的图.
At this point, we have a graph on which we can compute the shortest path.
幸运的是,python为图像加载和最短路径实现提供了简单的实现.以下代码处理路径计算以可视化结果:
Luckily, python provides easy implementation to the image loading and to the shortest path implementation. The following code handles the path computation the visualizes the result:
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()
免责声明:
- 我在图像处理方面没有经验,所以我怀疑解决方案中的每个步骤.
- 该解决方案假定一个非常幼稚的邻接谓词.对于这部分,在计算几何中可能有一些更好的方法.
这篇关于在Python中计算位图中两点之间的最短路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!