Many computer vision applications rely on the efficient
optimization of challenging, so-called non-submodular, binary
pairwise MRFs. A promising graph cut based approach
for optimizing such MRFs known as "roof duality"
was recently introduced into computer vision. We study two
methods which extend this approach. First, we discuss an
efficient implementation of the "probing" technique introduced
recently by Boros et al. [5]. It simplifies the MRF
while preserving the global optimum. Our code is 400-700
faster on some graphs than the implementation of [5]. Second,
we present a new technique which takes an arbitrary
input labeling and tries to improve its energy. We give theoretical
characterizations of local minima of this procedure.
We applied both techniques to many applications, including
image segmentation, new view synthesis, superresolution,
diagram recognition, parameter learning, texture
restoration, and image deconvolution. For several applications
we see that we are able to find the global minimum
very efficiently, and considerably outperform the original
roof duality approach. In comparison to existing techniques,
such as graph cut, TRW, BP, ICM, and simulated
annealing, we nearly always find a lower energy.