43

この領域に「ドット」が分布している 2D 領域があります。私は現在、ドットの「クラスター」、つまり特定の高密度のドットがある領域を検出しようとしています。

これらの領域をエレガントに検出する方法についての考え (または考えのある記事へのリンク) はありますか?

4

16 に答える 16

24

スペースの任意の解像度を定義し、そのマトリックス内の各ポイントについて、そのポイントからすべてのドットまでの距離の測定値を計算して、「ヒートグラフ」を作成し、しきい値を使用してクラスターを定義するのはどうでしょうか。

これは処理のための優れた演習です。後で解決策を投稿するかもしれません。

編集：

ここにあります：

//load the image
PImage sample;
sample = loadImage("test.png");
size(sample.width, sample.height);
image(sample, 0, 0);
int[][] heat = new int[width][height];

//parameters
int resolution = 5; //distance between points in the gridq
int distance = 8; //distance at wich two points are considered near
float threshold = 0.5;
int level = 240; //leven to detect the dots
int sensitivity = 1; //how much does each dot matters

//calculate the "heat" on each point of the grid
color black = color(0,0,0);
loadPixels();
for(int a=0; a<width; a+=resolution){
  for(int b=0; b<height; b+=resolution){
    for(int x=0; x<width; x++){
      for(int y=0; y<height; y++){
        color c = sample.pixels[y*sample.width+x];        
        /**
         * the heat should be a function of the brightness and the distance, 
         * but this works (tm)
         */
        if(brightness(c)<level && dist(x,y,a,b)<distance){
          heat[a][b] += sensitivity;
        }
      }
    }
  }
}

//render the output
for(int a=0; a<width; ++a){
  for(int b=0; b<height; ++b){
    pixels[b*sample.width+a] = color(heat[a][b],0,0);
  }
}
updatePixels();
filter(THRESHOLD,threshold);

編集2（わずかに非効率的なコードですが同じ出力）：

//load the image
PImage sample;
sample = loadImage("test.png");
size(sample.width, sample.height);
image(sample, 0, 0);
int[][] heat = new int[width][height];
int dotQ = 0;
int[][] dots = new int[width*height][2];
int X = 0;
int Y = 1;


//parameters
int resolution = 1; //distance between points in the grid
int distance = 20; //distance at wich two points are considered near
float threshold = 0.6;
int level = 240; //minimum brightness to detect the dots
int sensitivity = 1; //how much does each dot matters

//detect all dots in the sample
loadPixels();
for(int x=0; x<width; x++){
 for(int y=0; y<height; y++){
   color c = pixels[y*sample.width+x];
   if(brightness(c)<level) {
       dots[dotQ][X] += x;
       dots[dotQ++][Y] += y;
   }
 }
}

//calculate heat
for(int x=0; x<width; x+=resolution){
 for(int y=0; y<height; y+=resolution){
   for(int d=0; d<dotQ; d++){
     if(dist(x,y,dots[d][X],dots[d][Y]) < distance)
       heat[x][y]+=sensitivity;
   }
 }
}

//render the output
for(int a=0; a<width; ++a){
 for(int b=0; b<height; ++b){
   pixels[b*sample.width+a] = color(heat[a][b],0,0);
 }
}
updatePixels();
filter(THRESHOLD,threshold);

/** This smooths the ouput with low resolutions
* for(int i=0; i<10; ++i) filter(DILATE);
* for(int i=0; i<3; ++i) filter(BLUR);
* filter(THRESHOLD);
*/

そして、（縮小された）ケントサンプルを使用した出力：

于 2008-12-10T13:40:43.650 に答える
24

平均シフトカーネルを使用して、ドットの密度中心を見つけることをお勧めします。

平均シフト図 http://cvr.yorku.ca/members/gradstudents/kosta/compvis/file_mean_shift_path.gif

この図は、平均シフト カーネル (最初はクラスターのエッジを中心としていた) がクラスターの最高密度点に向かって収束していることを示しています。

理論的には（一言で言えば）：

この質問に対するいくつかの回答は、平均シフトの方法をすでに示唆しています。

アニメーションの図に表示されているのは、これら 2 つの提案の組み合わせです。移動する「ブロック」(つまりカーネル) を使用して、局所的に最も高い密度を探します。

mean-shift は、カーネルと呼ばれるピクセル近傍(これに似ています) を使用する反復法であり、それを使用して、基になる画像データの平均を計算します。このコンテキストでの平均は、カーネル座標のピクセル加重平均です。

各反復では、カーネルの平均が次の反復の中心座標を定義します。これはシフトと呼ばれます。したがって、名前は mean-shiftです。反復の停止条件は、シフト距離が 0 になったときです (つまり、近隣で最も密度の高い場所にいるとき)。

平均シフトの包括的な紹介 (理論と応用の両方) は、この ppt プレゼンテーションで見つけることができます。

実際には：

