如何用程序解图片迷宫？-H5 Tutorial-php.cn

　英文原文：Representing and solving a maze given an image

　　译注：原文是 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 &gt; 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)) &amp;&amp; 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 &lt;= 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

Copy after login

这是个简单的实现，应该很容易就能够改写为 Python 或其他语言，下面是程序的运行结果：

提问者更新：

　　我用 Python 实现了一下 Mikhail 的方法，其中用到了 numpy 库，感谢 Thomas 推荐。我感觉这个算法是正确的，但是效果不太如预期，以下是相关代码，使用了 PyPNG 库处理图片。

　　译注：很遗憾，我用提问者提供的代码并没有跑通程序，并且似乎代码缩进有点问题，而下面其他参与者的代码能够执行通过，并且效果很好。

import png, numpy, Queue, operator, itertools

def is_white(coord, image):
  &quot;&quot;&quot; Returns whether (x, y) is approx. a white pixel.&quot;&quot;&quot;
  a = True
  for i in xrange(3):
    if not a: break
    a = image[coord[1]][coord[0] * 3 + i] &gt; 240
  return a

def bfs(s, e, i, visited):
  &quot;&quot;&quot; Perform a breadth-first search. &quot;&quot;&quot;
  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 = &quot;thescope-134.png&quot;)
  rows, cols, pixels, meta = r.asDirect()
  assert meta[&#039;planes&#039;] == 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, [])

Copy after login

　回答 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 &quot;Queue has been exhausted. No answer was found.&quot;

if __name__ == &#039;__main__&#039;:

    # 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])

Copy after login

动态执行效果：

回答 by Jim

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

　　下面是相关的 MATLAB 代码及运行结果：

% read in and invert the image
im = 255 - imread(&#039;maze.jpg&#039;);

% sharpen it to address small fuzzy channels
% threshold to binary 15%
% run connected components
result = bwlabel(im2bw(imfilter(im,fspecial(&#039;unsharp&#039;)),0.15));

% purge small components (e.g. letters)
for i = 1:max(reshape(result,1,1002*800))
    [count,~] = size(find(result==i));
    if count &lt; 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(&#039;square&#039;,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);

Copy after login