Markov Random Fields (MRF) have become anudimportant tool for many vision applications, and the optimizationudof MRFs is a problem of fundamental importance.udRecently, Veksler and Kumar et al. proposed the range moveudalgorithms, which are some of the most successful optimizers.udInstead of considering only two labels as in previousudmove-making algorithms, they explore a large search spaceudover a range of labels in each iteration, and significantlyudoutperform previous move-making algorithms. However, twoudproblems have greatly limited the applicability of rangeudmove algorithms: 1) They are limited in the energy functionsudthey can handle (i.e., only truncated convex functions); 2)udThey tend to be very slow compared to other move-makingudalgorithms (e.g., �-expansion and ��-swap). In this paper,udwe propose two generalized range move algorithms (GRMA)udfor the efficient optimization of MRFs. To address theudfirst problem, we extend the GRMAs to more general energyudfunctions by restricting the chosen labels in each move soudthat the energy function is submodular on the chosen subset.udFurthermore, we provide a feasible sufficient condition forudchoosing these subsets of labels. To address the secondudproblem, we dynamically obtain the iterative moves by solvingudset cover problems. This greatly reduces the number ofudmoves during the optimization.We also propose a fast graphudconstruction method for the GRMAs. Experiments showudthat the GRMAs offer a great speedup over previous rangeudmove algorithms, while yielding competitive solutions.
展开▼