给定图像的迷宫的表示和求解

Question

给出一个图像，表示和解决迷宫的最佳方法是什么？

给定一个JPEG图像（如上图所示），什么是最好的方法来读取它，将它解析成某种数据结构，并解决迷宫？我的第一个本能是逐像素读取图像，并将其存储在布尔值列表（数组）中:true表示白色像素，而false表示非白色像素（颜色可以丢弃）。这种方法的问题是，图像可能不是“像素完美”的。我的意思是，如果墙上的某个地方有一个白色像素，它可能会产生一条意想不到的路径。

另一种方法（经过思考后我想到的）是将图像转换为SVG文件--这是画布上绘制的路径列表。这样，路径可以被读入相同类型的列表（布尔值）中，其中true表示路径或墙，false表示可旅行空间。如果转换不是100%准确，并且没有完全连接所有的墙，从而产生空隙，那么这种方法就会出现问题。

转换到SVG的另一个问题是线条不是“完全”直的。这导致路径为三次bezier曲线。使用由整数索引的布尔值的列表（数组），曲线将不容易传输，并且必须计算曲线上的所有点，但不会与列表索引完全匹配。

我假设这些方法中的一种可能起作用（尽管可能不起作用），但是对于如此大的图像，它们的效率非常低，并且存在一种更好的方法。如何做到最好（最有效和/或最不复杂）？有没有最好的办法？

然后是迷宫的解开。如果我使用前两种方法中的任何一种，我基本上会得到一个矩阵。根据这个答案，表示迷宫的好方法是使用树，解决迷宫的好方法是使用a*算法。如何从图像中创建一棵树？有什么想法吗？

lt；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, [])

Answer 1

这里有一个解决方案。

1. 将图像转换为灰度（还不是二进制），调整颜色的权重，使最终的灰度图像大致均匀。您可以简单地在Photoshop中控制图像->调整->黑白
中的滑块
2. 通过在图像->调整->阈值中的Photoshop中设置适当的阈值将图像转换为二进制。
3. 确保阈值选择正确。使用0公差的魔棒工具，点样，连片，无抗锯齿。检查选择中断处的边缘是否为错误阈值引入的假边缘。事实上，这个迷宫的所有内部点从一开始就可以访问。
4. 在迷宫上添加人工边界，以确保虚拟旅行者不会在迷宫周围行走:)
5. 用您喜欢的语言实现广度优先搜索(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中实现它应该不会有什么困难。

答案如下：