A Self-calibration Bundle Adjustment Algorithm Based on Block Matrix Cholesky Decomposition Technology

doi:10.11947/j.JGGS.2023.0102

Abstract

Abstract:

In this study, the problem of bundle adjustment was revisited, and a novel algorithm based on block matrix Cholesky decomposition was proposed to solve the thorny problem of self-calibration bundle adjustment. The innovation points are reflected in the following aspects: ① The proposed algorithm is not dependent on the Schur complement, and the calculation process is simple and clear; ② The complexities of time and space tend to O(n) in the context of world point number is far greater than that of images and cameras, so the calculation magnitude and memory consumption can be reduced significantly; ③ The proposed algorithm can carry out self-calibration bundle adjustment in single-camera, multi-camera, and variable-camera modes; ④ Some measures are employed to improve the optimization effects. Experimental tests showed that the proposed algorithm has the ability to achieve state-of-the-art performance in accuracy and robustness, and it has a strong adaptability as well, because the optimized results are accurate and robust even if the initial values have large deviations from the truth. This study could provide theoretical guidance and technical support for the image-based positioning and 3D reconstruction in the fields of photogrammetry, computer vision and robotics.

Key words: bundle adjustment; self-calibration; block matrix; Cholesky decomposition

Huasheng SUN,Yuan ZHANG. A Self-calibration Bundle Adjustment Algorithm Based on Block Matrix Cholesky Decomposition Technology[J]. Journal of Geodesy and Geoinformation Science, 2023, 6(1): 11-30.

Figures/Tables 18

Fig.1

Tab.1

Tab.2

Tab.3

Fig.2

Tab.4

Fig.3

Tab.5

Tab.6

Tab.7

Errors between the absolute orientated result and the simulated truth"

Image	$e X s$	$e Y s$	$e Z s$	e_ω/(°)	e_φ/(°)	e_κ/(°)
1	-6.3e-6	2.7e-6	-2.9e-5	1.2e-5	2.0e-7	-2.2e-6
2	-1.1e-6	1.7e-6	-3.2e-5	1.1e-5	5.5e-8	-9.3e-8
3	3.9e-6	1.9e-6	-2.9e-5	1.2e-5	7.8e-7	2.4e-6
4	-5.8e-6	6.6e-6	-2.3e-5	1.1e-5	-9.5e-7	-2.4e-6
5	-1.5e-6	6.6e-6	-2.5e-5	1.1e-5	-6.0e-7	-4.1e-9
6	2.4e-6	5.9e-6	-2.4e-5	1.1e-5	-2.7e-7	2.5e-6
7	-5.0e-6	8.7e-6	-1.9e-5	1.8e-5	-7.3e-7	-3.7e-6
8	-2.0e-6	8.4e-6	-1.8e-5	1.8e-5	-1.2e-6	1.7e-8
9	4.8e-7	7.9e-6	-1.7e-5	1.8e-5	-7.4e-7	3.9e-6

Tab.7

Fig.4

Tab.8

Fig.5

Tab.9

Fig.6

Fig.7

Fig.8

Fig.9

References 29

