Motion Averaging

A Framework for Efficient and Accurate Large-Scale Camera Estimation in 3D Vision

Tutorial at CVPR 2018

Time and Location: 8:30am to 12:30pm on 18 June 2018 in Room 155-DEF

Venu Madhav Govindu
Department of Electrical Engineering
Indian Institute of Science
Bengaluru 560012 INDIA
venug[at]iisc.ac.in

This is a revised and updated version of a tutorial presented at CVPR 2017.
Slides for the 2017 version are available here.
Slides for the 2018 version are available here.
Videos of this tutorial are available : Part 1 and Part 2

Abstract

In recent years there has been growing interest in large-scale 3D reconstruction using both RGB and depth cameras. The concomitant need for accuracy, efficiency and scalability in camera motion estimation is addressed by the framework of motion averaging. Given many relative motion estimates between pairs of cameras, motion averaging solves for the 3D motions of individual cameras. The efficacy of motion averaging has attracted research interest leading to significant theoretical and algorithmic maturity. Owing to its major advantages over conventional approaches, motion averaging is now utilised in many 3D reconstruction pipelines. This tutorial will provide a comprehensive introduction to motion averaging in 3D vision. An intuitive and systematic understanding of the underlying geometry of matrix Lie groups will be developed. A comparative classification and summarization of various motion averaging methods will be presented. In addition, this tutorial will provide an exposition of algorithms and best practices. Along with developing a clear understanding of the state-of-the-art, this tutorial will aim to enable researchers to utilise motion averaging principles in novel contexts of large-scale structure-from-motion as well as dense 3D modeling using depth cameras.

Brief Biosketch of the Presenter

Venu Madhav Govindu obtained his Ph.D from the University of Maryland, College Park, USA. He is on the faculty of the Department of Electrical Engineering, Indian Institute of Science, Bengaluru, India. His primary research interests lie at the intersection of geometry and statistical estimation. The current interests of his research group include robust approaches to motion averaging, large-scale structure-from-motion problems, high quality shape reconstruction using depth cameras and the application of motion averaging in geometric SLAM. Details of his research group are available here.

Outline of Presentation

Topic Details Time
Introduction

Motivation, Problem statement, Application contexts

 1 hr 45 mins 
Theory and Formulation

Geometric properties and structure of matrix Lie groups, Group structure and properties of SO(2),SO(3),SE(3), Averaging on Lie groups
Intrinsic Methods

Averaging of relative motions, Theoretical issues, Distributed consensus methods (Weiszfeld algorithm etc.), Cost functions, Convexity issues, Hardness/difficulty of problems, Graph theory considerations
Break (30 mins) 
Robustness

M-estimators, IRLS, l-1 methods, RANSAC variants, Loop consensus statistics

 1 hr 
Extrinsic Methods

Rank-based methods, Matrix completion, Theoretical issues, Algorithmic considerations, Comparison with intrinsic methods
Rotation Averaging

Quaternion averaging, Intrinsic methods, Conjugate rotations, Applications in large-scale SfM
Translation Averaging

Problem statement, Parallel rigidity theory and existence of solution, Optimization of cost functions, Comparison of methods, Applications in large-scale SfM
Hierarchical SfM

Motion averaging and hierarchical representations of large-scale SfM datasets, Properties and advantages, Comparison with incremental bundle adjustment

 45 mins 
Euclidean Motion Averaging

Averaging of relative motions in SE(3), Theoretical considerations, differences wrt SO(3), application in large-scale SfM, multiview alignment of 3D scans
Conclusion

Relation with motion estimation in SLAM, graph SLAM etc., Open problems, Future directions

 

Relevant Publications of the Presenter

