Visual similarity search algorithm

Question

I'm trying to build a utility like this http://labs.ideeinc.com/multicolr, but I don't know which algorithm they are using, Does anyone know?

Answer 1

Probably just creating a histogram of the colors used in the images, then doing a best fit to the user-selected colors.

Answer 2

All they are doing is matching histograms. So build a histogram for your images. Normalize the histograms by size of image. A histogram is a vector with as many elements as colors. You don't need 32,24, and maybe not even 16 bits of accuracy and this will just slow you down. For performance reasons, I would map the histograms down to 4, 8, and 10-12 bits. Do a fuzzy least distance compare between the all the 4 bit histograms and your sample colors. Then take that set and do the 8 bit histogram compare. Then maybe go up to a 10 or 12 bit histogram compare with the remaining set. This will be the highest performance search, because you are comparing the total set with a very small number of calculations, to find a small subset. Then you work on the small subset with a higher number of calculations, etc. The real big trick is to find the best algorithm for matching similar histograms. Start with the distance calculation. In 3 dimensions i think it was: SQR((x1-x2)^2 + (y1-y2)^2 + (Z1-Z2)^2)...I'm doing this from memory, so look it up to make sure. For your purposes, you will have more than 3 dimensions, so you will have more terms. A 4 bit histogram would have 16 terms, an 8 bit one would have 256 terms, etc. Remember that this kind of math is slow, so don't actually do the SQR part. If you normalize the size of your images small enough, say down to 10,000 pixels, then you know you only will ever have to do x^2 for values 0..10,0000. Precalc a lookup table of x^2 where x goes from 0..10,000. Then your calculations will go fast. When you select a color from the palette, just make a histogram with that color = 10,0000. When select 2, make a histogram with color1=5000,color2=5000 etc. In the end you will have to add in fudge factors to make the application match the real world, but you will find these with testing.

Answer 3

I'd suggest you do some kind of clustering of the colors present in the images in your database. I mean, for each image in your database: - collect the colors of each pixel in the image - perform clustering (let's say k-mean clustering with 5 clusters) on the collected colors - store the clustered colors as representative descriptor of the image

When the user provide set of one or more query colors you do some kind of greedy matching choosing the best match between the given colors and the color descriptor (the 5 reprsentative colors) of each image in your database.

What is the size of your image collection, because depending on the size some search indexing can prove to be bigger problem than the alogorith itself?