一种基于3D点划分和异步通信的分布式稀疏捆绑调整算法

申小龙; 窦勇; Steven Mills; David M Eyers; 冯欢; 黄志毅

doi:10.1631/FITEE.1800173

Your Location：

Home >

Browse articles >

一种基于3D点划分和异步通信的分布式稀疏捆绑调整算法

常规文章 | Updated：2022-05-19

- 一种基于3D点划分和异步通信的分布式稀疏捆绑调整算法
- Distributed sparse bundle adjustment algorithm based on three-dimensional point partition and asynchronous communication
- 信息与电子工程前沿（英文） 2018年19卷第7期页码：889-904
- 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：
  
  Project supported by the National Natural Science Foundation of China (Nos. U1435219, U1435222, and 61572515), the National Key R & D Program of China (No. 2016YFB0200401), and the Major Research Plan of the National Key R & D Program of China (No. 2016YFC0901600)
- DOI：10.1631/FITEE.1800173
  中图分类号： TP312;TP217.4
- 收稿：2018-03-20，
  
  修回：2018-;7-13，
  
  纸质出版：2018-07
- Accepted：
Scan QR Code
申小龙, 窦勇, Steven Mills, 等. 一种基于3D点划分和异步通信的分布式稀疏捆绑调整算法[J]. 信息与电子工程前沿（英文）, 2018,19(7):889-904.

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.
申小龙, 窦勇, Steven Mills, 等. 一种基于3D点划分和异步通信的分布式稀疏捆绑调整算法[J]. 信息与电子工程前沿（英文）, 2018,19(7):889-904. DOI： 10.1631/FITEE.1800173.

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 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

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