Encontrar una subimagen dentro de una imagen de Numpy

Question

Tengo dos matrices Numpy (uint8 tridimensional) convertidas a partir de imágenes PIL.

Quiero encontrar si la primera imagen contiene la segunda imagen, y si es así, buscar las coordenadas del píxel superior izquierdo dentro de la primera imagen donde está la coincidencia.

¿Hay alguna forma de hacer eso puramente en Numpy, de una manera lo suficientemente rápida, en lugar de usar bucles puros de Python (4! Muy lento).

ejemplo 2D:

a = numpy.array([ 
    [0, 1, 2, 3], 
    [4, 5, 6, 7], 
    [8, 9, 10, 11] 
]) 
b = numpy.array([ 
    [2, 3], 
    [6, 7] 
]) 

cómo hacer algo como esto?

position = a.find(b) 

position sería entonces (0, 2).

Answer 1

Esto se puede hacer usando scipy's correlate2d y luego usando argmax para encontrar el pico en la correlación cruzada.

Here's una explicación más completa de las matemáticas y las ideas, y algunos ejemplos.

Si desea permanecer en Numpy puro y no usar scipy, o si las imágenes son grandes, probablemente sea mejor utilizar un enfoque basado en FFT para las correlaciones cruzadas.

Editar: La pregunta solicitó específicamente una solución Pure Numpy. Pero si puede usar OpenCV u otras herramientas de procesamiento de imágenes, obviamente es más fácil usar uno de estos. Un ejemplo de esto está dado por PiQuer a continuación, que recomiendo si puedes usarlo.

Answer 2

Estoy haciendo esto con la función OpenCVmatchTemplate. Hay una excelente conexión de pitón a OpenCV que utiliza numpy internamente, por lo que las imágenes son solo numpy arrays. Por ejemplo, supongamos que tiene un archivo BGR de 100x100 píxeles testimage.bmp. Tomamos una subimagen de 10x10 en la posición (30,30) y la encontramos en el original.

import cv2 
import numpy as np 

image = cv2.imread("testimage.bmp") 
template = image[30:40,30:40,:] 

result = cv2.matchTemplate(image,template,cv2.TM_CCOEFF_NORMED) 
print np.unravel_index(result.argmax(),result.shape) 

Salida:

(30, 30) 

Se puede elegir entre varios algoritmos para que coincida con la plantilla a la original, cv2.TM_CCOEFF_NORMED es sólo uno de ellos. Consulte la documentación para obtener más detalles, algunos algoritmos indican coincidencias como mínimas, otras como máximas en la matriz de resultados. Una palabra de advertencia: OpenCV usa el orden de los canales BGR por defecto, así que tenga cuidado, p. cuando compara una imagen que cargó con cv2.imread con una imagen que convirtió de PIL a numpy. Siempre puede usar cv2.cvtColor para convertir entre formatos.

Para encontrar todos partidos por encima de un umbral dado confidence, utilizo algo en la línea de esta situación para sacar la comparación de las coordinadas de mi resultado matriz:

match_indices = np.arange(result.size)[(result>confidence).flatten()] 
np.unravel_index(match_indices,result.shape) 

Esto da una tupla de matrices de longitud 2 , cada una de las cuales es una coordenada coincidente.

Answer 3

Acabo de terminar de escribir una implementación independiente de correlación cruzada normalizada para matrices N-dimensionales.Puede obtenerlo de here.

La correlación cruzada se calcula ya sea directamente, utilizando scipy.ndimage.correlate, o en el dominio de la frecuencia, utilizando scipy.fftpack.fftn/ifftn dependiendo de lo que será más rápida para los tamaños de entrada dados.

Answer 4

En realidad se puede reducir este problema a una simple búsqueda en cadena mediante una regex como la siguiente aplicación - acepta dos PIL.Image objetos y se encuentra coordenadas del needle dentro del haystack. Esto es aproximadamente 127x más rápido que usar una búsqueda píxel por píxel.

def subimg_location(haystack, needle): 
    haystack = haystack.convert('RGB') 
    needle = needle.convert('RGB') 

    haystack_str = haystack.tostring() 
    needle_str = needle.tostring() 

    gap_size = (haystack.size[0] - needle.size[0]) * 3 
    gap_regex = '.{' + str(gap_size) + '}' 

    # Split b into needle.size[0] chunks 
    chunk_size = needle.size[0] * 3 
    split = [needle_str[i:i+chunk_size] for i in range(0, len(needle_str), chunk_size)] 

    # Build regex 
    regex = re.escape(split[0]) 
    for i in xrange(1, len(split)): 
     regex += gap_regex + re.escape(split[i]) 

    p = re.compile(regex) 
    m = p.search(haystack_str) 

    if not m: 
     return None 

    x, _ = m.span() 

    left = x % (haystack.size[0] * 3)/3 
    top = x/haystack.size[0]/3 

    return (left, top)