.net - ¿Algoritmo rápido para encontrar una imagen pequeña en una imagen grande?

algorithm image-processing

Question

¿Cuál sería la mejor manera (más rápida) de verificar si una imagen pequeña está dentro de una imagen grande?

(Imagen ampliada :)

Querer encontrar:

Tengo una solución, pero es muy lenta:

• Recorreré cada píxel (x, y) en la imagen general y compararé el píxel (0,0) de la imagen pequeña (valor de color).
• si el píxel es el mismo, recorro la imagen pequeña y la comparo con la imagen más grande ... si falla, vuelve al bucle de exploración de imagen grande.

este método necesita aproximadamente 7 segundos para encontrar una foto de 50x50 en una foto de 1600x1200.

Tal vez usted sabe un mejor algoritmo? Conozco un software que puede hacer esto en menos de un segundo.

Answer 1

La convolution operación matemática (que se puede implementar de manera eficiente con la Transformada Rápida de Fourier ) se puede utilizar para esto.

Answer 2

Lo que haría sería cortar ambas imágenes en imágenes 10x10, calcular el color "promedio" de cada imagen pequeña y hacer el mismo algoritmo que hiciste.

Esto debería escalar con cualquier algoritmo, ya que solo afecta el factor constante.

Answer 3

Si sabe que los valores de los píxeles serán exactos, esto solo se convierte en un caso especial de un problema de coincidencia de cadenas. Hay muchos algoritmos de coincidencia de cadenas rápidos, comenzaría con Boyer-Moore o Knuth-Morris-Pratt .

Answer 4

la otra respuesta describe la correlación cruzada a través de la convolución de imágenes (implementada multiplicando los elementos). pero a veces desea utilizar una correlación cruzada normalizada : consulte http://scribblethink.org/Work/nvisionInterface/nip.html para obtener una discusión completa y detalles de una implementación rápida.

Answer 5

O(hA*wA*hB*wB) algo tiene un caso peor de O(hA*wA*hB*wB) donde hA , wA , hB , wB son la altura y el ancho de la imagen grande A y la imagen pequeña B

Este algo debería tener un peor caso de O((wA+wB)*hA*hB)

Se basa en la coincidencia de cadenas y así es como funciona:

• Encuentra cada fila de la imagen B en cada fila de la imagen A utilizando la coincidencia de cadenas cada vez.
  • Cada vez que tenga una coincidencia, almacene en la matriz matched_row un triple (rA, cA, rB) donde (rA, cA) representa el punto de inicio en la imagen A de la fila rB del archivo B
• Ahora ordena matched_row primero según cA , luego a rA y luego a rB .

• Ahora iterar la matriz y si ha emparejado una imagen B de 5 filas tendrá algo como esto:

   (12, 5, 0), (13, 5, 1), (14, 5, 2), (15, 5, 3), (15, 5, 4)