检测点“簇”的算法
image-processing
6
0

我有一个二维区域,在该区域上分布有“点”。我现在正在尝试检测点的“簇”,即具有一定密度的点的区域。

是否有任何想法(或带有想法的文章链接)如何优雅地检测这些区域?

参考资料:
Stack Overflow
收藏
评论
共 10 个回答
高赞 时间 活跃

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

或者,更明确地说:给定四叉树和级别顺序遍历,由“点”组成的每个较低级别的节点将代表一个高密度区域。随着节点级别的增加,此类节点表示“点”的较低密度区域

收藏
评论

“具有一定高密度的区域”意味着您知道大约每单位面积有多少个点被认为很高。这将我引向一种网格方法,在该方法中,您将总面积分成适当大小的子区域,然后计算每个区域中的点数。找到阈值附近的网格区域后,您也可以搜索网格的相邻区域。

收藏
评论

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

这是一个很好的处理过程,也许以后我会发布解决方案。

编辑:

这里是:

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

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

收藏
评论

让我整理一下作为研究论文

一个。问题陈述

引用Epaga的话 :“我有一个二维区域,在该区域上分布有“点”。我现在正在尝试检测点的“簇”,即具有一定密度的点的区域。

请注意,在任何地方都没有提到点来自图像。 (尽管可以将它们作为一体订购)。

b。方法案例1:如果点仅是点(点= 2D空间中的点)。在这种情况下,您将已经拥有所有点的x和y位置。问题减少到聚类点之一。 伊万在提出解决方案方面做得很出色。他还总结了类似味道的其他答案。除了他的文章外,我的2cts还考虑您是否知道先验的簇数。算法(可以选择监督的聚类还是非监督的聚类)。

情况2:如果这些点确实来自图像。这里问题需要澄清。让我解释一下使用这张图片替代文字如果在点的灰度值上没有区别,则组1、2、3、4和5都是“不同的簇”。但是,如果根据灰度值进行区分,则簇5会比较棘手,因为点具有不同的灰度值。

无论如何,通过光栅扫描图像并存储非零(非白色)像素的坐标,可以将此问题减少到情况1。然后,可以采用较早提出的聚类算法来计算聚类和聚类中心的数量。

收藏
评论

为了在Trebs声明中增加一些帮助,我认为重要的是首先切实地定义集群的定义,当然,“点靠得很近”,那是相当大的。

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

但是,以编程方式识别此“集群”可能很困难。

人类可能认为这是一个较大的环形星团,但是您的自动化程序更有可能将其确定为一系列近距离较小的星团。

另外,请注意,存在超高密度区域,这些区域在更大的范围内只是分散注意力

您需要考虑这种行为,并可能将密度相似的簇链接在一起,这些簇仅由较低密度的无关紧要的空隙隔开,具体取决于特定的应用。

无论您开发什么,我至少都会对它如何识别此集合中的数据感兴趣。

(我认为研究HDRI ToneMapping背后的技术可能是有条理的,因为这些技术或多或少地在光密度上起作用,并且有“本地”色调图和“全局”色调图,每种产生不同的结果。)

收藏
评论
  1. 将概率密度函数拟合到数据。我将使用“高斯混合”,并使用由K-means算法引发的期望最大化学习进行拟合。如果没有EM,则K均值本身有时就足够了。群集数量本身需要使用模型顺序选择算法进行填充。
  2. 然后,可以使用模型对每个点进行p(x)评分。即获得该点由模型生成的后验概率。
  3. 找出最大值p(x)以找到聚类质心。

可以使用机器学习工具箱在Matlab之类的工具中对此进行快速编码。 MoG / EM学习/ K-Means聚类在Web /标准文本中进行了广泛讨论。我最喜欢的文本是Duda / Hart的“模式分类”。

收藏
评论

形态学方法怎么样?

将阈值图像扩大一定数量(取决于点的目标密度),然后群集中的点将显示为单个对象。

OpenCV支持形态操作(以及一系列图像处理库):

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

收藏
评论

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

现在,“较暗”区域将标识点簇。

收藏
评论

这确实听起来像是一个学术问题。

我想到的解决方案涉及r *树。这会将您的总面积划分为各个大小和可能重叠的框。完成此操作后,您可以通过计算平均距离来确定每个方框是否代表一个“集群”。

R *树

如果这种方法难以实施,则最好将数据网格划分为相等大小的细分,然后确定每个细分中是否都存在集群;但是,使用这种方法必须非常注意边缘条件。我建议您在进行初始划分之后,遍历并在定义的边缘的某个阈值内用数据点重新组合区域。

收藏
评论

我建议使用均值漂移核来找到点的密度中心。

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

该图显示了均值漂移核(最初位于群集的边缘中心)朝群集的最高密度点收敛。

理论上(简而言之):

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

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

均值平移是一种迭代方法,该方法使用称为内核的像素邻域(与类似),并使用它来计算基础图像数据的均值 。在这种情况下, 平均是内核坐标的像素加权平均。

在每次迭代中, 内核的均值定义了下一次迭代的中心坐标,这称为shift 。因此,名称为mean-shift 。迭代的停止条件是当移位距离降至0时(即我们位于附近最密集的位置)。

此ppt演示中可以找到有关均值漂移的全面介绍(无论是理论上还是应用上)

在实践中:

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

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

O'Reilly的Learning OpenCv(Google书籍摘录)也对它的工作方式进行了很好的解释。基本上只将其输入您的点图像(prob_image)。

实际上,诀窍是选择适当的内核大小 。内核越小,就越需要将其启动到集群。内核越大,初始位置可以越随机。但是,如果图像中有多个点簇,则内核可能会在它们之间收敛。

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号