[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix

  • Published:
International Journal of Computer Vision Aims and scope Submit manuscript

Abstract

This paper has two goals. The first is to develop a variety of robust methods for the computation of the Fundamental Matrix, the calibration-free representation of camera motion. The methods are drawn from the principal categories of robust estimators, viz. case deletion diagnostics, M-estimators and random sampling, and the paper develops the theory required to apply them to non-linear orthogonal regression problems. Although a considerable amount of interest has focussed on the application of robust estimation in computer vision, the relative merits of the many individual methods are unknown, leaving the potential practitioner to guess at their value. The second goal is therefore to compare and judge the methods.

Comparative tests are carried out using correspondences generated both synthetically in a statistically controlled fashion and from feature matching in real imagery. In contrast with previously reported methods the goodness of fit to the synthetic observations is judged not in terms of the fit to the observations per se but in terms of fit to the ground truth. A variety of error measures are examined. The experiments allow a statistically satisfying and quasi-optimal method to be synthesized, which is shown to be stable with up to 50 percent outlier contamination, and may still be used if there are more than 50 percent outliers. Performance bounds are established for the method, and a variety of robust methods to estimate the standard deviation of the error and covariance matrix of the parameters are examined.

The results of the comparison have broad applicability to vision algorithms where the input data are corrupted not only by noise but also by gross outliers.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Ballard, D. H. and Brown, C. M. 1982. Computer Vision. Prentice-Hall: New Jersey.

    Google Scholar 

  • Bar-Shalom, Y. and Fortmann, T. E. 1988. Tracking and Data Association. Academic Press.

  • Beardsley, P. A., Torr, P. H. S., and Zisserman, A. P. 1996. 3D model acquisition from extended image sequences. OUEL Report 2089/96, Department of Engineering Science, University of Oxford.

    Google Scholar 

  • Bookstein, F. 1979. Fitting conic sections to scattered data. Computer Vision Graphics and Image Processing, 9:56-71.

    Google Scholar 

  • Chaterjee, S. and Hadi, A. S. 1988. Sensitivity Analysis in Linear Regression. John Wiley: New York.

    Google Scholar 

  • Cook, R. D. and Weisberg, S. 1980. Characterisations of an empirical influence function for detecting influential cases in regression. Technometrics, 22:337-344.

    Google Scholar 

  • Critchley, F. 1985. Influence in principal component analysis. Biometrika, 72:627-636.

    Google Scholar 

  • Dempster, A. P., Laird, N. M., and Rubin, D. B. 1977. Maximum likelihood from incomplete data via the em algorithm. J. Roy. Statist. Soc., 39 B:1-38.

    Google Scholar 

  • Devlin S. J., Gnanadesikan, R., and Kettering, J. R. 1981. Robust estimation of dispersion matrices and principal components. J. Amer. Stat. Assoc., 76:354-362.

    Google Scholar 

  • Faugeras, O. D. 1992. What can be seen in three dimensions with an uncalibrated stereo rig? In Proc. 2nd European Conference on Computer Vision, G. Sandini (Ed.), Santa Margherita Ligure, Italy, Springer-Verlag, vol. LNCS 588, pp. 563-578.

    Google Scholar 

  • Fischler, M. A. and Bolles, R. C. 1981. Random sample consensus: A paradigm for model fitting with application to image analysis and automated cartography. Commun. Assoc. Comp. Mach., 24:381- 395.

    Google Scholar 

  • Gill, P. E. and Murray, W. 1978. Algorithms for the solution of the nonlinear least-squares problem. SIAM J. Num. Anal., 15(5):977- 992.

    Google Scholar 

  • Golub, G. H. 1973. Some modified eigenvalue problems. SIAM Review, 15(2):318-335.

    Google Scholar 

  • Golub, G. H. and van Loan, C. F. 1989. Matrix Computations. The John Hopkins University Press.

  • Gu, M. and Eisenstat, S. C. 1995. Downdating the singular value decomposition. SIAM J. Matrix Analysis and Applications, 16:793- 810.

    Google Scholar 

  • Hampel J. P., Ronchetti, E. M., Rousseeuw, P. J., and Stahel, W. A. 1986. Robust Statistics: An Approach Based on Influence Functions. Wiley: New York.

    Google Scholar 

  • Hartley, R. I. 1992. Estimation of relative camera positions for uncalibrated cameras. In Proc. 2nd European Conference on Computer Vision, G. Sandini (Ed.), Santa Margherita Ligure, Italy, Springer-Verlag, vol. LNCS 588, pp. 579-587.

    Google Scholar 

  • Hartley, R. I. 1995. In defence of the 8-point algorithm. Proc. 5th Int. Conf. on Computer Vision, Boston, MA, pp. 1064-1070. IEEE Computer Society Press: Los Alamitos CA.

    Google Scholar 

  • Hartley, R. I. and Sturm, Y. 1994. Triangulation. In Proc. ARPA Image Understanding Workshop, pp. 957-966. and see Proc. Computer Analysis of Images and Patterns, Prague, vol. LNCS 970, Springer Verlag, 1995, pp. 190-197.

    Google Scholar 

  • Hoaglin, D. C., Mosteller, F., and Tukey, J. W. (Eds.), 1985. Robust Regression. John Wiley and Sons.

  • Huber, P. J. 1981. Robust Statistics. John Wiley and Sons.

  • Kanatani, K. 1992. Geometric Computation for Machine Vision. Oxford University Press.

  • Kanatani, K. 1994. Statistical bias of conic fitting and renormalization. IEEE Trans. Pattern Analysis and Machine Intelligence, 16(3):320-326.

    Google Scholar 

  • Kanatani, K. 1996. Statistical Optimization for Geometric Computation: Theory and Practice. Elsevier Science: Amsterdam.

    Google Scholar 

  • Kendall, M. and Stuart, A. 1983. The Advanced Theory of Statistics. Charles Griffin and Company: London.

    Google Scholar 

  • Kumar, R. and Hanson, A. R. 1994. Robust methods for estimating pose and a sensitivity analysis. Computer Vision, Graphics and Image Processing, 60(3):313-342.

    Google Scholar 

  • Li, G. 1985. Exploring data tables, trends and shapes. In Robust Regression, D. C. Hoaglin, F. Mosteller, and J. W. Tukey (Eds.), John Wiley and Sons, pp. 281-343.

  • Li, H., Lavin, M. A., and LeMaster, R. J. 1986. Fast Hough transforms: A hierarchical approach. Computer Vision, Graphics and Image Processing, 36:139-161.

    Google Scholar 

  • Longuet-Higgins, H. C. 1981. A computer algorithm for reconstructing a scene from two projections. Nature, 293:133-135.

    Google Scholar 

  • Luong, Q. T. 1992. Matrice Fondamentale et Calibration Visuelle sur l'environnement: Vers use plus grande autonomie des systemes robotiques. Ph. D. Thesis, Paris University.

  • Luong, Q. T., Deriche, R., Faugeras, O. D., and Papadopoulo, T. 1993. On determining the fundamental matrix: Analysis of different methods and experimental results. INRIA Technical Report 1894, INRIA-Sophia Antipolis.

  • Maronna, R. A. 1976. Robust M-estimators of multivariate location and scatter. Ann. Stat., 4:51-67.

    Google Scholar 

  • McLauchlan, P. F. 1990. Describing Textured Surfaces Using Stereo Vision. Ph. D. Thesis, AI Vision Research Unit, University of Sheffield.

  • Meer, M., Mintz, D., and Rosenfeld, A. (1991). Robust regression methods for computer vision: A review. International Journal of Computer Vision, 6:59-70.

    Google Scholar 

  • Mosteller, F. and Tukey, J. W. 1977. Data and Analysis and Regression. Addison-Wesley: Reading, MA. Numerical Algorithms Group, 1988. NAG Fortran Library, vol 7.

    Google Scholar 

  • Olsen, S. I. 1992. Epipolar line estimation. In Proc. 2nd European Conference on Computer Vision, G. Sandini (Ed.), Santa Margherita Ligure, Italy, Springer-Verlag, vol. LNCS 588, pp. 307-311.

    Google Scholar 

  • Pearson, K. 1901. On lines and planes of closest fit to systems of points in space. Philos. Mag. Ser. 6, 2:559.

    Google Scholar 

  • Pratt, V. 1987. Direct least squares fitting of algebraic surfaces. Computer Graphics, 21(4):145-152.

    Google Scholar 

  • Roth, G. and Levine, M. D. 1993. Extracting geometric primitives. Computer Vision, Graphics, and Image Processing, 58(1):1-22.

    Google Scholar 

  • Rousseeuw, P. J. 1987. Robust Regression and Outlier Detection. Wiley: New York.

    Google Scholar 

  • Sampson, P. D. 1982. Fitting conic sections to 'very scattered' data: An iterative refinement of the Bookstein algorithm. Computer Graphics and Image Processing, 18:97-108.

    Google Scholar 

  • Shapiro, L. S. and Brady, J. M. 1995. Rejecting outliers and estimating errors in an orthogonal regression framework. Phil. Trans. R. Soc. Lond. A, 350:407-439.

    Google Scholar 

  • Spetsakis, M. and Aloimonos, Y. 1991. Amulti-frame approach to visual motion perception. International Journal of Computer Vision, 6:245-255.

    Google Scholar 

  • Sprent, P. 1989. Applied Nonparametric Statistical Methods. Chapman and Hall: London.

    Google Scholar 

  • Stewart, C. V. 1995. MINPRAN, a new robust estimator for computer vision. IEEE Trans. on Pattern Analysis and Machine Intelligence, 17(10):925-938.

    Google Scholar 

  • Taubin, G. 1991. Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations with applications to edge and range image segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 13(11):1115-1138.

    Google Scholar 

  • Thisted, R. A. 1988. Elements of Statistical Computing. Chapman and Hall: New York.

    Google Scholar 

  • Torr, P. H. S. 1995. Outlier Detection and Motion Segmentation. D. Phil. Thesis, University of Oxford.

  • Torr, P. H. S. and Murray, D. W. 1992. Statistical detection of non-rigid motion. In Proc. 3rd British Machine Vision Conference, Leeds, D. Hogg (Ed.), Springer-Verlag, pp. 79-88.

  • Torr, P. H. S. and Murray, D. W. 1993a. Statistical detection of independent movement from a moving camera. Image and Vision Computing, 1(4):180-187.

    Google Scholar 

  • Torr, P. H. S. and Murray, D. W. 1993b. Outlier detection and motion segmentation. In Proc. Sensor Fusion VI, Boston, MA, P. S. Schenker (Ed.), vol. SPIE 2059, pp. 432-443.

  • Torr, P. H. S. and Murray, D. W. 1994. Stochastic motion segmentation. In Proc. 3rd European Conference on Computer Vision, Stockholm, J.-O. Ecklundh (Ed.), Springer-Verlag, pp. 328- 338.

  • Torr, P. H. S., Zisserman, A., and Maybank, S. 1995a. Robust detection of degeneracy. Proc. 5th Int. Conf. on Computer Vision, Boston, MA, IEEE Computer Society Press: Los Alamitos CA, pp. 1037-1044.

    Google Scholar 

  • Torr, P. H. S, Zisserman, A., and Murray, D. W. 1995b. Motion clustering using the trilinear constraint over three views. In Europe-China Workshop on Geometrical Modelling and Invariants for Computer Vision, R. Mohr and C. Wu (Eds.), Springer-Verlag, pp. 118- 125.

  • Torr, P. H. S, Maybank, S., and Zisserman, A. 1996. Robust detection of degenerate configurations for the fundamental matrix. OUEL Report 2090/96, Department of Engineering Science, University of Oxford.

  • Teukolsky, S. A., Press, W. H., Flannery, B. P., and Vetterling, W. T. 1988. Numerical Recipes in C, the Art of Scientific Computing. Cambridge University Press: Cambridge.

    Google Scholar 

  • Tsai, R. Y. and Huang, T. S. 1984. Uniqueness and estimation of three-dimensional motion parameters of rigid objects with curved surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:13-27.

    Google Scholar 

  • Weng, J., Huang, T. S., and Ahuja, N. 1989. Motion and structure from two perspective views: Algorithms, error analysis, and error estimation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11:451-476.

    Google Scholar 

  • Weng, J., Ahuja, N., and Huang, T. S. 1993. Optimal motion and structure estimation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 15(9):864-884.

    Google Scholar 

  • Zhang, Z., Deriche, R., Faugeras, O. D., and Luong, Q. T. 1994. A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry. AI Journal, 78:87- 119.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Engineering Science, University of Oxford, Parks Road, Oxford, OX1 3PJ, UK

    P.H.S. Torr & D.W. Murray

Authors
  1. P.H.S. Torr
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. D.W. Murray
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Torr, P., Murray, D. The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix. International Journal of Computer Vision 24, 271–300 (1997). https://doi.org/10.1023/A:1007927408552

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1007927408552

Search

Navigation