Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Ising Models for Binary Clustering via Adiabatic Quantum Computing Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Maximum Consensus Parameter Estimation by Reweighted \(\ell _1\) Methods

Authors : Pulak Purkait, Christopher Zach, Anders Eriksson

Published in: Energy Minimization Methods in Computer Vision and Pattern Recognition

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Robust parameter estimation in computer vision is frequently accomplished by solving the maximum consensus (MaxCon) problem. Widely used randomized methods for MaxCon, however, can only produce random approximate solutions, while global methods are too slow to exercise on realistic problem sizes. Here we analyse MaxCon as iterative reweighted algorithms on the data residuals. We propose a smooth surrogate function, the minimization of which leads to an extremely simple iteratively reweighted algorithm for MaxCon. We show that our algorithm is very efficient and in many cases, yields the global solution. This makes it an attractive alternative for randomized methods and global optimizers. The convergence analysis of our method and its fundamental differences from the other iteratively reweighted methods are also presented.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Superpixels Optimized by Color and Shape
next chapter A Graph Theoretic Approach for Shape from Shading
Footnotes
1
Since \(\mathbf {s}^{(l)}\) is only used to compute the weights \(\mathbf {w}^{(l+1)}\) in the next iteration, an approximate solution, which still minimizes the objective, is sufficient to initialize \(\mathbf {s}^{(l+1)}\).
 
Literature
1.
Meer, P.: Robust techniques for computer vision. In: Medioni, G., Kang, S.B. (eds.) Emerging Topics in Computer Vision, pp. 107–190. Prentice Hall (2004)
2.
3.
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009)MathSciNetCrossRefMATH
4.
5.
Fischler, M.A., Bolles, R.C.: Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24, 381–395 (1981)MathSciNetCrossRef
6.
Choi, S., Kim, T., Yu, W.: Performance evaluation of RANSAC family. JCV 24, 271–300 (1997)
7.
Torr, P.H., Zisserman, A.: MLESAC: a new robust estimator with application to estimating image geometry. CVIU 78, 138–156 (2000)
8.
9.
Raguram, R., Chum, O., Pollefeys, M., Matas, J., Frahm, J.M.: USAC: a universal framework for random sample consensus. IEEE TPAMI 35, 2022–2038 (2013)CrossRef
10.
Olsson, C., Enqvist, O., Kahl, F.: A polynomial-time bound for matching and registration with outliers. In: CVPR (2008)
11.
12.
Chin, T.J., Purkait, P., Eriksson, A., Suter, D.: Efficient globally optimal consensus maximisation with tree search. In: CVPR, pp. 2413–2421 (2015)
13.
Li, H.: Consensus set maximization with guaranteed global optimality for robust geometry estimation. In: ICCV, pp. 1074–1080. IEEE (2009)
14.
Zheng, Y., Sugimoto, S., Okutomi, M.: Deterministically maximizing feasible subsystems for robust model fitting with unit norm constraints. In: CVPR (2011)
15.
16.
Lebeda, K., Matas, J., Chum, O.: Fixing the locally optimized RANSAC-full experimental evaluation. In: BMVC12. Citeseer (2012)
17.
Tordoff, B.J., Murray, D.W.: Guided-MLESAC: faster image transform estimation by using matching priors. IEEE TPAMI 27, 1523–1535 (2005)CrossRef
18.
Olsson, C., Eriksson, A., Hartley, R.: Outlier removal using duality. In: CVPR (2010)
19.
Vanderbei, R.J.: LOQO User’s Manual-version 4.05. Princeton University, Princeton (2006)
20.
Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Prog. 106, 25–57 (2006)MathSciNetCrossRefMATH
21.
Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: ICASSP, pp. 3869–3872. IEEE (2008)
22.
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)CrossRefMATH
23.
Kahl, F., Hartley, R.I.: Multiple-view geometry under the \(l_\infty \)-norm. IEEE TPAMI 30, 1603–1617 (2008)CrossRef
24.
Candes, E.J., Wakin, M.B., Boyd, S.P.: Enhancing sparsity by reweighted \(\mathbf{l}_1\) minimization. J. Fourier Anal. Appl. 14, 877–905 (2008)MathSciNetCrossRefMATH
25.
Gorodnitsky, I.F., Rao, B.D.: Sparse signal reconstruction from limited data using focuss: a re-weighted minimum norm algorithm. TSP 45, 600–616 (1997)
26.
Chartrand, R.: Exact reconstruction of sparse signals via nonconvex minimization. IEEE SPL 14, 707–710 (2007)
27.
Sriperumbudur, B.K., Lanckriet, G.R.: A proof of convergence of the concave-convex procedure using Zangwill’s theory. Neural Comput. 24, 1391–1407 (2012)MathSciNetCrossRefMATH
28.
29.
30.
Ye, Y., Tse, E.: An extension of Karmarkar’s projective algorithm for convex quadratic programming. Math. Prog. 44, 157–179 (1989)MathSciNetCrossRefMATH
31.
Sim, K., Hartley, R.: Removing outliers using the \(l_\infty \) norm. In: CVPR (2006)
32.
Wipf, D., Nagarajan, S.: Iterative reweighted and methods for finding sparse solutions. JSTSP 4, 317–329 (2010)
33.
34.
Grant, M., Boyd, S.: CVX: matlab software for disciplined convex programming (2008)
35.
Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2003)MATH
Metadata
Title
Maximum Consensus Parameter Estimation by Reweighted Methods
Authors
Pulak Purkait
Christopher Zach
Anders Eriksson
Copyright Year
2018
Book
Energy Minimization Methods in Computer Vision and Pattern Recognition

Print ISBN: 978-3-319-78198-3

Electronic ISBN: 978-3-319-78199-0

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-78199-0_21

Premium Partner

    Image Credits