I have plenty of respect for the people who work in Image Processing. <\/p>\n
However, you wouldn’t guess that from my latest experiment. I didn’t do any reading or studying. I didn’t try to stand on the shoulders of giants. I just plowed in and tried something. Unsurprisingly, I had mixed results.<\/p>\n
Let me build up to the problem…<\/p>\n
Suppose you have a large collection of files, and you suspect there are duplicates. How do you find them?<\/p>\n
The standard solution would be to create a hash of each file and add references to a hash table, looking for duplicates as you go.<\/p>\n
What hash would you use for random files?<\/p>\n
The first thing to remember is you need a better hash than you might think because of the Birthday Paradox<\/a> – there are a lot of pairwise comparisons here – SHA<\/a> (or some other cryptographic hash) would probably be the gold-standard, but it is computationally expensive and unnecessarily secure against forgery.<\/p>\n CRC<\/a> is cheaper, but is intended for checking that files aren’t corrupted. The Python CRC library explicitly warns against using it for hashes. I haven’t completely understood why.<\/p>\n I wonder if XOR could be used as a cheap hash. Divide the file into, say, 64 bit chunks, and XOR them together. It would be hopeless at doing MD5’s job of being unforgeable, and it would be hopeless at doing CRC’s job of detecting missing packets, but it sounds like a cheap and reasonable hash for unknown data. I haven’t investigated further than that.<\/p>\n So, the next trick is to use special hashes (based on knowledge of the type of data) to detect approximate matches.<\/p>\n I last did this in anger about two years ago, when I used the Soundex<\/a> hash to look over our customer database. Soundex is a hash that attempts to make like-sounding English strings end up with the same hash value, so you can fix misspellings and the like. I successfully found several cases where customers appeared twice in our database with slight variations to the spellings of their names.<\/p>\n So, I have lots of photos, and some are duplicated on several web-sites, with no reference to the original source. I want to detect matches, so I can move them (and their associated meta-data) all to a single yet-to-be-determined<\/a> destination.<\/p>\n But here’s the snag. Some of the photos have been made into different sizes and qualities for web-viewing. It would save me time if I could automatically detect this. I need an equivalent to SoundEx that works on images, so images have the same hash even if they are resized.<\/p>\n How would you do that? If you answered “Google it, and find what the standard solution is”, you might be smarter than me. This article is about what I did instead.<\/p>\n Remember what the cost is of making a mistake. <\/p>\n If the algorithm makes a false positive (i.e. declares two photos are the same when they are not), I will notice when I sift through the results and I will correct it. Total cost: 5 seconds effort.<\/p>\n If it makes a false negative (i.e. fails to realise two images are the same), it won’t be as easy to find. I will end up with a duplicate photo in the final database, or I will fail to merge meta-data. Total cost: practically nothing; slightly lower quality photo site.<\/p>\n So, with the stakes so low, I just waded in with my eyes shut and I created my own hash function. <\/p>\n My first version of the hash function had two parts.<\/p>\n The first part was the height:width ratio. I assumed that any two photos whose height:width ratio differed by more than 2% couldn’t be rescalings of the same photo. <\/p>\n The second part was a 5×5 array of tuples. To produce the array, I first divided each photo into 5×5 equal-sized rectangles, and summed all the Red, Blue and Green values for each pixel in each rectangle. <\/p>\nO(n2<\/sup>)<\/code> – and there are likely to be more clashes than you might first expect.<\/p>\nUsing customised hashes to detect approximate matches<\/h4>\n
The Real Problem: Detecting Duplicate Photos<\/h4>\n
Hash Function, Version 1<\/h4>\n