How to find a 10x10x3 numpy array within a 1000x1000x3 numpy array (fast)?

小能豆

How to find a 10x10x3 numpy array within a 1000x1000x3 numpy array (fast)?

I am wondering the following:

I have a 10x10x3 and a 1000x1000x3 numpy array. I want to check if the smaller array can be found within the bigger array (and where). This is pretty easy with 2 for loops, but that solution is very slow:

H, W, _ = big.shape
h, w, _ = small.shape

for i in range(H - h + 1):
    for j in range(W - w + 1):
        if np.array_equal(big[i:i+h, j:j+w, :], small):
            print(i,j)

I was wondering if there is a way to vectorize this? Or a way to write this routine faster?

阅读 109

2023-11-23

共1个答案

小能豆

You can use NumPy’s view_as_windows function to efficiently extract all possible windows from the larger array, and then use np.where to find the positions where the windows match the smaller array. This avoids the need for explicit loops.

Here’s an example:

import numpy as np
from skimage.util import view_as_windows

# Create example arrays
big = np.random.rand(1000, 1000, 3)
small = np.random.rand(10, 10, 3)

# Extract windows from the larger array
windows = view_as_windows(big, (10, 10, 3))

# Compare windows with the smaller array
matches = np.where(np.all(windows == small, axis=(2, 3, 4)))

# Print the positions of matches
for i, j in zip(*matches):
    print(i, j)

This code uses the view_as_windows function from skimage.util to create a view of the larger array as a set of overlapping windows. Then, it uses np.where to find the positions where the windows match the smaller array.

Note that this approach assumes an exact match of values in all dimensions. If you want to allow for a certain tolerance (e.g., considering two arrays equal if their values are close), you may need to adjust the comparison condition accordingly.

2023-11-23