Reduced Epipolar Cost for Accelerated Incremental SfM

Abstract

We propose a reduced algebraic cost based on pairwise epipolar constraints for the iterative refinement of a multiple view 3D reconstruction. The aim is to accelerate the intermediate steps required when incrementally building a reconstruction from scratch.
Though the proposed error function is algebraic, careful input data normalization makes it a good approximation to the true geometric epipolar distance. Its minimization is significantly faster and obtains a geometric reprojection error very close to the optimum value, requiring very few iterations of final standard BA refinement.
Smart usage of a reduced measurement matrix for each pair of views allows elimination of the variables corresponding to the 3D points prior to the nonlinear optimization process, subsequently reducing computation, memory usage, and considerably accelerating convergence.
This approach has been tested in a wide range of real and synthetic problems, consistently obtaining significant robustness and convergence improvements even when starting from rough initial solutions. Its efficiency and scalability make it thus an ideal choice for incremental SfM techniques in real-time tracking applications or scene modeling from large Internet image databases.

Authors

A. L. Rodriguez
alrl1@um.es
DITEC, Universidad de Murcia

P E. Lopez-de-Teruel
pedroe@um.es
DITEC, Universidad de Murcia

A. Ruiz
aruiz@um.es
DIS, Universidad de Murcia

Publications

Preventing the influence of mismatchings in reduced structure-less cost optimization. To appear in first International Workshop on Multi VIew Geometry in RObotics. In Proc. of RSS 2013. Paper

Algebraic epipolar constraints for efficient structureless multiview motion estimation. PhD thesis. Universidad de Murcia, Spain. May 2013. Download.

GEA Optimization for Live Structureless Motion Estimation. First International Workshop on Live Dense Reconstruction from Moving Cameras. In Proc. of ICCV 2011. Extended abstract.

Reduced epipolar cost for accelerated incremental SfM. In Proc. of CVPR 2011. Paper.

Test data

Data-sets referenced in the workshop MVIGRO: medusa (19 views), and desktoplong (100 views). They contain the input images, the matchings (matchings.txt) and 3D reconstruction (output.nvm) obtained with VisualSfM.
Data-sets referenced from the paper Bundle Adjustment in the large: these data-sets were obtained from large sets of pictures capturing the same scene. These data-sets are: dubrovnik, trafalgar, venice and lady-bug. They can be found here.
Data-sets in laSBA example application format. The following data-sets are well known and can be also obtained from different sources at the Internet: maquette, dinosaur and corridor

The following data-sets were obtained using a SfM tracking application capable of detecting loop-closings. These reconstructions feature moderate and large dead-reckoning errors, so you can use them to test GEA and sSBA loop-closing correction capacity: boxes-8 (original video is boxes-8.avi), boxes-xl (original video is boxes-xl.avi) and desktop-long (original video is desktop-long.avi)

Software

A new C++ GEA implementation is available in the QVision library, which offers the robustification and optimizations described in the paper published at the MVIGRO workshop. A test example application is also included. It can be used to compare the reprojection error, performance time and the reconstruction obtained with GEA, using the algorithm proposed at the LDRMC workshop.

If you have the ROS framework installed, and the QVision configured to link against it, you can also compare results and performance obtained with GEA and sSBA. You can find more information of the QVision functionality for GEA at the API documentation, and information about the test application here.

An alternative GEA implementation for Haskell is included in the set of computer vision packages easyVision. You can find it at the directory projects/gea inside the source code.

Acknowledgements

Part of this work was supported by the Spanish MEC and MICINN, as well as European Commission FEDER funds, under Grants CSD2006-00046 and TIN2009-14475-C04.