Global Optimization for Geometric Understanding with Provable Guarantees
Time: Sunday Morning, Oct. 27 Room: 402, COEX Convention Center, Seoul, Korea
Overview
This tutorial aims to give an in-depth introduction to global optimization tools, including convex and semidefinite relaxations, applied to 3D vision problems. The first goal of the tutorial is to motivate the need for global solvers by providing real-world examples where the lack of robustness results from the difficulty in solving large optimization problems to optimality. The second goal is to provide the attendees with basic mathematical and algorithmic concepts, and survey important recent advances in the area. The third goal is to outline several open research avenues: global optimization has an enormous untapped potential and it is hoped that this tutorial will inspire researchers to use modern optimization tools to solve several outstanding challenges in geometric vision.
Hands-on Tutorial on Global Optimization in Matlab
We have prepared a detailed hands-on tutorial for using global optimization in Matlab to solve Rotation Averaging and Pose Graph Optimization. We highly encourage people to read and try out the tutorial. Download the tutorial here.
List of non-minimal solvers in computer vision and robotics
With powerful global optimization techniques, typically based on Semidefinite and Sums of Squares Relaxations, the research community have developed certifiably optimal non-minimal solvers for many computer vision and robotics problems that used to be known as non-convex and NP-hard. We here provide a list of references to the best of our knowledge and we hope this list can keep growing!
Garcia-Salguero, M., & Gonzalez-Jimenez, J. (2021). Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras. ArXiv Preprint ArXiv:2101.08524.
@article{Garcia21arXiv-FastCertTwoView,
title = {Fast and Robust Certifiable Estimation of the Relative Pose Between Two Calibrated Cameras},
author = {Garcia-Salguero, Mercedes and Gonzalez-Jimenez, Javier},
journal = {arXiv preprint arXiv:2101.08524},
year = {2021},
pdf = {https://arxiv.org/pdf/2101.08524.pdf}
}
Garcia-Salguero, M., Briales, J., & Gonzalez-Jimenez, J. (2020). Certifiable Relative Pose Estimation. ArXiv Preprint ArXiv:2003.13732.
@article{Garcia20arXiv-certifiableRelativePose,
title = {{Certifiable Relative Pose Estimation}},
author = {Garcia-Salguero, Mercedes and Briales, Jesus and Gonzalez-Jimenez, Javier},
journal = {arXiv preprint arXiv:2003.13732},
year = {2020},
pdf = {https://arxiv.org/pdf/2003.13732.pdf}
}
Yang, H., & Carlone, L. (2020). In Perfect Shape: Certifiably Optimal 3D Shape Reconstruction from 2D Landmarks. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR).
@inproceedings{Yang20cvpr-shapeRecon,
title = {{In Perfect Shape: Certifiably Optimal 3D Shape Reconstruction from 2D Landmarks}},
author = {Yang, Heng and Carlone, Luca},
booktitle = {IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)},
year = {2020},
pdf = {https://arxiv.org/pdf/1911.11924.pdf}
}
Yang, H., & Carlone, L. (2020). One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers. Advances in Neural Information Processing Systems (NeurIPS).
@inproceedings{Yang20NeurIPS-CertifiablePerception,
title = {One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers},
author = {Yang, Heng and Carlone, Luca},
booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
year = {2020},
pdf = {https://arxiv.org/abs/2006.06769}
}
Lajoie, P., Hu, S., Beltrame, G., & Carlone, L. (2019). Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models. IEEE Robotics and Automation Letters (RA-L).
@article{Lajoie19ral-DCGM,
author = {Lajoie, P. and Hu, S. and Beltrame, G. and Carlone, L.},
title = {Modeling Perceptual Aliasing in {SLAM} via Discrete-Continuous Graphical Models},
journal = {{IEEE} Robotics and Automation Letters ({RA-L})},
pdf = {https://arxiv.org/pdf/1810.11692.pdf},
year = {2019}
}
Giamou, M., Ma, Z., Peretroukhin, V., & Kelly, J. (2019). Certifiably Globally Optimal Extrinsic Calibration From Per-Sensor Egomotion. IEEE Robotics and Automation Letters (RA-L), 4(2), 367–374.
@article{Giamou19ral-SDPExtrinsicCalibration,
title = {Certifiably Globally Optimal Extrinsic Calibration From Per-Sensor Egomotion},
author = {Giamou, Matthew and Ma, Ziye and Peretroukhin, Valentin and Kelly, Jonathan},
journal = {{IEEE} Robotics and Automation Letters ({RA-L})},
volume = {4},
number = {2},
pages = {367--374},
year = {2019},
publisher = {IEEE},
pdf = {https://arxiv.org/pdf/1809.03554.pdf}
}
Zhao, J. (2019). An Efficient Solution to Non-Minimal Case Essential Matrix Estimation. ArXiv Preprint ArXiv:1903.09067.
@article{zhao19arxiv-relativePose,
title = {An Efficient Solution to Non-Minimal Case Essential Matrix Estimation},
author = {Zhao, Ji},
journal = {arXiv preprint arXiv:1903.09067},
pdf = {https://arxiv.org/pdf/1903.09067.pdf},
year = {2019}
}
Agostinho, S., Gomes, J., & Del Bue, A. (2019). CvxPnPL: A unified convex solution to the absolute pose estimation problem from point and line correspondences. ArXiv Preprint ArXiv:1907.10545.
@article{agostinho19arxiv-cvxpnpl,
title = {Cvx{P}n{PL}: A unified convex solution to the absolute pose estimation problem from point and line correspondences},
author = {Agostinho, S{\'e}rgio and Gomes, Jo{\~a}o and Del Bue, Alessio},
journal = {arXiv preprint arXiv:1907.10545},
pdf = {https://arxiv.org/pdf/1907.10545.pdf},
year = {2019}
}
Yang, H., & Carlone, L. (2019). A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers. Intl. Conf. on Computer Vision (ICCV).
@inproceedings{Yang19iccv-QUASAR,
title = {A Quaternion-based Certifiably Optimal Solution to the {Wahba} Problem with Outliers},
author = {Yang, Heng and Carlone, Luca},
booktitle = {Intl. Conf. on Computer Vision (ICCV)},
pdf = {https://arxiv.org/pdf/1905.12536.pdf},
year = {2019}
}
Yang, H., & Carlone, L. (2019). A Polynomial-time Solution for Robust Registration with Extreme Outlier Rates. Robotics: Science and Systems (RSS).
@inproceedings{Yang19rss-teaser,
author = {Yang, Heng and Carlone, Luca},
title = {A Polynomial-time Solution for Robust Registration with Extreme Outlier Rates},
booktitle = {Robotics: Science and Systems (RSS)},
pdf = {https://arxiv.org/pdf/1903.08588.pdf},
year = {2019}
}
Yenamandra, T., Bernard, F., Wang, J., Mueller, F., & Theobalt, C. (2019). Convex Optimisation for Inverse Kinematics. ArXiv Preprint ArXiv:1910.11016.
@article{Yenamandra19arXiv-SDPInverseKinematics,
title = {Convex Optimisation for Inverse Kinematics},
author = {Yenamandra, Tarun and Bernard, Florian and Wang, Jiayi and Mueller, Franziska and Theobalt, Christian},
journal = {arXiv preprint arXiv:1910.11016},
year = {2019},
pdf = {https://arxiv.org/pdf/1910.11016.pdf}
}
Probst, T., Paudel, D. P., Chhatkuli, A., & Van Gool, L. (2019). Convex Relaxations for Consensus and Non-Minimal Problems in 3D Vision. Intl. Conf. on Computer Vision (ICCV).
@article{Probst19ICCV-convexRelaxationNonminimal,
title = {Convex Relaxations for Consensus and Non-Minimal Problems in {3D} Vision},
author = {Probst, Thomas and Paudel, Danda Pani and Chhatkuli, Ajad and Van Gool, Luc},
journal = {Intl. Conf. on Computer Vision (ICCV)},
year = {2019},
pdf = {https://arxiv.org/pdf/1909.12034.pdf}
}
Rosen, D. M., Carlone, L., Bandeira, A. S., & Leonard, J. J. (2018). SE-Sync: a certifiably correct algorithm for synchronization over the Special Euclidean group. Intl. J. of Robotics Research.
@article{Rosen18ijrr-sesync,
author = {Rosen, David M and Carlone, Luca and Bandeira, Afonso S and Leonard, John J},
title = {{SE-Sync}: a certifiably correct algorithm for synchronization over the
{Special Euclidean} group},
journal = {Intl. J. of Robotics Research},
pdf = {https://arxiv.org/pdf/1612.07386.pdf},
year = {2018}
}
Briales, J., Kneip, L., & Gonzalez-Jimenez, J. (2018). A certifiably globally optimal solution to the non-minimal relative pose problem. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 145–154.
@inproceedings{briales18CVPR-relativePose,
title = {A certifiably globally optimal solution to the non-minimal relative pose problem},
author = {Briales, Jesus and Kneip, Laurent and Gonzalez-Jimenez, Javier},
booktitle = {IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)},
pages = {145--154},
year = {2018},
pdf = {http://openaccess.thecvf.com/content_cvpr_2018/CameraReady/3968.pdf}
}
Eriksson, A., Olsson, C., Kahl, F., & Chin, T.-J. (2018). Rotation averaging and strong duality. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR).
@inproceedings{Eriksson18cvpr-rotationAveraging,
title = {Rotation averaging and strong duality},
author = {Eriksson, Anders and Olsson, Carl and Kahl, Fredrik and Chin, Tat-Jun},
booktitle = {IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)},
year = {2018},
pdf = {https://arxiv.org/pdf/1705.01362.pdf}
}
Briales, J., & Gonzalez-Jimenez, J. (2017). Convex global 3D registration with lagrangian duality. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 4960–4969.
@inproceedings{briales17CVPR-registration,
title = {Convex global 3{D} registration with lagrangian duality},
author = {Briales, Jesus and Gonzalez-Jimenez, Javier},
booktitle = {IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)},
pages = {4960--4969},
year = {2017},
pdf = {https://zpascal.net/cvpr2017/Briales_Convex_Global_3D_CVPR_2017_paper.pdf}
}
Maron, H., Dym, N., Kezurer, I., Kovalsky, S., & Lipman, Y. (2016). Point registration via efficient convex relaxation. ACM Transactions on Graphics (TOG), 35(4), 1–12.
@article{Maron16tog-RegistrationSDP,
title = {Point registration via efficient convex relaxation},
author = {Maron, Haggai and Dym, Nadav and Kezurer, Itay and Kovalsky, Shahar and Lipman, Yaron},
journal = {ACM Transactions on Graphics (TOG)},
volume = {35},
number = {4},
pages = {1--12},
year = {2016},
publisher = {ACM New York, NY, USA},
pdf = {https://shaharkov.github.io/projects/ProcrustesMatchingSDP_lowres.pdf}
}
Carlone, L., Calafiore, G. C., Tommolillo, C., & Dellaert, F. (2016). Planar pose graph optimization: Duality, optimal solutions, and verification. IEEE Trans. Robotics.
@article{carlone2016planar,
title = {Planar pose graph optimization: Duality, optimal solutions, and verification},
author = {Carlone, Luca and Calafiore, Giuseppe C and Tommolillo, Carlo and Dellaert, Frank},
journal = {{IEEE} Trans. Robotics},
year = {2016},
pdf = {https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7470464}
}
Carlone, L., & Dellaert, F. (2015). Duality-based verification techniques for 2D SLAM. IEEE Intl. Conf. on Robotics and Automation (ICRA).
@inproceedings{Carlone15icra-duality2DSLAM,
title = {Duality-based verification techniques for {2D SLAM}},
author = {Carlone, Luca and Dellaert, Frank},
booktitle = {IEEE Intl. Conf. on Robotics and Automation (ICRA)},
year = {2015},
pdf = {https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7139835}
}
Chaudhury, K. N., Khoo, Y., & Singer, A. (2015). Global registration of multiple point clouds using semidefinite programming. SIAM Journal on Optimization, 25(1), 468–501.
@article{Chaudhury15Jopt-multiplePointCloudRegistration,
title = {Global registration of multiple point clouds using semidefinite programming},
author = {Chaudhury, Kunal N and Khoo, Yuehaw and Singer, Amit},
journal = {SIAM Journal on Optimization},
volume = {25},
number = {1},
pages = {468--501},
year = {2015},
publisher = {SIAM},
pdf = {https://epubs.siam.org/doi/pdf/10.1137/130935458}
}
Wang, L., & Singer, A. (2013). Exact and stable recovery of rotations for robust synchronization. Information and Inference: A Journal of the IMA, 2(2), 145–193.
@article{Wang13ii-rotationSync,
title = {Exact and stable recovery of rotations for robust synchronization},
author = {Wang, Lanhui and Singer, Amit},
journal = {Information and Inference: A Journal of the IMA},
volume = {2},
number = {2},
pages = {145--193},
year = {2013},
publisher = {Oxford University Press},
pdf = {https://arxiv.org/pdf/1211.2441.pdf}
}
Aholt, C., Agarwal, S., & Thomas, R. (2012). A QCQP approach to triangulation. European Conf. on Computer Vision (ECCV), 654–667.
@inproceedings{Aholt12ECCV-qcqpTriangulation,
title = {{A QCQP approach to triangulation}},
author = {Aholt, Chris and Agarwal, Sameer and Thomas, Rekha},
booktitle = {European Conf. on Computer Vision (ECCV)},
pages = {654--667},
year = {2012},
organization = {Springer},
pdf = {https://arxiv.org/pdf/1207.7160.pdf}
}
Fredriksson, J., & Olsson, C. (2012). Simultaneous multiple rotation averaging using lagrangian duality. Asian Conf. on Computer Vision (ACCV), 245–258.
@inproceedings{Fredriksson12accv-rotationaveragingLagrangian,
title = {Simultaneous multiple rotation averaging using lagrangian duality},
author = {Fredriksson, Johan and Olsson, Carl},
booktitle = {Asian Conf. on Computer Vision (ACCV)},
pages = {245--258},
year = {2012},
organization = {Springer},
pdf = {http://www1.maths.lth.se/matematiklth/vision/publdb/reports/pdf/fredriksson-olsson-accv-12.pdf}
}
Schweighofer, G., & Pinz, A. (2008). Globally Optimal O (n) Solution to the PnP Problem for General Camera Models. British Machine Vision Conf. (BMVC), 1–10.
@inproceedings{schweighofer08BMVC-SOSPnP,
title = {Globally Optimal O (n) Solution to the PnP Problem for General Camera Models.},
author = {Schweighofer, Gerald and Pinz, Axel},
booktitle = {British Machine Vision Conf. (BMVC)},
pages = {1--10},
year = {2008},
pdf = {https://pdfs.semanticscholar.org/0e14/b9c6532d217a7ecb32354869a87aa8819a9c.pdf}
}
Kahl, F., & Henrion, D. (2007). Globally optimal estimates for geometric reconstruction problems. Intl. J. of Computer Vision, 74(1), 3–15.
@article{Kahl07ijcv-globalGeometricReconstruction,
title = {Globally optimal estimates for geometric reconstruction problems},
author = {Kahl, Fredrik and Henrion, Didier},
journal = {Intl. J. of Computer Vision},
volume = {74},
number = {1},
pages = {3--15},
year = {2007},
publisher = {Springer},
pdf = {http://www.cs.ait.ac.th/~mdailey/cvreadings/Kahl-Global.pdf}
}
