Quickly calculating the 'dirtied' areas between two similar images

Question

I have two very similar images (specifically, two screenshots) and I'm trying to find the best (quickest) way of finding which areas of the image have changed (as an array of rectangles representing the differing areas)

A few criteria:

• It does not need to be pixel-accurate but must include all changes however small (i.e. it would be acceptable for a single-pixel change to have a large margin of error around it)
• It needs to be fast (Ideally 2x 1920x1080 images should take < 20ms on a typical consumer machine purchased today)
• It does not require a configurable threshold (but if there is a solution that allows for this, it would be a nice bonus)
• It can be assumed that the input images are always perfect loss-less images.

I have two working solutions as is but one is a brute force pixel-by-pixel calculation which of course is very slow. And for the other I tried splitting up the two images into chunks of varying sizes and calculating checksums for each chunk, but this is also quite slow.

Just for those wondering what I'm building - it's a kind of dumber (and slower) remote desktop that can be used in a browser without any plugins.

Answer 1

You will need to do a pixel per pixel comparison. I don't think it should be that slow. For example the code:

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

runs in about 40 ms on my laptop. If it's only grayscale, it runs under 20 ms. If you would use real image data the diff[i] != 0 would indicate a change in the two images.

Your solution might be slow if you are reading the pixel values using Bitmap.GetPixel or another slow method. If that is the case I suggest looking up on the Bitmap.LockBits or using an unsafe method.