Iterative Extensions of the Sturm/Triggs Algorithm: Convergence and Nonconvergence
|
We give the first complete theoretical convergence analysis for the iterative extensions of the Sturm/Triggs algorithm. We show that the simplest extension, SIESTA, converges to nonsense results. Another proposed extension has similar problems, and experiments with “balanced” iterations show that they can fail to converge or become unstable. We present CIESTA, an algorithm which avoids these problems. It is identical to SIESTA except for one simple extra computation. Under weak assumptions, we prove that CIESTA iteratively decreases an error and approaches fixed points. With one more assumption, we prove it converges uniquely. Our results imply that CIESTA gives a reliable way of initializing other algorithms such as bundle adjustment. A descent method such as Gauss–Newton can be used to minimize the CIESTA error, combining quadratic convergence with the advantage of minimizing in the projective depths. Experiments show that CIESTA performs better than other iterations.
[1] 2217 R. Berthilsson, A. Heyden, and G. Sparr, “Recursive Structure and Motion from Image Sequences Using Shape and Depth Spaces,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, pp. 444-449, 1997.
[2] A. Buchanan and A. Fitzgibbon, “Damped Newton Algorithms for Matrix Factorization with Missing Data,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, vol. II, pp. 316-322, 2005.
[3] A.P. Dempster, N. Laird, and D. Rubin, “Maximum Likelihood from Incomplete Data via the EM Algorithm,” J. Royal Statistical Soc., vol. 39, no. B, pp. 1-38, 1977.
[4] R. Dutta, R. Manmatha, L.R. Williams, and E.M. Riseman, “A Data Set for Quantitative Motion Analysis,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, pp. 159-164, 1989.
[5] R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, 2000.
[6] A. Heyden, R. Berthilsson, and G. Sparr, “An Iterative Factorization Method for Projective Structure and Motion from Image Sequences,” Image and Vision Computing, vol. 17, pp. 981-991, 1999.
[7] B.K.P. Horn and E.J. Weldon, Jr., “Direct Methods for Recovering Motion,” Int'l J. Computer Vision, vol. 2, no. 1, pp. 51-76, 1988.
[8] R. Kumar and A.R. Hanson, “Sensitivity of the Pose Refinement Problem to Accurate Estimation of Camera Parameters,” Proc. Int'l Conf. Computer Vision, pp. 365-369, 1990.
[9] S. Mahamud, M. Hebert, Y. Omori, and J. Ponce, “Provably-Convergent Iterative Methods for Projective Structure from Motion,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, vol. I, pp. 1018-1025, 2001.
[10] S. Mahamud and M. Hebert, “Iterative Projective Reconstruction from Multiple Views,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, vol. II, pp. 430-437, 2000.
[11] J. Oliensis and R. Hartley, “Iterative Extensions of the Sturm/Triggs Algorithm: Convergence and Nonconvergence,” Proc. European Conf. Computer Vision, vol. IV, pp. 214-227, 2006.
[12] J. Oliensis, “Fast and Accurate Self-Calibration,” Proc. Int'l Conf. Computer Vision, pp. 745-752, 1999.
[13] J. Oliensis and Y. Genc, “Fast and Accurate Algorithms for Projective Multi-Image Structure from Motion,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 6, pp. 546-559, June 2001.
[14] P. Sturm and B. Triggs, “A Factorization Based Algorithm for Multi-Image Projective Structure and Motion,” Proc. European Conf. Computer Vision, vol. II, pp. 709-720, 1996.
[15] C. Tomasi and T. Kanade, “Shape and Motion from Image Streams under Orthography: A Factorization Method,” Int'l J. Computer Vision, vol. 9, pp. 137-154, 1992.
[16] B. Triggs, “Factorization Methods for Projective Structure and Motion,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, pp. 845-851, 1996.
[17] B. Triggs, P. McLauchlan, R. Hartley, and A. Fitzgibbon, “Bundle Adjustment—A Modern Synthesis,” Proc. Workshop Vision Algorithms: Theory and Practice, pp. 298-372, 1999.
[18] Z. Zhang, “A Flexible New Technique for Camera Calibration,” Microsoft Technical Report MSR-TR-98-71, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 11, pp. 1330-1334, Nov. 2000.
Index Terms:
Structure from motion, projective geometry, factorization, projective factorization, convergence, optimization, Sturm/Triggs algorithm
Citation:
John Oliensis, Richard Hartley, "Iterative Extensions of the Sturm/Triggs Algorithm: Convergence and Nonconvergence," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 12, pp. 2217-2233, June 2007, doi:10.1109/TPAMI.2007.1132
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb