搜尋
首頁web前端H5教程如何用程序解图片迷宫?

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

  译注:原文是 StackOverflow 上一个如何用程序读取迷宫图片并求解的问题,几位参与者热烈地讨论并给出了自己的代码,涉及到用 Python 对图片的处理以及广度优先(BFS)算法等。

  问题 by Whymarrh:

1116.jpg

       当给定上面那样一张 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, :) = 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 或其他语言,下面是程序的运行结果:

1117.jpg

提问者更新:

  我用 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);

1118.jpg

回答 by Stefano

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

以上就是如何用程序解图片迷宫的内容,更多相关内容请关注PHP中文网(www.php.cn)!


陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
ace-guard client exe是什么程序ace-guard client exe是什么程序Sep 22, 2021 pm 06:07 PM

ace-guard client exe是腾讯代理游戏的反作弊程序,是ewido的守护进程,保护“ewido.exe”进程不被恶意软件关闭;使用它可以检测游戏用户是否有开挂行为,可自动进行封号处理。

修复: 操作员拒绝 Windows 任务计划程序中的请求错误修复: 操作员拒绝 Windows 任务计划程序中的请求错误Aug 01, 2023 pm 08:43 PM

要自动化任务和管理多个系统,任务计划软件是您武器库中的宝贵工具,尤其是对于系统管理员而言。Windows任务计划程序完美地完成了这项工作,但最近许多人报告说操作员拒绝了请求错误。该问题存在于操作系统的所有迭代中,即使已经广泛报告和涵盖,也没有有效的解决方案。继续阅读以找到真正对其他人有用的内容!操作员或管理员拒绝了任务计划程序0x800710e0中的请求是什么?任务计划程序允许在没有用户输入的情况下自动执行各种任务和应用程序。您可以使用它来安排和组织特定应用程序、配置自动通知、帮助传递消息等。它

如何在Windows 10和11上按面部对照片进行排序如何在Windows 10和11上按面部对照片进行排序Aug 08, 2023 pm 10:41 PM

Windows的操作随着每个版本而变得越来越好,具有诱人的功能来改善用户体验。用户希望在Windows10和11上探索的一项功能是能够按面部对照片进行排序。此功能允许您通过面部识别对朋友和家人的照片进行分组。听起来很有趣,对吧?继续阅读如何了解如何利用该功能。我可以在Windows上按面孔对照片进行分组吗?是的,您可以使用“照片”应用在Windows10和11上按人脸对图片进行分组。但是,此功能在照片应用程序版本上不可用。此外,您可以使用“人脉”选项卡将这些照片链接到联系人。因此,使用此功能可以

microsoft visual c++可以卸载吗?microsoft visual c++可以卸载吗?Sep 14, 2022 am 11:36 AM

“microsoft visual c++”是可以卸载的,但是不建议卸载;“microsoft visua”这些都是一些微软的组件,里面包括一些“C++”标准库、原始数据库等相关信息,很多软件尤其是游戏中需要“microsoft visual c++”中的环境组件,如果缺少了“C++”标准库的支持,可能会造成软件的无法运行。

如何自动切换特定应用程序的iPhone方向锁定如何自动切换特定应用程序的iPhone方向锁定Jun 06, 2023 am 08:22 AM

在iOS中,当您将iPhone从纵向旋转到横向时,许多App会显示不同的视图。根据应用程序及其使用方式,这种行为并不总是可取的,这就是Apple在“控制中心”中包含方向锁定选项的原因。但是,某些应用程序在禁用方向锁定的情况下工作得更有用-想想YouTube或照片应用程序,将设备旋转到横向可以提供更好的全屏观看体验。如果您倾向于保持锁定状态,则必须在每次打开这些类型的应用程序时在“控制中心”中禁用它以获得全屏体验。然后,当您关闭应用程序时,您必须记住重新打开方向锁定,这并不理想。幸运的是,您可以创

如何从Microsoft商店快速卸载应用如何从Microsoft商店快速卸载应用Jul 12, 2023 pm 09:25 PM

Microsoft应用商店是内置存储库,用户可以在其中下载、更新和卸载适用于Windows操作系统的应用。可悲的是,许多用户不知道如何在MicrosoftStore上卸载应用程序。因此,本文将带您了解如何快速从Microsoft商店卸载应用程序。或者,如果您的Windows11PC上缺少Microsoft应用商店应用程序,我们提供了有关下载和安装应用商店应用程序的详细指南。是否可以直接从Microsoft应用商店卸载应用?否,Microsoft应用商店不提供直接从平台卸载应用的选项。您只能通过平

C语言中的身份矩阵程序C语言中的身份矩阵程序Aug 30, 2023 am 10:45 AM

给定一个方阵M[r][c],其中“r”是一定数量的行,“c”是列,使得r=c,我们必须检查“M”是否是单位矩阵。恒等矩阵恒等矩阵也称为大小为nxn方阵的单位矩阵,其中对角元素的整数值为1,非对角元素的整数值为0就像下面给定的示例-$$I1=\begin{bmatrix}1\end{bmatrix},\I2=\begin{bmatrix}1&0\0&1\end{bmatrix},\I3=\begin{bmatrix}1&0&0\0&1&0\0&

卸载程序的文件名是什么卸载程序的文件名是什么Oct 21, 2022 pm 02:05 PM

卸载程序的文件名是“uninstall.exe”或“uninst.exe”,是用以协助使用者将软件自电脑中删除的一种电脑软件。使用方法:1、在文件资源管理器中挖掘并导航到应用程序EXE文件所在的文件路径;2、通过文件路径打开应用程序的安装目录,找到“uninstall.exe”文件;3、双击卸载文件“uninstall.exe”即可开始程序删除过程。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前By尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
1 個月前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
4 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

EditPlus 中文破解版

EditPlus 中文破解版

體積小,語法高亮,不支援程式碼提示功能

SublimeText3 英文版

SublimeText3 英文版

推薦:為Win版本,支援程式碼提示!

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強大的PHP整合開發環境