GPU Parallel Bundle Block Adjustment

doi:10.11947/j.AGCS.2017.20160636

Abstract

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

CLC Number:

P237

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

References

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