Dynamic Hybrid Algorithms for MAP Inference in Discrete 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 alpha-expansion) works by `recycling' results from previous problem instances. The second method simplifies the energy function by `reducing' the number of unknown variables present in the problem. Further, we show that it 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. We also demonstrate the applicability of our schemes for certain higher order energy functions, such as the one described in Kohli et al. 2009, for interactive texture based image and video segmentation. 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, but is conceptually much simpler. Both alpha-expansion and Fast-PD can be made orders of magnitude faster when used in conjunction with the `reduce' scheme proposed in this paper.
Type de document :
Article dans une revue
IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 2010, 32 (10), 〈10.1109/TPAMI.2009.194〉
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01216727
Contributeur : Karteek Alahari <>
Soumis le : vendredi 16 octobre 2015 - 18:02:49
Dernière modification le : lundi 19 octobre 2015 - 16:28:25
Document(s) archivé(s) le : jeudi 27 avril 2017 - 06:08:53

Fichier

alahari10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Karteek Alahari, Pushmeet Kohli, Philip H. S. Torr. Dynamic Hybrid Algorithms for MAP Inference in Discrete MRFs. IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 2010, 32 (10), 〈10.1109/TPAMI.2009.194〉. 〈hal-01216727〉

Partager

Métriques

Consultations de la notice

39

Téléchargements de fichiers

59