Reconocimiento de patrones de puntos

Con dos tamaños diferentes de conjuntos de puntos (2D para simplificar) dispersos dentro de dos cuadrados de diferentes tamaños, la pregunta es:

1- ¿Cómo encontrar cualquier ocurrencia del pequeño a través del grande?
2- ¿Alguna idea sobre cómo clasificar las ocurrencias como se muestra en la siguiente figura?

Aquí hay una demostración simple de la pregunta y una solución deseada:

Actualización 1:
La siguiente figura muestra una visión un poco más realista del problema que se está investigando.

En cuanto a los comentarios, se aplican las siguientes propiedades:

• ubicación exacta de puntos disponibles
• tamaño exacto de puntos disponibles
  • el tamaño puede ser cero (~ 1) = solo un punto
• todos los puntos son negros sobre un fondo blanco
• no hay efecto de escala de grises / anti-aliasing

Aquí está mi implementación del método presentado endolithcon algunos pequeños cambios (roté el objetivo en lugar del origen ya que es más pequeño y más rápido en rotación). Acepté la respuesta de 'endolith porque estaba pensando en eso antes. Sobre RANSAC no tengo experiencia hasta ahora. Además, la implementación de RANSAC requiere mucho código.

Esta no es la mejor solución, pero es una solución. Me gustaría aprender mejores técnicas:

Si no se iban a rotar o escalar, podría usar una simple correlación cruzada de las imágenes. Habrá un pico brillante donde sea que aparezca la imagen pequeña en la imagen grande.

• Registrar una imagen usando la correlación cruzada normalizada
• Convolución y coincidencia basada en plantillas

Puede acelerar la correlación cruzada utilizando un método FFT, pero si solo está haciendo coincidir una imagen de origen pequeña con una imagen de destino grande, el método de multiplicar y agregar fuerza bruta es a veces (no generalmente) más rápido.

Fuente:

Objetivo:

Correlación cruzada:

Los dos puntos brillantes son las ubicaciones que coinciden.

Pero sí tiene un parámetro de rotación en su imagen de ejemplo, por lo que no funcionará por sí solo. Si solo se permite la rotación, y no la escala, entonces todavía es posible usar la correlación cruzada, pero debe correlacionar cruzada, rotar la fuente, correlacionarla cruzada con toda la imagen objetivo, rotarla nuevamente, etc. para Todas las rotaciones.

Tenga en cuenta que esto no necesariamente encontrará la imagen. Si la imagen de origen es ruido aleatorio y el objetivo es ruido aleatorio, no lo encontrará a menos que busque exactamente en el ángulo correcto. Para situaciones normales, probablemente lo encontrará, pero depende de las propiedades de la imagen y los ángulos en los que busque.

Esta página muestra un ejemplo de cómo se haría, pero no proporciona el algoritmo.

Cualquier compensación donde la suma está por encima de un umbral es una coincidencia. Puede calcular la bondad de la coincidencia correlacionando la imagen de origen consigo misma y dividiendo todas sus sumas por este número. Una combinación perfecta será 1.0.

Sin embargo, esto será muy pesado desde el punto de vista informático, y probablemente haya mejores métodos para hacer coincidir los patrones de puntos (que me gustaría saber).

Ejemplo rápido de Python usando escala de grises y método FFT:

from __future__ import division
from pylab import *
import Image
import ImageOps

source_file = 'dots source.png'
target_file = 'dots target.png'

# Load file as grayscale with white dots
target = asarray(ImageOps.invert(Image.open(target_file).convert('L')))

close('all')
figure()
imshow(target)
gray()
show()

source_Image = ImageOps.invert(Image.open(source_file).convert('L'))

for angle in (0, 180):
    source = asarray(source_Image.rotate(angle, expand = True))
    best_match = max(fftconvolve(source[::-1,::-1], source).flat)

    # Cross-correlation using FFT
    d = fftconvolve(source[::-1,::-1], target, mode='same')

    figure()
    imshow(source)


    # This only finds a single peak.  Use something that finds multiple peaks instead:
    peak_x, peak_y = unravel_index(argmax(d),shape(d))

    figure()    
    plot(peak_y, peak_x,'ro')
    imshow(d)

    # Keep track of all these matches:
    print angle, peak_x, peak_y, d[peak_x,peak_y] / best_match

Mapas de bits de 1 color

Sin embargo, para mapas de bits de 1 color, esto sería mucho más rápido. La correlación cruzada se convierte en:

