如何将二维掩码数组分割为独立连通段并分别标注

我需要处理由随机位置分布的1和0构成的数组，将数组中所有由1组成的连通簇分离出来并分别标注，该需求可通过示例直观理解：左侧为示例输入，右侧为示例输出。

我编写了一个本质为连通簇填充的递归函数实现该功能：遍历输入数组，当检测到未被标记的1时，调用该递归函数填充整个连通簇，对应的Python代码如下：

def search(i,j,dmask,lbls,lbl):
    lbls[i,j] = lbl
    if (i-1 < dmask.shape[0]) & (j-1 < dmask.shape[1]) & (i-1 >= 0) & (j-1 >= 0):
        if  (dmask[i-1,j-1] == 1) & (lbls[i-1,j-1] == 0):
            search(i-1,j-1,dmask,lbls,lbl)

    if (i-1 < dmask.shape[0]) & (j < dmask.shape[1]) & (i-1 >= 0) & (j >= 0):
        if (dmask[i-1,j] == 1) & (lbls[i-1,j] == 0) :
            search(i-1,j,dmask,lbls,lbl)

    if (i-1 < dmask.shape[0]) & (j+1 < dmask.shape[1]) & (i-1 >= 0 ) & ( j+1 >= 0 ):
        if ( dmask[i-1,j+1] == 1 ) & ( lbls[i-1,j+1] == 0):
            search(i-1,j+1,dmask,lbls,lbl)

    if (i < dmask.shape[0]) & (j-1 < dmask.shape[1]) & (i >= 0 ) & ( j - 1 >= 0 ):
        if (dmask[i,j-1] == 1 ) & ( lbls[i,j-1] == 0 ):
            search(i,j-1,dmask,lbls,lbl)    
            
    if (i < dmask.shape[0]) & (j+1 < dmask.shape[1]) & (i >= 0 ) & ( j+1 >= 0 ):
        if (dmask[i,j+1] == 1 ) & ( lbls[i,j+1] == 0):
            search(i,j+1,dmask,lbls,lbl)
            
    if (i+1 < dmask.shape[0]) & (j-1 < dmask.shape[1]) & (i+1 >= 0 ) & ( j-1 >= 0 ):
        if ( dmask[i+1,j-1] == 1 ) & ( lbls[i+1,j-1] == 0): 
            search(i+1,j-1,dmask,lbls,lbl)
            
    if (i+1 < dmask.shape[0]) & (j < dmask.shape[1]) & (i+1 >= 0 ) & ( j >= 0 ):
        if ( dmask[i+1,j] == 1 ) & ( lbls[i+1,j] == 0):
            search(i+1,j,dmask,lbls,lbl)
            
    if (i+1 < dmask.shape[0]) & (j+1 < dmask.shape[1]) & (i+1 >= 0 ) & ( j+1 >= 0 ):
        if (dmask[i+1,j+1] == 1 ) & ( lbls[i+1,j+1] == 0):
            search(i+1,j+1,dmask,lbls,lbl)
    return dmask,lbls

# 初始化标签
lbl = 1

# 输入数组
a = np.array([[1, 0, 0, 0, 0],
    [1, 1, 0, 0, 1],
    [1, 1, 0, 0, 0],[1,1,0,1,1],[0,0,0,1,0],[1,1,0,1,1]])

# 初始化输出数组
b = np.zeros(np.shape(a),int)

# 遍历数组，检测到未标记的1时调用递归函数
for i in np.arange(a.shape[0]):
    for j in np.arange(a.shape[1]):
        if (a[i,j] == 1) & (b[i,j] == 0):
            [c,d] = search(i,j,a,b,lbl)
            lbl += 1

该方案在小规模输入数组（例如示例图中的样例）上可正常运行，但需要将其应用于包含大尺寸连通簇的大规模数组时，运行代码会导致内核自动重启。判断问题原因是触发了递归深度限制，且已经尝试通过sys.setrecursionlimit()函数调高递归上限仍无法解决。
希望得到解决该问题的相关建议，无需手动从零实现该功能，如果有成熟的第三方库可以便捷实现该需求也完全适用。

直接用成熟库实现是效率最高、稳定性最好的选择，完全不需要自己写递归逻辑，两个常用方案任选即可：

• 方案1：用scipy的连通域标记函数，专门处理这类二值数组连通簇标注需求，性能极强，支持8邻域（即现有代码使用的对角也算连通的规则）和4邻域两种模式，代码示例：

import numpy as np
from scipy.ndimage import label

# 输入数组
a = np.array([[1, 0, 0, 0, 0],
    [1, 1, 0, 0, 1],
    [1, 1, 0, 0, 0],[1,1,0,1,1],[0,0,0,1,0],[1,1,0,1,1]])

# structure参数定义连通规则，8邻域传入3x3全1矩阵即可
labeled_array, num_clusters = label(a, structure=np.ones((3,3), dtype=int))

返回的labeled_array就是目标标注结果，每个连通簇会被标记为1、2、3…的连续整数，原0值位置保持为0，num_clusters是统计得到的总连通簇数量。该实现基于底层C代码，处理百万级以上元素的大数组也不会出现栈溢出问题，运行速度比手写Python递归快几个数量级。

• 方案2：如果是图像处理类场景，用opencv的connectedComponents函数也可以实现同等功能，同样是底层编译实现，无递归深度限制。

如果一定要自行实现逻辑，把递归版深度优先搜索改成迭代版的广度优先/深度优先搜索即可，用队列或栈存储待遍历的像素坐标，完全不依赖Python递归调用栈，就不会触发递归深度限制。但从实用性角度看，直接调用成熟库是最优选择，这类库的连通域实现经过了大量场景验证，边界处理和性能表现都远好于手写Python逻辑。

内容的提问来源于stack exchange，提问作者Ahsora