OpenCV / SURF How to generate a image hash / fingerprint / signature out of the descriptors?

Question

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.

Jeans

The code performs what is called "nearest neighbor" matching - taking the descriptor (a vector of size N) and comparing it to a set of other size N vectors (this can be by calculating the Euclidean distance between them or any other distance measure) and selecting the one which is closest. The naive in the name means that the vector is compared with ALL other vectors. There are other algorithms which use approximate nearest neighbor which are less accurate but more efficient – Cannibalism

To make things short - you can't make a hash function out of images (that is too ill posed and presumptuous). You can refer to the literature for nearest neighbor classification or image similarity measures. – Cannibalism

Okay, what would be the best way to store any query the image descriptors than? – Jeans

Everything you seek is contained within my answers, there is really nothing more to it. – Cannibalism

Thanks so much Liza for all your help! Through your hints all of this becomes much more clear to me. – Jeans

It's been almost 2 years since you posted this question. I'd like to do pretty much the exact same thing...have you had any luck? What's worked, what hasn't? Is it possible to create a hash or at least a concise representation of the SURF descriptors for fast lookup? – Drida

Did you find any way, i have the same problem and don't find any solution. Thank ! – Operable

Any solution still find some sort of hash function – Rambert

Answer 1

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

Cannibalism

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? – Jeans

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 – Cannibalism

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 – Cannibalism

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. – Jeans

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? – Cannibalism

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. – Cannibalism

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. – Jeans

I've added an update to my questing clarifying what I've meant by linear hash. – Jeans

Answer 2

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?

Paella

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. (...) – Jeans

(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. – Jeans

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? – Paella

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. – Jeans

Dan, i have the same problem. Did you find a way to achieve this ? Thank – Operable

Answer 3

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

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

Heft

Answer 4

Min-Hash or min-Hashing is a technique that might help you. It encodes the whole image in a representation with adjustable size that is then stored in hash tables. Several variants like Geometric min-Hashing, Partition min-Hash and Bundle min-Hashing do exist. The resulting memory footprint is not one of the smallest but these techniques works for a variety of scenarios such as near-duplicate retrieval and even small object retrieval - a scenario where other short signatures often do not perform very well.

There are several papers on this topic. Entry literature would be: Near Duplicate Image Detection: min-Hash and tf-idf Weighting Ondrej Chum, James Philbin, Andrew Zisserman, BMVC 2008 PDF

Winther