Algorithm for finding visually similar photos from a database?

Question

TinEye, Google and others offer a "reverse image search" -- you can upload a photo and within seconds it will find similar photos.

Is there an open-source version of these algorithms?

---

I know about "SIFT" and other algorithms for finding "visually similar" photos, but they only work for comparing one photo directly to another. i.e., to find similar photos to a given photo is an O(n) operation, to find all visually similar photos would be O(n^2) -- both of which are prohibitively slow.

I need a feature descriptor that is indexable by a [relational] database to reduce the result set to something more manageable.

By "visually similar" I mean very similar. i.e, a photo that has been lightly touched up/recolored in Photoshop, slightly cropped or resized, photos taken in rapid succession of the same scene, or flipped or rotated images.

Answer 1

A valid approach you can consider is the Bag-of-Words model.

Basically you can do an offline computation of the target images. You can extract from those images a bunch of features in order to create a codebook with algorithms like k-means clustering. Searching for the nearest images will lead to the applications of an algorithm like Nearest neighbor search in the space of the codebook.

For the neighbour search you can use FLANN

• http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN
• http://opencv.willowgarage.com/documentation/cpp/flann_fast_approximate_nearest_neighbor_search.html

Take a look also at: Visual similarity search algorithm

This is only a possibility and, truth must be told, this topic is really challenging and litterature on it is really huge.

Just some references:

• http://www.cs.nott.ac.uk/~qiu/webpages/Papers/ColorPatternRecognition.pdf
• http://cs.brown.edu/~th/papers/Hofmann-UAI99.pdf
• http://www.ifp.illinois.edu/~jyang29/ScSPM.htm
• http://johnwinn.org/Publications/papers/Savarese_Winn_Criminisi_Correlatons_CVPR2006.pdf
• http://www-cvr.ai.uiuc.edu/ponce_grp/publication/paper/cvpr06b.pdf