algorithm - 用于检测点“簇”的算法

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）方法，它是mean-shift 的理论基础。

• j0rd4n和Bill the Lizard都建议将你的空间离散成块并检查它们的密度。

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

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

在每次迭代中，内核的均值定义了下一次迭代的中心坐标——这称为shift。因此名称为mean-shift。迭代的停止条件是当移动距离下降到 0 时（即我们在附近最密集的点）。

可以在这个 ppt 演示文稿中找到对均值偏移的全面介绍（理论和应用）。

在实践中：

OpenCV中提供了均值偏移的实现：

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

O'Reilly 的 Learning 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

Answer 7

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

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

R* 树

如果这种方法变得难以实施，您最好将数据网格分成大小相等的细分并确定每个细分中是否出现集群；但是，您必须非常注意这种方法的边缘条件。我建议在初始划分之后，您通过定义边缘的某个阈值内的数据点重新组合区域。

Answer 8

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

这可以使用机器学习工具箱在 Matlab 等工具中快速编码。MoG/EM 学习/K-Means 聚类在网络/标准文本中得到广泛讨论。我最喜欢的文本是 Duda/Hart 的“模式分类”。

Answer 9

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

Answer 10

我认为这取决于点和簇之间有多少分离。如果距离很大且不规则，我会首先对这些点进行三角剖分，然后删除/隐藏所有边长在统计上较大的三角形。剩余的子三角剖分形成任意形状的簇。遍历这些子三角剖分的边缘会产生多边形，这些多边形可用于确定哪些特定点位于每个集群中。根据需要，还可以将多边形与已知形状进行比较，例如 Kent Fredric 的圆环。

IMO，网格方法适用于快速和肮脏的解决方案，但在稀疏数据上很快就会变得非常饥饿。四叉树更好，但对于任何更复杂的分析，TIN 是我个人的最爱。

Answer 11

让我把它组织成一篇研究论文

一种。问题陈述

引用Epaga的话：“我有一个 2D 区域，该区域上分布着“点”。我现在正在尝试检测点的“簇”，即点的密度一定很高的区域。

请注意，没有任何地方提到这些点来自图像。（尽管它们可以作为一个订购）。

b.方法 案例1：如果点只是点（点=二维空间中的点）。在这种情况下，您将已经拥有所有点的 x 和 y 位置。问题归结为对点进行聚类之一。Ivan在提出解决方案方面做得很好。他还总结了其他类似的答案。除了他的帖子之外，我的 2cts 是您考虑是否先验地知道集群的数量。算法（可以相应地选择有监督与无监督聚类）。

情况 2：如果这些点确实来自图像。这里需要澄清问题。让我用这张图解释一下 如果不区分点的灰度值，那么组 1、2、3、4 和 5 都是“不同的簇”。但是，如果根据灰度值进行区分，则簇 5 是棘手的，因为点具有不同的灰度值。

无论如何，通过光栅扫描图像并存储非零（非白色）像素的坐标，可以将此问题简化为情况 1。如前所述，聚类算法可以用来计算聚类和聚类中心的数量。

Answer 12

我会计算从每个点到所有其他点的距离。然后对距离进行排序。彼此之间的距离低于阈值的点被视为Near。一组彼此靠近的点是一个簇。

问题是，当人们看到图表时，集群可能很清楚，但没有明确的数学定义。您需要定义您的接近阈值，可能需要根据经验对其进行调整，直到您的算法结果（或多或少）等于您认为是聚类的结果。

Answer 13

你可以在你的平面上覆盖一个逻辑网格。如果网格包含一定数量的点，则将其视为“密集”，然后可以对其进行细化。这在 GIS 应用程序中使用集群容差时会做很多事情。使用网格有助于划分细化算法。

Answer 14

您可以为此使用遗传算法。如果您将“集群”定义为具有高点密度的矩形子区域，您可以创建一组初始“解决方案”，每个解决方案都包含一些随机生成的非重叠矩形集群. 然后，您将编写一个评估每个解决方案的“适应度函数”——在这种情况下，您希望适应度函数最小化簇的总数，同时最大化每个簇中的点密度。

您最初的一组“解决方案”很可能都很糟糕，但有些可能会比其他的稍微不那么糟糕。您使用适应度函数消除最差的解决方案，然后通过杂交上一代的“赢家”来创建下一代解决方案。通过一代又一代地重复这个过程，你应该最终得到一个或多个解决这个问题的好方法。

为了使遗传算法起作用，问题空间的不同可能解决方案在解决问题的能力方面必须彼此逐渐不同。点簇非常适合这一点。

Answer 15

Cluster 3.0 包括一个用于进行统计聚类的 C 方法库。它有几种不同的方法，可能会也可能不会解决您的问题，具体取决于您的点簇采用什么形式。该库可在此处获得，并在 Python 许可下分发。

Answer 16

您是否尝试过 Accusoft Pegasus 的 ImagXpress 等简单的现成解决方案？

BlobRemoval 方法可以针对像素数和密度进行调整，以找到打孔，即使它们不是连续的。（您也可以尝试使用扩张功能来缩小差距）

在绝大多数情况下，只要稍微玩一下，你就可以得到你需要的结果，只需要很少的代码或科学。

C#:
public void DocumentBlobRemoval(矩形区域, int MinPixelCount, int MaxPixelCount, short MinDensity)