A tutorial on binary descriptors – part 2 – The BRIEF descriptor

23 Replies

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:

  1. A sampling pattern: where to sample points in the region around the descriptor.
  2. Orientation compensation: some mechanism to measure the orientation of the keypoint and rotate it to compensate for rotation changes.
  3. 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:

  1. X and Y are randomly uniformly sampled.
  2. X and Y are randomly sampled using a Gaussian distribution, meaning that locations that are closer to the center of the patch are preferred.
  3. 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.
  4. X and Y are randomly sampled from discrete location of a coarse polar gird.
  5. 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:

BRIEF - illustration of the five sampling pattern

BRIEF – illustration of the five sampling pattern

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:

BRIEF descriptor - performance of the five sampling patterns

BRIEF descriptor – performance of the five sampling patterns

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.‏

23 thoughts on “A tutorial on binary descriptors – part 2 – The BRIEF descriptor”

  1. Carlos Caetano

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

    Reply ↓

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

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

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

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

  7. Chulian Zhang

    Assume 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.

    Reply ↓

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

  12. Sanjaya

    Nice 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.

    Reply ↓
    1. gillevicv Post author

      Hi,

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

      Best,
      Gil

      Reply ↓

  13. Pingback: Feature Descriptors – Deep Learning KEYSCORE

  14. Josan

    Great 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

    Reply ↓
    1. gillevicv Post author

      Thank 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

      Reply ↓
  15. Sayan Chaudhuri

    Hi 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??

    Reply ↓

Leave a comment