cvpr cvpr2013 cvpr2013-317 cvpr2013-317-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Erik Ask, Olof Enqvist, Fredrik Kahl
Abstract: This paper is concerned with model fitting in the presence of noise and outliers. Previously it has been shown that the number of outliers can be minimized with polynomial complexity in the number of measurements. This paper improves on these results in two ways. First, it is shown that for a large class of problems, the statistically more desirable truncated L2-norm can be optimized with the same complexity. Then, with the same methodology, it is shown how to transform multi-model fitting into a purely combinatorial problem—with worst-case complexity that is polynomial in the number of measurements, though exponential in the number of models. We apply our framework to a series of hard registration and stitching problems demonstrating that the approach is not only of theoretical interest. It gives a practical method for simultaneously dealing with measurement noise and large amounts of outliers for fitting problems with lowdimensional models.
[1] E. Ask, Y. Kuang, and K A˚str ¨om. Exploiting p-fold symmetries for faster polynomial equation solving. In Int. Conf. Pattern Recognition, Tsukuba, Japan, 2012. 6
[2] M.S. Bazaraa, H.D. Sherali, and C.M. Shetty. NonlinearProgramming: Theory and Algorithms. Wiley, 1993. 3, 4
[3] J-C. Bazin, Y. Seo, C. Demonceaux, P. Vasseur, K. Ikeuchi, I. Kweon, and M. Pollefeys. Globally optimal line clustering and vanishing point estimation in manhattan world. In Conf. Computer Vision and Pattern Recognition, 2012. 1
[4] A. Blake and A. Zisserman. Visual Reconstruction. MIT Press, Cambridge, USA, 1987. 2
[5] M. Byr o¨d, K. Josephson, and K. A˚str ¨om. Fast and stable polynomial equation solving and its application to computer vision. Int. Journal of Computer Vision, 2009. 5
[6] O. Chum and J. Matas. Optimal randomized ransac. IEEE Trans. Pattern Analysis and Machine Intelligence, 2008. 1
[7] O. Enqvist, E. Ask, F. Kahl, and K. A˚str ¨om. Robust fitting for multiple view geometry. In European Conf. on Computer Vision, 2012. 1, 2, 3
[8] O. Enqvist, K. Josephson, and F. Kahl. Optimal correspondences from pairwise constraints. In Int. Conf. Computer Vision, 2009. 1
[9] O. Enqvist and F. Kahl. Robust optimal pose estimation. In European Conf. on Computer Vision, 2008. 1
[10] M. A. Fischler and R. C. Bolles. Random sample consensus: a paradigm for model fitting with application to image analysis and automated cartography. Commun. Assoc. Comp. Mach., 1981 . 1
[11] B. Horn, H. M. Hilden, and S. Negahdaripour. Closed-form solution of absolute orientation using ortonormal matrices. Journal of the Optical Society of America A, 1988. 5
[12] K. Lebeda, J. Matas, and O. Chum. Fixing the locally optimized ransac. In British Machine Vision Conf., 2012. 1, 7
[13] H. Li. Consensus set maximization with guaranteed global optimality for robust geometry estimation. In Int. Conf. Computer Vision, 2009. 1
[14] C. Olsson, O. Enqvist, and F. Kahl. A polynomial-time bound for matching and registration with outliers. In Conf. Computer Vision and Pattern Recognition, 2008. 1
[15] R. Toldo and A. Fusiello. Robust multiple structures estimation with J-linkage. In European Conf. on Computer Vision, 2008. 1
[16] B. Tordoff and D. W. Murray. Guided sampling and consensus for motion estimation. In European Conf. on Computer Vision, 2002. 1
[17] J. Wills, S. Agarwal, and S. Belongie. A feature-based approach for dense segmentation and estimation of large disparity motion. Int. Journal of Computer Vision, 2006. 2
[18] M. Zuliani, C.S. Kenney, and B.S. Manjunath. The multiRANSAC algorithm and its application to detect planar homographies. In Int. Conf. Image Processing, 2005. 1, 2 111777222977