Graph-Based Simplex Method for Pairwise Energy Minimization With Binary Variables

Daniel Prusa

CVPR 2015poster8 citations

Graph-Based Simplex Method for Pairwise Energy Minimization With Binary Variables

Abstract

We show how the simplex algorithm can be tailored to the linear programming relaxation of pairwise energy minimization with binary variables. A special structure formed by basic and nonbasic variables in each stage of the algorithm is identified and utilized to perform the whole iterative process combinatorially over the input energy minimization graph rather than algebraically over the simplex tableau. This leads to a new efficient solver. We demonstrate that for some computer vision instances it performs even better than methods reducing binary energy minimization to finding maximum flow in a network.

BibTeX

@inproceedings{cvpr2015_graphbasedsimple,
  title = {Graph-Based Simplex Method for Pairwise Energy Minimization With Binary Variables},
  author = {Daniel Prusa},
  booktitle = {CVPR 2015},
  year = {2015}
}