代表和解决迷宫给出的图像
代表和解决迷宫给出图像的最佳方式是什么？
给出一个JPEG图像（如上所示），读入它的最佳方式是什么，将其解析为一些数据结构并解决迷宫问题？ 我的第一本能是以像素为单位读取图像并将其存储在布尔值列表（数组）中：对于白色像素为True ，对于非白色像素为False （可丢弃颜色）。 这种方法的问题是，图像可能不是“像素完美”。 我的意思是，如果在墙上某处有白色像素，它可能会产生一个无意的路径。
另一种方法（经过一番思考后找到了我）将图像转换为SVG文件 - 这是一个画布上绘制的路径列表。 这样，可以将路径读入相同类型的列表（布尔值），其中True表示路径或墙， False表示可行驶的空间。 如果转换不是100％准确的，并且没有完全连接所有的墙壁，则会产生这种方法的问题，从而产生空白。
转换为SVG的另一个问题是线条不是“完美”的直线。 这导致路径为三次贝塞尔曲线。 对于由整数索引的布尔值列表（数组），曲线不会轻易转移，曲线上的所有点必须计算，但不会完全匹配列表索引。
我认为，尽管这些方法中的一种可能起作用（尽管可能不是），但考虑到如此大的图像，它们可能效率低下，并且存在更好的方法。 这是如何最好（最有效和/或复杂性最低）？ 有没有最好的方法？
然后是解决迷宫。 如果我使用前两种方法中的任何一种，我将基本上最终得到一个矩阵。 根据这个答案，一个表示迷宫的好方法是使用树，解决问题的一个好方法是使用A *算法。 如何从图像创建一棵树？ 有任何想法吗？
TL; DR
最佳的解析方法？ 进入什么数据结构？ 上述结构将如何帮助/阻碍解决？
UPDATE
我试图用@Mhohail推荐的方式来实现@Mikhail使用numpy编写的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, [])
这是一个解决方案。
这里是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或其他方面实现它不应该有困难。
答案如下：
这个解决方案是用Python编写的。 感谢米哈伊尔在图像准备方面的指导。
动画广度优先搜索：
完成的迷宫：
#!/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搜索这个问题。 紧随其后的是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发布的图像启发）。 动画在主循环的10000次迭代后显示一个新帧。
广度优先搜索：
星级曼哈顿距离：
A-Star平方欧几里得距离：
A星曼哈顿距离乘以四：
结果显示，迷宫的探索区域在所使用的启发式方面差异很大。 因此，平方欧氏距离甚至产生与其他度量不同的（次优）路径。
关于A-Star算法在直到终止时的运行时间方面的性能，请注意，与广度优先搜索（BFS）相比，距离和成本函数的许多评估加起来只需要评估每个候选人位置。 这些额外的功能评估（A-Star）的成本是否超过了大量节点检查（BFS）的成本，特别是性能是否对您的应用而言是一个问题，这是个人感知的问题当然不能一般回答。
一般来说，与彻底搜索（例如BFS）相比，知情搜索算法（如A-Star）可能是更好的选择，下面是一个可以说的事情。 随着迷宫的维数，即搜索树的分支因子，穷举搜索（穷举搜索）的缺点呈指数增长。 随着复杂性的增加，这样做变得越来越不可行，并且在某些情况下，您对任何结果路径都非常满意，无论是（大约）最优与否。
链接地址: http://www.djcxy.com/p/13967.html