如何检查一个二维NumPy数组是否包含特定的值模式？

I have a large NumPy.array field_array and a smaller array match_array, both consisting of int values. Using the following example, how can I check if any match_array-shaped segment of field_array contains values that exactly correspond to the ones in match_array?

我有一个很大的NumPy.array field_array和一个较小的数组match_array,两者都由int值组成。使用以下示例,如何检查field_array的match_array形状段是否包含与match_array中的值完全对应的值?

import numpy
raw_field = ( 24,  25,  26,  27,  28,  29,  30,  31,  23, \
              33,  34,  35,  36,  37,  38,  39,  40,  32, \
             -39, -38, -37, -36, -35, -34, -33, -32, -40, \
             -30, -29, -28, -27, -26, -25, -24, -23, -31, \
             -21, -20, -19, -18, -17, -16, -15, -14, -22, \
             -12, -11, -10,  -9,  -8,  -7,  -6,  -5, -13, \
              -3,  -2,  -1,   0,   1,   2,   3,   4,  -4, \
               6,   7,   8,   4,   5,   6,   7,  13,   5, \
              15,  16,  17,   8,   9,  10,  11,  22,  14)
field_array = numpy.array(raw_field, int).reshape(9,9)
match_array = numpy.arange(12).reshape(3,4)

These examples ought to return True since the pattern described by match_array aligns over [6:9,3:7].

这些示例应该返回True,因为match_array描述的模式在[6:9,3:7]上排列。

4 个解决方案

#1

Approach #1

This approach derives from a solution to Implement Matlab's im2col 'sliding' in python that was designed to rearrange sliding blocks from a 2D array into columns. Thus, to solve our case here, those sliding blocks from field_array could be stacked as columns and compared against column vector version of match_array.

这种方法源于在python中实现Matlab的im2col“滑动”的解决方案,该解决方案旨在将滑动块从2D阵列重新排列成列。因此,为了解决我们的情况,来自field_array的那些滑动块可以堆叠为列,并与match_array的列向量版本进行比较。

Here's a formal definition of the function for the rearrangement/stacking -

这是重新排列/堆叠功能的正式定义 -

def im2col(A,BLKSZ):   

    # Parameters
    M,N = A.shape
    col_extent = N - BLKSZ[1] + 1
    row_extent = M - BLKSZ[0] + 1

    # Get Starting block indices
    start_idx = np.arange(BLKSZ[0])[:,None]*N + np.arange(BLKSZ[1])

    # Get offsetted indices across the height and width of input array
    offset_idx = np.arange(row_extent)[:,None]*N + np.arange(col_extent)

    # Get all actual indices & index into input array for final output
    return np.take (A,start_idx.ravel()[:,None] + offset_idx.ravel())

To solve our case, here's the implementation based on im2col -

为了解决我们的情况,这里是基于im2col的实现 -

# Get sliding blocks of shape same as match_array from field_array into columns
# Then, compare them with a column vector version of match array.
col_match = im2col(field_array,match_array.shape) == match_array.ravel()[:,None]

# Shape of output array that has field_array compared against a sliding match_array
out_shape = np.asarray(field_array.shape) - np.asarray(match_array.shape) + 1

# Now, see if all elements in a column are ONES and reshape to out_shape. 
# Finally, find the position of TRUE indices
R,C = np.where(col_match.all(0).reshape(out_shape))

The output for the given sample in the question would be -

问题中给定样本的输出将是 -

In [151]: R,C
Out[151]: (array([6]), array([3]))

Approach #2

Given that opencv already has template matching function that does square of differences, you can employ that and look for zero differences, which would be your matching positions. So, if you have access to cv2 (opencv module), the implementation would look something like this -

鉴于opencv已经具有模板匹配功能,可以实现差异,您可以使用它并查找零差异,这将是您的匹配位置。所以,如果你有权访问cv2(opencv模块),那么实现看起来像这样 -

import cv2
from cv2 import matchTemplate as cv2m

M = cv2m(field_array.astype('uint8'),match_array.astype('uint8'),cv2.TM_SQDIFF)
R,C = np.where(M==0)

giving us -

给我们 -

In [204]: R,C
Out[204]: (array([6]), array([3]))

---

Benchmarking

This section compares runtimes for all the approaches suggested to solve the question. The credit for the various methods listed in this section goes to their contributors.

本节比较了解决问题所建议的所有方法的运行时间。本节中列出的各种方法的功劳归于其贡献者。

Method definitions -

方法定义 -

def seek_array(search_in, search_for, return_coords = False):
    si_x, si_y = search_in.shape
    sf_x, sf_y = search_for.shape
    for y in xrange(si_y-sf_y+1):
        for x in xrange(si_x-sf_x+1):
            if numpy.array_equal(search_for, search_in[x:x+sf_x, y:y+sf_y]):
                return (x,y) if return_coords else True
    return None if return_coords else False

