GPU并行区域网平差

doi:10.11947/j.AGCS.2017.20160636

测绘学报 ›› 2017, Vol. 46 ›› Issue (9): 1193-1201.doi: 10.11947/j.AGCS.2017.20160636

GPU并行区域网平差

郑茂腾¹, 周顺平¹, 熊小东², 朱俊峰²

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

收稿日期:2016-12-22 修回日期:2017-08-14 出版日期:2017-09-20 发布日期:2017-10-12
通讯作者: 周顺平 E-mail:zhoushunping@mapgis.com
作者简介:郑茂腾(1987-),男,博士,副研究员,研究方向为航空航天摄影测量与计算机视觉。E-mail:tengve@163.com
基金资助:
国家自然科学基金（41601502）；中国博士后科学基金面上项目（2015M572224）；中央高校基本科研业务费专项资金（CUG160838；CUG170664）

GPU Parallel Bundle Block Adjustment

ZHENG Maoteng¹, ZHOU Shunping¹, XIONG Xiaodong², ZHU Junfeng²

1. National Engineering Research Center for Geographic Information System, China University of Geosciences, Wuhan 430074, China;
2. Smart Mapping Technology Lnc., Beijing 100830, China

Received:2016-12-22 Revised:2017-08-14 Online:2017-09-20 Published:2017-10-12
Supported by:
The National Natural Science Foundation of China (No. 41601502);The China Postdoctoral Science Foundation (No. 2015M572224);The Fundamental Research Funds for the Central Universities(Nos. CUG160838;CUG170664)

摘要/Abstract

摘要： 为了进一步解决大数据量带来的平差效率低下的问题，引入GPU并行计算技术，同时使用预条件共轭梯度法以及不精确牛顿解法求解区域网平差过程中的法方程，构建了适用于GPU并行计算的全新的区域网平差技术流程。本文方法避免了存储法方程系数矩阵，而是在需要的时候实时的计算该矩阵，使得本文算法相较于传统的算法所需的计算机内存空间大幅减少（仅需要存储平差原始数据即可），平差计算速度明显提升，同时计算精度与传统方法相当。初步试验证明，本文的方法在普通电脑上仅需要约1.5min即可完成对4500张影像、近900万像点数据的平差计算，且计算精度达到子像素级。

关键词: GPU并行计算, 区域网平差, 预条件共轭梯度, 不精确牛顿解, 大数据

Abstract: To deal with massive data in photogrammetry, we introduce the GPU parallel computing technology. The preconditioned conjugate gradient and inexact Newton method are also applied to decrease the iteration times while solving the normal equation. A brand new workflow of bundle adjustment is developed to utilize GPU parallel computing technology. Our method can avoid the storage and inversion of the big normal matrix, and compute the normal matrix in real time. The proposed method can not only largely decrease the memory requirement of normal matrix, but also largely improve the efficiency of bundle adjustment. It also achieves 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 1.5 minutes while achieving sub-pixel accuracy.

Key words: GPU parallel computing, bundle adjustment, preconditioned conjugate gradient, inexact Newton method, big data

中图分类号:

P237

郑茂腾, 周顺平, 熊小东, 朱俊峰. GPU并行区域网平差[J]. 测绘学报, 2017, 46(9): 1193-1201.

