Guaranteed Outlier Removal With Mixed Integer Linear Programs
The maximum consensus problem is fundamentally important to robust geometric fitting in computer vision. Solving the problem exactly is computationally demanding, and the effort required increases rapidly with the problem size. Although randomized algorithms are much more efficient, the optimality of the solution is not guaranteed. Towards the goal of solving maximum consensus exactly, we present guaranteed outlier removal as a technique to reduce the runtime of exact algorithms. Specifically, before conducting global optimization, we attempt to remove data that are provably true outliers, i.e., those that do not exist in the maximum consensus set. We propose an algorithm based on mixed integer linear programming to perform the removal. The result of our algorithm is a smaller data instance that admits much faster solution by a subsequent exact algorithm, while yielding the same globally optimal result as the original problem. We demonstrate that overall speedups of up to 80% can be achieved on common vision problems.
Code (0)
등록된 구현이 없습니다.
Tasks
global-optimizationSimilar Papers 제목 키워드 기반
Outlier-immune Data-driven Linear Power Flow Model Construction via Mixed-Integer Programming
The common approaches to construct a data-driven linear power flow (DD-LPF) model cannot completely eliminate the adverse impacts of outliers in a training dataset. In this letter, a novel outlier-immune DD-LPF model con…
GLIMPS: A Greedy Mixed Integer Approach for Super Robust Matched Subspace Detection
Due to diverse nature of data acquisition and modern applications, many contemporary problems involve high dimensional datum $\x \in \R^\d$ whose entries often lie in a union of subspaces and the goal is to find out whic…
Guaranteed Outlier Removal for Point Cloud Registration with Correspondences
An established approach for 3D point cloud registration is to estimate the registration function from 3D keypoint correspondences. Typically, a robust technique is required to conduct the estimation, since there are fals…
Point Cloud RegistrationSize Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization
Plain vanilla K-means clustering has proven to be successful in practice, yet it suffers from outlier sensitivity and may produce highly unbalanced clusters. To mitigate both shortcomings, we formulate a joint outlier de…
ClusteringConstrained ClusteringOutlier DetectionFuzzy Mixed Integer Linear Programming for Air Vehicles Operations Optimization
Multiple Air Vehicles (AVs) to prosecute geographically dispersed targets is an important optimization problem. Associated multiple tasks viz., target classification, attack and verification are successively performed on…
Scheduling