views:

3454

answers:

6

There are some topics here that are very helpful on how to find similar pictures.

What I want to do is to get a fingerprint of a picture and find the same picture on different photos taken by a digital camera. The SURF algorithm seams to be the best way to be independent on scaling, angle and other distortions.

I'm using OpenCV with the SURF algorithm to extract features on the sample image. Now I'm wondering how to convert all this feature data (position, laplacian, size, orientation, hessian) into a fingerprint or hash.

This fingerprint will be stored in a database and a search query must be able to compare that fingerprint with a fingerprint of a photo with almost the same features.

Update:

It seems that there is no way to convert all the descriptor vectors into a simple hash. So what would be the best way to store the image descriptors into the database for fast querying?

Would Vocabulary Trees be an option?

I would be very thankful for any help.

+2  A: 

The feature data you mention (position, laplacian, size, orientation, hessian) is insufficient for your purpose (these are actually the less relevant parts of the descriptor if you want to do matching). The data you want to look at are the "descriptors" (the 4th argument):

void cvExtractSURF(const CvArr* image, const CvArr* mask, CvSeq** keypoints, CvSeq** descriptors, CvMemStorage* storage, CvSURFParams params)

These are 128 or 64 (depending on params) vectors which contain the "fingerprints" of the specific feature (each image will contain a variable amount of such vectors). If you get the latest version of Opencv they have a sample named find_obj.cpp which shows you how it is used for matching

update:

you might find this discussion helpful

liza
Hi Liza, thanks for your reply. I looked at the example but don't find any way to transform the vectors of the descriptors stored in CvSeq into an hash value that makes it possible to be stored in a database and be compared to other hashes. Do you have any hint on that?
dan
the CvSeq simply stores float arrays (look at the source code of cvExtractSURF to see how they store it). those arrays (128 or 64 in length) are what you are interested in
liza
by the way, if what you want is get some magical hash which would map all dog images for example to the same hash code, i'm afraid it is more complicated than just extracting the SURF features. Have a look at the link I put on the update
liza
No, I'm trying to find the same picture within a photo. The OpenCV Sample works great with all of my test shots.But I'm still having no clue how to transform the descriptors into a linear hash value to use the Hamming distance to calculate the similarity.
dan
You need to define what you mean by "linear hash" and what you require of it. If I understand you correctly what you really want is a similarity measure between two image, is this the case?
liza
The OpenCV example simply uses the euclidean distance between the descriptor vectors in order to fetch the "nearest neighbor". That means the matching of features is performed by taking a feature vector, computing the (euclidean)distance from it to ALL(hence the "naive") other features and choosing the one with the minimal distance.
liza
Liza, thank you very much for all your help.You are right, I'm looking for a hash fingerprint as a numeric string for every image that can be stored in a relational database. Than I want to calculate the Hamming distance between two images to check if the images are almost the same. My problem is that I don't know how to convert the descriptors vector data into such an string - just like the pHash library does.
dan
I've added an update to my questing clarifying what I've meant by linear hash.
dan
+1  A: 

A trivial way to compute a hash would be the following. Get all the descriptors from the image (say, N of them). Each descriptor is a vector of 128 numbers (you can convert them to be integers between 0 and 255). So you have a set of N*128 integers. Just write them one after another into a string and use that as a hash value. If you want the hash values to be small, I believe there are ways to compute hash functions of strings, so convert descriptors to string and then use the hash value of that string.

That might work if you want to find exact duplicates. But it seems (since you talk about scale, rotation, etc) you want to just find "similar" images. In that case, using a hash is probably not a good way to go. You probably use some interest point detector to find points at which to compute SURF descriptors. Imagine that it will return the same set of points, but in different order. Suddenly your hash value will be very different, even if the images and descriptors are the same.

So, if I had to find similar images reliably, I'd use a different approach. For example, I could vector-quantize the SURF descriptors, build histograms of vector-quantized values, and use histogram intersection for matching. Do you really absolutely have to use hash functions (maybe for efficiency), or do you just want to use whatever to find similar images?

Hi Sheldon,thank you for your reply.Before looking at SURF I was working with the pHash lib. That lib generates a hash value for media data (images, video and audio). Than you could use the Hamming distance to query your database of similar image hashes quite easily.I thought there must be a way to do the same with the SURF descriptors in some way.Now I'm thinking of storing the all the serialized image descriptor array-objects in the database. When I want to find a similar image in the database I have to select row by row and finding similar descriptors by hand. (...)
dan
(continued)The big downside would be a very bad performance for a large image database.I'm wondering how TinEye.com could find similar images so quickly. There must be some trick to query their database very fast.
dan
I think what would help is if you told what exactly are you trying to achieve. Given an image, what are you trying to find? Identical images, similar images, similar images up to rotation/translation scaling? Given an image X, do you want to find only images that are similar to X, or do you also want images that contain X as a sub-part? For example, the query is a face image. Do you want to find other face images, or also full-body photographs that contain the face but also a lot of other stuff? Why did you stop using pHash and decided to work with SURF descriptors instead?
What I'm trying to achieve is to build up a database containing signatures of sample images. Then I want to print out those sample images and take pictures with them with my mobile phone. Then I'm trying to match the photos with the original images from the database. Since the photos will have a different lighting and could be slightly distorted pHash will not work because this lib is not tolerant enough to lightning and other error sources. The SURF algorithm works great. The only problem I have is to store the descriptors in the database in an efficient way for fast querying.
dan
A: 

i use cvsurf descriptor like you and i try to do the same thing as you but i dont know how

what exactly from code must convert from vector to integer ?

and i have a question i want to find out how many degrees are different object in relation to another (each object located in different images)

thanks

ntouros
A: 

It seems like GIST might be a more appropriate thing to use.

http://people.csail.mit.edu/torralba/code/spatialenvelope/ has MATLAB code.

forefinger
A: 

Dan did you find a solution for your question? This is very interesting question how to store image fingerprints in database for further search..

Kirill
A: 

Hi there,

does anyone heard of a VQ implementation in C or C++ ? I'd like to vector quantize Surf descriptors but don't know how to practically do it.

Thx

Jayka