python find path

Question

Uninformed search to find within a black and white image a path that connects the upper left corner of the image with the lower right corner, passing only black pixels with depth search (DFS), my program already opens the image with opencv and if I put a coordinate, it tells me if the pixel is black or not but idk how to do the rest. Also I have to create an image with the found path, making an image that paints a pixel for each item in the successor list.

user_9647951 · Answer

Lets read image

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

Now, we can build a graph using this image and using path finding algorithms, we can get path between two nodes.

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')

python find path

1 Answers