GRMA: Generalized Range Move Algorithms for the efficient\ud optimization of MRFs

Article English OPEN
Liu, K. ; Zhang, J. ; Yang, P. ; Maybank, Stephen ; Huang, K. (2017)

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.
  • References (40)
    40 references, page 1 of 4

    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

  • Metrics
    No metrics available
Share - Bookmark