给定一张图片，如何表示和解决迷宫问题

Question

如何通过图像表示和解决迷宫问题？

给定一个JPEG图像（如上所示），最好的方法是什么，可以将其读入，解析成某些数据结构并解决迷宫问题？我的第一反应是逐像素读取图像，并将其存储在布尔值列表（数组）中：True表示白色像素，False表示非白色像素（颜色可以丢弃）。这种方法的问题是，图像可能不是“像素完美”的。我指的是如果墙上有一个白色像素，它可能会创建一个意外的路径。

另一种方法（经过一点思考后想到的）是将图像转换为SVG文件-这是在画布上绘制的路径列表。这样，路径可以读入相同类型的列表（布尔值），其中True表示路径或墙壁，False表示可行走的空间。使用此方法时可能会出现问题，如果转换不是100％准确的，则无法完全连接所有墙壁，从而创建间隙。

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

我认为其中一种方法可能有效（尽管可能不是），但考虑到这样一个大图像，它们的效率非常低，而且存在更好的方法。最佳方法是什么（最高效和/或最简单）？甚至有最佳方法吗？

然后是解决迷宫的问题。如果我使用前两种方法之一，我最终将得到一个矩阵。根据此答案，表示迷宫的好方法是使用树，解决它的好方法是使用A*算法。如何从图像创建树？有什么想法吗？

TL;DR 最佳解析方式？转换为哪种数据结构？该结构如何帮助/阻碍解决？

更新
我尝试使用numpy实现了@Mikhail编写的Python代码，正如@Thomas建议的那样。我觉得算法是正确的，但它并没有像希望的那样工作。（下面是代码。）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, [])

- Whymarrh

---

我会将迷宫转换成黑白图像，并使用路径规划细胞自动机算法来解决它。 - Dan D.

您只需要处理那张图片，还是有许多类似的图片需要处理？也就是说，是否存在某些特定于这张图片的手动处理选项？ - Mikhail

@Whymarrh 我不会编写Python，但我非常确定你应该将visited.append(s)移动到for.if下，并用visited.append(np)替换它。一旦顶点被添加到队列中，它就被访问过了。实际上，这个数组应该被命名为“queued”。一旦到达终点，您也可以终止BFS。 - Mikhail

@Whymarrh，你似乎还跳过了路径提取块的实现。没有它，你只能找出终点是否可达，但无法知道如何到达。 - Mikhail

为了找出是否存在解决方案，UnionFind和Linear Scan是最快的算法。它不会给你路径，但会给你一组瓷砖，其中路径是其子集。 - st0le

Answer 1

这是一个解决方案。

1. 将图像转换为灰度（但不是二进制），通过调整颜色权重使最终的灰度图像大致均匀。您可以在Photoshop中通过控制“图像”->“调整”->“黑白”中的滑块来完成此操作。
2. 通过在Photoshop中设置适当的阈值，将图像转换为二进制，在“图像”->“调整”->“阈值”中进行设置。
3. 确保选择正确的阈值。使用魔术棒工具，容差为0，采样点，连续，无反锯齿。检查选择断开的边缘是否是由于错误的阈值引入的虚假边缘。实际上，这个迷宫的所有内部点都可以从起点到达。
4. 在迷宫上添加人工边界，以确保虚拟旅行者不会围绕它走：）
5. 使用您喜欢的语言实现breadth-first search（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或其他语言实现都不应该有困难。

以下是答案：

- Mikhail

---

@Whymarrh 好的，“只有这张图片”现在你已经有了答案。你有什么具体问题吗？我所列出的1-4项是我所询问的手动处理。第5项是BFS——图形的基本算法，但它可以直接应用于图像，而无需将像素转换为顶点和邻居转换为边缘。 - Mikhail

@Whymarrh DFS 不会找到最短的路径，而 BFS 会。它们本质上是相同的，唯一的区别是底层结构。DFS 使用栈（FILO），BFS 使用队列（FIFO）。 - Mikhail

在这里，BFS是正确的选择，因为它产生最短路径，即使走廊比1像素宽得多时，也会给出一个“合理”的路径。另一方面，DFS倾向于使用“泛洪填充”模式探索走廊和不太有希望的迷宫区域。 - j_random_hacker

你能发布该图片的未经过路径处理的版本吗？我正试图复制您的结果，但我的图片迷宫有许多孤立区域。 - Joseph Kern

@JosephKern 路径没有与任何墙重叠。只需删除所有红色像素，就可以了。 - Mikhail

