一种用于分布式集束调整的低开销异步共识框架

刘卓昊; 刁常宇; 邢卫; 鲁东明

doi:10.1631/FITEE.1900451

Your Location：

Home >

Browse articles >

一种用于分布式集束调整的低开销异步共识框架

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

- 一种用于分布式集束调整的低开销异步共识框架
- A low-overhead asynchronous consensus framework for distributed bundle adjustment
- 信息与电子工程前沿（英文） 2020年21卷第10期页码：1442-1454
- Affiliations：
  
  College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
  Cultural Heritage Institute, Zhejiang University, Hangzhou 310027, China
  Key Scientific Research Base for Digital Conservation of Cave Temples, Zhejiang University, State Administration for Cultural Heritage, China
  4.Key Scientific Research Base for Digital Conservation of Cave Temples, Zhejiang University, Hangzhou 310027, China
- Author bio：
  
  [ "Zhuo-hao LIU, E-mail: roadliu@zju.edu.cn" ]
  Chang-yu DIAO, E-mail:dcy@zju.edu.cn
- Funds：
  
  Project supported by the Key R&D Program of Zhejiang Province, China (No. 2018C03051) and the Key Scientific Research Base for Digital Conservation of Cave Temples of the National Cultural Heritage Administration, China
- DOI：10.1631/FITEE.1900451
  中图分类号： TP391.41
- 收稿：2019-08-30，
  
  修回：2020-;6-;4，
  
  网络出版：2020-08-26，
  
  纸质出版：2020-10
- Accepted：
Scan QR Code
刘卓昊, 刁常宇, 邢卫, 等. 一种用于分布式集束调整的低开销异步共识框架[J]. 信息与电子工程前沿（英文）, 2020,21(10):1442-1454.

