一种快速有效的大数据区域网平差方法

doi:10.11947/j.AGCS.2017.20160293

测绘学报 ›› 2017, Vol. 46 ›› Issue (2): 188-197.doi: 10.11947/j.AGCS.2017.20160293

一种快速有效的大数据区域网平差方法

郑茂腾¹, 张永军², 朱俊峰³, 熊小东³, 周顺平¹

1. 中国地质大学(武汉)国家地理信息系统工程技术研究中心, 湖北武汉 430074;
2. 武汉大学遥感信息工程学院, 湖北武汉 430079;
3. 北京中测智绘有限责任公司, 北京 100830

收稿日期:2016-07-26 修回日期:2016-11-09 出版日期:2017-02-20 发布日期:2017-03-07
作者简介:郑茂腾(1987-),男,博士,讲师,研究方向为航空航天摄影测量,计算机视觉。E-mail:tengve@163.com
基金资助:
国家自然科学基金（41601502；41571434）；中国博士后科学基金面上项目（2015M572224）；中央高校基本科研业务费专项资金（CUG160838）

A Fast and Effective Block Adjustment Method with Big Data

ZHENG Maoteng¹, ZHANG Yongjun², ZHU Junfeng³, XIONG Xiaodong³, ZHOU Shunping¹

1. National Engineering Research Center for Geographic Information System, China University of Geosciences, Wuhan 430074, China;
2. School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China;
3. Smart Mapping Technology Inc., Beijing 100830, China

Received:2016-07-26 Revised:2016-11-09 Online:2017-02-20 Published:2017-03-07
Supported by:
The National Natural Science Foundation of China(Nos. 41601502,41571434),The China Postdoctoral Science Foundation(No. 2015M572224),The Fundamental Research Funds for the Central Universities(No. CUG160838)

摘要/Abstract

摘要： 针对摄影测量影像来源多样化、复杂化、大数据化等趋势，传统区域网平差算法在应对当前复杂多变的数据来源，矩阵排列毫无规律的法方程结构以及大数据量带来的高内存需求和低计算效率等问题上，遇到了前所未有的挑战，为了解决上述难题，本文引入了预条件共轭梯度法以及不精确牛顿解法求解区域网平差过程中的法方程，同时使用一种块状法方程系数矩阵压缩存储格式，构建了全新的区域网平差技术流程。本文方法避免了直接对法方程系数矩阵的求逆，压缩了法方程系数矩阵所需的内存空间，使得本文算法比传统算法所需计算机内存空间大幅减少，平差计算速度明显提升，同时保证了计算精度与传统方法相当。初步试验证明，本文方法对4500张影像、近900万像点数据的平差计算在普通电脑上仅需要约15 min，且计算精度达到子像素级。

关键词: 区域网平差, 预条件共轭梯度, 不精确牛顿解, 稀疏矩阵压缩, 大数据

Abstract: To deal with multi-source, complex and massive data in photogrammetry, and solve the high memory requirement and low computation efficiency of irregular normal equation caused by the randomly aligned and large scale datasets, we introduce the preconditioned conjugate gradient combined with inexact Newton method to solve the normal equation which do not have strip characteristics due to the randomly aligned images. We also use an effective sparse matrix compression format to compress the big normal matrix, a brand new workflow of bundle adjustment is developed. Our method can avoid the direct inversion of the big normal matrix, the memory requirement of the normal matrix is also decreased by the proposed sparse matrix compression format. Combining all these techniques, the proposed method can not only decrease the memory requirement of normal matrix, but also largely improve the efficiency of bundle adjustment while maintaining the same accuracy as the conventional method. Preliminary experiment results show that the bundle adjustment of a dataset with about 4500 images and 9 million image points can be done in only 15 minutes while achieving sub-pixel accuracy.

Key words: block adjustment, preconditioned conjugate gradient, inexact Newton method, sparse matrix compressing, big data

中图分类号:

P237

郑茂腾, 张永军, 朱俊峰, 熊小东, 周顺平. 一种快速有效的大数据区域网平差方法[J]. 测绘学报, 2017, 46(2): 188-197.

