再presenting和解决迷宫给定的图像 [英] Representing and solving a maze given an image
问题描述
什么是重新present解决给定的图像迷宫的最好方法是什么？
给定一个JPEG图像（如上所示），什么是在读它，分析它到一些数据结构和解决迷宫的最好方法是什么？我的第一直觉是像素读取像素的图像，并将其存储在布尔值的列表（数组）：真一个白色像素，而假一个非白色像素（颜色可以被丢弃）。这种方法的问题，是图像可能不是像素完美。我这样说只是意味着，如果有一个白色像素某处墙壁上可能会产生不路径。
的另一种方法（该来找我一点思想之后）是将图像转换为SVG文件 - 这是绘制在画布上的路径列表。通过这种方式，路径可以被理解成同样的排序列表（布尔值），其中真表示一个路径或墙壁，假表示旅行能空间。用这种方法的一个问题产生，如果转换不100％的准确，并没有完全连接所有的壁，产生间隙。
另外一个问题转换为SVG是该行没有完全直。这将导致被三次Bezier曲线的路径。与由整数索引的布尔值的列表（阵列）中，曲线将不会轻易转移，并且所有该行的曲线上的点必须被计算的，但不会完全匹配列出索引
我认为，虽然这些方法之一可能工作（虽然可能不是），他们是可悲的低效给出了这样一个大的图像，并且存在一个更好的办法。这是如何最好（最有效和/或与至少复杂性）做了什么？有没有连最好的方法是什么？
然后就是迷宫的求解。如果我用前两种方法，我将从根本上结束了一个矩阵。根据这个答案，一个很好的方式重新present迷宫是用一棵树，一个好办法解决这个问题是使用 A *算法。如何将一个从该映像创建一棵树？任何想法？
TL; DR
最好的方法来分析？成什么数据结构？如何将所述结构帮助/阻碍解决？
更新
我已经尽我的手在执行什么@Mikhail已经用Python编写的，使用 numpy的，因为@Thomas建议。我觉得这个算法是正确的，但它不工作的希望。 （以下code）的PNG库 PyPNG 。
导入PNG，numpy的，队列，运营商，itertools
高清is_white（坐标，图像）：
返回是否（X，Y）是大约一个白象素
A =真
对我的xrange（3）：
如果不是：休息
一个图象= [坐标[1]] [坐标[0] * 3 + I]≥ 240
返回
高清BFS（S，E，I，走访了）：
执行广度优先搜索。
边境= Queue.Queue（）
而S =Ë！
当d在[（-1，0），（0，-1），（1，0），（0，1）]：
NP =元组（图（operator.add，S，D））
如果is_white（NP，i）和NP不是在访问了：
frontier.put（NP）
visited.append（多个）
S = frontier.get（）
返回参观
高清的main（）：
R = png.Reader（文件名=thescope-134.png）
行，COLS，像素，元= r.asDirect（）
断言元['飞机'] == 3＃确保文件是RGB
image2d = numpy.vstack（itertools.imap（numpy.uint8，像素））
开始，结束=（402，985），（398，27）
打印BFS（开始，结束，image2d，[]）
下面是一个解决方案。
- 图像转换为灰度（尚未二进制），调整权重的颜色，使最终的灰度图像近似均匀。你可以简单地通过控制滑块在Photoshop中图片做 - >调整 - >黑与放大器;白色。
- 图像转换为二进制通过设置适当的阈值在Photoshop中的图像 - >调整 - >阈值
- 确保阈值选择权。使用魔术棒工具0宽容，点样，连续的，无抗锯齿。检查边缘处选择休息是不是错了门槛引进虚假的边缘。事实上，这个迷宫中所有的内部点是从一开始就进行访问。
- 添加人工边界上的迷宫，以确保虚拟旅客不会在其周围散步：）
- 实施广度优先搜索（BFS）在你最喜欢的语言，并从一开始就运行它。我preFER MATLAB 完成这个任务。正如@Thomas已经提到的，没有必要惹图的定期重presentation。您可以直接与二值图像的工作。
下面是MATLAB $ C $下BFS：
函数路径= solve_maze（img_file）
%%初始化数据
IMG = imread（img_file）;
IMG = rgb2gray（IMG）;
迷宫= IMG＆GT; 0;
启动= [985 398];
完成= [26 399];
%%初始化BFS
N = numel（迷宫）;
Q =零（N，2）;
M =零（[尺寸（迷宫）2]）;
前面= 0;
背面= 1;
功能推（P，D）
Q = P + D组;
如果迷宫（Q（1），Q（2））及和放大器; M（Q（1）中，q（2），1）== 0
前=前+ 1;
Q（前，:) = Q;
M（Q（1）中，q（2），:) =重塑（对，[1 1 2]）;
结束
结束
推（启动，[0]）;
D = [0 1; 0 -1; 1 0; -1 0];
%%运行BFS
前阵子＆LT; =前
P = Q（回，:);
背背= + 1;
对于i = 1：4
推（P，D（I，:)）;
结束
结束
%%提取路径
PATH =完成;
而真正的
Q =路径（结束，:);
p值=重塑（M（Q（1）中，q（2），:)，1，2）;
路径（结束+ 1，:) = P;
如果ISEQUAL（P，开始）
打破;
结束
结束
结束
这真的是很简单的标准，不应该有在 Python中实现此或困难无论什么。
而这里就是答案：
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.
- 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.
- Convert image to binary by setting appropriate threshold in Photoshop in Image -> Adjustments -> Threshold.
- 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.
- Add artificial borders on the maze to make sure virtual traveler will not walk around it :)
- 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:
这篇关于再presenting和解决迷宫给定的图像的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
