Ricerca di sottomatrici corrispondenti all'interno di una matrice

Question

Ho un array 2D 100x200 espresso come una serie numpy composta da celle nere (0) e bianche (255). È un file bitmap. Poi ho forme 2D (è più facile pensarle come lettere) che sono anche celle 2D in bianco e nero.

So che posso scorrere in modo ingenuo attraverso la matrice ma questa sarà una porzione "calda" del mio codice, quindi la velocità è una preoccupazione. C'è un modo veloce per eseguire questo in numpy/scipy?

Ho esaminato brevemente la funzione correlata di Scipy. Non mi interessano le "partite sfocate", solo le corrispondenze esatte. Ho anche guardato alcuni documenti accademici, ma sono sopra la mia testa.

Answer 1

È possibile utilizzare correlato. Dovrai impostare i valori neri su -1 e i valori bianchi su 1 (o viceversa) in modo da conoscere il valore del picco della correlazione e che si verifichi solo con la lettera corretta.

Il seguente codice fa ciò che penso si desideri.

import numpy 
from scipy import signal 

# Set up the inputs 
a = numpy.random.randn(100, 200) 
a[a<0] = 0 
a[a>0] = 255 

b = numpy.random.randn(20, 20) 
b[b<0] = 0 
b[b>0] = 255 

# put b somewhere in a 
a[37:37+b.shape[0], 84:84+b.shape[1]] = b 

# Now the actual solution... 

# Set the black values to -1 
a[a==0] = -1 
b[b==0] = -1 

# and the white values to 1 
a[a==255] = 1 
b[b==255] = 1 

max_peak = numpy.prod(b.shape) 

# c will contain max_peak where the overlap is perfect 
c = signal.correlate(a, b, 'valid') 

overlaps = numpy.where(c == max_peak) 

print overlaps 

Emette (array([37]), array([84])), le posizioni dei offset impostati nel codice.

È probabile che se la dimensione della lettera moltiplicata per la dimensione del grande array è più grande di circa Nlog (N), dove N è la dimensione corrispondente del grande array in cui stai cercando (per ogni dimensione), quindi probabilmente aumenterai la velocità usando un algoritmo basato su fft come scipy.signal.fftconvolve (tenendo presente che dovrai girare ogni asse di uno dei set di dati se stai usando una convoluzione piuttosto che una correlazione - flipud e fliplr). L'unica modifica sarebbe quella di c assegnazione:

c = signal.fftconvolve(a, numpy.fliplr(numpy.flipud(b)), 'valid') 

Confrontando i tempi delle dimensioni di cui sopra:

In [5]: timeit c = signal.fftconvolve(a, numpy.fliplr(numpy.flipud(b)), 'valid') 
100 loops, best of 3: 6.78 ms per loop 

In [6]: timeit c = signal.correlate(a, b, 'valid') 
10 loops, best of 3: 151 ms per loop 

Answer 2

Qui è un metodo che può essere in grado di utilizzare, o adattare, a seconda dei dettagli di le tue esigenze Esso utilizza ndimage.label and ndimage.find_objects:

1. etichetta dell'immagine usando ndimage.label questo trova tutti blob nella matrice e li etichetta in interi.
2. Prendi le fette di questi blob utilizzando ndimage.find_objects
3. Quindi utilizzare insieme intersezione per vedere se la found blobs corrispondono con il tuo wanted blobs

Codice per 1. e 2.:

import scipy 
from scipy import ndimage 
import matplotlib.pyplot as plt 

#flatten to ensure greyscale. 
im = scipy.misc.imread('letters.png',flatten=1) 
objects, number_of_objects = ndimage.label(im) 
letters = ndimage.find_objects(objects) 

#to save the images for illustrative purposes only: 
plt.imsave('ob.png',objects) 
for i,j in enumerate(letters): 
    plt.imsave('ob'+str(i)+'.png',objects[j]) 

esempio di ingresso:

etichettati:

blob isolati da confrontare: