How to find the difference between two images?

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.

Solution 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.