Practical globally optimal consensus maximization by Branch-and-bound based on interval arithmetic. (July 2021)

• Record Type: Journal Article
• Authors: Wang, Yiru; Liu, Yinlong; Li, Xuechen; Wang, Chen; Wang, Manning; Song, Zhijian
• Is Part Of: Pattern recognition. Volume 115(2021)
• Publication Date: 2021-07
• Subjects: Consensus maximization -- Globally optimization -- Robust model fitting -- Branch-and-bound -- Interval arithmetic; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2021.107897
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: We achieve globally optimal consensus maximization by Branch-and-Bound framework and draw the idea of interval arithmetic-based bound calculation back on the map. We provide the detailed derivation of interval arithmetic-based bound calculation for consensus maximization problems with both linear and quasi-convex residuals. Extensive experiments show that the proposed method can better deal with larger number of data points and higher outlier ratios than existing global methods. Abstract: 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