画像を与えられた迷路を表現して解決する

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

画像が与えられた迷路を表現して解決するための最良の方法は何ですか?

The The ScopeIssue134のカバー画像

JPEG画像(上記のように)が与えられた場合、それを読み取り、データ構造に解析し、迷路を解決するための最良の方法は何ですか?私の最初の本能とは、画像をピクセルごとに読み取り、ブール値のリスト(配列)に格納することです。白いピクセルの場合は True 、非白いピクセルの場合は Falseです。ピクセル(色は破棄できます)この方法の問題は、画像が「ピクセルパーフェクト」ではない可能性があることです。つまり、壁のどこかに白いピクセルがあると、意図しないパスが作成される可能性があります。

もう1つの方法(少し考えた後で思いついた)は、画像をSVGファイル(キャンバスに描画されたパスのリスト)に変換することです。このようにして、パスを次のように読み取ることができます。同じ種類のリスト(ブール値)。ここで、 True はパスまたは壁を示し、 False 移動可能なスペースを示します。この方法の問題は、変換が100%正確でなく、すべての壁を完全に接続していない場合に発生し、ギャップが生じます。

SVGへの変換の問題は、線が「完全に」ないことです。 " 真っ直ぐ。これにより、パスは3次ベジェ曲線になります。整数でインデックス付けされたブール値のリスト(配列)を使用すると、曲線は簡単に転送されず、曲線上に並ぶすべてのポイントを計算する必要がありますが、リストのインデックスと正確に一致しません。

これらの方法の1つは機能するかもしれませんが(おそらくそうではありませんが)、そのような大きな画像を考えるとひどく非効率的であり、より良い方法が存在すると思います。 )完了しましたか?最善の方法もありますか?

次に迷路を解きます。最初の2つの方法のいずれかを使用すると、基本的に行列になります。この回答、迷路を表す良い方法は木を使用することであり、それを解決する良い方法は A *アルゴリズム。画像からツリーを作成するにはどうすればよいですか?

TL; DR
解析するための最良の方法は?構造?構造はどのように解決を助け/妨げますか?

更新
私は@MikhailがPythonで書いたものをnumpy、@ Thomasが推奨しているように。アルゴリズムは正しいと思いますが、期待どおりに機能していません。 (以下のコード。)PNGライブラリはPyPNGです。

  import png、numpy、Queue、operator、itertools def is_white(coord、image): "" "(x、y)がほぼ白いピクセルかどうかを返します。" "" a = True for xrange(3)のi:そうでない場合: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))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#ファイルがRGBであることを確認しますimage2d = numpy.vstack(itertools.imap(numpy.uint8、pixels))start、end =(402、985)、(398 、27)print bfs(start、end、image2d、[])