Suppose I have two similar images as follows

Image 1 (base)

Image 2 (target)

The second image is basically a variation of the first image, except with a green oval slapped on top (indeed, I used image1 as the base to produce image2). To save space, I realize that instead of storing two separate images, I simply need to store the difference and then record the offset in, say, a text file.

So I would go and arbitrarily crop out that oval that I want, and I’ve effectively shaved off 2 KB in total because my images are solid colors so it’s nicely compressed.

This is (or was?) a common technique used in various applications such as games to push down filesize, especially if you have a single image with dozens of variations, but those variations cover maybe 10% of the entire image, so there’s a lot of redundant data. And if you’re working with full 32bpp with lots and lots of color everywhere, that can add up quite quickly.

Problem

The problem I’m interested in is this: given the base image (image 1) and the cropped variation, merge them together in such a way that you end up with the original image (image 2)

Ideas

If the cropped variation preserved its position by simply removing all the redundant pixels, then the problem is already solved. However, that isn’t always the case.

My approach is largely based on the fact that the target image is derived from the base image. For the above examples, the difference is a single green oval. Because I sloppily cropped out the oval without making any effort to isolate it from the background, I happen to have given myself a way to determine whether the cropped image “fits” in place.

So for example, if I were to randomly place the cropped image somewhere in the middle, I might get something like this

Now when you compare it to the base image, you can see that the red and blue rectangles are slightly off by a lot, and it is obviously visually incorrect.

If I didn’t know anything about the surrounding pixels (for example, if the cropped variation was simply the green oval), then it would be impossible to reproduce the target image without going in there manually.

I can indirectly quantify how “close” my candidate image is to the target image by taking the sum of the differences between all pixels between the candidate image and the base image: the only pixels that should be different are the ones that make up the variation; the rest of the surrounding pixels that just happened to be in the rectangle should be exactly the same as the base image and should contribute a difference of 0.

Basic Solution

A brute-force approach would basically compute the sum of all pixel differences of every possible position that the cropped image can be placed, and then return all the positions that minimize this sum. For sufficiently complex images, the chances that there will be multiple results is pretty small compared to simple images.

At some point I realized that I only have to consider the pixels inside the cropped image’s rectangle, because those are the only pixels in the candidate image that changes compared to the base image, so this avoids some unnecessary computation.

Improvements?

My idea seems kind of slow. Well, it’ll likely take less than a minute for images of size 1280×960 or 1920x1080p, and it’s still a lot faster than doing it by hand.

Can my approach be improved? For example, do I really need to try every possible combination?

It would be interesting to see if there were other ways to approach the problem as well.