平均シフトの実装は、OpenCVで利用できます。

int cvMeanShift( const CvArr* prob_image, CvRect window,
                 CvTermCriteria criteria, CvConnectedComp* comp );

O'Reilly's Learning OpenCv (google book excerpts)にも、それがどのように機能するかについての素晴らしい説明があります。基本的には、ドット画像 (prob_image) をフィードするだけです。

実際には、適切なカーネル サイズを選択するのがコツです。カーネルが小さいほど、クラスターの近くで開始する必要があります。カーネルが大きいほど、初期位置がよりランダムになります。ただし、画像にドットのクラスターがいくつかある場合、カーネルはそれらの間で収束する可能性があります。

于 2009-01-05T18:28:04.540 に答える
12

Trebsの声明に少し補助を加えるために、クラスターの定義が何であるかを現実的に最初に定義することが重要だと思います。

私が生成したこのサンプル セットを見てください。そこにクラスター シェイプがあることがわかり、私が作成しました。

ただし、この「クラスター」をプログラムで特定するのは難しい場合があります。

人間はそれを大きなトロイダル クラスターと見なすかもしれませんが、自動化されたプログラムはそれを半接近した一連の小さなクラスターと判断する可能性が高くなります。

また、超高密度の領域があることに注意してください。これは、全体像のコンテキストにあり、単なる気晴らしにすぎません。

この動作を考慮し、特定のアプリケーションに応じて、より低い密度の取るに足らないボイドだけで区切られた同様の密度のクラスターを連鎖させる必要があります。

あなたが開発するものは何でも、少なくともこのセット内のデータを識別する方法に興味があります.

(HDRI ToneMapping の背後にあるテクノロジーを検討することが適切であると思います。これらは多かれ少なかれ Light Density で機能し、「ローカル」トーンマップと「グローバル」トーンマップがあり、それぞれ異なる結果が得られるためです)

于 2008-12-10T13:56:30.967 に答える
12

2D 領域のコピーにぼかしフィルターを適用します。何かのようなもの

1 2 3 2 1
2 4 6 4 2
3 6 9 6 3
2 4 6 4 2
1 2 3 2 1

「暗い」領域は、ドットのクラスターを識別します。

于 2008-12-10T13:57:14.287 に答える
10

データのQuadtree表現を作成してみてください。グラフの短いパスは、高密度の領域に対応します。

または、より明確に言えば、クアッドツリーとレベル次のトラバーサルが与えられた場合、「ドット」で構成される各下位レベルのノードは高密度領域を表します。ノードのレベルが上がると、そのようなノードは「ドット」の密度の低い領域を表します

于 2008-12-10T13:31:32.700 に答える
6

形態学的アプローチはどうですか？

しきい値処理された画像を（ドットのターゲット密度に応じて）いくつかの数だけ拡張すると、クラスター内のドットが単一のオブジェクトとして表示されます。

OpenCVは、形態学的操作をサポートします（さまざまな画像処理ライブラリと同様）。

http://www.seas.upenn.edu/~bensapp/opencvdocs/ref/opencvref_cv.htm#cv_imgproc_morphology

于 2008-12-10T13:38:00.987 に答える
4

これは本当に学術的な質問のように聞こえます。

頭に浮かぶ解決策には、r* ツリーが含まれます。これにより、全体の領域が、個別にサイズ設定され、場合によっては重なり合うボックスに分割されます。これを行った後、平均距離を計算することで、各ボックスが「クラスター」を表しているかどうかを判断できます。

R*ツリー

そのアプローチの実装が困難になった場合は、データグリッドを同じサイズのサブディビジョンに分割し、それぞれにクラスターが発生するかどうかを判断することをお勧めします。ただし、このアプローチではエッジ条件に非常に注意する必要があります。最初の分割の後、定義されたエッジの特定のしきい値内のデータポイントを使用して領域を再結合することをお勧めします。

于 2008-12-10T14:02:38.490 に答える
3

「特定の高密度の領域」とは、単位面積あたりのドットの数がおおよそ知っていることを意味します。これにより、グリッドアプローチに進みます。このアプローチでは、合計領域を適切なサイズのサブ領域に分割し、各領域のドット数をカウントします。しきい値の近くにグリッドの領域が見つかったら、グリッドの隣接する領域も検索できます。

于 2008-12-10T13:40:48.580 に答える
3

これを研究論文として整理させてください

を。問題文

Epagaの言葉を引用すると、「この領域に「ドット」が分布している 2D 領域があります。現在、ドットの「クラスタ」、つまり特定の高密度のドットがある領域を検出しようとしています。

ドットが画像からのものであるとはどこにも言及されていないことに注意してください。(ただし、それらは 1 つとして注文できます)。

