2

各セルに整数の重みが割り当てられた長方形の平面グリッドがあります。平均よりも重みが高い 3 ～ 6 個の隣接セルのクラスターを識別するアルゴリズムを探しています。これらのブロブは、ほぼ円形である必要があります。

私の場合、クラスターを含まないセルの平均重みは約 6 であり、クラスターを含むセルの平均重みは約 6+4 です。つまり、「背景の重み」は約 6 です。重みはポアソン統計で変動します。

小さなバックグラウンドでは貪欲またはシードされたアルゴリズムはかなりうまく機能しますが、クラスター セルの重みがバックグラウンドで変動に近い場合、つまり何もない場合でもクラスターを見つける傾向がある場合、これは機能しません。また、グリッドが大きく (1000x1000 のようなもの)、非常に頻繁に (10^9 回) 実行する予定であるため、考えられるすべてのセットアップをループするブルート フォース検索を実行することはできません。グラフ理論でこれに取り組む方法があるかもしれないという印象があります。頂点カバーとクリークについて聞いたことがありますが、私の問題を彼らの言語に最もよく翻訳する方法がわかりません。グラフ理論には入力の統計的性質に問題がある可能性があることは知っていますが、すべてのクラスターを識別できない場合でも、そこからどのようなアルゴリズムが見つかるかを知りたいと思います。

クリッピングの例を次に示します。フレーム領域にはセルあたり平均 10 個のエントリがあり、他のすべてのセルには平均 6 個のエントリがあります。もちろん、グリッドはさらに拡張されます。

| 8|  8|  2|  8|  2|  3| 
| 6|  4|  3|  6|  4|  4| 
        ===========
| 8|  3||13|  7| 11|| 7|
|10|  4||10| 12|  3|| 2|
| 5|  6||11|  6|  8||12|
        ===========
| 9|  4|  0|  2|  8|  7|
4

4 に答える 4

1

グラフ理論ソリューションの場合、ウィキペディアには2つの文がありますが、MathOverflowに投稿するのがおそらく最善です。この質問も役立つかもしれません。

これらを解決するためのコンピューティングにおける従来の方法（そしておそらくその遍在性を考慮すると最も良い方法）はラスター分析です-GISとリモートセンシングの世界でよく知られているので、実装を提供するツールがたくさんあります。問題に最も適したキーワードを見つけるために使用するキーワードは、ラスター、最近傍、リサンプリング、およびクラスタリングです。多くの場合、GDALライブラリは他のツールの基盤です。

例： http： //clusterville.org/spatialtools/index.html

GDALライブラリとソースコードをチェックして、自分の状況で使用できるかどうか、またはどのように実装されているかを確認することができます。

円形をチェックするために、残りの値をポリゴンに変換して、結果のフィーチャをチェックすることができます

http://www.gdal.org/gdal_polygonize.html

于 2010-04-17T17:32:46.747 に答える
0

問題をグラフの問題に変換する方法を探しているだけの場合は、次のことができます。

各ポイントから、すべての隣人を見てください (これは、必要に応じて、隣接する 8 つの正方形または隣接する 4 つの正方形になります)。最大値を持つ隣人を探し、それが自分よりも大きい場合は、自分自身をこの正方形に接続します。小さい場合は何もしません。

この後、森またはおそらく木ができます（可能性は低いと思いますが）。これは、マトリックスをグラフに変換する 1 つの可能性です。それが最も有用な翻訳であるかどうかはわかりません。

于 2010-05-18T04:23:40.257 に答える
0

グラフ理論の類推が見られるかどうかはわかりませんが、面積積分を事前に計算することで速度を上げることができます。これはマルチスケールのように感じます。

A[i,j] = Sum[Sum[p[u,v], {u, 0, i}, {v, 0, j}]];

次に、長方形の（a、b）、（c、d）領域の平均輝度は

(A[c,d] - (A[c,b] + A[a,d]) + A[a,b])/((ca)(db))

セルに大きな数がある場合、オーバーフローはおそらくあなたの友人ではありません。

于 2010-05-12T16:12:31.653 に答える
0

クラスタリングに共用体検索アルゴリズムを使用しますか? とても速いです。

グラフは、接続されている隣接する高値セルの各ペアを考慮することから得られると思います。union-find アルゴリズムを使用してすべてのクラスターを検索し、特定のサイズを超えるすべてのクラスターを受け入れます。おそらく、形状の制約もあります (クラスターの中心からの平均二乗距離とクラスターのサイズに基づくなど)。必要な統計 (カウント、x の合計、x^2 の合計、y の合計、y^2 の合計) を収集するのは、union-find アルゴリズムの些細なバリエーションです。

于 2010-05-18T00:37:22.833 に答える