python 查找路径

Question

不知情的搜索在黑白图像中找到连接图像左上角和右下角的路径，仅通过深度搜索 (DFS) 的黑色像素，我的程序已经用 opencv 打开图像并且如果我输入坐标，它会告诉我像素是否为黑色，但我不知道如何进行其余操作。此外，我还必须使用找到的路径创建一个图像，制作一个为后继列表中的每个项目绘制一个像素的图像。

Answer 1

让我们看图

import cv2
im = cv2.imread("image.png", 0)

现在，我们可以使用这张图片构建一个图，并使用寻路算法，我们可以获得两个节点之间的路径。

from itertools import product, chain
import math
import mtplotlib.pyplot as plt
import numpy as np
import networkx as nx


h, w = im.shape. # Get height and width of image

# Add only those nodes which are black to graph
nodes = [(i, j) for (i, j) in product(range(h), range(w)) if im[i, j] == 0]
g = nx.Graph(nodes)

# For each node there can be 8 neighbours, if you consider diagonal as well.
def get_neighbors(node):
    box_coords = product([-1, 0, 1], [-1, 0, 1])
    nns = []
    for coord in box_coords:
        if coord[0] != coord[1]:
            nn = (node[0] - coord[0], node[1] - coord[1])
            nns.append(nn)
    return nns

# A point will be a neighbour if it is black as well and is in image bounds
neighbors = list(chain.from_iterable([[(node, ng_node, 1) for ng_node in  get_neighbors(node) if (im[node] == 0) and (0 < ng_node[0] < h) and (0 < ng_node[1] , w)] for node in nodes]))

g.add_weighted_edges_from(neighbors)

# In image loaded above (0, 0) is top left point. To keep things little more generic. I select point closest to (0, 0) as start and furthest as end.

min_pt = min(nodes, key=lambda x: math.hypot(x[0], x[1]))
max_pt = max(nodes, key=lambda x: math.hypot(x[0], x[1]))

# Now we can just use networkx to find path between two points
path = nx.shortest_path(g, source=min_pt, target=max_pt)

# Get new image with only shortest path
im2 = 255*np.ones_like(im)
for pt in path:
    im2[pt] = 0
cv2.imwrite('image_path.png', im2)
plt.figure(figsize=(10, 10))
plt.imshow(im2, cmap='gray')