A discriminative view of MRF pre-processing algorithms
This work addresses a bottleneck in computer vision for MRF users by improving pre-processing efficiency, though it is incremental as it builds on existing techniques.
The paper tackled the problem of MRF inference pre-processing leaving many variables unlabeled by framing it as a classification task, achieving speedups of 2 to 12 times over expansion moves and slightly lower energy on non-submodular functions.
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.