Calcolo rapido delle aree "sporche" tra due immagini simili

Question

Ho due immagini molto simili (in particolare, due schermate) e sto cercando di trovare il modo migliore (più veloce) per individuare quali aree dell'immagine sono cambiate (come una serie di rettangoli rappresentano le differenti aree)

alcuni criteri:

• non deve essere pixel accurata, ma deve comprendere tutte le modifiche per quanto piccola (cioè sarebbe accettabile per un singolo pixel cambiare per avere un ampio margine di errore intorno ad esso)
• Deve essere veloce (Idealmente 2x 1920x1080 im età dovrebbero prendere < 20ms su una tipica macchina di consumo acquistati oggi)
• non richiede una soglia configurabile (ma se c'è una soluzione che consente a questo, sarebbe un bel bonus)
• Si può presumere che le immagini di input sono sempre perfette immagini senza perdita.

Ho due soluzioni di lavoro come è, ma uno è un calcolo forza per pixel forza bruta che, naturalmente, è molto lento. E per l'altro ho provato a dividere le due immagini in blocchi di dimensioni diverse e calcolare i checksum per ogni chunk, ma anche questo è piuttosto lento.

Solo per chi si chiede cosa sto costruendo, è una specie di desktop remoto più stupido (e più lento) che può essere utilizzato in un browser senza plug-in.

Answer 1

È necessario eseguire un confronto pixel per pixel. Non penso che dovrebbe essere così lento. Ad esempio il codice:

 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); 

eseguito in circa 40 ms sul mio laptop. Se è solo in scala di grigi, funziona meno di 20 ms. Se si utilizzano dati di immagine reali, il diff [i]! = 0 indica una modifica delle due immagini.

La soluzione potrebbe essere lenta se si stanno leggendo i valori dei pixel utilizzando Bitmap.GetPixel o un altro metodo lento. In questo caso, suggerisco di cercare su Bitmap.LockBits o utilizzare un metodo non sicuro.

Answer 2

La mia risposta precedente è stata cancellata a causa del suo formato, lo scriverò di nuovo, in un modo migliore.

Ti stavo chiedendo se si considera di utilizzare GPU per calcolare le differenze di immagine tra le due immagini. Questa soluzione potrebbe migliorare notevolmente il tempo di calcolo in quanto la GPU è altamente parallela rispetto al calcolo della CPU.

Utilizzando C#, è possibile provare a utilizzare XNA per questo scopo. Effettivamente ho fatto un piccolo test utilizzando un unico passaggio HLSL (è quello che viene utilizzato per programmare GPU con Direct3D) pixel shader:

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(); 
    } 
} 

Il calcolo da parte XNA è molto semplice. Usando il frammento di base del XNA con Visual Studio, ho appena scritto la funzione di disegno come:

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 e IM2 sono i due 1920 * 1080 immagini BMP colorati caricate come Texture2D, ed e è il file.fx caricato come un effetto.

Utilizzando questa tecnica, ho un 17/18 ms tempo di calcolo sul computer abbastanza regolare (computer portatile con i5-2410M @ 2.3GHz, 4GB di RAM, Nvidia Geforce GT525m.

Ecco l'output del programma, con l'immagine differenza mostrata (scusate questo è altamente ingrandita, perché non ho uno schermo 1920 * 1080:>), e inoltre sono l'im1 due immagini e IM2 con alcune piccole differenze tra loro: http://img526.imageshack.us/img526/2345/computationtime.jpg

sono abbastanza nuovo alla programmazione GPU, quindi se ho fatto un errore enorme su come il tempo dovrebbe essere calcolato o qualsiasi altra cosa, non esitate a dirlo!

Modifica: Prima cosa da notare, ho appena letto che "sarà un'operazione non banale dato che le GPU non gestiscono il branching molto bene".

Cordiali saluti