def skimage_based(field_array,match_array):
    windows = view_as_windows(field_array, match_array.shape)
    return (windows == match_array).all(axis=(2,3)).nonzero()

def im2col_based(field_array,match_array):   
    col_match = im2col(field_array,match_array.shape)==match_array.ravel()[:,None]
    out_shape = np.asarray(field_array.shape) - np.asarray(match_array.shape) + 1  
    return np.where(col_match.all(0).reshape(out_shape))

def cv2_based(field_array,match_array):
    M = cv2m(field_array.astype('uint8'),match_array.astype('uint8'),cv2.TM_SQDIFF)
    return np.where(M==0)

Runtime tests -

运行时测试 -

Case # 1 (Sample data from question):

案例#1(问题的样本数据):

In [11]: field_array
Out[11]: 
array([[ 24,  25,  26,  27,  28,  29,  30,  31,  23],
       [ 33,  34,  35,  36,  37,  38,  39,  40,  32],
       [-39, -38, -37, -36, -35, -34, -33, -32, -40],
       [-30, -29, -28, -27, -26, -25, -24, -23, -31],
       [-21, -20, -19, -18, -17, -16, -15, -14, -22],
       [-12, -11, -10,  -9,  -8,  -7,  -6,  -5, -13],
       [ -3,  -2,  -1,   0,   1,   2,   3,   4,  -4],
       [  6,   7,   8,   4,   5,   6,   7,  13,   5],
       [ 15,  16,  17,   8,   9,  10,  11,  22,  14]])

In [12]: match_array
Out[12]: 
array([[ 0,  1,  2,  3],
       [ 4,  5,  6,  7],
       [ 8,  9, 10, 11]])

In [13]: %timeit seek_array(field_array, match_array, return_coords = False)
1000 loops, best of 3: 465 µs per loop

In [14]: %timeit skimage_based(field_array,match_array)
10000 loops, best of 3: 97.9 µs per loop

In [15]: %timeit im2col_based(field_array,match_array)
10000 loops, best of 3: 74.3 µs per loop

In [16]: %timeit cv2_based(field_array,match_array)
10000 loops, best of 3: 30 µs per loop

Case #2 (Bigger random data):

案例#2(更大的随机数据):

In [17]: field_array = np.random.randint(0,4,(256,256))

In [18]: match_array = field_array[100:116,100:116].copy()

In [19]: %timeit seek_array(field_array, match_array, return_coords = False)
1 loops, best of 3: 400 ms per loop

In [20]: %timeit skimage_based(field_array,match_array)
10 loops, best of 3: 54.3 ms per loop

In [21]: %timeit im2col_based(field_array,match_array)
10 loops, best of 3: 125 ms per loop

In [22]: %timeit cv2_based(field_array,match_array)
100 loops, best of 3: 4.08 ms per loop

#2

There's no such search function built in to NumPy, but it is certainly possible to do in NumPy

NumPy中没有内置的搜索功能,但在NumPy中肯定可以做到

As long as your arrays are not too massive*, you could use a rolling window approach:

只要您的数组不是太大*,您可以使用滚动窗口方法:

from skimage.util import view_as_windows

windows = view_as_windows(field_array, match_array.shape)

The function view_as_windows is written purely in NumPy so if you don't have skimage you can always copy the code from here.

函数view_as_windows完全是用NumPy编写的,所以如果你没有skimage,你总是可以从这里复制代码。

Then to see if the sub-array appears in the larger array, you can write:

然后要查看子数组是否出现在较大的数组中,您可以编写:

>>> (windows == match_array).all(axis=(2,3)).any()
True

To find the indices of where the top-left corner of the sub-array matches, you can write:

要查找子数组左上角匹配的索引,可以编写:

>>> (windows == match_array).all(axis=(2,3)).nonzero()
(array([6]), array([3]))

This approach should also work for arrays of higher dimensions.

这种方法也适用于更高维度的阵列。

---

*although the array windows takes up no additional memory (only the strides and shape are changed to create a new view of the data), writing windows == match_array creates a boolean array of size (7, 6, 3, 4) which is 504 bytes of memory. If you're working with very large arrays, this approach might not be feasible.

*虽然数组窗口不占用额外的内存(只改变了步幅和形状以创建数据的新视图),但写入windows == match_array会创建一个大小为(7,6,3,4)的布尔数组,这是504字节的内存。如果您正在使用非常大的数组,这种方法可能不可行。

#3

One solution is to search the entire search_in array block-at-a-time (a 'block' being a search_for-shaped slice) until either a matching segment is found or the search_for array is exhausted. I can use it to get coordinates for the matching block, or just a bool result by sending True or False for the return_coords optional argument...

