Consensus set maximization with guaranteed global optimality for robust geometry estimation

Hongdong LiICCV 2009 · OpenReview

Abstract

Finding the largest consensus set is one of the key ideas used by the original RANSAC for removing outliers in robust-estimation. However, because of its random and non-deterministic nature, RANSAC does not fulfill the goal of consensus set maximization exactly and optimally. Based on global optimization, this paper presents a new algorithm that solves the problem exactly. We reformulate the problem as a mixed integer programming (MIP), and solve it via a tailored branch-and-bound method, where the bounds are computed from the MIP's convex under-estimators. By exploiting the special structure of linear robust-estimation, the new algorithm is also made efficient from a computational point of view.
BibTeX
@inproceedings{li2009consensus,
  author = {Hongdong Li},
  title = {{Consensus set maximization with guaranteed global optimality for robust geometry estimation}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2009},
  url = {https://openreview.net/forum?id=SyVOKWMuWS},
}

Loading related content...

Figure