3
$\begingroup$

I'm using an algorithm to detect interest points in an image and get their descriptor. The most recent algorithms use binary strings instead of float vectors to dramatically increase the performance because inserting those float vectors in a database and comparing them to whatever will suffer the curse of dimensionality. The thing that bothers me is, if those algorithms convert the descriptors into binary strings, why does it still return a float vector? Do I need to binarise it manually?

Just a quick note, I'm also studying complementary solutions (e.g. Neural Network) for this large-dimension querying issue.

EDIT:

Found a very interesting paper on the subject, but I'm having a hard time understanding how it's effectively done. Besides, I fear that this binarization is already being done somewhere in the descriptor extraction algorithm.

|improve this question
$\endgroup$
  • $\begingroup$ Why do you think they are returning a float vector? Can you post the opencv code you are using to get the feature descriptors? If you use BRISK for example, you can type cast to bool and see the feature descriptor in Microsoft Visual Studio (if you are using it). Also for matching, the Hamming distance is used with such descriptors (which is a roundabout way of saying that they can't be floats). $\endgroup$ – Mustafa Oct 31 '12 at 20:53
  • $\begingroup$ It depends on implementation - string of booleans can be stored as array of bytes, which can be in turn read as array of floats (every four bytes can be converted to single-precision floating point number). The neural network approach looks interesting. Do you have any references for that? How long does it take to train the network? How many neurons are usually used for that? Is the performance comparable to principal component analysis (a tool often used to reduce dimensionality). $\endgroup$ – Libor Oct 31 '12 at 23:26
  • $\begingroup$ @Mustafa: If I perform a Hamming distance matcher with about 500 photos it takes a few ms to finish, exactly because it's using the binary descriptors. What I want is to get the same binary descriptor and put it in the database, because at the moment it's inserting float values (what is inserted in the descriptor.compute(...) method). $\endgroup$ – Rafael Soledade Matos Nov 2 '12 at 9:20
  • $\begingroup$ @Libor: The neural network appproach has been discarded after I've had a chat with a PhD fellow that is specializing in the area. He says that for millions of descriptors the neural network will not scale well...it'll be equally slow. He suggested instead SVM or simply pure old-school database optimization. $\endgroup$ – Rafael Soledade Matos Nov 2 '12 at 9:22
4
$\begingroup$

You're mixing together different things, so let's have a look at the big picture first. For object detection / image matching, it's common to use a keypoint-based process:

  1. detect-and-describe keypoints in your database / learning set
  2. (optional) sort your reference descriptors in an acceleration structure (e.g. kd-tree)
  3. detect-and-describe keypoints in your query image
  4. find the nearest neighbors of your query descriptors and your reference set.

The descriptors can be real (floating-points, e.g. SIFT/SURF) or binary (bit-strings, e.g. BRIEF, BRISK, FREAK). Binary descriptors are obtained through a specific design process: the operations used to compute the descriptor are quite different from the operations involved in real descriptors.

Let's take the example of SIFT vs. BRIEF. The SIFT descriptor is made of histograms of the image gradient directions in a patch centered on the keypoint. The BRIEF descriptor can be modeled by a 2-step process: 1. compute a real descriptor by computing the difference between small neighborhoods inside a patch centered on the keypoint 2. binaries descriptor by retaining only the sign of the difference. I have also described this process in a blog post.

So no, you can't just binarize a floating-point descriptor, you need to use a dedicated one.

After that, it's up to you how you do the nearest neighbors queries.

In actual implementations, you may find some weird things about descriptor sizes. The goal is t ensure that the size of a binary feature vector fits with hardware dedicated commands to compute Hamming distances in order to be very fast, and to allow the use of vectorized instructions such as SSE to compare different descriptors at the same time.

|improve this answer
$\endgroup$
  • $\begingroup$ What you said about the very fast computation of hamming distances is what I want to accomplish with database querying. I want to save those binary descriptors as my descriptors in the database, but he just gives me float-point vectors. That's my only problem right now...everything else is being done well and fast. I'm also studying some new alternatives, such as min hash functions (since Neural Networks will not scale well) $\endgroup$ – Rafael Soledade Matos Nov 2 '12 at 9:57
  • $\begingroup$ If your database software only accepts floating points, you can choose a size which is a multiple of 4 bytes and then cast indifferently between float and uint. Note that the database acceleration structures (mostly binary trees) will not really help you because the Hamming distance between features is not related to their L2 distance. $\endgroup$ – sansuiso Nov 2 '12 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.