nach oben

International Journal of Computer Vision

Erschienen in:

29.08.2016

GRMA: Generalized Range Move Algorithms for the Efficient Optimization of MRFs

verfasst von: Kangwei Liu, Junge Zhang, Peipei Yang, Stephen Maybank, Kaiqi Huang

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Markov random fields (MRF) have become an important tool for many vision applications, and the optimization of MRFs is a problem of fundamental importance. Recently, Veksler and Kumar et al. proposed the range move algorithms, which are some of the most successful optimizers. Instead of considering only two labels as in previous move-making algorithms, they explore a large search space over a range of labels in each iteration, and significantly outperform previous move-making algorithms. However, two problems have greatly limited the applicability of range move algorithms: (1) They are limited in the energy functions they can handle (i.e., only truncated convex functions); (2) They tend to be very slow compared to other move-making algorithms (e.g., \(\alpha \)-expansion and \(\alpha \beta \)-swap). In this paper, we propose two generalized range move algorithms (GRMA) for the efficient optimization of MRFs. To address the first problem, we extend the GRMAs to more general energy functions by restricting the chosen labels in each move so that the energy function is submodular on the chosen subset. Furthermore, we provide a feasible sufficient condition for choosing these subsets of labels. To address the second problem, we dynamically obtain the iterative moves by solving set cover problems. This greatly reduces the number of moves during the optimization. We also propose a fast graph construction method for the GRMAs. Experiments show that the GRMAs offer a great speedup over previous range move algorithms, while yielding competitive solutions.

Vorheriger Artikel Mining Mid-level Visual Patterns with Deep CNN Activations

Nächster Artikel 2D Sub-pixel Point Spread Function Measurement Using a Virtual Point-Like Source

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

Nur mit Berechtigung zugänglich

In this work, we consider the optimization of arbitrary semimetric energy functions. Here, “semimetric” means that the pairwise function should satisfy \(\theta (\alpha ,\beta )=0\Leftrightarrow \alpha =\beta \) and \(\theta (\alpha ,\beta )=\theta (\beta ,\alpha )\ge 0\).

A function \(g(\cdot )\) is convex if it satisfies \(g(x+1)-2g(x)+g(x-1) \ge 0\) for any integer x. Note that convex is a special case of submodular.

Here, the interval [a, b] denotes the set of integers \(\{x|a \le x \le b\}\).

In \(\alpha \beta \)-swap, we call these iteration moves considering all the pairs of labels once as a “cycle”. An \(\alpha \beta \)-swap algorithm usually takes several cycles to converge (Boykov et al. 2001).

We chose this cost function for simplicity, but a better iterative process may be developed with other choices, for example \(c(S_i) = 1+|S_i|\), because a small number of repeated labels may lead to a better solution without a significant increasing in the run time. Another choice is to set \(c(S_i)\) to be the estimate of improvement in energy as Batra and Kohli (2011). However, the experiments show that GRSA yields promising results with the simple choice of cost function made here.

If \({\hat{f}}\) is a local minimum, it means that \(E({\hat{f}})\) cannot be decreased by any of the moves \({\mathcal {L}}_{i}\).

When \(\theta _{pq}\) is a truncated linear function, the graph construction in the GRSA is the same as previous methods.

The edges \((p_i,p_{i+1})\) for all \(i \in [1,m)\) and \((p_m,t)\) are already included in the unary edges

https://static-content.springer.com/image/art%3A10.1007%2Fs11263-016-0944-z/MediaObjects/11263_2016_944_IEq361_HTML.gif

. We can add the capacities that represent the pairwise potentials to these edges.

Note that when \(\theta _{pq}\) is a truncated linear function, the numbers of edges in the new construction and in the previous method are the same, because \(c(p_i,q_j)=0\) for \(i\ne j\) in this case.

http://vision.middlebury.edu/stereo/eval/.

http://cvn.ecp.fr/personnel/pawan/research/truncated-moves.html.

Here, the interval [a, b] denotes the set of integers \(\{x|a \le x \le b\}\).

Batra, D., & Kohli, P. (2011). Making the right moves: Guiding alpha-expansion using local primal-dual gaps. In IEEE Conference on Computer Vision and Pattern Recognition (pp. 1865–1872).

Besag, J. (1986). On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society, 48(3), 259–302.MathSciNetMATH

Boykov, Y., & Jolly. (2001) Interactive graph cuts for optimal boundary and region segmentation of objects in nd images. In IEEE International Conference on Computer Vision (pp. 105–112).

Boykov, Y., & Jolly, M. P. (2000). Interactive organ segmentation using graph cuts. In Medical Image Computing and Computer-Assisted Intervention (pp. 276–286).

Boykov, Y., & Kolmogorov, V. (2003). Computing geodesics and minimal surfaces via graph cuts. In IEEE International Conference on Computer Vision (pp. 26–33).

Boykov, Y., Veksler, O., & Zabih, R. (2001). Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11), 1222–1239.CrossRef

Chekuri, C., Khanna, S., Naor, J., & Zosin, L. (2004). A linear programming formulation and approximation algorithms for the metric labeling problem. SIAM Journal on Discrete Mathematics, 18(3), 608–625.MathSciNetCrossRefMATH

Feige, U. (1998). A threshold of ln n for approximating set cover. Journal of the ACM, 45(4), 634–652.MathSciNetCrossRefMATH

