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

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

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

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

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

编辑:

这里是:

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

编辑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

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

        
Yikes,对于nxn点的平方,这是o(n ^ 4),或者对于较低分辨率r,o(n ^ 2*((n/r)^ 2)).好吧作为小图像的蛮力方法可能,但不是一般的解决方案. 

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

均值漂移图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).

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

        

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

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

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

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

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

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

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

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

        

4> P Daddy..：
将模糊滤镜应用于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


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

        

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

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

        

6> Ian Hopkinso..：
形态学方法怎么样？

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

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

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