2001
[1]  Combining Two-view Constraints For Motion Estimation. (Venu Madhav Govindu), In CVPR, 2001.
2004
[2]Lie-Algebraic Averaging for Globally Consistent Motion Estimation (Venu Madhav Govindu), In CVPR, 2004.
2006
[3]Robustness in Motion Averaging (Venu Madhav Govindu), In Asian Conference on Computer Vision (ACCV), 2006.
2013
[4]Efficient and Robust Large-Scale Rotation Averaging (Avishek Chatterjee, Venu Madhav Govindu), In ICCV, 2013.
2014
[5]On Averaging Multiview Relations for 3D Scan Registration (Venu Madhav Govindu, A. Pooja), In IEEE Transactions on Image Processing, volume 23, 2014.
[6]Divide and conquer: Efficient large-scale structure from motion using graph partitioning (Brojeshwar Bhowmick, Suvam Patra, Avishek Chatterjee, Venu Madhav Govindu, Subhashis Banerjee), In Asian Conference on Computer Vision, 2014.
2016
[7]Motion Averaging in 3D Reconstruction Problems (Venu Madhav Govindu), Chapter in Riemannian Computing in Computer Vision (Pavan K. Turaga, Anuj Srivastava, eds.), Springer, 2016.
[8]Divide and conquer: A Hierarchical Approach to Large-scale Structure-from-Motion (Brojeshwar Bhowmick, Suvam Patra, Avishek Chatterjee, Venu Madhav Govindu, Subhashis Banerjee), In Computer Vision and Image Understanding (CVIU), 2016.
2017
[9]Robust Relative Rotation Averaging (Avishek Chatterjee, Venu Madhav Govindu), In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume , 2017.

Relevant Publications

