UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Optimizing binary MRFs via extended roof duality

Rother, C; Kolmogorov, V; Lempitsky, V; Szummer, M; (2007) Optimizing binary MRFs via extended roof duality. In: 2007 IEEE CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION, VOLS 1-8. (pp. 1784 - 1791). IEEE

Full text not available from this repository.


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.

Type:Proceedings paper
Title:Optimizing binary MRFs via extended roof duality
Event:IEEE Conference on Computer Vision and Pattern Recognition
Location:Minneapolis, MN
Dates:2007-06-17 - 2007-06-22
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record