Full Text:   <2303>

Summary:  <168>

CLC number: TP312; TP217.4

On-line Access: 2018-09-04

Received: 2018-03-20

Revision Accepted: 2018-07-02

Crosschecked: 2018-07-13

Cited: 0

Clicked: 1283

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Xiao-long Shen

http://orcid.org/0000-0002-6481-4287

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2018 Vol.19 No.7 P.889-904

http://doi.org/10.1631/FITEE.1800173


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


Author(s):  Xiao-long Shen, Yong Dou, Steven Mills, David M Eyers, Huan Feng, Zhiyi Huang

Affiliation(s):  College of Computer, National University of Defense Technology, Changsha 410000, China; more

Corresponding email(s):   shenxiaolong11@nudt.edu.cn, yongdou@nudt.edu.cn, steven@cs.otago.ac.nz, dme@cs.otago.ac.nz, fenghuan517@gmail.com

Key Words:  Sparse bundle adjustment, Parallel, Distributed sparse bundle adjustment, Three-dimensional reconstruction, Asynchronous


Xiao-long Shen, Yong Dou, Steven Mills, David M Eyers, Huan Feng, Zhiyi Huang. 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.

@article{title="Distributed sparse bundle adjustment algorithm based on three-dimensional point partition and asynchronous communication",
author="Xiao-long Shen, Yong Dou, Steven Mills, David M Eyers, Huan Feng, Zhiyi Huang",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="19",
number="7",
pages="889-904",
year="2018",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1800173"
}

%0 Journal Article
%T Distributed sparse bundle adjustment algorithm based on three-dimensional point partition and asynchronous communication
%A Xiao-long Shen
%A Yong Dou
%A Steven Mills
%A David M Eyers
%A Huan Feng
%A Zhiyi Huang
%J Frontiers of Information Technology & Electronic Engineering
%V 19
%N 7
%P 889-904
%@ 2095-9184
%D 2018
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1800173

TY - JOUR
T1 - Distributed sparse bundle adjustment algorithm based on three-dimensional point partition and asynchronous communication
A1 - Xiao-long Shen
A1 - Yong Dou
A1 - Steven Mills
A1 - David M Eyers
A1 - Huan Feng
A1 - Zhiyi Huang
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 19
IS - 7
SP - 889
EP - 904
%@ 2095-9184
Y1 - 2018
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1800173


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 (S-DSBA), 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).

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

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

关键词:稀疏捆绑调整;并行;分布式稀疏捆绑调整;3D重建;异步

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Agarwal S, Furukawa Y, Snavely N, et al., 2011. Building Rome in a day. Commun ACM, 54(10):105-112.

[2]Choudhary S, Gupta S, Narayanan P, 2010. Practical time bundle adjustment for 3D reconstruction on the GPU. In: Kutulakos KN (Ed.), Trends and Topics in Computer Vision. Springer-Verlag Berlin Heidelberg.

[3]Eriksson A, Bastian J, Chin T, et al., 2016. A consensus-based framework for distributed bundle adjustment. IEEE Conf on Computer Vision and Pattern Recognition, p.1754-1762.

[4]Frahm J, Fite-Georgel P, Gallup D, et al., 2010. Building Rome on a cloudless day. Proc 11th European Conf on Computer Vision, p.368-381.

[5]Hänsch R, Drude I, Hellwich O, 2016. Modern methods of bundle adjustment on the GPU. ISPRS Ann Photogr Remote Sens Spatial Inform Sci, III-(3):43-50.

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

[7]Heinecke A, Vaidyanathan K, Smelyanskiy M, et al., 2013. Design and implementation of the linpack benchmark for single and multi-node systems based on Inteltextregistered Xeon Phi coprocessor. Proc 27th Int Symp on Parallel and Distributed Processing, p.126-137.

[8]Husbands P, Yelick K, 2007. Multi-threading and one-sided communication in parallel LU factorization. ACM/IEEE Conf on Supercomputing, Article 31.

[9]Jo G, Nah J, Lee J, et al., 2015. Accelerating LINPACK with MPI-OpenCL on clusters of multi-GPU nodes. IEEE Trans Parall Distrib Syst, 26(7):1814-1825.

[10]Li X, Wu C, Zach C, et al., 2008. Modeling and recognition of landmark image collections using iconic scene graphs. Proc 10th European Conf on Computer Vision, p.427-440.

[11]Liu X, Gao W, Hu Z, 2012. Hybrid parallel bundle adjustment for 3D scene reconstruction with massive points. Comput Sci Technol, 27(6):1269-1280.

[12]Lourakis M, Argyros A, 2009. SBA: a software package for generic sparse bundle adjustment. ACM Trans Math Soft, 36(1), Article 2.

[13]Ni K, Steedly D, Dellaert F, 2007. Out-of-core bundle adjustment for large-scale 3D reconstruction. Proc 11th Int Conf on Computer Vision, p.1-8.

[14]Ramamurthy K, Lin C, Aravkin A, et al., 2017. Distributed bundle adjustment. IEEE Int Conf on Computer Vision Workshop, p.2146-2154.

[15]Snavely N, Seitz S, Szeliski R, 2006. Photo tourism: exploring photo collections in 3D. ACM Trans Graph, 25(3):835-846.

[16]Snavely N, Seitz S, Szeliski R, 2008. Skeletal graphs for efficient structure from motion. IEEE Conf on Computer Vision and Pattern Recognition, p.1-8.

[17]Triggs B, McLauchlan P, Hartley R, et al., 1999. Bundle adjustment—modern synthesis. Int Workshop on Vision Algorithms: Theory and Practice, p.298-372.

[18]Wu C, Agarwal S, Curless B, et al., 2011. Multicore bundle adjustment. IEEE Conf on Computer Vision and Pattern Recognition, p.3057-3064.

[19]Zheng E, Wu C, 2015. Structure from motion using structure-less resection. IEEE Int Conf on Computer Vision, p.2075-2083.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE