用于检测点的"簇"的算法

Question

我在这个区域有一个带有"点"的2D区域.我现在正试图检测点的"簇",即具有一定高密度点的区域.

有关如何优雅地检测这些区域的任何想法(或链接到有想法的文章)？

Answer 1

如何为您的空间定义任意分辨率,并计算该矩阵中的每个点,从该点到所有点的距离的度量,然后您可以制作"热图"并使用阈值来定义集群.

这是一个很好的处理练习,也许以后我会发布一个解决方案.

编辑:

这里是:

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

和(减少的)肯特样本的输出:

Answer 2

我建议使用均值平移内核来找到点的密度中心.

均值漂移图http://cvr.yorku.ca/members/gradstudents/kosta/compvis/file_mean_shift_path.gif

该图显示了平均移位内核(最初以簇的边缘为中心)朝向簇的最高密度点收敛.

理论上(简而言之):

这个问题的几个答案已经暗示了这种方法的平均转变方式:

• P Daddy模糊图像并找到最暗点实际上是核密度估计(KDE)方法,它是均值漂移的理论基础.

• 无论j0rd4n和比尔蜥蜴建议将离散的空间分成块,并检查它们的密度.

您在动画图中看到的是这两个建议的组合:它使用移动的"块"(即内核)来寻找局部最高密度.

均值漂移是一种迭代方法,它使用称为内核的像素邻域(类似于此)并使用它来计算底层图像数据的平均值.该平均在这方面是内核坐标的像素加权平均值.

在每次迭代中,内核的均值定义了下一次迭代的中心坐标 - 这称为移位.因此名称平均移位.迭代的停止条件是当移位距离下降到0时(即,我们处于邻域中最密集的点).

本ppt演示文稿中可以找到对均值漂移(理论和应用)的全面介绍.

在实践中:

OpenCV中提供了均值漂移的实现:

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

O'Reilly的学习OpenCv(谷歌书籍摘录)也有一个很好的解释它是如何工作的.基本上只是喂你的点图像(prob_image).

实际上,诀窍是选择足够的内核大小.内核越小,就越需要将其发送到集群.内核越大,初始位置就越随机.但是,如果图像中有多个点簇,则内核可能会在它们之间汇聚.

Answer 3

为了给Trebs语句添加一些助手,我认为现实地首先定义一个集群的定义是肯定的,"点靠近在一起",这很重要.

拿这个我生成的样本集,我知道那里有一个簇形状,我创建了它.

但是,以编程方式识别此"群集"可能很难.

人类可能认为是一个大的环形星团,但是你的自动程序更有可能决定它是半近距离的一系列较小的星团.

此外,请注意,存在超高密度区域,这些区域在更大的图景中,仅仅是分心

您需要考虑这种行为,并可能将相似密度的簇链接在一起,这些簇仅由较低密度的微小空隙分开,具体取决于具体应用.

无论你开发什么,我至少会对它如何识别这一组中的数据感兴趣.

(我认为研究HDRI ToneMapping背后的技术可能是有序的,因为它们或多或少地对光密度起作用,并且有"本地"色调图和"全局"色调图,每个都产生不同的结果)

Answer 4

将模糊滤镜应用于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

"黑暗"区域现在识别出点簇.

Answer 5

您可以尝试创建数据的四叉树表示.图中较短的路径对应于高密度区域.

或者,更清楚地说明:给定四叉树和水平顺序遍历,由"点"组成的每个低级节点将代表高密度区域.随着节点级别的增加,这些节点代表"点"的低密度区域

Answer 6

形态学方法怎么样？

将阈值图像扩展一些数字(取决于点的目标密度),然后聚类中的点将显示为单个对象.

OpenCV支持形态学操作(与一系列图像处理库一样):

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