b.方法 ケース 1: 点が単純な点の場合 (点 = 2D 空間の点)。このシナリオでは、すべてのポイントの x と y の両方の位置が既に存在します。問題は、ポイントのクラスタリングの 1 つに縮小されます。Ivanは解決策を提案する素晴らしい仕事をしました。彼はまた、同様の味の他の回答をまとめました。彼の投稿に加えて私の 2 点は、アプリオリにクラスターの数を知っているかどうかを検討することです。アルゴリズム (それに応じて、教師ありクラスタリングと教師なしクラスタリングを選択できます)。

ケース 2: ポイントが実際に画像に由来する場合。ここで問題を明確にする必要があります。この画像を使って説明しましょう代替テキスト ドットのグレー値に区別がない場合、グループ 1、2、3、4、および 5 はすべて「別個のクラスター」です。ただし、グレー値に基づいて区別する場合、ドットのグレー値が異なるため、クラスター 5 は注意が必要です。

とにかく、この問題は、画像をラスタースキャンし、非ゼロ (非白) ピクセルの座標を保存することで、ケース 1 に減らすことができます。その後、以前に提案されたクラスタリング アルゴリズムを使用して、クラスタの数とクラスタの中心を計算できます。

于 2010-09-01T14:34:55.927 に答える
3

ドットとクラスターの間にどれだけの間隔があるかによると思います。距離が大きくて不規則な場合は、最初にポイントを三角測量してから、統計的に大きな辺の長さを持つすべての三角形を削除/非表示にします。残りの部分三角形分割は、任意の形状のクラスターを形成します。これらのサブ三角形分割のエッジをトラバースすると、各クラスターにある特定のポイントを決定するために使用できるポリゴンが生成されます。多角形は、必要に応じて、Kent Fredric のトーラスなどの既知の形状と比較することもできます。

IMO、グリッドメソッドは迅速で汚いソリューションには適していますが、まばらなデータではすぐに空腹になります。四分木の方が優れていますが、より複雑な分析には TIN が個人的にお気に入りです。

于 2008-12-10T14:46:43.953 に答える
0

各ポイントから他のすべてのポイントまでの距離を計算します。次に、距離を並べ替えます。互いに距離がしきい値を下回っているポイントは、ニアと見なされます。互いに近いポイントのグループはクラスターです。

問題は、人間がグラフを見るとクラスターが明確である可能性があるが、明確な数学的定義がないことです。近いしきい値を定義する必要があります。おそらく、アルゴリズムの結果がクラスター化されていると感じるものと（多かれ少なかれ）等しくなるまで、経験的に調整します。

于 2008-12-10T13:37:20.070 に答える
0

Accusoft Pegasus の ImagXpress のような簡単ですぐに使えるソリューションを試しましたか?

BlobRemoval メソッドは、ピクセル数と密度を調整して、連続していない場合でもパンチ穴を見つけることができます。(隙間を埋めるために膨張機能を試すこともできます)

ほとんどの場合、コードや科学をほとんど使わずに、少し遊んでみるだけで、必要な結果が得られる可能性があります。

C#:
public void DocumentBlobRemoval( Rectangle Area, int MinPixelCount, int MaxPixelCount, short MinDensity )

于 2009-06-15T18:41:36.383 に答える
0

Cluster 3.0 には、統計的クラスタリングを行うための C メソッドのライブラリが含まれています。ドットクラスターがどのような形をとっているかに応じて、問題を解決する場合としない場合があるいくつかの異なる方法があります。ライブラリはここから入手でき、 Python ライセンスの下で配布されます。

于 2009-02-25T12:32:05.997 に答える
0

プレーンに論理グリッドを重ねることができます。グリッドに特定の数のドットが含まれている場合、そのグリッドは「密」であると見なされ、細くすることができます。これは、クラスタの許容値を扱うときに、GIS アプリケーションでよく行われます。グリッドを使用すると、間引きアルゴリズムを区分化するのに役立ちます。

于 2008-12-10T14:02:17.100 に答える
0

これには遺伝的アルゴリズムを使用できます。たとえば、「クラスター」をドット密度の高い長方形のサブエリアとして定義すると、「ソリューション」の初期セットを作成できます。各ソリューションは、いくつかのランダムに生成された重複しない長方形のクラスターで構成されます。 . 次に、各ソリューションを評価する「適合関数」を記述します。この場合、適合関数は、各クラスター内のドット密度を最大化しながら、クラスターの総数を最小化する必要があります。

あなたの最初の一連の「解決策」はおそらくすべてひどいものになるでしょう。フィットネス関数を使用して最悪のソリューションを排除し、最後の世代の「勝者」を交​​配して次世代のソリューションを作成します。このプロセスを世代ごとに繰り返すことで、この問題に対する 1 つまたは複数の適切な解決策が得られるはずです。

遺伝的アルゴリズムが機能するためには、問題空間に対するさまざまな可能な解が、問題をどれだけうまく解決できるかという点で、互いに段階的に異なる必要があります。ドット クラスターはこれに最適です。

于 2008-12-10T14:30:25.173 に答える