Reconociendo imagen dentro de la imagen en C#

Question

Me gustaría encontrar una imagen (aguja) dentro de una imagen (pajar).

Para mantener las cosas simples, tomo dos capturas de pantalla de mi escritorio. Un tamaño completo (Haystack) y uno pequeño (needle). Luego recorro la imagen del pajar e intento encontrar la imagen de la aguja.

1. aguja de captura y pajar pantalla
2. bucle a través de pajar, mirando hacia fuera para pajar [i] == primer pixel de la aguja
3. [si es verdad 2.:] bucle a través del segundo al último píxel de aguja y compárela con el pajar [i]

Resultado esperado: la imagen de la aguja se encuentra en la ubicación correcta.

Ya lo tengo trabajando para algunas coordenadas/anchuras/alturas (A).

Pero a veces las piezas parecen estar "apagadas" y por lo tanto no se ha encontrado ninguna coincidencia (B).

¿Qué podría estar haciendo mal? Cualquier sugerencia es bienvenida. Gracias.

---

var needle_height = 25; 
var needle_width = 25; 
var haystack_height = 400; 
var haystack_width = 500; 

---

A. ejemplo de entrada - Partido de

var needle = screenshot(5, 3, needle_width, needle_height); 
var haystack = screenshot(0, 0, haystack_width, haystack_height); 
var result = findmatch(haystack, needle); 

B. ejemplo de entrada - NO partido

var needle = screenshot(5, 5, needle_width, needle_height); 
var haystack = screenshot(0, 0, haystack_width, haystack_height); 
var result = findmatch(haystack, needle); 

---

imagen pajar

1. aguja de captura y

private int[] screenshot(int x, int y, int width, int height) 
{ 
Bitmap bmp = new Bitmap(width, height, PixelFormat.Format32bppArgb); 
Graphics.FromImage(bmp).CopyFromScreen(x, y, 0, 0, bmp.Size); 

var bmd = bmp.LockBits(new Rectangle(0, 0, bmp.Width, bmp.Height), 
    ImageLockMode.ReadOnly, bmp.PixelFormat); 
var ptr = bmd.Scan0; 

var bytes = bmd.Stride * bmp.Height/4; 
var result = new int[bytes]; 

Marshal.Copy(ptr, result, 0, bytes); 
bmp.UnlockBits(bmd); 

return result; 
} 

2. tratar de encontrar un partido

public Point findmatch(int[] haystack, int[] needle) 
{ 
var firstpixel = needle[0]; 

for (int i = 0; i < haystack.Length; i++) 
{ 
    if (haystack[i] == firstpixel) 
    { 
    var y = i/haystack_height; 
    var x = i % haystack_width; 

    var matched = checkmatch(haystack, needle, x, y); 
    if (matched) 
     return (new Point(x,y)); 
    } 
}  
return new Point(); 
} 

3. verificar partido completo

public bool checkmatch(int[] haystack, int[] needle, int startx, int starty) 
{ 
    for (int y = starty; y < starty + needle_height; y++) 
    { 
     for (int x = startx; x < startx + needle_width; x++) 
     { 
      int haystack_index = y * haystack_width + x; 
      int needle_index = (y - starty) * needle_width + x - startx; 
      if (haystack[haystack_index] != needle[needle_index]) 
       return false; 
     } 
    } 
    return true; 
} 

Answer 1

Primero, hay un problema con el lazo findmatch. Usted no sólo debe usar la imagen como una matriz pajar, porque hay que restar el ancho y la altura de la aguja de derecha e inferior, respectivamente:

public Point? findmatch(int[] haystack, int[] needle) 
{ 
    var firstpixel = needle[0]; 

    for (int y = 0; y < haystack_height - needle_height; y++) 
     for (int x = 0; x < haystack_width - needle_width; x++) 
     { 
      if (haystack[y * haystack_width + x] == firstpixel) 
      { 
       var matched = checkmatch(haystack, needle, x, y); 
       if (matched) 
        return (new Point(x, y)); 
      } 
     } 

    return null; 
} 

