  We consider the task of obtaining the maximum a posteriori estimate of
discrete pairwise random fields with arbitrary unary potentials and semimetric
pairwise potentials. For this problem, we propose an accurate hierarchical move
making strategy where each move is computed efficiently by solving an st-MINCUT
problem. Unlike previous move making approaches, e.g. the widely used
a-expansion algorithm, our method obtains the guarantees of the standard linear
programming (LP) relaxation for the important special case of metric labeling.
Unlike the existing LP relaxation solvers, e.g. interior-point algorithms or
tree-reweighted message passing, our method is significantly faster as it uses
only the efficient st-MINCUT algorithm in its design. Using both synthetic and
real data experiments, we show that our technique outperforms several commonly
used algorithms.
