Accelerating FAB-MAP With Concentration Inequalities

We outline an approach for using concentration inequalities to perform rapid approximate multi-hypothesis testing. In a scenario where multiple hypotheses are ranked according to a large set of features, our scheme improves the efficiency of selecting the best hypothesis by providing a "bail-out threshold" at which un-promising hypotheses can be excluded from further evaluation. We show how concentration inequalities can be used to derive principled bail-out thresholds, subject to a user-specified error tolerance. The technique is similar to the sequential probability ratio test, but is applicable in more general conditions. We apply the technique to improve the speed of the fast-appearance-based mapping system for appearance-based place recognition and mapping. The speed increase provided by the new approach is data dependent, but we demonstrate speed improvements of between 25x - 50x on real data, with only a slight degradation in accuracy.