如何用程序解图片迷宫?


 英文原文:Representing and solving a maze given an image  译注:原文是 StackOverflow 上一个如何用程序读取迷宫图片并求解的问题,几位参与者热烈地讨论并给出了自己的...

 英文原文:Representing and solving a maze given an image

  译注:原文是 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 代码:

这是个简单的实现,应该很容易就能够改写为 Python 或其他语言,下面是程序的运行结果:

提问者更新:

  我用 Python 实现了一下 Mikhail 的方法,其中用到了 numpy 库,感谢 Thomas 推荐。我感觉这个算法是正确的,但是效果不太如预期,以下是相关代码,使用了 PyPNG 库处理图片。

  译注:很遗憾,我用提问者提供的代码并没有跑通程序,并且似乎代码缩进有点问题,而下面其他参与者的代码能够执行通过,并且效果很好。

标签:

相关资讯

7款HTML5精美应用教程 让你立即爱上HTML5

7款HTML5精美应用教程 让你立即爱上HTML5

你喜欢HTML5吗?我想下面的这7个HTML5应用一定会让你爱上HTML5的,不信就一起来看看吧。1、HTML5/jQuery雷达动画图表 图表配置十分简单之前我们介绍过不少形形色色的HTML5图表

html标签的语义化之搜索引擎优化

为了使我们的网站更好的被搜索引擎抓取收录,更自然的获得更高的流量,网站标签的语义化就显得尤为重要。所谓标签语义化,就是指标签的含义。为了更好的理解标签的语义化,先看下面

HTML5体验改进的14条军规

来自公园《HTML5——用新方式创造更好的用户体验》线下活动中来自火速轻应用的技术总监胡敏东的分享。 1. fake 页 - 首屏加速目标:首屏 3s 以内 因为 71% 的用户期望移动页

HTML head 头标签

HTML head 头部分的标签、元素有很多,涉及到浏览器对网页的渲染,SEO 等等,而各个浏览器内核以及各个国内浏览器厂商都有些自己的标签元素,这就造成了很多差异性。移动互联网时

将HTML5封装成android应用APK文件的几种方法

越来越多的开发者热衷于使用html5+JavaScript开发移动Web App。不过,HTML5 Web APP的出现能否在未来取代移动应用,就目前来说,还是个未知数。一方面,用户在使用习惯上,不喜欢在浏

HTML5里的placeholder属性

HTML5里的placeholder属性

HTML5里新引入很多有趣的新特征;有些体现在HTML里,有些是JavaScript API,全部非常的有用。其中我最喜欢的一个特征就是文本框(INPUT)里的placeholder属性。placeholder

HTML5 Canvas中绘制矩形实例教程

HTML5 Canvas中绘制矩形实例教程

本文翻译自Steve Fulton & Jeff Fulton HTML5 Canvas, Chapter 2, “The Basic Rectangle Shape”. 让我们来看一下Canvas内置的简单几何图形 — 矩形的绘制。在Canvas中,

7种炫酷HTML5 SVG液态水滴融合动画特效

7种炫酷HTML5 SVG液态水滴融合动画特效

这是一组使用HTML5 SVG过滤器制作的炫酷液态水滴融合动画特效。这些SVG动画特效使一些HTML元素,如菜单、分页按钮、APP、选择框等元素的过渡动画像几粒水滴一样融合分解,效果

绘制SVG内容到Canvas的HTML5应用

绘制SVG内容到Canvas的HTML5应用

SVG与Canvas是HTML5上绘制图形应用的两种完全不同模式的技术,两种绘制图形方式各有优缺点,但两者并非水火不容,尤其是SVG内容可直接绘制在Canvas上的功能,使得两者可以完美的融

PHP结合HTML5使用FormData对象提交表单及上传图片

PHP结合HTML5使用FormData对象提交表单及上传图片

FormData 对象,可以把form中所有表单元素的name与value组成一个queryString,提交到后台。在使用Ajax提交时,使用FormData对象可以减少拼接queryString的工作量。 使用Form