Abstract
The problem of automatic robust estimation of the epipolar geometry in cases where the correspondences are contaminated with a high percentage of outliers is addressed. This situation often occurs when the images have undergone a significant deformation, either due to large rotation or wide baseline of the cameras. An accelerated algorithm for the identification of the false matches between the views is presented. The algorithm generates a set of weak motion models (WMMs). Each WMM roughly approximates the motion of correspondences from one image to the other. The algorithm represents the distribution of the median of the geometric distances of a correspondence to the WMMs as a mixture model of outlier correspondences and inlier correspondences. The algorithm generates a sample of outlier correspondences from the data. This sample is used to estimate the outlier rate and to estimate the outlier pdf. Using these two pdfs the probability that each correspondence is an inlier is estimated. These probabilities enable guided sampling. In the RANSAC process this guided sampling accelerates the search process. The resulting algorithm when tested on real images achieves a speedup of between one or two orders of magnitude.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Adam, A., Rivlin, E., & Shimshoni, I. (2001). ROR: Rejection of outliers by rotations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(1), 78–84.
Chen, H., & Meer, P. (2003). Robust regression with projection based m-estimators. In International conference on computer vision (pp. 878–885).
Chum, O., Matas, J., & Kittler, J. V. (2003). Locally optimized RANSAC. In German pattern recognition symposium (pp. 236–243).
Duda, R. O., Hart, P. E., & Stork, D. G. (2001). Pattern classification. New York: Wiley.
Fischler, M. A., & Bolles, R. C. (1981). Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6), 381–395.
Freund, Y., & Schapire, R. (1997). A decision-theoretic generalization of online learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119–139.
Goshen, L., & Shimshoni, I. (2005). Guided sampling via weak motion models and outlier sample generation for epipolar geometry estimation. In Proceedings of the IEEE conference on computer vision and pattern recognition (pp. I: 1105–1112).
Hartley, R. I., & Zisserman, A. (2000). Multiple view geometry in computer vision. Cambridge: Cambridge University Press.
Lee, K. M., Meer, P., & Park, R. H. (1998). Robust adaptive segmentation of range images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(2), 200–205.
Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2), 91–110.
Matas, J., & Chum, O. (2004). Randomized RANSAC with T d,d test. Image and Vision Computing, 22(10), 837–842.
Moisan, L., & Stival, B. (2004). A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix. International Journal of Computer Vision, 57(3), 201–218.
Rozenfeld, S., & Shimshoni, I. (2005). The modified pbM-estimator method and a runtime analysis technique for the ransac family. In Proceedings of the IEEE conference on computer vision and pattern recognition (pp. I: 1113–1120).
Stewart, C. V. (1995). Minpran: a new robust estimator for computer vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(10), 925–938.
Subbarao, R., & Meer, P. (2007). Discontinuity preserving filtering over analytic manifolds. In Proceedings of the IEEE conference on computer vision and pattern recognition (pp. 1–6).
Tordoff, B., & Murray, D. W. (2002). Guided sampling and consensus for motion estimation. In European conference on computer vision (pp. I: 82–96).
Torr, P. H. S. (1995). Motion segmentation and outlier detection. Ph.D. thesis, Department of Engineering Science, University of Oxford.
Torr, P. H. S., & Davidson, C. (2003). IMPSAC: Synthesis of importance sampling and random sample consensus. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(3), 354–364.
Torr, P. H. S., & Zisserman, A. (2000). MLESAC: a new robust estimator with application to estimating image geometry. Computer Vision and Image Understanding, 78(1), 138–156.
Triggs, B. (1995). Matching constraints and the joint image. In International conference on computer vision (pp. 338–343).
Triggs, B. (2001). Joint feature distributions for image correspondence. In International conference on computer vision (pp. II: 201–208).
Wand, M. P., & Jones, M. C. (1995). Kernel smoothing. London: Chapman & Hall.
Wang, H., & Suter, D. (2004a). Mdpe: a very robust estimator for model fitting and range image segmentation. International Journal of Computer Vision, 59(2), 139–166.
Wang, H., & Suter, D. (2004b). Robust adaptive-scale parametric model estimation for computer vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(11), 1459–1474.
Yu, X. M., Bui, T. D., & Krzyzak, A. (1994). Robust estimation for range image segmentation and reconstruction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5), 530–538.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported partly by grant 01-99-08430 of the Israeli Space Agency through the Ministry of Science Culture and Sports of Israel.
Rights and permissions
About this article
Cite this article
Goshen, L., Shimshoni, I. Guided Sampling via Weak Motion Models and Outlier Sample Generation for Epipolar Geometry Estimation. Int J Comput Vis 80, 275–288 (2008). https://doi.org/10.1007/s11263-008-0126-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-008-0126-8