多维数组/类图像的连通分量标记

Question

问题

我正在尝试对3维以上的数组执行connected component labling。我的意思是，我的布尔数组有一个.shape，比如像(5,2,3,6,10)，它是5维的

对于2D图像（而不是我的>；3D问题），连接的组件标签将是将标签放置到连接的区域（在我的例子中是超卷）。如果两个（hpyer-）像素彼此相邻且在布尔数组中均为真，则两个（hpyer-）像素将连接起来

我已经试过了

对于2维can be done with OpenCV和最多3维，这可以通过scikit-image's{}完成。然而，我不知道如何为我的案件解决这个问题

---

为感兴趣的读者提供更多资料（但对我的问题没有帮助）：

• http://scipy-lectures.org/packages/scikit-image/auto_examples/plot_labels.html
• https://docs.opencv.org/3.0-beta/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html#connectedcomponents
• connected component labeling in python

Answer 1

如果2D中的4连接性就足够了，您可以使用最近邻树在n log n时间内获得同样是前景的相邻像素。 然后是构造图和查找连接的组件（也就是n logn，IIRC）的问题

#!/usr/bin/env python
"""
https://stackoverflow.com/questions/66724201/connected-component-labling-for-arrays-quasi-images-with-many-dimension
"""
import numpy as np
import networkx as nx

from scipy.spatial import cKDTree


def get_components(boolean_array):
    # find neighbours
    coordinates = list(zip(*np.where(boolean_array)))
    tree = cKDTree(coordinates)
    neighbours_by_pixel = tree.query_ball_tree(tree, r=1, p=1) # p=1 -> Manhatten distance; r=1 -> what would be 4-connectivity in 2D

    # create graph and find components
    G = nx.Graph()
    for ii, neighbours in enumerate(neighbours_by_pixel):
        if len(neighbours) > 1:
            G.add_edges_from([(ii, jj) for jj in neighbours[1:]]) # skip first neighbour as that is a self-loop
    components = nx.connected_components(G)

    # create output image
    output = np.zeros_like(data, dtype=np.int)
    for ii, component in enumerate(components):
        for idx in component:
            output[coordinates[idx]] = ii+1

    return output


if __name__ == '__main__':

    shape = (5, 2, 3, 6, 10)
    D = len(shape)
    data = np.random.rand(*shape) < 0.1
    output = get_components(data)

对于形状为（50，50，50，50）的阵列，我在笔记本电脑上获得以下计时：

In [48]: %timeit output = get_components(data)
5.85 s ± 279 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Answer 2

^{}直接执行您想要的操作：

In [1]: import numpy as np
In [2]: arr = np.random.random((5,2,3,6,10)) > 0.5
In [3]: from scipy import ndimage as ndi
In [4]: labeled, n = ndi.label(arr)
In [5]: n
Out[5]: 11