ZHENG Maoteng, ZHANG Yongjun, ZHU Junfeng, XIONG Xiaodong, ZHOU Shunping. A Fast and Effective Block Adjustment Method with Big Data[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(2): 188-197.

参考文献

[1] 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.
[2] 陈驰, 杨必胜, 彭向阳. 低空UAV激光点云和序列影像的自动配准方法[J]. 测绘学报, 2015, 44(5):518-525. DOI:10.11947/j.AGCS.2015.20130558. CHEN Chi, YANG Bisheng, PENG Xiangyang. Automatic Registration of Low Altitude UAV Sequent Images and Laser Point Clouds[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(5):518-525. DOI:10.11947/j.AGCS.2015.20130558.
[3] 闫利, 费亮, 叶志云, 等. 大范围倾斜多视影像连接点自动提取的区域网平差法[J]. 测绘学报, 2016, 45(3):310-317. DOI:10.11947/j.AGCS.2016.20140673. YAN Li, FEI Liang, YE Zhiyun, et al. Automatic Tie-points Extraction for Triangulation of Large-scale Oblique Multi-view Images[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(3):310-317. DOI:10.11947/j.AGCS.2016.20140673.
[4] 季顺平, 史云. 车载全景相机的影像匹配和光束法平差[J]. 测绘学报, 2013, 42(1):94-100, 107. JI Shunping, SHI Yun. Image Matching and Bundle Adjustment Using Vehicle-based Panoramic Camera[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(1):94-100, 107.
[5] 李德仁. 展望大数据时代的地球空间信息学[J]. 测绘学报, 2016, 45(4):379-384. 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:10.11947/j.AGCS.2016.20160057.
[6] 王祥, 张永军, 黄山, 等. 旋转多基线摄影光束法平差法方程矩阵带宽优化[J]. 测绘学报, 2016, 45(2):170-177. 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:10.11947/j.AGCS.2016.20150282.
[7] 林诒勋. 稀疏矩阵计算中的带宽最小化问题[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.
[8] GIBBS N E, POOLE JR 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.
[9] 郑志镇, 李尚健, 李志刚. 稀疏矩阵带宽减小的一种算法[J]. 华中理工大学学报, 1998, 26(1):43-45. ZHENG Zhizhen, LI Shangjian, LI Zhigang. A New Algorithm for Reducing Bandwidth of Sparse Matrix[J]. Journal of Huazhong University of Science & Technology, 1998, 26(1):43-45.
[10] FRADSEN P E, JONASSON K, NIELSEN H B, et al. Unconstrained Optimization[M/OL]. 3rd ed. Denmark:Informatics and Mathematical Modelling, Technical University of Denmark, 2004. http://www.imm.dtu.dk/courses/02611/uncon.pdf.
[11] HESTENES M R, STIEFEL E. Methods of Conjugate Gradients for Solving Linear Systems[J]. Journal of Research of the National Bureau of Standards, 1952, 49(6):409-436.
[12] AGARWAL S, SNAVELY N, SEITZ S M, et al. Bundle Adjustment in the Large[M]//DANIILIDIS K, MARAGOS P, PARAGIOS N. Computer Vision-ECCV 2010. Berlin Heidelberg:Springer, 2010:29-42.
[13] AGARWAL S, FURUKAWA Y, SNAVELY N, et al. Building Rome in a Day[J]. Communications of the ACM, 2011, 54(10):105-112.
[14] BYRÖ D M, ÅSTRÖ M K. Conjugate Gradient Bundle Adjustment[M]//DANIILIDIS K, MARAGOS P, PARAGIOS N. Computer Vision-ECCV 2010. Berlin Heidelberg:Springer, 2010, 6312:114-127.
[15] JIAN Y D, BALCAN D C, DELLAERT F. Generalized Subgraph Preconditioners for Large-scale Bundle Adjustment[C]//Proceedings of IEEE International Conference on Computer Vision. Barcelona:IEEE, 2011:295-302.
[16] BRU R, MARÍN J, MAS J, et al. Balanced Incomplete Factorization[J]. SIAM Journal on Scientific Computing, 2008, 30(5):2302-2318.
[17] BYRÖ D M, ÅSTRÖ M K. Bundle Adjustment using Conjugate Gradients with Multiscale Preconditioning[C]//Proceedings of 2009 British Machine Vision Conference. London:BMVC, 2009.
[18] 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.
[19] WU Changchang, AGARWAL S, CURLESS B, et al. Multicore Bundle Adjustment[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Providence, RI:IEEE, 2011:3057-3064.
[20] BELL N, GARLAND M. Implementing Sparse Matrix-Vector Multiplication on Throughput-Oriented Processors[C]//Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis. Portland, OR:IEEE, 2009:1-11.
[21] SAAD Y. Iterative Methods for Sparse Linear Systems[M]. 2nd ed. Philadelphia, PA:SIAM, 2003.
[22] GRIMES R G, KINCAID D R, YOUNG D M. ITPACK 2.0 User's Guide[R]. Technical Report CNA-150. Austin, TX:Center for Numerical Analysis, University of Texas, 1980.
[23] NIELSEN H B, Damping Parameter in Marquardt's Method[R]. Technical Report IMM-REP-1999-05. Denmark:Technical University of Denmark, 1999.

一种快速有效的大数据区域网平差方法

A Fast and Effective Block Adjustment Method with Big Data

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张兵, 杨晓梅, 高连如, 孟瑜, 孙显, 肖晨超, 倪丽. 遥感大数据智能解译的地理学认知模型与方法[J]. 测绘学报, 2022, 51(7): 1398-1415.
[2]	张力, 刘玉轩, 孙洋杰, 蓝朝桢, 艾海滨, 樊仲藜. 数字航空摄影三维重建理论与技术发展综述[J]. 测绘学报, 2022, 51(7): 1437-1457.
[3]	刘耀林, 刘启亮, 邓敏, 石岩. 地理大数据挖掘研究进展与挑战[J]. 测绘学报, 2022, 51(7): 1544-1560.
[4]	王家耀, 武芳, 闫浩文. 大变化时代的地图学[J]. 测绘学报, 2022, 51(6): 829-842.
[5]	唐炉亮, 赵紫龙, 杨雪, 阚子涵, 任畅, 高婕, 李朝奎, 张霞, 李清泉. 大数据环境下道路场景高时空分辨率众包感知方法[J]. 测绘学报, 2022, 51(6): 1070-1090.
[6]	李德仁, 徐小迪, 邵振峰. 论万物互联时代的地球空间信息学[J]. 测绘学报, 2022, 51(1): 1-8.
[7]	李志林, 刘万增, 徐柱, 遆鹏, 高培超, 闫超德, 林艳, 李然, 陆辰妮. 时空数据地图表达的基本问题与研究进展[J]. 测绘学报, 2021, 50(8): 1033-1048.
[8]	伍洋, 张永生, 李凯, 于英, 赖广陵. 附加视线向量修正的卫星影像区域网平差[J]. 测绘学报, 2021, 50(1): 85-96.
[9]	夏吉喆, 周颖, 李珍, 李帆, 乐阳, 程涛, 李清泉. 城市时空大数据驱动的新型冠状病毒传播风险评估——以粤港澳大湾区为例[J]. 测绘学报, 2020, 49(6): 671-680.
[10]	韩杰, 陶醉, 谢勇, 刘其悦, 石宏斌. 顾及多积分时间特性的GF-4卫星PMS传感器交叉辐射定标[J]. 测绘学报, 2020, 49(10): 1311-1320.
[11]	曹辉, 陶鹏杰, 李海鸿, 张祖勋. DEM约束的卫星影像定位法[J]. 测绘学报, 2020, 49(1): 79-91.
[12]	杨必胜, 董震. 点云智能研究进展与趋势[J]. 测绘学报, 2019, 48(12): 1575-1585.
[13]	王培晓, 张恒才, 王海波, 吴升. ST-CFSFDP:快速搜索密度峰值的时空聚类算法[J]. 测绘学报, 2019, 48(11): 1380-1390.
[14]	唐炉亮, 阚子涵, 任畅, 张霞, 李清泉. 利用GPS轨迹的转向级交通拥堵精细分析[J]. 测绘学报, 2019, 48(1): 75-85.
[15]	王晋, 张勇, 张祖勋, 李晓, 陶鹏杰, 宋孟肖. ICESat激光高程点辅助的天绘一号卫星影像立体区域网平差[J]. 测绘学报, 2018, 47(3): 359-369.