Gould, S,, Amat, F., & Koller, D. (2009). Alphabet soup: A framework for approximate energy minimization. In IEEE Conference on Computer Vision and Pattern Recognition (pp. 903–910).

Greig, D., Porteous, B., & Seheult, A. H. (1989). Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society, 51, 271–279.

Gridchyn, I., & Kolmogorov, V. (2013). Potts model, parametric maxflow and k-submodular functions. In IEEE International Conference on Computer Vision (pp. 2320–2327).

Ishikawa, H. (2003). Exact optimization for markov random fields with convex priors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(10), 1333–1336.CrossRef

Kappes, J. H., Andres, B., Hamprecht, F. A., Schnörr, C., Nowozin, S., Batra, D., Kim, S., Kausler, B. X., Lellmann, J., Komodakis, N., & Rother, C. (2013). A comparative study of modern inference techniques for discrete energy minimization problem. In IEEE Conference on Computer Vision and Pattern Recognition (pp. 1328–1335).

Kohli, P., Osokin, A., & Jegelka, S. (2013). A principled deep random field model for image segmentation. In IEEE Conference on Computer Vision and Pattern Recognition (pp. 1971–1978)

Kolmogorov, V. (2006). Convergent tree-reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10), 1568–1583.CrossRef

Kolmogorov, V., & Rother, C. (2007). Minimizing nonsubmodular functions with graph cuts-a review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(7), 1274–1279.CrossRef

Kolmogorov, V., & Zabin, R. (2004). What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2), 147–159.CrossRef

Kumar, M. P. (2014). Rounding-based moves for metric labeling. In Advances in Neural Information Processing Systems (pp. 109–117).

Kumar, M. P., Koller, D. (2009). Map estimation of semi-metric mrfs via hierarchical graph cuts. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (pp. 313–320).

Kumar, M. P., & Torr, P. H. (2009). Improved moves for truncated convex models. In Advances in Neural Information Processing Systems (pp. 889–896).

Kumar, M. P., Veksler, O., & Torr, P. H. (2011). Improved moves for truncated convex models. The Journal of Machine Learning Research, 12, 31–67.

Lempitsky, V., Rother, C., & Blake, A. (2007). Logcut-efficient graph cut optimization for markov random fields. In IEEE International Conference on Computer Vision (pp. 1–8).

Lempitsky, V., Rother, C., Roth, S., & Blake, A. (2010). Fusion moves for markov random field optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(8), 1392–1405.CrossRef

Liu, K., Zhang, J., Huang, K., & Tan, T. (2014). Deformable object matching via deformation decomposition based 2d label mrf. In IEEE Conference on Computer Vision and Pattern Recognition (pp. 2321–2328).

Liu, K., Zhang, J., Yang, P., & Huang, K. (2015). GRSA: Generalized range swap algorithm for the efficient optimization of mrfs. In IEEE Conference on Computer Vision and Pattern Recognition (pp. 1761–1769).

Martin, D., Fowlkes, C., Tal, D., & Malik, J. (2001). A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. IEEE International Conference on Computer Vision, 2, 416–423.

Nagarajan, R. (2003). Intensity-based segmentation of microarray images. IEEE Transactions on Medical Imaging, 22(7), 882–889.CrossRef

Poggio, T., Torre, V., & Koch, C. (1989). Computational vision and regularization theory. Image understanding, 3(1–18), 111.

Rother, C., Kolmogorov, V., Lempitsky, V., & Szummer, M. (2007). Optimizing binary mrfs via extended roof duality. In textitIEEE Conference on Computer Vision and Pattern Recognition (pp. 1–8).

Scharstein, D., & Szeliski, R. (2002). A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision, 47, 7–42.CrossRefMATH

Schlesinger, D., & Flach, B. (2006). Transforming an arbitrary minsumproblem into a binary one. TU, Fak. Informatik.

Slavłk, P. (1996). A tight analysis of the greedy algorithm for set cover. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (pp. 435–441).

Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., et al. (2008). A comparative study of energy minimization methods for mrfs with smoothness-based priors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(6), 1068–1080.CrossRef

Tappen, M. F., & Freeman, W. T. (2003). Comparison of graph cuts with belief propagation for stereo using identical mrf parameters. In IEEE International Conference on Computer Vision (pp. 900–906).

Veksler, O. (2007). Graph cut based optimization for mrfs with truncated convex priors. In IEEE Conference on Computer Vision and Pattern Recognition (pp. 1–8).

Veksler, O. (2012). Multi-label moves for mrfs with truncated convex priors. International Journal of Computer Vision, 98(1), 1–14.MathSciNetCrossRefMATH

Titel: GRMA: Generalized Range Move Algorithms for the Efficient Optimization of MRFs
verfasst von: Kangwei Liu
Junge Zhang
Peipei Yang
Stephen Maybank
Kaiqi Huang
Publikationsdatum: 29.08.2016
Verlag: Springer US
Erschienen in: International Journal of Computer Vision / Ausgabe 3/2017
Print ISSN: 0920-5691
Elektronische ISSN: 1573-1405
DOI: https://doi.org/10.1007/s11263-016-0944-z

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/2017

Subspace Procrustes Analysis

2D Sub-pixel Point Spread Function Measurement Using a Virtual Point-Like Source

On the Existence of Epipolar Matrices

Mining Mid-level Visual Patterns with Deep CNN Activations

Premium Partner