Practical globally optimal consensus maximization by Branch-and-bound based on interval arithmetic

摘要

Consensus maximization is widely used in robust model fitting, and it is usually solved by RANSAC-type methods in practice. However, these methods cannot guarantee global optimality and sometimes return the wrong solutions. A series of Branch-and-bound (BnB) based globally optimal methods have been proposed, most of which involve deriving a complex bound. Interval arithmetic was utilized to derive simple bounds for BnB in solving geometric matching problems in 2003. However, this idea was somewhat forgotten in the community because it seems natural that the simple interval arithmetic based bounds might be worse than those elaborate bounds. Recently, some new globally optimal algorithms without using BnB were developed for consensus maximization, but they can only work with a small number of data points and low outlier ratios. In this work, we draw the idea of simple bounds by interval arithmetic back on the map and demonstrate its practicability by making substantial extensions. Concretely, we give detailed derivation of solving robust model fitting problems with both linear and quasi-convex residuals and propose practical methods to use them under Unit-Norm constraint and in a high-dimensional problem. Extensive experiments show that the proposed method can handle practical problems with large number of data points and high outlier ratios. It outperforms state-of-the-art global, RANSAC-type, and deterministic methods in terms of both accuracy and efficiency in low-dimensional problems. The source code is publicly available. 2