  Discrete energy minimization is a ubiquitous task in computer vision, yet is
NP-hard in most cases. In this work we propose a multiscale framework for
coping with the NP-hardness of discrete optimization. Our approach utilizes
algebraic multiscale principles to efficiently explore the discrete solution
space, yielding improved results on challenging, non-submodular energies for
which current methods provide unsatisfactory approximations. In contrast to
popular multiscale methods in computer vision, that builds an image pyramid,
our framework acts directly on the energy to construct an energy pyramid.
Deriving a multiscale scheme from the energy itself makes our framework
application independent and widely applicable. Our framework gives rise to two
complementary energy coarsening strategies: one in which coarser scales involve
fewer variables, and a more revolutionary one in which the coarser scales
involve fewer discrete labels. We empirically evaluated our unified framework
on a variety of both non-submodular and submodular energies, including energies
from Middlebury benchmark.
