3

Suppose I have two similar images as follows

Image 1 (base)

img1

Image 2 (target)

img2

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.

img3

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

pic4

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 1280x960 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.

  • 2
    There are video formats that have full reference frames, then store deltas for the next few frames. Seems like a similar idea. Maybe one of those algorithms could be adapted to this purpose. – user22815 Apr 27 '14 at 5:33
  • Why not just store the coordinates you cropped it from?? Literally 4 bytes of metadata. – Rotem Apr 27 '14 at 8:05
  • @Rotem, I don't think the idea is to fix an existing implementation. I think he's asking a theoretical question. Given the constraints he's set up, what is the best way to solve his problem? – MetaFight Apr 27 '14 at 11:01
  • 1
    @MetaFight I understand the theoretical merits, it's just that the question mentions an intended usage for which this is an overly complicated solution. "My approach is largely based on the fact that the target image is derived from the base image." - given this assumption, I can't imagine a valid practical use in which you could not have the coordinates at hand. IMHO The real interesting theoretical question is the one without this constraint. – Rotem Apr 27 '14 at 11:17
2

You're basically reinventing video compression. See e.g this introductory document describing how MPEG-2 does it, or this for MPEG-4/H264. To address a couple of points in your post:

  • The search can be done much more efficiently than a brute-force scan over all possibilities by starting on a coarse grid (or at lower resolution) to get an estimate of the motion, and then refining it.
  • I believe one of the things MPEG-4 adds to MPEG-2's approach is some notion of segmented regions of a scene (or sprite coding), which allows better compression of objects moving against a static background, layered cel animations and the like. The term "object based video" is often used.
  • My goal is specifically for re-constructing images and image composition, but it looks like the same idea is used for animation/video compression. – That Umbrella Guy Apr 28 '14 at 15:46
  • 1
    Using multiple scans with various grid sizes to quickly filter out obvious places that cannot be candidates makes sense. Checking two possible positions that are one pixel apart really doesn't make a difference if the entire region is invalid. – That Umbrella Guy Apr 28 '14 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.