python - ¿Cómo puedo verificar si una matriz bidimensional NumPy contiene un patrón específico de valores dentro de ella?

arrays pattern-matching

Question

Tengo un gran NumPy.array field_array y una matriz más pequeña match_array , ambos compuestos por valores int . Usando el siguiente ejemplo, ¿cómo puedo verificar si algún segmento en forma de field_array de field_array contiene valores que se corresponden exactamente con los de 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)

Estos ejemplos deberían devolver True ya que el patrón descrito por match_array alinea sobre [6:9,3:7] .

Answer 1

Aquí hay una solución usando la función as_strided() del módulo stride_tricks

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

# field_array (I modified it to have two matching arrays)
A = np.array([[ 24,  25,  26,  27,  28,  29,  30,  31,  23],
              [ 33,   0,   1,   2,   3,  38,  39,  40,  32],
              [-39,   4,   5,   6,   7, -34, -33, -32, -40],
              [-30,   8,   9,  10,  11, -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]])

# match_array
B = np.arange(12).reshape(3,4)


# Window view of A
A_w = as_strided(A, shape=(A.shape[0] - B.shape[0] + 1,
                           A.shape[1] - B.shape[1] + 1,
                           B.shape[0], B.shape[1]),
                    strides=2*A.strides).reshape(-1, B.shape[0], B.shape[1])

match = (A_w == B).all(axis=(1,2))

También podemos encontrar los índices del primer elemento de cada bloque coincidente en A

where = np.where(match)[0]
ind_flat = where + (B.shape[1] - 1)*(np.floor(where/(A.shape[1] - B.shape[1] + 1)).astype(int))
ind = [tuple(row) for row in np.array(np.unravel_index(ind_flat, A.shape)).T]

Resultado

print(match.any())
True

print(ind)
[(1, 1), (6, 3)]

Answer 2

No hay tal función de búsqueda integrada en NumPy, pero ciertamente es posible hacerlo en NumPy

Siempre que sus matrices no sean demasiado masivas *, podría usar un enfoque de ventana móvil:

from skimage.util import view_as_windows

windows = view_as_windows(field_array, match_array.shape)

La función view_as_windows está escrita exclusivamente en NumPy, por lo que si no tiene skimage, siempre puede copiar el código desde here .

Luego, para ver si la matriz secundaria aparece en la matriz más grande, puede escribir:

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

Para encontrar los índices de dónde coincide la esquina superior izquierda de la submatriz, puede escribir:

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

Este enfoque también debería funcionar para matrices de dimensiones superiores.

* aunque las windows matriz no ocupan memoria adicional (solo se cambian los pasos y la forma para crear una nueva vista de los datos), escribir windows == match_array crea una matriz booleana de tamaño (7, 6, 3, 4) que es 504 bytes de memoria. Si está trabajando con matrices muy grandes, este enfoque podría no ser factible.

Answer 3

Para agregar a las respuestas ya publicadas, me gustaría agregar una que tenga en cuenta los errores debidos a la precisión de punto flotante en caso de que las matrices provengan, digamos, del procesamiento de imágenes, por ejemplo, donde los números están sujetos a operaciones de punto flotante.

Puede repetir los índices de la matriz más grande, buscando la matriz más pequeña. Luego puede extraer una submatriz de la matriz más grande que coincida con el tamaño de la matriz más pequeña.

Tiene una coincidencia si el contenido de ambos, la submatriz de "grande" y la matriz "pequeña" coinciden.

El siguiente ejemplo muestra cómo devolver los primeros índices de la ubicación en la matriz grande que coinciden. Sería trivial extender esta función para devolver un conjunto de ubicaciones que coincidan si esa es la intención.

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

Usando la función anterior puede ejecutar el siguiente ejemplo:

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)

Lo que imprimiría:

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

Answer 4

Una solución es buscar en todo el bloque search_in array-at-a-time (un ''bloque'' es un search_for forma) hasta que se encuentre un segmento coincidente o se search_for conjunto search_for . Puedo usarlo para obtener coordenadas para el bloque coincidente, o simplemente un resultado bool enviando True o False para el argumento opcional return_coords ...

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

Sin embargo, me pregunto si NumPy aún no tiene una función que pueda hacer lo mismo ...

Answer 5

Enfoque n. ° 1

Este enfoque deriva de a solution para Implement Matlab''s im2col ''sliding'' in python que fue diseñado para rearrange sliding blocks from a 2D array into columns . Por lo tanto, para resolver nuestro caso aquí, esos bloques deslizantes de field_array podrían apilarse como columnas y compararse con la versión vectorial de match_array de match_array .

Aquí hay una definición formal de la función para la reorganización / apilamiento:

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())

Para resolver nuestro caso, aquí está la implementación basada en 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))

El resultado para la muestra dada en la pregunta sería:

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

Enfoque n. ° 2

Dado que opencv ya tiene una función de coincidencia de plantilla que hace un cuadrado de diferencias, puede emplear eso y buscar diferencias cero, que serían sus posiciones de coincidencia. Entonces, si tiene acceso a cv2 (módulo opencv), la implementación se vería así:

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)

dándonos -

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

Benchmarking

Esta sección compara tiempos de ejecución para todos los enfoques sugeridos para resolver la pregunta. El crédito por los diversos métodos enumerados en esta sección va a sus contribuyentes.

Definiciones de métodos -

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)

Pruebas de tiempo de ejecución

Caso # 1 (Datos de muestra de la pregunta):

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

Caso # 2 (datos aleatorios más grandes):

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