代表和解决迷宫的形象
代表和解决一个迷宫的最佳方式是什么？
给出一个JPEG图像（如上所示），读入它的最佳方式是什么，将其parsing为一些数据结构并解决迷宫问题？ 我的第一本能是逐像素地读取图像，并将其存储在布尔值的列表（数组）中：对于白色像素为True ，对于非白色像素为False （可以丢弃颜色）。 这个方法的问题是，图像可能不是“像素完美”。 我只是说，如果在墙上的某个地方有一个白色像素，它可能会产生一个无意的path。
另一种方法（经过一番思考后find的）是将图像转换为SVG文件 – 这是在canvas上绘制的path列表。 这样，path可以被读入相同types的列表（布尔值），其中True表示path或墙壁， False表示可行驶的空间。 如果转换不是100％准确的，并且没有完全连接所有的墙壁，则会产生这种方法的问题，造成空白。
另外一个转换为SVG的问题是线条不是“完美”的直线。 这导致path为三次贝塞尔曲线。 对于由整数索引的布尔值列表（数组），曲线不会轻易转移，曲线上的所有点将不得不计算，但与列表索引不完全匹配。
我认为，虽然其中一种方法可能有效（尽pipe可能不是），但鉴于这样一个大的形象，它们可能是效率低下的，而且存在一个更好的方法。 这是如何最好（最有效和/或最简单的）？ 还有最好的方法吗？
然后是解决迷宫。 如果我使用前两种方法中的任何一种，我将基本上以matrix结束。 根据这个答案 ，代表一个迷宫的一个好方法是使用一棵树，而解决这个问题的一个好方法是使用A *algorithm 。 如何从图像中创build一棵树？ 有任何想法吗？
TL; DR
最好的parsing方法？ 进入什么数据结构？ 上述结构如何帮助/阻碍解决？
UPDATE
我已经试过我的手在实现@Mikhail使用numpy编写的Python，就像@Thomas推荐的一样。 我觉得这个algorithm是正确的，但是这个algorithm并没有像预期的那样工作。 （代码如下）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, [])
这是一个解决scheme。
- 将图像转换为灰度（尚未二进制），调整颜色的权重，使最终的灰度图像近似一致。 您可以简单地通过在图像 – >调整 – >黑白控制滑块在Photoshop中。
- 通过在图像 – >调整 – >阈值的Photoshop中设置适当的阈值将图像转换为二进制。
- 确保阈值select正确。 使用Magic Wand工具，公差为0，点采样，连续，无消除锯齿。 检查select中断的边缘是不是由错误的阈值引入的虚假边缘。 事实上，这个迷宫的所有内部点都可以从一开始。
- 在迷宫中添加人造边框以确保虚拟旅行者不会在其周围走动:)
- 使用您最喜欢的语言实现广度优先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或其他方面实现这个应该不会有困难。
这里是答案：
这个解决scheme是用Python编写的。 感谢米哈伊尔为图像准备的指针。
animation广度优先search：
完成的迷宫：
#!/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])
注：标记一个白色的访问像素灰色。 这消除了访问列表的需要，但是这需要在绘制path之前从磁盘第二次加载图像文件（如果不需要最终path和所有path的合成图像）。
我使用的迷宫的空白版本。
我试图自己实施这个问题的星级search。 紧随其后的是Joseph Kern对这个框架和algorithm伪代码的实现：
import heapq def AStar(start, goal, neighbor_nodes, dist_between, heuristic_cost_estimate): def reconstruct_path(came_from, current_node): path = [current_node] while current_node in came_from: current_node = came_from[current_node] path.append(current_node) return list(reversed(path)) g_score = {start: 0} f_score = {start: g_score[start] + heuristic_cost_estimate(start, goal)} openheap = [(f_score[start], start)] openset = {start} closedset = set() came_from = dict() while openset: _, current = heapq.heappop(openheap) openset.remove(current) if current == goal: return reconstruct_path(came_from, goal) closedset.add(current) for neighbor in neighbor_nodes(current): tentative_g_score = ( g_score[current] + dist_between(current, neighbor) ) if neighbor in closedset and tentative_g_score >= g_score[neighbor]: continue if neighbor not in openset or tentative_g_score < g_score[neighbor]: came_from[neighbor] = current g_score[neighbor] = tentative_g_score # TODO: there might be an implementation error: # is the heap updated when the f_score of a node is changed? f_score[neighbor] = ( g_score[neighbor] + heuristic_cost_estimate(neighbor, goal) ) if neighbor not in openset: heapq.heappush(openheap, (f_score[neighbor], neighbor)) openset.add(neighbor) print "no path found :("
由于A-Star是一种启发式searchalgorithm，因此您需要提供估算剩余成本（此处为距离）的函数，直到达到目标。 除非你对一个不理想的解决scheme感到满意，否则不应该高估成本。 这里保守的select是曼哈顿（或者出租车）距离，因为这代表了用于冯诺依曼邻域的两个点之间的直线距离。 （在这种情况下，它永远不会高估成本。）
然而，这会显着低估当前迷宫的实际成本。 所以我加了两个距离度量平方欧氏距离和曼哈顿距离乘以四来比较。 然而，这些可能会高估实际成本，因此可能会产生不理想的结果。
代码如下：
import sys from PIL import Image def is_blocked(p): x,y = p pixel = path_pixels[x,y] if any(c < 225 for c in pixel): return True def von_neumann_neighbors(p): x, y = p neighbors = [(x-1, y), (x, y-1), (x+1, y), (x, y+1)] return [p for p in neighbors if not is_blocked(p)] def manhattan(p1, p2): return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1]) def squared_euclidean(p1, p2): return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2 start = (400, 984) goal = (398, 25) # invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.] path_img = Image.open(sys.argv[1]) path_pixels = path_img.load() path = AStar(start, goal, von_neumann_neighbors, manhattan, manhattan, #lambda p1,p2 : 4*manhattan(p1,p2), #squared_euclidean, ) for position in path: x,y = position path_pixels[x,y] = (255,0,0) # red path_img.save(sys.argv[2])
下面是一些结果可视化图片（由Joseph Kern发布的图片）。 animation在主while循环的10000次迭代后显示一个新的帧。
广度优先search：
星级曼哈顿距离：
一星平方欧几里得距离：
曼哈顿星际距离乘以四：
结果显示，迷宫的探索区域在所使用的启发式方面差别很大。 因此，平方欧氏距离甚至产生与其他度量不同的（次优）path。
关于A-Staralgorithm在运行时直到终止时的性能，请注意，与广度优先search（BFS）相比，距离和成本函数的许多评估加起来，只需要评估“守门员”每个候选人的位置 这些额外的function评估（A-Star）的成本是否超过大量节点检查（BFS）的成本，尤其是性能是否是您的应用程序的问题，这是个人感知的问题当然不能普遍回答。
一般来说，与详尽的search（例如BFS）相比，知情searchalgorithm（例如A-Star）是否可能是更好的select是以下内容。 随着迷宫的维数（即search树的分支因子），穷举search（穷尽search）的缺点呈指数增长。 随着复杂性的增加，这样做变得越来越不可行，并且在某种程度上，你对任何结果path都非常满意， 无论是（大约）最优的还是不是。
树search太多了。 迷宫沿解path是固有的可分离的。
（感谢来自Reddit的rainman002指出了这一点。）
因此，您可以快速使用连接的组件来识别连接的迷宫壁部分。 这遍历像素两次。
如果您想将其转化为解决schemepath的一个很好的图表，则可以使用具有结构元素的二元操作来填充每个连接区域的“死angular”path。
MATLAB的演示代码如下。 它可以使用调整来更好地清理结果，使其更加通用化，并使其运行得更快。 （有时不是2:30 AM）
% 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 (eg 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);
使用队列进行阈值连续填充。 将入口左侧的像素推入队列，然后启动循环。 如果一个排队的像素足够暗，它就是浅灰色（高于阈值），并且所有邻居都被推入队列。
from PIL import Image img = Image.open("/tmp/in.jpg") (w,h) = img.size scan = [(394,23)] while(len(scan) > 0): (i,j) = scan.pop() (r,g,b) = img.getpixel((i,j)) if(r*g*b < 9000000): img.putpixel((i,j),(210,210,210)) for x in [i-1,i,i+1]: for y in [j-1,j,j+1]: scan.append((x,y)) img.save("/tmp/out.png")
解决scheme是灰墙和彩色墙之间的走廊。 请注意，这个迷宫有多个解决scheme。 而且，这似乎只是工作。
在这里你去： maze-solver-python （GitHub）
我玩得很开心，并且延续了Joseph Kern的回答。 不要贬低它; 我只是对可能对此感兴趣的任何人做了一些小的补充。
这是一个基于python的求解器，它使用BFS来find最短path。 我当时的主要补充是：
- 在search之前清理图像（即转换为纯黑白）
- 自动生成一个GIF。
- 自动生成一个AVI。
就目前而言，开始/结束点是硬编码的示例迷宫，但我打算扩展它，以便您可以select适当的像素。
我会去的matrix的bools选项。 如果您发现标准Python列表效率太低，您可以使用numpy.bool数组。 那么1000×1000像素的迷宫存储就是1MB。
不要打扰创build任何树或graphics数据结构。 这只是一种思考的方式，但不一定是把它expression出来的好方法。 布尔matrix更容易编码和更高效。
然后使用A *algorithm来解决它。 对于距离启发式，使用曼哈顿距离（ distance_x + distance_y ）。
用(row, column)坐标元组来表示节点。 每当algorithm（ 维基百科伪代码 ）要求“邻居”，这是一个简单的问题，循环四个可能的邻居（介意图像的边缘！）。
如果您发现它仍然太慢，您可以尝试缩小图像，然后再加载它。 小心不要在这个过程中失去任何狭窄的path。
也许可以在Python中进行1：2的缩放，检查是否确实没有丢失任何可能的path。 一个有趣的select，但它需要更多的思想。
这里有一些想法。
（1.image processing:)
1.1将图像加载为RGB像素图。 在C＃中使用system.drawing.bitmap是微不足道的。 在对图像没有简单支持的语言中，只需将图像转换为便携式像素映射格式 （PPM）（Unix文本表示，生成大文件）或一些简单的二进制文件格式（例如BMP或TGA）即可轻松读取。 Unix中的ImageMagick或Windows中的IrfanView 。
1.2如前所述，您可以通过将每个像素的（R + G + B）/ 3作为灰度色调的指标来简化数据，然后对该值进行阈值生成黑白表格。 假设0 =黑色和255 =白色的东西接近200将取出JPEG文物。
（2.解决scheme:)
2.1深度优先search：首先初始化一个空的堆栈，然后收集可用的后续动作，随机挑选一个堆栈，并将其推入堆栈，直至达到结尾或出现死angular。 通过popup堆栈来消除回溯，您需要跟踪在地图上访问的位置，所以当您收集可用的移动时，您将永远不会采用相同的path两次。 非常有趣的animation。
2.2广度优先search：前面提到，类似于上面，但只使用队列。 也有趣的animation。 这个工作就像填充图像编辑软件一样。 我想你可以用这个技巧来解决Photoshop中的迷宫问题。
2.3墙壁追随者：在几何学上，迷宫是一个折叠/curl的pipe子。 如果你把手放在墙上，你最终会find出口;）这并不总是奏效。 有一定的假设：完美的迷宫等，例如，某些迷宫含有岛屿。 看看它; 这是令人着迷的。
（3.评论:)
这是一个棘手的问题。 如果用一些简单的数组来表示，每个元素是一个具有北，东，南，西墙和被访问的标志域的单元types，则很容易解决迷宫问题。 然而，鉴于你正在试图做一个手绘草图这变得凌乱。 我真的认为，试图合理化草图将驱使你疯了。 这类似于相当涉及的计算机视觉问题。 也许直接进入图像映射可能更容易但更浪费。