Theory
1977
[1] Riemannian center of mass and mollifier smoothing (H. Karcher), In Communications on Pure and Applied Mathematics, volume 30, 1977.
1995
[2]Distance metrics on the rigid-body motions with applications to mechanism design (Frank C Park), In Journal of Mechanical Design, American Society of Mechanical Engineers, volume 117, 1995.
2004
[3]A globally convergent numerical algorithm for computing the centre of mass on compact Lie groups (Jonathan H. Manton), In International Conference on Control, Automation, Robotics and Vision, ICARCV 2004, 2004.
[4]Lie-Algebraic Averaging for Globally Consistent Motion Estimation (Venu Madhav Govindu), In CVPR, 2004.
2010
2013
[6]Rotation Averaging (Richard I. Hartley, Jochen Trumpf, Yuchao Dai, Hongdong Li), In International Journal of Computer Vision, volume 103, 2013.
2014
[7]Left-Invariant Riemannian Geodesics on Spatial Transformation Groups (E. Zacur, M. Bossa, S. Olmos), In SIAM Journal on Imaging Sciences, volume 7, 2014.
2017
[8]Robust Relative Rotation Averaging (Avishek Chatterjee, Venu Madhav Govindu), In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume , 2017.
Intrinsic Methods (including Rotation Averaging)
2004
[1] Lie-Algebraic Averaging for Globally Consistent Motion Estimation (Venu Madhav Govindu), In CVPR, 2004.
2006
[2]A new distributed time synchronization protocol for multihop wireless networks (Roberto Solis, Vivek S Borkar, PR Kumar), In Proceedings of the 45th IEEE Conference on Decision and Control, 2006.
2009
[3]Rotation averaging with application to camera-rig calibration (Yuchao Dai, Jochen Trumpf, Hongdong Li, Nick Barnes, Richard Hartley), In Asian Conference on Computer Vision, 2009.
2011
[4]L1 rotation averaging using the Weiszfeld algorithm. (Richard I. Hartley, Khurrum Aftab, Jochen Trumpf), In CVPR, 2011.
2012
[3]Simultaneous multiple rotation averaging using lagrangian duality (Johan Fredriksson, Carl Olsson), In Asian Conference on Computer Vision, 2012.
2013
[5]Efficient and Robust Large-Scale Rotation Averaging (Avishek Chatterjee, Venu Madhav Govindu), In IEEE International Conference on Computer Vision (ICCV), 2013.
2014
[6]Distributed 3-D localization of camera sensor networks from 2-D image measurements (Roberto Tron, René Vidal), In IEEE Transactions on Automatic Control, IEEE, volume 59, 2014.
2017
[7]Robust Relative Rotation Averaging (Avishek Chatterjee, Venu Madhav Govindu), In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume , 2017.
Extrinsic Methods
2001
[1] Combining Two-view Constraints For Motion Estimation. (Venu Madhav Govindu), In CVPR, 2001.
2007
[2]Robust rotation and translation estimation in multiview reconstruction (Daniel Martinec, Tomas Pajdla), In 2007 IEEE Conference on Computer Vision and Pattern Recognition, 2007.
2013
[4]Exact and stable recovery of rotations for robust synchronization (Lanhui Wang, Amit Singer), In Information and Inference, 2013.
2014
[5]Cramér--Rao bounds for synchronization of rotations (Nicolas Boumal, Amit Singer, P-A Absil, Vincent D Blondel), In Information and Inference, Oxford University Press, volume 3, 2014.
[6]Robust absolute rotation estimation via low-rank and sparse matrix decomposition (Federica Arrigoni, Luca Magri, Beatrice Rossi, Pasqualina Fragneto, Andrea Fusiello), In 2nd International Conference on 3D Vision, volume 1, 2014.
Robustness
2006
[1]Robustness in Motion Averaging (Venu Madhav Govindu), In Asian Conference on Computer Vision (ACCV), 2006.
2010
[2]Disambiguating visual relations using loop constraints. (Christopher Zach, Manfred Klopschitz, Marc Pollefeys), In CVPR, 2010.
2011
[3]Structure from motion for scenes with large duplicate structures (Richard Roberts, Sudipta N Sinha, Richard Szeliski, Drew Steedly), In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, 2011.
[4]L1 rotation averaging using the Weiszfeld algorithm. (Richard I. Hartley, Khurrum Aftab, Jochen Trumpf), In CVPR, 2011.
[5]Discrete-continuous optimization for large-scale structure from motion. (David J. Crandall, Andrew Owens, Noah Snavely, Dan Huttenlocher), In CVPR, 2011.
2013
[6]Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion (P. Moulon, P. Monasse, R. Marlet), In IEEE International Conference on Computer Vision (ICCV), 2013.
[7]Efficient and Robust Large-Scale Rotation Averaging (Avishek Chatterjee, Venu Madhav Govindu), In IEEE International Conference on Computer Vision (ICCV), 2013.
2014
[8]Global motion estimation from relative measurements in the presence of outliers (Guillaume Bourmaud, Rémi Mégret, Audrey Giremus, Yannick Berthoumieu), In Asian Conference on Computer Vision, 2014.
[9]Robust Global Translations with 1DSfM (Kyle Wilson, Noah Snavely), In European Conference on Computer Vision (ECCV), 2014.
2015
[10]Robust Rotation Synchronization via Low-rank and Sparse Matrix Decomposition (Federica Arrigoni, Andrea Fusiello, Beatrice Rossi, Pasqualina Fragneto), In arXiv preprint arXiv:1505.06079, 2015.
2016
[11] Robustness in view-graph SLAM (Tariq Abuhashim, Lorenzo Natale), In Information Fusion (FUSION), 2016 19th International Conference on, 2016.
Translation Averaging
2001
[1] Combining Two-view Constraints For Motion Estimation. (Venu Madhav Govindu), In CVPR, 2001.
2014
[2]Robust Global Translations with 1DSfM (Kyle Wilson, Noah Snavely), In European Conference on Computer Vision (ECCV), 2014.
2015
[3]Robust camera location estimation by convex programming (Onur Ozyesil, Amit Singer), In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2015.
[4]Linear Global Translation Estimation with Feature Tracks (Zhaopeng Cui, Nianjuan Jiang, Chengzhou Tang, Ping Tan), 2015.
[5]On Computing the Translations Norm in the Epipolar Graph (Federica Arrigoni, Andrea Fusiello, Beatrice Rossi), In 3D Vision (3DV), 2015 International Conference on, 2015.
2016
[6]ShapeFit and ShapeKick for Robust, Scalable Structure from Motion (Thomas Goldstein, Paul Hand, Choongbum Lee, Vladislav Voroninski, Stefano Soatto), In European Conference on Computer Vision, 2016.
Euclidean Motion Averaging
2004
[1] Lie-Algebraic Averaging for Globally Consistent Motion Estimation (Venu Madhav Govindu), In CVPR, 2004.
2011
[2]Multiview registration via graph diffusion of dual quaternions (Andrea Torsello, Emanuele Rodola, Andrea Albarelli), In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, 2011.
2014
[3]On Averaging Multiview Relations for 3D Scan Registration (Venu Madhav Govindu, A. Pooja), In IEEE Transactions on Image Processing, volume 23, 2014.
[4]Statistical Pose Averaging with Non-Isotropic and Incomplete Relative Measurements (Roberto Tron, Kostas Daniilidis), In European Conference on Computer Vision, 2014.
2015
[5]Global Structure-from-Motion by Similarity Averaging (Zhaopeng Cui, Ping Tan), 2015.
2016
[6]Camera motion from group synchronization (Federica Arrigoni, Andrea Fusiello, Beatrice Rossi), In 3D Vision (3DV), 2016 International Conference on, 2016.
[7]Global Registration of 3D Point Sets via LRS Decomposition (Federica Arrigoni, Beatrice Rossi, Andrea Fusiello), In European Conference on Computer Vision, 2016.
Hierarchical Methods
2014
[1] Divide and conquer: Efficient large-scale structure from motion using graph partitioning (Brojeshwar Bhowmick, Suvam Patra, Avishek Chatterjee, Venu Madhav Govindu, Subhashis Banerjee), In Asian Conference on Computer Vision, 2014.
2016
[2]Large Scale SfM with the Distributed Camera Model (Chris Sweeney, Victor Fragoso, Tobias Hollerer, Matthew Turk), In 3D Vision (3DV), 2016 International Conference on, 2016.
[3]Divide and conquer: A Hierarchical Approach to Large-scale Structure-from-Motion (Brojeshwar Bhowmick, Suvam Patra, Avishek Chatterjee, Venu Madhav Govindu, Subhashis Banerjee), In Computer Vision and Image Understanding (CVIU), 2016.

