Distributed sparse bundle adjustment algorithm based on three-dimensional point partition and asynchronous communication

Xiao-long SHEN; Yong DOU; Steven MILLS; David M EYERS; Huan FENG; Zhiyi HUANG

doi:10.1631/FITEE.1800173

Your Location：

Home >

Browse articles >

Distributed sparse bundle adjustment algorithm based on three-dimensional point partition and asynchronous communication

Regular Papers | Updated：2022-05-19

- Distributed sparse bundle adjustment algorithm based on three-dimensional point partition and asynchronous communication
- 一种基于3D点划分和异步通信的分布式稀疏捆绑调整算法
- Frontiers of Information Technology & Electronic Engineering Vol. 19, Issue 7, Pages: 889-904(2018)
- Affiliations：
  
  College of Computer, National University of Defense Technology, Changsha 410000, China
  Science and Technology on Parallel and Distributed Laboratory, National University of Defense Technology, Changsha 410000, China
  Department of Computer Science, University of Otago, Dunedin 9016, New Zealand
  Department of Computer Science, Tsinghua University, Beijing 100084, China
- Author bio：
  
  Xiao-long SHEN, E-mail: shenxiaolong11@nudt.edu.cn
  [ "Yong DOU, E-mail:yongdou@nudt.edu.cn" ]
  [ "Steven MILLS, E-mail:steven@cs.otago.ac.nz" ]
  [ "David M EYERS, E-mail: dme@cs.otago.ac.nz" ]
  [ "Huan FENG, E-mail:fenghuan517@gmail.com" ]
  [ "Zhiyi HUANG, E-mail:zhuang@cs.otago.ac.nz" ]
- Funds：
- DOI：10.1631/FITEE.1800173
  CLC： TP312;TP217.4
- Received：20 March 2018，
  
  Revised：2018-;7-13，
  
  Published：2018-07
