代表和解决给定图像的迷宫

Question

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

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

另一种方法(经过深思熟虑后来找我)是将图像转换为SVG文件 - 这是在画布上绘制的路径列表.这样,路径可以被读入相同类型的列表(布尔值),其中True指示路径或墙,False指示可行进空间.如果转换不是100%准确,并且未完全连接所有墙壁,从而产生间隙,则会出现此方法的问题.

转换为SVG的另一个问题是线条不是"完美"直线.这导致路径是立方贝塞尔曲线.使用由整数索引的布尔值列表(数组),曲线不会轻易转移,并且必须计算曲线上所有的点,但不会与列表索引完全匹配.

我假设虽然这些方法中的一种可能有用(尽管可能不是),但鉴于这么大的图像,它们的效率非常低,并且存在更好的方法.如何最好(最有效和/或最简单)完成？有没有最好的方法？

然后是迷宫的解决方案.如果我使用前两种方法中的任何一种,我基本上会得到一个矩阵.根据这个答案,表示迷宫的好方法是使用树,解决它的好方法是使用A*算法.如何从图像中创建树？有任何想法吗？

TL; DR
最好的解析方法？进入什么数据结构？该结构将如何帮助/阻碍解决？

更新
我已经尝试过实现@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, [])

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搜索这个问题.紧随其后的是实施约瑟夫·克恩的框架,并给出了算法的伪代码在这里:

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

然而,这将显着低估手头给定迷宫的实际成本.因此,我添加了另外两个距离度量平方欧氏距离和曼哈顿距离乘以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发布的图像).动画在主要while循环的10000次迭代之后显示每个新帧.

广度优先搜索:

A-Star曼哈顿距离:

A-Star Squared欧几里德距离:

A-Star Manhattan Distance乘以4:

结果表明,对于所使用的启发式方法,迷宫的探索区域差异很大.因此,平方欧几里德距离甚至产生与其他度量不同的(次优的)路径.

关于A-Star算法在运行时直到终止的性能,请注意,与广度优先搜索(BFS)相比,大量的距离和成本函数评估总和需要评估"目标性".每个候选人职位.这些额外功能评估(A-Star)的成本是否超过了大量要检查的节点(BFS)的成本,特别是性能是否对您的应用程序来说是一个问题,是个人感知的问题当然不能得到普遍回答.

一件事,可以比穷举搜索(例如,BFS)是依照一般约是否知情搜索算法(如A-星)说可能是更好的选择.利用迷宫的维数,即搜索树的分支因子,穷举搜索(穷举搜索)的缺点呈指数增长.随着复杂性的增加,这样做变得越来越不可行,并且在某些时候,您对任何结果路径都非常满意,无论是(近似)最优还是不是.

Answer 4

树搜索太多了.迷宫沿着溶液路径固有地是可分离的.

(感谢Reddit的rainman002指出这个问题.)

因此,您可以快速使用连接的组件来识别迷宫墙的连接部分.这会迭代像素两次.

如果要将其转换为解决方案路径的漂亮图表,则可以使用带结构元素的二元运算来填充每个连接区域的"死胡同"路径.

下面是MATLAB的演示代码.它可以使用tweaking来更好地清理结果,使其更具通用性,并使其运行更快.(有时候不是凌晨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)

我玩得很开心,延伸到约瑟夫克恩的回答.不要减损它; 我只是为其他可能有兴趣玩这个的人做了一些小的补充.

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

1. 在搜索之前清理图像(即转换为纯黑色和白色)
2. 自动生成GIF.
3. 自动生成AVI.

就目前而言,这个样本迷宫的起点/终点是硬编码的,但我计划扩展它,以便你可以选择合适的像素.

Answer 7

我会去找bools矩阵选项.如果您发现标准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 =黑色且255 =白色,接近200的东西将取出JPEG伪像.

(2.解决方案:)

2.1深度优先搜索:初始化具有起始位置的空堆栈,收集可用的后续移动,随机选择一个并推入堆栈,继续直到达到结束或去除.在通过弹出堆栈进行后退回溯时,您需要跟踪地图上访问的位置,这样当您收集可用的移动时,您永远不会两次使用相同的路径.动画非常有趣.

2.2广度优先搜索:之前提到过,类似于上面但仅使用队列.动画也很有趣.这类似于图像编辑软件中的泛洪填充.我想你可以使用这个技巧在Photoshop中解决迷宫问题.

2.3墙跟随器:从几何学上讲,迷宫是折叠/旋绕管.如果你把手放在墙上,你最终会找到出口;)这并不总是有效.有一定的假设:完美的迷宫等,例如,某些迷宫包含岛屿.看一看; 这很有意思.

(3.评论:)

这是棘手的.如果以一些简单的数组形式表示,很容易解决迷宫,每个元素是具有北,东,南和西墙和访问标志字段的单元类型.但是考虑到你试图用手绘草图来做这件事,它会变得混乱.老实说,我认为试图使草图合理化会让你疯狂.这类似于相当复杂的计算机视觉问题.也许直接进入图像地图可能更容易,但更浪费.