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

來源：懂視網責編：小采時間：2020-11-27 14:17:37

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

用Python代碼來解圖片迷宮的方法整理:譯注：原文是StackOverflow上一個如何用程序讀取迷宮圖片并求解的問題，幾位參與者熱烈地討論并給出了自己的代碼，涉及到用Python對圖片的處理以及廣度優先(BFS)算法等。問題by Whymarrh：當給定上面那樣一張JPEG圖片，如何才能更好地將這張圖轉換為合

推薦度：

點擊下載本文 文檔為doc格式

導讀用Python代碼來解圖片迷宮的方法整理:譯注：原文是StackOverflow上一個如何用程序讀取迷宮圖片并求解的問題，幾位參與者熱烈地討論并給出了自己的代碼，涉及到用Python對圖片的處理以及廣度優先(BFS)算法等。問題by Whymarrh：當給定上面那樣一張JPEG圖片，如何才能更好地將這張圖轉換為合

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

問題by Whymarrh：

201542111941881.jpg (800×1002)

當給定上面那樣一張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或其他語言，下面是程序的運行結果：

201542112134749.jpg (800×1002)

提問者更新：

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

動態執行效果：

201542112219406.gif (160×200)

回答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);

201542112302746.jpg (964×1088)