numpy:在方阵中寻找不重叠块

Question

用一个例子介绍我的问题:我有一个numpy矩阵。

     1 . . 1 .
     . 1 . . 1
A =  . . 1 . 1 
     1 . . 1 .
     . 1 1 . 1

为了更好的视觉清晰度，我用点来表示零。只要跟踪矩阵，我就可以自由地重新排序矩阵的行和列，这表明它可以用块形式表示：

     1 1 . . .
     1 1 . . .
B =  . . 1 1 . 
     . . 1 1 1
     . . . 1 1

很明显，这个矩阵由两个不重叠的块组成，

1 1         1 1 .
1 1   and   1 1 1
            . 1 1

用指数B[0:2,0:2]和B[2:5,2:5]。

是否有一种通用的方法可以在原始矩阵A中找到所有这类不重叠块的数目和索引？A可以有不同的大小，但总是平方的、对称的，并且只由条目1和0组成。

我有一种模糊的感觉，可能有某种聪明的线性代数技巧来做这件事，但到目前为止，我还没有看到。

Answer 1

感谢@Julien在评论中提到了图表和连接。经过一番周旋之后，我想出了个办法。

假设我们从我最初文章中的“无序”矩阵A开始：

import scipy
import scipy.sparse
import scipy.ndimage

# transform A to sparse format;
# use scipy graph methods to reorder it into "contiguous" block form
B = scipy.sparse.csr_matrix(A)
permut = scipy.sparse.csgraph.reverse_cuthill_mckee(B)
B = B[permut,:][:,permut].toarray() # transform back to normal numpy array

# using scipy.ndimage methods, relabel all "non-touching" features 
# in matrix B and extract their index slices
B, num_features = scipy.ndimage.label(B)
slices = scipy.ndimage.find_objects(B)

代码段末尾的B (用圆点表示的零)：

     1 1 . . .
     1 1 1 . .
B =  . 1 1 . .
     . . . 2 2
     . . . 2 2

slices

[(slice(0, 3, None), slice(0, 3, None)),
 (slice(3, 5, None), slice(3, 5, None))]

它代表了我要求的块，只是顺序不同。

所用方法的文件编制：

麦基 (维基百科)

ndimage.label

对象