Distributed bundle adjustment method for super large-scale datasets based on LM algorithm

doi:10.11947/j.AGCS.2025.20240142

Abstract

Abstract:

This paper proposes a distributed bundle adjustment method based on Levenberg Marquardt (LM) model for large-scale dataset. In order to solve the storage and solution of large-scale coefficient matrix of normal equation, a block-based sparse matrix compression format (BSMC) is used to compress the coefficient matrix of normal equation by taking advantage of its sparse block characteristics. This format also supports distributed storage and update of the coefficient matrix of normal equation. Based on the above compression format, a distributed bundle adjustment method adjustment framework based on the strict LM model has been established. By constructing the normal equations in distributed parallel and parallelizing other steps with high computational complexity, the distributed bundle adjustment for large-scale dataset has been achieved. Through comprehensive comparative experiments between the method proposed in this paper and state-of-the-art methods, the preliminary results show that the memory requirement of this method is significantly reduced, and the data processing capacity is significantly improved. For the first time, we have implemented a bundle adjustment based on the LM strict model on a distributed computing system, which includes real dataset with 1.18 million images and simulated dataset with 10 million images (approximately 500 times the state-or-the-art method based on the LM strict model).

Key words: distributed computing system, bundle adjustment, Levenberg Marquardt algorithm, sparse matrix compression, preconditioned conjugate gradient

CLC Number:

P236

Maoteng ZHENG, Yihui LU, Junfeng ZHU, Xiaoru ZENG, Huanbin QIU, Yuyao JIANG, Xingyue LU, Hao QU, Nengcheng CHEN. Distributed bundle adjustment method for super large-scale datasets based on LM algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2025, 54(5): 899-910.

Figures/Tables 10

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Tab. 1

Tab. 2

Tab. 3

Fig. 5

Fig. 6

Fig. 7

References 39

[1]	李德仁. 展望大数据时代的地球空间信息学[J]. 测绘学报, 2016, 45(4): 379-384. DOI: . doi: 10.11947/j.AGCS.2016.20160057
	LI Deren. Towards geo-spatial information science in big data era[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4): 379-384. DOI: . doi: 10.11947/j.AGCS.2016.20160057
[2]	言司. 独辟蹊径，不断创新　贴近摄影测量：第三种摄影测量方式的诞生：专访武汉大学遥感信息工程学院张祖勋院士[J]. 中国测绘, 2019(10): 31-37.
	YAN Si. Creating a new way, constantly innovating and approaching photogrammetry: the birth of the third photogrammetry method: interview with academician ZHANG Zuxun from school of remote sensing information engineering, Wuhan University[J]. China Surveying and Mapping, 2019(10): 31-37.
[3]	李清泉, 黄惠, 姜三, 等. 优视摄影测量方法及精度分析[J]. 测绘学报, 2022, 51(6): 996-1007. DOI: . doi: 10.11947/J.AGCS.2022.20210685
	LI Qingquan, HUANG Hui, JIANG San, et al. Optimized views photogrammetry and its precision analysis[J]. Acta Geodaetica et Cartographica Sinica, 2022, 51(6): 996-1007. DOI: . doi: 10.11947/j.AGCS.2022.20210685
