Reconocimiento de patrones de puntos

46

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: ingrese la descripción de la imagen aquí


Actualización 1:
La siguiente figura muestra una visión un poco más realista del problema que se está investigando. ingrese la descripción de la imagen aquí

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. ingrese la descripción de la imagen aquí

Desarrollador
fuente
1
¿Está buscando una solución para unir esos puntos o imágenes más complejas? ¿Cuántos puntos puede haber en las fotos?
Si, eso es muy importante. Si solo se trata de puntos de tamaño conocido, puede optimizar para eso. Si tiene control sobre los marcadores fiduciarios, puede optimizar para eso. Sé más específico sobre para qué estás usando esto.
endolito el
Para el problema en el que estoy trabajando, hay conjuntos de puntos (cada uno de varios cientos de puntos) en los que se busca otro conjunto de puntos de menor tamaño (digamos <100). La demostración anterior es muy simplificada y clara, sin embargo, el verdadero problema parece complicado. También hay un interés en encontrar coincidencias clasificadas en base a puntos no deseados que existen entre ellos.
Desarrollador
1
¿Habrá solo puntos en blanco y negro? ¿Los está obteniendo de una cámara / escáner / algo más? Los valores binarios podrían hacer que los cálculos sean mucho más rápidos.
endolito
¿Tiene algún problema para encontrar los centros de los puntos, o simplemente para encontrar la miniatura en el cuadro completo sabiendo las posiciones de los puntos?

Respuestas:

17

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.

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:

ingrese la descripción de la imagen aquí

Objetivo:

ingrese la descripción de la imagen aquí

Correlación cruzada:

ingrese la descripción de la imagen aquí

Los dos puntos brillantes son las ubicaciones que coinciden.

Pero 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
  • 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.

endolito
fuente
1
Así es, para el problema que se investiga no hay escala pero la rotación puede suceder. Gracias por el enlace y la respuesta.
Desarrollador
@Developer: Bueno, esto funcionará entonces, pero probablemente haya una mejor manera. Sin embargo, si es solo una imagen binaria, la correlación cruzada será mucho más rápida. (¿Existe una FFT para la señal binaria?) ¿La rotación es arbitraria? Tendría que experimentar con un conjunto de valores de rotación que dan buenos resultados, como incrementar en 1 grado o 5 grados, etc.
endolito
1
Sí, es un problema binario. También recuerdo de algún lado que había un método para encontrar una señal más corta modulada en una señal más larga con diferentes amplitudes. Recuerdo que, independientemente de la complejidad, funcionaba muy bien mostrando los puntos de selección como los puntos iniciales de las ocurrencias. Como el problema está en 2D, no tengo claro cómo usar un concepto similar. Esto también es complicado debido a la rotación que se aplica en 2D.
Desarrollador
1
Sí, esto se vuelve inviable al agregar la libertad de rotación. Es por eso que se desarrollaron métodos como RANSAC. Creo que ayuda pensar fuera del cuadro DSP en este caso.
Matt M.
@MattM .: Funciona, es lento. :)
endolith
22

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.

ingrese la descripción de la imagen aquí

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.

Matt M.
fuente
Agregué un poco más de detalles en la pregunta. Comprobaré profundamente sus enlaces, sin embargo, una impresión rápida fue que son conceptos diferentes.
Desarrollador
1
Parece que de hecho es un problema de RANSAC / homografía :)
Matt M.
Bien. Fue un concepto nuevo para mí. Lo intentaré lo antes posible. Si me enfrento a dificultades, compartiré con ustedes, excelentes y solidarios miembros de la comunidad.
Desarrollador
P simple: ¿Es posible / factible aplicar el método RANSAC / homografía a la nube de puntos 3D?
Desarrollador
Esta no es una solución válida. Desafortunadamente, la pregunta no contiene información de intensidad y, por lo tanto, los esquemas descriptores simples no funcionarían. El problema es bastante más geométrico que eso.
Tolga Birdal
3

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.

mirror2image
fuente
1
¿Nos darías un ejemplo con más explicaciones de tu idea? La versión actual de su respuesta me resulta confusa.
Desarrollador
3

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:

ingrese la descripción de la imagen aquí

  1. Utilice la implementación predeterminada de OpenCV de la transformación Hough generalizada para obtener: ingrese la descripción de la imagen aquí

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 .

Tolga Birdal
fuente