基于二维数组Union Find的图像白色像素聚类计数问题咨询

嘿，这个场景我太熟悉了！你要统计独立白色像素簇，本质就是连通分量标记问题，而Union-Find（并查集）刚好完美匹配你提到的Union操作需求。下面给你一步步拆解实现思路，还有可直接运行的代码示例：

我们可以遍历每个白色像素（值为1的元素），检查它的相邻像素（优先处理上、左两个方向，避免重复操作），如果相邻像素也是白色，就将当前像素与相邻像素执行Union操作。最后统计所有白色像素中独立根节点的数量，就是你要的白色簇总数。

步骤1：实现Union-Find数据结构 #

并查集需要两个核心操作：find（查找根节点，配合路径压缩优化）和union（合并两个集合）。为了方便操作，我们可以把二维数组的坐标(i,j)映射成一维索引：index = i * width + j，这样并查集可以用一维数组实现。

步骤2：遍历二维数组并执行合并 #

遍历每个像素时，只需要检查上方和左方的白色像素即可——右方和下方的像素会在后续遍历中处理，这样能避免重复合并操作，提升效率。

步骤3：统计独立簇数量 #

遍历所有白色像素，找到每个像素的根节点，用集合去重后，集合的大小就是独立白色簇的总数。

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
    
    def find(self, x):
        # 路径压缩优化，加快后续查找速度
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

def count_white_clusters(binary_image):
    if not binary_image or not binary_image[0]:
        return 0
    
    height = len(binary_image)
    width = len(binary_image[0])
    total_pixels = height * width
    uf = UnionFind(total_pixels)
    
    # 遍历每个像素
    for i in range(height):
        for j in range(width):
            if binary_image[i][j] == 1:
                current_idx = i * width + j
                # 检查上方像素
                if i > 0 and binary_image[i-1][j] == 1:
                    up_idx = (i-1)*width + j
                    uf.union(current_idx, up_idx)
                # 检查左方像素
                if j > 0 and binary_image[i][j-1] == 1:
                    left_idx = i*width + (j-1)
                    uf.union(current_idx, left_idx)
    
    # 统计独立根节点数量
    root_set = set()
    for i in range(height):
        for j in range(width):
            if binary_image[i][j] == 1:
                root = uf.find(i*width + j)
                root_set.add(root)
    
    return len(root_set)

# 测试用例
test_image = [
    [1,0,1,1],
    [1,0,0,1],
    [0,1,0,0],
    [1,1,1,0]
]
print(count_white_clusters(test_image))  # 输出：3

• 邻域选择：上面的代码用的是4邻域（上、下、左、右），如果需要支持8邻域（包含对角线像素），只需要在遍历的时候额外检查左上、右上、左下、右下的像素即可，逻辑完全一致。
• 性能优化：如果图像中黑色像素占比极高，可以只给白色像素分配并查集节点，不用为所有像素初始化，能大幅节省空间。
• 效率提升：可以在第一次遍历的时候就记录所有白色像素的索引，避免最后二次遍历整个数组，减少不必要的循环。

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