Wie kann ich überprüfen, ob ein zweidimensionales NumPy-Array ein bestimmtes Muster von Werten enthält?

Ich habe eine große NumPy.array field_array und eine kleinere array match_array , die beide aus int Werten bestehen. Mit dem folgenden Beispiel, wie kann ich überprüfen, ob ein match_array-förmiges Segment von field_array Werte enthält, die genau denen entsprechen, die in 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) 

Diese Beispiele sollten True da das von match_array beschriebene Muster über [6:9,3:7] .

4 Solutions collect form web for “Wie kann ich überprüfen, ob ein zweidimensionales NumPy-Array ein bestimmtes Muster von Werten enthält?”

Ansatz Nr. 1

Dieser Ansatz leitet sich von a solution zur Implement Matlab's im2col 'sliding' in python , die entworfen wurde, um rearrange sliding blocks from a 2D array into columns zu rearrange sliding blocks from a 2D array into columns . field_array also unseren Fall hier zu lösen, konnten diese field_array aus field_array als Spalten gestapelt und mit der Spaltenvektorversion von match_array .

Hier ist eine formale Definition der Funktion für die Umlagerung / Stapelung –

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

Um unseren Fall zu lösen, hier ist die Implementierung auf der Grundlage von 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)) 

Die Ausgabe für die gegebene Probe in der Frage wäre –

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

Ansatz Nr. 2

Angesichts der Tatsache, dass opencv bereits eine Vorlagen-Matching-Funktion hat, die Platz von Unterschieden macht, können Sie das verwenden und nach Null-Differenzen suchen, was Ihre passenden Positionen sein würde. Also, wenn du Zugriff auf cv2 (opencv-Modul) hast, würde die Implementierung so aussehen –

 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) 

geben uns –

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

Benchmarking

Dieser Abschnitt vergleicht Laufzeiten für alle Ansätze, die vorgeschlagen wurden, um die Frage zu lösen. Die Gutschrift für die verschiedenen Methoden, die in diesem Abschnitt aufgeführt werden, geht an ihre Mitwirkenden.

Methodendefinitionen –

 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 –

Fall Nr. 1 (Beispieldaten aus Frage):

 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 

Fall Nr. 2 (größere zufällige Daten):

 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 

Es gibt keine solche Suchfunktion in NumPy eingebaut, aber es ist sicherlich möglich, in NumPy zu tun

Solange deine Arrays nicht zu massiv sind, könnte man einen Rolling-Fenster verwenden:

 from skimage.util import view_as_windows windows = view_as_windows(field_array, match_array.shape) 

Die Funktion view_as_windows ist rein in NumPy geschrieben, also wenn du keinen Skimage hast, kannst du den Code immer hier kopieren.

Dann, um zu sehen, ob das Sub-Array im größeren Array erscheint, können Sie schreiben:

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

Um die Indizes zu finden, wo die obere linke Ecke des Sub-Array übereinstimmt, können Sie schreiben:

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

Dieser Ansatz sollte auch für Arrays höherer Dimensionen funktionieren.


* Obwohl das Array- windows keinen zusätzlichen Speicher aufnimmt (nur die Fortschritte und die Form werden geändert, um eine neue Ansicht der Daten zu erstellen), schreibt windows == match_array ein boolesches Array von Größe (7, 6, 3, 4), das ist 504 Bytes Speicher. Wenn Sie mit sehr großen Arrays arbeiten, ist dieser Ansatz vielleicht nicht möglich.

Eine Lösung besteht darin, die gesamte search_in Array-Block-at-a-Time zu durchsuchen (ein 'Block' ist ein search_for Slice), bis entweder ein passendes Segment gefunden wird oder das search_for Array erschöpft ist. Ich kann es verwenden, um Koordinaten für den passenden Block zu bekommen, oder einfach nur ein bool Ergebnis, indem return_coords True oder False für das optionale Argument 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 

Ich frage mich, ob NumPy nicht schon eine Funktion hat, die das Gleiche tun kann, obwohl …

Um zu den bereits gebuchten Antworten hinzuzufügen, möchte ich noch einen hinzufügen, der Fehler aufgrund von Gleitkomma-Präzision berücksichtigt, falls Matrizen aus, z. B. Bildverarbeitung, wo Zahlen unter Gleitkomma-Operationen stehen, kommen.

Sie können die Indizes der größeren Matrix wiederkehren und nach der kleineren Matrix suchen. Dann kannst du eine Submatrix der größeren Matrix extrahieren, die der Größe der kleineren Matrix entspricht.

Sie haben ein Spiel, wenn der Inhalt von beiden, die Submatrix von 'groß' und die 'kleine' Matrix übereinstimmen.

Das folgende Beispiel zeigt, wie die ersten Indizes des Standorts in der gefundenen großen Matrix zurückgegeben werden können. Es wäre trivial, diese Funktion zu erweitern, um ein Array von Orten zurückzugeben, die gefunden werden, um zu entsprechen, wenn das die Absicht ist.

 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 

Mit der obigen Funktion können Sie folgendes Beispiel ausführen:

 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) 

Was würde drucken:

 Beispiel 1, Schnittpunkt: [1, 2]
 Beispiel 2, Kreuzung: Keine
  • Wie man eine Pandas-Zeitreihe nach NAN-Werten aufteilt
  • Implementiere MATLABs im2col 'sliding' in Python
  • Python matplotlib plot spärliches matrixmuster
  • Numpy Version von "Exponential gewichtet gleitenden Durchschnitt", entspricht pandas.ewm (). Mean ()
  • Wie kann ich numpy benutzen, ohne es zu installieren?
  • Durchschnitt mit Gruppierungswert in einem anderen Vektor (numpy / Python)
  • Miniconda "installiert" numpy aber Python kann es nicht importieren
  • Extrahieren von unsigniertem Zeichen aus dem Array von numpy.uint8
  • Scipy Interpolation, wie man die Größe von 3x3 Matrix auf 5x5 skizzieren
  • Numpy Array mit Python's langen Typ
  • Python, numpy boolean array: negation in wo ausgabe
  • Python ist die beste Programmiersprache der Welt.