python - 蟒蛇查找路径
问题描述
在黑白图像中查找连接图像左上角和右下角的路径的不知情搜索,仅通过深度搜索(DFS)的黑色像素,我的程序已经打开图像,opencv
如果我放了一个坐标,它告诉我像素是否为黑色,但不知道如何做剩下的。此外,我必须使用找到的路径创建一个图像,制作一个为后继列表中的每个项目绘制一个像素的图像。
解决方案
让我们阅读图像
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')
推荐阅读
- embedded - 在 STM32 设备中读取和写入文件到闪存的末尾
- clojure - 如何遍历列表并制作元素列表
- asp.net-core - Blazor 服务器端递归组件内存消耗过多
- javascript - Chrome 扩展将动态脚本注入标头和打开正文标记后
- d3.js - 气泡图中 y 位置的强制碰撞
- xcode - Xcode 11 - 关于为 iOS 构建的 ld 警告,但为独立构建的目标文件
- c++ - 将 Eigen::MatrixXd 转换为 arma::mat 并在新对象上制作副本
- c++ - 做图灵机,不太懂动作表
- apache - Python 应用程序的 HTTP 504 错误 AWS ElasticBeanstalk
- javascript - React Hooks 静态变量:对象属性与 useRef()