☰

画像を与えられたときに迷路を表現して解く 質問する

tag-icon • tag-icon python algorithm matlab image-processing maze
画像を与えられたときに迷路を表現して解く 質問する

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

The Scope 134号の表紙画像

JPEG 画像 (上記参照) がある場合、それを読み込み、何らかのデータ構造に解析して迷路を解く最適な方法は何でしょうか。私の最初の直感は、画像をピクセルごとに読み取り、ブール値のリスト (配列) に格納することです。ブール値は、True白のピクセルとFalse白以外のピクセル (色は無視できます) です。この方法の問題は、画像が「ピクセル パーフェクト」ではない可能性があることです。つまり、壁のどこかに白のピクセルがあると、意図しないパスが作成される可能性があるということです。

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

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

これらの方法の 1 つは機能するかもしれませんが (おそらく機能しないでしょうが)、このような大きな画像ではひどく非効率的であり、よりよい方法があると思います。これを最も効果的に (最も効率的に、または最も複雑さを最小限に抑えて) 実行するにはどうすればよいでしょうか。そもそも、最善の方法はあるのでしょうか。

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

TL;DR
解析する最良の方法は? どのようなデータ構造に? その構造は解決にどのように役立つ/妨げになるか?

更新
@Thomas の推奨に従い、@Mikhail が書いたものを Python で実装してみましたnumpy。アルゴリズムは正しいと思いますが、期待通りには動作しません。(コードは以下のとおりです。) 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

ここに解決策があります。

  1. 画像をグレースケール (まだバイナリではありません) に変換し、最終的なグレースケール画像がほぼ均一になるように色の重みを調整します。これは、Photoshop の [イメージ] -> [色調補正] -> [白黒] でスライダーを制御するだけで簡単に実行できます。
  2. Photoshop の「イメージ」->「調整」->「しきい値」で適切なしきい値を設定して、画像をバイナリに変換します。
  3. しきい値が正しく選択されていることを確認します。マジック ワンド ツールを、許容値 0、ポイント サンプル、連続、アンチエイリアスなしで使用します。選択が中断されるエッジが、誤ったしきい値によって生成された偽のエッジではないことを確認します。実際、この迷路のすべての内部ポイントは最初からアクセス可能です。
  4. 仮想旅行者が迷路の周りを歩かないように、迷路に人工的な境界線を追加します :)
  5. 埋め込む幅優先探索(BFS)を好きな言語で最初から実行してください。私はマテリアライズドこのタスクでは、@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

これは本当にシンプルで標準的なものなので、これを実装するのに困難はないはずです。パイソンあるいは何でも。

そして答えはこうです:

ここに画像の説明を入力してください

おすすめ記事