PROSAGA码农传奇-matlab-表示并解决给定图像的迷宫

<p>给定一个JPEG图像（如上所示），读取它，将其解析为某种数据结构并解决迷宫的最佳方法是什么？我的第一个本能是逐像素读取图像并将其存储在布尔值列表（数组）中：True对于白色像素，False对于非白色像素（可以丢弃颜色）。这种方法的问题在于图像可能不是“像素完美”的。我的意思只是说，如果墙壁上的某处有白色像素，可能会产生意外的路径。 另一种方法（经过一番思考后才想到）是将图像转换为SVG文件-SVG文件是在画布上绘制的路径的列表。这样，可以将路径读入相同种类的列表（布尔值），其中True表示路径或墙壁，False表示可移动的空间。如果转换不是100％准确，并且不能完全连接所有墙，从而产生间隙，则此方法会出现问题。 转换为SVG的另一个问题是这些线不是“完美”的直线。这导致路径是三次贝塞尔曲线。使用由整数索引的布尔值列表（数组），曲线将不易转移，并且必须计算曲线上直线的所有点，但不会与列表索引完全匹配。 我假设虽然其中一种方法可能会（虽然可能不会）起作用，但考虑到如此大的图像，它们的效率很低，并且存在更好的方法。如何做到最好（最有效和/或最低复杂度）？有没有最好的方法？ 然后是迷宫的解决。如果我使用前两种方法中的任何一种，则基本上将得到一个矩阵。根据此答案，表示迷宫的一种好方法是使用树，而使用A *算法解决该问题的好方法。一个人如何从图像中创建一棵树？有任何想法吗？ TL; DR 解析的最佳方法？变成什么数据结构？所述结构将如何帮助/阻碍解决？ 更新 我已尝试使用numpy@Thomas建议的方法，实现@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, [])</p>

这是一个解决方案。

将图像转换为灰度（尚未二进制），调整颜色的权重，以使最终的灰度图像大致均匀。您只需在Photoshop中控制图像->调整->黑白中的滑块即可完成此操作。
通过在Photoshop中的“图像”->“调整”->“阈值”中设置适当的阈值，将图像转换为二进制。
确保正确选择阈值。使用魔术棒工具，公差为0，点采样，连续，无抗锯齿。检查选择中断处的边不是由错误阈值引入的错误边。实际上，从一开始就可以访问此迷宫的所有内部点。
在迷宫上添加人工边界，以确保虚拟旅行者不会在它周围走动:)
以您喜欢的语言实现广度优先搜索（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或其他任何方式下实现它都应该没有困难。