[4]	闫利, 费亮, 叶志云, 等. 大范围倾斜多视影像连接点自动提取的区域网平差法[J]. 测绘学报, 2016, 45(3): 310-317. DOI: . doi: 10.11947/J.AGCS.2016.20140673
	YAN Li, FEI Liang, YE Zhiyun, et al. Automatic tie-point sextraction for triangulation of large-scale oblique multi-view images[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(3): 310-317. DOI: . doi: 10.11947/j.AGCS.2016.20140673
[5]	郑茂腾, 张永军, 朱俊峰, 等. 一种快速有效的大数据区域网平差方法[J]. 测绘学报, 2017, 46(2): 188-197. DOI: . doi: 10.11947/j.AGCS.2017.20160293
	ZHENG Maoteng, ZHANG Yongjun, ZHU Junfeng, et al. A fast and effective block adjustment method with big data[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2): 188-197. DOI: . doi: 10.11947/j.AGCS.2017.20160293
[6]	郑茂腾, 周顺平, 熊小东, 等. GPU并行区域网平差[J]. 测绘学报, 2017, 46(9): 1193-1201. DOI: . doi: 10.11947/j.AGCS.2017.20160636
	ZHENG Maoteng, ZHOU Shunping, XIONG Xiaodong, et al. GPU parallel bundle block adjustment[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(9): 1193-1201. DOI: . doi: 10.11947/j.AGCS.2017.20160636
[7]	LEVENBERG K. A method for the solution of certain non-linear problems in least squares[J]. Quarterly of Applied Mathematics, 1944, 2(2): 164-168.
[8]	MARQUARDT D W. An algorithm for least-squares estimation of nonlinear parameters[J]. Journal of the Society for Industrial and Applied Mathematics, 1963, 11(2): 431-441.
[9]	王祥, 张永军, 黄山, 等. 旋转多基线摄影光束法平差法方程矩阵带宽优化[J]. 测绘学报, 2016, 45(2): 170-177. DOI: . doi: 10.11947/j.AGCS.2016.20150282
	WANG Xiang, ZHANG Yongjun, HUANG Shan, et al. Bandwidth optimization of normal equation matrix in bundle block adjustment in multi-baseline rotational photography[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(2): 170-177. DOI: . doi: 10.11947/j.AGCS.2016.20150282
[10]	林诒勋. 稀疏矩阵计算中的带宽最小化问题[J]. 运筹学杂志, 1983, 2(1): 20-27.
	LIN Yixun. Bandwidth minimization problem in sparse matrix computations[J]. Chinese Journal of Operations Research, 1983, 2(1): 20-27.
[11]	郑志镇, 李尚健, 李志刚. 稀疏矩阵带宽减小的一种算法[J]. 华中理工大学学报, 1998, 26(12): 43-45.
	ZHENG Zhizhen, LI Shangjian, LI Zhigang. A new algorithm for reducing bandwidth of sparse matrix[J]. Journal of Huazhong University of Science and Technology, 1998, 26(12): 43-45.
[12]	GIBBS N E, POOLE W G, STOCKMEYER P K. An algorithm for reducing the bandwidth and profile of a sparse matrix[J]. SIAM Journal on Numerical Analysis, 1976, 13(2): 236-250.
[13]	ZHOU Lei, LUO Zixin, ZHEN Mingmin, et al. Stochastic bundle adjustment for efficient and scalable 3D reconstruction[C]//Procceedings of 2020 Computer Vision. Cham: Springer International Publishing, 2020: 364-379.
[14]	DEMMEL N, GAO Maolin, LAUDE E, et al. Distributed photometric bundle adjustment[C]//Proceedings of 2020 International Conference on 3D Vision. Fukuoka: IEEE, 2020: 140-149.
[15]	ERIKSSON A, BASTIAN J, CHIN T J, et al. A consensus-based framework for distributed bundle adjustment[C]//Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas: IEEE, 2016: 1754-1762.
[16]	RAMAMURTHY K N, LIN C C, ARAVKIN A, et al. Distributed bundle adjustment[C]//Proceedings of 2017 IEEE International Conference on Computer Vision Workshops. Venice: IEEE, 2017: 2146-2154.
[17]	ZHANG Runze, ZHU Siyu, FANG Tian, et al. Distributed very large scale bundle adjustment by global camera consensus[C]//Procceedings of 2017 IEEE International Conference on Computer Vision. Venice: IEEE, 2017: 29-38.
[18]	GOVINDU V M. Lie-algebraic averaging for globally consistent motion estimation[C]//Proceedings of 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington: IEEE, 2004: 684-691.
[19]	HARTLEY R, TRUMPF J, DAI Yuchao, et al. Rotation averaging[J]. International Journal of Computer Vision, 2013, 103(3): 267-305.
[20]	ZHU Siyu, SHEN Tianwei, ZHOU Lei, et al. Parallel structure from motion from local increment to global averaging[EB/OL]. [2024-02-06]. https://arxiv.org/abs/1702.08601.
[21]	TOSELLI A, WIDLUND O. Domain decomposition methods algorithms and theory[M]. Berlin: Springer, 2004.
[22]	HUANG Jingwei, HUANG Shan, SUN Mingwei. DeepLM: large-scale nonlinear least squares on deep learning frameworks using stochastic domain decomposition[C]//Proceedings of 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Nashville: IEEE, 2021: 10303-10312.
[23]	ZHENG Maoteng, ZHOU Shunping, XIONG Xiaodong, et al. A new GPU bundle adjustment method for large-scale data[J]. Photogrammetric Engineering & Remote Sensing, 2017, 83(9): 633-641.
[24]	REN Jie, LIANG Wenteng, YAN Ran, et al. Megba: a GPU-based distributed library for largescale bundle adjustment[C]//Proceedings of 2022 ECCV. Tel Aviv: Springer, 2022: 715-731.
[25]	WU Changchang, AGARWAL S, CURLESS B, et al. Multicore bundle adjustment[C]//Procceedings of 2011 CVPR. Colorado: IEEE, 2011: 3057-3064.
[26]	FRAHM J M, FITE-GEORGEL P, GALLUP D, et al. Building Rome on a cloudless day[C]//Proceedings of 2010 European Conference on Computer Vision. Berlin: Springer, 2010.
[27]	JARED H, SCHONBERGER J L, DUNN E, et al. Reconstructing the world in six days[C]//Proceedings of 2015 CVPR. Boston: IEEE, 2015.
[28]	KLINGNER B, MARTIN D, ROSEBOROUGH J. Street view motion-from-structure-from-motion[C]//Proceedings of 2013 IEEE International Conference on Computer Vision. Sydney: IEEE, 2013: 953-960.
[29]	SHEN Tianwei, ZHU Siyu, FANG Tian, et al. Graph-based consistent matching for structure-frommotion[C]//Proceedngs of 2016 ECCV. Amsterdam: Springer, 2016: 139-155.
[30]	NI Kai, STEEDLY D, DELLAERT F. Out-of-core bundle adjustment for large-scale 3D reconstruction[C]//Proceedings of 2007 IEEE International Conference on Computer Vision. Rio de Janeiro: IEEE, 2007: 1-8.
[31]	AGARWAL S, FURUKAWA Y, SNAVELY N, et al. Building Rome in a day[J]. Communications of the ACM, 2011, 54(10): 105-112.
[32]	AGARWAL S, MIERLE K. Ceres solver: tutorial & reference[EB/OL]. [2024-02-03]. https://www.helloandroid.cn/android/4.3_r1/download/external/ceres-solver/docs/ceres-solver.pdf.
[33]	AGARWAL S, SNAVELY N, SEITZ S M, et al. Bundle adjustment in the large[C]//Proceedings of 2010 ECCV. Berlin: Springer, 2010: 29-42.
[34]	BELL N, GARLAND M. Implementing sparse matrix-vector multiplication on through put-oriented processors[C]//Proceedings of 2009 Conference on High Performance Computing Networking, Storage and Analysis. Portland Oregon: ACM Press, 2009: 1-11.
[35]	SAAD Y. Sparskit: a basic tool kit for sparse computations[EB/OL]. [2024-02-04]. https://www-users.cse.umn.edu/~saad/software/SPARSKIT/.
[36]	ZHENG Maoteng, ZHANG Yongjun, ZHOU Shunping, et al. Bundle block adjustment of large-scale remote sensing data with block-based sparse matrix compression combined with preconditioned conjugate gradient[J]. Computers & Geosciences, 2016, 92: 70-78.
[37]	ZHENG Maoteng, ZHANG Fayong, ZHU Junfeng, et al. A fast and accurate bundle adjustment method for very large-scale data[J]. Computers & Geosciences, 2020, 142: 104539.
[38]	BYRÖD M, ÅSTRÖM K. Bundle adjustment using conjugate gradients with multiscale preconditioning[C]//Proceedings of 2009 British Machine Vision Conference. London: British Machine Vision Association, 2009.
[39]	BYROD M, ASTROM K. Conjugate gradient bundle adjustment[C]//Proceedings of 2010 ECCV. Berlin: Springer, 2010: 114-127.

数据集	数据来源	相机数	影像数	物方点数	像点数	稀疏度
Ladybug-1723	公开数据^[33]	1723	1723	156 502	678 718	0.040 2
Venice-1778	公开数据^[33]	1778	1778	993 923	5 001 946	0.082 5
Final-13682	公开数据^[33]	13 682	13 682	4 456 117	28 987 644	0.070 2
SW-20975	无人机数据	5	20 975	31 150 569	166 980 328	0.004 2
JLP-44975	无人机数据	5	44 975	44 379 729	228 467 901	0.002 1
YQC-46405	无人机数据	5	46 405	38 862 849	254 234 253	0.002 1
JZ-49345	无人机数据	5	49 345	41 617 959	218 489 728	0.001 4
XS-61729	无人机数据	95	61 729	55 545 104	267 117 022	0.001 0
DG-71132	无人机数据	5	71 132	87 134 159	385 107 892	0.000 9
NM-85513	无人机数据	50	85 513	101 149 520	638 272 989	0.001 1
MCZ-86607	无人机数据	8	86 607	98 685 808	588 743 297	0.001 0
WQ-91700	无人机数据	60	91 700	93 622 588	535 230 410	0.000 8
DaPu-133350	无人机数据	10	133 350	8 319 094	60 939 241	0.000 4
HM-407470	无人机数据	35	407 470	352 798 750	1 790 563 849	0.000 2
AJH-442300	无人机数据	35	442 300	112 769 192	1 500 899 038	0.000 3
DG-1181860	无人机数据	114	1 181 860	1 016 725 921	5 084 023 410	0.000 079
Syn1-5000000	模拟数据	2	5 000 000	404 947 456	2 839 153 207	0.000 003
Syn2-10000000	模拟数据	2	10 000 000	809 963 105	5 836 771 022	0.000 001

数据集	Ceres			PBA			DeepLM			MegBA			本文方法
数据集	内存/GB	时间/s	精度/像素	内存/GB	时间/s	精度/像素	内存/GB	时间/s	精度/像素	内存/GB	时间/s	精度/像素	内存/GB	时间/s	精度/像素
Ladybug	0.52	46.7	1.14	0.3	12.3	2.22	2.1	3.9	1.12	1.6	0.77	0.56	0.06	15.6	1.12
Venice	3.68	1992	0.66	—		—	6.2	24.4	0.66	13.6	11.9	0.33	0.27	69.7	0.67
Final	16.8	3897	1.59	11.9	340	3.0	14.89	149	1.50	89.7	22.6	0.75	4.93	906.3	1.24

数据集	M_t/GB	M_r/GB	M_u/GB	迭代次数	时间/h	精度/像素
SW-20975	6.3	0.53	1.21	6	0.44	1.29
JLP-44975	8.7	1.21	2.22	4	0.48	1.37
YQC-46405	9.1	1.37	2.44	7	1.10	0.89
JZ-49345	8.3	0.69	1.60	6	0.62	1.29
XS-61729	10.5	0.91	2.06	6	0.66	1.05
DG-71132	15.5	1.39	3.10	5	0.74	1.24
NM-85513	23.0	2.46	5.04	6	2.72	1.22
MCZ-86607	21.6	2.22	4.63	7	2.65	0.69
WQ-91700	19.9	2.00	4.22	5	1.59	1.24
DaPu-133350	2.1	1.81	2.23	6	0.23	1.45
HM-407470	69	9.72	17.73	6	4.60	1.27
AJH-442300	46.3	16.18	22.64	6	10.50	1.28
DG-1181860	197	28.22	51.15	6	12.73	1.23
Syn1-5000000	99.9	20.84	33.52	3	3.68	1.15
Syn2-10000000	204	41.70	67.48	3	7.72	1.17