欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

用Python代碼來解圖片迷宮的方法整理

 更新時間:2015年04月02日 11:28:47   作者:StackOverflow  
這篇文章主要介紹了用Python代碼來解圖片迷宮的方法整理,本文精選了StackOverflow相關(guān)人氣問題上的幾個回答,需要的朋友可以參考下

譯注:原文是StackOverflow上一個如何用程序讀取迷宮圖片并求解的問題,幾位參與者熱烈地討論并給出了自己的代碼,涉及到用Python對圖片的處理以及廣度優(yōu)先(BFS)算法等。

問題by Whymarrh:

201542111941881.jpg (800×1002)

當(dāng)給定上面那樣一張JPEG圖片,如何才能更好地將這張圖轉(zhuǎn)換為合適的數(shù)據(jù)結(jié)構(gòu)并且解出這個迷宮?

我的第一直覺是將這張圖按像素逐個讀入,并存儲在一個包含布爾類型元素的列表或數(shù)組中,其中True代表白色像素,F(xiàn)alse代表非白色像素(或彩色可以被處理成二值圖像)。但是這種做法存在一個問題,那就是給定的圖片往往并不能完美的“像素化”。考慮到如果因為圖片轉(zhuǎn)換的原因,某個非預(yù)期的白色像素出現(xiàn)在迷宮的墻上,那么就可能會創(chuàng)造出一一條非預(yù)期的路徑。

經(jīng)過思考之后,我想出了另一種方法:首先將圖片轉(zhuǎn)換為一個可縮放適量圖形(SVG)文件,這個文件由一個畫布上的矢量線條列表組成,矢量線條按照列表的順序讀取,讀取出的仍是布爾值:其中True表示墻,而False表示可通過的區(qū)域。但是這種方法如果無法保證圖像能夠做到百分之百的精確轉(zhuǎn)換,尤其是如果不能將墻完全準(zhǔn)確的連接,那么這個迷宮就可能出現(xiàn)裂縫。

圖像轉(zhuǎn)換為SVG的另一個問題是,線條并不是完美的直線。因為SVG的線條是三次貝塞爾曲線,而使用整數(shù)索引的布爾值列表增加了曲線轉(zhuǎn)換的難度,迷宮線條上的所有點在曲線上都必須經(jīng)過計算,但不一定能夠完美對應(yīng)列表中的索引值。

假設(shè)以上方法的確可以實現(xiàn)(雖然很可能都不行),但當(dāng)給定一張很大的圖像時,它們還是不能勝任。那么是否存在一種更好地方法能夠平衡效率和復(fù)雜度?

這就要討論到如何解迷宮了。如果我使用以上兩種方法中的任意一種,我最終將會得到一個矩陣。而根據(jù)這個問答(http://stackoverflow.com/questions/3097556/programming-theory-solve-a-maze/3097677#3097677),一個比較好的迷宮表示方式應(yīng)該是使用樹的結(jié)構(gòu),并且使用A*搜索算法來解迷宮。那么如何從迷宮圖片中構(gòu)造出迷宮樹呢?有比較好的方法么?

以上廢話太多,總結(jié)起來問題就是:如何轉(zhuǎn)換迷宮圖片?轉(zhuǎn)換成為什么樣的數(shù)據(jù)結(jié)構(gòu)?采用什么樣的數(shù)據(jù)結(jié)構(gòu)能夠幫助或阻礙解迷宮?

回答by Mikhail:

這是我的解決方案:

1. 將圖片轉(zhuǎn)換為灰度圖像(不是直接二值),調(diào)整不同顏色的權(quán)重使得最終的灰度看起來比較統(tǒng)一,你可以通過簡單地調(diào)節(jié)Photoshop 圖像->調(diào)整->黑白 菜單中的控制條來實現(xiàn)。
2. 將上一步得到的灰度圖片轉(zhuǎn)換為二值圖片,可以通過在PS 圖像->調(diào)整->閾值 菜單中設(shè)定適當(dāng)?shù)拈撝祦韺崿F(xiàn)
3. 確保正確設(shè)置了閾值。使用魔棒工具(參數(shù)設(shè)置:容差 0、取樣點、連續(xù)以及消除鋸齒)選擇空白區(qū)域,檢查所選區(qū)域的邊緣不是因為錯誤的閾值設(shè)置而產(chǎn)生的假邊緣。事實上,這個迷宮中從start到end應(yīng)該由聯(lián)通的空白區(qū)域。
4. 人為地在迷宮外部加上邊界,確保迷宮漫游者^_^不會從start繞著迷宮跑到終點。:)
5. 選擇語言實現(xiàn)廣度優(yōu)先搜索算法(BFS),從start處開始讓程序運行。下面的代碼我選擇用Matlab實現(xiàn)。正如Thomas提到的,沒必要糾結(jié)于圖像的表示形式,你可以直接在二值圖像上運行。

