Abstract. Consensus maximization is one of the most widely used robust fitting paradigms in computer vision, and the development of algorithms for consensus maximization is an active research topic. In this
paper, we propose an efficient deterministic optimization algorithm for
consensus maximization. Given an initial solution, our method conducts
a deterministic search that forcibly increases the consensus of the initial
solution. We show how each iteration of the update can be formulated
as an instance of biconvex programming, which we solve efficiently using
a novel biconvex optimization algorithm. In contrast to our algorithm,
previous consensus improvement techniques rely on random sampling or
relaxations of the objective function, which reduce their ability to signifi-
cantly improve the initial consensus. In fact, on challenging instances, the
previous techniques may even return a worse off solution. Comprehensive experiments show that our algorithm can consistently and greatly
improve the quality of the initial solution, without substantial cost