在给定图像的情况下,表示和解决迷宫的最佳方法是什么?
给定一张 JPEG 图像(如上所示),读取它、将其解析为某种数据结构并解决迷宫问题的最佳方法是什么?我的第一直觉是逐像素读取图像并将其存储在 bool 值列表(数组)中:True
表示白色像素,False
表示非-白色像素(可以丢弃颜色)。这种方法的问题在于图像可能不是“像素完美”。我的意思是,如果墙上某处有一个白色像素,它可能会创建一条意想不到的路径。
另一种方法(经过一番思考后想到)是将图像转换为 SVG 文件 - 这是在 Canvas 上绘制的路径列表。这样,路径可以被读入相同类型的列表( bool 值),其中 True
表示路径或墙壁,False
表示可通行的空间。如果转换不是 100% 准确,并且没有完全连接所有墙壁,从而产生间隙,则此方法会出现问题。
转换为 SVG 的另一个问题是线条不是“完全”笔直的。这导致路径是三次贝塞尔曲线。使用整数索引的 bool 值列表(数组),曲线不会轻易转移,曲线上的所有点都必须计算,但不会与列表索引完全匹配。
我认为虽然其中一种方法可能有效(尽管可能无效),但考虑到如此大的图像,它们的效率非常低,并且存在更好的方法。这是如何做到最好(最有效和/或复杂性最低)的?有没有最好的办法?
然后是迷宫的解决。如果我使用前两种方法中的任何一种,我基本上都会得到一个矩阵。根据this answer ,表示迷宫的好方法是使用树,解决它的好方法是使用 A* algorithm .如何从图像中创建一棵树?有什么想法吗?
TL;DR
最好的解析方式?变成什么数据结构?所述结构如何帮助/阻碍解决?
更新
正如@Thomas 推荐的那样,我已经尝试使用numpy
来实现@Mikhail 用Python 编写的内容。我觉得算法是正确的,但它并没有像希望的那样工作。 (代码如下。)PNG库是PyPNG .
import png, numpy, Queue, operator, itertools
def is_white(coord, image):
""" Returns whether (x, y) is approx. a white pixel."""
a = True
for i in xrange(3):
if not a: break
a = image[coord[1]][coord[0] * 3 + i] > 240
return a
def bfs(s, e, i, visited):
""" Perform a breadth-first search. """
frontier = Queue.Queue()
while s != e:
for d in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
np = tuple(map(operator.add, s, d))
if is_white(np, i) and np not in visited:
frontier.put(np)
visited.append(s)
s = frontier.get()
return visited
def main():
r = png.Reader(filename = "thescope-134.png")
rows, cols, pixels, meta = r.asDirect()
assert meta['planes'] == 3 # ensure the file is RGB
image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels))
start, end = (402, 985), (398, 27)
print bfs(start, end, image2d, [])
最佳答案
这里有一个解决方案。
- 将图像转换为灰度(尚未二值化),调整颜色的权重以使最终的灰度图像大致均匀。您只需在 Photoshop 中的图像 -> 调整 -> 黑白中控制 slider 即可。
- 通过在 Photoshop 中的图像 -> 调整 -> 阈值中设置适当的阈值,将图像转换为二进制。
- 确保阈值选择正确。使用具有 0 容差、点采样、连续、无抗锯齿的魔棒工具。检查选择中断处的边缘是否不是由错误阈值引入的错误边缘。事实上,这个迷宫的所有内部点从一开始就可以进入。
- 在迷宫上添加人工边框,以确保虚拟旅行者不会在迷宫周围走动 :)
- 实现 breadth-first search (BFS) 使用您喜欢的语言并从一开始就运行它。我更喜欢 MATLAB对于这个任务。正如@Thomas 已经提到的,没有必要弄乱图形的常规表示。您可以直接使用二值化图像。
这是 BFS 的 MATLAB 代码:
function path = solve_maze(img_file)
%% Init data
img = imread(img_file);
img = rgb2gray(img);
maze = img > 0;
start = [985 398];
finish = [26 399];
%% Init BFS
n = numel(maze);
Q = zeros(n, 2);
M = zeros([size(maze) 2]);
front = 0;
back = 1;
function push(p, d)
q = p + d;
if maze(q(1), q(2)) && M(q(1), q(2), 1) == 0
front = front + 1;
Q(front, :) = q;
M(q(1), q(2), :) = reshape(p, [1 1 2]);
end
end
push(start, [0 0]);
d = [0 1; 0 -1; 1 0; -1 0];
%% Run BFS
while back <= front
p = Q(back, :);
back = back + 1;
for i = 1:4
push(p, d(i, :));
end
end
%% Extracting path
path = finish;
while true
q = path(end, :);
p = reshape(M(q(1), q(2), :), 1, 2);
path(end + 1, :) = p;
if isequal(p, start)
break;
end
end
end
真的很简单也很标准,在Python 中实现应该不会有什么困难。或其他。
这就是答案:
关于python - 表示和解决给定图像的迷宫,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12995434/