在给定的图像中，表现和解决迷宫的最佳方法是什么?
Given an JPEG image (as seen above), what's the best way to read it in, parse it into some data structure and solve the maze? My first instinct is to read the image in pixel by pixel and store it in a list (array) of boolean values: True for a white pixel, and False for a non-white pixel (the colours can be discarded). The issue with this method, is that the image may not be "pixel perfect". By that I simply mean that if there is a white pixel somewhere on a wall it may create an unintended path.
另一种方法(经过思考后我想到的)是将图像转换为SVG文件——这是在画布上绘制的路径列表。这样，路径可以读入相同类型的列表(布尔值)，其中True表示路径或墙壁，False表示可移动空间。如果转换不是100%准确，并且没有完全连接所有的墙壁，就会出现一个问题。
转换为SVG的另一个问题是，这些线不是“完全”直的。这导致路径是三次贝塞尔曲线。对于一个由整数索引的布尔值列表(数组)，曲线将不容易转移，并且曲线上的所有点都必须计算，但不会与列表索引完全匹配。
我认为，虽然这些方法中的一种可能有效(虽然可能不是)，但对于如此大的图像，它们的效率非常低，并且存在更好的方法。如何才能做到最好(最有效和/或最简单)?有没有最好的办法?
然后是迷宫的解决。如果我用前两种方法中的任何一种，我最终都会得到一个矩阵。根据这个答案，表示迷宫的好方法是使用树，解决迷宫的好方法是使用a *算法。如何从图像中创建树?什么好主意吗?
博士TL;
最好的解析方法?转换成什么样的数据结构?结构如何帮助/阻碍解决问题?
更新
正如@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, [])
树搜索太多了。迷宫在解的路径上本质上是可分离的。
(感谢Reddit的rainman002为我指出了这一点。)
正因为如此，你可以快速使用连接组件来识别迷宫墙壁的连接部分。这将在像素上迭代两次。
如果您希望将其转换为解决方案路径的漂亮图表，那么您可以使用带有结构化元素的二进制操作来填充每个连接区域的“死胡同”路径。
下面是MATLAB的演示代码。它可以通过调整来更好地清理结果，使其更一般化，并使其运行得更快。(不是凌晨两点半的时候)
% read in and invert the image
im = 255 - imread('maze.jpg');
% sharpen it to address small fuzzy channels
% threshold to binary 15%
% run connected components
result = bwlabel(im2bw(imfilter(im,fspecial('unsharp')),0.15));
% purge small components (e.g. letters)
for i = 1:max(reshape(result,1,1002*800))
[count,~] = size(find(result==i));
if count < 500
result(result==i) = 0;
end
end
% close dead-end channels
closed = zeros(1002,800);
for i = 1:max(reshape(result,1,1002*800))
k = zeros(1002,800);
k(result==i) = 1; k = imclose(k,strel('square',8));
closed(k==1) = i;
end
% do output
out = 255 - im;
for x = 1:1002
for y = 1:800
if closed(x,y) == 0
out(x,y,:) = 0;
end
end
end
imshow(out);
这个解决方案是用Python编写的。感谢米哈伊尔对图像准备的指导。
一个动画宽度优先搜索:
完成的迷宫:
#!/usr/bin/env python
import sys
from Queue import Queue
from PIL import Image
start = (400,984)
end = (398,25)
def iswhite(value):
if value == (255,255,255):
return True
def getadjacent(n):
x,y = n
return [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]
def BFS(start, end, pixels):
queue = Queue()
queue.put([start]) # Wrapping the start tuple in a list
while not queue.empty():
path = queue.get()
pixel = path[-1]
if pixel == end:
return path
for adjacent in getadjacent(pixel):
x,y = adjacent
if iswhite(pixels[x,y]):
pixels[x,y] = (127,127,127) # see note
new_path = list(path)
new_path.append(adjacent)
queue.put(new_path)
print "Queue has been exhausted. No answer was found."
if __name__ == '__main__':
# invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]
base_img = Image.open(sys.argv[1])
base_pixels = base_img.load()
path = BFS(start, end, base_pixels)
path_img = Image.open(sys.argv[1])
path_pixels = path_img.load()
for position in path:
x,y = position
path_pixels[x,y] = (255,0,0) # red
path_img.save(sys.argv[2])
注意:标记白色访问像素灰色。这消除了访问列表的需要，但这需要在绘制路径之前从磁盘上第二次加载图像文件(如果您不想要最终路径和所有路径的合成图像)。
我用过的空白迷宫。
这里有一个解决方案。
Convert image to grayscale (not yet binary), adjusting weights for the colors so that final grayscale image is approximately uniform. You can do it simply by controlling sliders in Photoshop in Image -> Adjustments -> Black & White.
Convert image to binary by setting appropriate threshold in Photoshop in Image -> Adjustments -> Threshold.
Make sure threshold is selected right. Use the Magic Wand Tool with 0 tolerance, point sample, contiguous, no anti-aliasing. Check that edges at which selection breaks are not false edges introduced by wrong threshold. In fact, all interior points of this maze are accessible from the start.
Add artificial borders on the maze to make sure virtual traveler will not walk around it :)
Implement breadth-first search (BFS) in your favorite language and run it from the start. I prefer MATLAB for this task. As @Thomas already mentioned, there is no need to mess with regular representation of graphs. You can work with binarized image directly.
下面是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或其他语言中实现它应该没有困难。
这就是答案:
