给出一个图像来表示和解决一个迷宫

在给定的图像中，表现和解决迷宫的最佳方法是什么?

The Scope第134期封面图片

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

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

转换为SVG的另一个问题是，这些线不是“完全”直的。这导致路径是三次贝塞尔曲线。对于一个由整数索引的布尔值列表(数组)，曲线将不容易转移，并且曲线上的所有点都必须计算，但不会与列表索引完全匹配。

我认为，虽然这些方法中的一种可能有效(虽然可能不是)，但对于如此大的图像，它们的效率非常低，并且存在更好的方法。如何才能做到最好(最有效和/或最简单)?有没有最好的办法?

然后是迷宫的解决。如果我用前两种方法中的任何一种，我最终都会得到一个矩阵。根据这个答案，表示迷宫的好方法是使用树，解决它的好方法是使用A *算法。如何从图像中创建树?什么好主意吗?

< p > 博士TL; < br > 最好的解析方法?转换成什么样的数据结构?结构如何帮助/阻碍解决问题?< / p > < p > 更新 < br > 我已经尝试了@Mikhail用Python写的东西，使用numpy，正如@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, [])
63484 次浏览
小开

我会选择矩阵-布尔斯。如果你发现标准的Python列表在这方面效率太低，你可以使用numpy.bool数组来代替。一个1000x1000像素的迷宫的存储空间只有1mb。

不要费心创建任何树或图数据结构。这只是思考它的一种方式，但不一定是在记忆中表示它的好方法;布尔矩阵更容易编码，效率更高。

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

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

如果你发现它仍然太慢，你可以在加载它之前尝试缩小图像的比例。小心不要在这个过程中丢失任何狭窄的路径。

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

小开
最佳答案

这里有一个解决方案。

  1. 将图像转换为灰度(尚未二进制)，调整颜色的权重，使最终的灰度图像近似均匀。你可以简单地通过在Photoshop中控制图像->调整->黑色&白色
  2. 通过在Photoshop中image -> adjustment -> threshold设置适当的阈值将图像转换为二进制。
  3. 确保阈值选择正确。使用魔棒工具，零公差，点采样，连续，无抗锯齿。检查选择断线处的边不是由错误阈值引入的假边。事实上，这个迷宫的所有内部点从一开始就可以进入。
  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或其他地方实现它不应该有困难。

这就是答案:

Enter image description here

小开

使用队列进行阈值连续填充。将入口左侧的像素推入队列，然后开始循环。如果一个排队的像素足够暗，它就被显示为浅灰色(高于阈值)，并且所有的邻居都被推到队列上。

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

解决方案是灰色墙和彩色墙之间的走廊。注意这个迷宫有多种解决方案。而且，这只是看起来有效。

Solution

小开

树搜索太多了。迷宫在解的路径上本质上是可分离的。

(感谢Reddit的rainman002为我指出了这一点。)

正因为如此，你可以快速使用连接组件来识别迷宫墙壁的连接部分。这将在像素上迭代两次。

如果您希望将其转换为解决方案路径的漂亮图表，那么您可以使用带有结构化元素的二进制操作来填充每个连接区域的“死胡同”路径。

下面是MATLAB的演示代码。它可以通过调整来更好地清理结果，使其更一般化，并使其运行得更快。(不是凌晨两点半的时候)

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

result of current code .

小开

这里有一些想法。

（1. 图像处理:)

1.1加载图像为RGB像素映射。在c#中，使用system.drawing.bitmap是很简单的。在不支持简单成像的语言中，只需将图像转换为便携式像素图格式 (PPM)(一种Unix文本表示，产生大文件)或一些容易读取的简单二进制文件格式，如骨形态发生蛋白或矫正性大动脉转位。Unix中的ImageMagick或Windows中的IrfanView。

1.2如前所述，您可以将数据简化，将每个像素的(R+G+B)/3作为灰度调的指标，然后将其阈值设置为黑白表。假设0=黑，255=白，那么接近200的值就可以去掉JPEG工件。