Other Related Papers (including SLAM)

2010
[1]Exploiting loops in the graph of trifocal tensors for calibrating a network of cameras (Jérôme Courchay, Arnak Dalalyan, Renaud Keriven, Peter Sturm), In European Conference on Computer Vision, 2010.
2011
[2]Closed-form solutions to multiple-view homography estimation (Pierre Schroeder, Adrien Bartoli, Pierre Georgel, Nassir Navab), In Applications of Computer Vision (WACV), 2011 IEEE Workshop on, 2011.
[3]g2o: A general framework for graph optimization (G Grisetti, H Strasdat, K Konolige, W Burgard), In IEEE International Conference on Robotics and Automation, 2011.
2013
[4]A global linear method for camera pose registration (Nianjuan Jiang, Zhaopeng Cui, Ping Tan), In Proceedings of the IEEE International Conference on Computer Vision, 2013.
[5]SfM with MRFs: Discrete-continuous optimization for large-scale structure from motion (David J Crandall, Andrew Owens, Noah Snavely, Daniel P Huttenlocher), In IEEE transactions on pattern analysis and machine intelligence, IEEE, volume 35, 2013.
[6]Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion (P. Moulon, P. Monasse, R. Marlet), In IEEE International Conference on Computer Vision (ICCV), 2013.
2014
[7]A fast and accurate approximation for planar pose graph optimization (Luca Carlone, Rosario Aragues, José A Castellanos, Basilio Bona), In The International Journal of Robotics Research, SAGE Publications, 2014.
2015
[8]Stable camera motion estimation using convex programming (Onur Ozyesil, Amit Singer, Ronen Basri), In SIAM Journal on Imaging Sciences, SIAM, volume 8, 2015.
[9]Lagrangian duality in 3D SLAM: Verification techniques and optimal solutions (Luca Carlone, David M Rosen, Giuseppe Calafiore, John J Leonard, Frank Dellaert), In Intelligent Robots and Systems (IROS), 2015 IEEE/RSJ International Conference on, 2015.
[10]Duality-based verification techniques for 2D SLAM (Luca Carlone, Frank Dellaert), In 2015 IEEE International Conference on Robotics and Automation (ICRA), 2015.
2016
[11]Lagrangian Duality in Complex Pose Graph Optimization (Giuseppe C Calafiore, Luca Carlone, Frank Dellaert), Chapter in Optimization and Its Applications in Control and Data Sciences, Springer, 2016.
[12]Past, Present, and Future of Simultaneous Localization And Mapping: Towards the Robust-Perception Age (Cesar Cadena, Luca Carlone, Henry Carrillo, Yasir Latif, Davide Scaramuzza, Jose Neira, Ian D Reid, John J Leonard), In arXiv preprint arXiv:1606.05830, 2016.
[13]Online Variational Bayesian Motion Averaging (Guillaume Bourmaud), In European Conference on Computer Vision, 2016.
[14] From Intrinsic Optimization to Iterated Extended Kalman Filtering on Lie Groups (Guillaume Bourmaud, Rémi Mégret, Audrey Giremus, Yannick Berthoumieu), In Journal of Mathematical Imaging and Vision, Springer, volume 55, 2016.