Encontrar submatrices coincidentes dentro de una matriz

Question

Tengo una matriz 2D de 100x200 expresada como una matriz numpy que consta de celdas negras (0) y blancas (255). Es un archivo de mapa de bits. Luego tengo formas 2D (es más fácil pensar en ellas como letras) que también son celdas en blanco y negro en 2D.

Sé que puedo iterar ingenuamente a través de la matriz, pero esta va a ser una parte "caliente" de mi código por lo que la velocidad es una preocupación. ¿Hay una manera rápida de realizar esto en numpy/scipy?

Miré brevemente la función de correlación de Scipy. No estoy interesado en 'partidos difusos', solo coincide exactamente. También miré algunos documentos académicos, pero están por encima de mi cabeza.

Answer 1

Usted puede uso correlacionar. Tendrá que establecer sus valores de negro a -1 y sus valores de blanco a 1 (o viceversa) para que sepa el valor del pico de la correlación, y que solo ocurra con la letra correcta.

El siguiente código hace lo que creo que desea.

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 

Esto da salida a (array([37]), array([84])), las ubicaciones de las compensaciones establecidas en el código.

Usted encontrará probablemente que si el tamaño de letra multiplicado por su gran tamaño de la matriz es más grande que aproximadamente Nlog (N), donde N es el tamaño correspondiente de la gran variedad en la que usted está buscando (para cada dimensión), entonces probablemente obtendrá una velocidad usando un algoritmo basado en fft como scipy.signal.fftconvolve (teniendo en cuenta que necesitará voltear cada eje de uno de los conjuntos de datos si está utilizando una convolución en lugar de una correlación - flipud y fliplr). La única modificación sería la de asignar c:

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

Comparando los tiempos en los tamaños más arriba:

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

Aquí es un método que puede ser capaz de usar o adaptar, dependiendo de los detalles de tus requerimientos Utiliza ndimage.label and ndimage.find_objects:

1. etiqueta de la imagen utilizando este ndimage.label encuentra todas las manchas de la matriz y los etiqueta con los números enteros.
2. Obtener las rebanadas de estas manchas usando ndimage.find_objects
3. A continuación, utilice intersección de conjuntos para ver si el found blobs corresponden con su wanted blobs

Código de 1. y 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]) 

ejemplo de entrada:

etiquetados:

manchas aisladas para poner a prueba en contra: