Improving Binary Descriptors using Noncooperative Games

Improving Binary Descriptors using Noncooperative Games

Victor Fragoso Matthew Turk   Joao Hespanha


Recently, binary descriptors, e.g., BRIEF, BRISK, ORB, and others, have had a lot of attention as they require a low memory footprint and can be computed and matched quickly. Consequently, these descriptors are suitable for mobile devices and mobile applications that demand real-time and low memory footprint.

Computing an optimal set of pixel-pairs for binary descriptors.

One of the problems that these descriptors have is their capacity of capturing enough discriminative information from a patch, in contrast to other more sophisticated descriptors such as SIFT. This problem affects the performance of important applications, e.g., feature matching, visual tracking, and others.

In this project, we propose to compute an optimal set of pixel-pairs, which are utilized when the binary descriptor is constructed, to maximize the discriminative information that can be captured by these descriptors. We compute these pixel-pairs by means of a simultaneous zero-sum game.

The Game

Two players confront each other: the maximizer (P2) selects pixel-pairs whose intensity variation is high to construct discriminative binary descriptors. While the minimizer (P1) selects patch-pairs to confuse his opponent; we assume that P1 (the "nature" of the patches) is choosing his actions carefully to confuse P2. We are interested in the P2's policy as it indicates us which pixel-pairs are relevant to choose assuming that P1 is playing carefully and against us, i.e., P2's policy is a strategy to follow assuming the worse from his opponent. We solve the appropriate linear programs (see Prof. Hespanha notes on Noncooperative game theory notes for details on these LPs) and obtain P2's policy and we extract the pixel-pairs (see paper for details).


We compare our approach in combination with FERNS (GTFL-Ferns) and regular Ferns, which uses a uniform distribution to select pixel-pairs. We use the Oxford datasets Graf & Wall for a feature matching test with two different bit-lengths (450 & 256 bits).

Graf Dataset (Left): Our Approach performs similarly than Ferns. Wall Dataset (Right): Our approach presents an increase in the matching performance when keypoints present a similar texture.



V. Fragoso, M. Turk, J. Hespanha. Locating Binary Features for Keypoint Recognition using Noncooperative Games. In Proc. IEEE International Conference on Image Processing (ICIP 2012). Student Paper Award Finalist.