Comparing (similar) images with Python/PIL

Question

I'm trying to calculate the similarity (read: Levenshtein distance) of two images, using Python 2.6 and PIL.

I plan to us e the python-levenshtein library for fast comparison.

Main question:

What is a good strategy for comparing images? My idea is something like:

• Convert to RGB (transparent -> white) (or maybe convert to monochrome?)
• Scale up the smaller one to the larger one's size
• Convert each channel (= the only channel, if converted to monochrome) to a sequence (item value = color value of the pixel)
• Calculate the Levenshtein distance between the two sequences

Of course, this will not handle cases like mirrored images, cropped images, etc. But for basic comparison, this should be useful.

Is there a better strategy documented somewhere?

EDIT: Aaron H is right about the speed issue. Calculating Levelshtein takes about forever for images bigger then a few hundred by a few hundred pixels. However, the difference between the results after downscaling to 100x100 and 200x200 is less then 1% in my example, so it might be wise to set up a maximum image size of ~100px or so...

EDIT: Thanks PreludeAndFugue, that question is what I was looking for.

By the way, Levenshtein distance can be optimized it seems, but it is giving me some really bad results, perhaps because of there's lots of redundant elements in the backgrounds. Got to look at some other algorithms.

EIDT: Root mean square deviation and Peak signal-to-noise ration seem to be another two options that are not very hard to implement and are seemingly not very CPU-expensive. However, it seems I'm going to need some kind of a context analysis for recognizing shapes, etc.

Anyway, thanks for all the links, and also for pointing out the direction towards NumPy/SciPy.

Ipoh

I can't answer directly, but I suspect that because of the loss of precision of the data in scaling up, you will have a lot of "distance" between the two, where scaling down the larger might result in closer relationship between the two. -- As for Levenshtein distance, I've no idea, but this quote from wikipedia makes me skeptical as to it's usefulness in this application: "The Levenshtein distance can also be computed between two longer strings, but the cost to compute it, which is roughly proportional to the product of the two string lengths, makes this impractical." – Scroggins

This question may help: #613646 – Repudiate

Also, convert PIL image to numpy array to do the mathematical manipulation. numpy is designed to manipulate large arrays of numerical data. This question shows the procedure: https://mcmap.net/q/79946/-how-do-i-convert-a-pil-image-into-a-numpy-array – Repudiate

Answer 1

You can take a look at the stsci library, it is made for comparing and analysing images. It should give you what you want but might be a little overkill.

If ou want to keep it simple you could reduce the amount of colors and the resolution first and then calculate the distance.

Arakawa

Well, as it turned out, the problem with the distance calculation is that it is not really good for finding similar content in the images, since a lot of background is identical; I think I need a more robust algorithm here. – Ipoh

In that case you probably need fourier analysis to detect the lines in the image and compare the shapes. But that's a little more tricky to do. Although scipy could probably help you a lot in that area. – Arakawa

Answer 2

Check out imgSeek:

imgSeek is a collection of free open source visual similarity projects. The query (image you are looking for) can be expressed either as a rough sketch painted by the user or as another image you supply (or an image in your collection). The searching algorithm makes use of multiresolution wavelet decomposition of the query and database images.

Litmus