Detecting Similar images

Question

Possible Duplicate:
Image comparison algorithm

So basically i need to write a program that checks whether 2 images are the same or not. Consider the following 2 images:

http://i221.photobucket.com/albums/dd298/ramdeen32/starry_night.jpg

http://i221.photobucket.com/albums/dd298/ramdeen32/starry_night2.jpg

Well they are both the same images but how do i check to see if these images are the same. I am only limited to the media functions. All i can think of right now is the width height scaling and compare the RGB for each pixel but wouldnt the color be different?

Im completely lost on this one, any help is appreciated.

*Note this has to be in python and use the (media library)

Answer 1

ImageMagick has Python bindings and a comparison function. It should do most of the work for you, but I've never used it in Python.

Answer 2

Wow - that is a massive question, and one that has a vast number of possible solutions. I'm afraid I'm not a python expert, but I thought your question was interesting - so I wanted to propose a method that I would implement if I were posed with this problem.

Obviously, the two images you posted are actually very different - so you will need to consider 'how much different is the same', especially when working with images and considering different image formats and compression etc.

Anyway, for a solution that allows for a given difference in colour values (but not for pixels to be in the wrong places), I would do something like the following;

1. Pick two images.

2. Rescale the largest image to the exact same height and width as the first (even distorting the image if necessary).

3. Possibly grayscale the images to make the next steps simpler, without losing much in the way of effectiveness. Actually, possibly running edge detection here could work too.

4. Go through each pixel in both images and store the difference in either each of the RGB channels, or just the difference in grayscale intensity. You would end up with an array the size of the image noting the difference between the pixel intensities on the two images.

5. Now, I don't know the exact values, but you would probably then find that if you iterate over the array you could see whether the difference between each pixel in the two images is the same (or nearly the same) across all of the pixels. Perhaps iterate over the array once to find the average difference between the pixel intensities in the two images, then iterate over the image again to see if 90% of the differences fall within a certain threshold (5% difference?).

Just an idea. Of course, there might be some nice functions that I'm not aware of to make this easy, but I wouldn't hold my breath!

Answer 3

I think step 2 of John Wordsworths answer may be one of the hardest - here you are dealing with a stretched copy of the image but do you also allow rotated, cropped or in other ways distorted images? If so you are going to need a feature matching algorithm, such as used in Hugin or other panorama creation software. This will find matching features, distort to fit and then you can do the other stages of comparing. Ideally you want to recognise Van Gogh's painting from photos, even photos on mugs! It's easy for a human to do this, for a computer it needs rather more complex maths.