File structure for storing pixels that changed from one image to another

Question

Have two images with the same dimensions.

I want to create a file that contains information on what pixels are different between the two images. The file should also tell me the value of the new pixel (integer).

An example of such file is

230,8528
291,920
550,1500

Which tells me that the pixel at index 230 changed to 8528. The one at 291 is now value 920. And the pixel at 550 has value 1500.

I already have the means to get all such data (the indexes where they change and their new integer values). My problem is the storage of such info, which needs to be as small as possible and of course easy to iterate when my program needs to read this data back.

What I got currently is the following file format:

[pixel color], [index], [index], [index], ...
[pixel color], [index], ...
[pixel color], [index], [index], ...

Basically, each line represents a pixel color that has changed, and then separated by commas are the indexes of the pixels that will change to such color.

Is there a more suitable/efficient file structure to achieve this kind of data storage?

Answer 1

It much depends on what the changes are.

If you have lots of changes, you might do well by creating a difference image and encode it using an algorithm such as PNG, leveraging its data compression features.

If you have several changes to the same colour, then your approach might work.

If you have several changes in fixed areas, then storing coordinates and colours independently might yield advantages.

Also the file reading algorithm has its weight. If you store pixels in the same order as they are when reading the image (so, for example:

Y:X,C;X,C;X,C
Y:X,C;X,C;X,C

then you'll be able to decode the image in a single pass without storing everything in memory. Since both image reading and difference file reading are sequential, you can use any of several stream compression libraries to compress the difference file.

In the example above, X is the X coordinate. Since they are sorted, you can store the first number as is, and the next numbers as differences (zero based, offset by 1). So the three X coordinates 17, 25 and 27 become 17, 7 and 1. The advantage is that this increases the probability of smaller numbers coming by; when compressing, having some symbols more likely than others translates in better compression performance.

If you know that your coordinates will never exceed, say, 65535, you can store them as binary words of 16 bits. Then you do not need any separator between numbers; each number is represented by exactly two bytes.

But as you see, it all depends on what your input data actually are.

Update: it actually also depends on what you need to do. If you want to store a delta between two files, it's possible that in some scenarios you might be better served by using an utility such as rdiff instead of rolling (and having to debug and maintain!) your own 'difference engine'.