アルゴリズムに従うラスタパス

Question

私は、以下の画像のような値のラスタグリッドを持っています（白は高い値、黒の背景値はゼロ）。私はラインのうちの1つの端部で始まり、（可能な限り最高の値を経由、もう一方の端にトレースするパス次のコードのいくつかの種類を記述しようとしている

つまり、ライン内にあるように選択されたピクセルはより白くなりますが、もう一方の端にはまだ行きます）。

私はしばらくの間、これで苦労してきた、と私は仕事にしようと何かを得るように見えることはできません。だから私は疑問に思っています、この種の問題のためにジェネリックアルゴリズムがすでに開発されていますか？私は多くの検索をしましたが、ほとんどのパスアルゴリズムは、このようなラスターグリッドではなく、ベクトル/ネットワークで動作するように設計されているようです。

アイデア？

Answer 1

私は遺伝的アルゴリズムや何かばかげたものは必要ないと思います。良い古いファッションの再帰と動的なプログラミングで十分です。私は最初に、幅広い最初の検索を行うことで目標を達成できるはずであると考えています。あなたの出発点から、そのパス値よりも大きなスコアを持つすべての隣人を訪れます。すべてのセルが無限遠から始まり、黒色セルのコストは無限大になります。目的地に着くと、到達可能であれば、経路を見つけるためにバックトラックすることができます。それは欲張りですが、あなたのパスがこれらのようにうまく動作すれば、それはうまくいくはずです。

より多くのグレーと旋回のあるパスの場合、ラスターイメージをグラフに変換することをお勧めします。エッジウェイトは隣接ピクセルのグレースケール値です（グレースケール値の差、このデータが実際に意味するものに応じて）。だから、その解釈に基づいて最短経路にどのようなアルゴリズムをも使用できるはずです。

Answer 2

おそらく最も単純なアイデアは、各画素がノードであるA* algorithmを使用することで、ノードのコストは、画素暗闇です。

更新：素敵なtutorialが見つかりました。これを行うには

Answer 3

一つの方法：

1. フィルター画像が近い黒と白の画素だけにそれを得るために。
2. 白いピクセルを通って線を描きます。これを行うには、白いピクセルで開始します。そのピクセルから別の白いピクセルに2（または3かそこら）離れた距離を描画しますが、前のラインの近くのピクセルは無視します。行の近くにない画素（2または3ピクセル）を覆うまで続けてください。それをうまく機能させるには、ここで少し調整しなければなりません。
3. 描画した線の端点を接続します。近くに2つの端点（1または2ピクセル？）がある場合は、それらを接続します。おそらくいくつかのループとフォークで、多くの短いセグメントで構成されたいくつかの行で終わるはずです。
4. ラインの小さなループを取り除き、フォークのラインを分けるので、短いセグメントがたくさんある数行があります。
5. ポイントを減らします。各ラインについて、それがほぼ真っ直ぐかどうかを確認します。その場合は、すべての内部ポイントを削除します。そうでない場合は、最小セグメント長になるまで再帰的に行の2つの半分をチェックします。
6. オプションで、このポイントに線を通ってスプライン曲線を当てることができます。
7. 利益。

これはうまくいくためには微妙な調整が必要ですが、このようにすることは可能です。 1つまたは2つまたは3つのピクセルよりも幅が広い場合は、白い部分をアウトライン化し、後でその2つの線を結合します。

Answer 4

あなたは大きな規模でや研究のためにこれをやっている場合は、聖霊降臨祭http://en.wikipedia.org/wiki/Ant_colony_optimizationを試みるかもしれませんが、あなたはお金のためにこれをやっている場合だけで洪水のようなものを拾う。これは持っている、古典的な費用対距離の問題であるhttp://en.wikipedia.org/wiki/Flood_fill