How can I measure the similarity between two images?

Question

I would like to compare a screenshot of one application (could be a Web page) with a previously taken screenshot to determine whether the application is displaying itself correctly. I don't want an exact match comparison, because the aspect could be slightly different (in the case of a Web app, depending on the browser, some element could be at a slightly different location). It should give a measure of how similar are the screenshots.

Is there a library / tool that already does that? How would you implement it?

Answer 1

This depends entirely on how smart you want the algorithm to be.

For instance, here are some issues:

• cropped images vs. an uncropped image
• images with a text added vs. another without
• mirrored images

The easiest and simplest algorithm I've seen for this is just to do the following steps to each image:

1. scale to something small, like 64x64 or 32x32, disregard aspect ratio, use a combining scaling algorithm instead of nearest pixel
2. scale the color ranges so that the darkest is black and lightest is white
3. rotate and flip the image so that the lighest color is top left, and then top-right is next darker, bottom-left is next darker (as far as possible of course)

Edit A combining scaling algorithm is one that when scaling 10 pixels down to one will do it using a function that takes the color of all those 10 pixels and combines them into one. Can be done with algorithms like averaging, mean-value, or more complex ones like bicubic splines.

Then calculate the mean distance pixel-by-pixel between the two images.

To look up a possible match in a database, store the pixel colors as individual columns in the database, index a bunch of them (but not all, unless you use a very small image), and do a query that uses a range for each pixel value, ie. every image where the pixel in the small image is between -5 and +5 of the image you want to look up.

This is easy to implement, and fairly fast to run, but of course won't handle most advanced differences. For that you need much more advanced algorithms.