以下是用MATLAB實現(xiàn)的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

這是個簡單的實現(xiàn),應(yīng)該很容易就能夠改寫為Python或其他語言,下面是程序的運行結(jié)果:

201542112134749.jpg (800×1002)

提問者更新:

我用Python實現(xiàn)了一下Mikhail的方法,其中用到了numpy庫,感謝Thomas推薦。我感覺這個算法是正確的,但是效果不太如預(yù)期,以下是相關(guān)代碼,使用了PyPNG庫處理圖片。

 譯注:很遺憾,我用提問者提供的代碼并沒有跑通程序,并且似乎代碼縮進有點問題,而下面其他參與者的代碼能夠執(zhí)行通過,并且效果很好。

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])

動態(tài)執(zhí)行效果:

201542112219406.gif (160×200)

回答by Jim

使用樹搜索太繁雜了,迷宮本身就跟解路徑是可分的。正因如此,你可以使用連通區(qū)域查找算法來標(biāo)記迷宮中的連通區(qū)域,這將迭代搜索兩次這些像素點。如果你想要更好地解決方法,你可以對結(jié)構(gòu)單元使用二元運算(binary operations)來填充每個連通區(qū)域中的死路。

下面是相關(guān)的MATLAB代碼及運行結(jié)果:
 

% 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);

201542112302746.jpg (964×1088)

回答by Stefano

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

201542112345448.gif (320×401)

相關(guān)文章

  • python 實現(xiàn)判斷ip連通性的方法總結(jié)

    python 實現(xiàn)判斷ip連通性的方法總結(jié)

    下面小編就為大家分享一篇python 實現(xiàn)判斷ip連通性的方法總結(jié),具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-04-04
  • python 合并多個excel中同名的sheet

    python 合并多個excel中同名的sheet

    這篇文章主要介紹了python 如何合并多個excel中同名的sheet,幫助大家更好的利用python處理excel表格,感興趣的朋友可以了解下
    2021-01-01
  • Python中的各種裝飾器詳解

    Python中的各種裝飾器詳解

    這篇文章主要介紹了Python中的各種裝飾器詳解,Python裝飾器分兩部分,一是裝飾器本身的定義,一是被裝飾器對象的定義,本文分別講解了各種情況下的裝飾器,需要的朋友可以參考下
    2015-04-04
  • Perl中著名的Schwartzian轉(zhuǎn)換問題解決實現(xiàn)

    Perl中著名的Schwartzian轉(zhuǎn)換問題解決實現(xiàn)

    這篇文章主要介紹了Perl中著名的Schwartzian轉(zhuǎn)換問題解決實現(xiàn),本文詳解講解了Schwartzian轉(zhuǎn)換涉及的排序問題,并同時給出實現(xiàn)代碼,需要的朋友可以參考下
    2015-06-06
  • PyQt QCombobox設(shè)置行高的方法

    PyQt QCombobox設(shè)置行高的方法

    今天小編就為大家分享一篇PyQt QCombobox設(shè)置行高的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-06-06
  • python打包壓縮、讀取指定目錄下的指定類型文件

    python打包壓縮、讀取指定目錄下的指定類型文件

    這篇文章主要介紹了python打包壓縮、讀取指定目錄下的指定類型文件,需要的朋友可以參考下
    2018-04-04
  • python基于plotly實現(xiàn)畫餅狀圖代碼實例

    python基于plotly實現(xiàn)畫餅狀圖代碼實例

    這篇文章主要介紹了python基于plotly實現(xiàn)畫餅狀圖代碼實例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-12-12
  • 通俗易懂詳解Python基礎(chǔ)五種下劃線作用

    通俗易懂詳解Python基礎(chǔ)五種下劃線作用

    本來而言,這個問題網(wǎng)上很多資料,但是網(wǎng)上資料都是復(fù)制來復(fù)制去,很多話大家其實都不是很明白的,或者拿著官方文檔翻譯過來的,讓人看的非常迷糊。今天用通俗好懂表述解釋下這幾種情況
    2021-10-10
  • 對python mayavi三維繪圖的實現(xiàn)詳解

    對python mayavi三維繪圖的實現(xiàn)詳解

    今天小編就為大家分享一篇對python mayavi三維繪圖的實現(xiàn)詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-01-01
  • python實現(xiàn)的分層隨機抽樣案例

    python實現(xiàn)的分層隨機抽樣案例

    這篇文章主要介紹了python實現(xiàn)的分層隨機抽樣案例,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-02-02

最新評論