The estimation of the epipolar geometry is especially difficult when the putative correspondences include a low percentage of inlier correspondences and/or a large subset of the inliers is consistent with a degenerate configuration of the epipolar geometry that is totally incorrect. This work presents the Balanced Exploration and Exploitation Model Search (BEEM) algorithm that works very well especially for these difficult scenes. The algorithm handles these two problems in a unified manner. It includes the following main features: (1) Balanced use of three search techniques: global random exploration, local exploration near the current best solution and local exploitation to improve the quality of the model. (2) Exploits available prior information to accelerate the search process. (3) Uses the best found model to guide the search process, escape from degenerate models and to define an efficient stopping criterion. (4) Presents a simple and efficient method to estimate the epipolar geometry from two SIFT correspondences. (5) Uses the locality-sensitive hashing (LSH) approximate nearest neighbor algorithm for fast putative correspondences generation. The resulting algorithm when tested on real images with or without degenerate configurations gives quality estimations and achieves significant speedups compared to the state of the art algorithms.

The problem of automatic robust estimation of the epipolar geometry in cases where the correspondences are contaminated with a high percentage of outliers is addressed. This situation often occurs when the images have undergone a significant deformation, either due to large rotation or wide baseline of the cameras. An accelerated algorithm for the identification of the false matches between the views is presented. The algorithm generates a set of weak motion models (WMMs). Each WMM roughly approximates the motion of correspondences from one image to the other. The algorithm represents the distribution of the median of the geometric distances of a correspondence to the WMMs as a mixture model of outlier correspondences and inlier correspondences. The algorithm generates an outlier correspondence sample from the data. This sample is used to estimate the outlier rate and to estimate the outlier pdf. Using these two pdfs the probability that each correspondence is an inlier is estimated. These probabilities enable to guide the sampling. In the RANSAC process this guided sampling accelerates the search process. The resulting algorithm when tested on real images achieves a speedup of between one or two orders of magnitude.

The introduction of the joint image manifold allows to treat the problem of recovering camera motion and epipolar geometry as the problem of fitting a manifold to the data measured in a stereo pair. The manifold has a singularity and boundary, therefore care must be taken when fitting it. This paper reviews the notion of joint image manifold, and how previous motion recovery methods can be viewed in its context, and then offers a new fitting method, which improves upon previous results, especially when the extent of the data and/or the motion are small.