LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Liu, K.; Zhang, J.; Yang, P.; Maybank, Stephen; Huang, K. (2017)
Publisher: Springer
Languages: English
Types: Article
Subjects: csis
Markov Random Fields (MRF) have become an\ud important tool for many vision applications, and the optimization\ud of MRFs is a problem of fundamental importance.\ud Recently, Veksler and Kumar et al. proposed the range move\ud algorithms, which are some of the most successful optimizers.\ud Instead of considering only two labels as in previous\ud move-making algorithms, they explore a large search space\ud over a range of labels in each iteration, and significantly\ud outperform previous move-making algorithms. However, two\ud problems have greatly limited the applicability of range\ud move algorithms: 1) They are limited in the energy functions\ud they can handle (i.e., only truncated convex functions); 2)\ud They tend to be very slow compared to other move-making\ud algorithms (e.g., �-expansion and ��-swap). In this paper,\ud we propose two generalized range move algorithms (GRMA)\ud for the efficient optimization of MRFs. To address the\ud first problem, we extend the GRMAs to more general energy\ud functions by restricting the chosen labels in each move so\ud that the energy function is submodular on the chosen subset.\ud Furthermore, we provide a feasible sufficient condition for\ud choosing these subsets of labels. To address the second\ud problem, we dynamically obtain the iterative moves by solving\ud set cover problems. This greatly reduces the number of\ud moves during the optimization.We also propose a fast graph\ud construction method for the GRMAs. Experiments show\ud that the GRMAs offer a great speedup over previous range\ud move algorithms, while yielding competitive solutions.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • Batra D, Kohli P (2011) Making the right moves: Guiding alphaexpansion 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
    • 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 MP (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
    • 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
    • Feige U (1998) A threshold of ln n for approximating set cover. Journal of the ACM 45(4):634-652
    • 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 AH (1989) Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society pp 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
    • Kappes JH, Andres B, Hamprecht FA, Schno¨rr C, Nowozin S, Batra D, Kim S, Kausler BX, 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
    • 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
    • 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
    • Kumar MP (2014) Rounding-based moves for metric labeling. In: Advances in Neural Information Processing Systems, pp 109-117
    • Kumar MP, 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 MP, Torr PH (2009) Improved moves for truncated convex models. In: Advances in Neural Information Processing Systems, pp 889-896
    • Kumar MP, Veksler O, Torr PH (2011) Improved moves for truncated convex models. The Journal of Machine Learning Research 12
    • 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
    • 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. In: IEEE International Conference on Computer Vision, vol 2, pp 416-423
    • Nagarajan R (2003) Intensity-based segmentation of microarray images. IEEE Transactions on Medical Imaging 22(7):882-889
    • 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: IEEE 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
    • Schlesinger D, Flach B (2006) Transforming an arbitrary minsum problem into a binary one. TU, Fak. Informatik
    • Slavłk P (1996) A tight analysis of the greedy algorithm for set cover pp 435-441
    • Szeliski R, Zabih R, Scharstein D, Veksler O, Kolmogorov V, Agarwala A, Tappen M, Rother C (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
    • Tappen MF, Freeman WT (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
    • Using the equation above and Eq. 41, we obtain
    • and thus, the inequality (42) is true when a = 1. We assume inequality (42) holds true when a = k (k
    • (lk+1; l1) cut(lk; fq0 )+ (lk; l1) 0, we have
    • cut(lk+1; fq0 ) = cut(lk; fq0 ) + (lk+1; l1)
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article