2

我有一个 x，y 坐标列表

我需要做的是将它们分成连续区域的组

在此处输入图像描述

列表中的所有 x、y 坐标最终都属于特定组。

我目前有一个简单的算法，它只遍历每个点并找到所有相邻点（所以点在 x 上的坐标为 +-1，在 y 上的坐标为 +-1）但是，在使用大时它太慢了x,y 列表。

PS 请记住，组中间可能有孔。

4

3 回答 3

2

您要做的就是在图像处理中寻找连通分量。您有一个二进制图像，其中列表中的所有 (x, y) 像素都是 1，而不是 0。

您可以使用 numpy/scipy 将数据转换为 2D 二进制图像，然后调用 ndimage.label 查找连接的组件。

假设所有 x 和 y 都 >= 0，你知道 max_x 和 max_y，并且生成的图像适合内存，那么类似于：

import numpy as np
from scipy import ndimage

image = np.zeros(max_x, max_y)
for x, y in huge_list_of_xy_points:
    image[x, y] = 1

labelled = ndimage.label(image)

应该给你一个数组，其中第 1 组中的所有像素都有值 1，第 2 组中的所有像素都有值 2，等等。未测试。

于 2013-10-25T18:57:58.800 回答
2

您可以使用的一种简单方法是k-means clustering。k -means 将观察列表划分为k集群，其中每个点都属于具有最接近平均值的集群。如果您知道k=2有点组，那么这种方法应该会很好地工作，假设您的点簇被合理地分开（即使它们有孔）。SciPy 有一个易于应用的 k-means 实现。

这是您可以执行的分析类型的示例。

# import required modules
import numpy as np
from scipy.cluster.vq import kmeans2

# generate clouds of 2D normally distributed points
N = 6000000 # number of points in each cluster

# cloud 1: mean (0, 0)
mean1 = [0, 0]
cov1  = [[1, 0], [0, 1]]
x1,y1 = np.random.multivariate_normal(mean1, cov1, N).T

# cloud 2: mean (5, 5)
mean2 = [5, 5]
cov2  = [[1, 0], [0, 1]]
x2,y2 = np.random.multivariate_normal(mean2, cov2, N).T

# merge the clouds and arrange into data points
xs, ys = np.concatenate( (x1, x2) ), np.concatenate( (y1, y2) )
points = np.array([xs, ys]).T

# cluster the points using k-means
centroids, clusters = kmeans2(points, k=2)

在我 2012 年的 MBA 上运行这个具有 1200 万个数据点的速度非常快：

>>> time python test.py

real    0m20.957s
user    0m18.128s
sys     0m2.732s

它也是 100% 准确的（考虑到点云根本不重叠，这并不奇怪）。这是一些用于计算集群分配准确性的快速代码。唯一棘手的部分是我首先使用欧几里德距离来确定哪个集群的质心与原始数据云的平均值相匹配。

# determine which centroid belongs to which cluster
# using Euclidean distance
dist1 = np.linalg.norm(centroids[0]-mean1)
dist2 = np.linalg.norm(centroids[1]-mean1)
if dist1 <= dist2:
    FIRST, SECOND = 0, 1
else:
    FIRST, SECOND = 1, 0

# compute accuracy by iterating through all 2N points
# note: first N points are from cloud1, second N points are from cloud2
correct = 0
for i in range(len(clusters)):
    if clusters[i] == FIRST and i < N:
        correct += 1    
    elif clusters[i] == SECOND and i >= N:
        correct += 1

# output accuracy
print 'Accuracy: %.2f' % (correct*100./len(clusters))
于 2013-10-25T17:57:09.570 回答
0

首先，您可以通过相应的图表来识别问题G(V, E)：

点是顶点，当且仅当“接近”到时，点和点e之间存在边，您可以在其中自行定义“接近”。ABAB

由于每个点都属于一个组，因此组形成不相交的集合，您可以使用简单的DFS将点分配给组。在图论中，底层问题称为Connected Components。

DFS 的复杂性是线性的，即O(V + E)。

于 2013-10-25T18:06:10.807 回答