基于LM模型的超大规模影像分布式光束法平差方法

doi:10.11947/j.AGCS.2025.20240142

测绘学报 ›› 2025, Vol. 54 ›› Issue (5): 899-910.doi: 10.11947/j.AGCS.2025.20240142

基于LM模型的超大规模影像分布式光束法平差方法

郑茂腾¹^,²(), 鲁一慧³, 朱俊锋⁴, 曾晓茹⁴, 邱焕斌⁵, 江钰尧¹, 卢星月¹, 渠豪⁴, 陈能成¹()

^1.中国地质大学（武汉）国家地理信息系统工程技术研究中心，湖北　武汉　430078
^2.中国地质大学（武汉）自然资源信息管理与数字孪生工程软件教育部工程研究中心，湖北　武汉　430078
^3.山东省国土测绘院，山东　济南　250012
^4.北京中测智绘科技有限公司，北京　100010
^5.广州建通地理信息集团股份有限公司，广东　广州　510663

收稿日期:2024-04-10 修回日期:2025-04-23 出版日期:2025-06-23 发布日期:2025-06-23
通讯作者: 陈能成 E-mail:tengve@163.com;cnc@whu.edu.cn
作者简介:郑茂腾（1987—），男，博士，副研究员，主要从事航空航天摄影测量、计算机视觉三维重建的理论方法和应用研究。E-mail：tengve@163.com
基金资助:
湖北省自然科学基金(2024AFB680);湖北珞珈实验室重点基金(220100034)

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

Maoteng ZHENG¹^,²(), Yihui LU³, Junfeng ZHU⁴, Xiaoru ZENG⁴, Huanbin QIU⁵, Yuyao JIANG¹, Xingyue LU¹, Hao QU⁴, Nengcheng CHEN¹()

^1.National Engineering Research Center of Geographic Information System, China University of Geosciences, Wuhan 430078, China
^2.Engineering Research Center of Natural Resource Information Management and Digital Twin Engineering Software, Ministry of Education, China University of Geosciences, Wuhan 430078, China
^3.Shandong Provincial Institute of Land Surveying and Mapping, Jinan 250012, China
^4.Smart Mapping Technology, Beijing 100010, China
^5.Jiantong Survey, Guangzhou 510663, China

Received:2024-04-10 Revised:2025-04-23 Online:2025-06-23 Published:2025-06-23
Contact: Nengcheng CHEN E-mail:tengve@163.com;cnc@whu.edu.cn
About author:ZHENG Maoteng (1987—), male, PhD, associate researcher, majors in theoretical methods and application research of aerospace photogrammetry and computer vision 3D reconstruction.　E-mail: tengve@163.com
Supported by:
The Natural Science Foundation of Hubei(2024AFB680);Hubei Luojia Laboratory Foundation(220100034)

摘要/Abstract

摘要：

针对超大规模数据的整体光束法平差问题，本文提出一种基于LM模型的分布式光束法平差方法。为了解决大规模法方程系数矩阵的存储以及求解运算，利用法方程系数矩阵的稀疏块状特性，使用一种块状稀疏矩阵压缩格式（BSMC）对其进行压缩，该格式还支持对法方程系数矩阵的分布式存储和更新。基于上述压缩格式，建立了基于严格LM模型的分布式光束法平差框架，通过对法方程进行分布式构建以及对其他计算复杂度较高的步骤进行并行化设计，实现了对超大规模数据的整体光束法平差。通过对本文方法和国际上同类方法的全面对比试验，初步结果表明，本文方法对内存的需求大幅减少，数据处理容量大幅提升，首次在分布式计算系统上实现对118万张影像的真实数据和1000万张影像的模拟数据（处理的数据量大约是当前基于LM模型最好方法的500倍）的基于LM模型的整体光束法平差。

关键词: 分布式并行, 光束法平差, LM模型, 稀疏矩阵压缩, 预条件共轭梯度

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

中图分类号:

P236

郑茂腾, 鲁一慧, 朱俊锋, 曾晓茹, 邱焕斌, 江钰尧, 卢星月, 渠豪, 陈能成. 基于LM模型的超大规模影像分布式光束法平差方法[J]. 测绘学报, 2025, 54(5): 899-910.

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.

图/表 10

图1

图2

图3

图4

表1

表2

表3

图5

图6

图7

参考文献 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

基于LM模型的超大规模影像分布式光束法平差方法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 39

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王建荣, 杨元喜, 胡燕, 吕源, 杨秀策, 卢学良, 曹彬才. 高分十四号立体测绘卫星无控定位精度初步评估[J]. 测绘学报, 2023, 52(1): 8-14.
[2]	余俊鹏, 吴伟东, 孙佳明, 满益云, 沈刚. 附加傅里叶补偿项的卫星遥感影像RFM平差方法[J]. 测绘学报, 2022, 51(1): 127-134.
[3]	李佳田, 王聪聪, 阿晓荟, 晏玲, 朱志浩, 高鹏. 多向前方交会与单隐层神经网络结合的近景前方交会法[J]. 测绘学报, 2020, 49(6): 736-745.
[4]	王建荣, 王任享, 胡莘. 三线阵影像外方位元素平滑方程自适应光束法平差[J]. 测绘学报, 2018, 47(7): 968-972.
[5]	尚洋, 孙晓亮, 张跃强, 李由, 于起峰. 三维目标位姿跟踪与模型修正[J]. 测绘学报, 2018, 47(6): 799-808.
[6]	郑茂腾, 周顺平, 熊小东, 朱俊峰. GPU并行区域网平差[J]. 测绘学报, 2017, 46(9): 1193-1201.
[7]	张春森, 朱师欢, 臧玉府, 肖雄武, 薛万唱. 顾及曝光延迟的无人机GPS辅助光束法平差方法[J]. 测绘学报, 2017, 46(5): 565-572.
[8]	王任享, 王建荣, 胡莘. 光学卫星摄影无控定位精度分析[J]. 测绘学报, 2017, 46(3): 332-337.
[9]	薛武, 张永生, 赵玲, 于英, 王涛, 李磊. 增量式SFM与POS辅助光束法平差精度比较[J]. 测绘学报, 2017, 46(2): 198-207.
[10]	郑茂腾, 张永军, 朱俊峰, 熊小东, 周顺平. 一种快速有效的大数据区域网平差方法[J]. 测绘学报, 2017, 46(2): 188-197.
[11]	余岸竹, 姜挺, 郭文月, 秦进春, 江刚武. 总体最小二乘用于线阵卫星遥感影像光束法平差解算[J]. 测绘学报, 2016, 45(4): 442-449.
[12]	王任享, 王建荣, 胡莘. 卫星摄影姿态测定系统低频误差补偿[J]. 测绘学报, 2016, 45(2): 127-130.
[13]	王任享, 王建荣, 胡莘. 天绘一号03星定位精度初步评估[J]. 测绘学报, 2016, 45(10): 1135-1139.
[14]	郑顺义,黄荣永,郭宝云,胡堃. 附约束条件的立体相机标定方法[J]. 测绘学报, 2012, 41(6): 877-885.
[15]	王建梅,朱紫阳. 利用已有像控点的多期航空影像光束法区域网联合平差[J]. 测绘学报, 2010, 39(1): 0-82.