(2)。解决方案:)

2.1深度优先搜索:初始化一个空堆栈起始位置，收集可用的后续移动，随机选择一个并推入堆栈，直到到达终点或死角。在通过弹出堆栈的死胡同回溯中，你需要跟踪地图上访问的位置，这样当你收集可用的移动时，你就不会重复相同的路径。制作动画很有趣。

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

2.3墙的追随者:从几何上讲，迷宫是一个折叠/弯曲的管子。如果你把手放在墙上，你最终会找到出口。这并不总是有效。有一些假设关于:完美的迷宫，等等，例如，某些迷宫包含岛屿。一定要查一下;这很吸引人。

(3)。评论:)

这是一个棘手的问题。如果用一些简单的数组形式表示，每个元素都是一个单元格类型，有北、东、南、西墙壁和一个访问的旗帜字段，那么解决迷宫就很容易。然而，考虑到你正在尝试这样做，给出一个手绘草图，它变得混乱。老实说，我认为试图合理化这幅素描会让你发疯。这类似于相当复杂的计算机视觉问题。也许直接进入图像映射可能更容易，但更浪费。

小开

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

一个动画宽度优先搜索:

动画版的BFS

完成的迷宫:

Completed Maze

#!/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-Star搜索来解决这个问题。紧随其后的是框架的约瑟夫·克恩实现和给定的算法伪代码在这里:

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邻域的网格上两点之间的直线距离。(在这种情况下，这不会高估成本。)

然而，这大大低估了现有迷宫的实际成本。因此，我添加了另外两个距离度量的平方欧几里得距离和曼哈顿距离乘以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])

下面是一些可视化结果的图片(灵感来自约瑟夫·克恩发布的图片)。每次主while循环迭代10000次后，动画都会显示一个新帧。

广度优先搜索:

广度优先搜索

a星曼哈顿距离:

A-Star Manhattan Distance

a星平方欧几里得距离:

a星平方欧几里得距离

a星曼哈顿距离乘以4:

A-Star曼哈顿距离乘以4

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

关于a - star算法从运行时间到终止的性能，请注意，与只需要评估每个候选职位的“目标度”的广度优先搜索(width - first Search, BFS)相比，a - star算法对距离和代价函数的评估加起来很多。这些额外的函数评估(a - star)的成本是否超过了检查大量节点的成本(BFS)，特别是性能对应用程序来说是否是个问题，这是个人的看法，当然不能一般地回答。

可以一般来说，关于一个知情的搜索算法(如A- star)是否比穷尽搜索(如BFS)更好的选择，如下所示。随着迷宫的维数，即搜索树的分支因子，穷尽搜索(穷尽搜索)的缺点呈指数增长。随着复杂性的增长，这样做变得越来越不可行，在某些时候，你对任何结果路径非常满意，不管它(大约)是否是最优的。

小开

maze-solver-python (GitHub)

enter image description here

我玩得很开心，并扩展了约瑟夫·克恩的答案。不要贬低它;我只是为其他人做了一些小的补充，谁可能有兴趣玩这个。

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

  1. 图像在搜索(即。转换为纯黑色&白色)
  2. 自动生成GIF。
  3. 自动生成AVI。

就目前情况而言，这个示例迷宫的开始/结束点是硬编码的，但我计划扩展它，以便您可以选择适当的像素。

小开

这是一个用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")

瞧!

solution that correct found shortest path .

这就是如果你不填充一些边界像素会发生的事情(哈!)…

solution version where the solver goes around the maze .

完全披露:在我找到这个之前，我问并回答了一个非常类似的问题的问题。然后通过SO的魔法，发现这是其中一个顶部的“相关问题”。我想我可以用这个迷宫作为一个额外的测试案例……我很高兴地发现，我的答案也适用于这个应用程序，只需要很少的修改。

小开

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


提交答案