Determining image similarity

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

  1. Amit Sethi wrote:

    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
  2. Endolith wrote:

    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
  3. knoopx wrote:

    just resize the images to 128x128px and will be much faster :)

    Posted 22 Dec 2009 at 4:26 pm
  4. exhuma wrote:

    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
  5. Carlo wrote:

    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
  6. Brett Spurrier wrote:

    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