Efficient Globally Optimal Consensus Maximisation With Tree Search
Maximum consensus is one of the most popular criteria for robust estimation in computer vision. Despite its widespread use, optimising the criterion is still customarily done by randomised sample-and-test techniques, which do not guarantee optimality of the result. Several globally optimal algorithms exist, but they are too slow to challenge the dominance of randomised methods. We aim to change this state of affairs by proposing a very efficient algorithm for global maximisation of consensus. Under the framework of LP-type methods, we show how consensus maximisation for a wide variety of vision tasks can be posed as a tree search problem. This insight leads to a novel algorithm based on A* search. We propose efficient heuristic and support set updating routines that enable A* search to rapidly find globally optimal results. On common estimation problems, our algorithm is several orders of magnitude faster than previous exact methods. Our work identifies a promising solution for globally optimal consensus maximisation.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Globally Optimal Contrast Maximisation for Event-based Motion Estimation
Contrast maximisation estimates the motion captured in an event stream by maximising the sharpness of the motion compensated event image. To carry out contrast maximisation, many previous works employ iterative optimisat…
Event-based Motion EstimationMotion EstimationConsensus Maximization Tree Search Revisited
Consensus maximization is widely used for robust fitting in computer vision. However, solving it exactly, i.e., finding the globally optimal solution, is intractable. A* tree search, which has been shown to be fixed-para…
Robust Fitting in Computer Vision: Easy or Hard?
Robust model fitting plays a vital role in computer vision, and research into algorithms for robust fitting continues to be active. Arguably the most popular paradigm for robust fitting in computer vision is consensus ma…
Consensus Maximisation Using Influences of Monotone Boolean Functions
Consensus maximisation (MaxCon), which is widely used for robust fitting in computer vision, aims to find the largest subset of data that fits the model within some tolerance level. In this paper, we outline the connecti…
Globally-Optimal Inlier Set Maximisation for Simultaneous Camera Pose and Feature Correspondence
Estimating the 6-DoF pose of a camera from a single image relative to a pre-computed 3D point-set is an important task for many computer vision applications. Perspective-n-Point (PnP) solvers are routinely used for camer…
Camera Pose EstimationPose Estimation