给定图像表示和解决迷宫 [英] Representing and solving a maze given an image

问题描述

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

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

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

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

我认为虽然其中一种方法可能有效(尽管可能无效)，但鉴于如此大的图像，它们的效率非常低，并且存在更好的方法.这是如何最好(最有效和/或最不复杂)完成的?有没有最好的方法?

然后是迷宫的解决.如果我使用前两种方法中的任何一种，我基本上都会得到一个矩阵.根据

What is the best way to represent and solve a maze given an image?

Given an JPEG image (as seen above), what's the best way to read it in, parse it into some data structure and solve the maze? My first instinct is to read the image in pixel by pixel and store it in a list (array) of boolean values: True for a white pixel, and False for a non-white pixel (the colours can be discarded). The issue with this method, is that the image may not be "pixel perfect". By that I simply mean that if there is a white pixel somewhere on a wall it may create an unintended path.

Another method (which came to me after a bit of thought) is to convert the image to an SVG file - which is a list of paths drawn on a canvas. This way, the paths could be read into the same sort of list (boolean values) where True indicates a path or wall, False indicating a travel-able space. An issue with this method arises if the conversion is not 100% accurate, and does not fully connect all of the walls, creating gaps.

Also an issue with converting to SVG is that the lines are not "perfectly" straight. This results in the paths being cubic bezier curves. With a list (array) of boolean values indexed by integers, the curves would not transfer easily, and all the points that line on the curve would have to be calculated, but won't exactly match to list indices.

I assume that while one of these methods may work (though probably not) that they are woefully inefficient given such a large image, and that there exists a better way. How is this best (most efficiently and/or with the least complexity) done? Is there even a best way?

Then comes the solving of the maze. If I use either of the first two methods, I will essentially end up with a matrix. According to this answer, a good way to represent a maze is using a tree, and a good way to solve it is using the A* algorithm. How would one create a tree from the image? Any ideas?

TL;DR
Best way to parse? Into what data structure? How would said structure help/hinder solving?

UPDATE
I've tried my hand at implementing what @Mikhail has written in Python, using numpy, as @Thomas recommended. I feel that the algorithm is correct, but it's not working as hoped. (Code below.) The PNG library is 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, [])

解决方案

Here is a solution.

1. Convert image to grayscale (not yet binary), adjusting weights for the colors so that final grayscale image is approximately uniform. You can do it simply by controlling sliders in Photoshop in Image -> Adjustments -> Black & White.
2. Convert image to binary by setting appropriate threshold in Photoshop in Image -> Adjustments -> Threshold.
3. Make sure threshold is selected right. Use the Magic Wand Tool with 0 tolerance, point sample, contiguous, no anti-aliasing. Check that edges at which selection breaks are not false edges introduced by wrong threshold. In fact, all interior points of this maze are accessible from the start.
4. Add artificial borders on the maze to make sure virtual traveler will not walk around it :)
5. Implement breadth-first search (BFS) in your favorite language and run it from the start. I prefer MATLAB for this task. As @Thomas already mentioned, there is no need to mess with regular representation of graphs. You can work with binarized image directly.

Here is the MATLAB code for BFS:

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

It is really very simple and standard, there should not be difficulties on implementing this in Python or whatever.

And here is the answer:

这篇关于给定图像表示和解决迷宫的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！