Answer 2

这个解决方案是用Python编写的。感谢Mikhail对图像处理的指导。

一个动画广度优先搜索：

完成的迷宫：

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

注意：将一个白色的访问过的像素标记为灰色。这样可以避免需要一个已访问列表，但是在绘制路径之前需要从磁盘再次加载图像文件（如果您不想要最终路径和所有已经走过的路径组成的复合图像）。

我使用的迷宫的空白版本。

- Joseph Kern

---

因为您足够棒，即使在问题得到回答后仍然回来点赞了我，所以我制作了一张BFS的动画GIF，以帮助更好地可视化这个过程。 - Joseph Kern

不错，谢谢。对于其他想尝试这个的人，我想分享一下我遇到的困难以及我的一些建议。1）将图像转换为纯黑白或修改你的'isWhite()'函数以接受接近白色和黑色的颜色。我编写了一个'cleanImage'方法，预处理所有像素，将它们转换为纯白色或黑色，否则算法无法找到路径。2）明确地将图像读取为RGB格式[ base_img = Image.open(img_in); base_img = base_img.convert('RGB') ]。要获得一个gif文件，输出几个图像然后运行'convert -delay 5 -loop 1 *.jpg bfs.gif'。 - stefano

Answer 3

我尝试自己实现了A-Star搜索解决这个问题。紧密遵循Joseph Kern的框架和算法伪代码，此处提供了相关内容：

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算法是一种启发式搜索算法，您需要设计一个函数来估计到达目标所需的剩余成本（这里指距离）。除非您满意次优解，否则它不应高估成本。 这里的保守选择可能是曼哈顿（或出租车）距离，因为这代表了在使用Von Neumann邻域的网格上两点之间的直线距离。（在这种情况下，它永远不会高估成本。）

但是，这将会显着低估当前迷宫的实际成本。因此，我添加了两个其他的距离度量：平方欧几里得距离和曼哈顿距离乘以四作为比较。但是，这些可能高估实际成本，并且可能产生次优结果。

以下是代码：

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发布的一个图像启发）。这些动画显示主 while 循环的每10000次迭代后的一个新帧。

广度优先搜索：

A-Star 曼哈顿距离：

A-Star 平方欧氏距离：

A-Star 曼哈顿距离乘以四：

结果表明，使用不同的启发式方法，迷宫中探索的区域差异很大。因此，平方欧几里得距离甚至会产生与其他指标不同的（次优）路径。

关于 A-Star 算法在运行时间方面的性能，需要注意的是，与只需要评估每个候选位置的“目标价值”的广度优先搜索（BFS）相比，距离和成本函数的许多评估相加。这些额外的函数评估成本是否超过了要检查的节点数（BFS）的成本，尤其是对于您的应用程序来说性能是否是一个问题，这是一个个体感知的问题，当然不能一般化回答。

可以总体地说，关于是否使用启发式搜索算法（例如 A-Star）而不是穷举搜索（例如 BFS）可能是更好的选择，以下是一件事情。随着迷宫维度即搜索树的分支因子的增加，穷举搜索（耗尽搜索）的劣势呈指数增长。随着复杂性的增加，这变得越来越不可行，在某个点上，您几乎对任何结果路径都感到满意，无论它是否（近似）最优。

- moooeeeep

---

"A-Star 曼哈顿距离乘以四"？如果启发式函数可以高估距离，那么 A-Star 就不再是 A-Star 了。（因此也不能保证找到最短路径） - example

Answer 4

树搜索太过复杂了。迷宫沿着解决路径是本质可分离的。

(感谢 Reddit 用户 rainman002 指出这一点。)

因此，您可以快速使用 连通分量 来识别迷宫墙壁的连通区域。这会对像素进行两次迭代。

如果您想将其转换为漂亮的解决路径图表，那么您可以使用与结构元素的二进制操作来填补每个连通区域的"死角"通道。

下面是 MATLAB 的演示代码。它可以进行微调以更好地清理结果、使其更具普遍性并加速运行。（不是在凌晨2:30时）。

% 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);

- Jim Gray

Answer 5

在这里：maze-solver-python (GitHub)

我玩得很开心，并对Joseph Kern的解答进行了扩展。不是为了削弱它，而是为了给其他可能感兴趣的人一些小的添加。

这是一个基于Python的求解器，使用BFS算法寻找最短路径。我当时主要的添加有：

