For a ready made solution of mine along these lines, see Re^3: Identical Files to Symbolic Links. It is not focused on images, but on files -like any solution of this kind- but that's what the OP seems to want anyway. BTW: I still plan on rewriting it, but "ASAP" has not come yet. And it's still serving me right for the moment. Go figure!

I might be more concerned about false negative matches, but it depends upon what the OP meant by comparing images. You could upload a jpeg of a dog that gets an MD5sum of 00000 (or whatever). I could upload a png of that same photo and that gets an M5sum of ABDEF. Someone else could come along an upload another jpeg at a slightly different compression setting and get an MD5sum of A188F.

They're all different files, but they all represent the same image. To try and compensate for that, it'd require a more advanced technique like one of the articles linked to later on here in the thread to actually compare upon how the image actually looks, not merely how it's stored.

Of course, if you just want to make sure the same file isn't uploaded twice, the md5sum should do just fine.

A Super Search using "compare image" in SoPW turns up compare images, Using Perl and the GIMP to compare images, I need a comparison/hashing algorithm (not the usual). and comparing two images and detecting differences (among others) that may be of interest.

Once you've checked the size of the file and found it to be the same as an existing file, if you read a 32-bit word from the middle of both files and compare them, it will eliminate the need to run a full md5 checksum in 99.999999977% of cases.

That's true for any sort of compressed image. But if some of the files are raw bitmap, then filesize is just a function of resolution, and I don't think it's unlikely to find two files with a black or white pixel in the same place.

This is a statistical tactic so the file format is not a factor. Assuming binary files where all 256 values are possible.

If you pick a random offset within two files being compared, and compare the byte values at that offset, then the odds that they will have the same value is:

    256! / (256-2)! / 256^2 = 0.00390625  or 0.4%
[download]

And if you pick two random offsets and compare the bytes drawn from both files at those offsets, then the odds against them both being the same (if the files are different) is the above value squared:

    0.00390625^2 = 0.0000152587890625 or 0.0015%
[download]

Now, seeking to a random offset is much more expensive than reading 2 bytes instead of one once you are there. So, what are the odds of a word (2 sequential bytes), read at the same (random) offset from two files being the same?

    65536! / 65534! / 65536^2 = 0.0000152587890625 or 0.0015%
[download]

Ie. The same as the two random offset case above. And by extension, selecting two words at 2 offsets gives us a probability of:

    0.0000000002328 or 0.000000023%
[download]

Again, if the 2 words are read as a single dword at a single offset, then the odds remain the same.

In other words, the odds of two non-identical files containing the same 32-bit value at the same offset are statistically vanishingly small.

So, when comparing files, if the sizes are the same, there is still no need to read the whole file and perform a checksum or hashing algorithm on them quite yet. By storing a random offset/32-bit value pairing, along with a file's size and checksum/hash, the occasions on which it will be necessary to actually compute the checksum/hash are reduced almost to nil.

The choice of random offset deserves some thought.

Many filetypes have headers which contain control information which is either

• static (as in the 'MZ' in the first two bytes of a dos/win executable; the 'GIF8' bytes in .gif files; the 'JFIF' at offset 6 of jpeg files; etc.).
• or frequently the same in files of the same type containing different data. For example, the 32-bit fields at offset 16 & 20 (width & height respectively) of a .png (and similar fields in other image formats) will contain the same values for images of the same width/height regardless of the content of the images.

There are many other similarly non-diagnostic fields which should be avoided. A simple strategy for avoiding these (in most cases), is to use an offset derived from the filesize (which also reduces the volume of data that needs to be accumulated/stored). Eg. Reading the 32-bit value stored at the halfway point (suitably rounded down to the nearest 4-byte boundary) will avoid most headers in most file formats.

Although this simple (and fast) tactic is not guaranteed to weed out duplicates, the final sanctions are still the calculation of a full checksum or hash from the entire file, or even a full byte-wise comparison, so the risk is negligible. But the tactic serves to eliminate those final, relatively expensive strategies in all but a minuscule number of cases.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

Read one pixel out of an arbitrarily large file?

Nine Nines and two sevens? that's 33 out of a hundred billion!

Yup. Did you read this? Remember, if the two values are the same, you then go on and run a full md5, so there is no risk. But if they are different you saved yourself the bother/expense of doing it. And statistically, that should be the case in a very large percentage of cases.

The reality of any given set of data probably won't reach that theoretical maximum. For a start, many if not most images don't use the alpha byte, so the range of values is reduced to

( ( 2**24 * (2**24 - 2) ) / 2**48 ) == 0.999_999_887_92
[download]

but that's still pretty good odds for the effort of reading 4 bytes and comparing two integers.

Of course, if the two pictures being compared are

1. A 640x480x24-bit color image of a black cat in a coal celler inside the Artic Circle in winter, with no flash.
2. A 640x480x24-bit color image closeup of a black hole.

Then this quick and simple test may not discriminate between them. But then, will the viewers? :)

More seriously, it's possible that the camera that took the images has a bad cell in the CCD that means that one pixel in the same place on every image is always black (or white or red), and this test would fail to distinquish them if it happens to check that exact pixel. But if the dword compared is (semi-)randomly chosen, that would be pretty unlucky.

Even if you mount the camera on a tripod and use a remote trigger to avoid micro-seismic disturbances, and take two frames one after the other, with 16 mlllion colors to choose from for each pixel, even the slightest variation in the light, or focus, or even the battery charge is likely to cause variations in the pixel colors at identical positions in identical shots by the same camera. In 8-bit color/grey scale images, the variation will be less, but then you are comparing 4 pixels not one. In a strictly B&W image, you would be comparing 32 adjacent pixels.

But when the statistically improbable happens and you get a false positive, that false positive would be caught by the full md5 anyway. The point is to save time by avoiding that full md5 (or similar) where possible--not ditch it all together.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

I think it's usually enough to compare the images byte-to-byte. You can do this by storing the md5 sums of all the images somewhere, and when someone wants to upload an image, calculate its md5 sum, compare to all existing ones, and if it's new, add the image and store the md5 sum.

You can calculate md5 sums either with the Digest::MD5 module (which is now distributed with perl) or with the md5sum program found on most unices, or with the GnuPG program.

If you really want to compare the images pixel-by-pixel, that is, compare different formats of the same image as equal, then you have to recompress all the images to a certain format of your choice (also removing all metadata). I don't really think this is really neccessary.

CREATE TABLE `image` (
  `id` mediumint(9) NOT NULL auto_increment,
  `type` varchar(20) default 'jpeg',
  `mime_type` varchar(20) default 'image/jpeg',
  `image` mediumblob,
  `size` mediumint(9) default NULL,
  `width` int(11) default NULL,
  `height` int(11) default NULL,
  `user_id` mediumint(9) default NULL,
  `created` datetime NOT NULL default '0000-00-00 00:00:00',
  `copyright_id` mediumint(9) default NULL,
  `comments` text,
  `hidden` enum('true','false') default 'false',
  PRIMARY KEY  (`id`),
  UNIQUE KEY `uk_image_image` (`image`(256))
)
[download]