Optimizing binary MRFs via extended roof duality.pdfVIP

Optimizing Binary MRFs via Extended Roof Duality Technical Report MSR-TR-2007-46 Carsten Rother 1 , Vladimir Kolmogorov 2 , Victor Lempitsky 3 , Martin Szummer 1 1 Microsoft Research Cambridge {carrot, szummer}@ 2 University College London vnk@adastral.ucl.ac.uk 3 Moscow State University victorlempitsky@ /vision/cambridge/ Abstract Many computer vision applications rely on the efficient optimization of challenging, so-called non-submodular, bi- nary pairwise MRFs. A promising graph cut based ap- proach 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 intro- duced recently by Boros et al. [8]. It simplifies the MRF while preserving the global optimum. Our code is 400-700 faster on some graphs than the implementation of [8]. Sec- ond, we present a new technique which takes an arbitrary input labeling and tries to improve its energy. We give theo- retical characterizations of local minima of this procedure. We applied both techniques to many applications, in- cluding image segmentation, new view synthesis, super- resolution, diagram recognition, parameter learning, tex- ture restoration, and image deconvolution. For several ap- plications we see that we are able to find the global mini- mum very efficiently, and considerably outperform the orig- inal roof duality approach. In comparison to existing tech- niques, such as graph cut, TRW, BP, ICM, and simulated annealing, we nearly always find a lower energy. 1. Introduction Most early vision problems can be formulated in terms of Markov random fields (MRFs). Algorithms for MRF in- ference therefore are of fundamental importance for com- puter vision. The MAP-MRF approach (computing maxi- mum a posteriori configurations in an MRF) has proven to be extremely successful for many vision applications such as stereo, image segmentation, image denoising, super- r