1. 在搜索之前清理图像（即转换为纯黑白）
2. 自动生成GIF文件。
3. 自动生成AVI文件

目前为止，起点/终点在这个示例迷宫中是硬编码的，但我计划扩展它，使您可以选择适当的像素。

- stefano

---

太好了，谢谢。它在BSD/Darwin/Mac上没有运行，一些依赖项和shell脚本需要进行微小的更改，对于那些想在Mac上尝试的人：[maze-solver-python]: https://github.com/holg/maze-solver-python - HolgT

@HolgT：很高兴你觉得它有用。我欢迎任何关于这个的pull requests。 :) - stefano

Answer 6

使用队列实现连续填充的阈值。将入口左侧的像素推入队列，然后开始循环。如果队列中的像素足够暗，则将其着色为浅灰色（高于阈值），并将所有邻居推入队列。

from PIL import Image
img = Image.open("/tmp/in.jpg")
(w,h) = img.size
scan = [(394,23)]
while(len(scan) > 0):
    (i,j) = scan.pop()
    (r,g,b) = img.getpixel((i,j))
    if(r*g*b < 9000000):
        img.putpixel((i,j),(210,210,210))
        for x in [i-1,i,i+1]:
            for y in [j-1,j,j+1]:
                scan.append((x,y))
img.save("/tmp/out.png")

解决方案是灰色墙和彩色墙之间的走廊。请注意，这个迷宫有多个解决方案。此外，这似乎仅仅是可行的。

- kylefinn

---

有趣的天真解决方案，基于手靠在墙上的方法。确实不是最好的选择，但我喜欢它。 - zessx

Answer 7

以下是一些想法。

(1. 图像处理:)

1.1 将图像作为 RGB 像素图加载。在 C# 中，使用 system.drawing.bitmap 很容易实现。如果语言不支持成像，则只需将图像转换为 可移植像素图格式 (PPM)（Unix 文本表示，产生大文件）或某些简单的二进制文件格式以便于读取，比如 BMP 或 TGA。在 Unix 上可以使用 ImageMagick 或者在 Windows 上可以使用 IrfanView。

1.2 如前所述，您可以通过对每个像素的 (R+G+B)/3 取值作为灰度色调的指示器，并将该值阈值化以生成黑白表格来简化数据。接近 200 的值，假设 0=黑色，255=白色，将消除 JPEG 的伪影。

(2. 解决方案:)

2.1 深度优先搜索: 初始化一个起始位置的空栈，收集可以跟随的移动，随机选择一种并将其推入堆栈，继续直到到达终点或死路。在死路上回溯弹出堆栈，需要跟踪访问地图上的哪些位置，以便在收集可用移动时不会重复走同一条路径。非常有趣的动画效果。

2.2 广度优先搜索: 如前所述，类似于上面的方法，但只使用队列。也很有趣的动画效果。这就像图像编辑软件中的填充工具。我认为你可以使用这个技巧在 Photoshop 中解决迷宫。

2.3 遵循墙壁: 几何上讲，迷宫是一个折叠/卷曲的管道。如果你手放在墙上，最终会找到出口 ;) 这并不总是有效的。对于完美的迷宫等，存在某些假设条件。请查询一下；这很有趣。

(3. 注释:)

这是比较棘手的问题。如果以每个元素为一个单元格类型的简单数组形式表示，则很容易解决迷宫问题，并且包含北、东、南和西墙壁以及已访问标志字段。但是，考虑到您试图使用手绘草图来解决这个问题，这将变得混乱。我真的认为试图理性化这张草图会让你发疯。这类似于相当复杂的计算机视觉问题。也许直接进入图像地图可能更容易，但更加浪费。

- lino

Answer 8

我会选择布尔矩阵选项。如果您发现标准的Python列表对此效率太低，可以改用numpy.bool数组。1000x1000像素迷宫的存储只需要1 MB。

不要费心创建任何树形或图形数据结构。那只是一种思考方式，但不一定是在内存中表示它的好方法；布尔矩阵既易于编码又更有效。

然后使用A*算法来解决它。对于距离启发式，使用曼哈顿距离（distance_x + distance_y）。

通过元组的(row, column)坐标表示节点。每当算法（维基百科伪代码）调用“邻居”时，只需简单地循环遍历四个可能的邻居（注意图像的边缘！）。

如果您发现速度仍然太慢，可以尝试在加载之前缩小图像。请注意不要在此过程中丢失任何狭窄的路径。

