MARDI 6 FEVRIER 2007, 16h, Salle Henri Cartan Balanced Exploration and Exploitation Model (BEEM) Search for Efficient Epipolar Geometry Estimation Ilan Shimshoni (ishimshoni@mis.haifa.ac.il) Management Information Systems Dept., University of Haifa, Israel Abstract: Several years ago I worked on the problem of visual navigation of robots. The basic algorithm which has to be solved there is to estimate the Epipolar geometry from two wide-baseline images. This drew my attention to this problem and in the following years my students and I tackled this problem from several aspects. Our works addressed the following problems. We developed an accurate algorithm for epipolar geometry estimation which is theoretically more accurate than the "geometric" distance algorithm. In another work we dealt with the problem of matching outdoor images which were taken at different times of the day. We combine feature matching with matching of segmentation results. Together very accurate matching results are achieved. In the first part of the talk I will give short descriptions of these works. In the second part, I will describe in detail our "Balanced Exploration and Exploitation Model Search (BEEM)" algorithm. This algorithm can deal with the difficult cases 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. Degenerate configurations occur when most of the correspondences lie on a planar surface or a concentrated in a small part of the image. The algorithm borrows concepts from general optimization techniques and applies them to the RANSAC framework. These concepts are: global random exploration, local random search near the current best solution and local optimization to improve the quality of the model. Each of these three operations are applied according to the estimated quality of the current solution. The algorithm exploits available prior information to accelerate the search process. One of the most important components of the algorithm is its global exploration step. We present a method for estimating the fundamental matrix from only two pairs of SIFT matches. We exploit the local structure to generate four matches from each match. This method reduces the complexity of the RANSAC step immensely. The resulting estimation of the fundamental matrix is however not very accurate, but with the local optimization and local exploration steps of the BEEM algorithm, a high quality estimation is achieved. 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!