如何用程序解图片迷宫?

jopen 7年前

译注:原文是StackOverflow上一个如何用程序读取迷宫图片并求解的问题,几位参与者热烈地讨论并给出了自己的代码,涉及到用Python对图片的处理以及广度优先(BFS)算法等。

 

问题by Whymarrh:

如何用程序解图片迷宫?

当给定上面那样一张JPEG图片,如何才能更好地将这张图转换为合适的数据结构并且解出这个迷宫?

我的第一直觉是将这张图按像素逐个读入,并存储在一个包含布尔类型元素的列表或数组中,其中True代表白色像素,False代表非白色像素(或彩色可以被处理成二值图像)。但是这种做法存在一个问题,那就是给定的图片往往并不能完美的“像素化”。考虑到如果因为图片转换的原因,某个非预期的白色像素出现在迷宫的墙上,那么就可能会创造出一一条非预期的路径。

经过思考之后,我想出了另一种方法:首先将图片转换为一个可缩放适量图形(SVG)文件,这个文件由一个画布上的矢量线条列表组成,矢量线条按照列表的顺序读取,读取出的仍是布尔值:其中True表示墙,而False表示可通过的区域。但是这种方法如果无法保证图像能够做到百分之百的精确转换,尤其是如果不能将墙完全准确的连接,那么这个迷宫就可能出现裂缝。

图像转换为SVG的另一个问题是,线条并不是完美的直线。因为SVG的线条是三次贝塞尔曲线,而使用整数索引的布尔值列表增加了曲线转换的难度,迷宫线条上的所有点在曲线上都必须经过计算,但不一定能够完美对应列表中的索引值。

假设以上方法的确可以实现(虽然很可能都不行),但当给定一张很大的图像时,它们还是不能胜任。那么是否存在一种更好地方法能够平衡效率和复杂度?

这就要讨论到如何解迷宫了。如果我使用以上两种方法中的任意一种,我最终将会得到一个矩阵。而根据这个问答(http://stackoverflow.com/questions/3097556/programming-theory-solve-a-maze/3097677#3097677),一个比较好的迷宫表示方式应该是使用树的结构,并且使用A*搜索算法来解迷宫。那么如何从迷宫图片中构造出迷宫树呢?有比较好的方法么?

以上废话太多,总结起来问题就是:如何转换迷宫图片?转换成为什么样的数据结构?采用什么样的数据结构能够帮助或阻碍解迷宫?

 

回答by Mikhail:

这是我的解决方案:

1. 将图片转换为灰度图像(不是直接二值),调整不同颜色的权重使得最终的灰度看起来比较统一,你可以通过简单地调节Photoshop 图像->调整->黑白 菜单中的控制条来实现。
2. 将上一步得到的灰度图片转换为二值图片,可以通过在PS 图像->调整->阈值 菜单中设定适当的阈值来实现
3. 确保正确设置了阈值。使用魔棒工具(参数设置:容差 0、取样点、连续以及消除锯齿)选择空白区域,检查所选区域的边缘不是因为错误的阈值设置而产生的假边缘。事实上,这个迷宫中从start到end应该由联通的空白区域。
4. 人为地在迷宫外部加上边界,确保迷宫漫游者^_^不会从start绕着迷宫跑到终点。:)
5. 选择语言实现广度优先搜索算法(BFS),从start处开始让程序运行。下面的代码我选择用Matlab实现。正如Thomas提到的,没必要纠结于图像的表示形式,你可以直接在二值图像上运行。

以下是用MATLAB实现的BFS代码:

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实现了一下Mikhail的方法,其中用到了numpy库,感谢Thomas推荐。我感觉这个算法是正确的,但是效果不太如预期,以下是相关代码,使用了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, [])

回答by Joseph Kern:

#!/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  [.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])

动态执行效果:
如何用程序解图片迷宫?

 

回答by Jim

使用树搜索太繁杂了,迷宫本身就跟解路径是可分的。正因如此,你可以使用连通区域查找算法来标记迷宫中的连通区域,这将迭代搜索两次这些像素点。如果你想要更好地解决方法,你可以对结构单元使用二元运算(binary operations)来填充每个连通区域中的死路。

下面是相关的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);

如何用程序解图片迷宫?

回答by Stefano

stefano童鞋给出了生成搜索过程GIF及AVI文件的代码 maze-solver-python (GitHub)
如何用程序解图片迷宫?

原文链接: StackOverflow   翻译: 伯乐在线 - 熊崽Kevin
译文链接: http://blog.jobbole.com/62895/