I need to calculate the difference between 2 bitmaps and store it as a patch/diff that when applied to bitmap 1 will result in bitmap 2. The reverse is not necessary. I'd like the patch to be as small as possible, but lossless.
A simple implementation would be to find all changed pixels, determine their combined bounding box and store the contents of bitmap 2 within that box. However, if for example there are only small changes in 2 opposite corners of the image, this will store the entire image, wasting a lot of space. Instead, it would be better to include the 2 changes separately.
I imagine there already exists a good algorithm for this, used in e.g. VNC and video compression, but I wasn't able to find it. Do you know it and what it's called?
(The bitmaps in this case represent destructible terrain in a Worms-like game.)
Well, I've come up with something decent, at least for bitmask (black/white) images.
Take bitmap 1:
And bitmap 2:
XOR them together:
Crop edges:
Compress this with PNG or another lossless image codec, which should take care of the large black areas.