Ëàáîðàòîðèÿ êîìïüþòåðíîé ãðàôèêè è ìóëüòèìåäèà

Introduction

One of the key tasks in the field of computer vision is to establish a relation between information extracted from images and some mathematical parametric model. The problem is complicated due to the presence of noise and ouliers, which are the part of the data that has not been generated by estimated model. The estimation method is called robust if it can give accurate results in presence of noise and outliers.

RANdom SAmpling Consensus

Several methods were proposed to deal with presence of outliers – M-Estimators, voting schemes like Hough transform, Least Median of Squares, or a family of methods based on RANdom SAmpling Consensus estimator (RANSAC).
RANSAC-based methods turned out to be the most convenient tool for such problems as multiple-view relation estimation and camera calibration. This boosted the research in this area and a lot of modifications were introduced. First, the focus was on precision and robustness (e.g. MSAC, MLESAC), than it turned to speed enhancement (LO-MSAC, Preemptive-RANSAC).

One of the main drawbacks of previously mentioned methods is relying on parameters estimated elsewhere - outlier threshold or predefined noise variation and inlier share (except for MLESAC that estimates inlier share. In some cases, e.g. multiple-view relation estimation, these parameters can be known in advance. But in such tasks as sequential camera pose estimation for image sequences, the noise is accumulated and its value is unknown. In this case, general RANSAC-based methods can fail.

AMLESAC

For accurate robust estimation of model parameters we propose a novel algorithm called AMLESAC. It is based on general random sampling consensus framework but introduces maximum likelihood estimation of hypothesis with simultaneous noise parameters estimation. Our method also exploits local optimization and subset selection to increase precision and speed of estimation.

Experiments

The AMLESAC was tested on a number of synthetic tests such as line fitting, multiple view relation estimation and camera calibration. It has been shown to provide equal or superior results compared to other methods. The most impressive results were demonstrated when applied to sequential camera pose estimation on real data. The noise is accumulated during camera calibration and from certain frame general methods like MSAC fails to correctly estimate the pose of the camera, which results in severe degradation of estimated camera trajectory. AMLESAC successfully measures the noise parameters and reliable estimate camera pose when MSAC fails.

The example of MSAC and AMLESAC performance for sequential pose estimation is shown below:

 
Camera tracking with different robust estimators used for pose estimation.
Left - pose estimation by MSAC, right - pose estimation by AMLESAC

Results

When applied to camera tracking tasks AMLESAC outperforms other RANSAC-based estimators. Because of that AMLESAC is widely used in our Image-based modeling project.

A large collection of papers on parameter-estimation methods is collected in corresponding section of our library.

Publications

Anton Konouchine, Victor Gaganov, Vladimir Vezhnevets "AMLESAC: A New Maximum Likelihood Robust Estimator". Graphicon-2005, Novosibirsk,Akademgorodok, 2005. .pdf(419kb)

Anton Konouchine, Kirill Marinichev, Vladimir Vezhnevets "A survey of robust parameter estimation methods based on random sampling." Graphicon-2004, Moscow, Moscow State University, Russia, 2004 .pdf (240kb) (in Russian)

The project team

• Dr. Anton Konushin
• Viktor Gaganov
• Kirill Marinichev
• Dr. Vladimir Vezhnevets

Contacts

Dr. Anton Konouchine
ktosh@graphics.cs.msu.ru