• Coloque la imagen de origen sobre la imagen de destino
  • bit a bit Y todos los píxeles superpuestos (mucho más rápido que la multiplicación)
  • suma todos los 1s en el área superpuesta
• Mueve la imagen de origen en 1 píxel
  • bitwise-Y todos los píxeles superpuestos
  • suma todos los 1s
• ...

Umbralizar una imagen en escala de grises a binario y luego hacer esto podría ser lo suficientemente bueno.

Punto de nube

Si la fuente y el objetivo son patrones de puntos, un método más rápido sería encontrar los centros de cada punto (correlacionar una vez con un punto conocido y luego encontrar los picos) y almacenarlos como un conjunto de puntos, luego hacer coincidir la fuente para apuntar girando, traduciendo y encontrando el error de mínimos cuadrados entre los puntos más cercanos en los dos conjuntos.

Desde una perspectiva de visión por computadora: el problema básico es estimar una homografía entre su conjunto de puntos objetivo y un subconjunto de puntos en el conjunto grande. En su caso, solo con rotación, será una homografía afín. Deberías estudiar el método RANSAC . Está diseñado para encontrar una coincidencia en un conjunto con muchos valores atípicos. Entonces, estás armado con dos palabras clave importantes, homografía y RANSAC .

OpenCV ofrece herramientas para calcular estas soluciones, pero también puede usar MATLAB. Aquí hay un ejemplo de RANSAC usando OpenCV . Y otra implementación completa .

Una aplicación típica podría ser encontrar la portada de un libro en una imagen. Tienes una foto de la portada del libro y una foto del libro sobre una mesa. El enfoque no es hacer coincidencias de plantillas, sino encontrar esquinas sobresalientes en cada imagen y comparar esos conjuntos de puntos. Su problema se parece a la segunda mitad de este proceso: encontrar el punto establecido en una gran nube. RANSAC fue diseñado para hacer esto de manera robusta.

Supongo que los métodos de correlación cruzada también pueden funcionar para usted, ya que los datos son muy limpios. El problema es que agrega otro grado de libertad con la rotación, y el método se vuelve muy lento.

Si el patrón es binario escaso, puede hacer una covarianza simple de vectores de coordenadas en lugar de imágenes. Tome las coordenadas de los puntos en la subventana ordenada hacia la izquierda, haga un vector a partir de todas las coordenadas y calcule la covarianza con el vector formado por las coordenadas de los puntos del patrón ordenados hacia la izquierda. También puedes usar pesas. Después de eso, haga que la fuerza bruta vecino más cercano busque la covarianza máxima en alguna cuadrícula en la ventana grande (y también la cuadrícula en ángulos de rotación). Después de encontrar coordenadas aproximadas con la búsqueda, puede refinarlas con el método de mínimos cuadrados reponderado.

PS Idea es que, en lugar de trabajar con imágenes, puede trabajar con coordenadas de píxeles distintos de cero. Búsqueda común de vecino más cercano. Debe hacer una búsqueda exhaustiva de todo el espacio de búsqueda, tanto traslacional como rotacional, utilizando alguna cuadrícula, que es un paso en las coordenadas y el ángulo de pudrición. Para cada coordenada / ángulo, toma un subconjunto de píxeles en la ventana con el centro con esa coordenada girada a ese ángulo, tome sus coordenadas (rel al centro) y compárelas con las coordenadas de píxel del patrón que busca. Debes asegurarte de que en ambos conjuntos los puntos estén ordenados de la misma manera. Encuentra coordenadas con mínima diferencia (máxima covarianza). Después de esa coincidencia aproximada, puede encontrar una coincidencia precisa con algún método de optimización. Lo siento, no puedo transmitirlo más simple que eso.

Estoy muy sorprendido de por qué nadie mencionó los métodos de la familia de Transformación Hough Generalizada . Resuelven directamente este problema particular.

Esto es lo que propongo:

1. Tome la plantilla y cree la tabla R , indexando los bordes de la plantilla. Los bordes que selecciono son los siguientes:

2. Utilice la implementación predeterminada de OpenCV de la transformación Hough generalizada para obtener:

donde se marcan las ubicaciones coincidentes. El mismo método seguiría siendo funcional incluso si los bordes se reducen a un solo punto, porque el método no necesita intensidades de imagen.

Además, manejar rotaciones es muy natural para los esquemas de Hough. De hecho, para el caso 2D, es solo una dimensión adicional en el acumulador. En caso de que desee entrar en detalles para hacerlo realmente eficiente, M. Ulrich explica muchos trucos en su artículo .

Esta es una buena aplicación para el hash geométrico. página de wikipedia de hashing geométrico