如何在2D numpy数组中找到聚类大小?

15

我的问题如下,

我有一个二维numpy数组,其中填充了0和1,并具有吸收边界条件(所有外部元素均为0),例如:

[[0 0 0 0 0 0 0 0 0 0]
 [0 0 1 0 0 0 0 0 0 0]
 [0 0 1 0 1 0 0 0 1 0]
 [0 0 0 0 0 0 1 0 1 0]
 [0 0 0 0 0 0 1 0 0 0]
 [0 0 0 0 1 0 1 0 0 0]
 [0 0 0 0 0 1 1 0 0 0]
 [0 0 0 1 0 1 0 0 0 0]
 [0 0 0 0 1 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0]]

我想创建一个函数,它接受这个数组和它的线性维度 L 作为输入参数(在这种情况下 L = 10),并返回该数组的群集大小列表。

所谓的“群集”,是指该数组中元素1的孤立分组。

如果所有相邻的元素都是零,则数组元素 [ i ] [ j ] 是孤立的;其相邻元素是:

[i+1][j]
[i-1][j]
[i][j+1]
[i][j-1]

因此,在先前的数组中,我们有7个大小为(2,1,2,6,1,1,1)的聚类。

我尝试通过创建两个函数来完成此任务,第一个是递归函数:

def clust_size(array,i,j):

    count = 0

    if array[i][j] == 1:

        array[i][j] = 0

        if array[i-1][j] == 1:

            count += 1
            array[i-1][j] = 0
            clust_size(array,i-1,j)

        elif array[i][j-1] == 1:

            count += 1
            array[i-1][j] = 0
            clust_size(array,i,j-1)

        elif array[i+1][j] == 1:

            count += 1
            array[i-1][j] =  0
            clust_size(array,i+1,j)

        elif array[i][j+1] == 1:

            count += 1
            array[i-1][j] = 0
            clust_size(array,i,j+1)

    return count+1         

它应该返回一个集群的大小。每当函数找到一个等于1的数组元素时,它就会增加计数器“count”的值并将元素的值更改为0,以此方式每个'1'元素只被计算一次。 如果元素的任一邻居等于1,则函数会在该元素上调用自身。

第二个函数是:

def clust_list(array,L):

    sizes_list = []

    for i in range(1,L-1):
        for i in range(1,L-1):

           count = clust_size(array,i,j)

           sizes_list.append(count)

    return sizes_list

它应该返回包含集群大小的列表。for循环从1到L-1迭代,因为所有外部元素都为0。

这不起作用,我看不出错误在哪里...

我想知道是否有更简单的方法可以完成它。

4个回答

20

看起来像是渗透问题。 如果您已经安装了scipy,以下链接将为您提供答案。

http://dragly.org/2013/03/25/working-with-percolation-clusters-in-python/

from pylab import *
from scipy.ndimage import measurements

z2 = array([[0,0,0,0,0,0,0,0,0,0],
    [0,0,1,0,0,0,0,0,0,0],
    [0,0,1,0,1,0,0,0,1,0],
    [0,0,0,0,0,0,1,0,1,0],
    [0,0,0,0,0,0,1,0,0,0],
    [0,0,0,0,1,0,1,0,0,0],
    [0,0,0,0,0,1,1,0,0,0],
    [0,0,0,1,0,1,0,0,0,0],
    [0,0,0,0,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0]])

这将识别集群:

lw, num = measurements.label(z2)
print lw
array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
   [0, 0, 1, 0, 2, 0, 0, 0, 3, 0],
   [0, 0, 0, 0, 0, 0, 4, 0, 3, 0],
   [0, 0, 0, 0, 0, 0, 4, 0, 0, 0],
   [0, 0, 0, 0, 5, 0, 4, 0, 0, 0],
   [0, 0, 0, 0, 0, 4, 4, 0, 0, 0],
   [0, 0, 0, 6, 0, 4, 0, 0, 0, 0],
   [0, 0, 0, 0, 7, 0, 0, 0, 0, 0],
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

以下将计算它们的面积。

area = measurements.sum(z2, lw, index=arange(lw.max() + 1))
print area
[ 0.  2.  1.  2.  6.  1.  1.  1.]
这会得到你所期望的结果,尽管我认为你通过“眼渗透法”应该会看到一个由8个成员组成的簇。

4
我认为你在寻找“簇”的问题本质上与在二进制图像(值为0或1)上基于4连通性查找连接组件的问题相同。您可以在此Wikipedia页面中看到几个算法来识别连接组件(或您定义的“簇”):

http://en.wikipedia.org/wiki/Connected-component_labeling

一旦连接的组件或“簇”被标记,您可以轻松地找到任何您想要的信息,包括区域,相对位置或任何其他信息。


0

我认为你的方法几乎是正确的,除了每次递归调用函数clust_size时都要重新初始化变量count。我建议将计数变量添加到输入参数clust_size中,并在嵌套循环的第一次调用中使用count = 0重新初始化。

这样,您永远会像这样调用clust_sizecount=clust_size(array, i ,j, count)。虽然我没有测试过它,但我认为这应该行得通。

希望能有所帮助。


-2

如果将此转换为字符串,则相对简单的问题。

import numpy as np                                       
arr=np.array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],           
              [0, 0, 1, 0, 0, 0, 0, 0, 0, 0,],           
              [0, 0, 1, 1, 1, 1, 1, 1, 1, 0,],   #modified        
              [0, 0, 0, 0, 0, 0, 1, 0, 1, 0,],           
              [0, 0, 0, 0, 0, 0, 1, 0, 0, 0,],           
              [0, 0, 0, 0, 1, 0, 1, 0, 0, 0,],           
              [0, 0, 0, 0, 0, 1, 1, 0, 0, 0,],           
              [0, 0, 0, 1, 0, 1, 0, 0, 0, 0,],           
              [0, 0, 0, 0, 1, 0, 0, 0, 0, 0,],           
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])           

arr = "".join([str(x) for x in arr.reshape(-1)])         
print [len(x) for x in arr.replace("0"," ").split()] 

输出

[1, 7, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1] #Cluster sizes

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接