给定imag表示和求解迷宫

Question

在给定图像的情况下，表示和解决迷宫的最佳方法是什么？

给定一个JPEG图像（如上图所示），读入它、将它解析成某种数据结构并解决迷宫的最佳方法是什么？我的第一直觉是逐像素读取图像，并将其存储在布尔值列表（数组）中：对于白色像素，True，对于非白色像素，False（颜色可以丢弃）。这种方法的问题是，图像可能不是“像素完美”。我的意思很简单，如果墙上有一个白色的像素，它可能会产生一个意想不到的路径。

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

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

我认为，虽然其中一种方法可能有效（尽管可能不起作用），但考虑到如此大的图像，它们的效率非常低，而且存在一种更好的方法。如何做到最好（最有效和/或最简单）？有没有最好的办法？

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

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

我试着对这个问题进行A星搜索。紧接着是框架的Joseph Kern实现和给定的算法伪代码here：

def AStar(start, goal, neighbor_nodes, distance, cost_estimate):
    def reconstruct_path(came_from, current_node):
        path = []
        while current_node is not None:
            path.append(current_node)
            current_node = came_from[current_node]
        return list(reversed(path))

    g_score = {start: 0}
    f_score = {start: g_score[start] + cost_estimate(start, goal)}
    openset = {start}
    closedset = set()
    came_from = {start: None}

    while openset:
        current = min(openset, key=lambda x: f_score[x])
        if current == goal:
            return reconstruct_path(came_from, goal)
        openset.remove(current)
        closedset.add(current)
        for neighbor in neighbor_nodes(current):
            if neighbor in closedset:
                continue
            if neighbor not in openset:
                openset.add(neighbor)
            tentative_g_score = g_score[current] + distance(current, neighbor)
            if tentative_g_score >= g_score.get(neighbor, float('inf')):
                continue
            came_from[neighbor] = current
            g_score[neighbor] = tentative_g_score
            f_score[neighbor] = tentative_g_score + cost_estimate(neighbor, goal)
    return []

由于A-Star是一种启发式搜索算法，你需要想出一个函数来估计剩余成本（这里是：距离），直到达到目标。除非你对次优方案感到满意，否则不应高估成本。这里的保守选择是manhattan (or taxicab) distance，因为这表示所用Von Neumann邻域网格上两点之间的直线距离。（在这种情况下，这绝对不会高估成本。）

然而，这将大大低估手边给定迷宫的实际成本。因此，我将另外两个距离度量平方欧几里德距离和曼哈顿距离乘以4进行比较。然而，这些可能高估了实际成本，因此可能产生次优结果。

代码如下：

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()

distance = manhattan
heuristic = manhattan

path = AStar(start, goal, von_neumann_neighbors, distance, heuristic)

for position in path:
    x,y = position
    path_pixels[x,y] = (255,0,0) # red

path_img.save(sys.argv[2])

这里有一些图片用于结果的可视化（受Joseph Kern发布的图片的启发）。动画在main while循环的10000次迭代后显示一个新帧。

广度优先搜索：

A星曼哈顿距离：

A星平方欧氏距离：

A星曼哈顿距离乘以4：

结果表明，对于所使用的启发式方法，迷宫的探索区域有很大的不同。因此，平方欧几里德距离甚至会产生与其他度量不同的（次优）路径。

关于A-Star算法在终止前的运行时间方面的性能，请注意，与只需要评估每个候选位置的“目标性”的广度优先搜索（BFS）相比，对距离和成本函数的许多评估相加。这些额外的功能评估（A-Star）的成本是否超过要检查的节点（BFS）的成本，特别是性能是否对应用程序来说是一个问题，这是个人的看法，当然不能得到普遍的回答。

与穷举搜索（例如，BFS）相比，通常可以说关于知情搜索算法（例如A-Star）是否是更好的选择的事情如下。随着迷宫维数的增加，即搜索树的分枝因子的增加，穷举搜索（穷举搜索）的缺点呈指数增长。随着复杂性的增加，这样做变得越来越不可行，在某个时候，无论结果路径是（近似）最优还是非最优，您都会对任何结果路径感到非常满意。

Answer 2

这是一个解决方案。

1. 将图像转换为灰度（尚未二进制），调整颜色的权重，使最终的灰度图像近似均匀。只需在图像中控制Photoshop中的滑块->；调整->；黑白即可。
2. 通过在图像中的Photoshop中设置适当的阈值->；调整->；阈值，将图像转换为二进制。
3. 确保阈值选择正确。使用魔术棒工具与0公差，点采样，连续，没有反走样。检查选择断开的边不是由错误阈值引入的假边。事实上，这个迷宫的所有内部点从一开始就可以进入。
4. 在迷宫上添加人工边界，以确保虚拟旅行者不会绕着迷宫走：）
5. 用您喜欢的语言实现breadth-first search（BFS），并从一开始就运行它。我更喜欢用MATLAB来完成这个任务。正如@托马斯已经提到的，没有必要去处理图的正则表示。您可以直接使用二值化图像。

下面是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或其他什么地方实现它应该不会有困难。

答案是：

Answer 3

这个解决方案是用Python编写的。感谢米哈伊尔对图像准备的指点。

动态宽度优先搜索：

完成的迷宫：

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

注意：将白色访问像素标记为灰色。这就不需要访问列表，但这需要在绘制路径之前从磁盘再次加载映像文件（如果不希望生成最终路径和所有路径的合成映像）。

A blank version of the maze I used.