diff/patch for images

Question

I'm writing a project where I need to transfer a set of similar images over the net. To speed things up, I thought about doing what most movie codecs do. having keyframes and then just send the changes.

Now, what I got is a set of BufferedImages so in an analogy to text file I basically just want to diff them and send the patch. However I've never really worked with images before so if I will do this, it will be rather crappy.

So, what's the best way of implementing something like this, or is there already an good implementation for something like this?

I guess storing the images in a byte array and binary diff them wont be very effective.

Edit: I need to stream this the images. Edit2: It's not so much about the specifics of the implementation it's more: what is the most efficient idea for an algorithm. Like only work with 5px chunks and not ignore a px if it has only changed so little the eye won't notice (I can live with some quality loss)

Cimbalom

Maybe you could let an existing compression algorithm do the work for you by packing up the images into one large image (and compressing that in any common format), or into a zip (or similar) archive. – Endoscope

not an option if i need to stream them. – Cimbalom

What kind of streaming are we talking about? – Spiny

Remove the profanity from your question. That is not welcome here. – Thegn

@Damokles well, by the time I know what changed, I have already sent the keyframe – Cimbalom

Could you describe the nature of the images more, and how similar they are to each other. Furthermore how many updates per second are we talking about? – Spiny

Lots of chucks with the same color, about 1000x1000 px downscaled, at LEAST 1/s better 3/s that's REALLY hard with 100kbps upstream. – Cimbalom

Have you tried anything already? – Xmas

Answer 1

A simplistic approach would be to do the equivalent of an XOR operation on the two images. This will reveal the pixels that are identical (will be zero) and the pixels that have changed (non-zero).

If you don't care for nearly imperceptible differences then alternatively, use a 'subtract' blend then right-shift to discard one or two bits difference.

You could then calculate the bounds (maybe a simple rectangle) and only transmit the delta. The delta will likely contain a lot of zeroes or at most bytes with few rightmost bits of difference—i.e., it will have low 'entropy' which means it should theoretically be highly compressible using contemporary compression algorithms.

On the receiving end, the reverse process is just as simple. Given the delta and the bounding box, decompress the delta, then apply it (XOR, or left-shift then add) to the affected region of the previous/existing image.

For a more sophisticated, lossless approach, look into how animated GIF/PNGs are animated and what algorithms are used to compute/encode the delta information between frames. See, for example, What's the best way to make an animated GIF using an algorithm?

For an even more sophisticated approach, when dealing with real-world imagery and if you're willing to go the lossy route—then you already hinted at it. Look at how video codecs encode/transmit frames, for example MPEG Video Encoding.

It goes without saying that because there's a tradeoff between complexity (of the encoding/decoding process) and the reduction in size of transmitted data at some point you'll have to decide whether the added overhead in computation on either end is worth the savings in transmission.

Overindulge

Answer 2

You can iterate over all the pixels of a BufferedImage using getRGB(int x, int y).

for (int x = 0; x < img.getWidth(); ++x)
{
    for (int y = 0; y < img.getHeight(); ++y)
    {
        int oldARGB = oldImg.getRGB(x, y);
        int newARGB = img.getRGB(x, y);
        if (oldARGB != newARGB)
        {
            // handle the diffrence
        }
    }

}

Striation

handle the diffrence I think that is the really interesting part. You need to be able to transmit the differences in a way that is efficient. – Spiny

thanks, but my question was more on how a good algorithm could look like. i mean i can live with some quality loss. So I don't need to update a pixel if the alpha value has changed by one. what's the best thing to do this, like working with 5x5px chunks or whatever and yes, handling the difference is what I really care about. – Cimbalom

You could create a new BufferedImage (the delta), initially all pixels 100% transparent (or some other fixed value), and copy all changed pixels to that image. Send it as a PNG, and loop through all the pixels on the receiving end, copying the non-transparent pixels over. – Endoscope

"I don't need to update a pixel if the alpha value has changed by one." You could probably handle this fairly effectively by keeping a server-side copy of the image as the client sees it, and only include changed pixels a la jollybox's method if the RGB difference between reference and actual exceeds some threshold. – Cerberus

Answer 3

I got an idea, actually this is very simple. Compare pixel one by one

If pixel equal, then save as RGBA(0, 0, 0, 0). Then store the diff as PNG.

This is the demo result. the diff is very small.

The stackoverflow say you need at least 10 reputation to post images. So I can only post image address here.

http://oi61.tinypic.com/2vs5ifl.jpg

Typehigh

Answer 4

Depending on the amount of work you want to invest I would suggest a rather easy solution, save those images as bitmaps and let 7z compress them. Then send the archive.

Suffer

yeah, unfortunately this is not what i'm looking for i really need to "diff" them because it needs to be fast. – Cimbalom

Answer 5

If you don't mind some decrease in quality and want a really efficient solution in terms of bandwidth without a lot of manual work for you, you could also just encode you images with a real movie codec. Especially you have a GPU to offload the computation that approach can also be very efficient in terms of computational effort.

Bremen

Answer 6

Your time is probably better spent developing the app, and then evaluating performance improvements if it is a problem. I am guessing this whole thing will be YAGNI.

To speed things up, I thought about doing...

This isn't a requirement, just a 'wouldn't it be cool if...'. With network speeds of today, transferring even a couple hundred megs can be done in less than a minute.

Xmas

I have 2 MBps upstream. If poor internet is requiring this much complexity of code, maybe the easy solution is get a better internet package? Sorry if this answer isn't what you wanted to hear, i just wanted to provide a different viewpoint. – Xmas