ZHENG Maoteng, ZHOU Shunping, XIONG Xiaodong, ZHU Junfeng. GPU Parallel Bundle Block Adjustment[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(9): 1193-1201.

参考文献

[1] 李德仁. 展望大数据时代的地球空间信息学[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.
[2] 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.
[3] 陈驰, 杨必胜, 彭向阳. 低空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.
[4] 闫利, 费亮, 叶志云, 等. 大范围倾斜多视影像连接点自动提取的区域网平差法[J]. 测绘学报, 2016, 45(3):310-317, 338. 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, 338. DOI:10.11947/j.AGCS.2016.20140673.
[5] 季顺平, 史云. 车载全景相机的影像匹配和光束法平差[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.
[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. Band Width 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(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 & Technology, 1998, 26(12):43-45.
[10] 郑茂腾, 张永军, 朱俊峰, 等. 一种快速有效的大数据区域网平差方法[J]. 测绘学报, 2017, 46(2):188-197. 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:10.11947/j.AGCS.2017.20160293.
[11] 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.
[12] LIU Xin, GAO Wei, HU Zhanyi. Hybrid Parallel Bundle Adjustment for 3D Scene Reconstruction with Massive Points[J]. Journal of Computer Science and Technology, 2012, 27(6):1269-1280.
[13] 佟国峰, 蒋昭炎, 叶柠, 等. 大场景三维重建中多核并行捆集调整算法[J]. 控制与决策, 2013, 28(29):1403-1408. TONG Guofeng, JIANG Zhaoyan, YE Ning. Multi-core Bundle Adjustment Algorithm Using Parallel Processing in Large-scale 3D Scene Reconstruction[J]. Control and Decision, 2013, 28(29):1403-1408.
[14] AGARWAL S, SNAVELY N, SEITZ S M, et. al. Bundle Adjustment in the Large[C]//DANⅡLIDIS K, MARAGOS P, PARAGIOS N. Computer Vision-ECCV 2010. Berlin Heidelberg:Springer, 2010:29-42.
[15] AGARWAL S, FURUKAWA Y, SNAVELY N, et al. Building Rome in a Day[J]. Communications of the ACM, 2011, 54(10):105-112.
[16] LI Ruipeng, SAAD Y. GPU-accelerated Preconditioned Iterative Linear Solvers[J]. The Journal of Supercomputing, 2013, 63(2):443-466.
[17] WU Changchang. Multicore Bundle Adjustment[C]//Proceedings of 2011 IEEE Conference on Computer Vision and Pattern Recognition. Colorado Springs, CO:IEEE, 2011:3057-3064.
[18] CHOUDHARY S, GUPTA S, NARAYANAN P J. Practical Time Bundle Adjustment for 3D Reconstruction on the GPU[C]//Proceedings of the 11th European Conference on Trends and Topics in Computer Vision-Volume Part Ⅱ. Heraklion, Crete, Greece:Springer, 2010:423-435.
[19] SÁNCHEZ J R, ÁLVAREZ H, BORRO D. Towards Real Time 3D Tracking and Reconstruction on a GPU Using Monte Carlo Simulations[C]//Proceedings of the 9th IEEE International Symposium on Mixed and Augmented Reality. Seoul, South Korea:IEEE, 2010:185-192.
[20] BENNER P, EZZATTI P, KRESSNER D, et al. A Mixed-Precision Algorithm for the Solution of Lyapunov Equations on Hybrid CPU-GPU Platforms[J]. Parallel Computing Archive, 2011, 37(8):439-450.
[21] BHASKARAN-NAIR K, MA Wenjing, KRISHNAMOORTHY S, et al. Noniterative Multireference Coupled Cluster Methods on Heterogeneous CPU-GPU Systems[J]. Journal of Chemical Theory and Computation, 2013, 9(4):1949-1957.
[22] CHAI Jun, SU Huayou, WEN Mei, et al. Resource-efficient Utilization of CPU/GPU-based Heterogeneous Supercomputers for Bayesian Phylogenetic Inference[J]. The Journal of Supercomputing, 2013, 66(1):364-380.
[23] TAN Y S, LEE B S, HE Bingsheng, et al. A Map-reduce Based Framework for Heterogeneous Processing Element Cluster Environments[C]//Proceedings of the 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid). Ottawa, ON, Canada:IEEE, 2012:57-64.
[24] WEN Mei, SU Huayou, WEI Wenjie, et al. Using 1000+ GPUs and 10000+ CPUs for Sedimentary Basin Simulations[C]//Proceedings of 2012 IEEE International Conference on Cluster Computing (CLUSTER). Beijing, China:IEEE, 2012:27-35.
[25] NEWCOMBE R A, LOVEGROVE S J, DAVISON A J. DTAM:Dense Tracking and Mapping in Real-time[C]//Proceedings of 2011 IEEE International Conference on Computer Vision. Barcelona, Spain:IEEE, 2011:2320-2327.
[26] ACOSTA A, CORUJO R, BLANCO V, et al. Dynamic Load Balancing on Heterogeneous Multicore/MultiGPU Systems[C]//Proceedings of 2010 International Conference on High Performance Computing and Simulation (HPCS). Caen, France:IEEE, 2010:467-476.
[27] AGULLEIRO J I, VÁZQUEZ F, GARZÓN E M, et al. Hybrid Computing:CPU+ GPU Co-processing and Its Application to Tomographic Reconstruction[J]. Ultramicroscopy, 2012(115):109-114.
[28] AGULLO E, AUGONNET C, DONGARRA J, et al. QR Factorization on a Multicore Node Enhanced with Multiple GPU Accelerators[C]//Proceedings of 2011 IEEE International Parallel & Distributed Processing Symposium. Anchorage, AK:IEEE, 2011:932-943.
[29] HNSCH R, DRUDE I, HELLWICH O. Modern Methods of Bundle Adjustment on the GPU[C]//ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume Ⅲ-3, 2016 XXⅢ ISPRS Congress. Prague, Czech Republic:Copernicus Publications, 2016.

GPU并行区域网平差

GPU Parallel Bundle Block Adjustment

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.