When I saw this question on stackoverflow asking about how to determine if an image is identical, it reminded me of my favorite class at JHU, Computer Vision. One of the things that I remember is that if you wanted to compute how similar two images are, you’d treat their pixels as vectors, normalize them, then take their dot product. The result is a float between 0 and 1 that indicated the percent similarity of the two images. This process is called the normalized cross correlation. After you got that number, it was a matter of setting a threshold as to what you wanted to accept as similar or not. For fun, I whipped up a naive implementation of normalized cross correlation in Python using PIL and numpy:
import Image from numpy import average, linalg, dot import sys images = sys.argv[1:3] vectors = [] norms = [] for image in images: vector = [] for pixel_tuple in Image.open(image).getdata(): vector.append(average(pixel_tuple)) vectors.append(vector) norms.append(linalg.norm(vector, 2)) a, b = vectors a_norm, b_norm = norms print dot(a / a_norm, b / b_norm)
It’s pretty slow, taking about a minute to process two 400k jpegs on my MacBook Pro, but I bet there’s a nice way to parallelize it (maybe using Python 2.6′s sweet new multiprocessing module?).
Comments 6
This is a nice solution but it does not work many a times as it gives a Value Error: matrices are not aligned . Well i solved this by adding zeros to the smaller Vector making the two vectors equal. I think this is a pretty valid change considering that we are in a sense calculating the euclidean distance.
Posted 07 May 2009 at 6:37 pm ¶1. Cross-correlation is already built into SciPy a few different ways
2. An FFT-based cross-correlation will be much faster. There’s a built-in function for this scipy.stsci.convolve.correlate2d, but it’s broken on my machine:
https://bugs.launchpad.net/bugs/397217
http://projects.scipy.org/scipy/ticket/973
3. Cross-correlation can’t help you if the images have been scaled or rotated, though. Wikipedia says this can be handled by using log-polar coordinates, but I don’t know the details.
http://en.wikipedia.org/wiki/Image_registration#Spatial_vs._frequency_domain_methods
Posted 15 Aug 2009 at 6:56 pm ¶just resize the images to 128x128px and will be much faster
Posted 22 Dec 2009 at 4:26 pm ¶I tried this, adding zeros as Amit proposed. However, with the images I tested, it did not work.
Are there any restrictions to this? Do the images need to be the same size?
Posted 06 Feb 2010 at 12:07 pm ¶Yes, the images have to be the same size. Btw, this post was more of a thought experiment, I’m sure there’s more robust ways to do image similarity out there.
Posted 11 Feb 2010 at 3:14 am ¶Interesting post. I have been following image similarity algorithms for a while but I haven’t found any that scale very well. Cross correlation gives great results, but try doing that across a million plus images.
I wrote a small SDK that I use in my iPhone AppStore app (called eyeBuy) which scans 5 million plus images in a few seconds. If you are interested, I can port it to whatever platform you are using. Have a look: http://sites.google.com/site/imagecomparison/
-Brett
Posted 19 Feb 2010 at 10:52 pm ¶