Esto probablemente se debe resolver el problema. Además, tenga en cuenta que puede haber múltiples coincidencias. Por ejemplo, si "aguja" es una parte del rectángulo completamente blanca de una ventana, lo más probable es que haya muchas coincidencias en toda la pantalla. Si esto es una posibilidad, modificar su método de findmatch para continuar la búsqueda de resultados después de la primera de ellas se encuentra:

public IEnumerable<Point> FindMatches(int[] haystack, int[] needle) 
{ 
    var firstpixel = needle[0]; 
    for (int y = 0; y < haystack_height - needle_height; y++) 
     for (int x = 0; x < haystack_width - needle_width; x++) 
     { 
      if (haystack[y * haystack_width + x] == firstpixel) 
      { 
       if (checkmatch(haystack, needle, x, y)) 
        yield return (new Point(x, y)); 
      } 
     } 
} 

Después, usted necesita para mantener un hábito de disponer manualmente todos los objetos que implementan IDisposable, que ha creado tú mismo. Bitmap y Graphics son tales objetos, lo que significa que su método de screenshot necesita ser modificado para envolver los objetos en using declaraciones:

private int[] screenshot(int x, int y, int width, int height) 
{ 
    // dispose 'bmp' after use 
    using (var bmp = new Bitmap(width, height, PixelFormat.Format32bppArgb)) 
    { 
     // dispose 'g' after use 
     using (var g = Graphics.FromImage(bmp)) 
     { 
      g.CopyFromScreen(x, y, 0, 0, bmp.Size); 

      var bmd = bmp.LockBits(
       new Rectangle(0, 0, bmp.Width, bmp.Height), 
       ImageLockMode.ReadOnly, 
       bmp.PixelFormat); 

      var ptr = bmd.Scan0; 

      // as David pointed out, "bytes" might be 
      // a bit misleading name for a length of 
      // a 32-bit int array (so I've changed it to "len") 

      var len = bmd.Stride * bmp.Height/4; 
      var result = new int[len]; 
      Marshal.Copy(ptr, result, 0, len); 

      bmp.UnlockBits(bmd); 

      return result; 
     } 
    } 
} 

El resto del código parece bien, con la observación de que no va a ser muy eficiente para ciertas entradas. Por ejemplo, puede tener un color sólido grande como fondo de su escritorio, lo que puede dar lugar a muchas llamadas checkmatch.

Si le interesa el rendimiento, tal vez quiera comprobar diferentes formas de acelerar la búsqueda (me viene a la memoria algo así como un Rabin-Karp modificado, pero estoy seguro de que hay algunos algoritmos que aseguran que los candidatos inválidos se salten inmediatamente).

Answer 2

lugar de haciendo dos capturas de pantalla de su escritorio con un intervalo de tiempo entre ellas, tomaría una captura de pantalla una vez y cortaría "aguja" y "pajar" de esa misma fuente de mapa de bits. De lo contrario, corre el riesgo de cambiar los contenidos de su escritorio entre los dos momentos en que se toman las capturas de pantalla.

EDITAR: Y cuando su problema aún ocurra después de eso, trataría de guardar la imagen en un archivo y volver a intentar con ese archivo usando su depurador, dándole una situación reproducible.

Answer 3

No creo que sus ecuaciones para haystack_index o needle_index sean correctas.Parece que toma el desplazamiento Scan0 en la cuenta cuando copia los datos del mapa de bits, pero necesita usar el mapa de bits Stride al calcular la posición del byte.

Además, el formato Format32bppArgb utiliza 4 bytes por píxel. Parece que está asumiendo 1 byte por píxel.

Aquí está el sitio que solía ayudar con esas ecuaciones: http://www.bobpowell.net/lockingbits.htm

Format32BppArgb: Teniendo en cuenta las coordenadas X e Y, la dirección del primer elemento en el píxel es scan0 + (y * zancada) + (x * 4). Esto apunta al byte azul. El siguientes tres bytes contiene los bytes verde, rojo y alfa.