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

CVPR 2015

doi:10.1109/CVPR.2015.7298645 /cvpr/2015/prusa2015cvpr-graphbased/

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.

PDF CVPR Semantic Scholar

Cite

Text

Prusa. "Graph-Based Simplex Method for Pairwise Energy Minimization with Binary Variables." Conference on Computer Vision and Pattern Recognition, 2015. doi:10.1109/CVPR.2015.7298645

Markdown

[Prusa. "Graph-Based Simplex Method for Pairwise Energy Minimization with Binary Variables." Conference on Computer Vision and Pattern Recognition, 2015.](https://mlanthology.org/cvpr/2015/prusa2015cvpr-graphbased/) doi:10.1109/CVPR.2015.7298645

BibTeX

@inproceedings{prusa2015cvpr-graphbased,
  title     = {{Graph-Based Simplex Method for Pairwise Energy Minimization with Binary Variables}},
  author    = {Prusa, Daniel},
  booktitle = {Conference on Computer Vision and Pattern Recognition},
  year      = {2015},
  doi       = {10.1109/CVPR.2015.7298645},
  url       = {https://mlanthology.org/cvpr/2015/prusa2015cvpr-graphbased/}
}