Deterministic approximate methods for maximum consensus robust fitting

Document Type

Journal Article

Publication Title

IEEE Transactions on Pattern Analysis and Machine Intelligence

Volume

43

Issue

3

First Page

842

Last Page

857

Publisher

IEEE

School

School of Science

RAS ID

30758

Funders

ARC Discovery Project ARC Future Fellowships ARC Centres of Excellence

Grant Number

ARC Number : DP160103490, FT170100072, CE140100016

Grant Link

http://purl.org/au-research/grants/arc/DP160103490 http://purl.org/au-research/grants/arc/FT170100072 http://purl.org/au-research/grants/arc/CE140100016

Comments

Le, H. M., Chin, T. J., Eriksson, A., Do, T. T., & Suter, D. (2021). Deterministic approximate methods for maximum consensus robust fitting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(3), 842-857. https://doi.org/10.1109/TPAMI.2019.2939307

Abstract

© 1979-2012 IEEE. Maximum consensus estimation plays a critically important role in several robust fitting problems in computer vision. Currently, the most prevalent algorithms for consensus maximization draw from the class of randomized hypothesize-and-verify algorithms, which are cheap but can usually deliver only rough approximate solutions. On the other extreme, there are exact algorithms which are exhaustive search in nature and can be costly for practical-sized inputs. This paper fills the gap between the two extremes by proposing deterministic algorithms to approximately optimize the maximum consensus criterion. Our work begins by reformulating consensus maximization with linear complementarity constraints. Then, we develop two novel algorithms: one based on non-smooth penalty method with a Frank-Wolfe style optimization scheme, the other based on the Alternating Direction Method of Multipliers (ADMM). Both algorithms solve convex subproblems to efficiently perform the optimization. We demonstrate the capability of our algorithms to greatly improve a rough initial estimate, such as those obtained using least squares or a randomized algorithm. Compared to the exact algorithms, our approach is much more practical on realistic input sizes. Further, our approach is naturally applicable to estimation problems with geometric residuals. Matlab code and demo program for our methods can be downloaded from https://goo.gl/FQcxpi.

DOI

10.1109/TPAMI.2019.2939307

Access Rights

subscription content

Link to Full Text

Share

 
COinS