Coincidencia de patrón de imagen (si existen coordenadas de retorno)

Question

Actualmente, en C#, estoy intentando encontrar una forma de encontrar un patrón específico en una imagen grande, una captura de pantalla en realidad. Se necesita una coincidencia del 100%, por lo que el problema es bastante directo.

Prueba de material: http://www.myhideout.eu/temp/pattern.png (NB: los píxeles transparentes son irrelevantes y no deben ser probados.) http://www.myhideout.eu/temp/test.png

Si se encuentra un patrón, voy a necesitar algún tipo de coordinar así que sé donde, pero eso es la parte fácil

El único enfoque que he encontrado hasta ahora es el más obvio. Tome el primer píxel del patrón e itere a través de la imagen de prueba hasta encontrar una coincidencia, luego pruebe el resto del patrón hasta que la prueba falle o no haya más patrón. Si la prueba falla, continúe con el siguiente píxel que coincida con el primer píxel del patrón y vuelva a intentarlo. Si recorre la imagen de prueba sin una coincidencia, obviamente no existe tal patrón y ese debería ser el resultado de la prueba.

Teoría que esto funciona, pero en realidad las cosas son un poco más complicadas. Todavía tengo que presentarte una forma adecuada de estructurar el código y los casos de prueba que he realizado han tenido errores bastante extraños, lo que no es una gran sorpresa teniendo en cuenta la complejidad.

Sin embargo, mi mayor preocupación es el tiempo. Esta es solo una pequeña parte de un proceso largo y el objetivo es reducir el tiempo de ejecución total a un par de segundos. Imagine una imagen 1920 * 1200, que es aproximadamente el límite, donde el patrón está al final y varias coincidencias parciales se producen antes de eso.

Por supuesto, he buscado en la red, varios foros, etc., pero el único material que se me ocurrió es muy avanzado y sería de poca utilidad, incluso si lograra entender que es para fines muy diferentes.

También he estado considerando si sería posible convertir el patrón y la imagen de prueba a algún tipo de conjunto de bits y luego simplemente AND, SHIFT y/o MASK a su través, pero eso está más allá de mis capacidades actuales.

Creo que ya describí mis problemas aquí. Lamento el retraso en el uso de ejemplos de código, pero lo que tengo podría ser de poca utilidad para cualquier persona y también un poco embarazoso.

Agradeceré cualquier ayuda.

Answer 1

AForge can handle that.

Answer 2

Si puede garantizar que sus imágenes van a estar en la misma orientación, entonces su implementación simple probablemente sea la más rápida.

Sin embargo, si está comprobando las imágenes que se han rotado, convertido a escala de grises o cualquier otro tipo de transformación, fallará rápidamente.

No tengo ningún código para usted, pero hay algunos buenos recursos de Generation5 (artículos de AI), específicamente de McGill University's COMP-644 (Pattern Recognition) course.

Espero que te gusten las matemáticas.

Answer 3

Además de la investigación general sobre la coincidencia de patrones

1. La descripción de la estrategia de búsqueda suena como el algoritmo de búsqueda de cadena de la fuerza bruta; ¿puedes aplicar métodos optimizados de búsqueda de cadenas (p.Boyer Mooore) a su problema?
2. Al observar su patrón y su "pajar", una (¿rápida?) Búsqueda del marco gris antes de buscar los iconos debería mejorar la velocidad de ejecución.
3. Si puede restringir el área donde se espera el patrón y preprocesar los patrones, puede ser una opción utilizar los conceptos/código de OCR.

Por supuesto, nada puede vencer a una biblioteca que hace exactamente lo que desea.