如何在骨架化的迷宫图像中找到最短路径？

Question

我正在使用 Image Processing 和 NetworkX 搜索算法解决迷宫问题，需要找到两点之间的最短连接路径那些线。

#Solving Maze Using Image Processing and NetWorkx search



    #Open Maze image
    img = cv2.imread("C:/Users/Dell/HandMadeMaze1.jpg")
    kernel = np.ones((1,1),np.uint8)

    #Convert to GrayScaledImage
    grayscaled = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

    #BınaryThreshold + OtsuThreshold + BinaryThreshold
    retval, threshold = cv2.threshold(grayscaled, 10, 255, cv2.THRESH_BINARY_INV+cv2.THRESH_OTSU)
    retval, threshold2 = cv2.threshold(threshold, 10, 255, cv2.THRESH_BINARY_INV)
    threshold2[threshold2 == 255] = 1

    #Skeletonize the Thresholded Image
    skel = skeletonize(threshold2)

    #Build Graph from skeleton
    graph = sknw.build_sknw(skel, multi=False)
    G = nx.Graph(graph)
    plt.imshow(img, cmap='gray')

    #Draw Edges by 'pts'
    for (s,e) in graph.edges():
        ps = graph[s][e]['pts']
        plt.plot(ps[:,1], ps[:,0], 'red')

    #Draw Node by 'o'   
    node, nodes = graph.node, graph.nodes()
    ps = np.array([node[i]['o'] for i in nodes])
    plt.plot(ps[:,1], ps[:,0], 'g.')
    plt.title('Skeletonize')
    plt.savefig('Overlay_Maze.jpg')
    plt.show()

    G = nx.path_graph(len(ps))
    G = nx.karate_club_graph()
    pos = nx.spring_layout(G)
    nx.draw(G,pos,node_color='b')

当我运行上面的代码时，我得到以下输出。

原始输入迷宫图像：

--

图像处理后：

--

X-Y坐标上的节点：

--

路径信息：

我可以成功执行图像处理操作，但搜索算法找到了两个节点之间的最短鸟类飞行距离。 我想找到沿着骨架的最短路径。

当我在处理这个问题时 github repo 向我展示了使用 NetworkX 库解决这个问题但我无法解决它，因为它没有提供任何细节。

如何使用图像处理和任何搜索算法找到沿迷宫图像骨架的最短路径？

提前致谢。

Answer 1

这是因为您在此处重新分配对骨架图的引用

G = nx.path_graph(len(ps))
G = nx.karate_club_graph()

Answer 2

可以使用skimage中的graph函数来实现。

import skimage.graph
### give start (y1,x1) and end (y2,x2) and the binary maze image as input
def shortest_path(start,end,binary):
    costs=np.where(binary,1,1000)
    path, cost = skimage.graph.route_through_array(
        costs, start=start, end=end, fully_connected=True)
    return path,cost

如何在骨架化的迷宫图像中找到最短路径？

How to find shortest path in skeletonized maze image?

python-2.7

opencv

image-processing

networkx

image-morphology