Skip to Main content Skip to Navigation
Conference papers

Reduce, reuse & recycle: Efficiently solving multi-label MRFs

Abstract : 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 α-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 α-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 α-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 α-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.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Karteek Alahari Connect in order to contact the contributor
Submitted on : Monday, October 19, 2015 - 12:19:19 PM
Last modification on : Monday, September 20, 2021 - 3:02:06 PM
Long-term archiving on: : Thursday, April 27, 2017 - 6:53:54 AM


Files produced by the author(s)



Karteek Alahari, Pushmeet Kohli, Philip H. S. Torr. Reduce, reuse & recycle: Efficiently solving multi-label MRFs. CVPR - IEEE Conference on Computer Vision & Pattern Recognition, Jun 2008, Anchorage, United States. ⟨10.1109/CVPR.2008.4587402⟩. ⟨hal-01217303⟩



Record views


Files downloads