Zhuo-hao LIU, Chang-yu DIAO, Wei XING, et al. A low-overhead asynchronous consensus framework for distributed bundle adjustment[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(10): 1442-1454.
刘卓昊, 刁常宇, 邢卫, 等. 一种用于分布式集束调整的低开销异步共识框架[J]. 信息与电子工程前沿（英文）, 2020,21(10):1442-1454. DOI： 10.1631/FITEE.1900451.

Zhuo-hao LIU, Chang-yu DIAO, Wei XING, et al. A low-overhead asynchronous consensus framework for distributed bundle adjustment[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(10): 1442-1454. DOI： 10.1631/FITEE.1900451.

摘要

分布式集束调整方法使用多个工作节点解决集束调整问题，克服单台计算机的计算和内存存储限制。但是，额外的块划分步骤和同步等待会引入可观的性能开销。因此，我们提出一个低开销共识框架，该方法基于异步共识融合使先到达的节点先共识融合，避免等待较慢的计算节点。此外，提出一个场景汇总方法，并将其集成到块划分步骤，用以在小规模汇总场景上执行聚类。在公开数据集上的实验结果表明，本文方法可以提高工作节点利用率，减少块划分时间。此外，在大规模文化遗产数据集上的实验也证明该方法有效。

Abstract

Generally

the distributed bundle adjustment (DBA) method uses multiple worker nodes to solve the bundle adjustment problems and overcomes the computation and memory storage limitations of a single computer. However

the performance considerably degrades owing to the overhead introduced by the additional block partitioning step and synchronous waiting. Therefore

we propose a low-overhead consensus framework. A partial barrier based asynchronous method is proposed to early achieve consensus with respect to the faster worker nodes to avoid waiting for the slower ones. A scene summarization procedure is designed and integrated into the block partitioning step to ensure that clustering can be performed on the small summarized scene. Experiments conducted on public datasets show that our method can improve the worker node utilization rate and reduce the block partitioning time. Also

sample applications are demonstrated using our large-scale culture heritage datasets.

关键词

Keywords

references

S Agarwal , , , K Mierle . . https://ceres-solver.org https://ceres-solver.org , , Ceres Solver , , [Accessed on Feb. 23, 2020] 2012 . . .

S Agarwal , , , N Snavely , , , SM Seitz , , , 等 . . Bundle adjustment in the large . . Proc 11 th European Conf on Computer Vision , , 2010 . . p.29 - - 42 . . DOI: 10.1007/978-3-642-15552-9_3 http://doi.org/10.1007/978-3-642-15552-9_3 . .

RI Bo , , , ER Csetnek . . ADMM for monotone operators: convergence analysis and rates . . Adv Comput Math , , 2019 . . 45 ( ( 1 ): ): 327 - - 359 . . DOI: 10.1007/s10444-018-9619-3 http://doi.org/10.1007/s10444-018-9619-3 . .

S Boyd , , , N Parikh , , , E Chu , , , 等 . . Distributed optimization and statistical learning via the alternating direction method of multipliers . . Found Trends Mach Learn , , 2011 . . 3 ( ( 1 ): ): 1 - - 122 . . DOI: 10.1561/2200000016 http://doi.org/10.1561/2200000016 . .

ZP Cui , , , P Tan . . Global structure-from-motion by similarity averaging . . IEEE Int Conf on Computer Vision , , 2015 . . p.864 - - 872 . . DOI: 10.1109/ICCV.2015.105 http://doi.org/10.1109/ICCV.2015.105 . .

IS Dhillon . . Co-clustering documents and words using bipartite spectral graph partitioning . . ACM Int Conf on Knowledge Discovery and Data Mining , , 2001 . . p.269 - - 274 . . . .

HK Dhonju , , , W Xiao , , , JP Mills , , , 等 . . Share our cultural heritage (SOCH): worldwide 3D heritage reconstruction and visualization via web and mobile GIS . . ISPRS Int J Geo-Inform , , 2018 . . 7 ( ( 9 ): ): 360 DOI: 10.3390/ijgi7090360 http://doi.org/10.3390/ijgi7090360 . .

A Eriksson , , , J Bastian , , , TJ Chin , , , 等 . . A consensus-based 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 Feng , , , X He , , , B Konte , , , 等 . . Summarization-based mining bipartite graphs . . ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining , , 2012 . . p.1249 - - 1257 . . DOI: 10.1145/2339530.2339725 http://doi.org/10.1145/2339530.2339725 . .

S Fuhrmann , , , F Langguth , , , M Goesele . . MVE: a multi-view reconstruction environment . . EUROGRAPHICS Workshop on Graphics and Cultural Heritage , , 2014 . . p.11 - - 18 . . DOI: 10.2312/gch.20141299 http://doi.org/10.2312/gch.20141299 . .

Y Furukawa , , , B Curless , , , SM Seitz , , , 等 . . Towards Internet-scale multi-view stereo . . IEEE Computer Society Conf on Computer Vision and Pattern Recognition , , 2010 . . p.1434 - - 1441 . . DOI: 10.1109/CVPR.2010.5539802 http://doi.org/10.1109/CVPR.2010.5539802 . .

P Giselsson , , , S Boyd . . Linear convergence and metric selection for Douglas-Rachford splitting and ADMM . . IEEE Trans Autom Contr , , 2017 . . 62 ( ( 2 ): ): 532 - - 544 . . DOI: 10.1109/TAC.2016.2564160 http://doi.org/10.1109/TAC.2016.2564160 . .

JL Han , , , SH Shen . . Distributed surface reconstruction from point cloud for city-scale scenes . . Int Conf on 3D Vision , , 2019 . . p.338 - - 347 . . DOI: 10.1109/3DV.2019.00045 http://doi.org/10.1109/3DV.2019.00045 . .

BS He , , , XM Yuan . . On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method . . SIAM J Numer Anal , , 2012 . . 50 ( ( 2 ): ): 700 - - 709 . . DOI: 10.1137/110836936 http://doi.org/10.1137/110836936 . .

X Huang , , , YX Peng , , , MK Yuan . . MHTN: modal-adversarial hybrid transfer network for cross-modal retrieval . . IEEE Trans Cybern , , 2020 . . 50 ( ( 3 ): ): 1047 - - 1059 . . DOI: 10.1109/TCYB.2018.2879846 http://doi.org/10.1109/TCYB.2018.2879846 . .

K Konolige . . Sparse sparse bundle adjustment . . Proc British Machine Vision Conf , , 2010 . . p.102.1 - - 102.11 . . DOI: 10.5244/C.24.102 http://doi.org/10.5244/C.24.102 . .

A Kushal , , , S Agarwal . . Visibility based preconditioning for bundle adjustment . . IEEE Conf on Computer Vision and Pattern Recognition , , 2012 . . p.1442 - - 1449 . . DOI: 10.1109/CVPR.2012.6247832 http://doi.org/10.1109/CVPR.2012.6247832 . .

ZH Liu , , , CY Diao , , , W Xing , , , 等 . . Critical parameter consensus for efficient distributed bundle adjustment . . Proc 14 th Int Joint Conf on Computer Vision, Imaging and Computer Graphics Theory and Applications , , 2019 . . p.800 - - 807 . . DOI: 10.5220/0007361108000807 http://doi.org/10.5220/0007361108000807 . .

M Lourakis , , , AA Argyros . . Is Levenberg-Marquardt the most efficient optimization algorithm for implementing bundle adjustment . . IEEE Int Conf on Computer Vision , , 2005 . . p.1526 - - 1531 . . DOI: 10.1109/ICCV.2005.128 http://doi.org/10.1109/ICCV.2005.128 . .

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

LP Lu , , , Y Zhang , , , K Liu . . Block partitioning and merging for processing large-scale structure from motion problems in distributed manner . . IEEE Access , , 2019 . . 7 114400 - - 114413 . . DOI: 10.1109/ACCESS.2019.2923667 http://doi.org/10.1109/ACCESS.2019.2923667 . .

C Mostegel , , , M Rumpler , , , F Fraundorfer , , , 等 . . Using self-contradiction to learn confidence measures in stereo vision . . IEEE Conf on Computer Vision and Pattern Recognition , , 2016 . . p.4067 - - 4076 . . DOI: 10.1109/CVPR.2016.441 http://doi.org/10.1109/CVPR.2016.441 . .

C Mostegel , , , F Fraundorfer , , , H Bischof . . Prioritized multi-view stereo depth map generation using confidence prediction . . ISPRS J Photogr Remote Sens , , 2018 . . 143 167 - - 180 . . DOI: 10.1016/j.isprsjprs.2018.03.022 http://doi.org/10.1016/j.isprsjprs.2018.03.022 . .

O zyeil , , , V Voroninski , , , R Basri , , , 等 . . A survey of structure from motion . . Acta Numer , , 2017 . . 26 305 - - 364 . . DOI: 10.1017/S096249291700006X http://doi.org/10.1017/S096249291700006X . .

YX Peng , , , XH Zhai , , , YZ Zhao , , , 等 . . Semi-supervised cross-media feature learning with unified patch graph regularization . . IEEE Trans Circ Syst Video Technol , , 2016 . . 26 ( ( 3 ): ): 583 - - 596 . . DOI: 10.1109/TCSVT.2015.2400779 http://doi.org/10.1109/TCSVT.2015.2400779 . .

YX Peng , , , X Huang , , , YZ Zhao . . An overview of cross-media retrieval: concepts, methodologies, benchmarks, and challenges . . IEEE Trans Circ Syst Video Technol , , 2018 . . 28 ( ( 9 ): ): 2372 - - 2385 . . DOI: 10.1109/TCSVT.2017.2705068 http://doi.org/10.1109/TCSVT.2017.2705068 . .

H Rahaman , , , E Champion . . To 3D or not 3D: choosing a photogrammetry workflow for cultural heritage groups . . Heritage , , 2019 . . 2 ( ( 3 ): ): 1835 - - 1851 . . DOI: 10.3390/heritage2030112 http://doi.org/10.3390/heritage2030112 . .

JL Schnberger , , , JM Frahm . . Structure-from-motion revisited . . IEEE Conf on Computer Vision and Pattern Recognition , , 2016 . . p.4104 - - 4113 . . DOI: 10.1109/CVPR.2016.445 http://doi.org/10.1109/CVPR.2016.445 . .

JL Schnberger , , , EL Zheng , , , JM Frahm , , , 等 . . Pixelwise view selection for unstructured multi-view stereo . . 14 th European Conf on Computer Vision , , 2016 . . p.501 - - 518 . . DOI: 10.1007/978-3-319-46487-9_31 http://doi.org/10.1007/978-3-319-46487-9_31 . .

XL Shen , , , Y Dou , , , S Mills , , , 等 . . Distributed sparse bundle adjustment algorithm based on three-dimensional point partition and asynchronous communication . . Front Inform Technol Electron Eng , , 2018 . . 19 ( ( 7 ): ): 889 - - 904 . . DOI: 10.1631/FITEE.1800173 http://doi.org/10.1631/FITEE.1800173 . .

JB Shi , , , J Malik . . Normalized cuts and image segmentation . . IEEE Trans Patt Anal Mach Intell , , 2000 . . 22 ( ( 8 ): ): 888 - - 905 . . DOI: 10.1109/34.868688 http://doi.org/10.1109/34.868688 . .

I Simon , , , N Snavely , , , SM Seitz . . Scene summarization for online image collections . . IEEE 11 th Int Conf on Computer Vision , , 2007 . . p.1 - - 8 . . DOI: 10.1109/ICCV.2007.4408863 http://doi.org/10.1109/ICCV.2007.4408863 . .

N Snavely , , , SM 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 , , , PF McLauchlan , , , RI Hartley , , , 等 . . Bundle adjustment-a modern synthesis . . Int Workshop on Vision Algorithms , , 1999 . . p.298 - - 372 . . DOI: 10.1007/3-540-44480-7_21 http://doi.org/10.1007/3-540-44480-7_21 . .

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

XH Zhai , , , YX Peng , , , JG Xiao . . Learning cross-media joint representation with sparse and semisupervised regularization . . IEEE Trans Circ Syst Video Technol , , 2014 . . 24 ( ( 6 ): ): 965 - - 978 . . DOI: 10.1109/TCSVT.2013.2276704 http://doi.org/10.1109/TCSVT.2013.2276704 . .

RL Zhang , , , JT Kwok . . Asynchronous distributed ADMM for consensus optimization . . Proc 31 st Int Conf on Machine Learning , , 2014 . . p.1701 - - 1709 . . . .

RZ Zhang , , , SW Li , , , T Fang , , , 等 . . Joint camera clustering and surface segmentation for large-scale multi-view stereo . . Proc IEEE Int Conf on Computer Vision , , 2015 . . p.2084 - - 2092 . . DOI: 10.1109/ICCV.2015.241 http://doi.org/10.1109/ICCV.2015.241 . .

RZ Zhang , , , SY Zhu , , , TW Shen , , , 等 . . Distributed very large scale bundle adjustment by global camera consensus . . IEEE Trans Patt Anal Mach Intell , , 2020 . . 42 ( ( 2 ): ): 291 - - 303 . . DOI: 10.1109/TPAMI.2018.2840719 http://doi.org/10.1109/TPAMI.2018.2840719 . .

SY Zhu , , , T Fang , , , JX Xiao , , , 等 . . Local readjustment for high-resolution 3D reconstruction . . IEEE Conf on Computer Vision and Pattern Recognition , , 2014 . . p.3938 - - 3945 . . DOI: 10.1109/CVPR.2014.503 http://doi.org/10.1109/CVPR.2014.503 . .

SY Zhu , , , RZ Zhang , , , L Zhou , , , 等 . . Very large-scale global SFM by distributed motion averaging . . IEEE/CVF Conf on Computer Vision and Pattern Recognition , , 2018 . . p.4568 - - 4577 . . DOI: 10.1109/CVPR.2018.00480 http://doi.org/10.1109/CVPR.2018.00480 . .

浏览量

Downloads

CSCD

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

Submit

工具集

关联资源

暂无数据