A Fast and Effective Block Adjustment Method with Big Data

doi:10.11947/j.AGCS.2017.20160293

Abstract

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

CLC Number:

P237

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.

References

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