How to find the difference between two images?

Question

I'm developing a screen-sharing application. In this project I need to transport images over the internet. Obviously, I can't send a new picture over the internet every few seconds, it would be extremely slow. I want to send one image of the server's screen to the client, and afterwards, instead of sending a new picture sending only the pixels that have been changed since the last image (the one the client already has).

I have written this code:

private List<Color> CompareBitmaps(Image old, Image _new)
{
    List<Color> returnList = new List<Color>();

    for(int i = 0; i < old.Width; i++)
        for (int j = 0; j < old.Height; j++)
        {
            if (((Bitmap)old).GetPixel(i, j) != ((Bitmap)_new).GetPixel(i, j))
            {
                returnList.Add(((Bitmap)_new).GetPixel(i, j));
            }
        }

return returnList;
}

However, it works way too slow.

I'm looking for a faster algorithm, one with a better complexity.

Note: I don't want a built library that does that. I need an algorithm.

Answer 1

This routine finds the differences between two Bitmaps and returns them in the 1st Bitmap by setting everything else to almost black and pretty much transparent. It can also restore the original 2nd file by adding the result back into the previous image..

I shrunk a screenshot of 800MB 1o 12k - but there was really just a very small change at the Clocks hands ;-) If your images differ in many pixels, the compression will not be as spectacular..but I believe it will b good enough for tranmitting and I doubt anything on a pixel by pixel basis will compare to the compression routines of png or jpg file formats.. (you don't transmit bmps, I hope!)

The routine uses LockBits and is pretty fast.

The bool parameter decides whether to create the difference bitmap or to restore the changed bitmap.

public static Bitmap Difference(Bitmap bmp0, Bitmap bmp1, bool restore)
{
    int Bpp = 4;  // assuming an effective pixelformat of 32bpp
    var bmpData0 = bmp0.LockBits(
                    new Rectangle(0, 0, bmp0.Width, bmp0.Height),
                    ImageLockMode.ReadWrite, bmp0.PixelFormat);
    var bmpData1 = bmp1.LockBits(
                    new Rectangle(0, 0, bmp1.Width, bmp1.Height),
                    ImageLockMode.ReadOnly, bmp1.PixelFormat);

    int len = bmpData0.Height * bmpData0.Stride;
    byte[] data0 = new byte[len];
    byte[] data1 = new byte[len];
    Marshal.Copy(bmpData0.Scan0, data0, 0, len);
    Marshal.Copy(bmpData1.Scan0, data1, 0, len);

    for (int i = 0; i < len; i += Bpp)
    {
        if (restore)
        {
            bool toberestored = (data1[i  ] != 2 && data1[i+1] != 3 && 
                                 data1[i+2] != 7 && data1[i+2] != 42);
            if (toberestored)
            {
                data0[i  ] = data1[i];    // Blue
                data0[i+1] = data1[i+1];  // Green 
                data0[i+2] = data1[i+2];  // Red
                data0[i+3] = data1[i+3];  // Alpha
            }
        }
        else
        {
            bool changed = ((data0[i  ] != data1[i  ]) ||  
                            (data0[i+1] != data1[i+1]) || (data0[i+2] != data1[i+2]) );
            data0[i  ] = changed ? data1[i  ] : (byte)2;   // special markers
            data0[i+1] = changed ? data1[i+1] : (byte)3;   // special markers
            data0[i+2] = changed ? data1[i+2] : (byte)7;   // special markers
            data0[i+3] = changed ? (byte)255  : (byte)42;  // special markers
        }
    }

    Marshal.Copy(data0, 0, bmpData0.Scan0, len);
    bmp0.UnlockBits(bmpData0);
    bmp1.UnlockBits(bmpData1);
    return bmp0;
}

Notes: - I have chosen a special color to mark those pixels that need to be restored at the recipient. Here I chose alpha=42 and R=7; G=3; B=2;.. Not 100% safe but almost; not a lot of pixels will be missed; and maybe you don't have tranparency anyway..?

I append two smaller images, both PNGs, around 400kB:

This is the difference image (3kB):

The restored image is the same as the 2nd image.

Answer 2

This may or may not work perfectly, but here goes. You can parallelize this if you see so fit by adding AsParallel.

I also copied and pasted a few lines in here, so feel free to let me know or edit if I have any typos or mismatched variables. But this is the gist of it. This should be pretty quick, within reason.

Essentially, since this might be a bit hard to understand as-is, the idea is to "lock" the bits, then use that pointer to copy them to a byte[]. That effectively copies out all the RGB(A) values, which you can then access really easily. This is a ton faster than GetPixel when you're reading, as you are, more than a pixel or two, because it takes a little while to grab the pixels out, but then it's just simple reads against memory.

Once I get them into the byte[]s, it's easy enough to just compare those for each pixel coordinate. I chose to use LINQ so that it's really easy to parallelize if need be, but you may or may not choose to actually implement that. I'm not sure whether you'll need to.

I've made a few assumptions here that I believe are fair, since it sounds like your implementation has all images coming from a single source. Namely, I assume that the images are the same size and format. So if that's not actually the case, you'll want to address that with some extra code in here, but that's still pretty easy.

private byte[] UnlockBits(Bitmap bmp, out int stride)
{
    BitmapData bmpData = bmp.LockBits(new Rectangle(Point.Empty, bmp.Size), System.Drawing.Imaging.ImageLockMode.ReadOnly, bmp.PixelFormat);

    IntPtr ptr = bmpData.Scan0;

    stride = bmpData.Stride;

    int bytes = Math.Abs(bmpData.Stride) * bmp.Height;

    byte[] ret = new byte[bytes];

    System.Runtime.InteropServices.Marshal.Copy(ptr, ret, 0, bytes);

    bmp.UnlockBits(bmpData);

    return ret;
}

private bool AreArraysEqual(byte[] a, byte[] b, int offset, int length)
{
    for (int v = 0; v < length; v++)
    {
        int c = v + offset;

        if (a[c] != b[c])
        {
            return false;
        }
    }
    return true;
}

private IEnumerable<KeyValuePair<Point, Tuple<Color, Color>>> GetDifferences(Bitmap a, Bitmap b)
{
    if (a.PixelFormat != b.PixelFormat)
        throw new ArgumentException("Unmatched formats!");

    if (a.Size != b.Size)
        throw new ArgumentException("Unmatched length!");

    int stride;
    byte[] rgbValuesA = UnlockBits(a, out stride);
    byte[] rgbValuesB = UnlockBits(b, out stride);

    if (rgbValuesA.Length != rgbValuesB.Length)
        throw new ArgumentException("Unmatched array lengths (unexpected error)!");

    int bytesPerPixel = Image.GetPixelFormatSize(a.PixelFormat) / 8;

    return Enumerable.Range(0, a.Height).SelectMany(y =>
           Enumerable.Range(0, a.Width)
                     .Where(x => !AreArraysEqual(rgbValuesA,
                                                 rgbValuesB,
                                                 (y * stride) + (x * bytesPerPixel),
                                                 bytesPerPixel))
                     .Select(x =>
                             {
                                 Point pt = new Point(x, y);

                                 int pixelIndex = (y * stride) + (x * bytesPerPixel);

                                 Color colorA = ReadPixel(rgbValuesA, pixelIndex, bytesPerPixel);
                                 Color colorB = ReadPixel(rgbValuesB, pixelIndex, bytesPerPixel);

                                 return new KeyValuePair<Point, Tuple<Color, Color>>(pt, colorA, colorB);
                             }
}

private Color ReadPixel(byte[] bytes, int offset, int bytesPerPixel)
{
    int argb = BitConverter.ToInt32(pixelBytes, offset);

    if (bytesPerPixel == 3) // no alpha
        argb |= (255 << 24);

    return Color.FromArgb(argb);
}

public IEnumerable<KeyValuePair<Point, Color>> GetNewColors(Bitmap _new, Bitmap old)
{
    return GetDifferences(_new, old).Select(c => new KeyValuePair<Point, Color>(c.Key, c.Value.Item1));
}

In a true implementation, you might want to think about endianness and pixel format a bit more thoroughly than I have, but this should work more or less as a proof of concept, and I believe should handle a majority of practical cases.

And as @TaW said in a comment, you could also try blanking out (setting alpha to zero, probably) any that haven't changed. You can also benefit from pixel unlocking for that, too. Again, there are likely tutorials that tell you how to do it. But much of this could remain the same.

Answer 3

I'm not sure of what you're trying to do with this code, because you aren't saving the indexes that have changed...

You may want to use an other constructor for your List, because List() haves a default capacity of 0

That mean you will re-allocate the internal buffer of the List maybe many times if many pixels have changed

Maybe recording the average number of pixels that has changed and setting the initial capacity of your List to that number can accelerate your code. At least, you can say that, E.g. 10% of the pixel change every frame :

List<Color> returnList = new List<Color>( (int)( 0.10 * numberOfPixel ) );

Answer 4

You need to return all the changed pixels, so the complexity will have to be m*n.

1. (Bitmap)_new).GetPixel(i, j) is called twice, use a temp value to store it might be a little better.

2. the pixel should have several values right? can you try to create a function called comprareTwoPixel(color A, color B)? and compare all the values one by one, if one of them is false, you don`t need to compare the rest, just return false. (Not sure if this will make it faster or not though.)

Like:

bool comprareTwoPixel(color A, color B)
{
    if(A.a!=B.b)
        return false;
    if(A.b!=B.b)
        return false;
    if(A.c!=B.c)
        return false;

    return true;
}