Abstract

Markov Random Fields (MRFs) are a widely used graphical model, but the inference problem is NP-hard. For first-order MRFs with binary labels, Dead End Elimination (DEE) [7] and QPBO [2, 14] can find the optimal labeling for some variables; the much harder case of larger label sets has been addressed by Kovtun [16, 17] and related methods [12, 23, 24, 25], which impose substantial computational overhead. We describe an efficient algorithm to correctly label a subset of the variables for arbitrary MRFs, with particularly good performance on binary MRFs. Wepropose a sufficient condition to check if a partial labeling is optimal, which is a generalization of DEE’s purely local test. We give a hierarchy of relaxations that provide larger optimal partial labelings at the cost of additional computa-tion. Empirical studies were conducted on several benchmarks, using expansion moves [4] for inference. Our algorithm runs in a few seconds, and improves the speed of MRFinference with expansion moves by a factor of 1.5 to 12.