Abstract

Many computer vision problems require optimization of binary non-submodular energies. We propose a general op-timization framework based on local submodular approximations (LSA). Unlike standard LP relaxation methods thatlinearize the whole energy globally, our approach itera-tively 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 ener-gies, our ideas extend to higher-order problems. The code is available online 1 .