similar images search solution

I've got a really big problem with my image storage server.

There are about 2,000,000 product images on it and keep increasing, but a lots of them are very similar. For example: an iPad photo with many similar sizes 120 * 120, 118 * 120, 131 * 125 ... etc. they took a lots of unnecessary disk space and bad user experience in my website (similar images in gallery).

Those images has indexed in database, I can find them with some conditions, like by product, category etc. I need to find a way to mark these similar开发者_Go百科 images in database and remove them.

What I have done: found a library named pHash can calculate two image's similarity, I can use it calculate images one by one. But in this way it will take a lots of time to find those images. Now I don't know how to make this process be more faster.

Any ideas?

---

• Use pHash to calculate the perceptual hash of all your images (not of the crossproduct of each combination),
• then sort that hash (while keeping the reference to the images),
• then define a critical value of that perceptual hash that you define as "the pictures are equivalent",
• then replace references to equivalent pictures with the reference to the one picture you want to keep.

---

You're right, a naive algorithm would be O(n^2) because you're doing a pairwise comparison across all of your n-sized dataset.

There is a technique called blocking, an implementation of which is canopy clustering, that can get around the pairwise comparisons by partitioning your comparison window size to a set of 'blocks' that are potentially similar.

You can cluster your images by extracting and sorting on a feature vector (which I'm not sure how to do on images).

Then, define a window of comparison, w, such that w < n.

Then apply a technique, called the sorted neighborhood method, which moves a window of fixed size w sequentially over the sorted records. Each image within the window is then paired with its "neighbor" and included in the candidate record pair list.

This basically reduces the comparison complexity to O(w * n), resulting in a linear algorithm with a constant w.

After you've performed the comparisons, you should take the transitive closure over matching pairs.

Your resulting pairs are now what would be considered similar images.

Note, this algorithm is embarrassingly parallel.