一种解决方案是一次一行地搜索整个search_in数组('block'是search_for形状的切片),直到找到匹配的段或者search_for数组耗尽。我可以使用它来获取匹配块的坐标,或者通过为return_coords可选参数发送True或False来获取bool结果...

def seek_array(search_in, search_for, return_coords = False):
    """Searches for a contiguous instance of a 2d array `search_for` within a larger `search_in` 2d array.
If the optional argument return_coords is True, the xy coordinates of the zeroeth value of the first matching segment of search_in will be returned, or None if there is no matching segment.
If return_coords is False, a boolean will be returned.
 * Both arrays must be sent as two-dimensional!"""
    si_x, si_y = search_in.shape
    sf_x, sf_y = search_for.shape

    for y in xrange(si_y-sf_y+1):
        for x in xrange(si_x-sf_x+1):
            if numpy.array_equal(search_for, search_in[x:x+sf_x, y:y+sf_y]):
                return (x,y) if return_coords else True  # don't forget that coordinates are transposed when viewing NumPy arrays!
    return None if return_coords else False

I wonder if NumPy doesn't already have a function that can do the same thing, though...

我想知道NumPy是否还没有能够做同样事情的功能,不过......

#4

To add to the answers already posted, I'd like to add one that takes into account errors due to floating point precision in case that matrices come from, let's say, image processing for instance, where numbers are subject to floating point operations.

为了添加已发布的答案,我想添加一个考虑到由于浮点精度导致的错误,如果矩阵来自,例如图像处理,例如,数字受浮点运算的影响。

You can recurse the indexes of the larger matrix, searching for the smaller matrix. Then you can extract a submatrix of the larger matrix matching the size of the smaller matrix.

您可以递归较大矩阵的索引,搜索较小的矩阵。然后,您可以提取与较小矩阵的大小匹配的较大矩阵的子矩阵。

You have a match if the contents of both, the submatrix of 'large' and the 'small' matrix match.

如果两者的内容,“大”和“小”矩阵的子矩阵匹配,则匹配。

The following example shows how to return the first indexes of the location in the large matrix found to match. It would be trivial to extend this function to return an array of locations found to match if that's the intent.

以下示例显示如何返回找到匹配的大矩阵中位置的第一个索引。如果这是意图,那么扩展此函数以返回找到匹配的位置数组将是微不足道的。

import numpy as np

def find_submatrix(a, b):
    """ Searches the first instance at which 'b' is a submatrix of 'a', iterates
        rows first. Returns the indexes of a at which 'b' was found, or None if
        'b' is not contained within 'a'"""
    a_rows=a.shape[0]
    a_cols=a.shape[1]

    b_rows=b.shape[0]
    b_cols=b.shape[1]

    row_diff = a_rows - b_rows
    col_diff = a_cols - b_cols

    for idx_row in np.arange(row_diff):
        for idx_col in np.arange(col_diff):
            row_indexes = [idx + idx_row for idx in np.arange(b_rows)]
            col_indexes = [idx + idx_col for idx in np.arange(b_cols)]

            submatrix_indexes = np.ix_(row_indexes, col_indexes)
            a_submatrix = a[submatrix_indexes]

            are_equal = np.allclose(a_submatrix, b)  # allclose is used for floating point numbers, if they
                                                     # are close while comparing, they are considered equal.
                                                     # Useful if your matrices come from operations that produce
                                                     # floating point numbers.
                                                     # You might want to fine tune the parameters to allclose()
            if (are_equal):
                return[idx_col, idx_row]

    return None

Using the function above you can run the following example:

使用上面的函数,您可以运行以下示例:

large_mtx = np.array([[1,  2, 3, 7, 4, 2, 6],
                      [4,  5, 6, 2, 1, 3, 11],
                      [10, 4, 2, 1, 3, 7, 6],
                      [4,  2, 1, 3, 7, 6, -3],
                      [5,  6, 2, 1, 3, 11, -1],
                      [0,  0, -1, 5, 4, -1, 2],
                      [10, 4, 2, 1, 3, 7, 6],
                      [10, 4, 2, 1, 3, 7, 6] 
                     ])

# Example 1: An intersection at column 2 and row 1 of large_mtx
small_mtx_1 = np.array([[4, 2], [2,1]])
intersect = find_submatrix(large_mtx, small_mtx_1)
print "Example 1, intersection (col,row): " + str(intersect)

# Example 2: No intersection
small_mtx_2 = np.array([[-14, 2], [2,1]])
intersect = find_submatrix(large_mtx, small_mtx_2)
print "Example 2, intersection (col,row): " + str(intersect)

Which would print:

哪个会打印:

Example 1, intersection: [1, 2]
Example 2, intersection: None