TY - GEN
T1 - Consensus set maximization with guaranteed global optimality for robust geometry estimation
AU - Li, Hongdong
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77953184592&partnerID=8YFLogxK
U2 - 10.1109/ICCV.2009.5459398
DO - 10.1109/ICCV.2009.5459398
M3 - Conference contribution
SN - 9781424444205
T3 - Proceedings of the IEEE International Conference on Computer Vision
SP - 1074
EP - 1080
BT - 2009 IEEE 12th International Conference on Computer Vision, ICCV 2009
T2 - 12th International Conference on Computer Vision, ICCV 2009
Y2 - 29 September 2009 through 2 October 2009
ER -