×

Robust fitting in computer vision: easy or hard? (English) Zbl 1477.68344

Summary: Robust model fitting plays a vital role in computer vision, and research into algorithms for robust fitting continues to be active. Arguably the most popular paradigm for robust fitting in computer vision is consensus maximisation, which strives to find the model parameters that maximise the number of inliers. Despite the significant developments in algorithms for consensus maximisation, there has been a lack of fundamental analysis of the problem in the computer vision literature. In particular, whether consensus maximisation is “tractable” remains a question that has not been rigorously dealt with, thus making it difficult to assess and compare the performance of proposed algorithms, relative to what is theoretically achievable. To shed light on these issues, we present several computational hardness results for consensus maximisation. Our results underline the fundamental intractability of the problem, and resolve several ambiguities existing in the literature.

MSC:

68T45 Machine vision and scene understanding
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C17 Robustness in mathematical programming

Software:

KITTI; Vlfeat; USAC
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Amaldi, E.; Kann, V., The complexity and approximability of finding maximum feasible subsystems of linear relations, Theoretical Computer Science, 147, 181-210 (1995) · Zbl 0884.68093 · doi:10.1016/0304-3975(94)00254-G
[2] Aronov, B.; Har-Peled, S., On approximating the depth and related problems, SIAM Journal on Computing, 38, 3, 899-921 (2008) · Zbl 1180.68278 · doi:10.1137/060669474
[3] Bazin, Jc; Li, H.; Kweon, Is; Demonceaux, C.; Vasseur, P.; Ikeuchi, K., A branch-and-bound approach to correspondence and grouping problems, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 7, 1565-1576 (2013) · doi:10.1109/TPAMI.2012.264
[4] Ben-David, S.; Eiron, N.; Simon, H., The computational complexity of densest region detection, Journal of Computer and System Sciences, 64, 1, 22-47 (2002) · Zbl 1006.68058 · doi:10.1006/jcss.2001.1797
[5] Bernholt, T. (2005). Robust estimators are hard to compute. Technical report 52, Technische Universität.
[6] Cai, Zhipeng; Chin, Tat-Jun; Le, Huu; Suter, David, Deterministic Consensus Maximization with Biconvex Programming, Computer Vision - ECCV 2018, 699-714 (2018), Cham: Springer International Publishing, Cham
[7] Campbell, D., Petersson, L., Kneip, L., Li, H. (2017). Globally-optimal inlier set maximisation for simultaneous camera pose and feature correspondence. In IEEE international conference on computer vision (ICCV).
[8] Cheney, Ew, Introduction to approximation theory (1966), New York: McGraw-Hill, New York · Zbl 0161.25202
[9] Chin, T. J., Cai, Z., Neumann, F. (2018). Robust fitting in computer vision: easy or hard? In European conference on computer vision (ECCV).
[10] Chin, T. J., Kee, Y. H., Eriksson, A., Neumann, F. (2016). Guaranteed outlier removal with mixed integer linear programs. In IEEE computer society conference on computer vision and pattern recognition (CVPR).
[11] Chin, T. J., Purkait, P., Eriksson, A., Suter, D. (2015). Efficient globally optimal consensus maximisation with tree search. In IEEE computer society conference on computer vision and pattern recognition (CVPR).
[12] Choi, S., Kim, T., Yu, W. (2009). Performance evaluation of RANSAC family. In British machine vision conference (BMVC).
[13] Cygan, M.; Fomin, Fv; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized algorithms (2015), Berlin: Springer, Berlin · Zbl 1334.90001
[14] Downey, Rg; Fellows, Mr, Parametrized complexity (1999), New York: Springer, New York
[15] Enqvist, O., Ask, E., Kahl, F., & Åström, K. (2012). Robust fitting for multiple view geometry. In European conference on computer vision (ECCV). · Zbl 1398.68576
[16] Enqvist, O.; Ask, E.; Kahl, F.; Åström, K., Tractable algorithms for robust model estimation, International Journal of Computer Vision, 112, 1, 115-129 (2015) · Zbl 1398.68576 · doi:10.1007/s11263-014-0760-2
[17] Erickson, J.; Har-Peled, S.; Mount, Dm, On the least median square problem, Discrete & Computational Geometry, 36, 4, 593-607 (2006) · Zbl 1104.68117 · doi:10.1007/s00454-006-1267-6
[18] Fischler, Ma; Bolles, Rc, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, 24, 6, 381-395 (1981) · doi:10.1145/358669.358692
[19] Fukuda, K.; Liebling, Tm; Margot, F., Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron, Computational Geometry, 8, 1-12 (1997) · Zbl 1133.68462 · doi:10.1016/0925-7721(95)00049-6
[20] Garey, Mr; Johnson, Ds, Computers and intractability: a guide to the theory of NP-completeness (1990), New York: W H Freeman & Co, New York
[21] Geiger, A., Lenz, P., Urtasun, R. (2012). Are we ready for autonomous driving? the kitti vision benchmark suite. In Conference on computer vision and pattern recognition (CVPR).
[22] Giannopoulos, Panos; Knauer, Christian; Rote, Günter, The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension, Parameterized and Exact Computation, 198-209 (2009), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1273.68170
[23] Hart, Pe; Nilsson, Nj; Raphael, B., A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions Systems Science and Cybernetics, 4, 2, 100-107 (1968) · doi:10.1109/TSSC.1968.300136
[24] Hartley, R.; Zisserman, A., Multiple view geometry in computer vision (2003), Cambridge: Cambridge University Press, Cambridge
[25] Johnson, Ds, Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences, 9, 256-278 (1974) · Zbl 0296.65036 · doi:10.1016/S0022-0000(74)80044-9
[26] Johnson, Ds; Preparata, Fp, The densest hemisphere problem, Theoretical Computer Science, 6, 93-107 (1978) · Zbl 0368.68053 · doi:10.1016/0304-3975(78)90006-3
[27] Le, H., Chin, T. J., Suter, D. (2017). An exact penalty method for locally convergent maximum consensus. In IEEE computer society conference on computer vision and pattern recognition (CVPR).
[28] Li, H. (2009). Consensus set maximization with guaranteed global optimality for robust geometry estimation. In: IEEE international conference on computer vision (ICCV).
[29] Lowe, D. G. (1999) Object recognition from local scale-invariant features. In The proceedings of the seventh IEEE international conference on computer vision, 1999 (Vol. 2, pp. 1150-1157). IEEE
[30] Matoušek, J., On geometric optimization with few violated constraints, Discrete and Computational Geometry, 14, 4, 365-384 (1995) · Zbl 0844.90071 · doi:10.1007/BF02570713
[31] Meer, P.; Medioni, G.; Kang, Sb, Robust techniques for computer vision, Emerging topics in computer vision (2004), New York: Prentice Hall, New York
[32] Parra Bustos, A., Chin, T. J., Suter, D.: Fast rotation search with stereographic projections for 3d registration. In IEEE computer society conference on computer vision and pattern recognition (CVPR) (2014)
[33] Parra Bustos, A., Chin, T. J. (2015). Guaranteed outlier removal for rotation search. In IEEE international conference on computer vision (ICCV).
[34] Purkait, P., Zach, C., Eriksson, A. (2017) Maximum consensus parameter estimation by reweighted L1 methods. In Energy minimization methods in computer vision and pattern recognition (EMMCVPR).
[35] Raguram, R.; Chum, O.; Pollefeys, M.; Matas, J.; Frahm, Jm, USAC: A universal framework for random sample consensus, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 8, 2022-2038 (2013) · doi:10.1109/TPAMI.2012.257
[36] Svärm, L., Enqvist, O., Oskarsson, M., Kahl, F. (2014). Accurate localization and pose estimation for large 3d models. In IEEE computer society conference on computer vision and pattern recognition (CVPR)
[37] Tran, Qh; Chin, Tj; Chojnacki, W.; Suter, D., Sampling minimal subsets with large spans for robust estimation, International Journal of Computer Vision (IJCV), 106, 1, 93-112 (2014) · Zbl 1328.68251 · doi:10.1007/s11263-013-0643-y
[38] Vazirani, V., Approximation algorithms (2001), Berlin: Springer, Berlin · Zbl 1138.90417
[39] Vedaldi, A., Fulkerson, B. (2010). Vlfeat: An open and portable library of computer vision algorithms. In Proceedings of the 18th ACM international conference on Multimedia (pp. 1469-1472). ACM.
[40] Yang, J., Li, H., Jia, Y.: Optimal essential matrix estimation via inlier-set maximization. In European conference on computer vision (ECCV)
[41] Zheng, Y., Sugimoto, S., Okutomi, M.: Deterministically maximizing feasible subsystems for robust model fitting with unit norm constraints. In IEEE computer society conference on computer vision and pattern recognition (CVPR) (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.