[解決済み】画像を使った迷路の表現と解き方

質問

迷路を画像で表現し、解くのに最適な方法は何でしょうか？

上のようなJPEG画像があったとして、それを読み込んで、何らかのデータ構造にパースし、迷路を解くのに最適な方法は何でしょうか？私の最初の直感は、画像をピクセル単位で読み込んで、ブール値のリスト（配列）に格納することです。 True は白い画素、そして False は白でない画素を表します（色は捨ててもかまいません）。この方法の問題点は、画像が「ピクセル・パーフェクト」でない可能性があることです。つまり、壁のどこかに白いピクセルがあると、意図しないパスができる可能性があるということです。

もうひとつの方法は（少し考えて思いついたのですが）、画像をSVGファイル（キャンバス上に描かれたパスのリスト）に変換することです。この方法では、パスは以下のようなリスト（ブール値）に読み込まれます。 True はパスまたは壁を示します。 False は移動可能な空間であることを示します。この方法の問題点は、変換が100％正確でない場合、すべての壁を完全につなげず、隙間ができてしまうことです。

また、SVGに変換する際の問題点として、線が完全に直線にならないことが挙げられます。その結果、パスは3次ベジェ曲線になります。整数値でインデックスされたブール値のリスト（配列）では、曲線は簡単に転送できず、曲線上に並ぶすべての点を計算する必要がありますが、リストのインデックスに正確に一致しません。

これらの方法のいずれかがうまくいくかもしれませんが（おそらくうまくいきませんが）、このような大きな画像を考えると非常に効率が悪く、より良い方法が存在すると推測されます。これはどのように行うのがベストでしょうか（最も効率的かつ/または最も複雑でない）？また、最適な方法はあるのでしょうか？

そして、迷路の解法です。最初の2つの方法のどちらを使っても、基本的には行列ができあがります。以下は この答え 迷路を表現する良い方法は木を使うことであり、迷路を解く良い方法は A* アルゴリズム . この画像からどのように木を作るのでしょうか？何かアイデアはありますか？

TL;DR

パースするのに最適な方法？どのようなデータ構造へ？その構造は解決にどのように役立つのか/妨げになるのか？

アップデイト

Mikhailが書いたものをPythonで実装してみました。 numpy のように、@Thomas が推奨するように。アルゴリズムは正しいと思うのですが、期待通りには動きません。(以下コード。) PNGライブラリは 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, [])

解決方法は？

ここでは、その解決策をご紹介します。

1. 画像をグレースケール（まだ2値化されていない）に変換し、最終的なグレースケール画像がほぼ均一になるように色の重みを調整します。Photoshopの画像 -> 調整 -> 黒と白でスライダーを操作すれば簡単に行えます。
2. Photoshopの「画像 ->調整 ->しきい値」で適切なしきい値を設定し、画像を2値に変換する。
3. しきい値が正しく選択されていることを確認します。マジックワンドツールを公差0、ポイントサンプル、連続、アンチエイリアス無しで使用します。選択範囲が途切れるエッジが、間違ったしきい値による偽エッジでないことを確認します。実際、この迷路の内部の点はすべて最初からアクセス可能です。
4. 迷路に人工的な境界線を追加し、仮想旅行者がその周りを歩かないことを確認する :)
5. 実装 幅優先探索 (BFS)を好きな言語で、最初から実行します。私の好みは MATLAB このタスクのために。すでに@Thomasが述べているように、グラフの通常の表現をいじる必要はありません。2値化された画像を直接扱うことができます。

以下はBFSのMATLABコードです。

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 などがあります。

そして、その答えがこちらです。