- Accepted：
Scan QR Code
Xiao-long SHEN, Yong DOU, Steven MILLS, et al. Distributed sparse bundle adjustment algorithm based on three-dimensional point partition and asynchronous communication[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(7): 889-904.
DOI：

Xiao-long SHEN, Yong DOU, Steven MILLS, et al. Distributed sparse bundle adjustment algorithm based on three-dimensional point partition and asynchronous communication[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(7): 889-904. DOI： 10.1631/FITEE.1800173.

摘要

稀疏捆绑调整（sparse bundle adjustment，SBA）是三维重建的关键步骤，但其速度慢且内存需求高。提出一种基于三维点的分布式SBA算法，以提高SBA速度和可扩展性。该算法利用异步约简通信机制（A-DSBA），将数据通信与方程组求解重叠。与同步DSBA（S-DSBA）相比，A-DSBA运行时间缩短46%。对几个三维重建数据集的实验结果表明，在8个节点上运行的分布式算法比独立并行SBA快5倍。此外，该算法在串行SBA（在单个节点上运行）上的加速比达到41。

Abstract

Sparse bundle adjustment (SBA) is a key but time- and memory-consuming step in three-dimensional (3D) reconstruction. In this paper

we propose a 3D point-based distributed SBA algorithm (DSBA) to improve the speed and scalability of SBA. The algorithm uses an asynchronously distributed sparse bundle adjustment (A-DSBA) to overlap data communication with equation computation. Compared with the synchronous DSBA mechanism (SDSBA)

A-DSBA reduces the running time by 46%. The experimental results on several 3D reconstruction datasets reveal that our distributed algorithm running on eight nodes is up to five times faster than that of the stand-alone parallel SBA. Furthermore

the speedup of the proposed algorithm (running on eight nodes with 48 cores) is up to 41 times that of the serial SBA (running on a single node).

关键词

Keywords

references

S Agarwal , , , Y Furukawa , , , N Snavely , , , 等 . . Building Rome in a day . . Commun ACM , , 2011 . . 54 ( ( 10 ): ): 105 - - 112 . . DOI: 10.1145/2001269.2001293 http://doi.org/10.1145/2001269.2001293 . .

S Choudhary , , , S Gupta , , , P Narayanan . . Practical time bundle adjustment for 3D reconstruction on the GPU. In: Kutulakos KN (Ed.), Trends and Topics in Computer Vision . . Springer-Verlag Berlin Heidelberg , , 2010 . . DOI: 10.1007/978-3-642-35740-4_33 http://doi.org/10.1007/978-3-642-35740-4_33 . .

A Eriksson , , , J Bastian , , , T Chin , , , 等 . . A consensusbased framework for distributed bundle adjustment . . IEEE Conf on Computer Vision and Pattern Recognition , , 2016 . . p.1754 - - 1762 . . DOI: 10.1109/CVPR.2016.194 http://doi.org/10.1109/CVPR.2016.194 . .

J Frahm , , , P Fite-Georgel , , , D Gallup , , , 等 . . Building Rome on a cloudless day . . Proc 11 th European Conf on Computer Vision , , 2010 . . p.368 - - 381 . . DOI: 10.1007/978-3-642-15561-1_27 http://doi.org/10.1007/978-3-642-15561-1_27 . .

R Hänsch , , , I Drude , , , O Hellwich . . Modern methods of bundle adjustment on the GPU . . ISPRS Ann Photogr Remote Sens Spatial Inform Sci , , 2016 . . Ⅲ- ( ( 3 ): ): 43 - - 50 . . DOI: 10.5194/isprs-annals-Ⅲ-3-43-2016 http://doi.org/10.5194/isprs-annals-Ⅲ-3-43-2016 . .

R Hartley , , , A Zisserman . . Multiple View Geometry in Computer Vision . . Cambridge University Press, Cambridge , , 2000 . . p.1865 - - 1872 . . . .

A Heinecke , , , K Vaidyanathan , , , M Smelyanskiy , , , 等 . . Design and implementation of the linpack benchmark for single and multi-node systems based on Intel® R Xeon Phi coprocessor . . Proc 27 th Int Symp on Parallel and Distributed Processing , , 2013 . . p.126 - - 137 . . DOI: 10.1109/IPDPS.2013.113 http://doi.org/10.1109/IPDPS.2013.113 . .

P Husbands , , , K Yelick . . Multi-threading and onesided communication in parallel LU factorization. ACM/IEEE Conf on Supercomputing . . Article 31 , , 2007 . . DOI: 10.1145/1362622.1362664 http://doi.org/10.1145/1362622.1362664 . .

G Jo , , , J Nah , , , J Lee , , , 等 . . Accelerating LINPACK with MPI-OpenCL on clusters of multi-GPU nodes . . IEEE Trans Parall Distrib Syst , , 2015 . . 26 ( ( 7 ): ): 1814 - - 1825 . . DOI: 10.1109/TPDS.2014.2321742 http://doi.org/10.1109/TPDS.2014.2321742 . .

X Li , , , C Wu , , , C Zach , , , 等 . . Modeling and recognition of landmark image collections using iconic scene graphs . . Proc 10th European Conf on Computer Vision , , 2008 . . p.427 - - 440 . . DOI: 10.1007/978-3-540-88682-2_33 http://doi.org/10.1007/978-3-540-88682-2_33 . .

X Liu , , , W Gao , , , Z Hu . . Hybrid parallel bundle adjustment for 3D scene reconstruction with massive points . . Comput Sci Technol , , 2012 . . 27 ( ( 6 ): ): 1269 - - 1280 . . DOI: 10.1007/s11390-012-1303-3 http://doi.org/10.1007/s11390-012-1303-3 . .

M Lourakis , , , A Argyros . . SBA: a software package for generic sparse bundle adjustment . . ACM Trans Math Soft , , 2009 . . 36 ( ( 1 ): ): Article 2 DOI: 10.1145/1486525.1486527 http://doi.org/10.1145/1486525.1486527 . .

K Ni , , , D Steedly , , , F Dellaert . . Out-of-core bundle adjustment for large-scale 3D reconstruction . . Proc 11 th Int Conf on Computer Vision , , 2007 . . p.1 - - 8 . . DOI: 10.1109/ICCV.2007.4409085 http://doi.org/10.1109/ICCV.2007.4409085 . .

K Ramamurthy , , , C Lin , , , A Aravkin , , , 等 . . Distributed bundle adjustment . . IEEE Int Conf on Computer Vision Workshop , , 2017 . . p.2146 - - 2154 . . DOI: 10.1109/ICCVW.2017.251 http://doi.org/10.1109/ICCVW.2017.251 . .

N Snavely , , , S Seitz , , , R Szeliski . . Photo tourism: exploring photo collections in 3D . . ACM Trans Graph , , 2006 . . 25 ( ( 3 ): ): 835 - - 846 . . DOI: 10.1145/1141911.1141964 http://doi.org/10.1145/1141911.1141964 . .

N Snavely , , , S Seitz , , , R Szeliski . . Skeletal graphs for efficient structure from motion . . IEEE Conf on Computer Vision and Pattern Recognition , , 2008 . . p.1 - - 8 . . DOI: 10.1109/CVPR.2008.4587678 http://doi.org/10.1109/CVPR.2008.4587678 . .

B Triggs , , , P McLauchlan , , , R Hartley , , , 等 . . Bundle adjustment—modern synthesis . . Int Workshop on Vision Algorithms: Theory and Practice , , 1999 . . p.298 - - 372 . . DOI: 10.1007/3-540-44480-7_21 http://doi.org/10.1007/3-540-44480-7_21 . .

C Wu , , , S Agarwal , , , B Curless , , , 等 . . Multicore bundle adjustment . . IEEE Conf on Computer Vision and Pattern Recognition , , 2011 . . p.3057 - - 3064 . . DOI: 10.1109/CVPR.2011.5995552 http://doi.org/10.1109/CVPR.2011.5995552 . .

E Zheng , , , C Wu . . Structure from motion using structureless resection . . IEEE Int Conf on Computer Vision , , 2015 . . p.2075 - - 2083 . . DOI: 10.1109/ICCV.2015.240 http://doi.org/10.1109/ICCV.2015.240 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

A new parallel meshing technique integrated into the conformal FDTD method for solving complex electromagnetic problems

Related Author

Yang GUO

Xiang-hua WANG

Jun HU

Related Institution

Centre for Optical and Electromagnetic Research, State Key Lab of MOI, Zhejiang University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