Abstract. Many computer vision methods use consensus maximization to relate measurements containing outliers with the correct transformation model. In
the context of rigid shapes, this is typically done using Random Sampling and
Consensus (RANSAC) by estimating an analytical model that agrees with the
largest number of measurements (inliers). However, small parameter models may
not be always available. In this paper, we formulate the model-free consensus
maximization as an Integer Program in a graph using ‘rules’ on measurements.
We then provide a method to solve it optimally using the Branch and Bound
(BnB) paradigm. We focus its application on non-rigid shapes, where we apply
the method to remove outlier 3D correspondences and achieve performance superior to the state of the art. Our method works with outlier ratio as high as 80%. We
further derive a similar formulation for 3D template to image matching, achieving
similar or better performance compared to the state of the art.