Following the previous posts that provided both an introduction to patch descriptors in general and specifically to binary descriptors, it’s time to talk about the individual binary descriptors in more depth. This post will talk about the BRIEF[1] descriptor and the following post will talk about ORB[2], BRISK[3] and FREAK[4].

As you may recall from the previous post, a binary descriptor is composed out of three parts:

- A sampling pattern: where to sample points in the region around the descriptor.
- Orientation compensation: some mechanism to measure the orientation of the keypoint and rotate it to compensate for rotation changes.
- Sampling pairs: which pairs to compare when building the final descriptor.

Recall that to build the binary string representing a region around a keypoint we need to go over all the pairs and for each pair (p1,p2) – if the intensity at point p1 is greater than the intensity at point p2, we write 1 in the binary string and 0 otherwise.

Presented in 2010[1], BRIEF was the first binary descriptor published. It does not have an elaborate sampling pattern or an orientation compensation mechanism, which makes it easier to understand, thus also a good choice for the first descriptor to explain about.

As we’ll see next, BRIEF takes only the information at single pixels location to build the descriptor, so to make him less sensitive to noise we first smooth it by a Gaussian filter.

Now, as we mentioned earlier, BRIEF does not have a sampling pattern thus pairs can be chosen at any point on the SxS patch. To build a BRIEF descriptor of length n, we need to determine n pairs (Xi,Yi). Denote by X and Y the vectors of point Xi and Yi, respectively.

In [1] the authors consider five methods to determine the vectors X and Y:

- X and Y are randomly uniformly sampled.
- X and Y are randomly sampled using a Gaussian distribution, meaning that locations that are closer to the center of the patch are preferred.
- X and Y are randomly sampled using a Gaussian distribution where first X is sampled with a standard deviation of 0.04*S^2 and then the Yi’s are sampled using a Gaussian distribution – Each Yi is sampled with mean Xi and standard deviation of 0.01 * S^2.
- X and Y are randomly sampled from discrete location of a coarse polar gird.
- For each i, Xi is (0, 0) and Yi takes all possible values on a coarse polar grid.

I hope the following figures, which illustrates examples of the five sampling strategies will help clear up the definitions:

The following figure presents recognition rates using all the five sampling strategies. We can see the recognition rates are about the same, expect for the fifth sampling strategy that shows worse performance:

As with all the binary descriptors, BRIEF’s distance measure is the number of different bits between two binary strings which can also be computed as the sum of the XOR operation between the strings.

The next post will talk about ORB[2] which extends BRIEF by introducing an orientation compensation mechanism and learns the sampling pairs instead of using a random choice.

Gil.

References:

[1] Calonder, Michael, et al. “Brief: Binary robust independent elementary features.” Computer Vision–ECCV 2010. Springer Berlin Heidelberg, 2010. 778-792.

[2] Rublee, Ethan, et al. “ORB: an efficient alternative to SIFT or SURF.” Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011.

[3] Leutenegger, Stefan, Margarita Chli, and Roland Y. Siegwart. “BRISK: Binary robust invariant scalable keypoints.” Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011.

[4] Alahi, Alexandre, Raphael Ortiz, and Pierre Vandergheynst. “Freak: Fast retina keypoint.” Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012.

Carlos CaetanoGreat work!!! Please keep on doing it! I work with binary descriptors too in my research at the graduation.

Pingback: A tutorial on binary descriptors – part 3 – The ORB descriptor | Gil's CV blog

UriExcellent article! Very informative and a great introduction to those who never heard of it. Keep it up!

Pingback: A tutorial on binary descriptors – part 4 – The BRISK descriptor | Gil's CV blog

Pingback: A tutorial on binary descriptors – part 5 – The FREAK descriptor | Gil's CV blog

Pingback: Adding rotation invariance to the BRIEF descriptor | Gil's CV blog

Chulian ZhangAssume we want to compare descriptor A in one picture against descriptor B from another picture. To calculate descriptor A, a sequence of sample pairs would be used (e.g. generated by Gaussian distribution); to calculate descriptor B, is it going to use the same sequence of pairs as A? Or another new sequence of sample pairs will be generated using Gaussian distribution?

Thanks in advance.

gillevicvPost authorHi,

The sequence of sampling pairs is chosen once for all the images that are compared.

Gil.

Divya VidyadharanVery interesting article. Much useful for me.

gillevicvPost authorThank you!

Gil

Pingback: Performance Evaluation of Binary Descriptor – Introducing the LATCH descriptor | Gil's CV blog

Matthew RobertsWhat keypoint detector does BRIEF use? Is it also FAST, like ORB?

Carlos CaetanoIn the BRIEF original paper, Calonder et al. used SURF keypoint detector.

intelloquadThanx a lot, you have given a very precise and easy to understand explanation 🙂

gillevicvPost authorThanks!

SanjayaNice Explanation…

Can you tell, how to choose the patch size(S) ? What is the value of S for best recognition ?

I could not find it in the original paper.

gillevicvPost authorHi,

In BRIEF they actually used the same patch size for all descriptors. In the OpenCV implementation it’s 48×48 pixels.

Best,

Gil

SanjayaThank You Gil Levi…..

Pingback: Feature Descriptors – Deep Learning KEYSCORE

JosanGreat explanation,

Is it mandatory to use the same sequence of sampling pairs for computing the descriptors in each image, if I want to match features from different images?

If that is the case, and I use ORB instead of BRIEF using opencv, how do I access that sequence, because I want to store the descriptors of a group of images in some file, a descriptor database, and have a program that only compute the descriptors of new images and compare then with the ones from that database. But I do not know how to make the ORB or BRIEF opencv’s function use the same sample pairs of the descriptors from the database.

Thanks

gillevicvPost authorThank you. In OpenCV, ORB uses a constant sequence of sampling pairs. It doesn’t change when you run it again or something like that. Same with BRIEF. You you don’t have to worry about that.

Best,

Gil

Sayan ChaudhuriHi Sir,

I actually did not get the sampling of points conception. Suppose we have S x S patch. So we have S^2 pixels in that patch. From there, do we have to select n pairs that are uniformly randomly sampled?? How to implement that in c++ or python??

gillevicvPost authorYes, uniformly sampled. You can use the implementation in OpenCV as reference.