译注：原文是StackOverflow上一个如何用程序读取迷宫图片并求解的问题，几位参与者热烈地讨论并给出了自己的代码，涉及到用Python对图片的处理以及广度优先(BFS)算法等。
问题by Whymarrh：
当给定上面那样一张JPEG图片，如何才能更好地将这张图转换为合适的数据结构并且解出这个迷宫？
我的第一直觉是将这张图按像素逐个读入，并存储在一个包含布尔类型元素的列表或数组中，其中True代表白色像素，False代表非白色像素（或彩色可以被处理成二值图像）。但是这种做法存在一个问题，那就是给定的图片往往并不能完美的“像素化”。考虑到如果因为图片转换的原因，某个非预期的白色像素出现在迷宫的墙上，那么就可能会创造出一一条非预期的路径。
经过思考之后，我想出了另一种方法：首先将图片转换为一个可缩放适量图形(SVG)文件，这个文件由一个画布上的矢量线条列表组成，矢量线条按照列表的顺序读取，读取出的仍是布尔值：其中True表示墙，而False表示可通过的区域。但是这种方法如果无法保证图像能够做到百分之百的精确转换，尤其是如果不能将墙完全准确的连接，那么这个迷宫就可能出现裂缝。
图像转换为SVG的另一个问题是，线条并不是完美的直线。因为SVG的线条是三次贝塞尔曲线，而使用整数索引的布尔值列表增加了曲线转换的难度，迷宫线条上的所有点在曲线上都必须经过计算，但不一定能够完美对应列表中的索引值。
假设以上方法的确可以实现(虽然很可能都不行)，但当给定一张很大的图像时，它们还是不能胜任。那么是否存在一种更好地方法能够平衡效率和复杂度？
这就要讨论到如何解迷宫了。如果我使用以上两种方法中的任意一种，我最终将会得到一个矩阵。而根据这个问答(http://stackoverflow.com/questions/3097556/programming-theory-solve-a-maze/3097677#3097677)，一个比较好的迷宫表示方式应该是使用树的结构，并且使用A*搜索算法来解迷宫。那么如何从迷宫图片中构造出迷宫树呢？有比较好的方法么？
以上废话太多，总结起来问题就是：如何转换迷宫图片？转换成为什么样的数据结构？采用什么样的数据结构能够帮助或阻碍解迷宫？
回答by Mikhail:
这是我的解决方案：
1. 将图片转换为灰度图像(不是直接二值)，调整不同颜色的权重使得最终的灰度看起来比较统一，你可以通过简单地调节Photoshop 图像->调整->黑白 菜单中的控制条来实现。
2. 将上一步得到的灰度图片转换为二值图片，可以通过在PS 图像->调整->阈值 菜单中设定适当的阈值来实现
3. 确保正确设置了阈值。使用魔棒工具(参数设置：容差 0、取样点、连续以及消除锯齿)选择空白区域，检查所选区域的边缘不是因为错误的阈值设置而产生的假边缘。事实上，这个迷宫中从start到end应该由联通的空白区域。
4. 人为地在迷宫外部加上边界，确保迷宫漫游者^_^不会从start绕着迷宫跑到终点。:)
5. 选择语言实现广度优先搜索算法(BFS)，从start处开始让程序运行。下面的代码我选择用Matlab实现。正如Thomas提到的，没必要纠结于图像的表示形式，你可以直接在二值图像上运行。
以下是用MATLAB实现的BFS代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
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实现了一下Mikhail的方法，其中用到了numpy库，感谢Thomas推荐。我感觉这个算法是正确的，但是效果不太如预期，以下是相关代码，使用了PyPNG库处理图片。
译注：很遗憾，我用提问者提供的代码并没有跑通程序，并且似乎代码缩进有点问题，而下面其他参与者的代码能够执行通过，并且效果很好。
|
1 2 3 4 5 6 7 8 9 1-given-an-image">StackOverflow。欢迎加入翻译组。 译注：原文是StackOverflow上一个如何用程序读取迷宫图片并求解的问题，几位参与者热烈地讨论并给出了自己的代码，涉及到用Python对图片的处理以及广度优先(BFS)算法等。
问题by Whymarrh：
当给定上面那样一张JPEG图片，如何才能更好地将这张图转换为合适的数据结构并且解出这个迷宫？ 我的第一直觉是将这张图按像素逐个读入，并存储在一个包含布尔类型元素的列表或数组中，其中True代表白色像素，False代表非白色像素（或彩色可以被处理成二值图像）。但是这种做法存在一个问题，那就是给定的图片往往并不能完美的“像素化”。考虑到如果因为图片转换的原因，某个非预期的白色像素出现在迷宫的墙上，那么就可能会创造出一一条非预期的路径。 经过思考之后，我想出了另一种方法：首先将图片转换为一个可缩放适量图形(SVG)文件，这个文件由一个画布上的矢量线条列表组成，矢量线条按照列表的顺序读取，读取出的仍是布尔值：其中True表示墙，而False表示可通过的区域。但是这种方法如果无法保证图像能够做到百分之百的精确转换，尤其是如果不能将墙完全准确的连接，那么这个迷宫就可能出现裂缝。 图像转换为SVG的另一个问题是，线条并不是完美的直线。因为SVG的线条是三次贝塞尔曲线，而使用整数索引的布尔值列表增加了曲线转换的难度，迷宫线条上的所有点在曲线上都必须经过计算，但不一定能够完美对应列表中的索引值。 假设以上方法的确可以实现(虽然很可能都不行)，但当给定一张很大的图像时，它们还是不能胜任。那么是否存在一种更好地方法能够平衡效率和复杂度？ 这就要讨论到如何解迷宫了。如果我使用以上两种方法中的任意一种，我最终将会得到一个矩阵。而根据这个问答(http://stackoverflow.com/questions/3097556/programming-theory-solve-a-maze/3097677#3097677)，一个比较好的迷宫表示方式应该是使用树的结构，并且使用A*搜索算法来解迷宫。那么如何从迷宫图片中构造出迷宫树呢？有比较好的方法么？ 以上废话太多，总结起来问题就是：如何转换迷宫图片？转换成为什么样的数据结构？采用什么样的数据结构能够帮助或阻碍解迷宫？
回答by Mikhail: 这是我的解决方案： 1. 将图片转换为灰度图像(不是直接二值)，调整不同颜色的权重使得最终的灰度看起来比较统一，你可以通过简单地调节Photoshop 图像->调整->黑白 菜单中的控制条来实现。 以下是用MATLAB实现的BFS代码：
这是个简单的实现，应该很容易就能够改写为Python或其他语言，下面是程序的运行结果：
提问者更新： 我用Python实现了一下Mikhail的方法，其中用到了numpy库，感谢Thomas推荐。我感觉这个算法是正确的，但是效果不太如预期，以下是相关代码，使用了PyPNG库处理图片。 译注：很遗憾，我用提问者提供的代码并没有跑通程序，并且似乎代码缩进有点问题，而下面其他参与者的代码能够执行通过，并且效果很好。 |
