Optimisation in Multiple View Geometry:
The L-infinity Way

 

Speakers

Tat-Jun Chin
Associate Professor
The University of Adelaide
Anders Eriksson
ARC Future Fellow
Queensland University of Technology
Fredrik Kahl
Professor
Chalmers University of Technology

 

Course description

 

Stemming from its roots in photogrammetry, the theory and practice of multiple view geometry has traditionally focussed on L2 minimisation, i.e., minimising sum of squared errors. However, due to the projective nature of the imaging process, many of the optimisation problems associated with L2 minimisation (e.g., bundle adjustment) involve objective functions that are plagued by multiple local minima [1]. This prevents algorithms that are tractable (i.e., able to efficiently and verifiably find the globally optimal solution), and necessitates careful preprocessing and/or initialisation to ensure success.

 

The situation changes dramatically, however, if we perform L-infinity minimisation. Pioneered by Hartley and Kahl in the mid-2000’s for multiple view geometry [2][3], it can be shown that many geometric problems (e.g., triangulation, homography estimation) are amenable to tractable solutions if we minimise the largest error. Since then, there has been significant progress in the “L-infinity way”, encompassing aspects such as robust estimation [4][5][6], large-scale optimisation [7][8], and guaranteed approximations [9]---most of which can be performed better due to the fundamental advantages of L-infinity minimisation. The intimate connection between L-infinity minimisation and quasiconvex programming [10] also enables theory and methods from the discrete geometry literature to be leveraged for computer vision.

 

This tutorial aims to give an in-depth introduction of L-infinity optimisation in geometric vision. We emphasise on the basic mathematical and algorithmic concepts, so as to convey deeper understanding and appreciation of the approach. We also survey important recent advances in the area, which contribute towards making the L-infinity way a bona fide alternative to current methods for geometric vision. It is hoped that the tutorial will inspire more researchers to incorporate L-infinity methods into their applications.

 

Detailed topics and schedule

 

 

TimeTopicSlidesPresenter
1330-1340 Arrival and welcome PDF Chin
1340-1430
  • Introduction: why L-infinity minimisation?
  • Convexity, pseudoconvexity, and quasiconvexity
  • Identifying solvable problems
  • Globally optimal algorithms for L-infinity minimisation
    • Bisection [3], Dinkelbach's method [11], Gugat's method [12]
    • Gradient descent [11,17], interior point method [13], polyhedron collapse [14]
PDF Kahl
1430-1520
  • Quasiconvex programming, LP-type methods
    • Basis, combinatorial dimension, support set, basis updating [10]
    • Approximate algorithms for L-infinity minimisation [9]
  • Robust estimation
    • Computational hardness (NP-hardness, fixed parameter tractability) [15]
    • Exact algorithms (enumeration [5], tree search [6])
    • Approximate algorithms (recursive outlier removal [4,22], Monte Carlo search [16], Frank-Wolfe method [20])
PDF Chin
1520-1600 Coffee break
1600-1650
  • Large-scale optimisation
    • Resection-intersection method [17]
    • Pseudo-convex proximal splitting [7] and consensus methods [8]
  • L-infinity pipeline for structure-from-motion
    • Globally optimal rotation averaging [19]
  • Applications
    • Large-scale 3D reconstruction
    • Simultaneous localisation and mapping
PDF Eriksson

 

References

 

  1. R. Hartley, F. Kahl: Optimal Algorithms in Multiview Geometry. ACCV 2007.
  2. R. Hartley, F. Schaffalitzky: L-infinity Minimization in Geometric Reconstruction Problems. CVPR 2004.
  3. F. Kahl: Multiple View Geometry and the L-infinity-norm. ICCV 2005.
  4. K. Sim, R. Hartley: Removing Outliers Using The L-infty Norm. CVPR 2006.
  5. O. Enqvist, E. Ask, F. Kahl, K. Åström: Tractable Algorithms for Robust Model Estimation. IJCV 112(1): 115-129 (2015).
  6. T.-J. Chin, P. Purkait, A. Eriksson, D. Suter: Efficient globally optimal consensus maximisation with tree search. CVPR 2015.
  7. A. Eriksson, M. Isaksson: Pseudoconvex Proximal Splitting for L-infinity Problems in Multiview Geometry. CVPR 2014.
  8. A. Eriksson, J. Bastian, T.-J. Chin, M. Isaksson: A Consensus-Based Framework for Distributed Bundle Adjustment. CVPR 2016.
  9. Q. Zhang, T.-J. Chin: Coresets for Triangulation. TPAMI 2017.
  10. D. Eppstein: Quasiconvex Programming. CoRR abs/cs/0412046 (2004).
  11. C. Olsson, A. Eriksson, F. Kahl: Efficient Optimization for L-problems using Pseudoconvexity. ICCV 2007.
  12. S. Agarwal, N. Snavely, S. M. Seitz: Fast Algorithms for L-infinity Problems in Multiview Geometry. CVPR 2008.
  13. Z. Dai, Y. Wu, F. Zhang, and H. Wang: A Novel Fast Method for L-infinity Problems in Multiview Geometry. ECCV 2012.
  14. S Donné, B Goossens, W Philips. Point Triangulation Through Polyhedron Collapse Using the l-infinity Norm. ICCV 2015.
  15. T.-J. Chin, D. Suter: The Maximum Consensus Problem: Recent Algorithmic Advances. Synthesis Lectures on Computer Vision, Morgan & Claypool Publishers 2017.
  16. H. Le, T.-J. Chin, D. Suter: RATSAC - Random Tree Sampling for Maximum Consensus Estimation. DICTA 2017.
  17. Q. Zhang, T.-J. Chin, H. Le: A Fast Resection-Intersection Method for the Known Rotation Problem. CVPR 2018.
  18. D. Martinec, T. Pajdla: Robust Rotation and Translation Estimation in Multiview Reconstruction. CVPR 2007.
  19. A. Eriksson, C. Olsson, F. Kahl, T.-J. Chin: Rotation Averaging and Strong Duality. CVPR 2018.
  20. H. Le, T.-J. Chin, D. Suter: An Exact Penalty Method for Locally Convergent Maximum Consensus. CVPR 2017.
  21. Q. Zhang, T.-J. Chin and D. Suter: Quasiconvex Plane Sweep for Triangulation with Outliers. ICCV 2017.
  22. J. Yu, A. Eriksson, T.-J. Chin, and D. Suter: An Adversarial Optimization Approach to Efficient Outlier Removal. ICCV 2011.