算法检测和QUOT;集群＆QUOT;点 [英] Algorithm for detecting "clusters" of dots

问题描述

我有分布在这一区域点二维区域。我现在正尝试检测点的簇，即，区域与点的某些高密度

I have a 2D area with "dots" distributed on this area. I now am trying to detect "clusters" of dots, that is, areas with a certain high density of dots.

上的任何想法（或链接到文章与思想）如何优雅地检测这些方面？

Any thoughts on (or links to articles with thoughts on) how to elegantly detect these areas?

推荐答案

如何定义一个任意分辨率的空间，并在矩阵计算每个点的距离的测量从该点所有的点，那么你可以做一个热图，并使用阈值来定义的集群。

How about defining an arbitrary resolution for your space, and calculate for each point in that matrix, a measure of the distance from that point to all dots, then you could make a "heat graph" and use a threshold to define the clusters.

这是一个很好的锻炼进行处理，也许以后我会发布的解决方案。

It's a nice exercise for processing, maybe later I will post a solution.

编辑：

这是：

//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);

EDIT 2（性能稍微少低效code，但相同的输出）：

EDIT 2 (slighly less inefficient code but same output):

//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);
*/

和与输出（减少）肯特示例：

And the output with (a reduced) Kent sample:

这篇关于算法检测和QUOT;集群＆QUOT;点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！