Nhanh chóng tính toán khu vực 'bẩn' giữa hai hình ảnh tương tự

Question

Tôi có hai hình ảnh rất giống nhau (cụ thể là hai ảnh chụp màn hình) và tôi đang cố tìm cách tốt nhất (nhanh nhất) để tìm khu vực nào của hình ảnh đã thay đổi (như một mảng của hình chữ nhật đại diện cho các lĩnh vực khác nhau)

một vài tiêu chí:

• nó không cần phải pixel chính xác nhưng phải bao gồm tất cả những thay đổi dù nhỏ (tức là nó sẽ được chấp nhận cho một single-pixel thay đổi để có một biên độ lớn của lỗi xung quanh nó)
• Nó cần phải được nhanh chóng (Lý tưởng 2x 1920x1080 im độ tuổi cần lấy < 20ms trên máy tiêu thụ thông thường được mua hôm nay)
• Nó không yêu cầu ngưỡng có thể định cấu hình (nhưng nếu có giải pháp cho phép điều này, nó sẽ là phần thưởng tốt)
• Có thể giả định rằng hình ảnh đầu vào luôn là hình ảnh mất hoàn hảo.

Tôi có hai giải pháp làm việc nhưng đó là một giải pháp tính toán điểm ảnh theo điểm ảnh mà tất nhiên là rất chậm. Và đối với người khác, tôi đã cố gắng chia hai hình ảnh thành nhiều phần có kích thước khác nhau và tính tổng kiểm tra cho mỗi đoạn, nhưng điều này cũng khá chậm.

Chỉ dành cho những người tự hỏi tôi đang xây dựng gì - đó là một loại máy tính từ xa (và chậm) dumber có thể được sử dụng trong trình duyệt mà không cần bất kỳ plugin nào.

Answer 1

Bạn sẽ cần thực hiện so sánh pixel trên mỗi pixel. Tôi không nghĩ rằng nó nên được làm chậm. Ví dụ: mã:

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

chạy trong khoảng 40 ms trên máy tính xách tay của tôi. Nếu nó chỉ màu xám, nó chạy dưới 20 ms. Nếu bạn sử dụng dữ liệu hình ảnh thực, thì diff [i]! = 0 sẽ cho biết sự thay đổi trong hai hình ảnh.

Giải pháp của bạn có thể chậm nếu bạn đang đọc các giá trị pixel bằng cách sử dụng Bitmap.GetPixel hoặc phương pháp chậm khác. Nếu đó là trường hợp tôi đề xuất tìm kiếm trên Bitmap.LockBits hoặc sử dụng phương pháp không an toàn.

Answer 2

Câu trả lời trước của tôi đã bị xóa do định dạng của nó, tôi sẽ viết lại, theo cách tốt hơn.

Tôi đã hỏi bạn xem bạn có cân nhắc sử dụng GPU để tính toán sự khác biệt hình ảnh giữa hai hình ảnh của bạn hay không. Giải pháp này có thể nâng cao đáng kể thời gian tính toán của bạn vì GPU là rất song song so với tính toán CPU.

Sử dụng C#, bạn có thể thử sử dụng XNA cho mục đích này. Trên thực tế tôi đã làm một thử nghiệm nhỏ sử dụng một đường chuyền HLSL duy nhất (đó là những gì được sử dụng để chương trình GPU với 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(); 
    } 
} 

Các tính toán trên một phần XNA là thực sự đơn giản. Sử dụng đoạn mã cơ sở của XNA với visual studio, tôi chỉ viết những chức năng vẽ như:

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 và im2 là những hình ảnh bmp màu hai 1920 * 1080 nạp như Texture2D, và e là file.fx nạp như một hiệu ứng.

Sử dụng kỹ thuật này, tôi nhận được một thời gian tính toán 17/18ms trên máy tính khá thường xuyên (máy tính xách tay với i5-2410M tốc độ 2,3 GHz, RAM 4GB, Nvidia Geforce GT525m.

Đây là kết quả của chương trình, với hình ảnh khác biệt được hiển thị (xin lỗi điều này được thu phóng cao vì tôi KHÔNG có màn hình 1920 * 1080:>) và bên cạnh đó là hai hình ảnh im1 và im2 với một số khác biệt nhỏ giữa chúng: http://img526.imageshack.us/img526/2345/computationtime.jpg

Tôi khá mới để lập trình GPU, vì vậy nếu tôi thực hiện một sai lầm lớn liên quan đến cách tính thời gian hoặc bất kỳ điều gì khác, vui lòng cho biết!

Chỉnh sửa: Điều đầu tiên cần lưu ý, tôi chỉ đọc rằng "nó sẽ là một hoạt động không thuận lợi vì GPU không xử lý phân nhánh rất tốt".

Trân trọng