40 8 Vol. 40, No ACTA AUTOMATICA SINICA August, ,,,.,.,,,.,.,,,.,,,. DOI,, L-M (Levenberg-Marquardt),,,.., 2014, 40(8):

Size: px

Start display at page:

Download "40 8 Vol. 40, No ACTA AUTOMATICA SINICA August, ,,,.,.,,,.,.,,,.,,,. DOI,, L-M (Levenberg-Marquardt),,,.., 2014, 40(8):"

熏娄
5 years ago
Views:

1 40 8 Vol. 40, No ACTA AUTOMATICA SINICA August, ,,,.,.,,,.,.,,,.,,,. DOI,, L-M (Levenberg-Marquardt),,,.., 2014, 40(8): /SP.J 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): ,., 2. (Structure from motion, SFM), Manuscript received December 13, 2012; accepted August 13, 2013 (973 ) (2012CB316302), ( ) Supported by National Basic Research Program of China (973 Program) (2012CB316302), and National Natural Science Foundation of China ( ) Recommended by Associate Editor ZHA Hong-Bin , , 1. National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences, Beijing , China 2. Nokia Research Center, Tampere 33720, Finland,..,. [1 11]..,.,,.,,.,.

2 ,.,,,..,, ;, ;,,. 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 ) γ.

3 8 : , 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 ][ Λ (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,.

4 , 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 ) 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

5 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..,,.

3 A structure with a prior information and its corresponding constraint graph 3. (BA n ) (BA p ) (BA pa )... 3.2,,,.

6 {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.1 SFM.,, ;, , 0.5, ,.,,.., [R t] = [I 0], ,..,, Fig. 4 (b) (b) Average deviation of motion 4 Average deviation of estimated parameters from truth,, ,.,.,,.. 5,.,.,. 6,.,.

of coplanar points 5 Fig. 5 Average deviation of structure 7., 7 (c),.. 8,.

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

The influence of maximal length of baseline (c)

8 , 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 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.,, ,.,. 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.$

9 8 : 1609 Table (ms) Time costs of augmented normal equation solving based on sparse and dense methods for Problem 1 (ms) \ (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) (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) (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 (ms) Time costs of augmented normal equation solving based on sparse and dense methods for Problem 2 (ms) \ (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) (20) 9.2 (22) 10 (24) 11 (26) 12 (29) 12 (31) 14 (34) 14 (37) 16 (40) 17 (43) 17 (46) (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 BA p BA pa [17].,,., [18],., 2.3.,,. 10 (a) 5. 0 π/4 π/ , (a) π/2, e i 2 [1 0 0]T [0 1 0] T. 113, 9 ( ), , 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.

Lecture Notes in Computer Science, 1998, 1506: 171 186 (a) 用于重建的图像 (a) Images used for reconstruction 9 Bartoli A, Sturm P.

Using horizontal and vertical building structure to constrain indirect sensor orientation.

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.

10 自 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): Szeliski R, Torr P H S. Geometrically constrained structure from motion: points on planes. Lecture Notes in Computer Science, 1998, 1506: (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): Gerke M. Using horizontal and vertical building structure to constrain indirect sensor orientation. ISPRS Journal of Photogrammetry and Remote Sensing, 2011, 66(3): (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, B3-III 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, (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, Timothy A D. Direct Methods for Sparse Linear Systems. Philadelphia: Society for Industrial and Applied Mathematics, 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, 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): 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: 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, 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, 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): 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): 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, 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: 谢远帆中国科学院自动化研究所博士研究生年获中南大学信息科学与工程学院自动化专业学士学位. 主要研究方向为基于视觉的同步定位与地图创建. 本文通信作者. 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 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.

Her research interest covers camera calibration, camera pose determination, and 3D reconstruction.). 1998 2002.. E-mail: Lixin.fan@nokia.

11 8 : ,,. 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 Her research interest covers camera calibration, camera pose determination, and 3D reconstruction.) 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 His research interest covers computer vision and pattern recognition.)

,,.,, : 1),,,,, 2),,,,, 3),,,,,,,,,, [6].,,, ( ),, [9], : 1), 2),,,,, 3),,, 2.,, [10].,,,,,,,,, [11]. 2.1,, [12],, ;, ; Fig. 1 1 Granular hier

,,.,, : 1),,,,, 2),,,,, 3),,,,,,,,,, [6].,,, ( ),, [9], : 1), 2),,,,, 3),,, 2.,, [10].,,,,,,,,, [11]. 2.1,, [12],, ;, ; Fig. 1 1 Granular hier 36 7 Vol. 36, No. 7 2010 7 ACTA AUTOMATICA SINICA July, 2010 1, 2 1, 2, 3 1, 2,,,,,,, DOI,,, 10.3724/SP.J.1004.2010.00923 Distributed Simulation System Hierarchical Design Model Based on Quotient Space