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

 

 

Time	Topic	Slides	Presenter
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.