也许在Python中可以进行1:2的缩放，同时确保不会丢失任何可能的路径。这是一个有趣的选项，但需要更多的思考。

- Thomas

---

这篇优秀的博客文章展示了如何在Mathematica中解决迷宫问题。将该方法翻译成Python不应该是个问题。 - Boris Gorelik

我已经更新了问题。如果我选择使用RGB三元组代替布尔值，存储是否仍然相同？矩阵大小为2400 * 1200。A*算法相比BFS对实际运行时间有显着影响吗？ - Whymarrh

@Whymarrh，位深度可以缩小以进行补偿。每像素2个比特应该足够了。 - Brian Cain

Answer 9

以下是使用R语言的解决方案。

### download the image, read it into R, converting to something we can play with...
library(jpeg)
url <- "https://istack.dev59.com/TqKCM.webp"
download.file(url, "./maze.jpg", mode = "wb")
jpg <- readJPEG("./maze.jpg")

### reshape array into data.frame
library(reshape2)
img3 <- melt(jpg, varnames = c("y","x","rgb"))
img3$rgb <- as.character(factor(img3$rgb, levels = c(1,2,3), labels=c("r","g","b")))

## split out rgb values into separate columns
img3 <- dcast(img3, x + y ~ rgb)

将RGB转换为灰度，参见：https://dev59.com/Zobca4cB1Zd3GeqPRRVN#27491947

# convert rgb to greyscale (0, 1)
img3$v <- img3$r*.21 + img3$g*.72 + img3$b*.07
# v: values closer to 1 are white, closer to 0 are black

## strategically fill in some border pixels so the solver doesn't "go around":
img3$v2 <- img3$v
img3[(img3$x == 300 | img3$x == 500) & (img3$y %in% c(0:23,988:1002)),"v2"]  = 0

# define some start/end point coordinates
pts_df <- data.frame(x = c(398, 399),
                     y = c(985, 26))

# set a reference value as the mean of the start and end point greyscale "v"s
ref_val <- mean(c(subset(img3, x==pts_df[1,1] & y==pts_df[1,2])$v,
                  subset(img3, x==pts_df[2,1] & y==pts_df[2,2])$v))

library(sp)
library(gdistance)
spdf3 <- SpatialPixelsDataFrame(points = img3[c("x","y")], data = img3["v2"])
r3 <- rasterFromXYZ(spdf3)

# transition layer defines a "conductance" function between any two points, and the number of connections (4 = Manhatten distances)
# x in the function represents the greyscale values ("v2") of two adjacent points (pixels), i.e., = (x1$v2, x2$v2)
# make function(x) encourages transitions between cells with small changes in greyscale compared to the reference values, such that: 
# when v2 is closer to 0 (black) = poor conductance
# when v2 is closer to 1 (white) = good conductance
tl3 <- transition(r3, function(x) (1/max( abs( (x/ref_val)-1 ) )^2)-1, 4) 

## get the shortest path between start, end points
sPath3 <- shortestPath(tl3, as.numeric(pts_df[1,]), as.numeric(pts_df[2,]), output = "SpatialLines")

## fortify for ggplot
sldf3 <- fortify(SpatialLinesDataFrame(sPath3, data = data.frame(ID = 1)))

# plot the image greyscale with start/end points (red) and shortest path (green)
ggplot(img3) +
  geom_raster(aes(x, y, fill=v2)) +
  scale_fill_continuous(high="white", low="black") +
  scale_y_reverse() +
  geom_point(data=pts_df, aes(x, y), color="red") +
  geom_path(data=sldf3, aes(x=long, y=lat), color="green")

看这里！

如果您不填写一些边框像素，就会发生这种情况（哈！）...

完全透明：在我找到这个问题之前，我自己提出并回答了一个非常类似的问题。然后通过SO的魔力，在相关问题中找到了这个问题之一。我想使用这个迷宫作为额外的测试用例...我很高兴地发现，我的答案也可以很少修改地适用于这个应用程序。

- Brian D

Answer 10

好的解决方案是，不要通过像素来查找邻居，而是通过单元格来完成，因为走廊可以有15个像素，所以在同一走廊中可以采取左或右的动作，而如果将位移视为立方体，则只需进行简单的上、下、左或右的操作。

- Johnny

---

你能否添加解决方案图和算法到答案中来证明你的观点？如果你能添加这些内容，那么对你的回答会有更大的支持力度，这样其他人就能更好地理解你的回答。 - Himanshu Bansal