{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:47:02Z","timestamp":1750308422095,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T00:00:00Z","timestamp":1619395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Comput. Graph. Interact. Tech."],"published-print":{"date-parts":[[2021,4,26]]},"abstract":"<jats:p>The rotation averaging problem is a fundamental task in computer vision applications. It is generally very difficult to solve due to the nonconvex rotation constraints. While a sufficient optimality condition is available in the literature, there is a lack of a fast convergent algorithm to achieve stationary points. In this paper, by exploring the problem structure, we first propose a block coordinate descent (BCD)-based rotation averaging algorithm with guaranteed convergence to stationary points. Afterwards, we further propose an alternative rotation averaging algorithm by applying successive upper-bound minimization (SUM) method. The SUM-based rotation averaging algorithm can be implemented in parallel and thus is more suitable for addressing large-scale rotation averaging problems. Numerical examples verify that the proposed rotation averaging algorithms have superior convergence performance as compared to the state-of-the-art algorithm. Moreover, by checking the sufficient optimality condition, we find from extensive numerical experiments that the proposed two algorithms can achieve globally optimal solutions.<\/jats:p>","DOI":"10.1145\/3451263","type":"journal-article","created":{"date-parts":[[2021,4,29]],"date-time":"2021-04-29T04:17:37Z","timestamp":1619669857000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Algorithms for Rotation Averaging Problems"],"prefix":"10.1145","volume":"4","author":[{"given":"Yihong","family":"Dong","sequence":"first","affiliation":[{"name":"School of Software Engineering, Tongji University, Shanghai, China"}]},{"given":"Lunchen","family":"Xie","sequence":"additional","affiliation":[{"name":"School of Software Engineering, Tongji University, Shanghai, China"}]},{"given":"Qingjiang","family":"Shi","sequence":"additional","affiliation":[{"name":"School of Software Engineering, Tongji University, Shanghai, China"}]}],"member":"320","published-online":{"date-parts":[[2021,4,28]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Alexandr Andoni Piotr Indyk Thijs Laarhoven Ilya Razenshteyn and Ludwig Schmidt. 2015. Practical and optimal LSH for angular distance. In Advances in Neural Information Processing Systems. 1225--1233.  Alexandr Andoni Piotr Indyk Thijs Laarhoven Ilya Razenshteyn and Ludwig Schmidt. 2015. Practical and optimal LSH for angular distance. In Advances in Neural Information Processing Systems. 1225--1233."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600425"},{"key":"e_1_2_1_3_1","volume-title":"Asian Conference on Computer Vision. Springer, 335--346","author":"Dai Yuchao","year":"2009","unstructured":"Yuchao Dai , Jochen Trumpf , Hongdong Li , Nick Barnes , and Richard Hartley . 2009 . Rotation averaging with application to camera-rig calibration . In Asian Conference on Computer Vision. Springer, 335--346 . Yuchao Dai, Jochen Trumpf, Hongdong Li, Nick Barnes, and Richard Hartley. 2009. Rotation averaging with application to camera-rig calibration. In Asian Conference on Computer Vision. Springer, 335--346."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCVW.2011.6130252"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00021"},{"key":"e_1_2_1_6_1","volume-title":"Asian Conference on Computer Vision. Springer, 245--258","author":"Fredriksson Johan","year":"2012","unstructured":"Johan Fredriksson and Carl Olsson . 2012 . Simultaneous multiple rotation averaging using lagrangian duality . In Asian Conference on Computer Vision. Springer, 245--258 . Johan Fredriksson and Carl Olsson. 2012. Simultaneous multiple rotation averaging using lagrangian duality. In Asian Conference on Computer Vision. Springer, 245--258."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2001.990963"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198555.1198701"},{"key":"e_1_2_1_9_1","volume-title":"Proc. of the 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS'10)","author":"Hartley Richard","year":"2010","unstructured":"Richard Hartley , Jochen Trumpf , Yuchao Dai , 2010 . Rotation averaging and weak convexity . In Proc. of the 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS'10) . 2435--2442. Richard Hartley, Jochen Trumpf, Yuchao Dai, et al. 2010. Rotation averaging and weak convexity. In Proc. of the 19th International Symposium on Mathematical Theory of Networks and Systems (MTNS'10). 2435--2442."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-012-0601-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.8.000377"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2007.383115"},{"key":"e_1_2_1_13_1","volume-title":"SIFT: Predicting amino acid changes that affect protein function. Nucleic acids research 31, 13","author":"Ng Pauline C","year":"2003","unstructured":"Pauline C Ng and Steven Henikoff . 2003 . SIFT: Predicting amino acid changes that affect protein function. Nucleic acids research 31, 13 (2003), 3812--3814. Pauline C Ng and Steven Henikoff. 2003. SIFT: Predicting amino acid changes that affect protein function. Nucleic acids research 31, 13 (2003), 3812--3814."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3384382.3384530"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/120891009"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480191223178"},{"volume-title":"ACM transactions on graphics (TOG)","author":"Snavely Noah","key":"e_1_2_1_17_1","unstructured":"Noah Snavely , Steven M Seitz , and Richard Szeliski . 2006. Photo tourism: exploring photo collections in 3D . In ACM transactions on graphics (TOG) , Vol. 25 . ACM , 835--846. Noah Snavely, Steven M Seitz, and Richard Szeliski. 2006. Photo tourism: exploring photo collections in 3D. In ACM transactions on graphics (TOG), Vol. 25. ACM, 835--846."},{"key":"e_1_2_1_18_1","first-page":"6","article-title":"Minimization on the Lie group SO (3) and related manifolds","volume":"16","author":"Taylor Camillo J","year":"1994","unstructured":"Camillo J Taylor and David J Kriegman . 1994 . Minimization on the Lie group SO (3) and related manifolds . Yale University 16 , 155 (1994), 6 . Camillo J Taylor and David J Kriegman. 1994. Minimization on the Lie group SO (3) and related manifolds. Yale University 16, 155 (1994), 6.","journal-title":"Yale University"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46478-7_16"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0892-3"},{"key":"e_1_2_1_21_1","unstructured":"Yihong WU Zhanyi Hu Fuchao Wu and Qiulei Dong. [n.d.]. 3D reconstruction dataset. http:\/\/vision.ia.ac.cn\/data.  Yihong WU Zhanyi Hu Fuchao Wu and Qiulei Dong. [n.d.]. 3D reconstruction dataset. http:\/\/vision.ia.ac.cn\/data."}],"container-title":["Proceedings of the ACM on Computer Graphics and Interactive Techniques"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3451263","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3451263","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:26Z","timestamp":1750268966000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3451263"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,26]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,4,26]]}},"alternative-id":["10.1145\/3451263"],"URL":"https:\/\/doi.org\/10.1145\/3451263","relation":{},"ISSN":["2577-6193"],"issn-type":[{"type":"electronic","value":"2577-6193"}],"subject":[],"published":{"date-parts":[[2021,4,26]]},"assertion":[{"value":"2021-04-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}