8

下の画像のような値のラスター グリッドがあります (白が高い値、黒の背景値がゼロ)。

RasterGrid の例

私は、行の1つの最後から開始し、可能な限り高い値を経由してもう一方の端までトレースする、ある種のパス追跡コードを記述しようとしています(つまり、行にあるように選択されたピクセルが白くなるほど)良い）しかし、まだ反対側に到達しています。

私はしばらくこれに苦労してきましたが、私がやろうとしていることが何も得られないようです。それで、この種の問題に対して一般的なアルゴリズムがすでに開発されているのではないかと思いました。私は多くの検索を行ってきましたが、ほとんどのパス アルゴリズムは、このようなラスター グリッドではなく、ベクター/ネットワークで動作するように設計されているようです。

何か案は？

4

4 に答える 4

8

最も簡単なアイデアは、おそらくA *アルゴリズムを使用することです。ここで、各ピクセルはノードであり、ノードのコストはピクセルの暗さです。

更新：素敵なチュートリアルが見つかりました。

于 2010-12-03T21:24:03.417 に答える
2

これを行う1つの方法：

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

うまく機能させるには多少の調整が必要ですが、この方法で行うことは可能です。もう1つのバリエーションは、白いセクションが1、2、または3ピクセルより広い場合は輪郭を描き、後で二重線を結合することです。

于 2010-12-03T21:24:26.820 に答える
1

これを大規模に、または研究のために行う場合は、 http：//en.wikipedia.org/wiki/Ant_colony_optimizationを試してみてください。ただし、これをお金のために行う場合は、フラッドフィルhttp：//enのようなものを選択してください。 wikipedia.org/wiki/Flood_fill

于 2010-12-03T21:24:54.043 に答える
1

遺伝的アルゴリズムやばかげたものは必要ないと思います。古き良き再帰と動的プログラミングで十分です。私は当初、幅優先検索を行うことで目標を達成できるはずだと考えています。開始点から、そのパスの値よりもスコアが大きいすべての隣接セルを訪問します。すべてのセルは無限大から始まり、黒いセルへのコストは無限大になります。これらは除去できるパスです)。目的地に着いたら、到達可能であれば、バックトラックしてパスを見つけることができるはずです。貪欲ですが、パスがこれらのように適切に動作していれば、問題ありません。

より多くのグレーとツイストとターンのあるパスの場合、ラスター イメージをグラフに変換することをお勧めします。エッジの重みは、隣接するパスのグレー スケール値 (またはグレー スケール値の差。データは実際に意味します)。そのため、その解釈に基づいて最短パスに任意のアルゴリズムを使用できるはずです。

于 2010-12-03T21:09:26.180 に答える