  Many computer vision problems require optimization of binary non-submodular
energies. We propose a general optimization framework based on local submodular
approximations (LSA). Unlike standard LP relaxation methods that linearize the
whole energy globally, our approach iteratively approximates the energies
locally. On the other hand, unlike standard local optimization methods (e.g.
gradient descent or projection techniques) we use non-linear submodular
approximations and optimize them without leaving the domain of integer
solutions. We discuss two specific LSA algorithms based on "trust region" and
"auxiliary function" principles, LSA-TR and LSA-AUX. These methods obtain
state-of-the-art results on a wide range of applications outperforming many
standard techniques such as LBP, QPBO, and TRWS. While our paper is focused on
pairwise energies, our ideas extend to higher-order problems. The code is
available online (http://vision.csd.uwo.ca/code/).
