英文:
Find all disjoint subsets of a binray matrix in Pyhton
问题
我有一个二进制矩阵，我想找到存在于该矩阵中的所有不相交的子集。为了澄清问题，该矩阵是一组图像掩模，这些掩模具有不规则的形状，每个由1组成的不相交子集代表一个单独的掩模。换句话说，如果我在一个大小为d1xd2的矩阵中有N个不相交的子集，我希望最终得到N个大小为d1xd2的矩阵，每个矩阵只包含其中一个不相交子集的1。
非常感谢任何帮助。
英文:
I have a binary matrix, and I want to find all disjoint subsets that exist in this matrix. To clarify the problem, the matrix is a collection of image masks, masks of irregular shapes, and each disjoint subset of 1s representing a separate mask. In other words, if I have a collection of N disjoint subsets in a matrix of size d1xd2, I want to end up with N matrices of size d1xd2, each having only one of the disjoint subsets of 1s.
Any help on that is highly appreciated.
答案1
得分: 1
在图像处理中，你试图做的事情也被称为连通组件标记（Connected Component Labelling，CCL）。Woodford提出的泛洪填充算法是一种用于执行CCL的算法之一。
你提出的问题的一个变种已经在另一个帖子中得到了回答，该帖子使用了scipy.ndimage.label函数。以下是对那个答案的轻微修改，应该会给你提供你需要的确切结果：
import numpy as np
from scipy.ndimage import label
# 在这里定义你的矩阵
X = np.array([
# （这里是你的矩阵数据）
], dtype=int)
# 你如何定义“连接”或“不连接”？4-邻居还是8-邻居。
# https://en.wikipedia.org/wiki/Connected-component_labeling
structure = np.ones((3, 3), dtype=int)
# 执行连通组件标记
labeled, ncomponents = label(X, structure)
# 遍历每个标记的斑块
for ii in range(1, ncomponents+1):
output = np.zeros(X.shape)
output[labeled == ii] = 1
# 对每个结果斑块进行一些操作...
print(output)
英文:
In image processing, what you are trying to do is also called Connected Component Labelling (CCL). Woodford's suggestion of Flood fill algorithm is one algorithm for performing CCL.
A variation of your question is already answered in this other thread, which uses the function scipy.ndimage.label.
Here's a slight modification of that answer, which should give you exactly what you are looking for:
import numpy as np
from scipy.ndimage import label
# Define your matrix here
X = np.array([
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
], dtype=int)
# How do you define "connected" or "disjointed"? 4-neighbors vs 8-neighbors.
# https://en.wikipedia.org/wiki/Connected-component_labeling
structure = np.ones((3, 3), dtype=int)
# Perform connected component labelling
labeled, ncomponents = label(X, structure)
# Iterate through each labelled blob
for ii in range(1, ncomponents+1):
output = np.zeros(X.shape)
output[labeled == ii] = 1
# Do something to each resulting blob...
print(output)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论