Calculando rápidamente las áreas "sucias" entre dos imágenes similares

Question

Tengo dos imágenes muy similares (específicamente, dos capturas de pantalla) y estoy tratando de encontrar la mejor (más rápida) forma de encontrar qué áreas de la imagen han cambiado (como un conjunto de rectángulos que representan las zonas diferentes)

algunos criterios:

• no necesita ser pixel-exacta, pero debe incluir todos los cambios sin embargo pequeño (es decir, sería aceptable para un solo píxel cambiar para tener un gran margen de error a su alrededor)
• Necesita ser rápido (Idealmente 2x 1920x1080 im edades deben tomar < 20 ms en una máquina típica de consumo adquiridos en la actualidad)
• que no requiere un umbral configurable (pero si hay una solución que permita esto, sería un buen bono)
• Se puede suponer que las imágenes de entrada son siempre imágenes perfectas sin pérdida.

Tengo dos soluciones de trabajo tal como están pero una es un cálculo de fuerza bruta píxel por píxel que, por supuesto, es muy lento. Y para el otro intento dividir las dos imágenes en trozos de diferentes tamaños y calcular las sumas de comprobación para cada fragmento, pero esto también es bastante lento.

Solo para aquellos que se preguntan qué estoy construyendo, es una especie de escritorio remoto más lento (y más lento) que se puede usar en un navegador sin complementos.

Answer 1

Tendrá que hacer una comparación de píxel por píxel. No creo que deba ser tan lento. Por ejemplo, el código:

 int size = 1920 * 1080 * 3; 
     byte[] image1 = new byte[size]; 
     byte[] image2 = new byte[size]; 
     byte[] diff = new byte[size]; 

     var sw = new System.Diagnostics.Stopwatch(); 
     sw.Start(); 
     for (int i = 0; i < size; i++) 
     { 
      diff[i] = (byte) (image1[i] - image1[i]); 
     } 
     sw.Stop();  
     Console.WriteLine(sw.ElapsedMilliseconds); 

funciona en aproximadamente 40 ms en mi computadora portátil. Si solo es en escala de grises, se ejecuta en menos de 20 ms. Si utilizara datos de imágenes reales, el diff [i]! = 0 indicaría un cambio en las dos imágenes.

Su solución puede ser lenta si está leyendo los valores de píxel usando Bitmap.GetPixel u otro método lento. Si ese es el caso, sugiero buscar en el Bitmap.LockBits o utilizar un método inseguro.

Answer 2

Mi respuesta anterior se eliminó debido a su formato, la escribiré de nuevo, de una mejor manera.

Le pregunté si considera usar GPU para calcular las diferencias de imagen entre sus dos imágenes. Esta solución podría mejorar considerablemente su tiempo de cálculo ya que la GPU es altamente paralela en comparación con el cálculo de la CPU.

Usando C#, podría intentar usar XNA para este propósito. En realidad lo hice una pequeña prueba utilizando un único pase HLSL (que es lo que se utiliza para programar la GPU con Direct3D) sombreado de píxeles:

texture texture1; 
texture texture2; 

sampler textureSampler1 = sampler_state{ 
    Texture = <texture1>; 
}; 

sampler textureSampler2 = sampler_state{ 
    Texture = <texture2>; 
}; 

float4 pixelShaderFunction(float2 TextureCoordinate : TEXCOORD0) : COLOR0{ 
    float4 color1 = tex2D(textureSampler1,TextureCoordinate); 
    float4 color2 = tex2D(textureSampler2,TextureCoordinate); 
    if((color1.r == color2.r) && (color1.g == color2.g) && (color1.b == color2.b)){ 
     color1.r = 0; 
     color1.g = 0; 
     color1.b = 0; 
    } 
    else{ 
     color1.r = 255; 
     color1.g = 255; 
     color1.b = 255; 
    } 

    return color1; 
} 


technique Compare 
{ 
    pass Pass1 
    { 
     PixelShader = compile ps_2_0 pixelShaderFunction(); 
    } 
} 

El cálculo por parte de XNA es muy simple. Utilizando el fragmento de la base de XNA con Visual Studio, que acabo de escribir la función de drenaje como:

protected override void Draw(GameTime gameTime) { 
    Stopwatch sw = new Stopwatch(); 
    sw.Start(); 
    GraphicsDevice.Clear(Color.CornflowerBlue); 
    e.Parameters["texture1"].SetValue(im1); 
    e.Parameters["texture2"].SetValue(im2); 
    spriteBatch.Begin(SpriteSortMode.Immediate, BlendState.AlphaBlend, SamplerState.LinearClamp, DepthStencilState.Default, RasterizerState.CullNone, e); 
    spriteBatch.Draw(im1,new Vector2(0,0),Color.White); 
    spriteBatch.End(); 
    base.Draw(gameTime); 
    sw.Stop(); 
    Console.WriteLine(sw.ElapsedMilliseconds); 
} 

im1 y im2 son los dos 1920 * 1080 imágenes BMP colores cargados como Texture2D, y e es la carga como file.fx Un efecto.

Usando esta técnica, consigo un tiempo de cálculo 17/18 ms en el ordenador bastante regular (ordenador portátil con i5-2410M @ 2,3 GHz, 4 GB de RAM, Nvidia Geforce GT525m.

Aquí está la salida del programa, la la imagen de diferencia se muestra (lo siento esto es muy ampliada, ya que no tengo una pantalla de 1920 * 1080:>), y además son las dos imágenes IM1 e IM2, con algunas pequeñas diferencias entre ellos: http://img526.imageshack.us/img526/2345/computationtime.jpg

soy bastante nuevo a la programación de la GPU, así que si cometí un gran error con respecto a cómo se debe calcular el tiempo o cualquier otra cosa, no dude en decirlo!

Editar: Primero que nada, acabo de leer que "será una operación no trivial ya que las GPU no manejan muy bien las ramificaciones".

Saludos cordiales