用于检测点“簇”的algorithm
我有一个分布在这个区域的“点”的2D区域。 我现在正在尝试检测点的“簇”，即具有一定高密度点的区域。
任何想法（或带有想法的文章的链接）如何优雅地检测这些区域？
如何为你的空间定义一个任意的分辨率，并计算该matrix中的每个点，从该点到所有点的距离的一个度量，然后你可以制作一个“热图”，并使用一个阈值来定义这个簇。
这是一个很好的练习，也许以后我会发布一个解决scheme。
编辑：
这里是：
//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); */
和（减less的）肯特样本的输出：
我会build议使用一个平均移位内核来find你的点的密度中心。
Mean-shift插图http://cvr.yorku.ca/members/gradstudents/kosta/compvis/file_mean_shift_path.gif
这个图显示了一个平均移位核心（最初集中在簇的边缘）朝向簇的最高密度点汇聚。
理论上（简而言之）：
这个问题的几个答案已经暗示了这样做的意思转变的方式：
-
P爸爸模糊图像，find最黑暗的地方实际上是核密度估计 （KDE）方法，这是平均移位的理论基础。
-
j0rd4n和Bill蜥蜴都build议把你的空间分解成块并检查它们的密度。
你在animation中看到的是这两个build议的结合：它使用一个移动的“块”（即内核）来寻找当地最高的密度。
均值偏移是一种迭代方法，它使用一个称为内核的像素邻域（类似于这个像素），并使用它来计算底层图像数据的平均值 。 这里的平均值是内核坐标的像素加权平均值。
在每次迭代中， 内核的均值定义了下一次迭代的中心坐标 – 这就是所谓的偏移 。 因此，这个名字意味着转变 。 迭代的停止条件是移位距离下降到0（即我们在邻域中最密集的点）。
在这个ppt的介绍中可以find关于均值漂移（在理论和应用上）的全面介绍。
在实践中：
在OpenCV中可以使用Mean-Shift的实现：
int cvMeanShift( const CvArr* prob_image, CvRect window, CvTermCriteria criteria, CvConnectedComp* comp );
O'Reilly的学习OpenCv（谷歌书摘）也有一个很好的解释，如何工作。 基本上只喂它你的点图像（prob_image）。
在实践中，诀窍是select足够的内核大小 。 内核越小，启动到集群的距离就越近。 内核越大，初始位置越可能随机。 但是，如果图像中有多个点群，则内核可能会在它们之间进行合并。
为了给Trebs声明增加一些助手，我认为重要的是首先定义一个集群的定义是什么，当然，“点靠得更近”，这是相当大的。
以我生成的这个样本集，我知道那里有一个集群形状，我创build了它。
但是，编程识别这个“集群”可能很难。
一个人可能认为是一个大的环形星团，但是你的自动化程序更有可能将它确定为一系列半接近的小星团。
另外，请注意，有一些超高密度的区域，这些区域在更大的情况下，只是分散注意力
您需要考虑这种行为，并且可能将类似密度的聚类连锁在一起，这些聚类只能由密度较小的微小空隙分开，这取决于具体的应用。
无论您开发什么，我至less会对如何识别这组数据感兴趣。
（我认为考虑HDRI ToneMapping背后的技术可能是有序的，因为这些技术对光密度的影响或多或less，并且存在“本地”色调图和“全局”色调图，每个产生不同的结果）
将模糊滤镜应用于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
现在，“黑暗”区域可以识别点群。
您可以尝试创build数据的四叉树表示。 图中较短的path将对应于高密度区域。
或者，更清楚地说明：在四叉树和水平遍历的情况下，由“点”组成的每个底层节点将代表高密度区域。 随着节点的等级增加，这样的节点代表“点”的较低密度区域，
这里有一个很好的聚类algorithm教程，他们讨论K-means和K-gaussians。
如何形态学方法？
将阈值图像扩大一些数量（取决于目标点的密度），则群集中的点将显示为单个对象。
OpenCV支持形态学操作（就像一系列image processing库一样）：
http://www.seas.upenn.edu/~bensapp/opencvdocs/ref/opencvref_cv.htm#cv_imgproc_morphology
这听起来像是一个学术问题。
想到的解决scheme涉及r *树。 这将您的总面积分为单独的大小和可能重叠的框。 做完这些之后，你可以通过计算平均距离来确定每个盒子是否代表一个“聚类”。
R *树
如果这种方法变得难以实现，你最好把你的数据网格分成相同大小的子部分，并确定每个部分是否发生了一个集群; 尽pipe如此，您仍然必须非常注意边缘条件。 我build议在最初的划分之后，通过在定义边界的某个阈值内重新组合数据点的区域。
- 拟合数据的概率密度函数。 我将使用“混合高斯”，并使用由K-meansalgorithm启动的期望最大化学习进行拟合。 没有EM，K-means本身有时是足够的。 簇的数量本身需要用模型顺序selectalgorithm来引发。
- 然后，使用模型可以用p（x）对每个点进行评分。 即得到该模型生成的点的后验概率。
- find最大的p（x）来find集群质心。
这可以使用机器学习工具箱在像Matlab这样的工具中非常快地编码。 MoG / EM学习/ K均值聚类在Web /标准文本中被广泛讨论。 我最喜欢的文字是Duda / Hart的“模式分类”。
“具有一定高密度的区域”意味着你大概知道你认为每单位面积有多less个点。 这导致我走向一个网格方法，在这里你将总面积分成合适大小的子区域，然后计算每个区域的点数。 一旦你发现你的网格附近的区域，你也可以search网格的邻近区域。
让我把它作为一个研究论文
一个。 问题陈述
引用Epaga的话说 ：“我在这个区域有一个分布有”点“的二维区域，现在我正在尝试检测点的”聚类“，即具有一定高密度点的区域。
请注意，这里没有提到点是来自图像。 （虽然他们可以被定为一个）。
b。方法 1：如果点只是点（点=二维空间中的点）。 在这种情况下，您已经拥有所有点的x和y位置。 问题归结为集中点之一。 伊万提出了一个很好的解决scheme。 他还总结了类似风味的其他答案。 除了他的post之外，我的两件事是，你考虑你是否知道聚类的数量。 algorithm（监督与非监督聚类可以相应地select）。
情况2：如果这些点确实来自图像。 这个问题需要澄清。 让我解释一下使用这个图像 
如果没有区分点的灰度值，则组1,2,3,4和5都是“不同的簇”。 但是，如果根据灰度值进行区分，则群5很棘手，因为点具有不同的灰度值。
无论如何，通过光栅扫描图像并存储非零（非白色）像素的坐标，可以将这个问题简化为情况1。 如前所述，聚类algorithm可以用来计算聚类和聚类中心的数量。
我认为这取决于点和群之间有多less分离。 如果距离很大并且不规则，我会先对这些点进行三angular测量 ，然后删除/隐藏所有具有统计上较大边长的三angular形。 其余的子三angular形形成任意形状的群集。 遍历这些子三angular形的边可以得到多边形，可以用来确定每个聚类中的哪些特定点。 也可以根据需要比较多边形的形状，如Kent Fredric的圆环。
国际海事组织（IMO）的网格方法适用于快速和肮脏的解决scheme，但对于稀疏的数据很快就会非常饥饿。 四叉树更好，但TIN是我个人最喜欢的任何更复杂的分析。
我会计算从每个点到所有其他点的距离。 然后sorting距离。 距离彼此距离低于阈值的点被认为是近点 。 一组彼此靠近的点是一个簇。
问题在于当他看到这个图时簇可能对人是清楚的，但是没有明确的math定义。 你需要定义你的近似阈值，可能是用经验来调整它，直到你的algorithm的结果（或多或less）等于你所认为的聚类。
你可以在你的飞机上覆盖一个逻辑网格。 如果一个网格包含一定数量的包含点，则认为它是“密集的”，然后可以被细化。 在处理群集公差时，这在GIS应用程序中做了很多工作。 使用网格有助于划分你的细化algorithm。
你可以使用遗传algorithm。 如果将“聚类”定义为具有高点密度的矩形子区域，则可以创build一组“初始解”，每个“解”包含若干个随机生成的非重叠矩形聚类。 然后，您将编写一个“适应度函数”来评估每个解决scheme – 在这种情况下，您将希望适应度函数最小化群集总数，同时最大化每个群集内的点密度。
你最初的“解决scheme”将会很糟糕，很可能，但有些可能会比其他scheme稍差。 您使用适应度函数来消除最差的解决scheme，然后通过交叉繁殖上一代的“优胜者”来创build下一代解决scheme。 通过一代又一代地重复这个过程，你最终应该得到一个或多个解决这个问题的好方法。
对于一个遗传algorithm的工作来说，问题空间的不同可能的解决scheme在解决问题的能力方面必须逐渐地不同。 点群是完美的。
Cluster 3.0包含一个用于进行统计聚类的C方法库。 它有几种不同的方法，可能会或可能不会解决你的问题，在你的点群上采取什么forms。 该库在这里可用，并在Python许可下分发。
您是否尝试过像Accusoft Pegasus这样简单的现成解决scheme，如ImagXpress？
BlobRemoval方法可以调整像素数量和密度来查找打孔，即使它们不是连续的。 （你也可以尝试一个扩张function来弥补差距）
稍微玩一下，你就可以在绝大多数的情况下得到你需要的结果，只需很less的代码或科学。
C＃：
public void DocumentBlobRemoval（Rectangle Area，int MinPixelCount，int MaxPixelCount，short MinDensity）
