A Quaternion-Based Certifiably Optimal Solution to the Wahba Problem With Outliers
© 2019 IEEE. The Wahba problem, also known as rotation search, seeks to find the best rotation to align two sets of vector observations given putative correspondences, and is a fundamental routine in many computer vision and robotics applications. This work proposes the first polynomial-time certifi...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021
|
| Online Access: | https://hdl.handle.net/1721.1/138065 |
| _version_ | 1826194365484105728 |
|---|---|
| author | Yang, Heng Carlone, Luca |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Yang, Heng Carlone, Luca |
| author_sort | Yang, Heng |
| collection | MIT |
| description | © 2019 IEEE. The Wahba problem, also known as rotation search, seeks to find the best rotation to align two sets of vector observations given putative correspondences, and is a fundamental routine in many computer vision and robotics applications. This work proposes the first polynomial-time certifiably optimal approach for solving the Wahba problem when a large number of vector observations are outliers. Our first contribution is to formulate the Wahba problem using a Truncated Least Squares (TLS) cost that is insensitive to a large fraction of spurious correspondences. The second contribution is to rewrite the problem using unit quaternions and show that the TLS cost can be framed as a Quadratically-Constrained Quadratic Program (QCQP). Since the resulting optimization is still highly non-convex and hard to solve globally, our third contribution is to develop a convex Semidefinite Programming (SDP) relaxation. We show that while a naive relaxation performs poorly in general, our relaxation is tight even in the presence of large noise and outliers. We validate the proposed algorithm, named QUASAR (QUAternion-based Semidefinite relAxation for Robust alignment), in both synthetic and real datasets showing that the algorithm outperforms RANSAC, robust local optimization techniques, global outlier-removal procedures, and Branch-and-Bound methods. QUASAR is able to compute certifiably optimal solutions (i.e. the relaxation is exact) even in the case when 95% of the correspondences are outliers. |
| first_indexed | 2024-09-23T09:54:52Z |
| format | Article |
| id | mit-1721.1/138065 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:54:52Z |
| publishDate | 2021 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1380652023-04-07T20:04:51Z A Quaternion-Based Certifiably Optimal Solution to the Wahba Problem With Outliers Yang, Heng Carlone, Luca Massachusetts Institute of Technology. Laboratory for Information and Decision Systems © 2019 IEEE. The Wahba problem, also known as rotation search, seeks to find the best rotation to align two sets of vector observations given putative correspondences, and is a fundamental routine in many computer vision and robotics applications. This work proposes the first polynomial-time certifiably optimal approach for solving the Wahba problem when a large number of vector observations are outliers. Our first contribution is to formulate the Wahba problem using a Truncated Least Squares (TLS) cost that is insensitive to a large fraction of spurious correspondences. The second contribution is to rewrite the problem using unit quaternions and show that the TLS cost can be framed as a Quadratically-Constrained Quadratic Program (QCQP). Since the resulting optimization is still highly non-convex and hard to solve globally, our third contribution is to develop a convex Semidefinite Programming (SDP) relaxation. We show that while a naive relaxation performs poorly in general, our relaxation is tight even in the presence of large noise and outliers. We validate the proposed algorithm, named QUASAR (QUAternion-based Semidefinite relAxation for Robust alignment), in both synthetic and real datasets showing that the algorithm outperforms RANSAC, robust local optimization techniques, global outlier-removal procedures, and Branch-and-Bound methods. QUASAR is able to compute certifiably optimal solutions (i.e. the relaxation is exact) even in the case when 95% of the correspondences are outliers. 2021-11-09T19:55:16Z 2021-11-09T19:55:16Z 2019-10 2021-04-09T17:55:24Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/138065 Yang, Heng and Carlone, Luca. 2019. "A Quaternion-Based Certifiably Optimal Solution to the Wahba Problem With Outliers." Proceedings of the IEEE International Conference on Computer Vision, 2019-October. en 10.1109/iccv.2019.00175 Proceedings of the IEEE International Conference on Computer Vision Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE arXiv |
| spellingShingle | Yang, Heng Carlone, Luca A Quaternion-Based Certifiably Optimal Solution to the Wahba Problem With Outliers |
| title | A Quaternion-Based Certifiably Optimal Solution to the Wahba Problem With Outliers |
| title_full | A Quaternion-Based Certifiably Optimal Solution to the Wahba Problem With Outliers |
| title_fullStr | A Quaternion-Based Certifiably Optimal Solution to the Wahba Problem With Outliers |
| title_full_unstemmed | A Quaternion-Based Certifiably Optimal Solution to the Wahba Problem With Outliers |
| title_short | A Quaternion-Based Certifiably Optimal Solution to the Wahba Problem With Outliers |
| title_sort | quaternion based certifiably optimal solution to the wahba problem with outliers |
| url | https://hdl.handle.net/1721.1/138065 |
| work_keys_str_mv | AT yangheng aquaternionbasedcertifiablyoptimalsolutiontothewahbaproblemwithoutliers AT carloneluca aquaternionbasedcertifiablyoptimalsolutiontothewahbaproblemwithoutliers AT yangheng quaternionbasedcertifiablyoptimalsolutiontothewahbaproblemwithoutliers AT carloneluca quaternionbasedcertifiablyoptimalsolutiontothewahbaproblemwithoutliers |