4.8 Article

Deterministic Approximate Methods for Maximum Consensus Robust Fitting

出版社

IEEE COMPUTER SOC
DOI: 10.1109/TPAMI.2019.2939307

关键词

Approximation algorithms; Optimization; Computer vision; Mathematical model; Estimation; Computational modeling; Data models; Maximum consensus; robust fitting; deterministic algorithm; approximate algorithm

资金

  1. [DP160103490]
  2. [FT170100072]
  3. [CE140100016]
  4. Australian Research Council [CE140100016] Funding Source: Australian Research Council

向作者/读者索取更多资源

Maximum consensus estimation is crucial in robust fitting problems in computer vision. Existing algorithms either provide rough approximate solutions cheaply or exact solutions at a high cost. This paper proposes deterministic algorithms to approximately optimize the maximum consensus criterion, filling the gap between the two extremes. The algorithms, based on convex subproblem solving, greatly improve rough initial estimates and are practical for realistic input sizes.
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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.8
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据