python - 表示和解决给定图像的迷宫

Question

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

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

另一种方法（经过一番思考后想到）是将图像转换为 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, [])

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或其他方式实现它应该没有困难。

这是答案：

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

注意：将访问过的白色像素标记为灰色。这消除了对访问列表的需要，但这需要在绘制路径之前从磁盘第二次加载图像文件（如果您不想要最终路径和所有路径的合成图像）。

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

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 是一种启发式搜索算法，您需要提出一个函数来估计达到目标之前的剩余成本（此处为：距离）。除非您对次优解决方案感到满意，否则不应高估成本。此处保守的选择是曼哈顿（或出租车）距离，因为它表示所用冯诺依曼邻域的网格上两点之间的直线距离。（在这种情况下，永远不会高估成本。）

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

这是代码：

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 星平方欧几里得距离：

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

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

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

关于与穷举搜索（例如，BFS）相比，明智的搜索算法（例如A -Star）是否是更好的选择，一般可以说如下。随着迷宫的维数，即搜索树的分支因子，穷举搜索（穷举搜索）的劣势呈指数增长。随着复杂性的增加，这样做变得越来越不可行，并且在某些时候，您对任何结果路径都非常满意，无论它（大约）最优与否。

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

Answer 5

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

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

解决方案是灰墙和彩墙之间的走廊。请注意，这个迷宫有多种解决方案。此外，这似乎只是工作。

Answer 6

给你：maze-solver-python (GitHub)

我玩得很开心，并扩展了Joseph Kern的回答。不减损它；我只是为其他可能有兴趣玩这个的人做了一些小的补充。

这是一个基于 python 的求解器，它使用 BFS 来查找最短路径。我当时的主要补充是：

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

就目前而言，此示例迷宫的起点/终点是硬编码的，但我计划对其进行扩展，以便您可以选择适当的像素。

Answer 7

我会选择矩阵的布尔选项。如果您发现标准 Python 列表对此效率太低，您可以使用numpy.bool数组来代替。1000x1000 像素迷宫的存储空间仅为 1 MB。

不要为创建任何树或图形数据结构而烦恼。这只是一种思考方式，但不一定是在内存中表示它的好方法；布尔矩阵既更容易编码，也更高效。

然后用A*算法求解。对于距离启发式，使用曼哈顿距离 ( distance_x + distance_y)。

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

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

也许也可以在 Python 中进行 1:2 的缩小，检查您实际上没有丢失任何可能的路径。一个有趣的选择，但它需要更多的思考。

Answer 8

这里有一些想法。

（1.图像处理：）

1.1 将图像加载为RGB像素图。在C#中，使用system.drawing.bitmap. 在没有简单的图像支持的语言中，只需将图像转换为可 移植像素图格式(PPM)（一种 Unix 文本表示，生成大文件）或一些您可以轻松阅读的简单二进制文件格式，例如BMP或TGA。Unix中的ImageMagick或 Windows 中的IrfanView。

1.2 如前所述，您可以通过将每个像素的（R+G+B）/3 作为灰度的指标来简化数据，然后对该值进行阈值化以生成黑白表。假设 0=black 和 255=white，接近 200 的值将消除 JPEG 伪影。

（2.解决方案：）

2.1 深度优先搜索：用起始位置初始化一个空栈，收集可用的后续移动，随机选择一个并推入栈，直到到达终点或死胡同。在通过弹出堆栈进行死路回溯时，您需要跟踪地图上访问了哪些位置，因此当您收集可用移动时，您永远不会两次走同一条路径。动画非常有趣。

2.2 广度优先搜索：前面提到过，和上面类似，只是使用了队列。动画也很有趣。这就像图像编辑软件中的洪水填充一样。我认为您可以使用此技巧在 Photoshop 中解决迷宫问题。

2.3 Wall Follower：从几何上讲，迷宫是一个折叠/回旋的管子。如果您将手放在墙上，您最终会找到出口；）这并不总是有效。有一定的假设：完美的迷宫等，例如，某些迷宫包含岛屿。一定要查一下；这很迷人。

（3.评论：）

这是一个棘手的问题。如果用一些简单的数组形式表示，则很容易解决迷宫，每个元素都是具有北、东、南和西墙的单元类型和一个已访问的标志字段。但是，鉴于您正在尝试使用手绘草图来执行此操作，它会变得混乱。老实说，我认为试图使草图合理化会让你发疯。这类似于相当复杂的计算机视觉问题。也许直接进入图像地图可能更容易但更浪费。

Answer 9

这是使用 R 的解决方案。

### download the image, read it into R, converting to something we can play with...
library(jpeg)
url <- "https://i.stack.imgur.com/TqKCM.jpg"
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 ://stackoverflow.com/a/27491947/2371031

# 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 的魔力，发现这个问题是最热门的“相关问题”之一。我想我会用这个迷宫作为一个额外的测试用例......我很高兴地发现我的答案也适用于这个应用程序，只需要很少的修改。

Answer 10

好的解决方案是，不是按像素查找邻居，而是按单元格来完成，因为走廊可以有 15px，所以在同一个走廊中，它可以采取左或右等动作，而如果它是按照位移来完成的是一个立方体，它会是一个简单的动作，比如向上、向下、向左或向右