Simple but efficient way to store a series of small changes to an image?

Question

I have a series of images. Each one is typically (but not always) similar to the previous one, with 3 or 4 small rectangular regions updated. I need to record these changes using a minimum of disk space.

The source images are not compressed, but I would like the deltas to be compressed.

I need to be able to recreate the images exactly as input (so a lossy video codec is not appropriate.)

I am thinking of something along the lines of:

• Composite the new image with a negative of the old image
• Save the composited image in any common format that can compress using RLE (probably PNG.)
• Recreate the second image by compositing the previous image with the delta.

Although the images have an alpha channel, I can ignore it for the purposes of this function.

Is there an easy-to-implement algorithm or free Java library with this capability?

Answer 1

If the changes are going to stay rectangular you could save these sections separately, i.e. the original image plus the changes and their positions.

Answer 2

Experiment a little with existing lossless compressors -- PNG, lossless JPEG, etc -- on an image consisting of the changes only (you can use transparent background for PNG, or some uniform color). These algorithms are very efficient when it comes to compressing an image which is mostly constant, you'll not be able to beat them if you are not an expert.

Answer 3

If the number of rectangles is typically small, and the rectangles themselves are small, you can makes out rows and columns with differences, use that to come up with rectangles that might be different...

Imagine the images with the following pixel values...

0 0 0 1 1 1 2 2 3 3
0 0 1 1 0 0 1 1 2 2
0 0 1 1 0 0 0 1 1 2
0 0 1 1 0 0 0 1 1 2
0 1 1 0 0 3 0 0 1 1
0 1 1 0 0 3 0 0 1 1
0 0 1 1 0 0 0 1 1 2
0 0 1 1 0 0 0 1 1 2
0 0 0 1 1 1 1 1 0 2
2 2 2 2 2 1 1 2 2 2

...and...

0 0 0 1 1 1 2 2 3 3
0 1 1 1 0 0 1 1 2 2
0 1 2 4 0 0 0 1 1 2
0 1 2 3 0 0 0 1 1 2
0 1 1 0 0 3 0 0 1 1
0 1 1 0 0 3 0 0 1 1
0 0 1 1 0 3 3 2 1 2
0 0 1 1 0 3 3 2 1 2
0 0 0 1 1 2 2 2 0 2
2 2 2 2 2 1 1 2 2 2

First you would come up with a mask of which pixels rows, rows, and columns had differences...

    0 1 1 1 0 1 1 1 0 0

0   0 0 0 0 0 0 0 0 0 0
1   0 1 0 0 0 0 0 0 0 0
1   0 1 1 1 0 0 0 0 0 0
1   0 1 1 1 0 0 0 0 0 0
0   0 0 0 0 0 0 0 0 0 0
0   0 0 0 0 0 0 0 0 0 0
1   0 0 0 0 0 1 1 1 0 0
1   0 0 0 0 0 1 1 1 0 0
1   0 0 0 0 0 1 1 1 0 0
0   0 0 0 0 0 0 0 0 0 0

The row and column data give us guidance as to where there might be rectangles...

    0 1 1 1 0 1 1 1 0 0

0   0 0 0 0 0 0 0 0 0 0
1   0 ? ? ? 0 ? ? ? 0 0
1   0 ? ? ? 0 ? ? ? 0 0
1   0 ? ? ? 0 ? ? ? 0 0
0   0 0 0 0 0 0 0 0 0 0
0   0 0 0 0 0 0 0 0 0 0
1   0 ? ? ? 0 ? ? ? 0 0
1   0 ? ? ? 0 ? ? ? 0 0
1   0 ? ? ? 0 ? ? ? 0 0
0   0 0 0 0 0 0 0 0 0 0

Iterate over each of the possible rectangles and decide if there are changes or not and then encode them. You can add other hashing axes instead of rows and columns, if you need to... like you can subdivide the picture into regions and hash on whether a region has any changes, then use the hash to decide whether or not a region needs to be encoded. That you could do an arbitrary number of times and have a reasonably quick algorithm that also produces small files.

Whatever the case, I think your best bet is to build a map of what has been changed and use aggregates that tell you if blocks have been changed to guide your decision-making. If you collect enough of these, you could even create a couple different algorithms that do good jobs under different circumstances and then put them in a Chain of Responsibility that decides which algorithm to use based on the characteristics of the map and hashes you built.