How to find a 2D array in a 2D array?

Question

There is a numpy array() with m x n size, and I want to get indexes that match a particular pattern.

Since the map would be bigger than the example below, I guess solving with loop is not efficient.

In this example, I want to get the following as result:

[
   [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3)],
   [(1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6)]
]

Is there any tool to do this easily?

Answer 1

You can efficiently solve this problem using a convolution where the filter is:

[[1, 0, 0, 0],
 [1, 1, 1, 1]]

This can be done efficiently with scipy.signal.convolve2d.

The resulting array can then be filtered by looking for values greater than the sum of the previous filter (ie. 5). This can be done with np.where(result >= 5).

Note that for big pattern, you can use an FFT-based convolution.

To summarize, you can do:

np.where(scipy.signal.convolve2d(m, np.flip(f), mode='valid') >= 5)