40 8 Vol. 40, No. 8 2014 8 ACTA AUTOMATICA SINICA August, 2014 1 1 2.,,,.,.,,,.,.,,,.,,,. DOI,, L-M (Levenberg-Marquardt),,,.., 2014, 40(8): 1601 1611 10.3724/SP.J.1004.2014.01601 Bundle Adjustment for Scenes Containing Planes XIE Yuan-Fan 1 WU Yi-Hong 1 FAN Li-Xin 2 Abstract Bundle adjustment has been considered as one of the most important components in computer vision systems where three-dimensional structures are needed. A general bundle adjustment can optimize the coordinates of space points independently. But for a scene composed of both natural and structured objects, this often leads to an over parametrization the result and which deviates from truth. In this paper, a bundle adjustment with planar constraints and angle constraints is proposed for recovering the structures of environments with planes. By the aid of a new parametrization, the optimization remains an unconstrained non-linear least squares problem even if these two kinds of constraints are added. Experiments show that this new bundle adjustment method with prior knowledge provides an accurate estimation of the structures. Since prior information is added, the dimensionality of the augmented normal equation increases. A sparse solver is used after preconditioning in order to alleviate this problem. Moreover, a graph based angle constraint inference is devised for automatically finding constraints in a greedy manner once all planes are identified. This greedy method can preserve as many angle constraints as possible. Key words Bundle adjustment, 3D reconstruction, Levenberg-Marquardt (L-M) method, sparse solver Citation Xie Yuan-Fan, Wu Yi-Hong, Fan Li-Xin. Bundle adjustment for scenes containing planes. Acta Automatica Sinica, 2014, 40(8): 1601 1611,., 2. (Structure from motion, SFM), 2012-12-13 2013-08-13 Manuscript received December 13, 2012; accepted August 13, 2013 (973 ) (2012CB316302), (61070107) Supported by National Basic Research Program of China (973 Program) (2012CB316302), and National Natural Science Foundation of China (61070107) Recommended by Associate Editor ZHA Hong-Bin 1. 100190, 2. 33720, 1. National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China 2. Nokia Research Center, Tampere 33720, Finland,..,. [1 11]..,.,,.,,.,.
1602 40,.,,,..,, ;, ;,,. L-M (Levenberg-Marquardt),,,,., : 1), ; 2) ; 3),. 1,... [1 4]. Lhuillier [1].,,,. Wong [2].,. Di [3].,,. Börlin [4]. [5 11]. Zhou [5].,.. Shan [6].,.,. Fua [7].,,.,. Szeliski [8].,,,. Bartoli [9].,. Gerke [10]..,,,. McGlone, [11].,.,., L-M,.,,,. 2 [12 13] : { } arg min Proj(X i, C j ) M ij 2 (1) X i,c j i j, X i i, M ij X i j C j. (1),. 2.1,. 2.2 (1)
8 : 1603. 2.3. 2.1, p :.,. p = {O, N 0, N 1 } = {O, R(γ)e 0, R(γ)e 1 } (2), O p, N 0 N 1, R(γ), e 0 e 1.,, R(γ) = e [γ], γ, [γ] 3 3. [14]. e 0 e 1, p (R(γ)e 0 ) (R(γ)e 1 ) = R(γ)(e 0 e 1 ) γ. e 0 e 1 N 0 N 1 R(γ), γ, e 0 e 1., p X i : X i = O + u i 0N 0 + u i 1N 1 = O + [ N 0 N 1 ]u i (3), u i = [ u i 0 u i 1 ] T. 1.. (2) (3) X i : X i (O, γ, e 0, e 1, u i ) = O + R(γ)[ e 0 e 1 ]u i (4) Xi 1 X2 i {X1 i (O 1, γ 1, e 1 0, e 1 1, u 1 i )} {Xi 2 (O 2, γ 2, e 2 0, e 2 1, u 2 i )}. Xi 1 Xi 2 : θ = R(γ 1 )(e 1 0 e 1 1), R(γ 2 )(e 2 0 e 2 1) (5) γ 1 γ 2,. γ 1 γ, {Xi 1 (O 1, γ, e 1 0, e 1 1, u 1 i )} {Xi 2 (O 2, γ, R e 2 0, R e 2 1, u 2 i )}, R = R 1 (γ 1 )R(γ 2 ). γ, (5).,.. (4) (1) Fig. 1 1 Parameters for a plane and a space point on it 2.1.1, P = {X i, i = 1,, n}, :, O, O = 1 n X i (6) n i=1, O,. O, P : M = [ X 1 X n ] = [ X 1 O X n O ] (7) M : M = UΣV T = [ U 1 U 2 U 3 ][ Λ 3 3 0 3 (n 3) ]V T (8) N 0 N 1 U, : N 0 = U 1, N 1 = U 2 (9) e 0 = [1 0 0] T, e 1 = [0 1 0] T, (2) (9), R = U. p P, X i u i : [ ] N 0, X i O u i = (10) N 1, X i O,.
1604 40 2.1.2, 2.1, γ e i 0 e i 1., O γ. O 2.1.1, R(γ) e i 0 ei 1.,.. p i = {O i, N0, i N1}, i i = 1, 2, 3.. 2, : { n1, n 2 cos θ 12 n 2, n 3 cos θ 23 (11) n 1, n 3 cos θ 13, n i = N i 0 N i 1 = R i (e i 0 e i 1)., R(γ). : 2 e i 2 Fig. 2 The configuration of the normals of the three planes and the corresponding e i 2 s e i 2, i = 1, 2, 3, Re i 2 p i. Re i 2, i = 1, 2, 3 (11), : { e 1 2, e 2 2 cos θ 12 e 2 2, e 3 2 cos θ 23 (12) e 1 2, e 3 2 cos θ 13 (12) e 1 2 e 2 2 e 3 2, : R = [n 1 n 2 n 3 ][e 1 2 e 2 2 e 3 2] 1 (13) 2, e 1 2 e 2 2 [1 0 0]T 2 = 1, 2) T e 3 2 (12). [cos θ 12 sin θ 12 0] T, e 3 2 e 3 (n 1 n 2 ) T n 3 = (e 1 2 e 2 3, D: D = [n 1 n N ] (14) N : 1) rank(d) = 1,, ; 2) rank(d) = 2, n 1 n 2 D, n 3 n 1 n 2, e 3 2 e 1 2 e 2 2. 3) rank(d) = 3, n 1 n 2 n 3 D. 4) R i R, p i, e i j = R 1 R i e i j, j = 0, 1 e i j., R(e i 0 e i 1) = N0 i N1. i p i = {O i, R(γ)e i 0, R(γ)e i 1}. γ,.,,..., e i 2 n i, R : arg min γ i R(γ)e i 2, n i (15) R(γ), n i R(γ)e i 2., e i 0 e i 1, e i 0 e i 1 = e i 2.,., : 1), ; 2) ; 3),. 2.2 (4), (1). M
8 : 1605, N K, X i i, Y j i j i, Z jk i k j i., : arg min P K Proj(Z jk i, C l ) M jk il 2 + k=1 j=1 j i i l l N Proj(Y j i, C l ) M j il 2 + M Proj(X i, C l ) M il 2 (16) i=1 l, C = C C V V 1 C T V C U U 1 C T U C X X 1 C T X (20) C Q = C Q C V V 1 Q T V (21) C Γ = C Γ C V V 1 Γ T V (22) C P = C P C U U 1 P T U (23) Q = Q Q V V 1 Q T V (24) Q Γ = Q Γ Q V V 1 Γ T V (25) Γ = Γ Γ V V 1 Γ T V (26) P = P P U U 1 P T U (27), M il M j jk il Mil. (16) P, P = [p c p q p γ p p p v p u p x ], p c, p q O, p γ K K, p p N, p v u ( (3) ), p u u, p x. (16). L-M, : (J T J + λi)δ = J T E (17), J., J T J,. C C Q C Γ C P C V C U C X Q Q Γ Q V Γ Γ V P V P U U X (18) V U X, diag{v, U, X} Schur : C C Q CΓ CP A = Q Q Γ Γ (19) P, (19) A = C C X X 1 C T X (28) [12]. L n, K P, N., (19) A nl + 3P + 3K + 6N., Schur.,., [15] [16]. A ;,. 2.3.,., G = [V E].,,,,. [9],.,, ;, G. ;,. 3
1606 40. {p 3, p 4, p 5 } {p 6, p 7, p 8 }, {p 1, p 2 }. 0 π/2. e i 2 [1 0 0] T [0 1 0] T [0 0 1] T..,,. (a) (a) Average deviation of structure 3 Fig. 3 A structure with a prior information and its corresponding constraint graph 3. (BA n ) (BA p ) (BA pa )... 3.2,,,. 3.1 SFM.,, ;, 0. 0.5 2.5, 0.5, 0.5 2.5.,.,,.., [R t] = [I 0], 1. 4. 4,..,, Fig. 4 (b) (b) Average deviation of motion 4 Average deviation of estimated parameters from truth,,. 0.. 10,.,.,,.. 5,.,.,. 6,.,.
8 : 1607,,.,,.,. (a) (a) The influence of view number (a) (a) The influence of view number (b) (b) The influence of maximal length of baseline (b) (b) The influence of maximal length of baseline (c) (c) The influence of proportion of coplanar points 5 Fig. 5 Average deviation of structure 7., 7 (c),.. 8,.,,., (19) A 7m 6n,, m, n., A,.. (c) (c) The influence of proportion of coplanar points Fig. 6 6 Average deviation of camera motion,. 1, 1/10. 2,. 1 2,.,,.
1608 40, A. (a) (a) The influence of view number (a) (a) The influence of view number (b) (b) The influence of maximal length of baseline (b) (b) The influence of maximal length of baseline (c) (c) The influence of proportion of coplanar points Fig. 7 7 3.2 Average deviation of initial structure 3.2.1,. 9,. BA n,. BA p,. BA pa,,.,. Fig. 8 (c) (c) The influence of proportion of coplanar points 8 Average steps of iteration before convergency., 9. 1., 3.,,. 3.2.2,.,. J-linkage
8 : 1609 Table 1 1 1 (ms) Time costs of augmented normal equation solving based on sparse and dense methods for Problem 1 (ms) \ 0 2 4 6 8 10 12 14 16 18 20 20 0.5 (0.8) 0.5 (1.1) 0.6 (1.4) 0.7 (1.8) 0.7 (2.2) 0.7 (2.7) 0.8 (3.2) 0.8 (3.8) 0.8 (4.5) 0.8 (5.0) 0.9 (5.7) 60 2.2 (20) 2.4 (22) 2.4 (24) 2.4 (26) 2.5 (29) 2.5 (31) 2.6 (34) 2.6 (37) 2.7 (40) 2.8 (42) 3.0 (45) 100 6.1 (89) 6.6 (95) 6.9 (108) 6.5 (112) 6.7 (118) 6.1 (122) 6.7 (132) 6.8 (136) 6.8 (143) 6.9 (149) 6.9 (162) Table 2 2 2 (ms) Time costs of augmented normal equation solving based on sparse and dense methods for Problem 2 (ms) \ 0 2 4 6 8 10 12 14 16 18 20 20 1.0 (0.8) 1.2 (1.1) 1.5 (1.4) 1.8 (1.7) 1.8 (2.2) 2.1 (2.7) 2.3 (3.2) 2.7 (3.8) 3.0 (4.5) 3.4 (5.3) 3.9 (6.2) 60 8.5 (20) 9.2 (22) 10 (24) 11 (26) 12 (29) 12 (31) 14 (34) 14 (37) 16 (40) 17 (43) 17 (46) 100 30 (91) 31 (96) 33 (100) 35 (106) 37 (112) 38 (120) 40 (126) 42 (132) 44 (138) 46 (146) 47 (155) Table 3 3 Length ratio of the segments measured s2/s1 s3/s1 s4/s1 s6/s5 s7/s5 s8/s5 s10/s9 s11/s9 s12/s9 BA n 0.995450 1.02070 1.01465 0.975152 0.977288 0.994831 0.979676 0.974925 1.00458 0.993029 0.0174973 BA p 0.997801 1.01539 1.01206 0.983739 0.984721 0.997248 0.991344 0.986924 1.00629 0.997281 0.0117884 BA pa 0.999215 1.01134 1.00870 0.989130 0.991947 0.998167 0.995963 0.991761 1.00341 0.998854 0.00771090 [17].,,., [18],., 2.3.,,. 10 (a) 5. 0 π/4 π/2. 102 1 8 000 9 000, 295. 10 (a) 12. 0 π/2, e i 2 [1 0 0]T [0 1 0] T. 113, 9 ( 6 000 ), 1 3 000 1, 305.,.,. 4 9 Fig. 9 Points and segments to be measured,,..,.
自 1610 动 参数表面重建过程中. 化 学 报 40 卷 7 Fua P. Regularized bundle-adjustment to model heads from image sequences without calibration data. International Journal of Computer Vision, 2000, 38(2): 153 171 8 Szeliski R, Torr P H S. Geometrically constrained structure from motion: points on planes. Lecture Notes in Computer Science, 1998, 1506: 171 186 (a) 用于重建的图像 (a) Images used for reconstruction 9 Bartoli A, Sturm P. Constrained structure and motion from multiple uncalibrated views of a piecewise planar scene. International Journal of Computer Vision, 2003, 52(1): 45 64 10 Gerke M. Using horizontal and vertical building structure to constrain indirect sensor orientation. ISPRS Journal of Photogrammetry and Remote Sensing, 2011, 66(3): 307 316 (b) 人机交互恢复出具有纹理的空间平面 (b) Textured planes recovered based on human machine interaction 11 McGlone J C. Bundle adjustment with geometric constraints for hypothesis evaluation. sl ISPRS Journal of Photogrammetry and Remote Sensing, 1996. B3-III529 534 12 Hartley R I, Zisserman A. Multiple View Geometry in Computer Vision. Cambridge: Cambridge University Press, 2004 (c) 自动平面模型拟合的平面恢复结果 13 Triggs B, McLauchlan P F, Hartley R I, Fitzgibbon A W. Bundle adjustment a modern synthesis. In: Proceedings of the International Workshop on Vision Algorithms: Theory and Practice. London, UK: IEEE, 2000. 298 372 (c) Textured planes recovered based on automatic plane fitting 图 10 Fig. 10 应用于建筑物重建时得到的表面模型 Surface model acquired when applied to building reconstruction References 14 Wedderburn J H M. Lectures on Matrices. Providence: American Mathematical Society, 1934 15 Timothy A D. Direct Methods for Sparse Linear Systems. Philadelphia: Society for Industrial and Applied Mathematics, 2006 1 Lhuillier M. Fusion of GPS and structure-from-motion using constrained bundle adjustments. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Colorado Springs, USA: IEEE, 2011. 3025 3032 16 Rotkin V, Toledo S. The design and implementation of a new out-of-core sparse cholesky factorization method. ACM Transactions on Mathematical Software, 2004, 30(1): 19 46 2 Wong K H, Chang M M Y. 3D model reconstruction by constrained bundle adjustment. In: Proceedings of the 17th International Conference on Pattern Recognition. Cambridge, UK: IEEE, 2004, 3: 902 905 17 Toldo R, Fusiello A. Robust multiple structures estimation with J-linkage. In: Proceedings of the 10th European Conference on Computer Vision: Part I. Marseille. France: Springer-Verlag, 2008. 537 547 3 Di K, Xu F, Li R. Constrained bundle adjustment of panoramic stereo images for Mars landing site mapping. In: Proceedings of the 4th International Symposium on Mobile Mapping Technology. Kunming, China: MMT, 2004. 29 31 18 Torr P H S, Zisserman A. MLESAC: a new robust estimator with application to estimating image geometry. Computer Vision and Image Understanding, 2000, 78(1): 138 156 4 Bo rlin N, Grussenmeyer P, Eriksson J, Lindstrom P. Pros and cons of constrained and unconstrained formulation of the bundle adjustment problem. In: International Archives of ISPRS, 2004, XXXV(B3): 589 594 5 Zhou Z H, Jin H L, Ma Y. Robust plane-based structure from motion. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Rhode Island, USA: IEEE, 2012. 1482 1489 6 Shan Y, Liu Z C, Zhang Z Y. Model-based bundle adjustment with application to face modeling. In: Proceedings of the 8th IEEE International Conference on Computer Vision. Vancouver, Canada: IEEE, 2001, 2: 644 651 谢远帆 中国科学院自动化研究所博士 研究生. 2007 年获中南大学信息科学与 工程学院自动化专业学士学位. 主要研 究方向为基于视觉的同步定位与地图创 建. 本文通信作者. E-mail: yfxie@nlpr.ia.ac.cn (XIE Yuan-Fan Ph. D. candidate at the Institute of Automation, Chinese Academy of Sciences. He received his bachelor degree from Central South University in 2007. His research interest covers vision-based simultaneous localization and mapping. Corresponding author of this paper.)
8 : 1611. 2001.,,. E-mail: yhwu@nlpr.ia.ac.cn (WU Yi-Hong Professor at the Institute of Automation, Chinese Academy of Sciences. She received her Ph. D. degree from the Institute of Systems Science, Chinese Academy of Sciences in 2001. Her research interest covers camera calibration, camera pose determination, and 3D reconstruction.). 1998 2002.. E-mail: Lixin.fan@nokia.com (FAN Li-Xin Principal research scientist in the Media Lab, Nokia Research Center, Tampere, Finland. He received his master and Ph. D. degrees from National University of Singapore in 1998 and 2002. His research interest covers computer vision and pattern recognition.)