Compact bitmap diff/patch

Question

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

Answer 1

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.