Abstract
We present an algebraic geometric approach to 3-D motion estimation and segmentation of multiple rigid-body motions from noise-free point correspondences in two perspective views. Our approach exploits the algebraic and geometric properties of the so-called multibody epipolar constraint and its associated multibody fundamental matrix, which are natural generalizations of the epipolar constraint and of the fundamental matrix to multiple motions. We derive a rank constraint on a polynomial embedding of the correspondences, from which one can estimate the number of independent motions as well as linearly solve for the multibody fundamental matrix. We then show how to compute the epipolar lines from the first-order derivatives of the multibody epipolar constraint and the epipoles by solving a plane clustering problem using Generalized PCA (GPCA). Given the epipoles and epipolar lines, the estimation of individual fundamental matrices becomes a linear problem. The clustering of the feature points is then automatically obtained from either the epipoles and epipolar lines or from the individual fundamental matrices. Although our approach is mostly designed for noise-free correspondences, we also test its performance on synthetic and real data with moderate levels of noise.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Avidan, S. and Shashua, A. 2000.Trajectory triangulation: 3D reconstruction of moving points from a monocular image sequence, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(4):348–357.
Costeira, J. and Kanade, T. 1995. Multibody factorization methods for motion analysis, In International Conference on Computer Vision, pp. 1071–1076.
Fan, X. and Vidal, R. 2005. The space of multibody fundamental matrices: Rank geometry and projection. In ICCV Workshop on Dynamical Vision.
Feng, X. and Perona, P. 1998. Scene segmentation from 3D motion, In IEEE Conference on Computer Vision and Pattern Recognition, pp. 225–231.
Han, M. and Kanade, T. 2000. Reconstruction of a scene with multiple linearly moving objects. In IEEE Conference on Computer Vision and Pattern Recognition, volume 2, pp. 542–549.
Harris, J. 1992. Algebraic Geometry: A First Course, Springer-Verlag.
Hartley R. and Zisserman A. 2000. Multiple View Geometry in Computer Vision, Cambridge.
Hartley, R. and Vidal, R. 2004. The multibody trifocal tensor: Motion segmentation from 3 perspective views, In IEEE Conference on Computer Vision and Pattern Recognition, volume I, pp. 769–775.
Kanatani, K. 2001. Motion segmentation by subspace separation and model selection, In International Conference on Computer Vision, vol. 2, pp. 586–591.
Kanatani, K. 2002. Evaluation and selection of models for motion segmentation, In Asian Conference on Computer Vision, pp. 7–12.
Lang, S. 1993. Algebra, Addison-Wesley Publishing Company, 3rd edition
Longuet-Higgins, H., C. 1981. A computer algorithm for reconstructing a scene from two projections, Nature, 293:133–135.
Ma, Y., Košecká, J. and Sastry, S. 2001. Optimization criteria and geometric algorithms for motion and structure estimation, International Journal of Computer Vision, 44(3):219–249.
Ma, Y. Soatto, S., Kosecka, J., and Sastry, S. 2003. An Invitation to 3D Vision: From Images to Geometric Models, Springer Verlag.
Shashua, A. and Levin, A. 2001. Multi-frame infinitesimal motion model for the reconstruction of (dynamic) scenes with multiple linearly moving objects. In International Conference on Computer Vision, vol. 2 :592–599.
Sturm, P. 2002. Structure and motion for dynamic scenes—the case of points moving in planes. In European Conference on Computer Vision, pp. 867–882.
Torr, P., Szeliski, R., and Anandan, P. 2001. An integrated Bayesian approach to layer extraction from image sequences. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(3):297–303.
Torr, P. H. S. 1998. Geometric motion segmentation and model selection, Philosophical Transactions Royal Society of London, 356(1740):1321–1340.
Vidal, R. and Hartley, R. 2004. Motion segmentation with missing data by PowerFactorization and Generalized PCA. In IEEE Conference on Computer Vision and Pattern Recognition, vol. II, pp. 310–316.
Vidal, R. and Ma, Y. 2004. A unified algebraic approach to 2-D and 3-D motion segmentation, In European Conference on Computer Vision, pp. 1–15.
Vidal, R., Ma, Y., and Piazzi. J. 2004. A new GPCA algorithm for clustering subspaces by fitting, differentiating and dividing polynomials. In IEEE Conference on Computer Vision and Pattern Recognition, (1):510–517.
Vidal, R., Ma, Y., and Sastry, S. 2005. Generalized principal component analysis (GPCA). IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(12):1–15.
Vidal, R., Ma, Y., and Sastry, S. 2003. Generalized Principal Component Analysis (GPCA). In IEEE Conference on Computer Vision and Pattern Recognition, (1):621–628.
Vidal, R. and Sastry, S. 2003. Optimal segmentation of dynamic scenes from two perspective views. In IEEE Conference on Computer Vision and Pattern Recognition, (2):281–286.
Vidal, R., Soatto, S., Ma, Y., and Sastry, S. 2002. Segmentation of dynamic scenes from the multibody fundamental matrix. In ECCV Workshop on Visual Modeling of Dynamic Scenes.
Vidal, R., Soatto, S., and Sastry, S. 2002. Two-view segmentation of dynamic scenes from the multibody fundamental matrix. Technical Report, UCB/ERL M02/02, UC Berkeley.
Wolf, L. and Shashua, A. 2001. Affine 3-D reconstruction from two projective images of independently translating planes. In International Conference on Computer Vision, pp. 238–244.
Wolf, L. and Shashua, A. 2001. Two-body segmentation from two perspective views. In Conference on Computer Vision and Pattern Recognition, pp. 263–270.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is an extended version of Vidal et al. (2002). Work supported by Hopkins WSE and UIUC ECE startup funds, and by grants NSF CAREER ISS-0447739, ONR N00014-00-1-0621, NSF CAREER IIS-0347456, NSF IIS-0347456, ONR N00014-03-1-0850, ARO DAAD19-99-1-0137 and AFOSRF49620-03-1-0095, N00014-05-1-0836.
Rights and permissions
About this article
Cite this article
Vidal, R., Ma, Y., Soatto, S. et al. Two-View Multibody Structure from Motion. Int J Comput Vision 68, 7–25 (2006). https://doi.org/10.1007/s11263-005-4839-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-005-4839-7