In this paper, we present novel techniques that improve the computational and
memory efficiency of algorithms for solving multi-label energy functions arising
from discrete MRFs or CRFs. These methods are motivated by the observations that
the performance of minimization algorithms depends on: (a) the initialization
used for the primal and dual variables; and (b) the number of primal variables
involved in the energy function. Our first method (dynamic alpha-expansion)
works by `recycling' results from previous problem instances. The second method
simplifies the energy function by `reducing' the number of unknown variables,
and can also be used to generate a good initialization for the dynamic
alpha-expansion algorithm by `reusing' dual variables.

We test the performance of our methods on energy functions encountered in the
problems of stereo matching, and colour and object based segmentation.
Experimental results show that our methods achieve a substantial improvement in
the performance of alpha-expansion, as well as other popular algorithms such as
sequential tree-reweighted message passing, and max-product belief propagation.
In most cases we achieve a 10-15 times speed-up in the computation time. Our
modified alpha-expansion algorithm provides similar performance to Fast-PD.
However, it is much simpler and can be made orders of magnitude faster by using
the initialization schemes proposed in the paper.