While Markov Random Fields (MRFs) are widely used in computer vision, they present a quite challenging inference problem. MRF inference can be accelerated by pre-processing techniques like Dead End Elimination (DEE) or QPBO-based approaches which compute the optimal labeling of a subset of variables. These techniques are guaranteed to never wrongly label a variable but they often leave a large number of variables unlabeled. We address this shortcoming by interpreting pre-processing as a classification problem, which allows us to trade off false positives (i.e., giving a variable an incorrect label) versus false negatives (i.e., failing to label a variable). We describe an efficient discriminative rule that finds optimal solutions for a subset of variables. Our technique provides both per-instance and worst-case guarantees concerning the quality of the solution. Empirical studies were conducted over several benchmark datasets. We obtain a speedup factor of 2 to 12 over expansion moves without preprocessing, and on difficult non-submodular energy functions produce slightly lower energy.
We apply the dead-end elimination (DEE) strategy from protein design as a heuristic for the max-flow min-cut formulation of the image segmentation problem. DEE combines aspects of constraint propagation and branch-and-bound to eliminate solutions incompatible with global optimization of the objective function. Though DEE can be used for segmentation into an arbitrary number of regions, in this paper we evaluate only the case of binary segmentation. We provide a runtime analysis and evaluation of DEE applied to two min-cut algorithms. Preliminary results show that DEE consistently reduces the search space for the Edmonds?Karp algorithm; tuning DEE as a heuristic for Boykov?Kolmogorov and other algorithms is future work. In this paper, we present novel techniques that improve the computational and memory efficiency of algorithms for solving multi-label energy functions arising from discrete MRFs or CRFs. These methods are motivated by the observations that the performance of minimization algorithms depends on: 1) the initialization used for the primal and dual variables and 2) the number of primal variables involved in the energy function. Our first method (dynamic α-expansion) works by "recycling" results from previous problem instances. The second method simplifies the energy function by "reducing" the number of unknown variables present in the problem. Further, we show that it can also be used to generate a good initialization for the dynamic α-expansion algorithm by "reusing" dual variables. We test the performance of our methods on energy functions encountered in the problems of stereo matching and color and object-based segmentation. Experimental results show that our methods achieve a substantial improvement in the performance of α-expansion, as well as other popular algorithms such as sequential tree-re-weighted message passing and max-product belief propagation. We also demonstrate the applicability of our schemes for certain higher order energy functions, such as the one described, for interactive texture-based image and video segmentation. In most cases, we achieve a 10-15 times speed-up in the computation time. Our modified α-expansion algorithm provides similar performance to Fast-PD, but is conceptually much simpler. Both α-expansion and Fast-PD can be made orders of magnitude faster when used in conjunction with the "reduce" scheme proposed in this paper.