How can I find if there is a submatrix in a numpy matrix?

user_19807358 0
Viewed 44

I have a 8x8 boolean matrix, and i would like to find if there is a submatrix in that matrix in the shape of 3x3 with only "False" in it.

for example:

the submatrix:

[[False, False, False],
[False, False, False],
[False, False, False]]

a matrix that have room for the submatrix (top left corner):

array([[False, False, False, False, False, False, False, False],
       [False, False, False, False, True, False, True, False],
       [False, False, False, False, False, False, False, False],
       [False, False, False, True, False, False, False, False],
       [False, False, False, False, False, False, False, False],
       [False, True, False, False, False, True, False, False],
       [False, False, False, True, False, False, False, False],
       [False, False, False, False, False, False, False, False]])

a matrix that does not have room for the submatrix:

array([[False, False, False, False, False, False, False, False],
       [False, True, False, True, False, True, False, False],
       [False, True, False, False, True, False, False, True],
       [False, False, False, False, False, False, False, False],
       [False, True, False, True, False, True, False, False],
       [False, False, True, False, False, False, True, False],
       [False, True, False, False, True, False, False, False],
       [False, False, False, True, False, False, True, False]])
numpy-ndarray numpy python
1 Answers

You can use the sliding window approach with window of size 3x3:

import numpy as np
from numpy.lib.stride_tricks import sliding_window_view



x = np.array([[False, False, False, False, False, False, False, False],
              [False, False, False, False, True, False, True, False],
              [False, False, False, False, False, False, False, False],
              [False, False, False, True, False, False, False, False],
              [False, False, False, False, False, False, False, False],
              [False, True, False, False, False, True, False, False],
              [False, False, False, True, False, False, False, False],
              [False, False, False, False, False, False, False, False]])


v = sliding_window_view(x, (3, 3))

v.sum(axis=(2,3))

array([[0, 0, 1, 1, 2, 1],
       [0, 1, 2, 2, 2, 1],
       [0, 1, 1, 1, 0, 0],
       [1, 2, 1, 2, 1, 1],
       [1, 2, 1, 2, 1, 1],
       [1, 2, 1, 2, 1, 1]])

where the locations of 0's are the locations of the upper-left corner of the submatrix in the matrix.

Edit: If you have any submatrix s, not with only False in it, you can do the following:

np.all(v == s, axis=(2,3))

and look for the locations of True values.

user_29453570
Related