表示和解決給定圖像的迷宮

| | | | | | | | | | | | | | | | | | | | | | | | |

給定圖像表示和解決迷宮的最佳方法是什麼?

The The Scope Issue 134 的封面圖片

給定一張 JPEG 圖像(如上所示),讀取它、將其解析為某種數據結構並解決迷宮問題的最佳方法是什麼?我的第一個本能是逐像素讀取圖像並將其存儲在布爾值列表(數組)中:True 表示白色像素,False 表示非白色像素(可以丟棄顏色)。這種方法的問題是圖像可能不是“像素完美”。我的意思是,如果牆上某處有一個白色像素,它可能會創建一個意想不到的路徑。

另一種方法(經過一番思考後想到)是將圖像轉換為 SVG 文件 - 這是在畫布上繪製的路徑列表。這樣,可以將路徑讀入相同類型的列表(布爾值),其中 True 表示路徑或牆壁,False表示可行駛的空間。如果轉換不是 100% 準確,並且沒有完全連接所有牆壁,從而產生間隙,則此方法會出現問題。

轉換為 SVG 的另一個問題是線條不是“完美的” “ 直的。這導致路徑是三次貝塞爾曲線。使用由整數索引的布爾值列表(數組),曲線不會輕易轉移,曲線上的所有點都必須計算,但不會與列表索引完全匹配。

我假設雖然其中一種方法可能有效(儘管可能無效),但考慮到如此大的圖像,它們的效率非常低,並且存在更好的方法。這如何最好(最有效和/或複雜性最低) ) 完成了嗎?有沒有最好的方法?

然後是解迷宮。如果我使用前兩種方法中的任何一種,我基本上都會得到一個矩陣。根據 this answer,表示迷宮的好方法是使用樹,解決它的好方法是使用 A* 算法。如何從圖像中創建一棵樹?有什麼想法嗎?

TL;DR
解析的最佳方式是什麼? ta結構?上述結構如何幫助/解決問題?

更新
我已經嘗試使用 numpy

實現@Mikhail 用 Python 編寫的內容代碼>,正如@Thomas 推薦的那樣。我覺得算法是正確的,但它沒有像希望的那樣工作。 (代碼如下。)PNG 庫是 PyPNG。 p>
import png, numpy, Queue, operator, itertools def is_white(coord, image): """ 返回 (x, y) 是否近似於一個白色像素。""" 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): """ 執行廣度優先搜索。""" frontier = Queue.Queue() while s != e: for d in [(-1, 0 ), (0, -1), (1, 0), (0, 1)]: np = tuple(map(operator.add, s, d)) 如果 is_white(np, i) 和 np 未訪問: frontier.put(np)visited.append(s) s = frontier.get() returnvisited def main(): r = png.Reader(filename = "thescope-134.png") 行、列、像素、元 = r.asDirect() assert meta["planes"] == 3 # 確保文件是 RGB image2d = numpy.vstack(itertools.imap(numpy.uint8, pixel)) start, end = (402, 985), (398 , 27) 打印 bfs(start, end, image2d, [])