How to check if an image is a scaled version of another image

Question

Hi,

I am looking for an EASY way to check if an image is a scaled version of another image. It does not have to be very fast, it just should be "fairly" accurate. And written in .NET. And for free.

I know, wishful thinking :-)

I am pretty sure, even without having tried it, that converting the bigger image to the smaller scale and comparing checksums is not working (especially if the smaller version was done with another software then .NET).

The next approach would be to scale down and compare pixels. But first of all, it seems like a really bad idea running a loop over all pixels with a bool comparison results, I am sure there will be some pixels off by a bit or so...

Any library coming to mind? Way back in the university we had some MPEG7 classes, so I am thinking about using a combination of "statistics" like tone distribution, brightness, etc..

Any ideas or links for that topic?

Thanks, Chris

Answer 1

You'll have to loop over the pixels at some point or another. Something that is easy to implement yet quite powerful is to calculate the difference between individual color components (RGB) for each pixel, find the average, and see if it crosses a certain threshold. It's certainly not the best method, but for a quick check it should do.

Answer 2

One idea to achieve this:

If the image is 10x10, and your original is 40x40

Loop each pixel in the 10x10, then retrieve the 4 pixels representative of that looped pixel.

So for each pixel in the smaller image, find the corresponding scaled amount of pixels in the larger image.

You can then take the average colour of the 4 pixels, and compare with the pixel in the smaller image. You can specify error bounds, IE -10% or +10% bounds are considered a match, others are considered a failure.

Build up a count of matches and failures and use the bounds to determine if it is considered a match or not.

I think this might perform better than scaling the image to the same size and doing a 1pixel:1pixel comparison as I'm not sure how resizing algorithms necesserially work and you might lose some detail which will give less accurate results. Or if there might be different ways and methods of resizing images. But, again I don't know how the resize might work depends on how you go about doing it.

Answer 3

The easiest way is just to scale the biggest image to the smaller images size and compare color difference. Since you don't know if the scaling is cubic or linear (or something else) you have to accept a small difference.

Don't forget to take the absolute value of each pixel difference. ;)

Answer 4

I'd have said roughly what Tom Gullen except I'd just scale down the bigger image to the smaller before comparing (otherwise you're just going to have hard maths if you are comparing a 25x25 with a 30x30 or something).

The other thing I might consider depending on image sizes is to scale them both down to a smaller image. ie if you have one that is 4000x4000 and another that is 3000x3000 then you can scale them both down to 200x200 and compare them at that size.

As others have said you would then need to do a check with a threshold (preferably on colour components) and decide what tolerances work best. I'd suggest this is probably best done by trial and error.

Answer 5

Having absolutely no authority or experience in this area I'm going to make a stab at helping you.

I'd start with the aspect ratio matching by some tolerance, unless you're comparing cropped sections of images, which will makes things a bit harder.

I'd then scan the pixels for regions of similarity, no exactness, again a tolerance level is needed. Then when an area is similar, run along in a straight line comparing one to the other, and find another similarly coloured area. Black & white's gonna be harder.

If you get a hit, you'll have two areas in a line with patches of likeness. With two points you have a reference of length between them and so now you can see what the scaling might be. You could also scale the images first, but this doesn't account for cropped sections where aspects don't match.

Now choose a random point in the source image and get the colour info. Then using the scale factor, find that same random point on the other image and see if the colour checks out. Do it a few times with random points. If many turn up similar it's likely a copy.

You might then want to mark it for further, more CPU intensive, inspection. Either a pixel by pixel comparison or something else.

I know Microsoft (Photosynth) use filters like "outline" (the sort of stuff in Photoshop) to remove the image colours and leave just squrly lines which leave just the 'components' of the picture for matching (they match boundaries and overlap).

For speed, I'd break the problem down into chunks and really think about how humans decide two photos are similar. For non-speed, exhaustively comparing colour will probably get you there.

The process in short:

If you hole punched a sheet of paper randomly 4 times, then put it over two photos, just by seeing the colours coming through you could tell if they were likely a copy and need further inspection.

Answer 6

Just scale the larger image back to the size of the smaller one, then compare each pixel by taking the absolute value of the difference in each of the red, green and blue components.

You can then set a threshold for deciding how close you need to be to count it as a match, e.g. if 95%+ of the pixels are within 5% of the colour value, you have a match.

The fuzzy match is necessary because you may have scaling artefacts / anti-aliasing effects.