[1]	BROWN D C. A solution to the general problem of multiple station analytical stereotriangulation[R]. Florida: Patrick Air Force Base, 1958.
[2]	WANG Zhizhuo. Principle of photogrammetry[M]. Beijing: Surveying and Mapping Press, 1979.
[3]	LI Deren. A posteriori weight estimation in self—calibrating bundle block adjustment[J]. Geomatics and Information Science of Wuhan University, 1982, 7(1): 16-24.
[4]	ZHAN Zongqian, ZHANG Zuxun, ZHANG Jianqing. A fast algorithm of bundle adjustment based on sparse matrix technology[J]. Bulletin of Surveying and Mapping, 2006(12): 5-8.
[5]	LIU Jun, WANG Donghong, ZHANG Li, et al. GPS/IMU supported bundle adjustment of airborne three line images[J]. Journal of Geomatics Science and Technology, 2009, 26(1): 36-40.
[6]	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.
[7]	LI Deren, XIAO Xiongwu, GUO Bingxuan, et al. Oblique image based automatic aerotriangulation and its application in 3D city model reconstruction[J]. Geomatics and Information Science of Wuhan University, 2016, 41(6): 711-721.
[8]	ZHANG Chunsen, ZHU Shihuan, ZANG Yufu, et al. GPS-supported bundle adjustment method of UAV by considering exposure delay[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(5): 565-572.
[9]	LIU Chubin, FAN Dazhao, WU Yongjin, et al. Self-calibration bundle block adjustment for ALOS PRISM imagery[J]. Journal of Geomatics Science and Technology, 2012, 29(3): 196-199, 203.
[10]	OU Yu, LEI Rong, JI Song, et al. An orientation image based on self-calibration bundle block adjustment model for ground geometric calibration method[J]. Engineering of Surveying and Mapping, 2012, 21(5): 8-12.
[11]	XIA Zemin, LI Zhongwei, ZHONG Kai. Camera calibration optimization with constrained sparse bundle adjustment[J]. Opto-Electronic Engineering, 2015, 42(5): 13-19.
[12]	XUE Junpeng, HU Yanfei, WANG Yixuan. Study on the initial value factors of influencing the accuracy of regional network bundle adjustment[J]. Optical Technique, 2019, 45(2): 181-187.
[13]	TRIGGS B, MCLAUCHLAN P F, HARTLEY R I, et al. Bundle adjustment—a modern synthesis[C]//Proceedings of International Workshop on Vision Algorithms. Corfu: Springer, 2000: 298-372.
[14]	SHAN J. A brief history and essentials of bundle adjustment[J]. Geomatics and Information Science of Wuhan University, 2018, 43(12): 1797-1810.
[15]	BYRÖD M, ÅSTRÖM K. Bundle adjustment using conjugate gradients with multiscale preconditioning[C]//Proceedings of British Machine Vision Conference. London: BMVC, 2009.
[16]	AGARWAL S, SNAVELY N, SEITZ S M, et al. Bundle adjustment in the large[C]//Proceedings of the 11th European Conference on Computer Vision. Heraklion: Springer, 2010: 29-42.
[17]	WU Changchang, AGARWAL S, CURLESS B, et al. Multicore bundle adjustment[C]//Proceedings of CVPR 2011. Colorado Springs: IEEE, 2011: 3057-3064.
[18]	LOURAKIS M I A, ARGYROS A A. SBA: a software package for generic sparse bundle adjustment[J]. ACM Transactions on Mathematical Software, 2009, 36(1): 2.
[19]	ZHOU Weijun, CHEN Xiaojun. Global convergence of a new hybrid Gauss-Newton structured BFGS method for nonlinear least squares problems[J]. SIAM Journal on Optimization, 2010, 20(5): 2422-2441. doi: 10.1137/090748470
[20]	LI Yanyan, FAN Shiyue, SUN Yanbiao, et al. Bundle adjustment method using sparse BFGS solution[J]. Remote Sensing Letters, 2018, 9(8): 789-798. doi: 10.1080/2150704X.2018.1480072
[21]	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. doi: 10.1007/s11390-012-1303-3
[22]	ZHAO Liang, HUANG Shoudong, SUN Yanbiao, et al. Parallax BA: bundle adjustment using parallax angle feature parametrization[J]. The International Journal of Robotics Research, 2015, 34(4-5): 493-516. doi: 10.1177/0278364914551583
[23]	ZHENG Maoteng, ZHOU Shunping, ZHU Xiaodong, et al. A new GPU bundle adjustment method for large-scale data[J]. Photogrammetric Engineering & Remote Sensing, 2017, 83(9): 633-641.
[24]	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.
[25]	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.
[26]	ZHANG Runze, ZHU Siyu, SHEN Tian, et al. Distributed very large scale bundle adjustment by global camera consensus[C]//Proceedings of 2017 IEEE International Conference on Computer Vision. Venice: IEEE, 2017: 29-38.
[27]	TOUCHETTE S, GUEAIEB W, LANTEIGNE E. Efficient Cholesky factor recovery for column reordering in simultaneous localisation and mapping[J]. Journal of Intelligent and Robotic Systems, 2016, 84: 859-875. doi: 10.1007/s10846-016-0367-7
[28]	HARTLEY R, ZISSERMAN A. Multiple view geometry in computer vision[M]. 2nd ed. London: Cambridge University Press, 2003.
[29]	BROWN D C. Close-range camera calibration[J]. Photogrammetric Engineering, 1971, 37(8): 855-866.

Camera serial number k	Total image point number in each group n_k	Image serial number j	Total image point number on each image n_j	Visible world point serial number i	Index number idx	Jacobian matrix of camera parameters A_ij	Jacobian matrix of world points B_ij	Weight matrix P_ij	Residual r_ij
1	6	1	3	1	1	A₁₁	B₁₁	P₁₁	r₁₁
				2	2	A₂₁	B₂₁	P₂₁	r₂₁
				3	3	A₃₁	B₃₁	P₃₁	r₃₁
		2	3	1	4	A₁₂	B₁₂	P₁₂	r₁₂
				2	5	A₂₂	B₂₂	P₂₂	r₂₂
				4	6	A₄₂	B₄₂	P₄₂	r₄₂
2	6	3	3	3	7	A₃₃	B₃₃	P₃₃	r₃₃
				4	8	A₄₃	B₄₃	P₄₃	r₄₃
				5	9	A₅₃	B₅₃	P₅₃	r₅₃
		4	3	2	10	A₂₄	B₂₄	P₂₄	r₂₄
				4	11	A₄₄	B₄₄	P₄₄	r₄₄
				5	12	A₅₄	B₅₄	P₅₄	r₅₄

Camera serial number k	Visible world point serial number i	Frequency of world point i on the images captured by camera kn_k₍_i₎	Image serial number j	Index number idx	Jacobian matrix of camera parameters A_ij	Jacobian matrix of world points B_ij	Weight matrix P_ij	Residual r_ij
1	1	2	1	1	A₁₁	B₁₁	P₁₁	r₁₁
	1	2	2	4	A₁₂	B₁₂	P₁₂	r₁₂
	2	2	1	2	A₂₁	B₂₁	P₂₁	r₂₁
	2	2	2	5	A₂₂	B₂₂	P₂₂	r₂₂
	3	1	1	3	A₃₁	B₃₁	P₃₁	r₃₁
	4	1	2	6	A₄₂	B₄₂	P₄₂	r₄₂
2	2	1	4	10	A₂₄	B₂₄	P₂₄	r₂₄
	3	1	3	7	A₃₃	B₃₃	P₃₃	r₃₃
	4	2	3	8	A₄₃	B₄₃	P₄₃	r₄₃
	4	2	4	11	A₄₄	B₄₄	P₄₄	r₄₄
	5	2	3	9	A₅₃	B₅₃	P₅₃	r₅₃
	5	2	4	12	A₅₄	B₅₄	P₅₄	r₅₄

Visible world point serial number i	Frequency of world point i on all images n_i	Image serial number j	Camera serial number k	Index number idx	Jacobian matrix of camera parameters A_ij	Jacobian matrix of world points B_ij	Weight matrix P_ij	Residual r_ij
1	2	1	1	1	A₁₁	B₁₁	P₁₁	r₁₁
1	2	2	1	4	A₁₂	B₁₂	P₁₂	r₁₂
2	3	1	1	2	A₂₁	B₂₁	P₂₁	r₂₁
		2	1	5	A₂₂	B₂₂	P₂₂	r₂₂
		4	2	10	A₂₄	B₂₄	P₂₄	r₂₄
3	2	1	1	3	A₃₁	B₃₁	P₃₁	r₃₁
3	2	3	2	7	A₃₃	B₃₃	P₃₃	r₃₃
4	3	2	1	6	A₄₂	B₄₂	P₄₂	r₄₂
		3	2	8	A₄₃	B₄₃	P₄₃	r₄₃
		4	2	11	A₄₄	B₄₄	P₄₄	r₄₄
5	2	3	2	9	A₅₃	B₅₃	P₅₃	r₅₃
5	2	4	2	12	A₅₄	B₅₄	P₅₄	r₅₄

k	j	f_x	f_y	x_p	y_p	k₁	k₂	p₁	p₂	X_s	Y_s	Z_s	ω/(°)	φ/(°)	κ/(°)
1	1	2400	2400	1015	1025	2e-8	3e-14	5e-6	4e-6	-80	-80	-505	-15	13	2
	2	2400	2400	1015	1025	2e-8	3e-14	5e-6	4e-6	5	-80	-505	-12	2	1
	3	2400	2400	1015	1025	2e-8	3e-14	5e-6	4e-6	80	-80	-505	-15	-14	3
2	4	2450	2450	1010	1015	3e-8	4e-14	3e-6	5e-6	-80	0	-500	1	15	2
	5	2450	2450	1010	1015	3e-8	4e-14	3e-6	5e-6	5	0	-500	2	1	3
	6	2450	2450	1010	1015	3e-8	4e-14	3e-6	5e-6	80	0	-500	0	-16	3
3	7	2500	2500	1020	1030	1e-8	2e-14	2e-6	4e-6	-80	80	-510	16	15	2
	8	2500	2500	1020	1030	1e-8	2e-14	2e-6	4e-6	5	80	-510	15	1	0
	9	2500	2500	1020	1030	1e-8	2e-14	2e-6	4e-6	80	80	-510	14	-15	1

Data	k	j	f_x	f_y	x_p	y_p	k₁	k₂	p₁	p₂	X_s	Y_s	Z_s	ω /(°)	φ /(°)	κ /(°)
Initial values	1	1	3000	3000	1000	1000	0	0	0	0	-73.71	-70.70	-499.16	-16.08	14.95	1.90
		2	3000	3000	1000	1000	0	0	0	0	13.12	-86.85	-495.81	-10.45	0.17	0.46
		3	3000	3000	1000	1000	0	0	0	0	72.54	-70.59	-501.89	-18.29	-9.50	4.46
	2	4	3000	3000	1000	1000	0	0	0	0	-71.73	9.14	-509.29	3.06	10.34	4.09
		5	3000	3000	1000	1000	0	0	0	0	7.65	-0.29	-493.02	-2.68	0.39	5.55
		6	3000	3000	1000	1000	0	0	0	0	71.95	6.01	-491.32	-2.23	-17.18	0.76
	3	7	3000	3000	1000	1000	0	0	0	0	-84.43	72.84	-506.43	11.46	17.66	3.80
		8	3000	3000	1000	1000	0	0	0	0	5.94	78.44	-504.85	10.97	3.95	1.55
		9	3000	3000	1000	1000	0	0	0	0	89.15	88.31	-505.14	17.23	-18.13	-2.37
Optimized result	1	1	2400	2400	1015	1025	2e-8	3e-14	5e-6	4e-6	-64.54	-63.90	-505.61	-16.53	13.11	2.08
		2	2400	2400	1015	1025	2e-8	3e-14	5e-6	4e-6	7.54	-63.84	-505.78	-13.51	2.12	1.07
		3	2400	2400	1015	1025	2e-8	3e-14	5e-6	4e-6	71.14	-63.80	-505.92	-16.49	-13.89	3.08
	2	4	2450	2450	1010	1015	3e-8	4e-14	3e-6	5e-6	-64.59	4.03	-503.16	-0.52	15.13	2.05
		5	2450	2450	1010	1015	3e-8	4e-14	3e-6	5e-6	7.49	4.09	-503.32	0.49	1.13	3.04
		6	2450	2450	1010	1015	3e-8	4e-14	3e-6	5e-6	71.09	4.14	-503.47	-1.50	-15.87	3.05
	3	7	2500	2500	1020	1030	1e-8	2e-14	2e-6	4e-6	-64.66	71.63	-513.42	14.49	15.14	2.01
		8	2500	2500	1020	1030	1e-8	2e-14	2e-6	4e-6	7.42	71.68	-513.59	13.49	1.14	0.01
		9	2500	2500	1020	1030	1e-8	2e-14	2e-6	4e-6	71.02	71.73	-513.73	12.49	-14.86	1.01