Compact bitmap diff/patch

414 views Asked by At

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

1

There are 1 answers

0
Bart van Heukelom On BEST ANSWER

Well, I've come up with something decent, at least for bitmask (black/white) images.

Take bitmap 1:

enter image description here

And bitmap 2:

enter image description here

XOR them together:

enter image description here

Crop edges:

enter image description here

Compress this with PNG or another lossless image codec, which should take care of the large black areas.