diff/patch for images

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 c开发者_如何学Pythonhanges.

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)

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.

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
        }
    }

}

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

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.

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.

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.