搜尋
首頁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
H5代碼的基礎:密鑰元素及其目的H5代碼的基礎:密鑰元素及其目的Apr 23, 2025 am 12:09 AM

HTML5的關鍵元素包括、、、、、等,用於構建現代網頁。 1.定義頭部內容,2.用於導航鏈接,3.表示獨立文章內容,4.組織頁面內容,5.展示側邊欄內容,6.定義頁腳,這些元素增強了網頁的結構和功能性。

HTML5和H5:了解常見用法HTML5和H5:了解常見用法Apr 22, 2025 am 12:01 AM

HTML5和H5沒有區別,H5是HTML5的簡稱。 1.HTML5是HTML的第五個版本,增強了網頁的多媒體和交互功能。 2.H5常用於指代基於HTML5的移動網頁或應用,適用於各種移動設備。

HTML5:現代網絡的基礎(H5)HTML5:現代網絡的基礎(H5)Apr 21, 2025 am 12:05 AM

HTML5是超文本標記語言的最新版本,由W3C標準化。 HTML5引入了新的語義化標籤、多媒體支持和表單增強,提升了網頁結構、用戶體驗和SEO效果。 HTML5引入了新的語義化標籤,如、、、等,使網頁結構更清晰,SEO效果更好。 HTML5支持多媒體元素和,無需第三方插件,提升了用戶體驗和加載速度。 HTML5增強了表單功能,引入了新的輸入類型如、等,提高了用戶體驗和表單驗證效率。

H5代碼:編寫清潔有效的HTML5H5代碼:編寫清潔有效的HTML5Apr 20, 2025 am 12:06 AM

如何寫出乾淨高效的HTML5代碼?答案是通過語義化標籤、結構化代碼、性能優化和避免常見錯誤。 1.使用語義化標籤如、等,提升代碼可讀性和SEO效果。 2.保持代碼結構化和可讀性,使用適當縮進和註釋。 3.優化性能,通過減少不必要的標籤、使用CDN和壓縮代碼。 4.避免常見錯誤,如標籤未閉合,確保代碼有效性。

H5:如何增強網絡上的用戶體驗H5:如何增強網絡上的用戶體驗Apr 19, 2025 am 12:08 AM

H5通過多媒體支持、離線存儲和性能優化提升網頁用戶體驗。 1)多媒體支持:H5的和元素簡化開發,提升用戶體驗。 2)離線存儲:WebStorage和IndexedDB允許離線使用,提升體驗。 3)性能優化:WebWorkers和元素優化性能,減少帶寬消耗。

解構H5代碼:標籤,元素和屬性解構H5代碼:標籤,元素和屬性Apr 18, 2025 am 12:06 AM

HTML5代碼由標籤、元素和屬性組成:1.標籤定義內容類型,用尖括號包圍,如。 2.元素由開始標籤、內容和結束標籤組成,如內容。 3.屬性在開始標籤中定義鍵值對,增強功能,如。這些是構建網頁結構的基本單位。

了解H5代碼:HTML5的基本原理了解H5代碼:HTML5的基本原理Apr 17, 2025 am 12:08 AM

HTML5是構建現代網頁的關鍵技術,提供了許多新元素和功能。 1.HTML5引入了語義化元素如、、等,增強了網頁結構和SEO。 2.支持多媒體元素和,無需插件即可嵌入媒體。 3.表單增強了新輸入類型和驗證屬性,簡化了驗證過程。 4.提供了離線和本地存儲功能,提升了網頁性能和用戶體驗。

H5代碼:Web開發人員的最佳實踐H5代碼:Web開發人員的最佳實踐Apr 16, 2025 am 12:14 AM

H5代碼的最佳實踐包括:1.使用正確的DOCTYPE聲明和字符編碼;2.採用語義化標籤;3.減少HTTP請求;4.使用異步加載;5.優化圖像。這些實踐能提升網頁的效率、可維護性和用戶體驗。

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脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版