nach oben

International Journal of Computer Vision

Erschienen in:

09.08.2019

Robust Fitting in Computer Vision: Easy or Hard?

verfasst von: Tat-Jun Chin, Zhipeng Cai, Frank Neumann

Erschienen in: International Journal of Computer Vision | Ausgabe 3/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Special Issue: Advances in Architectures and Theories for Computer Vision

Nächster Artikel Learning SO(3) Equivariant Representations with Spherical CNNs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

It may be the case that MAXCON is in class APX, i.e., that it could be approximated in polynomial time to some factor. However, we are not aware of any such algorithms.

Since RANSAC does not provide any approximation guarantees, it is not an “approximation scheme” by standard definition (Vazirani 2001).

A dicussion between Tat-Jun Chin and Komei Fukuda in Feb 2018 suggested that a direct reduction from MaxFS to MAXCON is itself infeasible, due to the intractability of bounding a hyperplane arrangement (Fukuda et al. 1997, Theorem 5.1).

If one was ever interested in only, say, robust affine registration of 2D point sets, then one could say that robust 2D affine registration is tractable, since the technique of Enqvist et al. (2012, 2015) can be used to construct an \(\mathcal {O}(N^7)\) algorithm, which is polynomial in the number of input correspondences N. However, robust fitting in general, where N and d can both vary, is not tractable by the reasons already alluded to above.

https://en.wikipedia.org/wiki/Parameterized_complexity.

This can be ensured by infinitesimal data perturbations (Matoušek 1995).

https://en.wikipedia.org/wiki/Computational_complexity_theory#Measuring_the_size_of_an_instance.

https://github.com/ZhipengCai/Demo---MAXCON-hardness.

We do not report the result of Algorithm 1 or 2 since they are too slow even for small o and d (both algorithms did finish in 2 hours for one data instance when \(d > 7\) and \(o > 7\)).

https://en.wikipedia.org/wiki/Single-precision_floating-point_format.

https://en.wikipedia.org/wiki/2-satisfiability.

https://en.wikipedia.org/wiki/L-reduction.

Amaldi, E., & Kann, V. (1995). The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Computer Science, 147, 181–210.MathSciNetCrossRef

Aronov, B., & Har-Peled, S. (2008). On approximating the depth and related problems. SIAM Journal on Computing, 38(3), 899–921.MathSciNetCrossRef

Bazin, J. C., Li, H., Kweon, I. S., Demonceaux, C., Vasseur, P., & Ikeuchi, K. (2013). A branch-and-bound approach to correspondence and grouping problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(7), 1565–1576.CrossRef

Ben-David, S., Eiron, N., & Simon, H. (2002). The computational complexity of densest region detection. Journal of Computer and System Sciences, 64(1), 22–47.MathSciNetCrossRef

Bernholt, T. (2005). Robust estimators are hard to compute. Technical report 52, Technische Universität.

Cai, Z., Chin, T. J., Le, H., Suter, D. (2018). Deterministic consensus maximization with biconvex programming. In European conference on computer vision (ECCV).CrossRef

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).

Cheney, E. W. (1966). Introduction to approximation theory. New York: McGraw-Hill.MATH

Chin, T. J., Cai, Z., Neumann, F. (2018). Robust fitting in computer vision: easy or hard? In European conference on computer vision (ECCV).

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).

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).

Choi, S., Kim, T., Yu, W. (2009). Performance evaluation of RANSAC family. In British machine vision conference (BMVC).

Cygan, M., Fomin, F. V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., et al. (2015). Parameterized algorithms (Vol. 3). Berlin: Springer.CrossRef

Downey, R. G., & Fellows, M. R. (1999). Parametrized complexity. New York: Springer.CrossRef

Enqvist, O., Ask, E., Kahl, F., & Åström, K. (2012). Robust fitting for multiple view geometry. In European conference on computer vision (ECCV).

Enqvist, O., Ask, E., Kahl, F., & Åström, K. (2015). Tractable algorithms for robust model estimation. International Journal of Computer Vision, 112(1), 115–129.MathSciNetCrossRef

Erickson, J., Har-Peled, S., & Mount, D. M. (2006). On the least median square problem. Discrete & Computational Geometry, 36(4), 593–607.MathSciNetCrossRef

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.MathSciNetCrossRef

Fukuda, K., Liebling, T. M., & Margot, F. (1997). Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. Computational Geometry, 8, 1–12.MathSciNetCrossRef

Garey, M. R., & Johnson, D. S. (1990). Computers and intractability: a guide to the theory of NP-completeness. New York: W H Freeman & Co.MATH

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).

Giannopoulos, P., Knauer, C., Rote, G.: The parameterized complexity of some geometric problems in unbounded dimension. In International workshop on parameterized and exact computation (IWPEC) (2009).CrossRef

Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions Systems Science and Cybernetics, 4(2), 100–107.CrossRef

Hartley, R., & Zisserman, A. (2003). Multiple view geometry in computer vision. Cambridge: Cambridge University Press.MATH

Johnson, D. S. (1974). Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9, 256–278.MathSciNetCrossRef

Johnson, D. S., & Preparata, F. P. (1978). The densest hemisphere problem. Theoretical Computer Science, 6, 93–107.MathSciNetCrossRef

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).

Li, H. (2009). Consensus set maximization with guaranteed global optimality for robust geometry estimation. In: IEEE international conference on computer vision (ICCV).

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

Matoušek, J. (1995). On geometric optimization with few violated constraints. Discrete and Computational Geometry, 14(4), 365–384.MathSciNetCrossRef

Meer, P. (2004). Robust techniques for computer vision. In G. Medioni & S. B. Kang (Eds.), Emerging topics in computer vision. New York: Prentice Hall.

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)

Parra Bustos, A., Chin, T. J. (2015). Guaranteed outlier removal for rotation search. In IEEE international conference on computer vision (ICCV).

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).

Raguram, R., Chum, O., Pollefeys, M., Matas, J., & Frahm, J. M. (2013). USAC: A universal framework for random sample consensus. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8), 2022–2038.CrossRef

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)

Tran, Q. H., Chin, T. J., Chojnacki, W., & Suter, D. (2014). Sampling minimal subsets with large spans for robust estimation. International Journal of Computer Vision (IJCV), 106(1), 93–112.MathSciNetCrossRef

Vazirani, V. (2001). Approximation algorithms. Berlin: Springer.MATH

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.

Yang, J., Li, H., Jia, Y.: Optimal essential matrix estimation via inlier-set maximization. In European conference on computer vision (ECCV)

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)

Titel: Robust Fitting in Computer Vision: Easy or Hard?
verfasst von: Tat-Jun Chin
Zhipeng Cai
Frank Neumann
Publikationsdatum: 09.08.2019
Verlag: Springer US
Erschienen in: International Journal of Computer Vision / Ausgabe 3/2020
Print ISSN: 0920-5691
Elektronische ISSN: 1573-1405
DOI: https://doi.org/10.1007/s11263-019-01207-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2020

DeepIM: Deep Iterative Matching for 6D Pose Estimation

Convolutional Networks with Adaptive Inference Graphs

DeepTAM: Deep Tracking and Mapping with Convolutional Neural Networks

EKLT: Asynchronous Photometric Feature Tracking Using Events and Frames

Special Issue: Advances in Architectures and Theories for Computer Vision

CornerNet: Detecting Objects as Paired Keypoints

Premium Partner