用Python代码来解图片迷宫的方法整理

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

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, <img src="http://python.jobbole.com/wp-includes/images/smilies/icon_smile.gif" alt=":)" class="wp-smiley"> = q;
   M(q(1), q(2), <img src="http://python.jobbole.com/wp-includes/images/smilies/icon_smile.gif" alt=":)" class="wp-smiley"> = 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, <img src="http://python.jobbole.com/wp-includes/images/smilies/icon_smile.gif" alt=":)" class="wp-smiley"> ;
  back = back + 1;
  for i = 1:4
   push(p, d(i, <img src="http://python.jobbole.com/wp-includes/images/smilies/icon_smile.gif" alt=":)" class="wp-smiley"> );
  end
 end

 %% Extracting path
 path = finish;
 while true
  q = path(end, <img src="http://python.jobbole.com/wp-includes/images/smilies/icon_smile.gif" alt=":)" class="wp-smiley"> ;
  p = reshape(M(q(1), q(2), <img src="http://python.jobbole.com/wp-includes/images/smilies/icon_smile.gif" alt=":)" class="wp-smiley"> , 1, 2);
  path(end + 1, <img src="http://python.jobbole.com/wp-includes/images/smilies/icon_smile.gif" alt=":)" class="wp-smiley"> = p;
  if isequal(p, start)
   break;
  end
 end
end

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

提问者更新:

我用Python实现了一下Mikhail的方法,其中用到了numpy库,感谢Thomas推荐。我感觉这个算法是正确的,但是效果不太如预期,以下是相关代码,使用了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, [])

回答by Joseph Kern:

#!/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 [.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])

动态执行效果:

回答by Jim

使用树搜索太繁杂了,迷宫本身就跟解路径是可分的。正因如此,你可以使用连通区域查找算法来标记迷宫中的连通区域,这将迭代搜索两次这些像素点。如果你想要更好地解决方法,你可以对结构单元使用二元运算(binary operations)来填充每个连通区域中的死路。

下面是相关的MATLAB代码及运行结果:

% read in and invert the image
im = 255 - imread('maze.jpg');

% sharpen it to address small fuzzy channels
% threshold to binary 15%
% run connected components
result = bwlabel(im2bw(imfilter(im,fspecial('unsharp')),0.15));

% purge small components (e.g. letters)
for i = 1:max(reshape(result,1,1002*800))
  [count,~] = size(find(result==i));
  if count < 500
    result(result==i) = 0;
  end
end

% close dead-end channels
closed = zeros(1002,800);
for i = 1:max(reshape(result,1,1002*800))
  k = zeros(1002,800);
  k(result==i) = 1; k = imclose(k,strel('square',8));
  closed(k==1) = i;
end

% do output
out = 255 - im;
for x = 1:1002
  for y = 1:800
    if closed(x,y) == 0
      out(x,y,:) = 0;
    end
  end
end
imshow(out);

回答by Stefano

stefano童鞋给出了生成搜索过程GIF及AVI文件的代码 maze-solver-python(GitHub)

(0)

相关推荐

  • python冒泡排序算法的实现代码

    1.算法描述:(1)共循环 n-1 次(2)每次循环中,如果 前面的数大于后面的数,就交换(3)设置一个标签,如果上次没有交换,就说明这个是已经好了的. 2.python冒泡排序代码 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- def bubble(l):    flag = True    for i in range(len(l)-1, 0, -1):        if flag:             flag = False

  • python使用rsa加密算法模块模拟新浪微博登录

    PC登录新浪微博时,在客户端用js预先对用户名.密码都进行了加密,而且在POST之前会GET一组参数,这也将作为POST_DATA的一部分.这样,就不能用通常的那种简单方法来模拟POST登录(比如人人网). 通过爬虫获取新浪微博数据,模拟登录是必不可少的. 1.在提交POST请求之前,需要GET获取四个参数(servertime,nonce,pubkey和rsakv),不是之前提到的只是获取简单的servertime,nonce,这里主要是由于js对用户名.密码加密方式改变了. 1.1 由于加密

  • python实现RSA加密(解密)算法

    RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被ISO推荐为公钥数据加密标准. 今天只有短的RSA钥匙才可能被强力方式解破.到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式.只要其密钥的长度足够长,用RSA加密的信息实际上是不能被解破的.但在分布式计算和量子计算机理论日趋成熟的今天,RSA加密安全性受到了挑战. RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但是想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥.

  • Python基于递归算法实现的走迷宫问题

    本文实例讲述了Python基于递归算法实现的走迷宫问题.分享给大家供大家参考,具体如下: 什么是递归? 简单地理解就是函数调用自身的过程就称之为递归. 什么时候用到递归? 如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法. 迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题. 在python中可以使用list

  • python回溯法实现数组全排列输出实例分析

    本文实例讲述了python回溯法实现数组全排列输出的方法.分享给大家供大家参考.具体分析如下: 全排列解释:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. from sys import stdout #code from http://www.jb51.net/ def perm(li, start, end): if(start == end): for elem in li: stdout.wr

  • Python基于回溯法子集树模板实现8皇后问题

    本文实例讲述了Python基于回溯法子集树模板实现8皇后问题.分享给大家供大家参考,具体如下: 问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0.1.2.....7列,我们认为每一行的皇后有8种状态.那么,我们只要套用子集树模板,从第0行开始,自上而下,对每一行的皇后,遍历它的8个状态即可. 代码: ''' 8皇后问题 '''

  • Python多线程经典问题之乘客做公交车算法实例

    本文实例讲述了Python多线程经典问题之乘客做公交车算法.分享给大家供大家参考,具体如下: 问题描述: 乘客乘坐公交车问题,司机,乘客,售票员协同工作,通过多线程模拟三者的工作. 司机:开车,停车 售票员:打开车门,关闭车门 乘客:上车,下车 用Python的Event做线程同步通信,代码如下: # *-* coding:gb2312 *-* import threading import time stationName=("车站0","车站1","车

  • python求众数问题实例

    本文实例讲述了python求众数问题的方法,是一个比较典型的应用.分享给大家供大家参考.具体如下: 问题描述: 多重集中重数最大的元素称为众数...就是一个可以有重复元素的集合,在这个集合中重复的次数最多的那个数就叫它的众数... 如S = [1,2,2,2,3,5] 重数是2,其重数为3 实例代码如下: list_num = [] list_num_count = 0 dict_num ={} #从文件读入,文件第一行为集合中元素的个数,以后每一行为一个元素 list_num_count =

  • Python使用回溯法子集树模板解决迷宫问题示例

    本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题 给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析 考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.

  • python实现的生成随机迷宫算法核心代码分享(含游戏完整代码)

    完整代码下载:http://xiazai.jb51.net/201407/tools/python-migong.rar 最近研究了下迷宫的生成算法,然后做了个简单的在线迷宫游戏.游戏地址和对应的开源项目地址可以通过上面的链接找到.开源项目中没有包含服务端的代码,因为服务端的代码实在太简单了.下面将简单的介绍下随机迷宫的生成算法.一旦理解后你会发现这个算法到底有多简单. 1.将迷宫地图分成多个房间,每个房间都有四面墙. 2.让"人"从地图任意一点A出发,开始在迷宫里游荡.从A房间的1/

  • python编写的最短路径算法

    一心想学习算法,很少去真正静下心来去研究,前几天趁着周末去了解了最短路径的资料,用python写了一个最短路径算法.算法是基于带权无向图去寻找两个点之间的最短路径,数据存储用邻接矩阵记录.首先画出一幅无向图如下,标出各个节点之间的权值. 其中对应索引: A --> 0 B--> 1 C--> 2 D-->3 E--> 4 F--> 5 G--> 6 邻接矩阵表示无向图: 算法思想是通过Dijkstra算法结合自身想法实现的.大致思路是:从起始点开始,搜索周围的路径

随机推荐