D-Brief: Efficient Discriminative Projections for Compact Binary Descriptors

D-Brief is a binary local feature descriptor which relies on discriminative projections trained to be computed efficiently from a small set of simple filters (e.g. box filters. With only 32 bits per descriptor, D-Brief outperforms the state-of-the-art binary descriptors in terms of both accuracy and efficiency, while being over an order of magnitude shorter.

How do we build our descriptor? We first train a set of discriminative projections using Linear Discriminant Analysis and then we approximate the projections as a linear combination of a few elements from a predefined dictionary D of simple elements (e.g. box filters) using sparsity constraints. See the paper for details.

Example approximation:

Results

Accuracy. Comparing D-Brief with the state-of-the-art binary descriptors on standard Liberty and Notre Dame datasets. The plots show the ROC curves for binary descriptors D-Brief, BRIEF, ORB and BRISK. We also show the results for floating point and much more complex to compute SIFT and SURF. In parentheses: Number of floating point (f) or binary (b) coordinates per descriptor. D-Brief outperforms its binary competitors while being almost order of magnitude shorter.

Speed. Description and matching timings per descriptor for SIFT, SURF, BRISK, BRIEF, ORB and D-Brief with box filters used to approximate discriminative projections. Results computed for 3000 descriptors extracted from the wall1.ppm image of Mikolajczyk dataset and averaged over 300 runs on a MacBook Pro with an Intel i7 2.66 GHz CPU and with a POPCNT instruction enabled.

Software

Note on Efficient Distance Computations. Computing the Hamming distance between two binary vectors corresponds to a simple bitcount on the result of a binary XOR operation between the vectors. The bitcount becomes particularly efficient on CPUs supporting the POPCNT instruction: The first in this series are Intel’s Bloomfield (SSE 4.2) and AMD’s Phenom (SSE 4a). If your CPU supports this instruction, you can safely; enable -msse4.2 (or -msse4a, respectively) in test_app/Makefile. This should give you a 10- to 15-fold speed increase for matching. If enabled despite SSE 4.2 (SSE 4a, respectively) is not supported, you will get an Illegal instruction. On linux, try grep sse /proc/cpuinfo and look for sse4_2 (or sse4a, respectively) to find out whether or not POPCNT is available on your machine.

Download: DBrief demo (C/C++), Train-and-test code with sample data (Matlab)
License: GPL v2
Dependency: OpenCV v2.0 or higher

References

T. Trzcinski; V. Lepetit : Efficient Discriminative Projections for Compact Binary Descriptors. 2012. European Conference on Computer Vision, Florence, Italy, 2012.